Cryptology ePrint Archive: Report 2015/091

Related-Key Forgeries for Prøst-OTR

Christoph Dobraunig and Maria Eichlseder and Florian Mendel

Abstract: We present a forgery attack on Prøst-OTR in a related-key setting. Prøst is a family of authenticated encryption algorithms proposed as candidates in the currently ongoing CAESAR competition, and Prøst-OTR is one of the three variants of the Prøst design. The attack exploits how the Prøst permutation is used in an Even-Mansour construction in the Feistel-based OTR mode of operation. Given the ciphertext and tag for any two messages under two related keys K and K + Delta with related nonces, we can forge the ciphertext and tag for a modified message under K. If we can query ciphertexts for chosen messages under K + Delta, we can achieve almost universal forgery for K. The computational complexity is negligible.

Category / Keywords: secret-key cryptography / CAESAR competition, Prøst, authenticated encryption, cryptanalysis, related-key

Original Publication (in the same form): IACR-FSE-2015

Date: received 6 Feb 2015, last revised 9 Feb 2015

Contact author: maria eichlseder at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20150216:050821 (All versions of this report)

Short URL: ia.cr/2015/091

Discussion forum: Show discussion | Start new discussion