Message Authentication Code
This week we focuses on the data integrity, Message Authentication Codes.
Define: MAC I=(S, V) defined over (K, M, T):
- S(k, m) outputs t in T
- V(k, m, t) output ‘yes’ or ‘no’
S stands for signing, V stands for verification.
Attacker can give Alice , to get . The goal is to produce some new valid message/tag pairs (m, t), aka existential forgery, such that:
The MAC is secure if attacker cannot generate new (m, t), even for existing message, . Or more formally: is negligible.
Secure PRF -> Secure MAC
The error bound of PRF is The is secure as long as is large enough.
Extend AES(16 bytes) from Small-MAC to Big-MAC:
- CBC-MAC, ANSI X9.9, FIPS 186-3
- HMAC, SSL, IPSec, SSH.
CBC-MAC and NMAC
It is important to use independent to encrypt the raw CBC output. For raw CBC, the attacker can
- choose one block message m, to get t = F(k, m)
- then for 2-block message , the MAC is t!
Also the independent encrypt the output of cascade MAC to make it secure.
We need to rotate keys for after messages with ECBC-MAC or for NMAC.
Once we find a hash collision, we can extend any arbitrary block to mount forgery attack.
Padding MUST be invertible to prevent forgery.
ISO: padding with
1 indicates the beginning of the padding. In case message has a clear cut, just append a dummy block.
CMAC uses for padding block, and for no-padding block to resolve the ambiguity. It is as safe as CBC-MAC, and standardized by NIST.
The enforce the block order, such . The padding use similar technical as CMAC.
It is easy to replace one specific block, and compute the MAC without recomputing everything.
Kind of like OTP, pick key, where q is a large prime number such as (), and break the message to blocks, :
where , aka a polynomial of L.
for F be a secure PRF, for r is random chosen: . The verification is: .
A function H is collision resistant if for efficient algorithms, the chance to fine the same hash is negligible.
Let I=(S, V) be a MAC for short message over (K, M, T), Let H:
Def: over as:
Thm: If I is a secure MAC and H is collision resistant, then is a secure MAC.
Let be a hash function () We can find a collision in time thanks to the birthday paradox:
Let be independent uniformly distributed integers. when then
Given , we obtain . So we can build a collision resistant function for larger message.
a block cipher: .
Suppose E is an ideal cipher, finding a collision of takes evaluations of (E, D).
Other natural variants are insecure:
- Merkle-Damgrad funciton
- Daives-Meyer Comporession
- SHACAL-2 block cipher.
Choose a random 2000-bit prime number, and random . For , define . is provable secure, but slow.