Miyaji Laboratory

RC4 was one of the most famous stream ciphers developed by Ron Rivest of RSA Data Security in 1987. The stream cipher is a kind of symmetric-key cryptography encrypting bit(byte) by bit(byte) of the plaintexts. The advantage of stream cipher is that it is possible to one by one encrypt even the data size is not decided. RC4 is encrypted by generating the pseudo-random number based on the private key, and taking the pseudo-random generated number and exclusive-OR the plaintext. RC4 is used widely in different areas such as Wired Equivalent Privacy(WEP), Wi-Fi Protected Access(WPA), SSL, and SSH, etc. After it is opened to the public in 1994 by reverse engineering, the research on the vulnerability of RC4 has gained popularity. However, it has not been broken completely and it is still being used widely at present. The analysis of RC4 has chiefly two approaches, namely, analysis on Key Scheduling Algorithm(KSA) and analysis on Pseudo-Random Generation Algorithm(PRGA). There has been a lot of attacks on RC4 such as the key recovery attack etc. By using the bias examed in the linear combination, the private key are proposed to the attack to KSA.
It is theoretically shown that it doesn't depend on the private key for PRGA and there is bias in an initial state, and to given the state restoration attack etc. to restore a proposal and an initial state of distinguisher. Moreover, it is theoretically shown that an equivalent key exists in RC4 when the length of the key is short recently, and the pair of the private key from which it begins to make an state that an initial state of RC4 is different only by two bytes in addition exists. Then, it aims to observe the state transition in an state different only by two bytes, and to derive an initial state from the output difference and the initial difference position in the present study.