Studies On Key Schedules And Single-key Attacks Of Block Ciphers

Symmetric cryptographic algorithms play fundamental roles in information security. Among all symmetric cryptographic algorithms, block ciphers are widely used in the field of practical security. Block ciphers have high-speed execution, easy software and hardware implementation, and are suitable for encrypting big data. Design and cryptanalysis of block ciphers have been a hot research topic over decades, especially the construction of secure and efficient block ciphers.The practical security of block ciphers depends on their resistance against cryptanalytic attacks. Many cryptanalytic techniques exploit the flaws of cipher structures or round functions, such as linear attacks and different attacks. As one of the significant modules in block ciphers, key schedules are receiving more and more attention these years. Many recently found attacks are based on the weaknesses of key schedules, such as meet-in-the-middle(MITM) attacks and their variants. However, compared with cipher structures and round functions, less research on the design of key schedules exists.Most existing design rules are proposed for cipher structures and round functions, and the key schedules lack of design rules that can provide practical guidance.The research of this thesis focuses on block ciphers. Our contributions contain two parts.The first part is about the attacks using the weaknesses of key schedules and design rules to avoid these attacks, including how to apply weaknesses in key schedules to obtain better attack results, how to design secure and efficient key schedules, and to show a concrete key schedule design. Our results in this part provide new guidance on the design of key schedules, as follows.1. We study the role that key schedules play in the cryptanalytic techniques. Firstly, we define the notion of actual key information, AKI, to precisely describe the situation where weaknesses in key schedules lead to practical attacks. We discover that most attacks related to key schedules exploit the existence of insufficient AKI in a computation path. One important cause for insufficient AKI is that the interplay of diffusion between key schedules and round functions results in leakage of key bit information in a computation path. Based on these observations,we propose a design rule to avoid the phenomenon of key bit leakage. With this rule, we can design diffusion of key schedules in a more targeting way when the round function has been decided. Also, we develop an efficient and effective tool to detect the flaws in key schedules automatically. For the attackers, our work provides a tool to search security flaws on existing ciphers. For the designers, the design rule we propose can be a guidance of quickly ruling out unreasonable key schedules at first step, and then our tool can be used to do further examination.2. We give practical attack instances according to the above theoretical results and the detection tool. By finding and exploiting computation paths with insufficient AKI, we improve the time complexity of an MITM attack on Serpent, improve the memory complexity of an MITM attack on AES-256, extend one more round of an integral attack on Safer++256, and give the first attack with extremely low data complexity on TWINE-80. Besides, we mount a 25-round MITM attack on XTEA, which has similar complexity with the so far best one, but is much simpler.3. We propose a new key schedule design for AES. Our design has no extra nonlinear operations(e.g., S-boxes) and no extra operations to introduce diffusion(e.g., module addition, exclusive-OR) in the generation of subkeys. Thus, our design has a close execution speed to the original AES key schedule, and is much faster than other variants of AES key schedules.The second part is about the single-key attacks unrelated to key schedules. That is,these attack techniques don’t use the properties in key schedules. Thus, the following results of this part help to more precisely understand the design and security of round functions and structures of block ciphers.1. We consider chosen-plaintext variants of the linear attack on reduced round Serpent block cipher. By reasonably fixing parts of the plaintexts of 10-round Serpent, the number of texts required in a linear attack with single approximation can be significantly reduced by a factor of 222. We also give the best data complexity on 10-round Serpent so far, which is 280. Moreover, we extend the chosenplaintext technique to multidimensional linear attacks and improve the results of cryptanalysis in data complexity or/and time complexity in different scenarios.As an application to show the usefulness of this technique, an experiment in the multidimensional linear model on 5-round Serpent is given.2. We present a 19-round multidimensional linear attack on the lightweight block cipher MIBS, which outperforms the previously best one in terms of number of attacked rounds and data complexities. Based on previous 6 linear approximations, we find other 594 linear approximations to reduce the data complexity.Previously, Nguyen et al. proposed an approach to reduce the time complexity in the counting phase of multidimensional linear attacks. We improve Nguyen et al.’s approach, so that it can be used for linear approximations with different input and output masks, instead of only for linear approximations with the same masks. Using more linear approximations and improved Nguyen et al.’s approach, the time complexity is reduced.3. We propose an MITM attack that can always be successfully mounted against any practical block ciphers with success probability one. The data complexity of this attack is the smallest according to the unicity distance. The time complexity can be written as 2k(1- ?), where ? > 0 for all practical block ciphers. Previously,the security bound was accepted to be the master key size k. We point out that actually this k-bit security is always overestimated and can never be reached because of the inevitable loss of the key bits. Effective key bits of many wellknown block ciphers are calculated. Also, we discover that when the number of rounds is fixed, it is better to take a key size equal to the block size.