Paper 2026/2624

Provable Security of SHA-256-Based LMS Revisited in the Ideal-Cipher Model

Abstract

The hash-based Leighton-Micali Signature (LMS) has been standardized by IETF, NIST and ISO. State-of-the-art non-quantum security proofs for LMS have been given by Katz (SSR 2016) and Fluhrer (Eprint 2017/553). However, the actual structure of SHA-256(/192) is the (chopped) Merkle-Damg{\aa}rd construction using a blockcipher-based Davies-Meyer function, and precise security bounds of SHA-256-based LMS\_SHA256\_M32 and SHA-256/192-based LMS\_SHA256\_M24 should be derived in the {\it ideal-cipher model (ICM)}. This was {\it not} considered in Katz and Fluhrer's proofs. In fact, by leveraging structural properties of (chopped) Merkle-Damg{\aa}rd, we exhibit forgery attacks against LMS\_SHA256\_M32 and LMS\_SHA256\_M24 that expose the inapplicability of Katz's and Fluhrer's random-oracle bounds to the concrete SHA-256 constructions. The precise security guarantees of LMS\_SHA256\_M32 and LMS\_SHA256\_M24 thus remain unknown (and are also missing in the standards). To bridge the structural gap, we provide ICM-based security proofs for the additive-Davies-Meyer abstractions of LMS\_SHA256\_M32 and LMS\_SHA256\_M24. The security level of LMS\_SHA256\_M32 is roughly $256-\log_2 \widehat{B}$ bits, where $\widehat{B}$ is the number of blocks in SHA-256 calls internally made by LMS\_SHA256\_M32 and $\widehat{B}\ll2^{128}$. The security level of LMS\_SHA256\_M24 is roughly $\min \{ 192 - \log_2 \widehat{\Gamma} , 256-\log_2 \widehat{B} \}$ bits, where $\widehat{\Gamma}$ is the number of SHA-256/192 calls internally made by LMS\_SHA256\_M24 and $\widehat{B}$ is the number of blocks in them, and $\widehat{B}\ll2^{128}$ and $\widehat{B} \widehat{\Gamma} \ll 2^{192}$. In conclusion, LMS\_SHA256\_M32 and LMS\_SHA256\_M24 ensure a moderate (yet not ``full'') level of security.

Note: Despite that the topic is post-quantum signature, the attacks and security proofs are mostly symmetric crypto.