17
$\begingroup$

Google succeeded to get a collision in SHA-1 last year in an attack called shattered. Does this fact make certificates based RSA-SHA1 Signature risky for creating fraud certificates?

If RSA-SHA1 signature is still safe, why is that (because the attacker doesn't have the private key)?

$\endgroup$
33
$\begingroup$

The answer is "not safe".

But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice.

Google found one collision based on some existing, publicly known collision attacks on SHA-1. Sees the introduction of Google's paper for a complete list of prior work.


First, let me briefly explain how RSA-SHA1 signature works. The explanation below is adapted from a W3C's page introducing RSA-SHA1.

  • The message $m$ is compressed via SHA-1 into a fixed-length string $h=\mathsf{SHA1}(m)$.

  • The RSA signature scheme (with padding via PKCS#1) creates a signature on $h$ rather than $m$. $\sigma=\mathsf{RSASignPKCS\#1}_\mathsf{sk}(h)$.

If SHA-1 is fully broken, we expect that we can find $m_1$ and $m_2$ with the same hash value under possible resource constriant: $\mathsf{SHA1}(m_1)=\mathsf{SHA1}(m_2)$.

In this case, they have the same $h$. A RSA-SHA1 signature for $m_1$ is also a RSA-SHA1 signature for $m_2$.


Now I give an example of why it fails. (corrected example, thanks to @peter-green)

I am the website owner of randomwebsite.com.
I want to have VeriSign sign a certificate for cvs.com.

So, I use the collision attack to generate two certificates.

  • A certificate for randomwebsite.com.
  • A certificate for cvs.com.

These two certificates have the same hash.

I have a CA to sign the certificate for randomwebsite.com.

Now, if you have randomwebsite.com's certificate signed by CA via RSA-SHA1, which has a signature for that hash. This signature can also be used in the certificate of cvs.com.

You can apply the signature to the fake cvs.com certificate. Different from the real cvs.com certificate, for this one, you have the private key associated with the public key in the certificate.

A more detailed discussion can be found in another post.


A lesson from the SHA-1 story:

  • Always use the MOST advanced cryptography. We know SHA-1 has some problems and there is SHA-256, SHA-512 and others to replace it. There is no reason to sit in front of a tiger.

Some comments to this post are of great help.
Thanks to Joshua, Squeamish Ossifrage, and Peter Green.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – SEJPM Jul 9 '18 at 16:08
6
$\begingroup$

Does this fact make certificates based RSA-SHA1 Signature risky for creating fraud certificates?

Not really.

A collision attack means that an attacker can create a pair of "files" (strictly byte sequences) with the same SHA1 hash. If one of those files is signed then the attacker can transplant the signature to the other file since their hashes match.

This is distinct from a preimage attack, in a preimage attack the attacker generates a file to match an existing hash. Preimage attacks are much harder than collision attacks; even the venerable MD5 has no known computationally feasible preimage attack (it has a theoretical one which is a bit better than brute force).

However not all collision attacks are equal. Generally, in the simplest collision attacks, the "good" file and the "evil" file are identical except for a small amount of random-looking garbage. Due to the structure of many hash algorithms, changing data before the collision garbage will break the collision, but changing data after it will not, provided that the same change is made to both the good and evil files.

Such an attack can be combined with a fancy format like pdf to produce a pair of documents with the same hash but different user-visible content. A common header is constructed, then the collision is found, then a common trailer is constructed which displays different information based on the content of the collision blocks.

Attacking a CA is harder for a couple of reasons.

  • CAs don't generally sign arbitrary certificates supplied by users, they generate the certificate and then sign it. Some parts of the certificate are controlled by the user but not all of it. In particular, certificates contain a "serial number" early in the certificate. Best practice for CAs is to use a randomised serial number.
  • The format of certificates is less flexible than something like pdf.

The upshot of this is that to realistically attack a CA you need a "distinct chosen-prefix collision" attack rather than a simple collision attack. You also need to be able to guess the "serial number".

Moving away from a hash function with known flaws is prudent, but there is a bunch of exaggeration going on.

$\endgroup$
  • $\begingroup$ i see, and what if the fraud certificate is the root certificate? (so it is possible to construct a copy of the certificate ) $\endgroup$ – adi Jul 9 '18 at 5:52
  • 1
    $\begingroup$ @adi: No, because that's a second preimage attack. To my knowledge there is not (yet) any published, feasible second preimage attack on SHA1. $\endgroup$ – Kevin Jul 9 '18 at 6:29
  • 1
    $\begingroup$ "CAs don't generally sign arbitrary certificates supplied by users, they generate the certificate and then sign it. " I think we should add that "CA" can change the certificate in an unpredictable way? $\endgroup$ – Weikeng Chen Jul 9 '18 at 15:33
4
$\begingroup$

No it is not safe to use SHA-1 anymore. CAs now use SHA-256. A collision means two messages produces the same hash value. When computing a signature, a message is hashed, then the private key is used to generate the signature. If two messages have the same hash value, one can get a signature of one message and claim it is the signature of the other message. If this is the case, then many security properties provided by digital signatures (like integrity, authentication, non-repudiation) will be gone.

In fact, SHA-1 have been considered not secure since 2004/5, and that was the primary drive behind the NIST competition on new hash functions, which led to the new SHA-3 standard.

Currently many organisations still use SHA-1 certificate. But it is just a matter of time, sooner or later people will move away from sha-1 like we did with MD5. Google has removed support for SHA-1 certificates in Chrome 56, and other browsers are doing the same.

$\endgroup$
  • $\begingroup$ i see, but why is it unsafe to use sha1 rsa signature? (although the attacker can get a collision in the sha1, he cannot find the private key, so he cannot create an identical signature) $\endgroup$ – adi Jul 8 '18 at 17:57
  • 3
    $\begingroup$ He does not need to create a signature, he just use the existing signature and it will pass verification when presented with the colliding message. $\endgroup$ – Changyu Dong Jul 8 '18 at 17:59

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.