Subject: [therightkey] What next for CT?

From: Ben Laurie <[email-masked]>
Date: Tue, 20 Nov 2012 12:33:23 +0000

Dear Group,

Following the recent BoF and discussion with Stephen Farrell, the plan
is to try to publish an experimental RFC for CT and, all going well,
follow up later with a WG.

In the experimental RFC we will cover the operation of the log, the
log protocol and TLS client verification of CT. We will be
specifically targetting the use of CT with PKI for HTTPS, and not
other applications such as DNSSEC, self-signed certs, device certs,
other TLS secured protocols, etc. Not that we exclude the possibility
of using transparency logs for such things, of course, they just will
not be covered by this initial RFC.

The RFC will be broadly similar the existing I-D but will flesh out
the protocols for interacting with the log, as far as they are
currently defined. It will add RSA signatures for logs that would
prefer to use it.

It will not cover details of the audit process (that is, how clients
verify that the timestamps they see really are included in the public
log) as we think that will evolve quite rapidly for some time to come.

The approximate timeline is that we hope to go to IETF last call
around the end of the year.

I intend to put out at least one more version for comment before that,
though.

As always, all comments are welcome.

Cheers,

Ben.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 20 Nov 2012 08:03:32 -0500

I think there should be two separate drafts.

1) Cover the technical spec describing how the notary log system works, the
data formats etc.
2) Cover the use of the scheme in the context of PKIX.

(1) is then reusable to other applications.

Phill

On Tue, Nov 20, 2012 at 7:33 AM, Ben Laurie <[email-masked]> wrote:

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

-- 
Website: http://hallambaker.com/

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 20 Nov 2012 13:07:07 +0000

Hi Phill,

Not sure what Ben thinks of that but I'd rather
just AD sponsor one draft for now. A split like
that would definitely make sense for the
standards-track work that's envisaged to follow
though. Do you think that's really a must-have
at this stage? I guess I don't, as of now.

Cheers,
S.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 20 Nov 2012 13:14:29 +0000

> at this stage? I guess I don't, as of now.

My view is that teasing the two parts apart is hard and so I agree it
would be good for standards track, but don't want to do it for
experimental.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 20 Nov 2012 08:17:23 -0500

> would be good for standards track, but don't want to do it for

My objective was to get the two parts teased apart rather than the
presentation as separate documents.

I think the exercise would improve the clarity of the spec.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 20 Nov 2012 15:09:24 +0000

> I think the exercise would improve the clarity of the spec.

Its still hard :-)

I'll see what I can do, though.

---

From: Paul Lambert <[email-masked]>
Date: Wed, 28 Nov 2012 13:46:23 -0800

In the current draft, there may be some minor errors in the description of the algorithms or confusion on my side on the nature of the notation.

The notation would be much clearer if the merkle tree nodes were indexed by the tuple representing the range of the hashed values covered by the node.

I've attached below an alternate description of the trees showing the correspondence of the nodes to the range tuple and a short summary of the algorithms using this notation.

Paul

PS - will publish associated Python code eventually

           0,3              0,4
          __|__            __|__ 
         /     \          /     \
       0,2     2,3      0,2     2,4
      /   \     |       / \     / \
    0,1   1,2  d2     0,1 1,2 2,3 3,4
     |     |           |   |   |   |
    d0    d1          d0  d1  d2  d3 
  
   Each hash in the tree can be identified as a tuple representing the range
   of values covered by the hash.
   
   For a Merkle Hash Tree with n leaf nodes and each i,j node
   identified by mth(i,j):
    - the root hash, MTH = mth(0,n)
    - the leaf hash for data entry di with 0<=i<n is mth(i,i+1)
    - leaf values are formed by hashing the input string d(i)
        mth(i,i+1) = hash( 0 | d(i))
        This is a hash of the single octet with value 0 concatenated with
        the ith input string d(i)
    - every non-leaf node mth(k1,k2) has the property that
        mth(k1,k2) = hash( 1 | mth(k1,k) | mth(k,k2) )
        where k = k1+lp2(k2-k1) , and lp2(i) is the largest power of 2 < i
    - new entries are added to the tree by:
      creating a leaf node
        mth(i,i+1) = hash( 0 | d(i))
      creating a new root hash
        mth(0,i+1) = hash( 1 + mth(k1,k) | mth(k,k2))
      recursively creating any mth(i,j) needed for the new root hash
    - an empty tree has a root hash value formed by hashing
      a null string, hash('')
      
   For n > 1, the audit path for the (m+1)th element d(m) in a list 
   of n > m elements is found by the recursive function:  
   
   PATH(m, D[0:n])

   Where:

   PATH(m, D[k1,k2]) = {} for (k2-k1)=1

   k = k1 + largestPower2(k2-k1)
   
   PATH(m, D[k1:k2]) = PATH(m, D[k1:k]) : MTH(D[k:k2]) for m < k; and
   
   PATH(m, D[k1:k2]) = PATH(m, D[k:k2]) : MTH(D[k1:k]) for m >= k,

                  0,7
             ______|______
            /             \   
          0,4             4,7           
         __|__           __|__
        /     \         /     \
      0,2     2,4     4,6     6,7
      / \     / \     / \      |
    0,1 1,2 2,3 3,4 4,5 5,6   d6
     |   |   |   |   |   |
    d0  d1  d2  d3  d4  d5  
   
   The audit path for d0 is [mth(1,2), mth(2,4), mth(4,7)].
   The audit path for d3 is [mth(2,3), mth(0,2), mth(4,7)].
   The audit path for d4 is [mth(5,6), mth(6,7), mth(0,4)].
   The audit path for d6 is [mth(4,6), mth(0,4)].