Certain Observations on ACORN v3 and the Implications to TMDTO Attacks

Abstract

ACORN is a lightweight authenticated cipher which is one of the selected designs among the fifteen third round candidates. This is based on the underlying model of a stream cipher with 6 LFSRs of different lengths and three additional bits. In this paper we consider the scenario that certain amount of key stream bits and some portion of the state is known. Then we try to discover the rest of the state bits. For example, we show that the LFSR of length 47 can be recovered from 47 key stream bits and guessing the rest of the state bits. We also present the implication of such results towards mounting TMDTO attack on ACORN v3. We show that a TMDTO attack can be mounted with preprocessing complexity $2^{171}$ and $2^{180}$ (without and with the help of a SAT solver) and the maximum of online time, memory and data complexity $2^{122}$ and $2^{120}$ respectively. While our results do not refute any claim of the designer, these observations might be useful for further understanding of the cipher.

1 Introduction

A new competition CAESAR (Competition for Authenticated Encryption: Security, Applicability, and Robustness) [4] has been initiated recently with the first submission deadline in March 2014. The selected candidates of the third round are now available and ACORN v3 is one among those [10]. This is a lightweight authenticated stream cipher composed of 6 Linear Feedback Shift Registers (LFSRs) and four additional bits, making a state size of 293 bits. It promises a 128-bit security using a 128-bit secret key and IV.

Given that the present ciphers are designed with well informed efforts, refuting the designer’s claim are quite challenging and sometimes even elusive. However, there are important observations discovered by the cryptanalysts that help in providing more robust ciphers. This is the reason ACORN has been revised twice and the current version is ACORN v3. In this paper we concentrate on this cipher and try to see how well one can obtain certain portion of the state bits of ACORN v3 given some key stream bits and the rest of the bits of the state. This is related to sampling resistance as noted in [2, 3]. In particular, we observe that the LFSR of length 47 $(S_{107}, \ldots , S_{153})$ can be recovered from 47 key stream bits and knowing the rest $293-47 = 246$ state bits of ACORN v3. This is achieved by writing a set of several equations and feeding them to a SAT solver such as SAGE [8]. Similarly, the 60 bits $(S_{0}, \ldots , S_{59})$ of the LFSR having length 61 $(S_{0}, \ldots , S_{60})$ could be recovered from 72 key stream bits and the rest 233 state bits of the cipher. This is presented in Sect. 2. This kind of observation helps in mounting Time-Memory-Data-Trade-Off (TMDTO) attack on stream ciphers with varied parameters.

In TMDTO attack, we have four parameters, the preprocessing time P, the amount of Memory (table in secondary storage) required M, the amount of Data D (which is the key stream in case of a stream cipher) and the time T (the number of accesses to the table, i.e., the secondary storage). In case the key is of k-bits and all the parameters P, M, T, D are less than $2^k$, then it can be considered as a break. It has been pointed out in [10, Sect. 3.3.2] that as the state size $(n = 293)$ of ACORN v3 is more than twice the secret key size $(k = 128)$, such an attack is elusive. However, there is another implication of TMDTO attack, where we allow the preprocessing time to be more than the exhaustive key search and then try to minimize the maximum of the online parameters M, T, D. In case the online parameters are less than $2^k$, that attracts some interest in terms of cryptanalysis. In case of BG attack [1, 5], the best situation is achieved when $P = T = M = D = 2^{\frac{n}{2}}$ and M, D can be reduced at the cost of increasing $P = T$. Thus, achieving $\max \{T, M, D\} < 2^{\frac{n}{2}}$ is not possible even when $P > 2^{\frac{n}{2}}$. Rather, we follow the idea of [2, 3], where it is possible to reduce all three of the online parameters T, M, D less than $2^{\frac{n}{2}}$ at the cost of increasing the preprocessing time P over $2^{\frac{n}{2}}$. In this regard, we obtain parameters like $P = 2^{171}, M = T = D = 2^{120}$, where all the online parameters are less than the complexity of exhaustive key search $2^{128}$ in case of ACORN v3 [10]. This is presented in Sect. 3. Before proceeding further, let us describe the cipher first.

1.1 Description of ACORN v3

