3
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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... $\endgroup$
    – SEJPM
    Commented Oct 20, 2018 at 18:26
  • $\begingroup$ And of course if your message is really short hash-based signature schemes famously only require one-way-ness of the hash function. $\endgroup$
    – SEJPM
    Commented Oct 20, 2018 at 18:32
  • $\begingroup$ Ah, "target-collision resistance". That sounds like a good term to Google. Hopefully I won't just score insightful comments but also answers of course. I'm already glad I asked :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 20, 2018 at 18:36
  • 2
    $\begingroup$ GHash is not second pre-image resistant and thus unsuitable $\endgroup$
    – CodesInChaos
    Commented Oct 20, 2018 at 19:15
  • 2
    $\begingroup$ 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). $\endgroup$
    – SEJPM
    Commented Oct 20, 2018 at 19:24

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 20, 2018 at 23:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – mephisto
    Commented Oct 21, 2018 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.