Paper 2009/186
Statistics of Random Permutations and the Cryptanalysis of Periodic Block Ciphers
Nicolas T. Courtois, Gregory V. Bard, and Shaun V. Ault
Abstract
A block cipher is intended to be computationally indistinguishable from a random
permutation of appropriate domain and range. But what are the properties of a
random permutation? By the aid of exponential and ordinary generating functions,
we derive a series of collolaries of interest to the cryptographic community. These
follow from the Strong Cycle Structure Theorem of permutations, and are useful in
rendering rigorous two attacks on Keeloq, a block cipher in wide-spread use.
These attacks formerly had heuristic approximations of their probability of success.
Moreover, we delineate an attack against the (roughly) millionth-fold iteration of
a random permutation. In particular, we create a distinguishing attack, whereby
the iteration of a cipher a number of times equal to a particularly chosen
highly-composite number is breakable, but merely one fewer round is considerably
more secure. We then extend this to a key-recovery attack in a “Triple-DES”
style construction, but using AES-256 and iterating the middle cipher (roughly) a
million-fold. This attack is
Note: The distinguishing attack was presented in the Rump Session of Eurocrypt 2009.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Submitted to a journal, the response is pending.
- Keywords
- Generating FunctionsEGFOGFRandom PermutationsCycle StructureCryptanalysisIterations of PermutationsAnalytic CombinatoricsKeeloq.
- Contact author(s)
- bard @ fordham edu
- History
- 2009-05-02: received
- Short URL
- https://ia.cr/2009/186
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/186, author = {Nicolas T. Courtois and Gregory V. Bard and Shaun V. Ault}, title = {Statistics of Random Permutations and the Cryptanalysis of Periodic Block Ciphers}, howpublished = {Cryptology {ePrint} Archive, Paper 2009/186}, year = {2009}, url = {https://eprint.iacr.org/2009/186} }