Related-Key Statistical Cryptanalysis.
Darakhshan Mir, Poorvi L. Vora · 2007
This paper studies the information-theoretic limits of block cipher statistical key-recovery attacks, which typically use several known plaintext/ciphertext (P/C) pairs to determine a single key. In particular, it studies related-key statistical key recovery, where the adversary uses n related keys, generated from k independent ones. Unlike classical related-key attacks such as differential related-key cryptanalysis, this attack does not exploit a special structural weakness in the cipher or key schedule, but amplifies the weakness exploited in single-key recovery. Using classical results from information theory the paper shows that there exists a relationship among the keys for which the number of P/C pairs required per independent key bit is finite, for any probability of key-recovery error. This may be compared to the unbounded number required per bit of the single-key-recovery attack; the adversarial advantage being similar to that of using error-correcting codes instead of repetition codes for channel communication. The paper also provides lower bounds on the number of P/C pairs required per independent key bit. The practical implications of the results are demonstrated through experiments on reduced-round DES.