×

Algebraic cryptanalysis of stream ciphers using decomposition of Boolean function. (English) Zbl 1369.94566

Summary: Algebraic attack is an important attack strategy against symmetric ciphers, particularly stream ciphers. The most vital issue of this attack strategy is to reduce the degree of the algebraic equations as much as possible in order to obtain a lower time complexity. This paper first presents one such means of obtaining low degree equations using the decomposition of Boolean functions. This method overcomes the three major drawbacks of fast algebraic attack. We discuss the general attack strategy using decomposable Boolean function. We also demonstrate the decomposition of some Boolean function used in practical stream ciphers. Then we find a bound on the degree of a function to be multiplied with a given function so that the product has low degree decomposition. The second major contribution of this paper is a new probabilistic algebraic attack for LFSR based stream cipher by using decomposition of Boolean function. Finally we apply our method to the stream cipher Grain-v1, which is one of the finalist of estream call for stream cipher proposals, by injecting fault in one bit of NFSR.

MSC:

94A60 Cryptography

Software:

Grain; HiTag2; RAKAPOSHI
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armknecht, F.: Improving fast algebraic attacks. In: Fast Software Encryption, pp. 65-82. Springer, Berlin (2004) · Zbl 1079.68536
[2] Braeken, A., Preneel, B.: Probabilistic algebraic attacks. In: Cryptography and Coding, pp. 290-303. Springer, Berlin (2005) · Zbl 1122.94030
[3] Cid, C., Kiyomoto, S., Kurihara, J.: The RAKAPOSHI stream cipher. In: Information and Communications Security, pp. 32-46 (2009)
[4] Courtois, N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology—CRYPTO 2003, pp. 176-194 (2003) · Zbl 1122.94365
[5] Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology—EUROCRYPT 2003, pp. 345-359 (2003) · Zbl 1038.94525
[6] Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Advances in Cryptology—EUROCRYPT 2000, pp. 392-407. Springer, Heidelberg (2000) · Zbl 1082.94514
[7] Courtois, N., O’Neil, S., Quisquater, J.J.: Practical algebraic attacks on the Hitag2 stream cipher. In: Information Security, pp. 167-176 (2009) · Zbl 1307.94050
[8] Crama, Y., Hammer, P.L.: Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, Cambridge (2010) · Zbl 1196.06001 · doi:10.1017/CBO9780511780448
[9] Cusick, T.W., Stănică, P.: Cryptographic Boolean Functions and Applications. Academic Press, Amsterdam (2009) · Zbl 1173.94002
[10] Dawson, E., Clark, A., Golic, J., Millan, W., Penna, L., Simpson, L.: The LILI-128 keystream generator. In: Proceedings of First NESSIE Workshop. Citeseer, Leuven (2000) · Zbl 1020.94514
[11] Faugre, J.C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139(1), 61-88. http://www-salsa.lip6.fr/ jcf/Papers/F99a (1999)
[12] Faugre, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. ISSAC ’02, pp. 75-83. ACM, New York. http://www-salsa.lip6.fr/ jcf/Papers/F02a (2002)
[13] Hell, M., Johansson, T., Maximov, A., Meier, W.: A stream cipher proposal: Grain-128. In: 2006 IEEE International Symposium on Information Theory, pp. 1614-1618. IEEE, New York (2006)
[14] Hell, M., Johansson, T., Meier, W.: Grain: a stream cipher for constrained environments. Int. J. Wirel. Mob. Comput. 2(1), 86-93 (2007) · doi:10.1504/IJWMC.2007.013798
[15] Karmakar, S., Chowdhury, D.R.: Fault analysis of Grain-128 by targeting NFSR. In: Progress in Cryptology—AFRICACRYPT 2011, pp. 298-315. Springer, Berlin (2011) · Zbl 1280.94074
[16] Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology—EUROCRYPT 2004, pp. 474-491. Springer, Heidelberg (2004) · Zbl 1122.94041
[17] Mihaljević, M.J., Gangopadhyay, S., Paul, G., Imai, H.: Internal state recovery of keystream generator LILI-128 based on a novel weakness of the employed Boolean function. Inf. Process. Lett. 112(21), 805-810 (2012a) · Zbl 1250.94039 · doi:10.1016/j.ipl.2012.07.013
[18] Mihaljević, M.J., Gangopadhyay, S., Paul, G., Imai, H.: Internal state recovery of grain-v1 employing normality order of the filter function. Inf. Secur. IET 6(2), 55-64 (2012b) · doi:10.1049/iet-ifs.2011.0107
[19] Segers, A.: Algebraic attacks from a Gröbner basis perspective. Master’s Thesis (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.