Some results on lightweight stream ciphers Fountain v1 &amp; Lizard

Ravi Anand; Dibyendu Roy; Santanu Sarkar

doi:10.3934/amc.2020128

Article Contents

2023, Volume 17, Issue 2: 298-319. Doi: 10.3934/amc.2020128

This issue Previous Article Next Article Codes with few weights arising from linear sets

Some results on lightweight stream ciphers Fountain v1 & Lizard

1.
Indian Institute of Technology Kharagpur, Kharagpur, India
2.
Indian Statistical Institute, Kolkata, India
3.
Indian Institute of Technology Madras, Chennai, India

^* Corresponding author: Dibyendu Roy
^* Corresponding author: Dibyendu Roy

Received: September 2019

Revised: September 2020

Early access: December 2020

Published: April 2023

Abstract Full Text(HTML) Figure(1) / Table(5) Related Papers Cited by

Abstract

In this paper, we propose cryptanalytic results on two lightweight stream ciphers: Fountain v1 and Lizard. The main results of this paper are the followings:

$ - $ We propose a zero-sum distinguisher on reduced round Fountain v1. In this context, we study the non-randomness of the cipher with a careful selection of cube variables. Our obtained cube provides a zero-sum on Fountain v1 till $ 188 $ initialization rounds and significant non-randomness till $ 189 $ rounds. This results in a distinguishing attack on Fountain v1 with $ 189 $ initialization rounds.

$ - $ Further, we find that the same cipher has a weakness against conditional Time-Memory-Data-Tradeoff (TMDTO). We show that TMDTO attack using sampling resistance has online complexity $ 2^{110} $ and offline complexity $ 2^{146} $.

$ - $ Finally, we revisit the Time-Memory-Data-Tradeoff attack on Lizard by Maitra et al. (IEEE Transactions on Computers, 2018) and provide our observations on their work. We show that instead of choosing any random string, some particular strings would provide better results in their proposed attack technique.

Keywords:

Mathematics Subject Classification: 94A60.

Citation:

Full Text(HTML)

Figure 1. Design Specification of Fountain v1.

Download: Full-size image PowerPoint slide

Table 1. S-box for key-IV initialization phase

$ x $	:	$ 0 $	$ 1 $	$ 2 $	$ 3 $	$ 4 $	$ 5 $	$ 6 $	$ 7 $	$ 8 $	$ 9 $	$ A $	$ B $	$ C $	$ D $	$ E $	$ F $
$ S(x) $	:	$ 1 $	$ A $	$ 4 $	$ C $	$ 6 $	$ F $	$ 3 $	$ 9 $	$ 2 $	$ D $	$ B $	$ 7 $	$ 5 $	$ 0 $	$ 8 $	$ E $

| Show Table

DownLoad: CSV

Table 2. Integrated S-box for key-IV initialization phase

$ x $	:	$ 0 $	$ 1 $	$ 2 $	$ 3 $	$ 4 $	$ 5 $	$ 6 $	$ 7 $	$ 8 $	$ 9 $	$ A $	$ B $	$ C $	$ D $	$ E $	$ F $
$ S(x) $	:	$ 9 $	$ 5 $	$ 6 $	$ D $	$ 8 $	$ A $	$ 7 $	$ 2 $	$ E $	$ 4 $	$ C $	$ 1 $	$ F $	$ 0 $	$ B $	$ 3 $

| Show Table

DownLoad: CSV

Table 3. Distinguishing attack on Fountain v1

Cube	Cube variable indices	Probability of superpoly = 0
Size					Rounds
		$ 187 $	$ 188 $	$ 189 $	$ 190 $	$ 191 $	$ 192 $	$ 193 $	$ 194 $	$ 195 $
$ \|I_4\|=31 $	$ I_4 $	$ 1.00 $	$ 1.00 $	$ 0.93 $	$ 0.50 $	$ 0.51 $	$ 0.48 $	$ 0.48 $	$ 0.52 $	$ 0.49 $

| Show Table

DownLoad: CSV

Table 4. TMDTO parameters for Fountain v1

Time	Memory	Data	Pre-processing
$ 110 $	$ 110 $	$ 110 $	$ 146 $

| Show Table

DownLoad: CSV

Table 5. State bits recovery

Keystream bit	Equation	Guessed bits	Feedback	Recovered
			bits	bit
