Digital Signatures with Outsourced Hashing

Abstract

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 the (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 many other 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.