We briefly state here the description of ACORN v3 relevant to our work. We assume the plaintext message to be a stream of 0’s and we concentrate only on the Pseudo Random Generation Algorithm (PRGA) that provides the key stream. We omit the Key Loading Algorithm (KLA) and the Key Scheduling Algorithm (KSA) of the cipher that are available at [10]. This is because the recovery of secret state bits during the PRGA and further the TMDTO attack can be studied irrespective of the initialization process. As stated before, ACORN v3 has 6 LFSRs and four additional bits concatenated to form the 293 bit state. The block diagram of ACORN is represented in Fig. 1 where $f_t$ represents the feedback bit and $m_t$ represents the message bit at $t^{th}$ step [10]. We denote the state of the cipher by $\mathscr {S}_t$ and its respective bits as: $S_{t+0} \ldots S_{t+292}$. The cipher has the following three functions.

Fig. 1.

The internal state of ACORN cipher.

Output Function. The output bit $z_t$ for any state t is generated as:

$$\begin{aligned} \begin{aligned} z_t =&S_{t+12} \oplus S_{t+154} \oplus maj(S_{t+235},S_{t+61},S_{t+193}) \\&\oplus \,ch(S_{t+230}, S_{t+111}, S_{t+66}) \end{aligned} \end{aligned}$$

(1)

Feedback Function. The feedback bit $f_{t}$ for any state t is generated as:

$$ \begin{aligned} \begin{aligned} f_t =&S_{t+0} \oplus ({\sim }{S_{t+107}}) \oplus maj(S_{t+244}, S_{t+23}, S_{t+160}) \\&\oplus \,(ca_t \, \& S_{t+196}) \oplus (cb_t \& z_t) \end{aligned} \end{aligned}$$

(2)

State Update Function. Before performing the shift, the bits $S_{t+289}$, $S_{t+230}$, $S_{t+193}$, $S_{t+154}$, $S_{t+107}$, $S_{t+61}$ are updated as follows:

$$\begin{aligned} S_{(t+289)}&= S_{(t+289)} \oplus S_{(t+235)} \oplus S_{(t+230)}\end{aligned}$$

(3)

$$\begin{aligned} S_{(t+230)}&= S_{(t+230)} \oplus S_{(t+196)} \oplus S_{(t+193)}\end{aligned}$$

(4)

$$\begin{aligned} S_{(t+193)}&= S_{(t+193)} \oplus S_{(t+160)} \oplus S_{(t+154)}\end{aligned}$$

(5)

$$\begin{aligned} S_{(t+154)}&= S_{(t+154)} \oplus S_{(t+111)} \oplus S_{(t+107)}\end{aligned}$$

(6)

$$\begin{aligned} S_{(t+107)}&= S_{(t+107)} \oplus S_{(t+66)} \oplus S_{(t+61)}\end{aligned}$$

(7)

$$\begin{aligned} S_{(t+61)}&= S_{(t+61)} \oplus S_{(t+23)} \oplus S_{(t+0)} \end{aligned}$$

(8)

And then the next bit is initialized with the feedback bit:

$$\begin{aligned} S_{t+293} = f_t \end{aligned}$$

(9)

2 Methods to Recover Certain Bits of the State

The underlying motivation of BSW sampling [2, 3] is the fact that certain bits of the state can be recovered by observing the key stream sequence $z^t$ and guessing the remaining part of the state. This reduces the search space and offers a wider range of parameters to choose from in TMDTO attack. We consider two approaches here. The first one is using the SAT solver and the other one is by discovering the equations by hand using trial and error.

2.1 Using SAT Solver

Towards this we first form a family of equations and then feeding them into a SAT solver. While forming the equations, the degree of equations formed increases rapidly, which makes it very difficult to find solutions. Hence, we have to adopt a specific approach for formulating equations by introducing new variables. This is in line of [9]. Consider some PRGA round t of ACORN v3. The equations for the same round are:

• 1. 1 output bit equation,

• 2. 1 feedback bit equation, and

• 3. 6 state update equations.

At the beginning of PRGA, the adversary has 293 state variables $S_0, S_1, \ldots , S_{292}$. The adversary has access to an $\ell$-length key stream $z_0, z_1, \ldots z_{\ell - 1}$. We will now explain how the output equation is introduced into the system of equations. The output equation as mentioned in (1) is:

$$\begin{aligned} z_t&= S_{t+12} \oplus S_{t+154} \oplus maj(S_{t+235}, S_{t+61}, S_{t+193}) \nonumber \\&\qquad \qquad \qquad \qquad \oplus \,ch(S_{t+230}, S_{t+111}, S_{t+66}) \end{aligned}$$

(10)

To add an equation to the SAT solver, the equations are represented in a way such that it is zero in the ring of Boolean polynomials. That is, the output equation is written as

