# Security Analysis of the Symmetric Cryptosystem Tiny Jambu
## 5 Statistical Analysis of Randomness
### Graphical Tests  
In this subsection, we discuss the application of the main graphical tests developed in reference [18]. These tests were implemented in Matlab 9.1 and executed on the PC described in Section 1. Most of the graphical tests group the bits in octets (groups of eight bits), except for the linear complexity test, which analyzes the sequence bit after bit, and the chaos game, which considers the bits in groups of two elements. Now, we detail the applied tests. This test is a measure of the sequence entropy, which would detect any useful information about the parameters used in the design of the sequence generator. The result of this test should be a distribution of points with no trends, no lines, no figures, etc., that is, without any specific pattern. Basically, the return map is a graph of the sequence terms \(x_{t}\) as a function of the previous terms \(x_{t-1}\). Figure 3 shows the return map of a keystream sequence generated using TinyJambu. In fact, it exhibits a cloud of disordered points spread out all over the rectangle without any particular distribution. In brief, it does not provide any information for a possible cryptanalysis, and consequently, from the point of view of this graphical test, the sequence is suitable for cryptographic application. In [18] (Section 5, Figure 3a,b), several examples of return maps obtained from quadratic generators reveal clearly geometric structures and a lack of randomness. 2. Linear Complexity  
Traditionally, linear complexity (LC) is a measure of the unpredictability of a sequence, which is a powerful metric for cryptographic sequences. LC is defined as the length of the shortest Linear Feedback Shift Register (LFSR) able to generate such a sequence [23] (pp. 27-29). The algorithm of Berlekamp-Massey [24] computes the value of this parameter. A typical linear complexity profile is a staircase graph that closely follows, but irregularly, the 1/2 line (that is, the straight line with a slope of 1/2), exhibiting average step lengths and step heights of values 2 and 4, respectively. More details concerning LC can be found in [25,26]. For cryptographic purposes, the complexity must be as large as possible. In practice, for a sequence of period T, its LC must satisfy \(LC\cong T/2\). In Figure 4, we can see (a) the complexity profile for the first 20,000 bits of a TinyJambu sequence and (b) a zoom-in of the linear complexity profile. After the analysis of 20,000 bits, the value of LC should be approximately LC = 10,000, as can be observed in Figure 4a. Figure 3: Example of return map for a TinyJambu keystream sequence: a set of disordered points that do not provide any information about the parameters of the generator. Shannon Entropy and Min-Entropy  
The entropy of a sequence is a measure of the amount of information provided by a process with a result that is the sequence, or equivalently, it is a measure of the uncertainty of a random variable X. Such a measure is expressed in bits; see [20]. Shannon entropy is defined as the average probability of all the values that the random variable can take. More precisely, let X be a random variable that takes the values x\({}_{1}\), x\({}_{2}\), x\({}_{3}\), \(\ldots\), x\({}_{n}\). Thus, Shannon entropy is defined as  
\[H(X)=-\sum_{i=1}^{n}Pr(x_{i})\cdot log_{2}(Pr(x_{i})).\]  
If the process is the generation of a sequence of integers modulo m, perfectly random with m = 2\({}^{n}\), then its entropy is equal to n. In our case, the entropy of a random sequence must be close to n = 8 bits per octet (byte). The min-entropy is the measure of the probability of the more frequent occurrence value of the random variable. It is a measure recommended by the NIST SP 800-90B standard for True Random Number Generators. In order to determine whether the TinyJambu generator of keystream sequences is suitable for these values of entropy, we can say that for a sequence of 2\({}^{20}\) bytes, the Shannon entropy must be \(\geq\)7.976 bits per byte, while the min-entropy must be approximately 7.91 bits per byte.