Double HMAC Doesn't Need Random Key

[defuse]

https://www.isecpartners.com/blog/2011/february/double-hmac-verification.aspx

Think about this carefully before changing the code. This post says we can re-use the key again in the second HMAC, instead of generating a random one. That would be a lot better, as it's not prone to RNG failures.

[narfbg]

I'm using this in another, very similar to this project that I'm just about to publish.

I thought really hard about it and couldn't think of a possible drawback from reusing the key. I also even switched the algorithm for verification to MD5 as I find SHA-256 to be an overkill.

[defuse]

Okay, let's suppose that we re-use $key for the comparison HMAC. The verification procedure can be summarized in one line:

HMAC(K, HMAC(K, C)) === HMAC(K, T)

Both C and T are inputs controlled by the attacker. The attacker knows a bunch of (C, T) pairs just by looking at valid ciphertexts. The === side channel leaks the length of the common prefix between the two sides. The attacker's goal is to learn something about HMAC(K, X) for any X that isn't one of the ciphertexts they observed (existential forgery).

This can be done as follows:

1. The attacker observes N valid ciphertext-tag pairs (C1, T1), (C2, T2) ... (CN, TN).
2. This means the attacker knows that HMAC(K, CR) = TR for R from 1 to N.
3. The attacker sends N chosen ciphertext-tag pairs (C1, C1), (C2, C2), ... (CN, CN).
4. The victim will compare HMAC(K, HMAC(K, CR)) === HMAC(K, CR) for R from 1 to N.
5. If N > 256, there's a good chance the first byte will match for at least one of them.
6. If that happens, the attacker knows that the first byte of HMAC(K, HMAC(K, CR)) is the first byte of HMAC(K, CR), which (by 2) is the first byte of TR, which the attacker knows.
7. The attacker has successfully learned the first byte of the HMAC of a message that isn't equal to any of the ciphertexts they were allowed to observe (with high probability).

If the comparison HMAC key were random, the attack doesn't work, because the comparison would be HMAC(Z, HMAC(K, CR)) === HMAC(Z, CR) for some random key Z, and even if the === leaked the entire left and right sides, it doesn't help the attacker at all because that key is only used once.

This particular attack is very weak (it takes 2^N chosen ciphertexts to leak the first N bits), and assumes there are a lot of known ciphertexts that are the same length as an HMAC, but it does demonstrate how information is leaked when the key is re-used.

I am not a brilliant cryptographer, and I figured this out in an hour, so there's a good chance an actual cryptographer would be able to improve this attack to get an efficient existential forgery.

So, I'm going to leave the code as it is now, using a random key.

EDIT: Actually, the attacker can send N^2 ciphertext-tag pairs (C1, C1), (C1, C2), ... (C1, CN), ... (CN, C1), ... (CN, CN), and this lets them forge HMAC much faster (I think 2^(n/2) instead of 2^n, depending on the distribution of the tags in the valid ciphertexts they observed).

[defuse]

@narfbg Be careful about your MD5 decision: Are you downgrading security because you think SHA-256 is much less efficient than MD5, or do you have solid evidence (benchmarks) that using SHA-256 would be too much of a burden?

I would guess the difference between SHA-256 and MD5 for HMAC comparisons is unnoticeable in practice. You might as well go with the secure one and be sure. If there actually is a significant performance difference, then use BLAKE2, which is faster than MD5 and more secure

[narfbg]

Not sure what T is in what is originally assumed, but I guess you mean T = HMAC(Key, Ciphertext), so I guess that one's right. However, I think you've mistaken the formula a few times while analyzing this, starting at point 4:

The victim will compare HMAC(K, HMAC(K, CR)) === HMAC(K, CR) for R from 1 to N.

That is not what the victim would compare. It is the following:

recvHMAC, cipherText are submitted by the attacker
calcHMAC = HMAC(Key, cipherText)
HMAC(Key, calcHMAC) === HMAC(Key, recvHMAC)

The whole point here is that it doesn't matter that === can leak length, because the prefix of the resulting double HMAC will constantly change. Therefore even if the first byte between HMAC(Key, calcHMAC) and HMAC(Key, recvHMAC) matches, you cannot rely cannot rely on the assumption that you've correctly guessed it, because moving to the next byte will change it, effectively turning your attack into a brute-force one instead of time-based.

This is also why I chose MD5, as the only requirement is that the prefix for HMAC(Key, 'Foo') and HMAC(Key, 'Fo0') is not the same. As for the benchmarks, the difference is somewhere between 80% and 100% in execution time. It's not practically noticeable for a single call indeed, but you know ... I'm always looking for the optimal solution. Unfortunately, PHP doesn't provide BLAKE2, so I can't use it.

[defuse]

The HMAC(K, HMAC(K, CR)) === HMAC(K, CR) is the tricky part, which makes the attack work. The trick is: The attacker sends the ciphertext as both the cipherText and the recvHMAC. So what the victim treats as an HMAC is actually a ciphertext!

As you correctly point out, HMACing with the same key does stop the classic byte-by-byte extraction attack, but it leaves open a highly-theoretical never-ever-going-to-be-exploited-in-practice attack, that is still technically a crypto break. With my attack, you cannot move on to the next byte, but it lets you use the birthday paradox to speed up collision-finding (you aren't supposed to be able to with HMAC). For example if the HMAC was 128 bits, then a forgery could be produced in 2^64 online queries, instead of the 2^128 that would be required if it were completely free of side channels.

So an online attack of on the order of 2^64 requests would be able to find a collision in @narfbg's HMAC-MD5 comparison, which is still very impractical but falls below what's usually considered "secure" (128 bits).

@narfbg Does that make sense?

[defuse]

Correction: The attack I mentioned here wouldn't break @narfbg's MD5, since it uses SHA256 and MD5 which are not the same function. But the attack which is the solution to this brain teaser (that I'm too lazy to type up), would.

[defuse]

By T I meant the HMAC value provided by the attacker (and C is the ciphertext provided by the attacker).

[narfbg]

Right, I forgot to clarify that I'm comparing:

HMAC-MD5(Key, recvHMACSHA256) === HMAC-MD5(Key, HMAC-SHA256(Key, cipherText))

I'm happy to hear that conclusion about my implementation, since I was looking for an audit on it. Thanks!

I'm starting to understand now what you're describing otherwise. I guess it does make some sense, even if highly theoretical.

[sarciszewski]

This post says we can re-use the key again in the second HMAC, instead of generating a random one.

You have me beat in crypto experience, so it's possible I'm wrong, but wouldn't an unpredictable random second HMAC key be more ideal?

That would be a lot better, as it's not prone to RNG failures.

RNG failures? Like, being backdoored a'la your PoC||GTFO article, or something else?

[defuse]

@sarciszewski Yes you are right. The attack a few comments up works against re-using the key, but doesn't work (it's more secure) when the key is random, so I left the code the way it is (using a random key). And, after a lot of discussion on Twitter, I figured out that the attack that's possible in the case of an RNG failure is no worse than the attack that's possible by re-using the key, so it's best to use a random key even if the RNG could fail.