Subject: [Trans] Verifying inclusion proof

From: Ondrej Mikle <[email-masked]>
Date: Fri, 26 Jun 2015 16:29:50 +0200

Pardon me if I am asking something obvious, but I'm missing one piece of
information for inclusion proof verification - the "placement" of each
node returned from "get-proof-by-hash" method in audit_path list
(whether it's left subtree or right subtree).

Since the hashing of concatenation of strings is not commutative, the
auditor needs to put the two partial tree hashes in correct order to get
to the correct root hash.

I'd guess the placement of the missing nodes from audit_path could be
derived from leaf_index and tree_size, but can't see a straightforward
way to do it. The reference client does not implement this verification
either.

Ondrej

---

From: Adam Eijdenberg <[email-masked]>
Date: Fri, 26 Jun 2015 16:02:22 +0000

Hi Ondrej,

I had the exact same question last week when I started wanted to verify
get-proof-by-hash.  It turns out that you actually can figure out which is
applied to the left and the right by looking the bits in the index of the
log entry that you are requesting proof for.  I found it easier to describe
in code than words.  Take a look at the following Python that fetches an
arbitrary entry from an arbitrary log, then fetches the current STH, then
requests an inclusion proof and finally verifies that proof.

I hope that helps.

Cheers, Adam

import urllib, urllib2, json, base64, hashlib

# Entry to play with
log_entry = 438942
log = 'ct.googleapis.com/pilot'

# Get the merkle tree leaf and b64 decode it
entries = json.loads(urllib2.urlopen('https://%s/ct/v1/get-entries?%s' %
(log, urllib.urlencode({'start': log_entry, 'end': log_entry}))).read())
mtl = base64.b64decode(entries['entries'][0]['leaf_input'])

# Get current STH
sth = json.loads(urllib2.urlopen('https://%s/ct/v1/get-sth' % log).read())

# Create the leaf hash
leaf_hash = hashlib.sha256(chr(0) + mtl).digest()

# Fetch proof that the leaft hash is included in the current STH
url = 'https://%s/ct/v1/get-proof-by-hash?%s' % (log,
urllib.urlencode({'hash': base64.b64encode(leaf_hash), 'tree_size':
sth['tree_size']}))
proof = json.loads(urllib2.urlopen(url).read())

# Derive the sha256 root hash based on the leaf_hash and the audit_proof
node = leaf_hash
idx = log_entry
for p in proof['audit_path']:
  if idx & 1:
    node = hashlib.sha256(chr(1) + base64.b64decode(p) + node).digest()
  else:
    node = hashlib.sha256(chr(1) + node + base64.b64decode(p)).digest()
  idx >>= 1

if node == base64.b64decode(sth['sha256_root_hash']):
  print 'Log proved inclusion'
else:
  print 'Fail.'

On Fri, Jun 26, 2015 at 7:30 AM Ondrej Mikle <[email-masked]> wrote:

> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans
>

---

From: Al Cutter <[email-masked]>
Date: Fri, 26 Jun 2015 16:27:37 +0100

> to the correct root hash.

Yes, you're quite right.

> way to do it. The reference client does not implement this verification
There are a couple of implementations of this in the o/s code base:
C++ is in cpp/merkletree/merkle_verifier.cc
<https://github.com/google/certificate-transparency/blob/master/cpp/merkletree/merkle_verifier.cc>
(see
VerifyPath())
Python is in python/ct/crypto/merkle.py
<https://github.com/google/certificate-transparency/blob/master/python/ct/crypto/merkle.py>
 (see verify_leaf_inclusion())

HTH.

Cheers,
Al.

-- 
Google UK Ltd | 123 Buckingham Palace Road | London SW1W 9SH | Registered
in England Number: 3977902

---

From: Stephen Kent <[email-masked]>
Date: Sun, 28 Jun 2015 11:05:01 -0400

IETF standards need to be unambiguous. Code is very helpful, but it is 
not a substitute
for a rigorous description of how to resolve the issue that Onderj raised.

Steve
>
> On Fri, Jun 26, 2015 at 3:29 PM, Ondrej Mikle <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
> <https://github.com/google/certificate-transparency/blob/master/cpp/merkletree/merkle_verifier.cc> (see 
> VerifyPath())
> <https://github.com/google/certificate-transparency/blob/master/python/ct/crypto/merkle.py> (see 
> verify_leaf_inclusion())
>
> HTH.
>
> Cheers,
> Al.
>
>     Ondrej
>
>     [email-masked] <mailto:[email-masked]>
> Google UK Ltd | 123 Buckingham Palace Road | London SW1W 9SH | 
> Registered in England Number: 3977902
>
>

