Rotational cryptanalysis of ARX revisited

Dmitry Khovratovich*, Ivica Nikolić, Josef Pieprzyk, Przemysław Sokołowski, Ron Steinfeld

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

19 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationFast software encryption
Subtitle of host publication22nd international workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015: Revised Selected Papers
EditorsGregor Leander
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages519-536
Number of pages18
ISBN (Electronic)9783662481165
ISBN (Print)9783662481158
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event22nd International Workshop on Fast Software Encryption, FSE 2015 - Istanbul, Turkey
Duration: 8 Mar 201511 Mar 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume9054
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd International Workshop on Fast Software Encryption, FSE 2015
Country/TerritoryTurkey
CityIstanbul
Period8/03/1511/03/15

Keywords

  • BLAKE2
  • Markov chain
  • Markov cipher
  • rotational cryptanalysis
  • Skein

Fingerprint

Dive into the research topics of 'Rotational cryptanalysis of ARX revisited'. Together they form a unique fingerprint.

Cite this