1 Introduction
1.1 Our contribution
-
We novelly propose a set of toy versions of Subterranean 2.0 with reduced state size. At first glance, Subterranean 2.0 can be weakened by increasing the rate. However, it cannot be done without changing the extraction function. Therefore, a better way seems to reduce the state size. Concretely, we choose a smaller prime number 97, adapt other parameters accordingly, and let the factor d used in the round function (see Sect. 2.2) be all possible values. Then we have a set of toy versions: Subterranean-m(d) which have much smaller state size and key size but share the same design with the original cipher.
-
For the first time in the literature, we observe that the non-linear layer of the round function of Subterranean 2.0 can be represented by a SIMON-like function. SIMON [2] is a family of lightweight block ciphers and has been extensively analysed since its publication, such as differential/linear analyses in [12]. Inspired by the existing work on SIMON, we propose explicit formulas for computing the exact correlation of linear trails of Subterranean 2.0 and other ciphers utilizing AND operations. We then build our models for handling the dependency issue, as well as searching optimal differential/linear trails of Subterranean 2.0.
-
For most values of d, Subterranean-m resists the linear attack and the state collision attack. However, there exist two instances of Subterranean-m(d) which do not resist the linear attack and the state collision attack respectively. This means different values of d are not equally good.
-
There does exist linear bias over four or three output blocks for Subterranean 2.0 and Subterranean-m. Our work helps to find a flaw in the designers’ reasoning of Subterranean 2.0’s linear biases.
-
Our experiments support the designers’ claim that there is no bias measurable from \(2^{96}\) data blocks or less.
1.2 Organization
2 Notations and specification of Subterranean 2.0
2.1 Notations
2.2 Round function
2.3 Duplex object and two keyed functions
2.3.1 Duplex object
i | \(12^{4i}\) | \(-12^{4i}\) | i | \(12^{4i}\) | \(-12^{4i}\) | i | \(12^{4i}\) | \(-12^{4i}\) | i | \(12^{4i}\) | \(-12^{4i}\) |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 256 | 8 | 64 | 193 | 16 | 241 | 16 | 24 | 4 | 253 |
1 | 176 | 81 | 9 | 213 | 44 | 17 | 11 | 246 | 25 | 190 | 67 |
2 | 136 | 121 | 10 | 223 | 34 | 18 | 137 | 120 | 26 | 30 | 227 |
3 | 35 | 222 | 11 | 184 | 73 | 19 | 211 | 46 | 27 | 140 | 117 |
4 | 249 | 8 | 12 | 2 | 255 | 20 | 128 | 129 | 28 | 225 | 32 |
5 | 134 | 123 | 13 | 95 | 162 | 21 | 169 | 88 | 29 | 22 | 235 |
6 | 197 | 60 | 14 | 15 | 242 | 22 | 189 | 68 | 30 | 17 | 240 |
7 | 234 | 23 | 15 | 70 | 187 | 23 | 111 | 146 | 31 | 165 | 92 |
32 | 256 |
2.3.2 Subterranean-deck and Subterranean-SAE
2.4 Toy versions
Version | State size | Key size | d | Extraction rate | Output \(Z_i\) |
---|---|---|---|---|---|
Subterranean 2.0 | 257 | 128 | 12 | 32 | \(s_{12^{4i}} + s_{-12^{4i}}\) |
Subterranean-m(d) | 97 | 48 | \(d\in D\) | 12 | \(s_{d^{4i}} + s_{-d^{4i}}\) |
\(D=\{5, 7, 10, 13, 14, 15, 17, 21, 23, 26, 29, 37, 38, 39, 40, 41, 56, 57, 58, 59, 60, 68, 71, 74, 76, 80,\) \(82, 83, 84, 87, 90, 92\}\) |
3 Properties of Subterranean 2.0 and three attack scenarios
3.1 Attack scenario 1: keystream biases
3.2 Attack scenario 2: state collisions
3.3 Attack scenario 3: state recovery in the nonce-misuse setting
Recall Property 1 that Subterranean 2.0 uses the single-round permutation with algebraic degree 2 in the duplex call. In the setting that a nonce can be used more than once, one may inject a difference \(\varDelta \overline{M}^i\) at \(s^i\) in the message processing phase as shown in Fig. 6, one will obtain some linear relations of the state difference \(\varDelta s^{i+1}\) through the output difference \(\varDelta Z^{i+2}\) as each output bit is the sum of two internal bits. More importantly, \(\varDelta s^{i+1}\) is linear in bits of \(s^i\) due to Fact 1 for quadratic Boolean functions. Therefore, \(\varDelta Z^{i+2}\) will be linear in \(s^i\) as well, and thus some bits of \(s^i\) will be leaked by observing such one-round differentials.In nonce-misuse scenario’s or when unwrapping invalid cryptograms returns more information than a simple error, we make no security claims and an attacker may even be able to reconstruct the secret state. Nevertheless we believe that this would probably a non-trivial effort, both in attack complexity as in ingenuity.
4 Differential and linear analysis tailored for keystream biases and state collisions
4.1 Dependency of AND operations
\(\varDelta x_{0}, \varDelta x_1\) | \(\varDelta y=0\) | \(\varDelta y=1\) | \(\varGamma x_{0}, \varGamma x_1\) | \(\varGamma y=0\) | \(\varGamma y=1\) |
---|---|---|---|---|---|
0, 0 | 4 | 0 | 0, 0 | 2 | 1 |
0, 1 | 2 | 2 | 0, 1 | 0 | 1 |
1, 0 | 2 | 2 | 1, 0 | 0 | 1 |
1, 1 | 2 | 2 | 1, 1 | 0 | −1 |
4.2 Represent \(\chi \) as a SIMON-like function
4.3 Linear analysis
-
For Subterranean-m(d)
-
For Subterranean 2.0
-
There does not exist any linear trail over four blocks with correlation higher or equal to \(2^{-49}\).
-
4.4 Differential analysis
-
For Subterranean-m(d)
-
For Subterranean 2.0
-
There does not exist any differential trail over four blocks with probability higher or equal to \(2^{-108}\).
-
Version | (|s|, |K|) | \(|Z^i|\) | #\(Z^i\) | \(\min -\log _2(Cor)\) |
---|---|---|---|---|
Subterranean-SAE | (257, 128) | 32 | \(\le 4\) | (49, 90] |
Subterranean-m | (97, 48) | 12 | \(\le 5\) | \(\varvec{23}\sim 34\) |
Version | (|s|, |K|) |
\(|\varDelta \overline{M}^i| \)
| #\(\varDelta \overline{M}^i\) |
\(\min -\log _2(p)\)
|
---|---|---|---|---|
Subterranean-SAE | (257,128) | 32+1 |
\(\le 4\)
| (108, 180] |
Subterranean-m | (97,48) | 12+1 |
\(\le 6\)
|
\(\varvec{47}\sim 64\)
|
4.5 Impact on Subterranean-deck and Subterranean-SAE
4.5.1 Bias of keystreams
Our linear analysis is twofold: we find that the first half of the statement is not a reasonable conjecture and we support the second half of the statement with detailed experiments. Our results show that there exist linear trails over three or four blocks for both Subterranean 2.0 and Subterranean-m. Within four keystream blocks, linear trails with correlation higher than \(2^{-48}\) do not exist for Subterranean 2.0. The experiments on the toy cipher Subterranean-m show that there are no better linear trails when we increase the number of keystream blocks to five, which gives some confidence that there is no better linear trails as well for Subterranean 2.0 over more output blocks. In short, our results support the designers’ claim on the security against linear cryptanalysis.This provides evidence that there is probably no bias for masks Z of less than 5 blocks and we believe there is no bias in Z measurable from output sequences of \(2^{96}\) blocks or less.
4.5.2 State collisions
5 Key recovery of Subterranean-SAE in the nonce-misuse setting
5.1 One-round differential analysis
5.2 Nested one-round differential analysis
5.3 Key recovery
No. | Pos. of \(s^i\) with difference | Recovered bits | #Recovered bits |
---|---|---|---|
1 | 15, 213, 223, 211, 134, 128, 35, 234, 70, 190, 184, 111, 165, 169, 11, 4, 22 | \(s^i_{5}, s^i_{12}, s^i_{16}, s^i_{21}, s^i_{34}, s^i_{69}, s^i_{71}, s^i_{110},s^i_{112}, s^i_{133}, s^i_{129}, \) \(s^i_{135}, s^i_{164}, s^i_{166}, s^i_{168}, s^i_{185}, s^i_{189}, s^i_{191},s^i_{210}, s^i_{212}, \) \(s^i_{214}, s^i_{224}, s^i_{233}, s^i_{235}, s^i_{3} + s^i_{10}, \) and 5 extra bits \(s^i_{241}, s^i_{223}, s^i_{128}, s^i_{68}, s^i_{22}\) | 30 bits of \(s^i\) |
2 | 137, 140, 30, 225, 197, 189, 95, 2, 256, 249 | \(s^i_{1}, s^i_{3}, s^i_{29}, s^i_{94}, s^i_{96}, s^i_{136}, s^i_{139}, s^i_{190}, s^i_{198 }, s^i_{196}, s^i_{226},\) \(s^i_{250}, s^i_{255}, s^{i+1}_{169} + s^{i+1}_{172}\) and 4 extra bits \(s^i_{256}, s^i_{121},\) \(s^i_{67}, s^i_2\) | 17 bits of \(s^i\), 1 bit of \(s^{i+1}\) |
3 | 136, 176, 1 | \(s^i_{177}, s^i_{2}, s^i_{137}, s^i_{0}, s^i_{175},s^{i+1}_{234}, s^{i+1}_{181}, s^{i+1}_{215}, s^{i+1}_{213}, s^{i+1}_{160},\) \(s^{i+1}_{162}, s^{i+1}_{13} + s^{i+1}_{249}\) and 3 extra bits \(s^{i+1}_{23},s^{i+1}_{44}, \) \( s^{i+1}_{95}\) | 5 bits of \(s^i\), 10 bits of \(s^{i+1}\) |
4 | 137, 64 | \(s^i_{63}, s^i_{138}, s^{i+1}_{246}, s^{i+1}_{92}, s^{i+1}_{76}, s^{i+1}_{248}, s^{i+1}_{154}, s^{i+1}_{74}, s^{i+1}_{55},\) \(s^{i+1}_{156}\) and 2 extra bits \(s^{i+1}_{11}, s^{i+1}_{165}\) | 2 bits of \(s^i\), 10 bits of \(s^{i+1}\) |
5 | 4,22 | \(s^i_{23}, s^{i+1}_{172}, s^{i+1}_{170}, s^{i+1}_{24}, s^{i+1}_{149}, s^{i+1}_{87}, s^{i+1}_{217}, s^{i+1}_{85},\) and 1 extra bit \(s^i_{234}\) | 2 bits of \(s^i\), 7 bits of \(s^{i+1}\) |
6 | 11, 140, 241 | \(s^i_{242}, s^i_{240}, s^{i+1}_{171}, s^{i+1}_{192}, s^{i+1}_{107}, s^{i+1}_{194}, s^{i+1}_{254}, s^{i+1}_{182}\) and 2 extra bits \(s^i_{15}, s^i_{17}\) | 4 bits of \(s^i\), 6 bits of \(s^{i+1}\) |
7 | 17,70,35,165 | \(s^i_{36}, s^{i+1}_{66}, s^{i+1}_{109}, s^{i+1}_{238}, s^{i+1}_{79}, s^{i+1}_{141}, s^{i+1}_{143}, s^{i+1}_{47} + s^{i+1}_{221},\) \( s^{i+1}_{49} + s^{i+1}_{219}\) | 1 bit of \(s^i\), 8 bits of \(s^{i+1}\) |
8 | 211, 95, 169 | \(s^i_{170}, s^{i+1}_{201}, s^{i+1}_{116}, s^{i+1}_{40}, s^{i+1}_{229}, s^{i+1}_{163}, s^{i+1}_{114}, s^{i+1}_{104}, s^{i+1}_{123}\) and 1 extra bit \(s^{i+1}_{134}\) | 1 bit of \(s^i\), 9 bits of \(s^{i+1}\) |
9 | 256,189, 223 | \(s^i_{222}, s^{i+1}_{103}, s^{i+1}_{193}, s^{i+1}_{108}, s^{i+1}_{106}, s^{i+1}_{105}, s^{i+1}_{81}, s^i_0\cdot s^{i+1}_{43} + s^{i+1}_{39} \) and 3 extra bits \(s^i_{35}, s^{i+1}_{64}, s^{i+1}_{176}\) | 2 bits of \(s^i\), 9 bits of \(s^{i+1}\) |
Recovered bits of \(s^1\) | Recovered bits of \(s^2\) | |
---|---|---|
No. \(3\sim 9\) at \(s^0\) | 59 bits: \(s^{1}_{234}, s^{1}_{181}, s^{1}_{215}, s^{1}_{213}, s^{1}_{160}, s^{1}_{162},\) \(s^{1}_{13} + s^{1}_{249},s^{1}_{23}, s^{1}_{44}, s^{1}_{95}, s^{1}_{246},s^{1}_{92}, s^{1}_{76}, s^{1}_{248},\) \(s^{1}_{154}, s^{1}_{74}, s^{1}_{55}, s^{1}_{156},s^{1}_{11}, s^{1}_{165}, s^{1}_{172}, s^{1}_{170}, \) \(s^{1}_{24},s^{1}_{149},s^{1}_{87}, s^{1}_{217}, s^{1}_{85}, s^{1}_{171}, s^{1}_{192}, s^{1}_{107},\) \( s^{1}_{194},s^{1}_{254}, s^{1}_{182}, s^{1}_{66}, s^{1}_{109}, s^{1}_{238}, s^{1}_{79}, s^{1}_{141},\) \(s^{1}_{143},s^{1}_{47} + s^{1}_{221},s^{1}_{49} + s^{1}_{219}, s^{1}_{201}, s^{1}_{116}, s^{1}_{40},\) \( s^{1}_{229}, s^{1}_{163}, s^{1}_{114}, s^{1}_{104}, s^{1}_{123},s^{1}_{134}, s^{1}_{103}, s^{1}_{193},\) \( s^{1}_{108}, s^{1}_{106}, s^{1}_{105}, s^{1}_{81},s^{1}_{64},\) \(s^{1}_{176}, s^i_0\cdot s^{1}_{43} + s^{1}_{39}\) (as \(s^0_0\) can be known) | |
No. \(1\sim 9\) at \(s^1\) | 60 bits: \(s^1_{5}, s^1_{12}, s^1_{16}, s^1_{21}, s^1_{34}, s^1_{69}, s^1_{71}, s^1_{110},\) \(s^1_{112},s^1_{133}, s^1_{129}, s^1_{135}, s^1_{166}, s^1_{168}, s^1_{185}, s^1_{189},\) \(s^1_{191},s^1_{210},s^1_{212},s^1_{214}, s^1_{224}, s^1_{233}, s^1_{235}, s^1_{3} + s^1_{10},s^1_{241},s^1_{223}, s^1_{128}, s^1_{68}, s^1_{22},(s^1_{164}),s^1_{1},s^1_{3},\) \(s^1_{29}, s^1_{94},s^1_{96},s^1_{136}, s^1_{139}, s^1_{190}, s^1_{198}, s^1_{196},\) \( s^1_{226}, s^1_{250}, s^1_{255}, s^1_{256}, s^1_{121},s^1_{67}, s^1_2 s^1_{177}, s^1_{2},\) \( s^1_{137}, s^1_{0}, s^1_{175}, s^1_{63}, s^1_{138} (s^1_{234}),(s^1_{23}),s^1_{242},\) \( s^1_{240}, s^1_{15}, s^1_{17}, s^1_{36}, (s^1_{170}), s^1_{222}, s^1_{35}\) | 60 bits: \(s^{2}_{169} + s^{2}_{172}, s^{2}_{234}, s^{2}_{181}, s^{2}_{215},s^{2}_{213},\) \(s^{2}_{160}, s^{2}_{162}, s^{2}_{13} + s^{2}_{249}, s^{2}_{23}, s^{2}_{44}, s^{2}_{95}, s^{2}_{246},\) \(s^{2}_{92}, s^{2}_{76}, s^{2}_{248}, s^{2}_{154}, s^{2}_{74},s^{2}_{55}, s^{2}_{156},s^{2}_{11}, s^{2}_{165}, \) \(s^{2}_{172}, s^{2}_{170},s^{2}_{24}, s^{2}_{149}, s^{2}_{87}, s^{2}_{217}, s^{2}_{85}, s^{2}_{171}, \) \(s^{2}_{192},s^{2}_{107}, s^{2}_{194}, s^{2}_{254},s^{2}_{182}, s^{2}_{66}, s^{2}_{109}, s^{2}_{238},\) \( s^{2}_{79}, s^{2}_{141},s^{2}_{143},s^{2}_{47} + s^{2}_{221},s^{2}_{116},s^{2}_{201}, s^{2}_{40},\) \(s^{2}_{49} + s^{2}_{219}, s^{2}_{229}, s^{2}_{163},s^{2}_{114}, s^{2}_{104},\) \( s^{2}_{123},s^{2}_{134}\), \(s^{2}_{103}, s^{2}_{193}, s^{2}_{108}, s^{2}_{106}, s^{2}_{105}, s^{2}_{81},s^{2}_{64},s^{2}_{176},\) \( s^1_0\cdot s^{2}_{43} + s^{2}_{39}\) |
No. \(1\sim 3\) at \(s^2\) | 52 bits: \(s^2_{5}, s^2_{12}, s^2_{16}, s^2_{21}, s^2_{34}, s^2_{69}, s^2_{71}, s^2_{110},\) \(s^2_{112}, s^2_{133}, s^2_{129}, s^2_{135}, s^2_{164}, s^2_{166}, s^2_{168}, s^2_{185},\) \( s^2_{189}, s^2_{191},s^2_{210}, s^2_{212}, s^2_{214}, s^2_{224}, s^2_{233}, s^2_{235},\) \( s^2_{3} + s^2_{10}, s^2_{241},s^2_{223},s^2_{128}, s^2_{68}, s^2_{22}, s^2_{1}, s^2_{3}, s^2_{29},\) \( s^2_{94}, s^2_{96}, s^2_{136},s^2_{139}, s^2_{190}, s^2_{198 }, s^2_{196}, s^2_{226},\) \(s^2_{250}, s^2_{255}, s^2_{256}, s^2_{121},s^2_{67}, s^2_2, s^2_{177}, s^2_{2}, s^2_{137},\) \(s^2_{0}, s^2_{175}\) | |
In total | 1 additional bit from No. 9 injection: \(s^1_{31} = s^2_{76}+ s^2_{201} + s^2_{196} + s^1_{94} + s^1_{226}*s^2_{189} + s^1_{226} + 1 + \varDelta Z^2_5 + \varDelta Z^2_{15}\). Thus, 120 bits plus 11 remaining extraction equations | 112 bits plus 16 remaining extraction equations |
Guess 26 bits: \(s^1_{49}, s^1_{47}, s^1_{8}, s^1_{184}, s^1_{60}, s^1_{43}, s^1_{111}, s^1_{19}, s^1_{26}, s^1_{51}, s^1_{53}, s^1_{57}, s^1_{62}, s^1_{83}, s^1_{89}, s^1_{98}, s^1_{100}, s^1_{118},\) \( s^1_{125},s^1_{131}, s^1_{152},s^1_{158},s^1_{179}, s^1_{203}, s^1_{205}, s^1_{207}\), and there remains only 26 quadratic terms in the expressions of \(s^2\). |