Paper 2015/095

Rotational Cryptanalysis of ARX Revisited

Dmitry Khovratovich, Ivica Nikolic, Josef Pieprzyk, Przemyslaw Sokolowski, and Ron Steinfeld

Abstract

Rotational cryptanalysis is a probabilistic attack applicable to word oriented designs that use (almost) rotation-invariant constants. It is believed that the success probability of rotational cryptanalysis against ciphers and functions based on modular additions, rotations and XORs, can be computed only by counting the number of additions. We show that this simple formula is incorrect due to the invalid Markov cipher assumption used for computing the probability. More precisely, we show that chained modular additions used in ARX ciphers do not form a Markov chain with regards to rotational analysis, thus the rotational probability cannot be computed as a simple product of rotational probabilities of individual modular additions. We provide a precise value of the probability of such chains and give a new algorithm for computing the rotational probability of ARX ciphers. We use the algorithm to correct the rotational attacks on BLAKE2 and to provide valid rotational attacks against the simplified version of Skein.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2015
Keywords
rotational cryptanalysisMarkov cipherMarkov chainSkeinBLAKE2
Contact author(s)
inikolic @ ntu edu sg
History
2015-02-23: received
Short URL
https://ia.cr/2015/095
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/095,
      author = {Dmitry Khovratovich and Ivica Nikolic and Josef Pieprzyk and Przemyslaw Sokolowski and Ron Steinfeld},
      title = {Rotational Cryptanalysis of {ARX} Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2015/095},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/095}},
      url = {https://eprint.iacr.org/2015/095}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.