Toward A More Efficient Gröbner-based Algebraic Cryptanalysis

Document Type : Research Article

Authors

Department of Computer Engineering, Amirkabir University of Technology, Tehran, Iran.

Abstract

In this paper, we propose a new method to launch a more efficient algebraic cryptanalysis. Algebraic cryptanalysis aims at finding the secret key of a cipher by solving a collection of polynomial equations that describe the internal structure of the cipher. Chosen correlated plaintexts, as what appears in higher order differential cryptanalysis and its derivatives such as cube attack or integral cryptanalysis, forces many linear relations between intermediate state bits in the cipher. In this paper, we take these polynomial relations into account, so it becomes possible to simplify the equation system arising from algebraic cryptanalysis, and consequently, solve the polynomial system more efficiently.
We take advantage of the Universal Proning technique to provide an efficient method to recover such linear polynomials. Another important parameter in the algebraic cryptanalysis of ciphers is to effectively describe the cipher. We employ the so-called Forward-Backward representation of S-boxes together with Universal Proning to help provide a more powerful algebraic cryptanalysis based on Gröbner-basis computation. We show our method is more efficient than doing algebraic cryptanalysis with MQ representation, and also than employing MQ together with Universal Proning. To show the effectiveness of our approach, we applied it for the cryptanalysis of several lightweight block ciphers. By this approach, we managed to mount algebraic attack on 12-round LBlock, 6-round MIBS, 7-round PRESENT and 9-round SKINNY light-weight block ciphers, so far.

Keywords

Main Subjects

References

