Exponential Generating Functions, High Powers of Random Permutations, and Very Iterated Block Ciphers
<-- Return to the list
Date: 02-10-2009
Start Time:
5:30pm
End Time: 6:30pm
Speaker: Gregory Bard, Fordham University
Location: 507 Math
ABSTRACT
Suppose you take a random permutation from $S_n$, and raise it to a power $k$. Then it turns out that the expected number of fixed points (in the limit as n goes to infinity) is $\tau(k)$, the number of positive integers dividing $k$. Thus, if you choose $k=1081079$, there are $2$, but only one higher, $k=1081080$, makes $256$ fixed points.
I use this to attack an arbitrary block cipher, on the assumption that the user makes the unwise decision to iterate the cipher some large number of times. There is no reason to imagine a user doing that, except very naive users (i.e. teenage hackers) sometimes iterate a cipher $1,000,000$ times thinking it would make it harder to break. To my knowledge, we are the first to show that it makes it weaker in each and every case (i.e. we assume nothing about the block cipher), via showing a "distinguisher attack."