March 29th, 2017
(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: email@example.com
SHA1 was meant to be a replacement for MD5. MD5 has an output space of only 128-bits, where as SHA1 has an output space of 160-bits. SHA1 is also designed differently than MD5, and is meant to not suffer the same sort of weaknesses or attacks that MD5 faces. However, over time, cryptographers have been able to severely attack SHA1, and as a result, they’ve all been warning us to get off SHA1, and move to SHA2. It should take 2^160 operations to find a collision with SHA1, however using the Birthday Paradox, we can have a probability of 50% of finding a SHA1 collision in about 2^80 operations. However, cryptanalysists have torn down SHA1 to a complexity of only 2^61 operations. Even better.
An output size of only 61-bits is small. For comparison sake, the distributed computing project http://distributed.net cracked the 64-bit RSA key in just over 5 years at a snails pace of 102 billion keys per second: http://stats.distributed.net/projects.php?project_id=5. The motivation was prompted by a $10,000 dollar award from RSA labratories to find the secret key encrypting a message.
Granted, you don’t need to search the entire 64-bit keyspace to find the key. It’s just as likely you’ll find the key immediately at the start of your search, as it is to find the key at the end of your search. But it shows how reachable 64-bits is. The reduced search space of 61-bits from SHA1′s attack vector is 8x smaller in search space than the 64-bits of that RSA secret key challenge. So, at 102 billion hashes per second, it’s reasonable to conclude that you could exhaust the 61-bit search space somewhere between 6 and 9 months.