While reading about MAC (Message Authentication Code) I have faced this sentence:
MAC function must resist existential forgery under chosen-plaintext attacks
but I got confused. What does resist existential mean and what does chosen-plaintext attacks mean? I am new to this field and I need your help so could anybody explain and simplify these two terms?
Explanation with examples would be appreciated.
An existential forgery of a chosen plaintext is having the ability as an attacker to obtain a valid MAC for a plaintext of your chosing, without knowing the key required to generate a correct MAC.
A common vector for this is a timing attack, and that would work like this:
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.
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.
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.
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.
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.
And most of this answer is copied directly from my answer to: Timing attack against HMAC in authenticated encryption? hence the references to HMAC specifically.
