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

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

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.