×

Cellular automata based S-boxes. (English) Zbl 1420.94087

Summary: Cellular Automata (CA) represent an interesting approach to design Substitution Boxes (S-boxes) having good cryptographic properties and low implementation costs. From the cryptographic perspective, up to now there have been only ad-hoc studies about specific kinds of CA, the best known example being the \(\chi \) nonlinear transformation used in Keccak. In this paper, we undertake a systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on their nonlinearity and differential uniformity. Next, we extend some previous published results about the construction of CA-based S-boxes by means of a heuristic technique, namely Genetic Programming (GP). In particular, we propose a “reverse engineering” method based on De Bruijn graphs to determine whether a specific S-box is expressible through a single CA rule. Then, we use GP to assess if some CA-based S-box with optimal cryptographic properties can be described by a smaller CA. The results show that GP is able to find much smaller CA rules defining the same reference S-boxes up to the size \(7\times 7\), suggesting that our method could be used to find more efficient representations of CA-based S-boxes for hardware implementations. Finally, we classify up to affine equivalence all \(3\times 3\) and \(4\times 4\) CA-based S-boxes.

MSC:

94A60 Cryptography
68Q80 Cellular automata (computational aspects)
06E30 Boolean functions

Software:

Keccak; PRESENT
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Augot, D., Finiasz, M.: Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, March 3-5, 2014. Revised Selected Papers, pp. 3-17 (2014) · Zbl 1382.94054
[2] Bäck, T., Fogel, D., Michalewicz, Z (eds.): Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol (2000) · Zbl 0973.68197
[3] Bertoni, G.; Daemen, J.; Peeters, M.; Assche, GV, Radiogatún, a belt-and-mill hash function, IACR Cryptology ePrint Archive, 2006, 369, (2006)
[4] Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: The Keccak reference. http://keccak.noekeon.org/ (2011) · Zbl 1306.94028
[5] Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems, CHES ’07, pp. 450-466. Springer, Berlin (2007) · Zbl 1142.94334
[6] Browning, K.A., Dillon, J.F., McQuistan, M.T., Wolfe, A.J.: An APN permutation in dimension six. Finite Fields: theory and applications, pp. 33-42 (2010) · Zbl 1206.94026
[7] Burnett, L., Carter, G., Dawson, E., Millan, W.: Efficient methods for generating MARS-Like S-boxes. In: Proceedings of the 7th International Workshop on Fast Software Encryption, FSE ’00, pp. 300-314. Springer, London (2001). http://dl.acm.org/citation.cfm?id=647935.740914 · Zbl 0994.68628
[8] Canteaut, A., Duval, S., Leurent, G.: Construction of lightweight S-boxes using Feistel and MISTY structures. In: Dunkelman, O., Keliher, L. (eds.) Selected Areas in Cryptography - SAC 2015: 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, pp. 373-393. Springer International Publishing, Cham (2016) · Zbl 1396.94064
[9] Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, 1st edn, pp. 257-397. Cambridge University Press, New York (2010) · Zbl 1209.94035
[10] Carlet, C.: Vectorial Boolean functions for cryptography. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, 1st edn, pp. 398-469. Cambridge University Press, New York (2010) · Zbl 1209.94036
[11] Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis. In: De Santis, A. (ed.) Advances in Cryptology—EUROCRYPT ’94: Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italy, 1994 Proceedings, pp. 356-365. Springer, Berlin (1995) · Zbl 0879.94023
[12] Claesen, L., Daemen, J., Genoe, M., Peeters, G.: Subterranean: a 600 Mbit/sec cryptographic VLSI chip. In: 1993 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993. ICCD ’93. Proceedings, pp. 610-613 (1993)
[13] Clark, JA; Jacob, JL; Stepney, S., The design of S-boxes by simulated annealing, N. Gener. Comput., 23, 219-231, (2005) · Zbl 1103.68047 · doi:10.1007/BF03037656
[14] Daemen, J., Clapp, C.S.K.: Fast hashing and stream encryption with PANAMA. In: Fast Software Encryption, 5th International Workshop, FSE ’98, Paris, France, March 23-25, 1998, Proceedings, pp. 60-74 (1998) · Zbl 1385.94024
[15] Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, New York, Secaucus (2002) · Zbl 1065.94005
[16] Daemen, J.; Govaerts, R.; Vandewalle, J., Invertible shift-invariant transformations on binary arrays, Appl. Math. Comput., 62, 259-277, (1994) · Zbl 0809.68088 · doi:10.1016/0096-3003(94)90087-6
[17] Daemen, J., Govaerts, R., Vandewalle, J.: A new approach to block cipher design. In: Anderson, R. (ed.) Fast Software Encryption: Cambridge Security Workshop Cambridge, U. K.,1993 Proceedings, pp. 18-32. Springer, Berlin (1994) · Zbl 0943.94518
[18] Dobraunig, C., Eichlseder, M., Schläffer, F.M., Ascon, M.: CAESAR submission, http://ascon.iaik.tugraz.at/ (2014)
[19] Gutowitz, H.: Cryptography with dynamical systems. In: Cellular Automata and Cooperative Systems, pp. 237-274. Springer (1993) · Zbl 0854.94008
[20] Kavut, S., Results on rotation-symmetric s-boxes, Inf. Sci., 201, 93-113, (2012) · Zbl 1276.94017 · doi:10.1016/j.ins.2012.02.030
[21] Knudsen, L.R., Robshaw, M.: The Block Cipher Companion. Information Security and Cryptography. Springer, Berlin (2011) · Zbl 1243.68010
[22] Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992) · Zbl 0850.68161
[23] Leander, G., Poschmann, A.: On the classification of 4 bit s-boxes. In: Carlet, C., Sunar, B. (eds.) Arithmetic of Finite Fields, Lecture Notes in Computer Science, vol. 4547, pp. 159-176. Springer, Berlin (2007) · Zbl 1184.94239
[24] Mariot, L., Leporati, A.: A cryptographic and coding-theoretic perspective on the global rules of cellular automata. Nat. Comput. https://doi.org/10.1007/s11047-017-9635-0 (2017) · Zbl 1338.94078
[25] McEliece, R.J.: Theory of Information and Coding, 2nd edn. Cambridge University Press, New York (2001)
[26] Nyberg, K.: On the construction of highly nonlinear permutations. In: Rueppel, R. (ed.) Advances in Cryptology - EUROCRYPT’ 92, Lecture Notes in Computer Science, vol. 658, pp. 92-98. Springer, Berlin (1993) · Zbl 0794.94008
[27] Nyberg, K.: S-boxes and round functions with controllable linearity and differential uniformity. In: Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings, pp. 111-130 (1994)
[28] Picek, S., Miller, J.F., Jakobovic, D., Batina, L.: Cartesian genetic programming approach for generating substitution boxes of different sizes. In: GECCO Companion ’15, pp. 1457-1458. ACM, New York (2015)
[29] Picek, S.; Cupic, M.; Rotim, L., A new cost function for evolution of S-boxes., Evol. Comput., 24, 695-718, (2016) · doi:10.1162/EVCO_a_00191
[30] Picek, S., Mariot, L., Leporati, A., Jakobovic, D.: Evolving S-boxes based on cellular automata with genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, pp. 251-252. ACM, New York (2017)
[31] Picek, S., Mariot, L., Yang, B., Jakobovic, D., Mentens, N.: Design of S-boxes defined with cellular automata rules. In: Proceedings of the Computing Frontiers Conference, CF’17, pp. 409-414. ACM, New York (2017)
[32] Poli, R., Langdon, W.B., McPhee, N.F.: A Field Guide to Genetic Programming. Lulu Enterprises Ltd, UK (2008)
[33] Poli, R., Langdon, W.B., McPhee, N.F.: A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk (With contributions by J. R. Koza) (2008)
[34] Rijmen, V.; Barreto, PSLM; Filho, DLG, Rotation symmetry in algebraically generated cryptographic substitution tables, Inf. Process. Lett., 106, 246-250, (2008) · Zbl 1188.94043 · doi:10.1016/j.ipl.2007.09.012
[35] Seredynski, M., Bouvry, P.: Block encryption using reversible cellular automata. In: Cellular Automata, 6th International Conference on Cellular Automata for Research and Industry, ACRI 2004, Amsterdam, The Netherlands, October 25-28, 2004, Proceedings, pp. 785-792 (2004) · Zbl 1116.68418
[36] Shannon, C., Communication theory of secrecy systems, Bell Syst. Tech. J., 28, 656-715, (1949) · Zbl 1200.94005 · doi:10.1002/j.1538-7305.1949.tb00928.x
[37] Sutner, K., De bruijn graphs and linear cellular automata, Complex Syst., 5, 19-30, (1991) · Zbl 0764.68100
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.