$$\begin{aligned} z_t&\oplus S_{t+12} \oplus S_{t+154} \oplus maj(S_{t+235}, S_{t+61}, S_{t+193}) \nonumber \\&\qquad \qquad \qquad \oplus \,ch(S_{t+230}, S_{t+111}, S_{t+66}) \equiv 0, \end{aligned}$$

(11)

for $t = 0, 1, 2, \ldots , \ell -1$ and added to the system. Thus we have an array of output equations as:

$$\begin{aligned}&z_0 \oplus S_{12} \oplus S_{154} \oplus maj(S_{235}, S_{61}, S_{193}) \oplus ch(S_{230}, S_{111}, S_{66}) \equiv 0 \nonumber \\&z_1 \oplus S_{13} \oplus S_{155} \oplus maj(S_{236}, S_{62}, S_{194}) \oplus ch(S_{231}, S_{112}, S_{67}) \equiv 0 \nonumber \\&\vdots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \nonumber \\&z_{(\ell -1)} \oplus S_{(\ell -1+12)} \oplus S_{(\ell -1+154)} \oplus maj(S_{(\ell -1+235)}, S_{(\ell -1+61)}, S_{(\ell -1+193)}) \nonumber \\&\oplus \,ch(S_{(\ell -1+230)}, S_{(\ell -1+111)}, S_{(\ell -1+66)}) \equiv 0 \nonumber \end{aligned}$$

Next we discuss the inclusion of feedback bit equation into the system of equations. The equation as mentioned in (2) for PRGA is:

$$\begin{aligned} f_t = S_{t+0} \oplus ({\sim }{S_{t+107}}) \oplus maj(S_{t+244}, S_{t+23}, S_{t+160}) \oplus S_{t+196} \end{aligned}$$

(12)

However, the feedback bit generated is not known. Thus directly substituting the state variable $S_{t+293}$ by feedback equations increases non-linearity. Instead, the we introduce new variables $f_0, f_1, \ldots f_{\ell -1}$ and add these equations to the SAT solver in the following manner:

$$\begin{aligned}&f_0 \oplus S_{0} \oplus ({\sim }{S_{107}}) \oplus maj(S_{244}, S_{23}, S_{160}) \oplus S_{196} \nonumber \equiv 0\\&f_1 \oplus S_1 \oplus ({\sim }{S_{108}}) \oplus maj(S_{245}, S_{24}, S_{161}) \oplus S_{197} \nonumber \equiv 0\\&\vdots \ \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \nonumber \\&\vdots \ \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \quad \ldots \nonumber \\&f_{(\ell -1)} \oplus S_{(\ell -1)} \oplus ({\sim }{S_{(\ell -1 + 107)}}) \nonumber \\&\oplus \,maj(S_{(\ell -1 +244)}, S_{(\ell -1 +23)}, S_{(\ell -1 +160)}) \oplus S_{(\ell -1+196)} \equiv 0 \nonumber \end{aligned}$$

By now, 2$\ell$ new equations and $\ell$ new variables have been introduced into the system. The variables $S_{t+289}, S_{t+230}, S_{t+193}, S_{t+154}, S_{t+107}, S_{t+61}$ are updated in Step 3 as mentioned earlier. For this, we introduce 6$\ell$ new variables $a^0_1$, $a^0_2$, $a^0_3$, $a^0_4$, $a^0_5$, $a^0_6$, $\ldots$, $a^{\ell -1}_1$, $a^{\ell -1}_2$, $a^{\ell -1}_3$, $a^{\ell -1}_4$, $a^{\ell -1}_5$, $a^{\ell -1}_6$ and add the following equations to the system (for $t = 0, 1, \ldots , \ell -1$):

$$\begin{aligned} a^{t}_1&\oplus S_{(t + 289)} \oplus S_{(t + 235)} \oplus S_{(t + 230)} \equiv 0\\ a^{t}_2&\oplus S_{(t + 230)} \oplus S_{(t + 196)} \oplus S_{(t + 193)}\equiv 0\\ a^{t}_3&\oplus S_{(t + 193)} \oplus S_{(t + 160)} \oplus S_{(t + 154)}\equiv 0\\ a^{t}_4&\oplus S_{(t + 154)} \oplus S_{(t + 111)} \oplus S_{(t + 107)}\equiv 0\\ a^{t}_5&\oplus S_{(t + 107)} \oplus S_{(t + 66)} \oplus S_{(t + 61)} \, \, \, \, \equiv 0\\ a^{t}_6&\oplus S_{(t + 61)} \oplus S_{(t + 23)} \oplus S_{(t + 0)}\ \quad \, \equiv 0\\ \end{aligned}$$

