# Could we use a more efficient hash for signature generation?

Is it possible to use a more efficient hash - such as one based on GHASH - instead of a cryptographic hash for signature generation?

In other words, could a combination of a fast hash and the private key operation together provide the security that we expect from a cryptographic hash? Could such a scheme be proven to be secure assuming that the underlying primitives are secure?

• And no, I did in this case not perform a whole lot of research. I think the question is interesting enough to be asked as a question here without having to look up all the scholary articles on it. Sorry :) – Maarten Bodewes Oct 20 '18 at 13:32
• Schnorr-based signature schemes like EdDSA famously "only" require target-collision resistance instead of full collision resistance. Now the question is of course whether you would actually trust a hash function which fails to provide full collision resistance but claims to have target-collision resistance... – SEJPM Oct 20 '18 at 18:26
• And of course if your message is really short hash-based signature schemes famously only require one-way-ness of the hash function. – SEJPM Oct 20 '18 at 18:32
• GHash is not second pre-image resistant and thus unsuitable – CodesInChaos Oct 20 '18 at 19:15
• This PDF-paper by Neven, Smart and Warinschi explicitly lists the requirements on the hash function in section 4. It appears that the answer is "it's complicated" and in fact so complicated that I won't answer (for now). – SEJPM Oct 20 '18 at 19:24

As mentioned in the comments already, you do not need collision resistance. You can get away with target collision resistance (TCR). The security game for TCR considers families of hash functions and requires the adversary to select the message it will find a collision for before it learns under which function of the family it has to find it. This is applicable in hash-and-sign signature schemes where you have a fixed length signature scheme that works without first hashing the message (like RSA) and then add a hash function to handle arbitrary length messages by signing their hash (like RSA-FDH). With TCR, you select a random function index and sign it with the hash.

One problem here, if you want to go for standard model security, is that the function indexes (keys) have to have length logarithmic in the message length. At least we do not know any domain extenders for TCR better than this. However, I will omit the details. A "heuristic" construction is the RMX construction by Halevi and Krawczyk.

For Fiat-Shamir based constructions like (EC)DSA things are not that easy as you cannot just "additionally" sign the index. What you can do however is to reuse the random nonce (think of $$g^r$$ in Schnorr) as index as pointed out by Mironov in this paper. Actually, that paper discusses a lot of the things I just wrote in more detail.

If you want to go weaker you start getting to run into issues. If you use the hash to compress the message you are signing, you need some sort of collision resistance (which TCR is). At least, you definitely need second-preimage resistance (which one might also consider a variant of collision resistance as you actually output a collision...). If your hash is not second-preimage resistant a malicious party, after seeing a message signature pair, can always come up with a colliding message for which the signature is valid.

• So if I put this in layman's terms: I cannot use GHASH because it doesn't offer second-preimage resistance, but for some schemes such as Schnorr signatures I can get away with weaker crypto hashes (MD5 / SHA-1 are examples in the paper that SEJPM linked to in the comments) because they just require TCR instead of full collision resistance. Am I on the right track? – Maarten Bodewes Oct 20 '18 at 23:01
• Yes, and in theory yes. In practice, I would still stick to hash functions that do not admit any known weaknesses and consider this a "security buffer". The problem with weakened constructions like SHA1 or MD5 is that they seem more likely to further break down as their structure seems to be vulnerable. – mephisto Oct 21 '18 at 10:15