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 $2^{119.237}$ times faster than brute-force search. It is hoped that these results will showcase the utility of exponential and ordinary generating functions and will encourage their use in cryptanalytic research.

Note: The distinguishing attack was presented in the Rump Session of Eurocrypt 2009.

Available format(s)
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
Short URL
https://ia.cr/2009/186

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},
note = {\url{https://eprint.iacr.org/2009/186}},
url = {https://eprint.iacr.org/2009/186}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.