Analysis Of RC4 Algorithm

In 1987, RC4 algorithm was designed by Ron Rivest for RSADSI, which mainly differed from other algorithms of stream ciphers in highly secure and efficient nature. Just as this algorithm has so many properties, it is most commonly used to protect Internet traffic using the SSL protocol. Moreover, it was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL and many other applications. In addition, it was chosen to be part of the Cellular Digital Packet Data specification. Indeed, these uses of RC4 may make it the most widely-used stream cipher in the world.As it is used so widely, RC4 turns to be one of the goals which cryptographers take interest in. Various analysis methods in its security, which are described particularly in §1.3, were proposed in recent years, including attacks of PRGA, weak-key schedules, analysis of pseudo-randomness and so on. One of the famous attacks which we refer to as Knudsen's attack was proposed in 1998 by Knudsen et al. Though Knudsen's attack is very inefficient in time without any apriori information about the permutation S, it becomes effective when attackers possess some known values.From Knudsen's attack, it is found that the complexity not only depends on the number of known values, but the distribution in the state as well. To be important, relationship between the complexity and the distribution of known values is still an unsolved problem, which author will take into account in this paper.This paper is divided into two chapters.In 1st chapter, author will introduce some knowledge about RC4 at length in §1.1, which includes some conceptions in cryptography, relations between stream cipher and block cipher, encryption of stream cipher, classification and randomicity of stream cipher, status of RC4. And then, the details of RC4 algorithm will be specified in §1.2, in which two parts of RC4, KSA and PRGA, will be introduced. Eventually, author will bring some previous analysis of RC4 in recent years.In chapter 2, the idea of Knudsen's attack is adopted chiefly, which contains three steps as follow.Step 1. It is checked whether St-1 [it ] has been assigned a value:(a) If it has, proceed to step 2.(b) If it has not, then assign, one after one, the 2" - at remaining values toSt-1 [it ], increment a1 and go to step 2.Step 2. It is checked whether Z, has a value which has been used in an assignment:(a) if it has, we can calculate the expected value of St [jt ] from the processof RC4 algorithm. If this does not lead to a contradiction, proceed to time t +1, and go to step 1.(b) if it has not, go to step 3.Step 3. It is checked whether St-1[jt ] has already been assigned a value: (a) if is has, then assign, one after one, the 2n - at remaining values to St-1[jt ], and update a1. Subsequently, it can be checked whether thegiven values of it, jt and Zt lead to a contradiction. If they do not,proceed to time t +1, and go to step 1.Subsequently, formulations to calculate the relevant complexity by which can get each complexity with some known random values in the initial state are specified in detail. In §2.2, author analyzes some other initial states with different known values.first, author defines three fundamental types as follow.Definition 2.1 If a continuous values in initial state are known beforehand, one of which it points to, this type of initial state can be defined Type Ⅰ; If there isan unknown value in the segment of continuous values of Type Ⅰ, we define it Type Ⅱ, and here, we assume there are a continuous known values in the left of the unknown, and a' in the right; If the unknown value in Type Ⅱ becomes a segment of a' continuous unknown values, we define this Type Ⅲ.And then, author implies some conclusions.Corollary 2.1 Complexity of Type Ⅰ (?) a certain complexity of initial state, in which there are a + △α known values.At the same time, author tells us how to calculate the complexity of Type I, and lists some results as well.Corollary 2.2 Complexity of Type Ⅱ (?) complex'(a + a',a + a' +1) in theprobabilitv of Pr =Corollary 2.3 If the correct value at the position of a + 1 can be revealed successfully,complexity of Type Ⅱ (?) complex' (a + a' + 1, a + a' +1) + (1 + 2n -a-a')/2, (1 + 2n -α-a') / 2 represents the times of assignments at the position of a +1.Corollary 2.4 Complexity of Type Ⅲ (?) complex' (a + a', a + a' + a") in theprobability of After the analysis of three types above, the exact idea on how to deal with an initial state with some known values has been fully introduced, and more complicated type can be analyzed in the same way. At last the author gives a brief summary in § 2.3.