Miyaji Laboratory

Symmetric key cryptography plays a very important role in information security, and before any proposed ciphers are applied in the real world, they should undergo enough cryptanalysis work. This is because even one weakness of the cipher will lead to the total break of the security. Thus we need to make sure the cipher has no flaws which are itself a very difficult task given the designer only. Also industries can gain confidence on the specific cipher through the work of cryptanalysis. This thesis mainly targets two stream ciphers, one is RC4 which is world-wide famous and old, and the other one is HC-128 which is newly proposed.

This thesis first concentrates on analyzing the weakness of stream cipher RC4, especially in the area of key collisions which is about the flaws that two different but somewhat related secret keys have the same encryption and decryption effects. Based on the previous researches, the mechanism behind the scene is investigated and discovered that the key collisions can be achieved by two keys related in pretty much different ways. This thesis then generalized the key collision mechanisms and summarized them into two patterns, namely, transitional pattern and self-absorbing pattern. All the up-to-known RC4 colliding key pairs can be concluded into either of the patterns. The probability of the key collision given the related key patterns is evaluated and the relation between the key length, hamming distance and the collision probability is revealed. A concrete attack against the RC4-Hash, proposed in 2007, is demonstrated by adapting our discovered key collision patterns.

This thesis further addresses the problem of how to find those colliding key pairs fast and efficiently. First, the key collision procedure in KSA algorithm is redefined into rounds with conditions defined in each round. A key collision is achieved if and only if two keys pass all the rounds. Thus this thesis reduces the problem to how to bypass as many rounds as possible with probability higher than random distribution. This thesis points out for transitional pattern it can bypass first, second and the last round with higher probability. And this thesis borrows the concept of multi-message modification used for attacking hash function here to speed up the searching procedure. As a result, this thesis is able to find by far the shortest 22-byte colliding key pairs in Transitional Pattern.

As a result, the doctor thesis investigates the weakness of RC 4, which gives incredible impact on the real world. His contribution is exactly enough to get a PhD degree of Information Science.