---

From: Ben Laurie <[email-masked]>
Date: Sun, 28 Jun 2015 16:26:51 +0100

On 28 June 2015 at 16:05, Stephen Kent <[email-masked]> wrote:
> IETF standards need to be unambiguous. Code is very helpful, but it is not a
> substitute

Whilst I am not necessarily opposed to that, there has to be a point
at which you stop explaining what can be worked out given existing
information. The RFC does state how the hash is calculated, from which
it is clear what the placement of each node is in the hash
calculation.

---

From: Matt Palmer <[email-masked]>
Date: Mon, 29 Jun 2015 08:06:48 +1000

> it is clear what the placement of each node is in the hash

s/it is clear/it is possible to determine/

I would be in favour of more clarity around exactly how the inclusion proof
is represented; I recall having significant trouble comprehending how
inclusion proofs "worked", and ended up examining existing operational logs
and using trial and error to determine how the inclusion proof was
presented.

- Matt

---

From: Ben Laurie <[email-masked]>
Date: Mon, 29 Jun 2015 12:29:47 +0100

> and using trial and error to determine how the inclusion proof was

Feel free to open a ticket. However, the mechanism for verifying
inclusion in a Merkle tree is widely available in standard texts, for
example 3.3 in http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf.

---

From: Stephen Kent <[email-masked]>
Date: Mon, 29 Jun 2015 14:21:07 -0400

Ben,

> On 28 June 2015 at 16:05, Stephen Kent<[email-masked]>  wrote:
My comment is based on the question that was posed by someone for
whom it was not clear. If most other (independent) implementers find
the text clear enough, OK.

Citing a tech paper is not the preferred approach for IETF docs. We
often reproduce info that is available via other means, so that RFCs
are as self-contained as possible.

Steve

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 29 Jun 2015 15:17:33 -0400

On Mon, Jun 29, 2015 at 2:21 PM, Stephen Kent <[email-masked]> wrote:

>>> not a

As a general rule, placement and organization does not matter.

If someone gives you the apex value of the tree and the sequence of branch
values and whether they are left or right, you have all the info required
to verify.

While the spec says 'Merkle tree', all that is required for interop is to
deliver the correct branches.

---

From: Matt Palmer <[email-masked]>
Date: Tue, 30 Jun 2015 09:04:58 +1000

> example 3.3 in http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf.

That document doesn't appear to be referenced in 6962bis, nor would it, I
assume, answer the question "how is the inclusion proof represented in the
response to get-sth-consistency".

- Matt

---

From: Ben Laurie <[email-masked]>
Date: Tue, 30 Jun 2015 13:30:12 +0100

On 29 June 2015 at 20:17, Phillip Hallam-Baker <[email-masked]> wrote:
> values and whether they are left or right, you have all the info required to
> verify.

CT does not tell you left or right, since you can work it out from the index.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 30 Jun 2015 13:30:32 +0100

> response to get-sth-consistency".

Fair enough. Do you have proposed text?

---

From: Adam Eijdenberg <[email-masked]>
Date: Tue, 30 Jun 2015 17:05:14 +0000

On Tue, Jun 30, 2015 at 5:30 AM Ben Laurie <[email-masked]> wrote:

> >> example 3.3 in
> http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf
> .
> >

Would the following text be helpful for /get-proof-by-hash? (I realize the
immediate question refers to get-sth-consistency, I'd be happy to tackle
that next)

To verify the Merkle Tree root hash for the tree_size provided as input, a
client can use the hash provided as input combined with applying the
audit_path and leaf_index returned as output in the following manner (note,
all values must be base64 decoded first):

1. Set the intermediate result "r" to hash.

2. For each "i" from 0 up to LENGTH(audit_path) - 1:

   If the least significant bit of (leaf_index >> i) is set, then:

   a. Set r to HASH(0x01 || audit_path[i] || r)

   otherwise:

   b. Set r to HASH(0x01 || r || audit_path[i])

3. Return r

If "r" is equal to the root hash previously returned by /get-sth for the
same tree_size that was passed as input, then the log has successfully
proven the inclusion of the certificate that the Merkle tree leaf hash was
constructed from.

---

From: Matt Palmer <[email-masked]>
Date: Wed, 1 Jul 2015 09:49:28 +1000

> Fair enough. Do you have proposed text?

Not at the present time.  I'll add it to the todo list.

- Matt