Cryptology ePrint Archive: Report 2007/227

Related-Key Statistical Cryptanalysis

Darakhshan J. Mir and Poorvi L. Vora

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.

Category / Keywords: secret-key cryptography / cryptanalysis, information theory

Date: received 11 Jun 2007, last revised 6 Jul 2007

Contact author: poorvi at gwu edu

Available formats: PDF | BibTeX Citation

Version: 20070707:054725 (All versions of this report)

Discussion forum: Show discussion | Start new discussion