Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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)?
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.
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:
Some comments to this post are of great help.
Thanks to Joshua, Squeamish Ossifrage, and Peter Green.
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.
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.
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.
