Suppose a hash function like SHA-1 has known collision attacks (including chosen-prefix collision attacks) but no known preimage attacks.

Does that mean there are no known attacks against using it in a signature scheme, under these assumptions:

  • I'm signing data by taking the SHA-1 hash and then using a public-key signing scheme to sign the hash (and assume the public-key signing scheme is not broken)
  • I salt the data before taking the hash, and then sign the salt along with the hash (so if the attacker tries a "chosen-prefix collision attack", where they have a 'good' document and an 'evil' document with the same SHA-1 hash value and they want me to sign the 'good' document, the salt will prevent that attack from working)

I don't understand why that would be considered unsafe if the only known attacks against SHA-1 are collision attacks.

Is it just because of the general inference that if a hash is vulnerable to collision attacks, it is more likely to be vulnerable to preimage attacks, even if none are known currently?

  • 2
    $\begingroup$ Because I can forge two messages, first a money transfer of $\10 and later a can send you to show that I sent you \$100000. Isn't this an attack? $\endgroup$
    – kelalaka
    Jan 21 '21 at 0:17
  • $\begingroup$ Possibly helpful $\endgroup$
    – fgrieu
    Jun 21 '21 at 14:47
  • $\begingroup$ Generally the signature generation includes hashing; the hashing isn't performed separately. I wonder if you haven't just described DSA, and that would not be secure under your conditions as far as I can see (prefixed randomness & randomness included in signature generation). $\endgroup$
    – Maarten Bodewes
    Jun 22 '21 at 14:51

Your idea of salting the signature to prevent the collision attack doesn't work, because your salted signing operation is a deterministic mathematical function, and the random choice of salt is only made at signature time, not at verification. Your signature algorithm has to be something like this. For a document $x$ and hash function $H$:

  1. Hash the document: $h = H(x)$;
  2. Generate a random salt $s$;
  3. Apply the signature primitive function: $r = \mathrm{Sign}_{sk}^s(h)$;
  4. Return $(s, r)$—the pair of the salt you picked and the signature primitive's result. Because verifiers are going to need the value of $s$ you picked on this occasion to verify the signature.

For a document $y$ and a putative signature $(s, r)$, the verification algorithm has to work something like this:

  1. Hash the document: $h = H(y)$;
  2. Apply the verification primitive function: $\mathrm{Verify}_{pk}^s(r)$.

No random choices involved in verification. So if I can craft a pair of colliding documents and convince you to sign the "good" one for me, I can take the signature you produced and give it to somebody along with the "bad" document, and when they try to verify it it'll check out.

  • 3
    $\begingroup$ I think he meant to salt the message along with document before hashing. Of course carelessly applying the salt won't work because finding collision for H(m)=H(m')=h also can make collision for H(m||s)=H(m'||s)=h', adjusting for padding. $\endgroup$ Jan 21 '21 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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