**Statistics of Random Permutations and the Cryptanalysis of Periodic Block Ciphers **

*Nicolas T. Courtois and 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.

**Category / Keywords: **secret-key cryptography / Generating Functions, EGF, OGF, Random Permutations, Cycle Structure, Cryptanalysis, Iterations of Permutations, Analytic Combinatorics, Keeloq.

**Publication Info: **Submitted to a journal, the response is pending.

**Date: **received 30 Apr 2009

**Contact author: **bard at fordham edu

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20090502:125914 (All versions of this report)

**Short URL: **ia.cr/2009/186

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]