International Association
for Cryptologic Research

Many practical signature schemes follow the Hash-then-Sign (HtS) paradigm: Instead of signing messages directly, messages are first hashed and then their hash values are signed. Attractive properties of the HtS approach include that the core signing algorithm does not have to get involved with handling arbitrarily long message inputs, and that the tasks of hashing and signing can be performed by different entities. For instance, if a signing algorithm is implemented in a smartcard setting, then an HtS scheme can allow sending only the hash value to the smartcard, instead of the whole message. While the HtS paradigm was introduced decades ago, most signature schemes leverage it, and many applications rely on it, security analyses for HtS signature schemes are typically conducted only holistically for the hash+sign hybrid. However, the corresponding security models (e.g., EUF-CMA) don’t cover the fact that the separation of hashing and signing allows for more attacks than monolithic schemes. In particular, cases where an attacker can interact with a smartcard and request the creation of signatures on arbitrary hash values (for which it may or may not know the messages), remain unaddressed. This work initiates a study of HtS signatures in the framework of provable security: After defining a precise syntax, we develop security notions that cover the artifacts of the separation of hashing and signing. We show that signature schemes exist that are weak in the HtS sense yet secure in the classic sense, demonstrating the relevance of our work. We then study the HtS security of a number of widely-standardized signature schemes, including of ECDSA. Finally, we propose a generic method for the secure separation of hashing and signing for signature schemes that use a Merkle–Damgård hash function.

Most practical signature schemes follow the hash-then-sign paradigm: First the (arbitrarily long) message is mapped to a fixed-length hash value, then a signing core derives the signature from the latter. As it is implementationally attractive, practitioners routinely exploit this structure by decoupling the two steps and distributing them among different entities; for instance, industry standards like PKCS#11 specify how security smartcards implement exclusively the core, leaving the hashing to their (untrusted) environment. At the same time, the classic security notions for signature schemes don’t consider such a decoupling, and thus don’t cover attacks involving, for instance, providing the core with maliciously chosen hash values. A first work that studied this gap appeared only recently (PKC 2024). While it could confirm for a few candidates that they remain secure when split according to PKCS#11, its syntactical abstractions and security definitions are too limited to cover most practical signature schemes (e.g., the many variants of Fiat–Shamir/Schnorr). This article studies how the functional separation of hashing and core in signature schemes can be systematized, so that implementational demands (in the spirit of PKCS#11) and, hopefully, security can be met simultaneously. We accompany this foundational work with a case study of a variety of standardized (EC)DLP based signatures. Surprisingly, as we show, their security varies across the full spectrum between universally forgeable and provably unforgeable. For instance, for the same scheme, we demonstrate universal forgeries when instantiated with 224-bit ECC (using an attack that completes in milliseconds), while we establish strong unforgeability for the 256-bit ECC case. Many schemes become completely insecure when the hash function is instantiated with SHA3 instead of with SHA2.