# Security Analysis of the Symmetric Cryptosystem Tiny Jambu
## 3 Security of TinyJambu against Cryptanalytic Attacks
### The Concept of Active AND Gates  
Differential cryptanalysis has been applied to the nonlinear part of the cryptosystem. Since the _NAND_ logic operation is the only nonlinear component of the feedback function, it is the natural target for launching a differential attack [14]. The key idea of this cryptanalysis is to introduce two slightly different initial states in two parallel versions of TinyJambu and analyze the evolution of these differences along the encryption process. Indeed, we denote with \(S\) and \(S^{*}\) two different 128-bit states of TinyJambu. As before, \(S_{i}\) and \(S_{i}^{*}\) correspond to the \(i\)-th bits of both states (\(i\) = 0, \(\dots\), 127), respectively. Thus, the initial differential between states \(S\) and \(S^{*}\) is defined as  
\[\Delta S_{i}=S_{i}\oplus S_{i}^{*}\text{ for }(i=0,\ 1,\ \dots,127). \tag{1}\]  
After I rounds of the keyed permutation \(P_{I}\), the state bits \(S_{i}\) and \(S_{i}^{*}\) have been simultaneously shifted as described in Section 2. That is, for state \(S\), the successive feedback results satisfy the following recurrence relationship:  
\[S_{128+j}=S_{0+j}\oplus S_{47+j}\oplus\overline{S_{70+j}\cdot S_{85+j}}\oplus S _{91+j}\oplus k_{j}\quad(j=0,\ 1,\dots,l), \tag{2}\]  
and similarly for state \(S^{*}\),  
\[S_{128+j}^{*}=S_{0+j}^{*}\oplus S_{47+j}^{*}\oplus\overline{S_{70+j}^{*}S_{85+ j}^{*}}\oplus S_{91+j}^{*}\oplus k_{j}\quad(j=0,\ 1,\dots,l). \tag{3}\]  
Summing up Equations (2) and (3), we obtain a differential that also satisfies its own recurrence relationship and gives rise to a differential trail of the form  
\[\Delta S_{128+j}=\Delta S_{0+j}\oplus\Delta S_{47+j}\oplus\Delta\left(\overline {S_{70+j}\cdot S_{85+j}}\right)\oplus\Delta S_{91+j}\quad(j=0,\ 1,\dots,l). \tag{4}\]Notice that in Equation (4), the only nonlinear term is the differential of the _NAND_ logic operation notated:  
\[\Delta\big{(}\overline{S_{70+j}\cdot S_{85+j}}\big{)}=\big{(}\overline{S_{70+j} \cdot S_{85+j}}\big{)}\oplus\big{(}\overline{S_{70+j}^{*}\cdot S_{85+j}^{*}} \big{)}\quad(j=0,\ 1,\ldots,l). \tag{5}\]  
This differential propagates along the keyed permutation \(P_{l}\) and tells us when a difference between the nonlinear term of both versions takes place. Then, two different items can be pointed out:  
1. According to Equation (4), it can be noticed that in the differential trail, the terms \(k_{j}\) of the key have been cancelled as they are just additive elements. 2. Since the complementation of a logic product is defined as \(\overline{a\cdot b}=a\cdot b\oplus 1\), we can omit the constant \(1\) that appears in both summands of Equation (5) and replace the _NAND_ gate for an _AND_ gate. In this way, we obtain a new and more simplified equation in terms of an _AND_ gate: \[\Delta\big{(}S_{70+j}\cdot S_{85+j}\big{)}=\big{(}S_{70+j}\cdot S_{85+j}\big{)} \oplus\big{(}S_{70+j}^{*}\cdot S_{85+j}^{*}\big{)}\ (j=0,\ 1,\ldots,l).\] (6)  
In the following and for the sake of simplicity, we will just use the _AND_ logic operation. Now, we define a new concept related to such an operation. An _active AND gate_ is defined as a differential of value \(1\). That is,  
\[\Delta(a\cdot b)=1 \tag{7}\]  
where \(a,\ b\in\mathbb{F}_{2}=\{0,1\}\). In TinyJambu, an active _AND_ gate, notated as \(\Delta\big{(}S_{70+j}\cdot S_{85+j}\big{)}=1\), determines the difference of the nonlinear component between the two parallel versions of the generator, which allows us to perform this differential cryptanalysis. In addition, we denote with X the number of active _AND_ gates through the permutation \(P_{l}\). Since a trail with score X can be satisfied with probability \(p=2^{-X}\) (see [7], Section 3), the challenge is to look for differential trails, as those defined in Equation (4), that minimize the number X of active _AND_ gates after \(l\) rounds.