Permutation After RC4 Key Scheduling Reveals the Secret Key
A theoretical analysis of the RC4 Key Scheduling Algorithm (KSA) is presented in this paper, where the nonlinear operation is swapping among the permutation bytes. Explicit formulae are provided for the probabilities with which the permutation bytes after
- PDF / 286,376 Bytes
- 18 Pages / 430 x 660 pts Page_size
- 35 Downloads / 232 Views
2
Department of Computer Science and Engineering, Jadavpur University, Kolkata 700 032, India goutam [email protected] Applied Statistics Unit, Indian Statistical Institute, 203, B T Road, Kolkata 700 108, India [email protected]
Abstract. A theoretical analysis of the RC4 Key Scheduling Algorithm (KSA) is presented in this paper, where the nonlinear operation is swapping among the permutation bytes. Explicit formulae are provided for the probabilities with which the permutation bytes after the KSA are biased to the secret key. Theoretical proofs of these formulae have been left open since Roos’s work (1995). Based on this analysis, an algorithm is devised to recover the l bytes (i.e., 8l bits, typically 5 ≤ l ≤ 16) secret key from the final permutation after the KSA with constant probability of success. The search requires O(24l ) many operations which is the square root of the exhaustive key search complexity 28l . Further, a generalization of the RC4 KSA is analyzed corresponding to a class of update functions of the indices involved in the swaps. This reveals an inherent weakness of shuffle-exchange kind of key scheduling. Keywords: Bias, Cryptanalysis, Key Scheduling, Permutation, RC4, Stream Cipher.
1
Introduction
Two decades have passed since the inception of RC4. Though a variety of other stream ciphers have been discovered after RC4, it is still the most popular and most frequently used stream cipher algorithm due to its simplicity, ease of implementation, speed and efficiency. RC4 is widely used in the Secure Sockets Layer (SSL) and similar protocols to protect the internet traffic, and was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL, etc. Though the algorithm can be stated in less than ten lines, even after many years of analysis its strengths and weaknesses are of great interest to the community. In this paper, we study the Key Scheduling Algorithm of RC4 in detail and find out results that have implications towards the security of RC4. Before getting into the contribution in this paper, we first revisit the basics of RC4.
C. Adams, A. Miri, and M. Wiener (Eds.): SAC 2007, LNCS 4876, pp. 360–377, 2007. c Springer-Verlag Berlin Heidelberg 2007
Permutation After RC4 Key Scheduling Reveals the Secret Key
361
The RC4 stream cipher has been designed by Ron Rivest for RSA Data Security in 1987, and was a propriety algorithm until 1994. It uses an S-Box S = (S[0], . . . , S[N − 1]) of length N , each location being of 8 bits. Typically, N = 256. S is initialized as the identity permutation, i.e., S[i] = i for 0 ≤ i ≤ N − 1. A secret key of size l bytes (typically, 5 ≤ l ≤ 16) is used to scramble this permutation. An array K = (K[0], . . . , K[N − 1]) is used to hold the secret key, where each location is of 8 bits. The key is repeated in the array K at key length boundaries. For example, if the key size is 40 bits, then K[0], . . . , K[4] are filled by the key and then this pattern is repeated to fill up the entire array K. The RC4 cipher has two components, namely, the Ke
Data Loading...
