Cryptology ePrint Archive: Report 2015/302

Boosting OMD for Almost Free Authentication of Associated Data

Reza Reyhanitabar and Serge Vaudenay and Damian Vizár

Abstract: We propose \emph{pure} OMD (p-OMD) as a new variant of the Offset Merkle-Damgård (OMD) authenticated encryption scheme. Our new scheme inherits all desirable security features of OMD while having a more compact structure and providing higher efficiency. The original OMD scheme, as submitted to the CAESAR competition, couples a single pass of a variant of the Merkle-Damgård (MD) iteration with the counter-based XOR MAC algorithm to provide privacy and authenticity. Our improved p-OMD scheme dispenses with the XOR MAC algorithm and is \emph{purely} based on the MD iteration; hence, the name ``pure'' OMD. To process a message of $\ell$ blocks and associated data of $a$ blocks, OMD needs $\ell+a+2$ calls to the compression function while p-OMD only requires $\max\left\{\ell, a\right\}+2$ calls. Therefore, for a typical case where $\ell \geq a$, p-OMD makes just $\ell+2$ calls to the compression function; that is, associated data is processed almost freely compared to OMD. We prove the security of p-OMD under the same standard assumption (pseudo-randomness of the compression function) as made in OMD; moreover, the security bound for p-OMD is the same as that of OMD, showing that the modifications made to boost the performance are without any loss of security.

Category / Keywords: secret-key cryptography / authenticated-encryption, OMD, associated data, performance, CAESAR competition

Original Publication (with minor differences): IACR-FSE-2015

Date: received 31 Mar 2015

Contact author: reza reyhanitabar at epfl ch

Available format(s): PDF | BibTeX Citation

Note: This is the revised version taking into account the nonce-misusing attack by Ashur and Mennink in Cryptology ePrint Archive: Report 2015/175.

Version: 20150406:223613 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]