International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Related-Key Statistical Cryptanalysis

Darakhshan J. Mir
Poorvi L. Vora
Search ePrint
Search Google
Abstract: This paper presents the Cryptanalytic Channel Model (CCM). The model treats statistical key recovery as communication over a low capacity channel, where the channel and the encoding are determined by the cipher and the specific attack. A new attack, related-key recovery -- the use of $n$ related keys generated from $k$ independent ones -- is defined for all ciphers vulnerable to single-key recovery. It is shown to correspond to the use of a concatenated code over the channel, where the relationship among the keys determines the outer code, and the cipher and the attack the inner code. It is shown that there exists a relationship among keys for which the communication complexity per bit of independent key is finite, for any probability of key recovery error. This may be compared to the unbounded communication complexity per bit of the single-key-recovery attack. The practical implications of this result are demonstrated through experiments on reduced-round DES.
  title={Related-Key Statistical Cryptanalysis},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / cryptanalysis, information theory},
  note={ 13701 received 11 Jun 2007, last revised 6 Jul 2007},
  author={Darakhshan J. Mir and Poorvi L. Vora},