# Bit Independence Criterion Extended to Stream Ciphers
## 1 Introduction  
Randomness is an essential component in the security of cryptographic algorithms [1, 2]. In particular, stream ciphers are composed of pseudo-random number generators and base their security on the statistical characteristics of these generators [1]. Several stream ciphers can be found in the literature whose description is based on different methods for the generation of pseudo-random numbers [3]. In practice, to determine if a generator is suitable to be used for cryptographic purposes, several statistical tests are usually applied on it to measure the randomness of its outputs [4, 5, 6]. There are numerous statistical tests to measure the randomness of the outputs of a pseudo-random number generator, among these those grouped in the batteries of NIST [7], Diehard [8], TestU01 [9], and Knuth [10], among others [2]. However, despite a large number of statistical tests being present in these batteries, none of them measure the correlation between the inputs and outputs of the stream cipher; they only measure the randomness of the outputs, which is a necessary, but not sufficient, condition to consider the generator for use in cryptography. To consider a stream cipher secure, there must be no statistically significant correlation between the structure of its inputs and outputs. If \"patterns\" depending on the structure of the cipher input are generated in the output of stream ciphers, this could provide information about the input used. In the literature, there are reports of cryptanalysis based on this type of weakness [11, 12]. In this way, it is essential to avoid the previous weakness and to have methods to detect it in the design and evaluation stage of the algorithm; in particular, it is necessary to have statistical tests that are capable of detecting the existence of significant statistical dependencies between the inputs and outputs of stream ciphers. In general, there are very few statistical test reports to detect the existence of statistical dependencies between the outputs and inputs of a stream cipher. Therefore, the design of statistical tests that allow for the evaluation of them in this sense is highly important in cryptography. The strict avalanche criterion (SAC) and the bit independence criterion (BIC) were proposed in [13] to evaluate the strength of the S-boxes used in block ciphers [14]. These two criteria measure different characteristics of the change's effect that an input bit has on the output bits; while the SAC verifies uniformity in the distribution of each output bit, the BIC measures the degree of independence between the output bits [15]. The SAC has been extended to be applied to stream ciphers [16; 17; 18; 19; 20; 21; 22]. In [22], the RC4 stream cipher [23] was evaluated through the SAC and the existence of statistical dependence between the input bits and outputs of the RC4 was detected for inputs of large size. This confirms the results obtained in [24; 25; 26; 27], where the existence of related inputs in RC4 was reported. The idea developed in [22] was to determine the behavior of the distribution of the bits in the output by changing any bit in the input. In the design of stream ciphers, the distribution behavior of the output elements must be uniformly distributed, regardless of the bit that is being changed at the input [5]. Otherwise, the outputs could provide information on the input bits, which constitutes a weakness that, in the worst-case scenario, could lead to an attack. A discussion of attacks on stream ciphers can be found in [28]. However, the BIC has not been applied, to the best of our knowledge, to assess the degree of statistical independence between the bits of the output stream ciphers from changing a bit of the input. In this paper, we propose an algorithm that extends this criterion to evaluate the degree of independence between the input bits and the outputs of the stream ciphers.