# Is Lamport OTS improved by using HMAC?

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?

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).

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.

• It's correct that HMAC-SHA-256 protect against length-extension attacks that are possible with SHA-256. But the difference goes beyond that: there's a key input to HMAC, not to SHA-256. And I think that's part of why HMAC makes sense in Lamport OTS.
– fgrieu
May 2, 2022 at 10:47
• Even if we derive private keys by $\text{Hash}(Seed || index )$ (not mandated by Lamport), you might want to spell out how we would use length extension to derive a future private key $\text{Hash}(Seed || (index + n))$ for $n$ not huge (say, less than $2^{64}$)... May 2, 2022 at 12:32
• @poncho Since each Lamport OTS signature reveals 50% of its corresponding private key, by looking at past signatures, we could end up knowing 50% of the private key HASH('mysecretseed-1') and 50% of the private key HASH('mysecretseed-10') and 50% of the private key HASH('mysecretseed-100'), etc... We can then carry out a length extension attack using all the known parts of those old/used private keys to try to fill in all the gaps in order to derive the entire private key HASH('mysecretseed-1000') for example.
– Jon
May 4, 2022 at 17:17
• @poncho The more messages are signed, the more parts of various past private keys we know, the more likely it is that we can fill in all the gaps to derive a later private key.
– Jon
May 4, 2022 at 17:20
• You may want to look at how a "length extension attack" works and what it can do - I suspect it doesn't work like what you're thinking... May 4, 2022 at 17:22