January 22, 2020 - Earlier this month, the Real World Crypto(graphy) conference took place at Colombia University in New York City. The RWC conference is a collection of presentations where cryptography meets industry, so much of the content is tangible and attracts engineers as much as it does researchers. This year’s conference covered topics from Facebook’s quest to implement end-to-end encryption to statistics that illustrate the adoption of the TLS 1.3 standard, the latest in transport layer security.
One of the most pressing takeaways from RWC this year was a presentation demonstrating a practical attack on SHA1 hashes. Let’s back up for a second though – why the emphasis on practical? What does this mean for us?
As a refresher…
SHA1 is a hash function which, as we know, is a one-way (irreversible) cryptographic mechanism that is typically used for integrity verification. Remember that this is because the outputs of hash functions are intended to appear completely different and unrelated, no matter how similar the inputs are (unless the inputs are the same, in which case the hash function must output the same value). Therefore, if, for example, the correct SHA1 hash of a file you want to download is a1b2c3d4e5…a1 then when you download it and check the SHA1 hash, it should exactly match. If it does not, then the file may be corrupt.
Great! What about the attacks against hash functions?
As mentioned above, hash functions should be irreversible. An attack against a hash function is considered significant if it demonstrates the ability to find the input corresponding to a hash output more efficiently than simply brute-forcing all possible inputs until a match is found. (Also remember, a match like this in the context of a hash function is called a collision).
Typically in the world of cryptography, an algorithm will start to be phased out once a theoretical attack against it has been shown. This means that the attack has been described in a research setting, but an implementation has not been presented yet. Do you remember the hash function MD5? A theoretical attack was shown against MD5 which led to the recommendation to stop using it. Intuitively, we can understand that the theoretical could be dangerous, but it may not feel like an immediate threat until the attack can be shown to be practical. At that point, it should be considered extremely dangerous to use such algorithms because an attack against them has been shown to be feasible. Well, in the case of MD5 a practical attack emerged not long after the theoretical one and now it is broad knowledge that it is highly concerning if MD5 is seen in the wild (there are some cryptographic functions that leverage MD5 in ways that are still secure, but that is beyond the scope of this post).
This same story line has come to fruition for SHA1. Theoretical attacks have been published and improving since 2005, but the first practical attack was shown at RWC a few weeks ago. The attack showed how to generate two *different* inputs that will result in the *same* output of the SHA1 hash function. One of the best moments of the presentation is when the researcher showed how relatively cheap the attack is… resources are not so expensive that only high profile groups see it within reach.
What this means…
…is that mechanisms relying on the uniqueness of SHA1 hashes could be compromised. The demonstration in the paper uses PGP as an example, but other applications of SHA1 such as certificates could be compromised as well.