Related-Key Conditional Differential Cryptanalysis Of KATAN Family

The KATAN family of block ciphers which are based on NLFSR is first published on CHES2009. It contains three block ciphers, the KATAN32, KATAN48and KATAN64. All the ciphers in the KATAN family share the same key schedule, which accepts an80-bit master key and254rounds, as well as the same nonlinear functions. The key schedule of the KATAN family loads the80-bit key into an LFSR (the least significant bit of the key is loaded to position0of the LFSR). For each round, the bits in positions0and1of the LFSR are generated as the round’s subkey k2i and k2i+1, and the LFSR is clocked twice. The chosen feedback polynomial is a primitive polynomial with the minimal hamming weight of5(there are no primitive polynomials of degree80with only3monomials):x80+x61+x50+x13+1.In this paper, we use conditional differential cryptanalysis to analyze the KATAN family. The cryptanalysis is to control the propagation of differ-ences by imposing conditions on the public variables of the cipher. Depending whether these conditions involve secret variables or not, key-recovery or dis-tinguishing attacks can be mounted. What’s more, we improve the attack by guessing the keys in the following rounds. We can get key-recovery attack for longer rounds with this method. The basic strategy is as follows: First, we find a key difference b whose expansion does not introduce differences for many rounds after some round r. The idea is to cancel all differences which are introduced by b up to round r and to maximize the number of rounds, where no differences are introduced again. Second, in order to find a plaintext difference a which can cancel the differ-ences introduced by b, we try to compute backwards from round r. We can fix a differential characteristic by now. Third, in the process of computing backwards from round r, we can get the conditions for the differential characteristic to be followed. Fourth, we derive a sample of valid plaintexts and empirically find the maximal number of rounds for which a bias can be detected in the ciphertext differences. Finally, we test the secret key to find whether it can influence the differential characteristic so as to get the correct key in the following rounds.In the KATAN family, the maximal number of consecutive rounds b that does not introduce differences is39, because the key expansion is80-bit LF-SR with the maximum period280-1and two bits are used per round. We try to find the largest r that can be controlled by conditions. If key bits are involved in the conditions, several samples will be derived and tested for the correct guess. If the key that we guessed is correctin the following rounds, the difference distribution will remain the same as the differential characteristic that we get in step two.For the KATAN family, we focus on its security in the related-key scenario and obtain key-recovery attacks for158,140and126of254rounds of KATAN32, KATAN48and KATAN64, respectively,what’s more,this is the best result of KATAN family for related-key differential cryptanalysis.