$ z_{34} $	$ s_{45}^{(1)} = z_{24} + s_{37}^{(1)} + s_{54}^{(2)} +s_{39}^{(3)} + s_{42}^{(3)} $	$ s_{1}^{(1)}, s_{1}^{(2)} $, $ s_{1}^{(3)} $		$ s_{45}^{(1)} $
	$ + s_{42}^{(4)}+s_{63}^{(4)}+s_{36}^{(4)}s_{31}^{(1)}+s_{28}^{(2)}s_{29}^{(3)} $	$ s_{1}^{(4)}, s_{0}^{(4)} $
	$ + s_{37}^{(4)} s_{61}^{(3)} + s_{36}^{(4)} s_{57}^{(4)} s_{64}^{(4)} $	$ s_{61}^{(3)}, s_{64}^{(4)} $	$ s_{64}^{(4)} $
$ z_{35} $	$ s_{46}^{(1)} = z_{25} + s_{38}^{(1)} + s_{55}^{(2)} +s_{40}^{(3)} + s_{43}^{(3)} $	$ s_{2}^{(1)}, s_{2}^{(2)} $, $ s_{2}^{(3)} $		$ s_{46}^{(1)} $
	$ + s_{43}^{(4)}+s_{64}^{(4)}+s_{37}^{(4)}s_{32}^{(1)}+s_{28}^{(2)}s_{29}^{(3)} $
	$ + s_{38}^{(4)} s_{62}^{(3)} + s_{37}^{(4)} s_{58}^{(4)} s_{65}^{(4)} $	$ s_{62}^{(3)}, s_{65}^{(4)} $	$ s_{65}^{(4)} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Lightweight Cryptography Standardization, Available from: https://csrc.nist.gov/projects/lightweight-cryptography.
