Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance

A definition of online authenticated-encryption (OAE), call it OAE1, was given by Fleischmann, Forler, and Lucks (2012). It has become a popular definitional target because, despite allowing encryption to be online, security is supposed to be maintained even if nonces get reused. We argue that this expectation is effectively wrong. OAE1 security has also been claimed to capture best-possible security for any online-AE scheme. We claim that this understanding is wrong, too. So motivated, we redefine OAE-security, providing a radically different formulation, OAE2. The new notion effectively does capture best-possible security for a user’s choice of plaintext segmentation and ciphertext expansion. It is achievable by simple techniques from standard tools. Yet even for OAE2, nonce-reuse can still be devastating. The picture to emerge is that no OAE definition can meaningfully tolerate nonce-reuse, but, at the same time, OAE security ought never have been understood to turn on this question.

Published in:
Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Proceedings, Part I, 493-517
Presented at:
CRYPTO 2015, Santa Barbara, CA, USA, August 16-20, 2015
Berlin, Springer
978-3-662-47989-6; 978-3-662-47988-9

 Record created 2015-08-31, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)