Конференции ИВТ СО РАН

Abstracts

Information protection is nowadays one of the important directions of information technologies. Many investigations in this field are dedicated to cryptanalysis of the block ciphers that are the important means of protecting information. If one suggests an attack which achieves just a relatively small decrease of complexity of breaking a cipher compared with other known methods, the motivation arises to further development of the cipher construction principles. We suggest a new attack to the block ciphers called "gradient statistical attack". We show the possibility of maintaining this attack with respect to the ciphers for which no more effective attacks than the exhaustive key search are known.

The majority of block ciphers are iterative, i.e., consist of many rounds of transformations usually framed by some prologue and epilogue [1]. Each of these may, in its turn, be divided into a number of simpler steps performing data transformations and encrypting data with the use of some subkeys produced from the main key. We suggest a chosen-plaintext attack for the cipher which can be described by such an iterative scheme with relatively small subkeys. It is possible for such modern ciphers as RC5, RC6, AES and others. Remark that our implementation of the attack uses the new statistical tests suggested by the authors in [2,3,4].

The suggested attack belongs to the class of chosen-plaintext attacks. In these attacks, a cryptanalyst can input any information to the cipher and observe the corresponding output. Her aim is to disclose the secret key or, which is almost the same, the round keys. It is assumed that the block ciphers must be secure against such kind of attacks.

One of the requirements applied to the block ciphers is that having a sequence of distinct blocks as input, the cipher must output the sequence of bits that looks like random. A truly random sequence can be defined as the one generated by the Bernoulli source with equal probabilities of zeros and ones. We shall informally call the sequences "more random" of "less random" depending on how much they differ from truly random sequences. One way to measure randomness is to use some statistic computed upon the sequence and having the property that less random sequences have a greater statistic value (to within some probability of error in decision). It may be the well-known x² statistic subjected to chi-square distribution.

Let all input cipher blocks are non-random and pairwise different. For example, these are the numbers 1, 2, 3, ..., written in the binary form. After application of one step of encryption to the input sequence, we obtain a more random sequence. After the second step of encryption, the randomness of the sequence further increases. And thus each step of encryption increases randomness.

Notice the obvious consequence: in decryption, randomness of the data decreases from step to step. But the following is important: if the decryption subkey is invalid then the sequence obtained will be more random. This occurs because the decryption with some other subkey corresponds to extra encryption with that subkey, which is the well-known multiple encryption principle. Generally speaking, the decryption with an invalid round key increases randomness while the decryption with the valid key decreases randomness. And this difference can be detected by the statistical test.

The suggested gradient statistical attack is maintained by the following way. First, we encrypt some non-random input sequence. Then we start the main procedure of finding the key. For all possible subkeys of the last encryption step, we decrypt the ciphertext and estimate the degree of randomness. We assume that the unknown subkey is the one under which the randomness is minimal. After that, based on the obtained (less random) sequence, we repeat the similar actions and find the next subkey and so on.

Our experimental research was carried out as follows. First, the degree of randomness of encrypted sequences was analysed as the function of the number of encryption steps. The aim was to find the maximal number of steps at which the tests could tell the encrypted sequence from the truly random one. Second, the assumption was checked, the suggested attack is based upon, namely, does the decryption under an invalid key increases randomness or, more accurately, can the sequences obtained by decryption with the valid and invalid subkeys be distinguished by the statistical test. Third, on the basis of the obtained results, the attack to the cipher was launched. The experiments were carried out on a multiprocessor system containing 10 1-GHz Alpha processors with 1G byte of memory per device.

The experiments confirm our assumptions about the principal possibility of maintaining the suggested gradient statistical attack. As a matter of fact, the RC5 cipher with 8 rounds can now be broken with the use of 2³³ plaintext-ciphertext pairs.

[1] Menzes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996.

[2] Ryabko B. Ya., Stognienko V. S., Shokin Yu. I. A new test for randomness and its application to some cryptographic problems // Journal of Statistical Planning and Inference. V. 123, N. 2. 2003. P. 365-376.

[3] B. Ya. Ryabko, V. A. Monarev. Using information theory approach to randomness testing. Journal of Statistical Planning and Inference, 2005 (accepted; available online 15 July 2004, see: Articles in Press).

[4] Ryabko B. Ya., Fionov A. N., Monarev V. A., Shokin Yu. I. Using information theory approach to randomness testing // 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing. -- Stuttgart, Germany, March 14 - 16, 2005. -- http://www.hlrs.de.

Note. Abstracts are published in author's edition

Comments

[Home] [Conference]

© 1996-2000, Institute of computational Techologies SB RAS, Novosibirsk
© 1996-2000, Siberian Branch of Russian Academy of Science, Novosibirsk