[2]	F. Armknecht and V. Mikhalev, On lightweight stream ciphers with shorter internal states, International Workshop on Fast Software Encryption (FSE), LNCS, Springer, 9054 (2015), 451–470. doi: 10.1007/978-3-662-48116-5_22.
[3]	J.-P. Aumasson, I. Dinur, W. Meier and A. Shamir, Cube testers and key recovery attacks on reduced-round MD6 and Trivium, International Workshop on Fast Software Encryption (FSE), LNCS, Springer, 5665 (2009), 1–22. doi: 10.1007/978-3-642-03317-9_1.
[4]	S. H. Babbage, Improved "exhaustive search" attacks on stream ciphers, European Convention on Security and Detection, IET, (1995), 161–166. doi: 10.1049/cp:19950490.
[5]	S. Banik, Some results on Sprout, International Conference on Cryptology in India (Indocrypt), LNCS, Springer, 9462 (2015), 124–139. doi: 10.1007/978-3-319-26617-6_7.
[6]	S. Banik, T. Isobe, T. Cui and J. Guo, Some cryptanalytic results on Lizard, IACR Transactions on Symmetric Cryptology, 2017 (2017), 82-98.
[7]	A. Biryukov and A. Shamir, Cryptanalytic time/memory/data tradeoffs for stream ciphers, International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt), LNCS, Springer, 1976 (2000), 1–13. doi: 10.1007/3-540-44448-3_1.
[8]	A. Biryukov, A. Shamir and D. Wagner, Real time cryptanalysis of A5/1 on a PC, International Workshop on Fast Software Encryption (FSE), LNCS, Springer, 1978 (2000), 37–44. doi: 10.1007/3-540-44706-7_1.
[9]	S. Dey, T. Roy and S. Sarkar, Some results on Fruit, Designs, Codes and Cryptography, Springer, 87 (2019), 349–364. doi: 10.1007/s10623-018-0533-y.
[10]	I. Dinur and A. Shamir, Cube attacks on tweakable black box polynomials, Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), LNCS, Springer, 5479 (2009), 278–299. doi: 10.1007/978-3-642-01001-9_16.
[11]	M. F. Esgin and O. Kara, Practical cryptanalysis of full Sprout with TMD tradeoff attacks, International Conference on Selected Areas in Cryptography (SAC), LNCS, Springer, 9566 (2015), 67–85. doi: 10.1007/978-3-319-31301-6_4.
[12]	V. A. Ghafari and H. Hu, A new chosen IV statistical distinguishing framework to attack symmetric ciphers, and its application to ACORN-v3 and Grain-128a, Journal of Ambient Intelligence and Humanized Computing, Springer, 10 (2019), 2393-2400.
[13]	V. A. Ghafari, H. Hu and Y. Chen, Fruit-80: A secure ultra-lightweight stream cipher for constrained environments, Entropy, Multidisciplinary Digital Publishing Institute, 20 (2018), 180.
[14]	V. A. Ghafari, H. Hu and M. Alizadeh, Necessary conditions for designing secure stream ciphers with the minimal internal states, IACR Cryptol. ePrint Arch., (2017), 765.
[15]	J. Golić, Cryptanalysis of alleged A5 stream cipher, International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), LNCS, Springer, 1233 (1997), 239–255.
[16]	C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 2012.
[17]	M. Hamann, M. Krause, W. Meier and B. Zhang, Design and analysis of small-state Grain-like stream ciphers, Cryptography and Communications, Springer, 10 (2018), 803–834. doi: 10.1007/s12095-017-0261-6.
[18]	M. Hamann, M. Krause and W. Meier, LIZARD - A lightweight stream cipher for power-constrained devices, IACR Transactions on Symmetric Cryptology, 2017 (2017), 45-79.
[19]	M. Hell, T. Johansson and W. Meier, Grain: A stream cipher for constrained environments, International Journal of Wireless and Mobile Computing, 2 (2007), 86-93. doi: 10.1504/IJWMC.2007.013798.
[20]	M. E. Hellman, A cryptanalytic time-memory trade-off, IEEE Transactions on Information Theory, 26 (1980), 401-406. doi: 10.1109/TIT.1980.1056220.
[21]	V. Lallemand and M. N. Plasencia, Cryptanalysis of full Sprout, Annual Cryptology Conference (Crypto), LNCS, Springer, 9215 (2015), 663–682. doi: 10.1007/978-3-662-47989-6_32.
[22]	S. Maitra, N. Sinha, A. Siddhanti, R. Anand and S. Gangopadhyay, A TMDTO attack against Lizard, IEEE Transactions on Computers, 67 (2017), 733-739. doi: 10.1109/TC.2017.2773062.
[23]	S. Maitra, S. Sarkar, A. Baksi and P. Dey, Key recovery from state information of Sprout: Application to cryptanalysis and fault attack, IPSI Transactions on Advanced Research, 12 (2016).
[24]	S. Maitra, A. Siddhanti and S. Sarkar, A differential fault attack on Plantlet, IEEE Transactions on Computers, 66 (2017), 1804-1808. doi: 10.1109/TC.2017.2700469.
[25]	M. J. Mihaljević, S. Gangopadhyay, G. Paul and H. Imai, Internal state recovery of Grain-v1 employing normality order of the filter function, IET Information Security, 6 (2012), 55-64.
[26]	M. J. Mihaljević, S. Gangopadhyay, G. Paul and H. Imai, Generic cryptographic weakness of $k$-normal Boolean functions in certain stream ciphers and cryptanalysis of Grain-128, Periodica Mathematica Hungarica, 65 (2012), 205-227. doi: 10.1007/s10998-012-4631-8.
[27]	V. Mikhalev, F. Armknecht and C. Müller, On ciphers that continuously access the non-volatile key, IACR Transactions on Symmetric Cryptology, 2016 (2016), 52-79. doi: 10.46586/tosc.v2016.i2.52-79.
[28]	R. Posteuca, Related-key differential slide attack against Fountain V1, Proceedings of the Romanian Academy, Series A, 21 (2020), 61–68.
[29]	S. Sarkar, S. Maitra and A. Baksi, Observing biases in the state: Case studies with Trivium and Trivia-sc, Designs, Codes and Cryptography, 82 (2017), 351-375. doi: 10.1007/s10623-016-0211-x.
[30]	Q. Wang, Y. Hao, Y. Todo, C. Li, T. Isobe and W. Meier, Improved division property based cube attacks exploiting algebraic properties of superpoly, International Cryptology Conference (Crypto), LNCS, Springer, 10991 (2018), 275–305. doi: 10.1007/978-3-319-96884-1_10.
[31]	D. Williams, Probability with Martingales, Cambridge Mathematical Textbooks, 1st Edition, Cambridge University Press, 1991. doi: 10.1017/CBO9780511813658.
[32]	B. Zhang, Fountain: A lightweight authenticated cipher (v1), NIST Lightweight Cryptography Competition, (2019), 1, https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/fountain-spec.pdf.
[33]	B. Zhang and X. Gong, Another tradeoff attack on Sprout-like stream ciphers, International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt), LNCS, Springer, 9453 (2015), 561–585. doi: 10.1007/978-3-662-48800-3_23.
[34]	B. Zhang, X. Gong and W. Meier, Fast correlation attacks on Grain-like small state stream ciphers, IACR Transactions on Symmetric Cryptology, 2017 (2017), 58-81.