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

From: Paul Selkirk <[email-masked]>
Date: Sun, 18 Mar 2018 12:35:28 -0400

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.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sun, 18 Mar 2018 19:21:19 +0000

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 <[email-masked]> on behalf of Paul Selkirk <[email-masked]>
Date: Sunday, 18 March 2018 at 16:35
To: "[email-masked]" <[email-masked]>
Subject: [Cfrg] draft-mcgrew-hash-sigs implementation and findings

    Code is available at:

    

    

    

    

    

    
    
      5. q = q + 1
    
      6. return S

    

    

    
      2. Sign the message

    

    

    
    _______________________________________________
    Cfrg mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/cfrg