Formalizing Hash-then-Sign Signatures

Abstract

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.