Related-Key Linear Cryptanalysis

A coding theory framework for related-key linear cryptanalytic attacks on block ciphers is presented. It treats linear cryptanalysis as communication over a low capacity channel, and a related key attack (RKA) as a concatenated code. It is used to show that an RKA, using n related keys generated from k independent ones, can improve the amortized cost - in number of plaintext-ciphertext pairs per key bit determined over that of k single key attacks, of any linear cryptanalysis, if k and n are large enough. The practical implications of this result are demonstrated through the design of an RKA, with k=5 and n=7, predicted to produce a 29% improvement for DES attacks that use an r-1 round approximation