Re: [Cfrg] LDWM implementation questions (Hash-Based Signatures - draft-mcgrew-hash-sigs-02)

[Szabó Áron <[e-mail]>]

Dear Members,

after re-reading the draft-mcgrew-hash-sigs-02, and implementing the described algorithms I know, that my previous questions were non-understandable in this context (sorry about this). Now, I collected some parts of the draft that are still seem to be not so clear. Some of them seem to be mistakes, and others need just more clarification.

1)
The section "3.3. Signature Methods" contains "n = 32" (instead of "n = 64"?) in the rows of "LDWM_SHA512_M64_W*", where "H = SHA512".

2)
The section "3.3. Signature Methods" contains "m = 32" (instead of "m = 64"?) in the rows of "LDWM_SHA512_M64_W*", where "F = SHA512".

3)
The section "3.4. Private Key" contains "array of size p containing m-byte strings" but Table 6 (test vectors of private key) lists 32 byte long strings such as "x[0] = 0xbfb757383fb08d324629115a84daf00b188d5695303c83c184e1ec7a501c431f" instead of "m = 20" byte long strings. Also "Algorithm 0: Generating a Private Key" does not refer to "F = SHA256-20", this function is applied just at "Algorithm 1: Generating a Public Key From a Private Key" and "Algorithm 3: Generating a Signature From a Private Key and a Message". So, signature and public key contains "array of size p containing m-byte strings" as chunks, but in the given example private key does not contain "uniformly random m-byte string" chunks.

4)
The section "3.6. Checksum" contains "Thus for the purposes of this document [...] let sum be a 16-bit non-negative integer for all combinations of n and w." Based on the expression "ls = (number of bits in sum) - (v * w)" and values of Table 4, the "number of bits in sum" is exactly always a "16-bit non-negative integer". If there may be no other value for "number of bits in sum" then perhaps this statement could be expressed harder.

5)
The section "3.6. Checksum" contains "The checksum function C is defined as follows, where S denotes the byte string that is input to that function." but perhaps it should clearly state that "S = H(message)".

Bonus question:
The draft says, that "Expires: January 5, 2015". What is the future plan of this draft? When will draft-mcgrew-hash-sigs-03 or a final RFC published?

Best regards,
Aron


---

Dear Members,

I am not a mathematician, but as a developer some questions came up during implementation the LDWM algorithm of standard draft (https://tools.ietf.org/html/draft-mcgrew-hash-sigs-02). Please, explain things that I imagine/understand wrong! Thx!

a)
"The LDWM public key is generated from the private key by applying the function F^(2^w - 1) to each individual element of x, then hashing all of the resulting values."

If I understand well the notations, "m" stands for length of (private) key chunks assigned as signature chunks based on the 0/1 value of H(message) "i"th bit (e.g. 256 bits in case of SHA-256, or 512 bits in case of SHA-512) and "n" stands for length of H(message) (e.g. 256 bits in case of SHA-256, or 512 bits in case of SHA-512).

In case of n=length(H(message)), there are no restrictions to the output length and the applied hash algorithm. It is also true in case of m=length(private_key_chunk[i]), but Winternitz parameter - { 1, 2, 4, 8 } - shall be applied to derive public_key_chunk[i] values before hashing (as I saw the pseudo-code in the draft). But why is this transformation specified as a "MUST" requirement? I mean, if I have a restriction that I shall not lose entropy at any sub-step of implementing the algorithm (e.g. because of Grover's algorithm) how can I use e.g. SHA-512 public keys as they are (without any kind of key size reduction) if the maximum value is just w=8 (2^8=256 bits)? So, shall/can I use e.g. w=16? Or is there any way to skip the size reduction sub-step of derived public keys in the pseudo-code (e.g. by inserting an "if-else" in it)?

b)
"A checksum is used to ensure that any forgery attempt that manipulates the elements of an existing signature will be detected."

Could you explain what the exact reason, and added value of this checksum is? I found nothing about this in the core descriptions of Lamport-Diffie one-time signature scheme in Bernstein-Buchmann-Dahmen's book. OK, I understand that this provides an easy way to pre-check signature validity before computing all the needed hashes (good from "developer" viewpoint), but if it is not a core step of algorithm (seeing from "mathematician" viewpoint), then I think this should be just an optional thing, isn't it? I have already read "8.1. Security of LDWM Checksum" section where it is described that "an attacker may try to change the values of h and c" and "then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j]" which is the array of public key chunks. But if I assume a trusted-third-party model (e.g. trusted CAs issuing signed public keys as X.509 certificates) the alteration of end user public keys is not possible (OK, hacking the whole trusted chain or finding a new PRNG backdoor w
 ould provide a solution, of course, but now I think about the expected way of operation). So, in case of public key chunks are signed by some kind of CA, perhaps performing and concatenating this C(H(message)) can be avoided...

c)
>From the developer and user viewpoint: beyond the specification of the core algorithm, I think the IETF RFC 5280 (X.509) and/or IETF RFC 3447 (PKCS#1) standard (or maybe this draft itself) shall be modified with an update/amendment in order to describe the exact ASN.1 data structures of private/public keys and created signatures. I know that CA softwares, and applied crypto libraries will not implement these modifications immediately, but for development and testing reasons it would be important to involve these now. (As I see, the OID of algorithm - which is important part of SubjectPublicKeyInfo - is already defined: 1.2.840.113549.1.9.16.3.17.X). So, could you also define the ASN.1-level data structures? (see my attempt below)

LDWMPublicKey ::= SEQUENCE {
 version Version,
 algorithm AlgorithmIdentifier,
 keyChunks KeyChunks,
 otherInfo OtherInfo OPTIONAL
}

LDWMPrivateKey ::= SEQUENCE {
 version Version,
 algorithm AlgorithmIdentifier,
 keyChunks KeyChunks
}

LDWMSignature ::= SEQUENCE {
 version Version,
 signatureChunks KeyChunks,
 checksum Checksum OPTIONAL
}

Version ::= INTEGER { v1(0) }

AlgorithmIdentifier ::= SEQUENCE {
 algorithm OBJECT IDENTIFIER,
 parameters ANY DEFINED BY algorithm OPTIONAL
}

KeyChunks ::= SEQUENCE SIZE(1..MAX) OF KeyChunk

KeyChunk ::= SEQUENCE {
 chunk0 BIT STRING,
 chunk1 BIT STRING
}

OtherInfo ::= SEQUENCE {
 winternitz INTEGER,
 keyDerivation AlgorithmIdentifier OPTIONAL
}

Checksum ::= SEQUENCE {
 checksumCalculation AlgorithmIdentifier,
 leftShiftBits INTEGER
}

Best regards,
Aron Szabo

P.S.: I apologise for that if you get this e-mail twice.