Miyaji Laboratory

When a sender sends a message for the recipient, the message will be exposed to attacks such as theft and tampering because of the unsafe channels. Especially in recent years, where the development of electronic government services and electronic commerce accelerated, it is necessary to ensure the security of the large amount of information flowing on the network. To ensure the information security is to ensure the confidentiality, integrity and availability. Encryption technology is the core technology fulfil these three requirements. The encryption technology to ensure confidentiality is divided two technologies, the symmetric cipher and public key cipher. For the symmetric cipher, the sender and recipient use the same key to encrypt and decrypt messages. On the other hand on the public key cipher, recipients has a secret key to decrypt messages and the sender uses recipient's public key for encryption. Symmetric cipher is adapted for hiding a large amount of data. This thesis will focus on the symmetric cipher.

Symmetric ciphers are divided into block cipher and stream cipher. Stream cipher has the feature that ciphertext errors do not propagete when decrypting the message. So stream cipher is used for noisy wireless communications etc. State transition stream cipher is one of the stream ciphers. State transition stream ciphers output on pseudo-random number while updating its internal state. In this study, we focus on the internal states which are not updated often. More specifically, we analyse a typical state transition stream cipher RC4. RC4 was developed by Rivest in 1987. It is used in various applications, for example WEP (Wired Equivalent Privacy), WPA (Wi-Fi Protected Access), SSL and so on. The cryptanalysis of RC4 had been proposed many times. But no method of cryptanalysis can get the message in realistic time. RC4 algorithm is divided into Key Scheduling Algorithm (KSA) and Pseudo Random Generation Algorithm (PRGA). KSA is given a secret key and generates the internal state S, which is an input of PRGA. PRGA is given the internal state S and generates pseude-random output and updates the internal state.

In 1995 Roos found experimentally that the internal state S after the RC4 KSA has a bias. Based on this bias, it was proposed that key recovery algorithm and analysis of WEP are possible. In addition Paul and Maitra gave the theoretical value to Roos's bais in 2007. Knudsen et al first proposed internal state restoration algorithm on PRGA in 1998. In addition Maximov et al proposed improved internal state restoration algorithm. They found that the relationship between some initial internal state bytes and the output can be represented by some equation with some probability. Also in 2009, Matsui shown theoretically that there is a private key pair to produce two initial internal state with only two bytes of difference. The same year, Miyaji, Sukegawa analysed the correlation between two bytes internal state with two differences in the initial round. Sukegawa et al focused on the relationship between the difference of two state outputs and the positions where differences exist in the initial round. By the relationship they guessed the internal state.

In this study, we analysed the following based on the correlation between two internal states with two bytes differences in the initial round.

(1). We estimates the PRGA internal state, 32.27% more effctively than random guessing .
(2). Based on the positions where differences exist in the initial round, we estimates the positions where differences exist after transition.
(3). We proposed the internal state restoring algorithm using (1), (2)

From these results, we evaluate the safety of the state transition stream ciphers.