Timing attack against HMAC in authenticated encryption?

Question

In an answer to another question of mine, it was noted that a class using standard string comparison functions when checking the HMAC in authenticated encryption would make the class vulnerable to timing attacks against the HMAC.

I can't wrap my head around how this a timing attack against the HMAC of authenticated encryption be an issue?

First of all, the implementations should be considered known to the attacker (in this particular case the source is simply published), so the only thing secret would be the key. Following this line of reasoning, how would a constant-time comparison function in the implementation protect against anything? (I would expect the attacker to simply remove it, if he would even use the same code).

And second, if I would think about the implementation as a black-box, the comparison is against a HMAC of the data with a PBKDF2 derived key. Wouldn't trying a timing attack against the HMAC be a) just as slow as trying to brute-force a PBKDF2 protected password b) not really disclose any information helpful in any attempt to decrypt the data? (the HMAC even appended to the cipher text, available to everyone with access to the encrypted data).

So, what am I missing here, why are timing attacks in this scenario considered a risk that needs protecting against?

Quick update:
I understand how timing attacks work, but I do not understand what would be gained by employing a timing attack in a scenario where the decrypt function looks like:

/**
 * @param binary $data Where $data = salt, IV, encrypted data, HMAC(salt, IV, encrypted data)
 * @param string $password The decrypt-password
 * @return string|null plain text if data was successfully decrypted, null otherwise
 */
function decrypt($data, $password) {
    ...
}

Answer 1

It allows for the potential of an existential forgery. An attacker can create a valid HMAC for a chosen message without knowing the HMAC key.

Basically, the way the attack works is this:

1. The attacker sends a message, and an HMAC (really just a sequences of bytes the same length as the HMAC) and times the response from the decryption system.

2. The attacker then sends the same message, and the same pseudo-HMAC repeatedly, with the exception that he now iterates though every (256) possible value for the first byte of the HMAC.

3. If the decryption system is returning an error immediately on finding a mismatch between bytes, one of these iterations (the one with the same first byte value as calculated by the decryption system) should take slightly longer to return. If the attacker can can detect that difference, he now knows the correct first byte for the correct HMAC for the message given the decryption system's HMAC key.

4. The attacker sends the same message and HMAC, this time with the known correct first byte, iterating over the second byte, until again, he finds the byte that causes the decryption system to take slightly longer to respond with an error. The attacker now knows the second byte of the correct HMAC.

5. Rinse and repeat for every successive byte in the HMAC, until a valid HMAC has been derived for the attacker's chosen message, sans key.

This is why HMAC comparison needs to be constant-time, comparing all the bytes of the submitted HMAC to the calculated HMAC before returning a response. This way, no matter the position of any incorrect bytes, the time to error will always be equal. The attacker no longer has a way to tell what or where the incorrect bytes are.

Update

In the specific scenario you present, the HMAC is providing you with integrity protection, or is the "authentication" piece of "authenticated encryption." If it can be forged by an attacker, the ciphertext can be modified without your knowledge, and you no longer have authenticated encryption, but effectively unauthenticated encryption and are vulnerable to chosen ciphertext attacks.

Answer 2

The risk is that an attacker can forge data. In other words, they can come up with their own ciphertext and then figure out the expected HMAC to make your system accept the input as valid.

The whole point of the HMAC is that only you as the owner of the key can “sign” data. However, if the application leaks information about the expected HMAC of the input, then an attacker can actually “sign” their own data.

Simply put, it works like this:

The attacker has come up with some data and wants your system to accept it. For that, they need to know the right HMAC. Since the attacker doesn't have the key, they cannot simply calculate the HMAC. However, by measuring subtle time differences, they can “ask” your system about the expected value:

• Attacker: “I have this piece of data, and my guess is that the HMAC begins with the byte 0x00. Is this correct?”
• You: “No.”
• Attacker: “Does the HMAC begin with 0x01?”
• You: “No.”
• ...
• Attacker: “Does the HMAC begin with 0xAB?”
• You: “Yes, the first byte is correct.”
• Attacker: “OK. Is the next byte 0x00?”
• You: “No.”
• ...

At the end, the attacker knows all bytes.

The problem is that the application doesn't just reject the wrong HMAC. It actually helps the attacker by telling them how the HMAC should look like.

---

Looking at your update, it seems you generally don't understand the purpose of the HMAC and why it's important.

Let's say there was no HMAC. In that case, you'd only protect the confidentiality of the data, not it's integrity. People could manipulate existing ciphertext or come up with their own ciphertext, and your application would happily turn that into whatever plaintext happens to come out. In many cases, this is a serious problem. Think of an encrypted session cookie which contains the user ID: You don't want people to change that.

So you add an HMAC as a kind of “signature” to prevent users from tampering with the ciphertext. You want confidentiality and integrity. However, if a user can figure out the right HMAC for arbitrary data, the whole exercise is pointless. You lose the integrity protection and go back to plain encryption. Now again anybody is able to mess with the ciphertext.