Since new variables have been introduced, new equations need to be introduced to maintain consistency of the system. That is, the following equations are added to the system:

$$\begin{aligned} a^{t}_1 \oplus S_{(t+288)}\equiv 0\\ a^{t}_2 \oplus S_{(t+229)}\equiv 0\\ a^{t}_3 \oplus S_{(t+192)}\equiv 0\\ a^{t}_4 \oplus S_{(t+153)}\equiv 0\\ a^{t}_5 \oplus S_{(t+106)}\equiv 0\\ a^{t}_6 \oplus S_{(t+60)}\equiv 0\\ \end{aligned}$$

for $t = 0, 1, \ldots , \ell -1$. Finally, we substitute the feedback bit into the state variable:

$$\begin{aligned} S_{293+t} = f_t \quad \quad \forall t \in [0,\ell -1]. \end{aligned}$$

Therefore, the number of variables used are $293 + \ell + 6\ell = 293 + 7\ell$ and the number of equations formulated are $\ell + \ell + 6\ell = 8\ell$ equations. All the equations are collected and fed to the SAT solver.

We set the SAT solver to find all possible solutions for the above system of equations. In this way, we are guaranteed that if the SAT solver returns only one solution, no other solution exists for the system of equations, and hence we are able to solve for the state. However, in few cases of our experiments we could not achieve that. For example, when we consider recovery of 60 bits with the help of 70 key stream bits, we sometimes obtain two solutions. The reason for the same is that the number of key stream bits is not enough and thus the SAT solver provides more solutions instead of a unique solution.

We use the SAT solver Cryptominisat-2.9.6 available with Sage-7.6 [8]. The experiments were performed on a laptop having hardware configuration Intel(R) Core(TM) i5-4200M CPU @ 2.50 GHz and 8 GB RAM running with Ubuntu-16.10. A few experimental data are provided where each row is based on $2^{15}$ experiments.

Table 1. Experimental results for solving the equations. The time required to run the PRGA for 293 clocks is 0.088 s on an average.

2.2 Formation of Equations by Observation, not Using SAT Solver

In this section, we build the system of equations used to recover 49 bits of internal state by using first 49 bits of keystream. To perform this recovery, we need to fix 10 bits of internal state with a particular pattern and guess remaining state bits. The internal state bits to be recovered are represented by set $\mathscr {R} =\mathscr {R}_{1}\cup \mathscr {R}_2$, where $\mathscr {R}_{1}= \{S_{(t+107)} : t=0,\ldots , 43\}$ and $\mathscr {R}_2= \{S_{(t+56)} : t=0,\ldots , 4\}$. The Eq. (1) for genrating keystream can be written as:

$$\begin{aligned} \begin{aligned} z_t&=S_{(t+12)} \oplus \overline{S_{(t+154)}} \oplus S_{(t+235)} \overline{S_{(t+61)}} \oplus S_{(t+235)}\overline{S_{(t+193)}} \oplus \,\overline{S_{(t+193)}} \overline{S_{(t+61)}} \\&\oplus \overline{S_{(t+230)}} S_{(t+111)} \oplus \overline{S_{(t+230)}}S_{(t+66)} \oplus S_{(t+66)}. \end{aligned} \end{aligned}$$

(13)

Note that in the above equation, over-lined bits are feedback bits. The state bits are updated according to the following equations before generating the output bit:

$$\begin{aligned} \begin{aligned} S_{(t+289)}&= S_{(t+289)} \oplus S_{(t+235)} \oplus S_{(t+230)}\\ S_{(t+230)}&= S_{(t+230)} \oplus S_{(t+196)} \oplus S_{(t+193)}\\ S_{(t+193)}&= S_{(t+193)} \oplus S_{(t+160)} \oplus S_{(t+154)}\\ S_{(t+154)}&= S_{(t+154)} \oplus S_{(t+111)} \oplus S_{(t+107)}\\ S_{(t+107)}&= S_{(t+107)} \oplus S_{(t+66)} \oplus S_{(t+61)}\\ S_{(t+61)}&= S_{(t+61)} \oplus S_{(t+23)} \oplus S_{(t+0)} \end{aligned} \end{aligned}$$

(14)

Thus, the Eq. (13) can be written as

