Nonce-Misuse On-Line AE

Don't Panic! The Cryptographers' Guide to Robust Authenticated (On-Line) Encryption

Current version: nonce-misuse-oae.pdf, Draft, March 11, 2015


In [1], Hoang et al. discuss the security definitions for nonce-misuse-resistant authenticated on-line encryption. They argue that (1) all on-line authenticated encryption schemes are vulnerable to the chosen-prefix secret-suffix (CPSS) attack; therefore, none deserves to be called “misuse-resistant” unlike misuse-resistant authenticated encryption (MRAE) schemes, which are off-line and invulnerable to that attack, and (2) if on-line encryption is required, then the OAE1 notion as defined by [2] is too weak for its claimed purpose. Therefore, the authors of [1] propose OAE2 as a putatively stronger alternative.

This work addresses their arguments in three directions. Firstly, we show that all AE schemes – including MRAE schemes –are vulnerable to an attack which we call chosen-plaintext overwrite-secret (CPOS), which is structurally similar to the CPSS attack. Secondly, while there is a clear need for AE schemes that limit the damage in the case of a nonce reuse, the phrase “misuse resistance” has always promised more than it can hold. Thus, we propose to replace it by “robustness” or “damage limitation”. Thirdly, we discuss the differences between OAE1 and OAE2. While the latter is an interesting security notion of its own, we argue that it solves a different problem than OAE1. We show that the combination of decryption robustness and OAE1 security (called OAE1+ ) implies OAE2 security, i.e., an OAE2 scheme may be vulnerable to decryption-misuse, but any decryption-robust OAE1 scheme can be transformed into a decryption-robust OAE2 scheme. Moreover, we introduce the notion OAE2+ for a decryption-robust OAE2 scheme. Finally, we argue that POET satisfies the properties of an OAE1+ scheme and show how it can be transformed into an OAE2+ scheme.

[1] Viet Tung Hoang, Reza Reyhanitabar, Phillip Rogaway, and Damian Vizár. Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance. Cryptology ePrint Archive, Report 2015/189, 2015.

[2] Ewan Fleischmann, Christian Forler, and Stefan Lucks. McOE: A Family of Almost Foolproof On-Line Authenticated Encryption Schemes. In FSE, pages 196–215, 2012.