Abstract
In the last few years, several practitioners have proposed a wide range of approaches for reducing the implementation area of the AES in hardware. However, an area-throughput trade-off that undermines high-speed is not realistic for real-time cryptographic applications. In this manuscript, we explore how Genetic Algorithms (GAs) can be used for pipelining the AES substitution box based on composite field arithmetic. We implemented a framework that parses and analyzes a Verilog netlist, abstracts it as a graph of interconnected cells and generates circuit statistics on its elements and paths. With this information, the GA extracts the appropriate arrangement of Flip-Flops (FFs) that maximizes the throughput of the given netlist. In doing so, we show that it is possible to achieve a 50 % improvement in throughput with only an 18 % increase in area in the UMC 0.13 \(\mu \)m low-leakage standard cell library.
This work was supported in part by the Technology Foundation STW (project 12624 - SIDES), The Netherlands Organization for Scientific Research NWO (project ProFIL 628.001.007) and the ICT COST action IC1204 TRUDEVICE.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Fischer, V., Drutarovský, M.: Two Methods of Rijndael Implementation in Reconfigurable Hardware. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 77–92. Springer, Heidelberg (2001)
Satoh, A., Morioka, S., Takano, K., Munetoh, S.: A compact rijndael hardware architecture with s-box optimization. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 239–254. Springer, Heidelberg (2001)
Mentens, N., Batina, L., Preneel, B., Verbauwhede, I.: A systematic evaluation of compact hardware implementations for the Rijndael S-BOX. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 323–333. Springer, Heidelberg (2005)
Canright, D.: A very compact s-box for AES. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 441–455. Springer, Heidelberg (2005)
Fischer, V., Drutarovský, M., Chodowiec, P., Gramain, F.: InvMixColumn decomposition and multilevel resource sharing in AES implementations. IEEE Trans. VLSI Syst. 13(8), 989–992 (2005)
Chodowiec, P., Gaj, K.: Very Compact FPGA Implementation of the AES Algorithm. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 319–333. Springer, Heidelberg (2003)
Wolkerstorfer, J., Oswald, E., Lamberger, M.: An ASIC implementation of the AES sboxes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 67–78. Springer, Heidelberg (2002)
Moradi, A., Poschmann, A., Ling, S., Paar, C., Wang, H.: Pushing the Limits: A Very Compact and a Threshold Implementation of AES. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 69–88. Springer, Heidelberg (2011)
Hodjat, A., Verbauwhede, I.: Area-throughput trade-offs for fully pipelined 30 to 70 gbits/s AES processors. IEEE Trans. Computers 55(4), 366–372 (2006)
Kumar, S., Sharma, V., Mahapatra, K.: Low latency VLSI architecture of S-box for AES encryption. In: 2013 International Conference on Circuits, Power and Computing Technologies (ICCPCT), pp. 694–698 (March 2013)
Jhajharia, S., Mishra, S., Bali, S.: Public key cryptography using neural networks and genetic algorithms. In: Parashar, M., Zomaya, A.Y., Chen, J., Cao, J., Bouvry, P., Prasad, S.K. (eds.) IC3, pp. 137–142. IEEE (2013)
Sokouti, M., Sokouti, B., Pashazadeh, S., Feizi-Derakhshi, M.R., Haghipour, S.: Genetic-based random key generator (GRKG): a new method for generating more-random keys for one-time pad cryptosystem. Neural Computing and Applications 22(7–8), 1667–1675 (2013)
Zarza, L., Pegueroles, J., Soriano, M., Martínez, R.: Design of cryptographic protocols by means of genetic algorithms techniques. In: Malek, M., Fernández-Medina, E., Hernando, J. (eds.) SECRYPT, pp. 316–319. INSTICC Press (2006)
Park, K., Hong, C.: Cryptographic protocol design concept with genetic algorithms. In: Khosla, R., Howlett, R.J., Jain, L.C. (eds.) KES 2005. LNCS (LNAI), vol. 3682, pp. 483–489. Springer, Heidelberg (2005)
Carpi, R.B., Picek, S., Batina, L., Menarini, F., Jakobovic, D., Golub, M.: Glitch it if you can: parameter search strategies for successful fault injection. In: Francillon, A., Rohatgi, P. (eds.) CARDIS 2013. LNCS, vol. 8419, pp. 236–252. Springer, Heidelberg (2014)
Clark, J.A., Jacob, J.L., Stepney, S.: The design of S-boxes by simulated annealing. New Generation Computing 23(3), 219–231 (2005)
Picek, S., Ege, B., Batina, L., Jakobovic, D., Chmielewski, L., Golub, M.: On Using Genetic Algorithms for Intrinsic Side-channel Resistance: The Case of AES S-box. Proceedings of the First Workshop on Cryptography and Security in Computing Systems, CS2 2014, pp. 13–18. ACM, New York (2014)
Picek, S., Ege, B., Papagiannopoulos, K., Batina, L., Jakobovic, D.: Optimality and beyond: The case of 4x4 s-boxes. In: 2014 IEEE International Symposium on Hardware-Oriented Security and Trust, HOST 2014, Arlington, VA, USA, May 6-7, pp. 80–83 (2014)
Faraday: Faraday Cell Library 0.13 \(\mu \)m Standard Cell (2004)
Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. The MIT Press, Cambridge (1992)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948 (November 1995)
Yao, X.: Optimization by genetic annealing. In: Proc. of 2nd Australian Conf. on Neural Networks, pp. 94–97 (1991)
Wolpert, D.H., Macready, W.G.: No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1(1), 67–82 (1997)
Syswerda, G.: Uniform crossover in genetic algorithms. In: Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2–9. Morgan Kaufmann Publishers Inc., San Francisco (1989)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer, Heidelberg (2003)
Knuth, D.E.: The Art of Computer Programming. Fundamental Algorithms, 3rd edn., vol. 1. Addison Wesley Longman Publishing Co. Inc., Redwood City (1997)
Weise, T.: Global Optimization Algorithms Theory and Application (2009)
Michalewicz, Z.: Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, London (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Batina, L., Jakobovic, D., Mentens, N., Picek, S., de la Piedra, A., Sisejkovic, D. (2014). S-box Pipelining Using Genetic Algorithms for High-Throughput AES Implementations: How Fast Can We Go?. In: Meier, W., Mukhopadhyay, D. (eds) Progress in Cryptology -- INDOCRYPT 2014. INDOCRYPT 2014. Lecture Notes in Computer Science(), vol 8885. Springer, Cham. https://doi.org/10.1007/978-3-319-13039-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-13039-2_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13038-5
Online ISBN: 978-3-319-13039-2
eBook Packages: Computer ScienceComputer Science (R0)