$$\begin{aligned} \begin{aligned} S_{(t+107)}&=z_t \oplus S_{(t+12)}\! \oplus S_{(t+154)} \oplus S_{(t+111)} \oplus S_{t+235} (S_{(t+61)} \oplus S_{(t+23)} \oplus S_{(t+0)}) \\&\oplus \,S_{(t+235)}(S_{(t+193)} \oplus S_{(t+160)} \oplus S_{(t+154)}) \\&\oplus \,(S_{(t+193)} \oplus S_{(t+160)} \oplus S_{(t+154)})(S_{(t+61)} \oplus S_{(t+23)} \oplus S_{(t+0)}) \\&\oplus \,(S_{(t+230)} \oplus S_{(t+196)} \oplus S_{(t+193)}) S_{(t+111)} \\&\oplus \,(S_{(t+230)} \oplus S_{(t+196)} \oplus S_{(t+193)})S_{(t+66)} \oplus S_{(t+66)}, \end{aligned} \end{aligned}$$

(15)

which makes the recovery simpler, because all the bits on the RHS of the equation are state bits (and not feedback bits) for $t=0, \ldots , 32$. However when we place $t=33, \ldots , 48$ in Eq. (15), feedback bits are also involved and need to be calculated.

Now we use Eq. (15) to recover internal state bits of set $\mathscr {R}_{1}$. The recovery of state bits is done in a certain order. For example, if we attempt to recover $S_{107}$ by placing $t=0$ in Eq. (15), then $S_{111}$ appears on the RHS of the equation and requires the knowledge of $S_{111}$. Thus, $S_{111}$ is recovered before performing the recovery of $S_{107}$.

We define four sets $\mathscr {R}_{3}, \mathscr {R}_{4}, \mathscr {R}_{5}$, $\mathscr {R}_{6}$, where

$$\begin{aligned} \mathscr {R}_{3}=\{ S_{(t+107)} : t=40, 36,\ldots , 0\} \\ \mathscr {R}_{4}= \{ S_{(t+107)} : t=41, 37,\ldots , 1\} \\ \mathscr {R}_{5}= \{ S_{(t+107)} : t=42, 38,\ldots , 2\}\\ \mathscr {R}_{6}= \{ S_{(t+107)} : t=43, 39,\ldots , 3\} \end{aligned}$$

and each $\mathscr {R}_{i} \subset \mathscr {R}_{1}$, for $i=3 \ldots , 6$. The order of recovery of state bits is $\mathscr {R}_{3}, \mathscr {R}_{4}, \mathscr {R}_{5}, \mathscr {R}_{6}$ and $\mathscr {R}_{2}$, respectively, i.e. the state bits of $\mathscr {R}_{3}$ are recovered first then $\mathscr {R}_{4}$ and so on. For each set $\mathscr {R}_{i} : i=2 \ldots , 6$, the higher index elements are recovered first. We need not fix any internal state bits for recovering $\mathscr {R}_{1}$. However, to recover $\mathscr {R}_{2}$, the internal state bits are fixed according to Table 2. Let the set $\mathscr {F}$ represent the internal state bits which are fixed according to Table 2.

Table 2. State bits fixed.

Now we describe recovery of $\mathscr {R}_{3}$. The internal state bit $S_{147}$ is recovered by substituting $t=40$ in Eq. (15). From this we have

$$\begin{aligned} \begin{aligned} S_{147}&=z_{40} \oplus S_{52} \oplus \overline{S_{194}} \oplus S_{151} \oplus S_{275} (S_{101} \oplus \overline{S_{63}} \oplus S_{40}) \\&\oplus \,S_{275}(\overline{S_{233}} \oplus \overline{S_{200}} \oplus \overline{S_{194}}) \oplus (\overline{S_{233}} \oplus \overline{S_{200}} \oplus \overline{S_{194}}) (S_{101} \oplus \overline{S_{63}} \oplus S_{40}) \\&\oplus \,(S_{270} \oplus \overline{S_{236}} \oplus \overline{S_{233}}) S_{151} \oplus (S_{270} \oplus \overline{S_{236}} \oplus \overline{S_{233}})S_{106} \oplus S_{106}. \end{aligned} \end{aligned}$$

(16)

In Eq. (16), all the bits appearing on the RHS of the equation are guessed, except the over-lined bits. The over-lined bits are feedback bits, and not internal state bits due to Eq. (14). Thus, we need to guess more internal state bits to calculate the value of $S_{63}, S_{194}, S_{200}, S_{233}$ and $S_{236}$ using Eq. (14). In this way, we recover $S_{147}$.

Now the internal state bit of $S_{143}$ is recovered by placing $t=36$ in Eq. (15) and we derive

