Paper 2013/572

Quad-RC4: Merging Four RC4 States towards a 32-bit Stream Cipher

Goutam Paul, Subhamoy Maitra, and Anupam Chattopadhyay

Abstract

RC4 has remained the most popular software stream cipher since the last two decades. In parallel to cryptanalytic attempts, researchers have come up with many variants of RC4, some targeted to more security, some towards more throughput. We observe that the design of RC4 has been changed a lot in most of the variants. Since the RC4 structure is quite secure if the cipher is used with proper precautions, an arbitrary change in the design may lead to potential vulnerabilities, such as the distinguishing attack (Tsunoo et al., 2007) on the word-oriented variant GGHN (Gong et al., 2005). Some variants keep the RC4 structure (Maitra et al., 2008), but is byte-oriented and hence is an overkill for modern wide-word processors. In this paper, we try to combine the best of both the worlds. We keep the basic RC4 structure which guarantees reasonable security (if properly used) and we combine 4 RC4 states tacitly to design a high throughput stream cipher called {\em Quad-RC4} that produces $32$-bit output at every round. The storage requirement for the internal state is only $1024$ bits. In terms of speed, this cipher performs much faster than normal RC4 and is comparable with HC-128, the fastest software stream cipher amongst the eSTREAM finalists. We also discuss the issue of generalizing the structure of Quad-RC4 to higher word-width variants.

Note: This is a work in progress which began in May 2012. Part of this work was mentioned in a tutorial talk by the second author at INDOCRYPT 2012.