Cryptology ePrint Archive: Report 2019/127

Beyond Birthday Bound Secure MAC in Faulty Nonce Model

Avijit Dutta and Mridul Nandi and Suprita Talnikar

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 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.

Category / Keywords: secret-key cryptography / Graceful Security, Faulty Nonce, Mirror Theory, Extended Mirror Theory, Expectation Method, CWC, GCM

Original Publication (with minor differences): IACR-EUROCRYPT-2019

Date: received 7 Feb 2019, last revised 12 Feb 2019

Contact author: avirocks dutta13 at gmail com,mridul nandi@gmail com,suprita45@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190213:172441 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]