A General Framework for the Related-Key Linear Attack Against Block Ciphers with Linear Key Schedules

We present a general framework for the related-key linear attack that can be applied to iterative block ciphers with linear key schedules. The attack utilizes a newly introduced related-key linear approximation that is obtained directly from a linear trail. The attack makes use of a known related-key data consisting of triplets of a plaintext, a ciphertext, and a key difference such that the ciphertext is the encrypted value of the plaintext under the key that is the xor of the key to be recovered and the specified key difference. If such a block cipher has a linear trail with linear correlation epsilon, it admits attacks with related-key data of size O(epsilon(-2)) just as in the case of classical Matsui's Algorithms. But since the attack makes use of a related-key data, the attacker can use a linear trail with the squared correlation less than 2(-n), n being the block size, in case the key size is larger than n. Moreover, the standard key hypotheses seem to be appropriate even when the trail is not dominant as validated by experiments. The attack can be applied in two ways. First, using a linear trail with squared correlation smaller than 2(-n), one can get an effective attack covering more rounds than existing attacks against some ciphers, such as Simon48/96, Simon64/128 and Simon128/256. Secondly, using a trail with large squared correlation, one can use related-key data for key recovery even when the data is not suitable for existing linear attacks.