Over the last two years, most of the digital world was forced to move from the flawed SHA-1 (Secure Hash Algorithm version 1) digital hash to SHA-2 (Secure Hash Algorithm version 2) because of increasingly successful cipher attacks. Anyone involved in those migrations knows the many hundreds of hours of research and work it took to successfully pull it off with minimal operational interruption. In more cases than we would care to admit, we prepared as best we could, “threw the switch,” and then hoped for the best. Cipher migrations aren’t something I would wish on my worst enemies.
Why then didn’t we move to SHA-3 (Secure Hash Algorithm version 3) instead of SHA-2, since we know that SHA-2 shares the same mathematical flaws as SHA-1 and SHA-3 doesn’t? Why are we being forced to do a SHA cipher migration all over again?
SHA ciphers and increasingly sophisticated attacks
SHA-1 was designed by the United States National Security Agency (NSA) and published by National Institute of Standards and Technology (NIST) as a federal standard (FIPS Pub 180-1) in 1995. It produces a 160-bit message digest, which if cryptographically perfectly secure means that it would take a brute force guessing attack 2159 tries on average to crack a hash. Even in today's world of very fast cloud computers, 2159 tries is considered non-trivial to create a useful attack. Non-trivial is the term crypto professionals use when they mean almost impossible, if not impossible, given current understanding of math and physics.
Starting in 2005, several theoretical attacks against SHA-1 were publicly documented. By 2012, SHA-1 attacks had theoretically reduced SHA-1's protection from a 159-bit maximum average to 57.5 to 61 bits of protection. For many years, this was just a theoretical attack. Over time, it was expected that theoretical would turn into practical, and that’s exactly what happened (although it took another five years).
Older ciphers getting cracked over time is an expected outcome for all cryptographic ciphers. Accordingly, NIST (along with the NSA) periodically holds public contests where anyone can submit newly created ciphers for review and potential selection. These contests usually take many years and are attended by the world’s leading cryptographers. In the end, a new cipher standard is chosen and announced as the new U.S. government’s officially required cipher. This is how many of the ciphers, including Advanced Encryption Standard (AES) and SHA-3, came into use.
In January 2011 (with NIST document SP800-131A), SHA-2 became the new recommended hashing standard. SHA-2, is often called the SHA-2 family of hashes, because it contains many different-length hashes, including 224-bit, 256-bit, 384-bit, and 512-bit digests (each discussed and released in related NIST Federal Information Processing Standard documents). You can't determine which SHA-2 bit length someone is using based on the name alone, but the most popular one is 256-bits by a large margin.
Slow move from SHA-1 to SHA-2
Even though successful attacks against SHA-1 were mounting and SHA-2 has been NIST’s required hash standard since 2011, most of the world had not moved to SHA-2 by 2016. The world reacts quickest to pain. At the time, public SHA-1 hacks were only theoretical.
In 2015, most of the world’s biggest crypto-using vendors decided to force their customers to move from SHA-1 to SHA-2 by January 1, 2018, because the theoretical breaks were absolutely going to turn into a real break soon. It mostly worked. Most companies were recently forced to do emergency migrations to SHA-2 for any program or device that relied on it. I wrote a whitepaper on the subject and several columns, including this one.
By early 2017, a large percentage of customers had migrated to SHA-2. It was just in time. On February 23, 2017, Google announced a successful, real-life, SHA-1 collision attack, demonstrated by presenting two different PDF files with the same SHA-1 hash. This attack essentially broke SHA-1 completely.
You could not have written a better global migration outcome. The world’s crypto vendors successfully moved most of the world from SHA-1 to SHA-2 just before SHA-1 was broken. Whoever hadn’t already migrated has a much easier time of it. Hundreds of thousands of companies had already completed successful migrations, so instructions on how to migrate were available on the web, vendors were ready to assist, and most of the software and device vendors had already prepared as well. The SHA-1 to SHA-2 migration planning and scheduling was a complete success. Lots of pats on the back were going around.
Unless you asked yourself why we didn’t just migrate to more secure SHA-3 instead?
Why migrate to SHA-3?
SHA-1 and SHA-2 were not created by publicly sourced contests. They were created by the NSA and then released as public-use patents. Although not identical, they share some of the same underlying math, which contains the same cryptographic flaws. What allows SHA-2 to be a safer hash is largely provided by its increased hash length.
Issue with SHA-2
Although significantly different, SHA-1 and SHA-2 share the same base algorithm (SHA), and ultimately some hash lengths are subject to the same types of attacks. In some scenarios, much of SHA-2’s better protection over SHA-1 is mostly due to SHA-2’s use of larger inputs and outputs.
Public attacks on SHA-2 have been happening since 2008. Just like what happened with SHA-1, the attacks against SHA-2 have been getting increasingly better and weakening SHA-2 over time. Some attacks have SHA-2’s effective protection down to 237. Some of the latest attacks, publicly announced in 2016, consider SHA-2 attacks to already be “practical”. Does this sound familiar? It should, because it’s what we were saying about SHA-1 just two or three years ago.
Again, it’s expected that existing ciphers will be attacked and become weaker over time. In fact, NIST selected SHA-3 using a public contest explicitly to have a new hash standard that was not derived from the SHA family ready to go when needed. The contest started in 2006, the Keccak cipher was selected as the sole finalist cipher in 2010, NIST published draft standards in 2015, and SHA-3 became an official recommended standard on August 5, 2015.
This is where many of wondered why we didn’t just move from SHA-1 to SHA-3. The world was being forced from SHA-1 with most of the work effort for the migration coming in later 2016 and 2017. The official drop-dead date for moving off SHA-1 was December 31, 2017. With almost three years to prepare, why didn’t we tell the world to move to SHA-3 instead of SHA-2?
Why didn’t we move to SHA-3?
The number one reason why the world didn’t move to SHA-3 is because almost none of the world’s software or hardware supported it. Even if you wanted to move to SHA-3, you couldn’t have, unless you wrote your own code and firmware for every device you owned or used.
On top of that, SHA-3 was a relative new-comer when the SHA-2 migration plans were being figured out. If you were in the early SHA-1 deprecation meetings, SHA-3 was not even an official standard yet. More importantly, SHA-2, although somewhat derived from SHA-1, was not as exploitable as SHA-1. Using any version of SHA-2 provided sufficient, for the time, protection. Third, SHA-3 was widely seen by many as being far slower than SHA-2. So why recommend something that was slower and wasn’t needed?
Most of the SHA-2 vendors had to update their SHA-2 routines to fix flaws anyway. It might have been just as easy for cipher vendors to write in SHA-3 algorithms as it was to implement SHA-2. Cipher vendors would have done so if the recommended pathway was SHA-1 to SHA-3 instead of having to go to this intermediate step of SHA-2.
What about the SHA-3 speed issues?
SHA-3 is slower only in software. In hardware, it handily beats SHA-1 and SHA-2. Cryptographic routines are increasingly being handled by hardware components, and that is expected to increase in the future.
Software-wise, SHA-1 is three times faster and SHA-512 is two times faster than SHA-3 on Intel CPUs. While this doesn’t sound great, most of the hash verifying components in most software and devices are so sparsely used that doubling or tripling of the time needed to hash or verify a hash wouldn’t be unduly burdensome in most customer scenarios. Because our CPUs are getting faster and faster, it wouldn’t be long before the increase in time wouldn’t be noticeable at all. Plus, the authors of the hash cipher selected as SHA-3 have told the NSA/NIST a few ways to make it significantly faster in software.
More important, why have a faster hash if it can’t be relied upon?
How to prepare for the SHA-3 migration
There is no doubt that within a few years we all will be executing a SHA-3 migration. What can you do?
First, be aware of the coming SHA-3 migration. When will you be forced to do it, no one knows. It depends on how the practical attacks against SHA-2 keep stacking up. One day, Google or someone else will announce that SHA-2 has been broken and we’ll all need to move. You don’t need to be one of the surprised ones.
Second, keep your old SHA-2 migration plans and documents handy. An SHA-3 migration will look much like your SHA-2 migration efforts. Think about what you would have done different. What were the lessons learned from your SHA-2 migration? Update your existing cipher migration documents now so the lessons learned aren’t lost. Are you still documenting what software and hardware products that you have use what ciphers?
Finally, remember that cipher migrations will be a normal, regular, ongoing cycle if you work in the IT world. You, your co-workers, and your vendors need to become crypto-agile. I covered the concept of crypto-agility here.