Efficient implementation of SHA-3 hash function on 8-bit AVR-based sensor nodes. (English) Zbl 07497444

Hong, Deukjo (ed.), Information security and cryptology – ICISC 2020. 23rd international conference, Seoul, South Korea, December 2–4, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12593, 140-154 (2021).
Summary: The Keccak algorithm was selected by NIST as the standard SHA-3 hash algorithm for replacing currently used SHA-2 algorithm in 2015. Despite SHA-3’s improved security compared to SHA-2, its low performance in software implementation limits its wide use. In this paper, we propose an optimized SHA-3 implementation on 8-bit AVR microcontrollers (MCU) which are dominantly used for sensor devices in WSNs. Until now, there are only a few researches on optimization of SHA-3 in spite of its security importance. Furthermore, it is very challenging to optimize hash function, especially, SHA-3, on 8-bit AVR MCUs. This is because the internal state of SHA-3 is 1,600-bit which is much larger than internal state of symmetric algorithms (typically, 128-bit) like AES, ARIA, and so on. In other words, it is difficult to accommodate the whole of SHA-3’s internal state on the registers of AVR MCUs, which incurs heavy memory accesses during computation. Thus, we analyzed the structure of SHA-3 algorithm and found that each lane of the internal state can be executed independently for each process in SHA-3. By using this fact, we propose an optimization method which can reduce efficiently the times of memory accesses to the internal state. With this proposed method minimizing the memory accesses, our implementation of SHA3-256 achieves around 25.0% of performance improvement when hashing 500 bytes message compared with the previous best work on 8-bit AVR MCU. To the best of our knowledge, our software is the fastest SHA-3 implementation on AVR platforms until now. In addition, the proposed optimization method can be easily extended to other embedded MCUs such as 16-bit MSP430, 32-bit RISC-V and ARM-based MCUs.
For the entire collection see [Zbl 1482.68025].


68P25 Data encryption (aspects in computer science)
94A60 Cryptography
Full Text: DOI