$$\begin{aligned} \begin{aligned} S_{143}&=z_{36} \oplus S_{48} \oplus {S_{190}} \oplus S_{147} \oplus S_{271} (S_{97} \oplus {S_{59}} \oplus S_{36}) \\&\oplus \,S_{271} ({S_{229}} \oplus \overline{{S_{196}}} \oplus {S_{190}}) \oplus ({S_{229}} \oplus \overline{{S_{196}}} \oplus {S_{190}}) (S_{97} \oplus {S_{59}} \oplus S_{36}) \\&\oplus \,(S_{266} \oplus \overline{{S_{232}}} \oplus {S_{229}}) S_{147} (\oplus S_{266} \oplus \overline{{S_{232}}} \oplus {S_{229}})S_{102} \oplus S_{102}. \end{aligned} \end{aligned}$$

(17)

Similarly, in Eq. (17), all the state bits appearing on the right side of equation need to be guessed, except $S_{271}, S_{190}$ and the over-lined bits. The internal state bits $S_{271}$ and $S_{190}$ are fixed according to Table 2. The over-lined bits are calculated using Eq. (14). Thus, we need to guess more internal state bits to calculate the value of $S_{196}, S_{232}$ and recover $S_{143}$.

The remaining state bits of $\mathscr {R}_{3}$ i.e. $S_{139}, S_{135}, \ldots , S_{107}$ are recovered by substituting $t=32, 28, \ldots , 0$, respectively, in Eq. (15). While placing $t=32, 28, \ldots , 0$ in Eq. (15), the internal state bits appearing on the RHS of the equation are guessed, except state bits belonging to $\mathscr {R}$ and $\mathscr {F}$. Following the same methodology, the internal state bits of set $\mathscr {R}_{4}, \mathscr {R}_{5}$ and $\mathscr {R}_{6}$ are recovered.

To recover the state bits of set $\mathscr {R}_{2}$, all things are same as done earlier, except for Eq. (13) which is rewritten as

$$\begin{aligned} \begin{aligned} S_{t+12}&=z_t \oplus S_{(t+107)} \oplus S_{(t+154)} \oplus S_{(t+111)} \oplus S_{t+235} (S_{(t+61)} \oplus S_{(t+23)} \oplus S_{(t+0)}) \\&\oplus \,S_{t+235}(S_{(t+193)} \oplus S_{(t+160)} \oplus S_{(t+154)}) \\&\oplus \,(S_{(t+193)} \oplus S_{(t+160)} \oplus S_{(t+154)})(S_{(t+61)} \oplus S_{(t+23)} \oplus S_{(t+0)}) \\&\oplus \,(S_{(t+230)} \oplus S_{(t+196)} \oplus S_{(t+193)}) S_{t+111} \\&\oplus \,(S_{(t+230)} \oplus S_{(t+196)} \oplus S_{(t+193)})S_{t+66} \oplus S_{t+66}. \end{aligned} \end{aligned}$$

(18)

Thus, the internal state bits $S_{56}, \ldots , S_{60}$ are recovered by using $t=44, \ldots , 48$ in Eq. (18), respectively. Another difference between recovery of $\mathscr {R}_{1}$ and $\mathscr {R}_{2}$ is that it is not necessary to recover the higher index elements first (as done before).

In this way, we recover 49 bits of $\mathscr {R}$ by fixing the 10 internal state bits of set $\mathscr {F}$ and guessing the remaining 234 state bits. However, there are nine internal state bits i.e. $S_{284}, \ldots , S_{292}$ which are not appeared in the equations used for recovery. However these bits are also considered as guessed bits during application of TMDTO attack. In the Table 3, the details of equations are given used for recovery of state bits of set $\mathscr {R}$. The over-lined state bits and underlined state bits in Table 3 are feedback bits and fixed state bits (according to Table 2), respectively.

Table 3. Recovery of 49 bits of the internal state after fixing 10 bits

3 Complexity of TMDTO Attack

Now we will describe the TMDTO attack in complete detail. We have a state size of $n = 293$ bits. Thus, the standard TMDTO formula [2, 3] with a single table will be as follows:

• $TM^2D^2 = N^2$, where $N = 2^n$,

• $D^2 \le T$,

• $P = \frac{N}{D}$.

