International Association
for Cryptologic Research

We show that the distinguishing attacks on Even-Mansour block ciphers

in the related key model can easily be converted into extremely efficient key recovery attacks.

This includes in particular all iterated Even-Mansour constructions with independent keys.

We apply this observation to the Caesar candidate Prøst-OTR and are able to recover the whole key with a number of requests linear in its size. This improves on recent forgery attacks in a similar setting.