0
$\begingroup$

What will it mean for ECDSA using SHA1 when we have practical attacks breaking the collision resistance property of SHA1?

[UPDATE] Added a bit more details to be clear.

If $(r,s)$ is the ECDSA signature for $m$, is it possible to give a different message $m'$ that will have the same signature.

Improve this question
$\endgroup$
3
$\begingroup$

The problem is that, imagine you sign a message $m$ using ECDSA and SHA-1 as hash algorithm. If an attacker manages to find a message $m'$ such as SHA-1$(m)$ = SHA-1$(m')$ then the computed signature for $m$ will be valid for $m'$.

So the attacker can substitute $m$ for $m'$ while keeping the same signature value. The receiver who will try to validate the signature won't be able to tell the difference.

[UPDATE] Let's explain it in details:

So when signing a message $m$ using ECDSA algorithm with SHA-1 hash function, according to wikipedia, it goes this way:

  • We compute $e =$ SHA-1$(m)$
  • Calculate $r = x_1\,\bmod\,n$ (where $(x_1, y_1) = k \times G$, $k$ is a random integer from $[1, n-1]$ and $n$ is the order of the elliptic curve)
  • Calculate $s = k^{-1}(z + r d_A)\,\bmod\,n$ (where $d_A$ is the private key signature and $z$ the $L_n$ leftmost bits of $e$)
  • The signature is the pair $(r,s)$

So if an attacker finds a message $m'$ as SHA-1$(m')$ = SHA-1$(m)$ then $e' =$ SHA-1$(m') = e$ and then $z' = z$. So the signature $(r,s)$ will be valid for the message $m'$ even if the attacker doesn't know the private key $d_A$ because all computations have been done for him.

Note that in this case the attacker needs a valid signature and to find a second pre-image to forge a signature.

An interesting comment from Ilmari Karonen:

There are practical scenarios where both $m$ and $m'$ may be controlled by the attacker, in which case a collision attack suffices. For example, the MD5 collision attack was used to forge SSL certificates by getting an established CA to sign an innocent-looking certificate, and then replacing it with another certificate with the same MD5 hash, but far higher privileges.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I don't that that is the case for ECDSA, because the signature relies on more than just the value of $z$ (first $Ln$ bits from the hash). $s = k^{-1}(z + r d_A) \mod n.$. Knowing or being able to predict $z$ won't help you with forging the signature. (with $d_A$ the private key and $k$ a random value). At least I think.. $\endgroup$ – Lee. M Feb 1 '16 at 15:54
  • $\begingroup$ You're right when saying that there are several parameters involved. But anyway, in the case described above the signature will still be valid despite other computations (because other parameters doesn't depend of the message, as you said it's the private key and a random value). $\endgroup$ – Raoul722 Feb 1 '16 at 16:00
  • $\begingroup$ If you have the pair $(r,s)$ for a message $m$, you can not simply use the fact that SHA1 has practical collision resistance attacks to provide me with a $m'$ that will validate against $(r,s)$? You would need the private key in order to allow the public key to validate against the signature? $\endgroup$ – Lee. M Feb 1 '16 at 16:15
  • 1
    $\begingroup$ Agreed, but in the context of SHA1 we are only worrying about collision resistance. So an attacker should have control over $m$ and $m'$. After he has $(r,s)$ and $m$ this will not work if second pre-image collision resistance is still a true property of SHA1. $\endgroup$ – Lee. M Feb 1 '16 at 17:03
  • 3
    $\begingroup$ If the attacker only has control over $m'$, then they need a (second) preimage attack to forge a signature. But there are practical scenarios where both $m$ and $m'$ may be controlled by the attacker, in which case a collision attack suffices. For example, the MD5 collision attack was used to forge SSL certificates by getting an established CA to sign an innocent-looking certificate, and then replacing it with another certificate with the same MD5 hash, but far higher privileges. $\endgroup$ – Ilmari Karonen Feb 1 '16 at 19:06

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.