Paper 2015/091

Related-Key Forgeries for Prøst-OTR

Christoph Dobraunig, Maria Eichlseder, and Florian Mendel


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.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in FSE 2015
CAESAR competitionPrøstauthenticated encryptioncryptanalysisrelated-key
Contact author(s)
maria eichlseder @ iaik tugraz at
2015-02-16: received
Short URL
Creative Commons Attribution


      author = {Christoph Dobraunig and Maria Eichlseder and Florian Mendel},
      title = {Related-Key Forgeries for Prøst-OTR},
      howpublished = {Cryptology ePrint Archive, Paper 2015/091},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.