Introduction
In symmetric-key cryptography, block ciphers like AES are typically assumed to be Pseudo-Random Permutations (PRPs). This strong assumption—that outputs are indistinguishable from random noise—underpins the security of most Message Authentication Codes (MACs). However, as cryptanalytic techniques like related-key attacks evolve, some ciphers may lose their "randomness" while remaining unpredictable (meaning it is still computationally hard to guess the output for a new input).
Unpredictability is a weaker security requirement than pseudorandomness. While previous research has shown it is possible to build MACs from unpredictable ciphers, these designs were often "low-rate," requiring multiple cipher calls per message block. This paper investigates whether efficient "rate-1" MACs (one cipher call per block) can be constructed under the weaker assumption of related-key unpredictability.
The Keyed PGV Model
To explore this, the authors revisit the PGV model, originally proposed by Preneel, Govaerts, and Vandewalle for analyzing block-cipher-based hash functions. They adapt this into a Keyed PGV model, where a secret key $K$ is integrated into the construction.
In this model, for each message block $M_i$, the construction determines three values:
- Key Mask (KM): Combined with the secret key $K$ via XOR.
- Input Block (IB): The plaintext input to the block cipher $E$.
- Feed-Forward (FF): A value XORed with the cipher's output to produce the next chaining value $T_i$.
The authors systematically analyzed all 64 possible ways to assign the message block $M_i$, the previous chaining value $T_{i-1}$, and a constant to these three slots ($KM, IB, FF$).
Security Analysis and Findings
The research reveals that standard rate-1 MACs like CBC-MAC, XCBC, and PMAC fail when the underlying block cipher is merely unpredictable rather than pseudorandom. The vulnerability stems from the "chaining value leak": if an adversary can observe or manipulate internal chaining values, they can often forge tags.
By adopting a "worst-case" security model—assuming the adversary can see all internal chaining values—the authors identified 24 provably secure constructions within the keyed PGV framework. Key insights include:
- Independence is Essential: Secure constructions ensure that the inputs to the block cipher (the key mask and the input block) are sufficiently independent to prevent an adversary from manipulating one to predict the other.
- Redundancy of Feed-Forward: The authors proposed a "Compact PGV model" by removing the feed-forward step ($FF=0$), proving it is unnecessary for MAC security in this context.
- Equivalence in Simplicity: Within the compact model, the six secure variants found are mathematically equivalent and can be transformed into one another using simple linear algebra.
Results and Practical Implications
The systematic categorization of the 64 potential designs yielded:
- 15 "meaningless" schemes (ignoring message or history).
- 25 schemes vulnerable to specific forgery attacks (fixed-M, fixed-T, or fixed-M⊕T attacks).
- 24 provably secure schemes under the Related-Key Unpredictable (RK-UP) assumption.
This group of 24 includes the 20 known secure PGV hash functions (when keyed) plus 4 additional schemes that work as MACs because MAC adversaries, unlike hash function adversaries, cannot perform "inverse" queries to the block cipher.
While these 24 schemes achieve the goal of being "rate-1," the authors note a practical trade-off. Because these constructions involve changing the block cipher's key for every message block, the overhead of the key schedule (preparing the cipher for a new key) can be significant. On hardware where key scheduling is slow, these MACs might be less efficient than traditional designs, despite their theoretical rate-1 efficiency.
Conclusion
This work demonstrates that robust MACs can be built from block ciphers that do not meet the full criteria of pseudorandomness. By identifying 24 secure constructions in the keyed PGV model, the authors provide a roadmap for building resilient authentication mechanisms that remain secure even as our assumptions about underlying primitives are challenged.
Summary updated