Is Lamport OTS improved by using HMAC?

Question

One problem with Lamport OTS is that the attacker can repeatedly try random inputs and there is a chance that a hash of a random input will match one of a large set of public keys, reducing the security margin somewhat.

But suppose the public key for the ith bit is calculated as [ TRUNCATE-128(HMAC(S0,i||"0")) , TRUNC-128(HMAC-SHA256(S1,i||"1")) ].

The sender reveals S0 or S1.

Now the verifier expects not just any string that hashes to the given value, but is given a key Sx (either S0 or S1) and expects TRUNC-128(HMAC-SHA256(Sx,i||bitvalue)) to evaluate to the public key part for that bit value.

Now the attacker cannot simply generate random strings and have them match potentially multiple public keys.

Would this raise the security margin and allow use of 128-bit signatures for exactly 128-bit (classical) security?

Answer 1

Would this raise the security margin and allow use of 128-bit signatures for exactly 128-bit (classical) security?

Yes and no - yes, it would raise the security margin somewhat, but not to the full "128 bit classical security level".

As for why it wouldn't raise it to the full 128 bit level, well, for two reasons:

• For one, the attacker could take a guess at S0, and compute TRUNCATE-128(HMAC(S0,i||"0")) and see if it happens to be the value in the public key; that can happen for two reasons:

  • His guess for S0 happens to be correct; if S0 is 128 bits, this happens with probability $2^{-128}$

  • His guess for S0 is wrong, but TRUNCATE-128(HMAC(S0,i||"0")) just happens to be the correct value anyways; if we model HMAC as a random function, then this happens with probability $2^{-128}$

Hence, the probability of either of these happening is approximately $2^{-127}$, giving us a security level that is slightly less than 128 bits.

• For another, let us assume that the adversary has $M$ public key, messages and signatures (each message being $N$ bits); what he can do is try to guess S0 for the first bit of each private key; if he succeeds (for any message with a 1 first bit, hence S1 was used), then he can generate that forgery for that public key. If we assume that the goal of the adversary is to generate a forgery for one of the public keys (and he doesn't care which), then the expected work effort is $2^{-128} / (N/2)$ (with the $N/2$ factor being the approximate messages with a 0 first bit); for large $N$ this is obviously a nontrivial decrease in security.

Now, the obvious defense against the first observation is to increase the size of S0 and S1 (which will cause an increase in the size of a signature). And, against the second observation, you need to stir in some per-public-key distinguisher (along with the 'bit position' which your proposal does) somehow into the one-way-function. If you look at the current standard hash based signature methods (LMS, XMSS, Sphincs+), they do that (using various techniques to stir things in - none of them use HMAC).

Answer 2

The advantage of using HMAC with Lamport OTS is that it provides protection against length-extension attacks. This is important if you want to securely derive multiple unique private keys from a single secret seed by feeding the seed + an incrementing index into a hash function.

Without HMAC, a key generation algorithm may be less secure because an attacker could potentially produce a valid signature on a new message by looking the last signature and public key used on the previous message and using a length extension attack to derive the next public key and signature in the sequence without knowing the secret seed or any private key.

SHA256 does not protect against length-extension attacks but HMAC-SHA256 does.