Miyaji Laboratory

Recently, a large amount of data flow in the network with a rapid spread of the Internet. Because the threat of tapping information, the forgery and illegal computer access etc. exist, the information security has become an important theme. Cipher is known as a main scheme of the information security. Cipher prevents data from leaking to others with scrambling data.
Cipher is classified into two kinds, symmetric cipher and public key encryption. Symmetric cipher uses the same key in both encryption and decryption and scrambles the secret data by repeating the encryption function which consists of simple logic and arithmetic operations with the key. Therefore symmetric cipher has the advantage of a high-speed operation and a compact implementation compared with public key encryption. Thus, it is used for equipments with low-speed CPU such as IC cards and cellular phones, and for communication form which requires high throughput such as WWW-service, VPN-service and etc.
Symmetric cipher is classified into block cipher and stream cipher. Block cipher encrypts the input called plaintext by the block. The security of the block cipher is evaluated by the number of rounds that makes the key-recovery possible more efficiently than an exhaustive key search. On the other hand, stream cipher generates the pseudo-random number and encrypts by xor between the pseudo-random number and plaintext by the bit. The security of stream cipher is evaluated by the amount of the pseudo-random number that makes the key-recovery possible more efficiently than an exhaustive key search. In this paper, we evaluate RC6 as block cipher and RC4 as stream cipher.

RC6 is a block cipher proposed by Rivest et al. and one of the final candidate of the AES. The RC6 consists of simple arithmetic operation and rotation shift and has been admired for high-speed software implementation. RC6-w/r/b means that four w-bit-word plaintexts are encrypted with r rounds by b-byte keys. It is recommended RC6-32/20/{16, 24, 32}.
Let us describe the simplified variants of RC6 as follows: RC6P mean RC6 without post-whitening. RC6-32 is only shown RC6.
The chi2 attack is known as the most efficient attack method against RC6. The chi2 attack makes use of correlations between plaintext and ciphertext measured by the chi2-test. Knudsen and Meier recovered the first extended keys with the rotation fixed to zero in the first round. Takenaka et al. proposed the method of calculating the theoretical chi2 value by using the transition matrix. Isogai et al. proposed chi2 attack with the rotation fixed to zero in the last round and showed the success probability of the chi2 attack against RC6P by using the result of distinguisher from random number. Takano et al. improved Isogai's chi2 attack and showed the attack was faster than an exhaustive key search for RC6/16/24 and RC6/16/32. Hinoue et al. proposed asymmetric chi2 test attack. The main feature of the attack is to deal with the position of test bits and key to recover asymmetrically. The computational complexity necessary for attacking the RC6/16/24 or RC6/16/32 was reduced from 2181 to 2158. To calculate the theoretical success probability of asymmetric chi2 test attack, they assumed the distribution of the chi2 value with a wrong key. However, there is greater difference between the experimental value and the theoretical value of the attack success probability than Takano's attack.
RC4 was designed by Ron Rivest in 1987. RC4 is the most widely used stream cipher in software applications. It is used to protect Internet traffic as part of the SSL and WEP. It was kept as a trade secret until it leaked out in 1994. RC4 has a secret internal state Fluhrer and McGrew designed a distinguisher of RC4 streams from random streams with statistical biases of two consecutive outputs. They also analyzed Fortuitous states of which only a values affect a consecutive outputs. Mantin showed digraphs tend to repeat with short gaps between them and how an attacker can use these biased patterns to distinguish RC4 streams from random streams. Fluhrer and McGrew showed some examples of state transitions related to digraphs. However it isn't known how many of digraphs appear.

In this paper, first, we reconsider the assumption of the distribution of the chi2 value with a wrong key for asymmetric chi2 test attack against RC6 and evaluate the strict theoretical success probability of the attack. Second, we focus on digraphs of RC4 including same values. We analyze state transitions related to these digraphs