Abstract: The long expected (by cryptographers) news is that it is becoming moderately cheap to find collisions on SHA-1 hash algorithm.
Current cost estimate is $75k – $120k of Amazon EC2 CPU/GPU resources, and this cost is expected to go down by factor 2 every 3 years or so (Moore’s Law) plus by additional factors for hardware and algorithm development.
The researchers at CWI did not produce actual hash collision, rather they got a very good measure of how much effort it needs at what commercial cost.
What does it mean for security algorithms?
It means that it is becoming possible to create a different message satisfying same public key signature that another valid message has. Alternate form of faked message is to factor the public key to its private key version, and then just sign with that – but large enough RSA key or good enough ECC key is much harder to factor than production of faked message with same SHA-1 than any previous published signature had.
However finding a hash collision will take non-trivial amount of time and resources, and it won’t be making quick turn-around challenge/response authentications any time soon. But it may become possible to create fake documents with valid signatures where document’s usage lifetime is months to years.
What are examples of documents where it can matter?
- Certificates – valid typically for up to 10 years. (CA signing certificates especially!)
- Legally binding agreements executed in digitally signed form and disputed after months or years.
- Security check sums of valuable data sets (including software source code releases)
What are examples of usages where collisions do not matter?
- Data compression for indexing something where all index matches are checked for additional keys or conditions to identify the interesting case. Typical database operations use much less compute intensive hash algorithms than SHA-1 to formulate these help indexes.
- Reversing longer input text from hash output result. (Probably for anything over 10 bytes, definitely for anything over 20 bytes.)
- Multi-round salted password hashes (probably stays safe)
In the PKI protocol spaces a few protocols use and will keep using SHA-1 to generate lookup index keys, however for primary signature formulation the news is that SHA-1 shall not be used.
The Certificate Authorities must phase out SHA-1 usage in certificates rather sooner than later. Signature generation on S/MIME emails must migrate to SHA-2 or SHA-3 algorithms.
PKI Vulnerabilities to SHA-1 Becoming Broken
Foremost is that currently around 28% of the internet connected servers serving TLS crypto (HTTPS for laymen) use certificates signed with SHA-1 for their self-identity.
This vulnerability centers on the way how PKI signatures are made: The certificate is a collection of data records that together give an identity to a public key value (which is also included in the collection). The signature is made by compressing (a canonical binary representation datastream of) certified data with SHA-1 hash algorithm and then signing that hash result with RSA. Then wrapping the certified data with the signature and associated data describing the signature method.
The vulnerability here is that only one hash algorithm output is signed at any given time, and therefore finding an efficient way to find different source data that produces same hash result is direct threat to all signatures.
Mostly for the end entity certificates (random web servers) this is not an interesting threat that somebody can fake its identity – because mostly those servers are not that interesting.
But when the server becomes interesting as a target for a faked service, then one should not be using certificates or certificate authorities that use SHA-1.
When does a system become interesting? We would hazard a guess that any site with more than purely single person private data would be such. Any web server that has more than 1 external reader a month. Especially any business related site.
Further Reading
See researchers SHAppening page for more information about what they actually achieved, and how.