Cryptology ePrint Archive: Report 2016/534

Damaging, Simplifying, and Salvaging p-OMD

Tomer Ashur and Bart Mennink

Abstract: One of the submissions to the CAESAR competition for the design of a new authenticated encryption scheme is Offset Merkle-Damgård (OMD). At FSE 2015, Reyhanitabar et al. introduced p-OMD, an improvement of OMD that processes the associated data almost for free. As an extra benefit, p-OMD was claimed to offer integrity against nonce-misusing adversaries, a property that OMD does not have.

In this work we show how a nonce-misusing adversary can forge a message for the original p-OMD using only 3 queries (including the forgery). As a second contribution, we generalize and simplify p-OMD. This is done via the introduction of the authenticated encryption scheme Spoed. The most important difference is the usage of a generalized padding function GPAD, which neatly eliminates the need for a case distinction in the design specification and therewith allows for a significantly shorter description of the scheme and a better security bound. Finally, we introduce the authenticated encryption scheme Spoednic, a variant of Spoed providing authenticity against a nonce-misusing adversary at a modest price.

Category / Keywords: secret-key cryptography / Authenticated encryption, CAESAR, p-OMD, nonce-misuse, forgery, simplification

Original Publication (with minor differences): ISC 2016

Date: received 30 May 2016

Contact author: tashur at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20160531:070023 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]