
-
Previous Article
On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators
- AMC Home
- This Issue
- Next Article
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 |
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.
References:
[1] |
Lightweight Cryptography Standardization, Available from: https://csrc.nist.gov/projects/lightweight-cryptography. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[16] |
C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 2012. Google Scholar |
[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. Google Scholar |
[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). Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
show all references
References:
[1] |
Lightweight Cryptography Standardization, Available from: https://csrc.nist.gov/projects/lightweight-cryptography. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[16] |
C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 2012. Google Scholar |
[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. Google Scholar |
[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). Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |

: | |||||||||||||||||
: |
: | |||||||||||||||||
: |
: | |||||||||||||||||
: |
: | |||||||||||||||||
: |
Cube | Cube variable indices | Probability of superpoly = 0 | ||||||||
Size | Rounds | |||||||||
Cube | Cube variable indices | Probability of superpoly = 0 | ||||||||
Size | Rounds | |||||||||
Time | Memory | Data | Pre-processing |
Time | Memory | Data | Pre-processing |
Keystream bit | Equation | Guessed bits | Feedback | Recovered |
bits | bit | |||
Keystream bit | Equation | Guessed bits | Feedback | Recovered |
bits | bit | |||
[1] |
Zhongbao Zhou, Yanfei Bai, Helu Xiao, Xu Chen. A non-zero-sum reinsurance-investment game with delay and asymmetric information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 909-936. doi: 10.3934/jimo.2020004 |
[2] |
Tinghua Hu, Yang Yang, Zhengchun Zhou. Golay complementary sets with large zero odd-periodic correlation zones. Advances in Mathematics of Communications, 2021, 15 (1) : 23-33. doi: 10.3934/amc.2020040 |
[3] |
Qingfeng Zhu, Yufeng Shi. Nonzero-sum differential game of backward doubly stochastic systems with delay and applications. Mathematical Control & Related Fields, 2021, 11 (1) : 73-94. doi: 10.3934/mcrf.2020028 |
[4] |
Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145 |
[5] |
Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108 |
[6] |
Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216 |
[7] |
Yutong Chen, Jiabao Su. Nontrivial solutions for the fractional Laplacian problems without asymptotic limits near both infinity and zero. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021007 |
[8] |
Jérôme Lohéac, Chaouki N. E. Boultifat, Philippe Chevrel, Mohamed Yagoubi. Exact noise cancellation for 1d-acoustic propagation systems. Mathematical Control & Related Fields, 2020 doi: 10.3934/mcrf.2020055 |
[9] |
Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054 |
[10] |
Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327 |
[11] |
Chandra Shekhar, Amit Kumar, Shreekant Varshney, Sherif Ibrahim Ammar. $ \bf{M/G/1} $ fault-tolerant machining system with imperfection. Journal of Industrial & Management Optimization, 2021, 17 (1) : 1-28. doi: 10.3934/jimo.2019096 |
[12] |
Ludovick Gagnon, José M. Urquiza. Uniform boundary observability with Legendre-Galerkin formulations of the 1-D wave equation. Evolution Equations & Control Theory, 2021, 10 (1) : 129-153. doi: 10.3934/eect.2020054 |
[13] |
El Haj Laamri, Michel Pierre. Stationary reaction-diffusion systems in $ L^1 $ revisited. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 455-464. doi: 10.3934/dcdss.2020355 |
[14] |
Xiaorui Wang, Genqi Xu, Hao Chen. Uniform stabilization of 1-D Schrödinger equation with internal difference-type control. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021022 |
[15] |
Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123 |
[16] |
Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 215-242. doi: 10.3934/cpaa.2020264 |
[17] |
Mokhtari Yacine. Boundary controllability and boundary time-varying feedback stabilization of the 1D wave equation in non-cylindrical domains. Evolution Equations & Control Theory, 2021 doi: 10.3934/eect.2021004 |
2019 Impact Factor: 0.734
Tools
Article outline
Figures and Tables
[Back to Top]