Re: [Trans] [ct-policy] Re: Certificate Transparency Mirrors (experimental)

[Florian MAURY <[e-mail]>]

Hi lists,

I decided to discuss this in private with Pierre, so that we would not
spam the list. Here is a summary of our conversation. Pierre, please
feel free to comment that report, in case I missed something or if the
report is inaccurate.

Pierre statement in the previous email is accurate. One could request
a consistency proof between a subtree and the latest tree head to
check if this subtree contains corrupted data or not. This is an
efficient way to detect which entry or set of entries are invalid.
Current Google implementations (and some others) are willing to return
such proofs. It is however noteworthy that this behavior is not
required by RFC6962 and RFC69626-bis current draft. These documents
only require that logs be able to return consistency proofs between
STHs. This requirement is probably to allow precomputation to limit
abusive behavior impacts on log load. Since all subtree roots are not
necessarily STHs, the consistency checks suggested by Pierre are nice
to have but cannot be expected from all logs.

We both agreed that it would be great to have some way to find out
previous STH. I would suggest adding a tree_size optional parameter to
the v2 get-sth endpoint. If present, the returned STH would be the STH
with the greatest tree_size inferior to the tree_size parameter. I
have not given it much thoughts and this might not be a good idea.
Anyway, this is probably not the right place to discuss this.

Pierre's suggestion to use inclusion proofs to verify that a specific
entry is consistent is an excellent idea. However, if you don't know
for sure which entry or set of entries are corrupted, then we agreed
that this check method is less efficient than downloading everything
all over again.

Finally, Pierre suggested that computing the root hash from the
downloaded entries is not sufficient to ensure an entry consistency.
Indeed, downloaded data include an extra_data field that should be
checked too, by verifying the signature chain up to a trust anchor.
This is an excellent idea that I added on my TODO list. Thanks!

Cheers,
Florian

On Fri, Nov 4, 2016 at 3:28 PM, Pierre Phaneuf <[e-mail]> wrote:
> On Fri, Nov 4, 2016 at 1:42 PM, Florian M. <[e-mail]> wrote:
>
>> if, for whatever reason, a get-entries response is corrupted, the root hash
>> will be incorrect. If the user has no access to intermediate STH, there is
>> no way to narrow down and track the corrupted get-entries result. The user
>> can only start over.
>
> That's not entirely true, there's a strategy you can use to find where
> the corruption occurred.
>
> If the root hash of the whole Merkle tree doesn't compute correctly,
> you can do a binary search for the corrupted entry, by using the
> MerkleTree::RootAtSnapshot method in the C++ implementation (for
> example) to compute the root hash of your tree at half the size, and
> do a get-sth-consistency between that tree size and the full one. If
> the proof applies correctly, then you know the entries below are good,
> and you can repeat the operation, until you isolate the tree size that
> stops validating with the consistency proof. You could then drop all
> the entries from there on and resume from there (simpler), or maybe
> just re-fetch a chunk and recompute the Merkle tree (hoping the
> corruption was localised).
>
> You can also spot check single entries using inclusion proofs.