[1] Park, S-E; Hwang, C-G; Park, D-C, Internet of Things (IoT) on system implementation with minimal Arduino based appliances standby power using a smartphone alarm in the environment, JKIECS, 10, 1175-1182 (2015)
[2] Stevens, M.; Bursztein, E.; Karpman, P.; Albertini, A.; Markov, Y.; Katz, J.; Shacham, H., The first collision for full SHA-1, Advances in Cryptology - CRYPTO 2017, 570-596 (2017), Cham: Springer, Cham · Zbl 1407.94153
[3] Wang, X.; Yin, YL; Yu, H.; Shoup, V., Finding collisions in the full SHA-1, Advances in Cryptology - CRYPTO 2005, 17-36 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.94454
[4] Rijmen, V., Oswald, E.: Update on SHA-1. IACR Cryptology ePrint Archive 2005:10 (2005) · Zbl 1079.94571
[5] De Cannière, C.; Rechberger, C.; Lai, X.; Chen, K., Finding SHA-1 characteristics: general results and applications, Advances in Cryptology - ASIACRYPT 2006, 1-20 (2006), Heidelberg: Springer, Heidelberg · Zbl 1172.94572
[6] Manuel, S., Classification and generation of disturbance vectors for collision attacks against SHA-1, Des. Codes Cryptogr., 59, 1-3, 247-263 (2011) · Zbl 1215.94061
[7] Khovratovich, D.; Rechberger, C.; Savelieva, A.; Canteaut, A., Bicliques for preimages: attacks on Skein-512 and the SHA-2 family, Fast Software Encryption, 244-263 (2012), Heidelberg: Springer, Heidelberg · Zbl 1282.94049
[8] Lamberger, M., Mendel, F.: Higher-order differential attack on reduced SHA-256. IACR Cryptology ePrint Archive 2011:37 (2011) · Zbl 1227.94031
[9] Mendel, F.; Nad, T.; Schläffer, M.; Johansson, T.; Nguyen, PQ, Improving local collisions: new attacks on reduced SHA-256, Advances in Cryptology - EUROCRYPT 2013, 262-278 (2013), Heidelberg: Springer, Heidelberg · Zbl 1306.94075
[10] Dobraunig, C., Eichlseder, M., Mendel, F.: Analysis of SHA-512/224 and SHA-512/256. IACR Cryptology ePrint Archive 2016:374 (2016) · Zbl 1382.94095
[11] Sasaki, Y., Wang, L., Aoki, K.: Preimage attacks on 41-step SHA-256 and 46-step SHA-512. IACR Cryptology ePrint Archive 2009:479 (2009)
[12] Dworkin Morris, J.: SHA-3 standard: permutation-based hash and extendable-output functions (2015). doi:10.6028/NIST.FIPS.202
[13] Lee, H-W; Hong, D.; Kim, H.; Seo, C.; Park, K., An implementation of an SHA-3 hash function validation program and hash algorithm on 16bit-UICC, J. Korea Inst. Inf. Secur. Cryptol., 41, 885-891 (2014)
[14] Kang, M.; Lee, H.; Hong, D.; Seo, C., Implementation of SHA-3 algorithm based on arm-11 processors, J. Korea Inst. Inf. Secur. Cryptol., 25, 749-757 (2015)
[15] Otte et al.: AVR-crypto-lib (2015). https://wiki.das-labor.org/w/-AVR-Crypto-Lib/en
[16] Balasch, J.; Mangard, S., Compact implementation and performance evaluation of hash functions in ATtiny devices, Smart Card Research and Advanced Applications, 158-172 (2013), Heidelberg: Springer, Heidelberg
[17] Keccack Team. Extended Keccack code package (2018). https://keccak.team/index.html
[18] KISA. SHA-3 source code manual (2020). https://seed.kisa.or.kr/kisa/kcmvp/EgovVerification.do
[19] Keccack Team. The extended Keccak code package (open-source implementations of the cryptographic schemes defined by the Keccak team). https://github.com/XKCP/XKCP
[20] Korea internet & security agency open cryptography algorithms. https://seed.kisa.or.kr/kisa/reference/EgovSource.do
[21] Sanadhya, S.K., Sarkar, P.: New collision attacks against up to 24-step SHA-2. IACR Cryptology ePrint Archive 2008:270 (2008) · Zbl 1203.94123
[22] Biryukov, A.; Lamberger, M.; Mendel, F.; Nikolić, I.; Lee, DH; Wang, X., Second-order differential collisions for reduced SHA-256, Advances in Cryptology - ASIACRYPT 2011, 270-287 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94031
[23] Atmel. AVR instruction set manual (2012). http://ww1.microch-ip.com/downloads/en/devicedoc/atmel-0856-avr-instruction-set-manual.pdf
[24] Kwon, H.; Kim, H.; Choi, SJ; Jang, K.; Park, J.; Kim, H.; Seo, H.; You, I., Compact implementation of CHAM block cipher on low-end microcontrollers, Information Security Applications, 127-141 (2020), Cham: Springer, Cham
[25] Kim, YB; Seo, SC; You, I., An efficient implementation of AES on 8-Bit AVR-based sensor nodes, Information Security Applications, 276-290 (2020), Cham: Springer, Cham
[26] Liu, Z.; Seo, H.; Großschädl, J.; Kim, H., Efficient implementation of NIST-compliant elliptic curve cryptography for 8-bit AVR-based sensor nodes, IEEE Trans. Inf. Forensics Secur., 11, 7, 1385-1397 (2016)
[27] Guo, X., Huang, S., Nazhandali, L., Schaumont, P.: Fair and comprehensive performance evaluation of 14 second round SHA-3 ASIC implementations, January 2010
[28] ARM Coporation. ARM architecture reference manual Armv8 (2010). https://www.scss.tcd.ie/ waldroj/3d1/arm_arm.pdf
[29] Cheng, H.; Dinu, D.; Großschädl, J.; Lanet, J-L; Toma, C., Efficient implementation of the SHA-512 hash function for 8-Bit AVR microcontrollers, Innovative Security Solutions for Information Technology and Communications, 273-287 (2019), Cham: Springer, Cham
[30] KISA. KCMVP manual for cryptography (2020). https://seed.k-isa.or.kr/kisa/Board/79/detailView.do
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.