During the preprocessing phase, we will prepare a table with m rows and t columns, where $mt^2 = N$ for a successful attack. The number of tables is $\frac{t}{D}$ and given a single table we have $t = D$. Each row of the table contains a chain of t elements. Consider that a specific state of $n = 293$ bits is $\zeta$ and f is the one way function. Here by one way function f, we mean that the cipher with the state $\zeta$ will be run for n times again to generate n many key stream bits. Those bits will be loaded as the new state, which is called $\eta$. That is $\eta = f(\zeta )$. We will start with a random state and then generate a row of t elements by this method. There will be m such rows. Thus, the total table size is mt. However, the complete row will not be saved. Only the starting and the final element will be saved. Thus, the storage requirement of the table will be O(m), which is actually the memory parameter M.

3.1 Knowledge of 47 Bits of State from 47 Key Stream Bits

Now consider the case when we are able to recover $\psi$ bits of the state from $\psi$ consecutive key stream bits and the rest of the state bits. In this case, we consider a fixed pattern for the key stream bits and only when that pattern is found in the key stream, we try to search the state in the table. Thus, in this case, we consider a state size of $n-\psi$ bits and the parameters are referred as $N' = 2^{n-\psi }$, $P', M', T', D'$. Let us now consider the exact parameters referring to Table 1, where $\psi = 47$. Thus, $T'M'D'^2 = N'^2 = 2^{2(293-47)}$. Let us consider $D'^2 = T$. Thus, we have $T'M' = 2^{293-47} = 2^{246}$. Now, one can consider, $T' = M' = 2^{123}$ and $D' = 2^{61.5}$. However, as we have discussed that during the online phase, we can only mount the attack when a specific $\psi$-bit pattern comes, we have $D = 2^\psi D'$. Thus, finally, we will have the parameters $T = T' = 2^{123}$, $M = M' = 2^{123}$, $D = 2^\psi D' = 2^{47} \cdot 2^{61.5} = 2^{108.5}$, $P = P' = \frac{N'}{D'} = 2^{184.5}$. This provides the maximum of online parameters as $2^{123}$, which is less than the exhaustive secret key search of complexity $2^{128}$. However, as expected, the pre-processing time is much larger than the exhaustive key search.

At this point, we like to explain about certain ‘unit’ cost related to exact complexity. Such unit cost may involve several computations related to the cipher operations. In a most generic way, given a k-bit secret key, the exhaustive attack asks for a complexity of $2^k$ units, where each unit may require several CPU clocks. While mounting the TMDTO attack the same situation is valid. Thus, in our technique, we also consider all the operations as unit cost. However, we will point out a few cases when our calculations are most costly and that should be taken care of in the complexity analysis. For example, simply generating a 293-bit key stream (that will become the state $\eta$) of ACORN v3 from a state $\zeta$ requires 0.088 s in our computing facility. However, to recover the 47 bits of the state from 47 bits of key stream and the remaining state bits requires a time of 0.076 s, which is almost as same as the time taken to generate $\zeta$. Thus, no additional complexity is required for solving. Hence for this scenario our parameters are as follows. We can take $T' = 2^{122}, M' = 2^{124}$ and $D' = 2^{61}$. Then, $T = T' \cdot 2^0 = 2^{122}$, $M = M' = 2^{124}$, $D = 2^\psi \cdot D' = 2^{47} \cdot 2^{61} = 2^{108}$, $P = P' = \frac{N'}{D'} = 2^{185}$.

3.2 Knowledge of 53 Bits of State from 60 Key Stream Bits

We follow a similar procedure as mentioned in Sect. 3.1. However, when the SAT solver is populated with equations and is set to find all possible solutions for 53 state bits using only 53 key stream bits, the SAT solver fails to find a unique solution. Instead, we get multiple solutions, where each solution provides the same 53-bit key stream pattern. To combat this problem, we involve a new idea. Instead of searching for a 53-bit pattern (say 53 continuous 0’s), we search for a 240-bit pattern where the first 53-bit sequence and the last 7-bit sequence are fixed (say to 0’s). This is based on the fact that the key stream sequence generated by all solutions are different. The SAT solver identifies the difference between the sequence of last 7 bits and removes all additional solutions. However, this gives us an additional Data complexity of $2^7$. Considering this constraint into the SAT solver in a similar fashion, (as explained in Sect. 2.1), we get the data mentioned in Table 1. However, in very few cases, two solutions sets are possible which generate the same keystream. Since the proportion is very small and our success probability is $\frac{2^{14}-1}{2^{14}}$, the time complexity should be multiplied by $T' = T' \times \frac{2^{14}}{2^{14}-1} \approx T' \times 1 = T'$. However, we still attempt to deal with this edge case scenario of two solutions. The idea is to simply discard the second solution during the offline phase and continue with the first solution set. The matrix stopping rule ensures the entire search space is covered with negligible collision. During the online phase, the adversary can access few more key stream bits following the fixed pattern in the key stream and hence conclude with the final solution. Our experiments show that 7 more key stream bits, i.e. 67 key stream bits in total are enough to find a unique solution.

Similar to Sect. 3.1 the time taken for solving equations is of the same order of generating $\zeta$, hence $T =T'$.

• $T = T' = 2^{120}$ is the total time complexity of the attack,

• $M = M' = 2^{120}$ is the amount of memory required,

• $D = D' \times 2^{60} = 2^{120}$ where $D' = 2^{60}$, since the adversary must succeed in finding a 60-bit pattern,

• $P = \frac{N'}{D'} = 2^{180}$ is the preprocessing time for formulating tables.

3.3 Knowledge of 49 Bits of State from 49 Key Stream Bits and Fixing 10 State Bits

Here we consider the third approach which is similar to what has been recently considered in [7] for a TMDTO attack against Lizard [6]. We consider that $\psi$ state bits can be recovered from $\psi$ many key stream bits and rest of the state bits, but $\tau$ many state bits has to be fixed to a specific pattern. This follows the idea mentioned in Sect. 2.2. In this case we go back to single preprocessing table. We will consider $\psi = 49$ here, with $\tau = 10$. That is from $\psi$ bits of key stream and the remaining $(n-\psi )$ state bits (out of which $\tau$ are fixed to a specific pattern), we will be able to solve for the $\psi$ bits of the state. The initial table preparation goes as follows. We start with a $(n-\psi -\tau )$ bit random pattern and then take a specific pattern for $\psi$. Also the fixed pattern of $\phi$ is known. Now, using the equations as described in Sect. 2.2, we solve for the rest $\psi$ bits of the state. This gives the complete state. Then we run the PRGA for $n-\tau$ times. The initial $\psi$ bits will be as fixed. The remaining $(n-\psi -\tau )$ pseudorandom bits will be considered as the part of the next state bits. Thus, we have $T'M' = 2^{n-\psi -\tau } = 2^{293-49-10} = 2^{234}$. Let us take $T' = 2^{112}$ and $M' = 2^{122}$, which also gives, $D' = \sqrt{T'} = 2^{56}$. Thus, we will now have the following parameters.