[1] J. Faugere and L. Perret. Improving the recognition of faces occluded by facial accessories. In International Conference on Information Security and Cryptology, pages 266--277. Springer, 2009. [ bib | DOI ]
[2] G. V. Bard, N. T. Courtois, J. Nakahara, P. Sepehrdad, and B. Zhang. Improving the recognition of faces occluded by facial accessories. In International Conference on Cryptology in India, pages 176--196. Springer, 2010. [ bib | DOI ]
[3] P. Sušilα, P. Sepehrdad, and S. Vaudenay. On Selection of Samples in Algebraic Attacks and a New Technique to Find Hidden Low Degree Equations. In Information Security and Privacy, pages 50--65. Springer, 2014. [ bib | DOI ]
[4] E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 4(1):3--72, 1991. [ bib | DOI ]
[5] L. Knudsen and D. Wagner. Integral cryptanalysis. In International Workshop on Fast Software Encryption, pages 112--127. Springer, 2002. [ bib | DOI ]
[6] Y. Todo. Structural evaluation by generalized integral property. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 287--314. Springer, 2015. [ bib | DOI ]
[7] M. Izadi, B. Sadeghiyan, S. S. Sadeghian, and H. A. Khanooki. Structural evaluation by generalized integral property. In International Conference on Cryptology and Network Security, pages 334--348. Springer, 2009. [ bib | DOI ]
[8] M. Wang. Structural evaluation by generalized integral property. In International Conference on Cryptology in Africa, pages 40--49. Springer, 2008. [ bib | DOI ]
[9] S. Wu and M. Wang. Integral attacks on reduced-round PRESENT. In International Conference on Information and Communications Security, pages 331--345. Springer, 2013. [ bib | DOI ]
[10] M. R. Z'aba, H. Raddum, M. Henricksen, and E. Dawson. Bit-pattern based integral attack. In International Workshop on Fast Software Encryption, pages 363--381. Springer, 2008. [ bib | DOI ]
[11] B. Collard and F. X. Standaert. A statistical saturation attack against the block cipher PRESENT. In Cryptographers’ Track at the RSA Conference, pages 195--210. Springer, 2009. [ bib | DOI ]
[12] M. Albrecht and C. Cid. Algebraic techniques in differential cryptanalysis. In International Workshop on Fast Software Encryption, pages 193--208. Springer, 2009. [ bib | DOI ]
[13] S. Wu and M. Wang. Automatic search of truncated impossible differentials for word-oriented block ciphers. In International Conference on Cryptology in India, pages 283--302. Springer, 2012. [ bib | DOI ]
[14] A. Bay, J. Nakahara, and S. Vaudenay. Cryptanalysis of reduced-round MIBS block cipher. In International Conference on Cryptology and Network Security, pages 1--19. Springer, 2010. [ bib | DOI ]
[15] Y. Sasaki and L. Wang. Comprehensive study of integral analysis on 22-round LBlock. In International Conference on Information Security and Cryptology, pages 156--169. Springer, 2012. [ bib | DOI ]
[16] N. T. Courtois, P. Sepehrdad, P. Sušil, and S. Vaudenay. ElimLin algorithm revisited. In International Workshop on Fast Software Encryption, pages 306--325. Springer, 2012. [ bib | DOI ]
[17] Z. Eskandari, A. B. Kidmose, S. Kölbl, and T. Tiessen. Finding Integral Distinguishers with Ease. In International Conference on Information Security and Cryptology, pages 115--138. Springer, 2018. [ bib | DOI ]
[18] M. Albrecht and G. Bard. The M4RI Library -- Version 20140914. The M4RI Team, 2014. [ bib | www: ]
[19] M. Brickenstein and A. Dreyer. Polybori: A framework for gröbner-basis computations with boolean polynomials. Journal of Symbolic Computation, 44(9):1326--1345, 2009. [ bib | DOI ]
[20] S. Islam, M. Afzal, and A. Rashdi. On the security of LBlock against the cube attack and side channel cube attack. In International Conference on Availability, Reliability, and Security, pages 105--121. Springer, 2013. [ bib | DOI ]
[21] A. Biryukov and C. D. Cannière. Block Ciphers and Systems of Quadratic Equations. In International Workshop on Fast Software Encryption, pages 274--289. Springer, 2003. [ bib | DOI ]
[22] J. N. Jr, P. Sepehrdad, B. Zhang, and M. Wang. Linear (hull) and algebraic cryptanalysis of the block cipher PRESENT. In International Conference on Cryptology and Network Security, pages 58--75. Springer, 2009. [ bib | DOI ]
[23] N. T. Courtois and J. Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In International Conference on the Theory and Application of Cryptology and Information Security, pages 267--287. Springer, 2002. [ bib | DOI ]
[24] J. L. Massey. SAFER K-64: A byte-oriented block-ciphering algorithm. In International Workshop on Fast Software Encryption, pages 1--17. Springer, 2009. [ bib | DOI ]
[25] J. Faugere and L. Perret. The cipher SHARK. In International Workshop on Fast Software Encryption, pages 99--111. Springer, 1996. [ bib | DOI ]
[26] J. Daemen, L. Knudsen, and V. Rijmen. The block cipher Square. In International Workshop on Fast Software Encryption, pages 149--165. Springer, 2009. [ bib | DOI ]
[27] X. Lai. Higher order derivatives and differential cryptanalysis. In Communications and cryptography, pages 227--233. Springer, 1994. [ bib ]
[28] C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich, and S. M. Sim. The SKINNY family of block ciphers and its low-latency variant MANTIS. In Annual International Cryptology Conference, pages 123--153. Springer, 2016. [ bib | DOI ]
[29] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: An ultra-lightweight block cipher. In International workshop on cryptographic hardware and embedded systems, pages 450--466. Springer, 2007. [ bib | DOI ]
[30] J. Faugere and L. Perret. LBlock: a lightweight block cipher. In International Conference on Applied Cryptography and Network Security, pages 327--344. Springer, 2011. [ bib | DOI ]
[31] P. SUŠIL. Algebraic Cryptanalysis of Deterministic Symmetric Encryption. [ bib | .pdf ]
[32] S. Abdul-Latip, M. R. Reyhanitabar, W. Susilo, and J. Seberry. Extended cubes: enhancing the cube attack by extracting low-degree non-linear equations. In Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, page 296–305. Springer, Berlin, Heidelberg, 2011. [ bib | DOI ]
[33] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of computer and system sciences, 47(3):549--595, 1993. [ bib | DOI ]
[34] I. Dinur and A. Shamir. Annual International Conference on the Theory and Applications of Cryptographic Techniques. In Proceedings of the Seventh IEEE International Conference on Computer Vision, pages 278--299. Springer, 1999. [ bib | DOI ]
[35] H. Arabnezhad-Khanoki, B. Sadeghiyan, and J. Pieprzyk. S-boxes representation and efficiency of algebraic attack. IET Information Security, 13(5):448--458, 2019. [ bib | DOI ]
[36] A. Flórez-Gutiérrez and M. Naya-Plasencia. Improving Key-Recovery in Linear Attacks: Application to 28-Round PRESENT. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 221--249. Springer, 2020. [ bib | DOI ]
[37] S. Sadeghi, T. Mohammadi, and N. Bagheri. Cryptanalysis of reduced round SKINNY block cipher. IACR Transactions on Symmetric Cryptology, 2018(3):124--162, 2018. [ bib | DOI ]

Files

History

  • Receive Date: 24 June 2020
  • Revise Date: 15 July 2020
  • Accept Date: 16 August 2020

Share

How to cite

Statistics