Re: [Cfrg] draft-mcgrew-hash-sigs implementation and findings

["Paterson, Kenny" <[e-mail]>]

Dear Paul,

Many thanks for this report - it's excellent to have another implementation, but equally excellent that you shared your implementation experiences based on the draft.

Authors: it seems like there's quite a few things here that should be cleaned up.

Thanks,

Kenny 

-----Original Message-----
From: Cfrg <[e-mail]> on behalf of Paul Selkirk <[e-mail]>
Date: Sunday, 18 March 2018 at 16:35
To: "[e-mail]" <[e-mail]>
Subject: [Cfrg] draft-mcgrew-hash-sigs implementation and findings

    I'm pleased to announce a clean-room implementation of
    draft-mcgrew-hash-sigs-10. There are actually two flavors: 1) a naive
    implementation that adheres as closely as possible to the text and
    pseudo-code of the draft (including storing keys in xdr format); and 2)
    a version that is targeted to the CrypTech prototype HSM, with AES
    keywrapping for the keys, and using our own hash implementation and
    hardware-based RNG.
    
    Code is available at:
    https://wiki.cryptech.is/browser/user/paul/hashsig-naive
    https://wiki.cryptech.is/browser/sw/libhal
    
    Most of my previous comments on draft-08 (email to group on 13 November
    2017) still stand, and have not been addressed in -09 or -10. Most of
    those comments are editorial in nature, and I won't belabor them here.
    
    What I will belabor is the pseudo-code (including lack of it), because
    that's essential for properly implementing the draft. The pseudo-code is
    generally complete and correct for LM-OTS, a little sloppier for LMS,
    and mostly missing for HSS.
    
    Section 4.4, Algorithm 1, step 2: n is not used here.
    
    Section 4.7, Algorithm 4a, missing step: set n p according to the
    pubtype and Table 1.
    
    Section 5.2, Algorithm 5, step 1: m is not used here.
    
    Section 5.2, Algorithm 5, missing step: generate I for this keypair.
    
    Section 5.2, Algorithm 5, missing step: return u32str(type) || u32str(q)
    || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1]
    
    Section 5.3, missing pseudo-code. I suggest something like the following:
    
      1. determine LMS type, LM-OTS type, and I from private key
    
      2. set h from the LMS type code and Table 2
    
      3. compute the hash value of each leaf node as follows:
         r = 2^(h+1) - 1
         while (r >= 2^h) {
           T[r] = H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB[r-2^h])
           r = r - 1
         }
    
      4. compute the hash value of each inner node as follows:
         r = 2^h - 1
         while (r > 0) {
           T[r] = H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])
           r = r - 1
         }
    
      5. return u32str(type) || u32str(otstype) || I || T[1]
    
    Section 5.4.1, missing pseudo-code. I suggest something like the following:
    
      1. set type to the typecode of the LMS algorithm
    
      2. create the LM-OTS signature for the message:
         ots_signature = ots_sign(message, LMS_PRIV[q])
    
      3. compute the array path as follows:
         r = 2^h + q
         i = 0
         while (r > 1) {
           if (r is odd):
             path[i] = T[r-1]
           else
             path[i] = T[r+1]
           r = r/2
           i = i + 1
         }
    
      4. S = u32str(q) || ots_signature || u32str(type) || path[0] ||
    path[1] || ... || path[h-1]
    
      5. q = q + 1
    
      6. return S
    
    Section 5.4.2, Algorithm 6a, step 2e: "ots_signature = bytes 8 through 8
    + n * (p + 1) - 1 of signature". This is actually the remainder of
    ots_signature after otssigtype. The full ots_signature would be bytes 4
    through 8 + n * (p + 1) - 1.
    
    Section 6.1, missing pseudo-code. I suggest something like the following:
    
      1. generate L LMS key pairs, as specified in sections 5.2 and 5.3
    
      2. sign each child public key with the private key of its parent:
         i = 0
         while (i < L-1) {
           sig[i] = lms_sign(LMS_PUB[i+1], LMS_PRIV[i])
           i = i + 1
         }
    
      3. return u32str(L) || LMS_PUB[0]
    
    Section 6.2: missing pseudo-code. I suggest something like the following:
    
      1. If the message-signing key LMS_PRIV[L-1] is exhausted, regenerate
         that key pair, together with any parent key pairs that might be
         necessary. If the root key pair is exhausted, then the HSS key pair
         is exhausted, and it MUST NOT generate any more signatures.
    
         if (LMS_PRIV[L-1].q == 2^h) {
           d = L-1
           while (LMS_PRIV[d-1].q == 2^h) {
             if (d == 0)
               return FAILURE
             d = d - 1
           }
           while (d < L) {
             regenerate keypair LMS_PRIV[d], LMS_PUB[d]
             sig[d-1] = lms_sign(LMS_PUB[d], LMS_PRIV[d-1])	
           }
         }
    
      2. Sign the message
         sig[L-1] = lms_sign(msg, LMS_PRIV[L-1])
    
      3. Create the list of signed public keys
         i = 0
         while (i < L-1) {
           signed_pub_key[i] = sig[i] || LMS_PUB[i+1]
           i = i + 1
         }
    
      4. return u32str(L-1) || signed_pub_key[0] || ... ||
    signed_pub_key[L-2] || sig[L-1]
    
    Section 6.3: missing an Algorithm number and heading.
    
    Other things I noted while implementing:
    
    The python implementation at http://github.com/davidmcgrew/hash-sigs/ is
    badly out of date (draft-05), and either the code should be updated or
    the reference should be removed from the draft.
    
    The History for Version 05 (which really means changes from 05 to 06?)
    refers to SPHINCS, which also shows up as an Informative Reference, but
    the text mentioning SPHINCS was removed in -08.
    
    In the LMS signature, it's odd that q is first and lms_type is after the
    ots_sig. For consistency, I'd expect something more like
      u32str(lms_type) || ots_signature || u32str(q) || path[0] || ...
    
    However, that would be an incompatible change to the protocol, which I
    don't expect to happen at this late date. I just wanted to flag it as
    something unexpected.
    
    _______________________________________________
    Cfrg mailing list
    [e-mail]
    https://www.irtf.org/mailman/listinfo/cfrg