RC4, developed by Ron Rivest in 1987, is a widely used stream cipher in commercial software applications. Since no linear feedback shift registers (LFSRs) are used to implement RC4, it is ideal for software implementation. To produce a pseudorandom keystream, the RC4 cipher has two main parts: the key-scheduling algorithm (KSA) and the pseudorandom generation algorithm (PRGA). Many scholars have uncovered the insecurity of RC4. In 2001, Fluhrer, Mantin, and Shamir discovered several weaknesses in the KSA [1]. Recently, Klein presented an improved way of attacking RC4 using the correlations between the RC4 keystream and the key [2].
Tews, Weinmann, and Pyshkin demonstrated an attack of a 104-bit RC4 in less than 60 seconds [3]. Therefore, the RC4 cipher is no longer recommended for use in new applications.
In this paper, the authors point out another weakness of RC4 by showing the correlation between the first byte of the keystream output of RC4 and the sum of the first three bytes of the secret key. As mentioned above, the correlation between keystream and specific secret keys has been observed and published in several other papers. This paper is the first to prove the keystream’s correlation with any arbitrary key. Therefore, the result may be more useful for the future design and analysis of ciphers. Besides the main contribution, the authors provide theoretical proof of some experimental observations in the RC4 stream cipher related to weak keys.