Cryptography
mac authenticated-encryption pseudo-random-function timing-attack
Updated Sun, 25 Sep 2022 19:20:42 GMT

Is constant-time compare really required for AEAD ciphers?


When verifying a (HMAC) authentication tag it is often indicated that a constant-time comparison is required for security. I can see how leaking information about a password hash can introduce a mild vulnerability as the password hash may become known. However, we're talking here about a calculation over a known and randomized ciphertext.

What would be the vulnerability if we were to perform a non-time constant comparison? Could it be that it would allow recovery of secrets (e.g., passwords) used to derive the authentication key?

Are there other attacks possible if we assume that the derived keys are fully randomized (i.e., no information about the value of the individual bits is known to the attacker?)

Solution

Let the vulnerable comparison compare byte-by-byte and break out of the loop after the first mismatch. If we neglect noise, this leaks how many bytes (prefix) of the MAC are correct via timing.

Then attacker could send the same message with the same nonce over and over again, with varying MAC. After an average of 128 tries, one more byte of the MAC will be correct, which will result in the comparison taking longer and the attacker learning it's correct. Then they can lock in that byte, and vary the next byte of the MAC. For a 16 byte MAC it will take 128*16=2048 tries to construct a fully valid MAC which the recipient will accept.

This will not leak the MAC key, but it will produce a successful forgery.

If the recipient accepts multiple messages with the same IV/nonce, the attacker can then combine this attack with any applicable oracle attack against then underlying unauthenticated encryption (e.g. padding-oracle against CBC) to learn the contents of an intercepted message.

Comments (5)

  • +0 – I accepted this, and then I thought: OK, but the message should be randomized each time using some kind of changing IV/nonce anyway. It seems that the attack only works if this is not verified by the receiving end. That sounds like it could invalidate this attack, but it doesn't. We can assume that this verification isn't performed for randomized nonces after all. The attack would not work for message counters, but only if the verification of the message counter takes place before verification - which doesn't make much sense by itself. And yes, please do not use CBC. — Aug 26, 2022 at 11:52  
  • +0 – If the connection / key is reset when authentication fails then this attack isn't valid, but let's make sure we use in-depth protection. Use secure schemes within protocols, instead of designing the protocol around an insecure scheme. — Aug 26, 2022 at 11:59  
  • +1 – An application that rejects invalid plaintexts (e.g. it's malformed json, xml, etc.) provides an oracle when using CTR mode that's just as exploitable as the padding oracle against CBC. Tom Ritter describes a separator attack, which is a simple form of such an attack. — Aug 26, 2022 at 12:20  
  • +0 – I expect protocols built on top of an unreliable UDP-transport like DTLS or QUIC/HTTP3 to simply ignore detected forgeries without terminating the connection or blacklisting the forgery's nonce. But I'd expect them to reject counters/nonces which were already accepted before without verifying the MAC. So they should suffer from the forgery attack, but not the decryption oracle attack, since each nonce will only be accepted once. — Aug 26, 2022 at 12:24  
  • +5 – @MaartenBodewes You seem to be assuming a communication protocol that mandates a specific sequence of nonces. But that's just one very specific way of using an AEAD construct. AEAD can, and more often than not is, used in protocols where the verifier-decryptor has nothing to verify the nonce against (for example, there isn't a well-defined order in which the messages are read, or the nonces are supposed to be random, or there are multiple reader instances that can't synchronize to tell each other which nonces they've seen). — Aug 27, 2022 at 08:56  

References