International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Beyond Birthday Bound Secure MAC in Faulty Nonce Model

Avijit Dutta
Mridul Nandi
Suprita Talnikar
DOI: 10.1007/978-3-030-17653-2_15 (login may be required)
Search ePrint
Search Google
Abstract: 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 $$\mathsf {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.
Video from EUROCRYPT 2019
  title={Beyond Birthday Bound Secure MAC in Faulty Nonce Model},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  author={Avijit Dutta and Mridul Nandi and Suprita Talnikar},