Paper 2019/127

Beyond Birthday Bound Secure MAC in Faulty Nonce Model

Avijit Dutta, Mridul Nandi, and Suprita Talnikar


Encrypt-then-MAC (EtM) is a popular mode for authenticated encryption (AE). Unfortunately, almost all designs following the EtM paradigm, including the AE suites for TLS, are vulnerable against nonce misuse. A single repetition of the nonce value reveals the hash key, leading to a universal forgery attack. There are only two authenticated encryption schemes following the EtM paradigm which can resist nonce misuse attacks, the GCM-RUP (CRYPTO-17) and the GCM/2+ (INSCRYPT-12). However, they are secure only up to the birthday bound in the nonce respecting setting, resulting in a restriction on the data limit for a single key. In this paper we show that nEHtM, a nonce-based variant of EHtM (FSE-10) constructed using a block cipher, has a beyond birthday bound (BBB) unforgeable security that gracefully degrades under nonce misuse. We combine nEHtM with the CENC (FSE-06) mode of encryption using the EtM paradigm to realize a nonce-based AE, CWC+. CWC+ is very close (requiring only a few more xor operations) to the CWC AE scheme (FSE-04) and it not only provides BBB security but also gracefully degrading security on nonce misuse.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in Eurocrypt 2019
Graceful SecurityFaulty NonceMirror TheoryExtended Mirror TheoryExpectation MethodCWCGCM
Contact author(s)
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
suprita45 @ gmail com
2019-02-13: received
Short URL
Creative Commons Attribution


      author = {Avijit Dutta and Mridul Nandi and Suprita Talnikar},
      title = {Beyond Birthday Bound Secure MAC in Faulty Nonce Model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/127},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.