×

Modelling the shrinking generator in terms of linear CA. (English) Zbl 1353.37026

Summary: This work analyses the output sequence from a cryptographic nonlinear generator, the so-called shrinking generator. This sequence, known as the shrunken sequence, can be built by interleaving a unique PN-sequence whose characteristic polynomial serves as basis for the shrunken sequence’s characteristic polynomial. In addition, the shrunken sequence can be also generated from a linear model based on cellular automata. The cellular automata here proposed generate a family of sequences with the same properties, period and characteristic polynomial, as those of the shrunken sequence. Moreover, such sequences appear several times along the cellular automata shifted a fixed number. The use of discrete logarithms allows the computation of such a number. The linearity of these cellular automata can be advantageously employed to launch a cryptanalysis against the shrinking generator and recover its output sequence.

MSC:

37B15 Dynamical aspects of cellular automata
11B85 Automata sequences
12E05 Polynomials in general fields (irreducibility, etc.)

Software:

CAR30
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. D. Cardell, Cryptanalysing the shrinking generator,, Proc. Comp. Sci., 51, 2893 (2015)
[2] S. D. Cardell, Performance of the cryptanalysis over the shrinking generator,, in Int. Joint Conf. CISIS’15 and ICEUTE’15 (eds. A.H. et al.), 111 (2015)
[3] S. D. Cardell, Linear models for the self-shrinking generator based on CA,, J. Cell. Autom., 11, 195 (2016) · Zbl 1432.94126
[4] K. Cattell, One-dimensional linear hybrid cellular automata,, IEEE Trans. Comp.-Aided Des., 15, 325 (1996) · Zbl 1055.68548 · doi:10.1109/12.508317
[5] D. Coppersmith, The shrinking generator,, in Adv. Crypt. - CRYPTO ’93, 23 (1993) · Zbl 0871.94018 · doi:10.1007/3-540-48329-2_3
[6] A. K. Das, Efficient characterisation of cellular automata,, IEEE Proc. Comp. Dig. Techn., 137, 81 (1990)
[7] S. Das, Car30: A new scalable stream cipher with rule 30,, Crypt. Commun., 5, 137 (2013) · Zbl 1335.94045 · doi:10.1007/s12095-012-0079-1
[8] P. F. Duvall, Decimation of periodic sequences,, SIAM J. Appl. Math., 21, 367 (1971) · Zbl 0243.94004
[9] A. Fúster-Sabater, Linear solutions for cryptographic nonlinear sequence generators,, Phys. Lett. A, 369, 432 (2007) · Zbl 1209.94039 · doi:10.1063/1.2827050
[10] A. Fúster-Sabater, A simple linearization of the self-shrinking generator by means of cellular automata,, Neural Netw., 23, 461 (2010) · Zbl 1396.94078
[11] S. W. Golomb, <em>Shift Register-Sequences</em>,, Aegean Park Press (1982)
[12] J. Jose, Inapplicability of fault attacks against trivium on a cellular automata based stream cipher,, in 11th Int. Conf. Cell. Autom. Res. Ind. ACRI 2014, 427 (2014)
[13] A. Kanso, Modified self-shrinking generator,, Comp. Electr. Engin., 36, 993 (2010) · Zbl 1213.94071
[14] R. Lidl, <em>Introduction to Finite Fields and their Applications</em>,, Cambridge Univ. Press (1986) · Zbl 0629.12016
[15] J. L. Massey, Shift-register synthesis and BCH decoding,, IEEE Trans. Inform. Theory, 15, 122 (1969) · Zbl 0167.18101
[16] W. Meier, Analysis of pseudo random sequences generated by cellular automata,, in Adv. Crypt. - EUROCRYPTO ’91, 186 (1991) · Zbl 0791.68121 · doi:10.1007/3-540-46416-6_17
[17] W. Meier, The self-shrinking generator,, in Adv. Crypt. - EUROCRYPT 1994, 205 (1994) · Zbl 0881.94009 · doi:10.1007/BFb0053436
[18] A. J. Menezes, <em>Handbook of Applied Cryptography</em>,, CRC Press (1996) · Zbl 0868.94001
[19] M. Mihaljević, A fast and secure stream cipher based on cellular automata over GF(q),, in Proc. Global Telecomm. Conf. GLOBECOM 1998, 3250 (1998)
[20] C. Paar, <em>Understanding Cryptography</em>,, Springer (2010) · Zbl 1190.94029
[21] S. Wolfram, Cellular automata as simple self-organizing system,, Caltrech preprint, 68 (1982)
[22] S. Wolfram, Cryptography with cellular automata,, in Adv. Crypt. - EUROCRYPT 1985, 429 (1985)
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.