# Bit Independence Criterion Extended to Stream Ciphers
## 2 Preliminaries
### Stream Ciphers and RC4  
The stream ciphers perform the encryption by converting plain text into bit-by-bit cipher-text through the use of a keystream and the XOR operation. A keystream is nothing more than a sequence of numbers generated in a pseudo-random way. This is achieved by building a pseudo-random number generator. The sequence of pseudo-random numbers used must meet certain statistical properties to be considered suitable for cryptographic use. In many applications (see [4; 31]), ciphers of this type have become very important tools since they are very fast and their implementation is simpler than other ciphers, e.g., a block cipher. In these types of scenarios, the problem is in the transmission of a large amount of data in communication networks in a short time. There are a wide variety of design proposals [32] to build pseudo-random number generators. Among these, the RC4 algorithm [23] stands out from others for its wide use in different applications and protocols. The RC4 stream cipher [23] is optimized to be used in 8-bit processors, being extremely fast and exceptionally simple. It was included in network protocols such as Secure Sockets Layer (SSL), Transport Layer Security (TLS), Wired Equivalent Privacy (WEP), Wi-Fi Protected Access (WPA), and in various applications used in Microsoft Windows, Lotus Notes, Apple Open Collaboration Environment (AOCE), and Oracle Secure SQL [23]. In the last decade, some applications [33; 34] avoided RC4 encryption given some weaknesses found [35]. However, although it is not considered very secure [36], RC4 is still one of the most widely used stream ciphers [37], and continues to motivate research nowadays [36; 37; 38]. Furthermore, this cipher is a good option to measure the effectiveness of methods that analyze weaknesses in stream ciphers related to those already known in RC4 [22; 24; 25; 26], or to check the performance of hardware or software schemes that make use of cryptography [39; 40; 41]. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Avalanche** & \multicolumn{6}{c}{**Avalanche Variables**} \\ \cline{2-9}
**Vectors** & \(\mathbf{v^{i}_{:1}}\) & \(\mathbf{v^{i}_{:2}}\) &... & \(\mathbf{v^{i}_{:j}}\) &... & \(\mathbf{v^{i}_{:k}}\) &... & \(\mathbf{v^{i}_{:m}}\) \\ \hline \(V^{i}_{1}\) & \(v^{i}_{11}\) & \(v^{i}_{12}\) &... & \(v^{i}_{1j}\) &... & \(v^{i}_{1k}\) &... & \(v^{i}_{1m}\) \\ \hline \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) \\ \hline \(V^{i}_{r}\) & \(v^{i}_{r1}\) & \(v^{i}_{r2}\) &... & \(v^{i}_{rj}\) &... & \(v^{i}_{rk}\) &... & \(v^{i}_{rm}\) \\ \hline \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) \\ \hline \(V^{i}_{l}\) & \(v^{i}_{l1}\) & \(v^{i}_{l2}\) &... & \(v^{i}_{lj}\) &... & \(v^{i}_{lk}\) &... & \(v^{i}_{lm}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: SAC matrix \(H^{i}=(v^{i}_{rj})\) of dimension \(l\times m\) for the change of bit \(i\) over the set \(D\) of \(l\) inputs. The RC4 has two main components: the key scheduling, and the pseudo-random number generator. The key scheduling generates an internal random permutation \(S\) of values from 0 to 255, from an initial permutation, a (random) key \(K\) of \(l\)-byte length, and two pointers \(i\) and \(j\). The maximal key length is of \(l=256\) bytes (see Algorithm 1). ```
1:for\(i=0\to 255\)do
2:\(S[i]\gets i\)
3:endfor
4:\(j\gets 0\)
5:for\(i=0\to 255\)do
6:\(j\leftarrow(j+S[i]+K[i\mod l])\mod n\)
7: Swap \(S[i]\) and \(S[j]\)
8:endfor
```  
**Algorithm 1** RC4 key-scheduling  
The main part of the algorithm is the pseudo-random number generator that produces one-byte output in each step. As usual, for stream ciphers, the encryption will be an XOR of the pseudo-random sequence with the message (see Algorithm 2).