• $D = D' \cdot 2^{\psi +\tau } = 2^{56+49+10} = 2^{115}$, as the specific pattern $\psi$ should come towards consulting the table, and also for a good success rate to have the specific $\tau$ bit pattern in the state we need to try $2^{\tau }$ many times,

• $M = M' = 2^{122}$,

• $T = T' \cdot 2^\tau = 2^{112+10} = 2^{122}$, as we only consult the preprocessing table when the specific $\psi$ bit pattern appears in the key stream, but we need to try $2^\tau$ times as we have that more data and here the solution time can be estimated from the operations in the equations and that can subsumed in the PRGA effort,

• $P = P' = \frac{N'}{D'} = 2^{234-56} = 2^{178}$.

A similar online parameter in this respect can be obtained considering the equation $5\psi +2\tau = n$. Here, $\psi = 49$, by fixing $\tau = 10$. However, we can easily increase $\tau$ to 24 to satisfy the equation $5\psi +2\tau = 5 \cdot 49 + 2 \cdot 24 = 293 = n$. That is we will fix 24 state bits to a specific pattern. In this case the online complexity becomes $T = M = D = 2^{\frac{n-\psi }{2}} = 2^{\frac{293-49}{2}} = 2^{122}$. However, the preprocessing becomes less, which is $P = 2^{\frac{n+\psi }{2}} = 2^{\frac{293+49}{2}} = 2^{171}$.

4 Conclusion

In this paper we have studied how certain portion of the state of ACORN v3 can be obtained from key stream and guessing or fixing the remaining state bits. We attempt that problem by generating a set of equations and feeding that to SAT solver. At the same time, we try to consider the structure of the equations and solve a set of equations without using the SAT solver. Several examples with different parameters are presented. Based on those parameters, we note different time-memory-data trade-off for attacking ACORN v3. Indeed it is possible to mount the attack where the online complexity is less than the exhaustive key search. The pre-processing effort is higher than exhaustive search but it can be reduced further by increasing the amount of data or by recovering more internal sate bits. While our observations do not refute any security claim of the cipher, the study adds certain insight towards the cryptanalysis and may lead to further research in this area.