A vulnerability in implementations of SHA-3, SHAKE, EdDSA, and other NIST-approved algorithms. (English) Zbl 07745599

Rosulek, Mike (ed.), Topics in cryptology – CT-RSA 2023. Cryptographers’ track at the RSA conference 2023, San Francisco, CA, USA, April 24–27, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13871, 3-28 (2023).
Summary: This paper describes a vulnerability in several implementations of the Secure Hash Algorithm 3 (SHA-3) that have been released by its designers. The vulnerability has been present since the final-round update of Keccak was submitted to the National Institute of Standards and Technology (NIST) SHA-3 hash function competition in January 2011 and is present in the eXtended Keccak Code Package (XKCP) of the Keccak team. It affects all software projects that have integrated this code, such as the scripting languages Python and PHP Hypertext Preprocessor (PHP). The vulnerability is a buffer overflow that allows attacker-controlled values to be eXclusive-ORed (XORed) into memory (without any restrictions on values to be XORed and even far beyond the location of the original buffer), thereby making many standard protection measures against buffer overflows (e.g., canary values) completely ineffective. First, we provide Python and PHP scripts that cause segmentation faults when vulnerable versions of the interpreters are used. Then, we show how this vulnerability can be used to construct second preimages and preimages for the implementation, and we provide a specially constructed file that, when hashed, allows the attacker to execute arbitrary code on the victim’s device. The vulnerability applies to all hash value sizes, and all 64-bit Windows, Linux, and macOS operating systems, and may also impact cryptographic algorithms that require SHA-3 or its variants, such as the Edwards-curve Digital Signature Algorithm (EdDSA) when the Edwards448 curve is used. We introduce the Init-Update-Final Test (IUFT) to detect this vulnerability in implementations.
For the entire collection see [Zbl 1521.94005].


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


[1] Benmocha, G.; Biham, E.; Perle, S.; Dunkelman, O.; Jacobson Jr., MJ; O’Flynn, C., Unintended features of APIs: cryptanalysis of incremental HMAC, Selected Areas in Cryptography, 301-325 (2021), Cham: Springer, Cham · Zbl 1485.94055 · doi:10.1007/978-3-030-81652-0_12
[2] Bertoni, G., Daemen, J., Hoffert, S., Peeters, M., Assche, G.V., Keer, R.V.: eXtended Keccak code package (2022). https://github.com/XKCP/XKCP
[3] Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: KeccakTools (2018). https://github.com/KeccakTeam/KeccakTools
[4] Forsythe, J., Held, D.: NIST SHA-3 competition security audit results. Fortify Software Blog (2009). http://web.archive.org/web/20120222155656if_/blog.fortify.com/repo/Fortify-SHA-3-Report.pdf
[5] Josefsson, S., Liusvaara, I.: Edwards-curve digital signature algorithm (EdDSA). RFC 8032 (2017). http://www.ietf.org/rfc/rfc8032.txt
[6] Kelsey, J., Chang, S., Perlner, R.: SHA-3 derived functions: cSHAKE, KMAC, TupleHash, and ParallelHash. NIST SP 800-185 (2016). doi:10.6028/NIST.SP.800-185
[7] Menezes, A.; van Oorschot, PC; Vanstone, SA, Handbook of Applied Cryptography (1996), BOca Raton: CRC Press, BOca Raton · Zbl 0868.94001 · doi:10.1201/9781439821916
[8] Mouha, N.: Automated techniques for hash function and block cipher cryptanalysis. Ph.D. thesis, Katholieke Universiteit Leuven (2012)
[9] Mouha, N.; Celi, C.; Jarecki, S., Extending NIST’s CAVP testing of cryptographic hash function implementations, Topics in Cryptology - CT-RSA 2020, 129-145 (2020), Cham: Springer, Cham · doi:10.1007/978-3-030-40186-3_7
[10] Mouha, N.; Raunak, MS; Kuhn, DR; Kacker, R., Finding bugs in cryptographic hash function implementations, IEEE Trans. Reliab., 67, 3, 870-884 (2018) · doi:10.1109/TR.2018.2847247
[11] National Institute of Standards and Technology: Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family. 72 Fed. Reg. (2007). https://www.federalregister.gov/d/E7-21581
[12] National Institute of Standards and Technology: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. NIST Federal Information Processing Standards Publication 202 (2015). doi:10.6028/NIST.FIPS.202
[13] National Institute of Standards and Technology: Hash Functions: SHA-3 Project (2020). https://csrc.nist.gov/projects/hash-functions/sha-3-project
[14] National Institute of Standards and Technology: Digital Signature Standard (DSS). NIST Federal Information Processing Standards Publication 186-5 (2023). doi:10.6028/NIST.FIPS.186-5
[15] Polubelova, M., et al.: HACLxN: verified generic SIMD crypto (for all your favourite platforms). In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) CCS 2020: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, 9-13 November 2020, pp. 899-918. ACM (2020). doi:10.1145/3372297.3423352
[16] Preneel, B.: Analysis and design of cryptographic hash functions. Ph.D. thesis, Katholieke Universiteit Leuven (1993)
[17] Protzenko, J., Ho, S.: Functional pearl: zero-cost, meta-programmed, dependently-typed stateful functors in \(F^*\). CoRR abs/2102.01644 (2021)
[18] Python Tracker: Issue 37630: Investigate replacing SHA3 code with OpenSSL (2019). https://bugs.python.org/issue37630
[19] Python Tracker: Issue 47098: sha3: Replace Keccak Code Package with tiny_sha3 (2022). https://bugs.python.org/issue47098
[20] 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 · doi:10.1007/11535218_2
[21] Wang, X.; Yu, H.; Cramer, R., How to break MD5 and other hash functions, Advances in Cryptology - EUROCRYPT 2005, 19-35 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94359 · doi:10.1007/11426639_2
[22] Zinzindohoué, J.K., Bhargavan, K., Protzenko, J., Beurdouche, B.: \(HACL^*\): a verified modern cryptographic library. In: Thuraisingham, B., Evans, D., Malkin, T., Xu, D. (eds.) Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, 30 October-03 November 2017, pp. 1789-1806. ACM (2017). doi:10.1145/3133956.3134043
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.