Generic Attacks against MAC Algorithms

Gaëtan Leurent 1, *
* Auteur correspondant
Abstract : Message Authentication Codes (MACs) are important cryptographic constructions , used to ensure the authenticity of messages. MACs can be built from scratch (SipHash, Chaskey), from block ciphers (CBC-MAC, PMAC), from hash functions (HMAC), or from universal hash functions (GMAC, Poly1305). Constructions based on a lower level primitive are usually studied with a prov-able security approach: for commonly used MAC algorithms, security proofs rule out any attack on the MAC with complexity less than 2 n/2 (the birthday bound), when using an ideal n-bit block cipher or compression function. On the other hand, a generic collision attack against iterated MACs by Preneel and van Oorschot [8] using 2 n/2 queries show that the security proofs are tight. The security of MAC algorithms seems to be well understood, but the generic attack of Preneel and van Oorschot is only an existential forgery attack, and stronger attacks (e.g. key-recovery attacks) are usually more expensive. In order to evaluate the security of common MAC algorithms below the birthday bound, we now focus on generic attacks, rather than on security proofs. The two approaches are complementary: generic attacks yields upper bounds on the security of a mode, and security proofs yield a lower bound. It is important to comin both, because constructions with a similar security proof can actually have a very different loss of security after the birthday bound. For instance, there is a collision-based almost universal forgery attack against several CBC-MAC variants with birthday complexity [4]. There is also an attack with birthday complexity recovering the secret mask in PMAC using collisions [5]; this implies a universal forgery attack. More recently, a similar attack was shown against AEZ v3, but it yields a full key-recovery attack because of the way the secret mask is derived from the master key [2]. Hash-based MACs also have varying security beyond the birthday bound. The main constructions process the message with an unkeyed iteration, and use the key only in the initialization (secret-prefix MAC), in the finalization (secret-suffix MAC), or both in the initialization and finalization (HMAC, envelope MAC, sandwich MAC). All these constructions are good MACs when used with a random oracle, but they offer different levels of security in practice. Constructions using the key only in the finalization are much less secure, because collisions in the hash function directly lead to forgeries independently of the key. In particular, these collisions can be computed offline, and do not require any queries to a MAC oracle. Secret-suffix MAC and envelope MAC are also susceptible to a key-recovery attack based on collisions with partial blocks [9]. Interestingly, the key-recovery attack can be applied to envelope MAC but not to sandwich MAC, although the construction are very close and have a similar security proof. Over the last years, a series of papers have studied more complex generic attacks against HMAC and similar hash-based MAC algorithms [6,7,3,1]. This proved that distinguishing-H, state-recovery, and universal forgery attacks against HMAC require less than 2 n operations, contrary to what was previously assumed. The first attacks used the structure of the cycle graph of random functions in an elegant way to build a distinguishing-H and state-recovery attack with complexity 2 n/2 [6]. Variants with short messages were also given, using the entropy loss of random functions (with complexity 2 2n/3), and later extended to HAIFA hash functions (with complexity 2 4n/5) [1]. Surprisingly, extensions of those techniques also lead to universal forgery attacks against long messages [7,3]. In addition, the state recovery attacks can be extended to key-recovery attacks for HMAC based on a hash function with an internal checksum. In particular, this gives a key-recovery attack with complexity 2 192 against HMAC-GOST (with n = 256), and 2 419 against HMAC-Streebog (with n = 512). All those examples show a large variety in the attack techniques and complexity , with several key-recovery attacks more efficient than exhaustive search. This highlights the importance of studying generic attacks in addition to the provable security driven approach to the design of MAC algorithms.
Type de document :
Communication dans un congrès
Selected Areas in Cryptography - SAC 2015, Aug 2015, Sackville, Canada
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger
Contributeur : Gaëtan Leurent <>
Soumis le : lundi 14 décembre 2015 - 15:38:48
Dernière modification le : vendredi 18 décembre 2015 - 01:12:52
Document(s) archivé(s) le : samedi 29 avril 2017 - 13:26:11


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01243151, version 1



Gaëtan Leurent. Generic Attacks against MAC Algorithms. Selected Areas in Cryptography - SAC 2015, Aug 2015, Sackville, Canada. 〈hal-01243151〉



Consultations de la notice


Téléchargements de fichiers