The Researches And Applications Of Biclique Cryptanalysis On Block Cipher

In the past few years, with the large development of communication and electronic techniques, the low resource devices such as RFID tags and sensor network have been used in our life, such as access control, parking management, e Health and so on. Traditional block cipher is not suitable for this extremely constrained environment, so lightweight block cipher emerges as the times require. Compared with traditional block cipher, lightweight block cipher has short key length and block length, and relatively simple structure. Lightweight block cipher is mainly used for safe products with large quantities and low cost, such as intelligent terminals in the mobile communication network, positioning terminals in the satellite navigation system, sensor terminals in the internet of things and so on. These systems have a huge number of terminals, strict requirements of power consumption, a weak function of processors and a limited memory, these ciphers are once destroyed that will cause huge losses. Lightweight block cipher has not enough redundancy, so the security of the lightweight block cipher is need to further research. Moreover, researches on the security of lightweight block cipher is the theory expansion of cryptanalysis techniques.In 2011, Andrey Bogdanov et.al first applied biclique technique originally used for attack of Hash function on the attack of block cipher AES, which made biclique attack be the first key recovery attack on all versions of AES with the lower complexity than exhaustive search. Biclique attack only needs a small part of the codebook and low memory requirement. From then on, biclique technique has been widely applied on the security analysis of PRESENT, MIBS, PRINCE, LED, KLEIN and so on. Therefore, the research of biclique cryptanalysis has important theoretical and practical significance on designing and analyzing of block cipher and lightweight block cipher.The main works done in this paper are as follows:Firstly, we introduce balanced independent biclique and star-based independent biclique in detail, including the structures of bicliques, the methods of constructing a biclique from independent related-key differentials, matching with precomputations and complexity analysis and so on.Secondly, we choose the lightweight block cipher LED-112 and give the results of balanced independent biclique attack on LED-112. The computation complexity of our attack is 2^111.37 encryptions, data complexity is 2⁶⁴ chosen plaintexts and memory complexity is 2⁸. This is the first biclique attack on LED with 112-bit key length.Thirdly, we choose the traditional block cipher AES and give the results of star-based independent biclique attack on AES-128. The computation complexity of our attack is 2^126.7 encryptions and required data can be reduced to a single plaintext-ciphertext pair.Fourthly, We choose the lightweight block cipher PRINCE and give the results of balanced independent biclique attack on PRINCEcore. The computation complexity of our attack is 2^62.68 encryptions, data complexity is 2³² and memory complexity is 2⁸. By better selections of differential characteristics in the biclique construction, both the computation complexity and data complexity are superior to the previous results of biclique attack on PRINCEcore.Lastly, For block cipher PRINCEcore, we give the results of star-based independent biclique attack on PRINCEcore. The computation complexity of our attack is 2^63.04 and required data can be reduce to a single plaintext-ciphertext pair. To be the best of our knowledge, the data complexity is optimal.