Many people don't understand crypto. That's okay. I don't either. But, I do get math, and I want to show you something **SIGNIFICANT** that affects your everyday habits online.

It's been demonstrated that MD5 is broken. It's now trivial to find what are called "collisions". This is where two completely different inputs hash to the same output. Here is a demonstration: http://www.mscs.dal.ca/~selinger/md5collision/

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.

This is far too slow. Let's look at another comparison. Bitcoin.

First, Bitcoin uses SHA256 rather than SHA1 as part of its mining algorithms. According to http://blockchain.info/charts/hash-rate, the Bitcoin network is processing about 30 million gigahashes per second. That's 30 *quadrillion* hashes per second. The size of 61-bits is a mere 2.3 quintillion hashes. Let's do some math:

2.3 quintillion hashes divided by 30 quadrillion hashes per second = 76 seconds.

What does this mean? The Bitcoin network is currently working over 2^61 SHA256 hashes every minute and 16 seconds. If this were SHA1, we could brute force 1,150 SHA1 collisions *every day*.

Why should you care? Because when you connect to a server with SSH, SHA1 is likely presented as the hash. When you use your browser to connect to an HTTPS site using SSL, SHA1 is lkely presented as the hash. When you encrypt something with OpenPGP, or cryptographically sign a key or document, SHA1 is likely presented as the hash.

It's the case that most of your encrypted communication online is using SHA1 in one way or another. And yet, it's well within our reach to process 1,150 SHA1 collisions EVERY. SINGLE. DAY. It's long over due that we replace SHA1 with SHA2 or SHA3. Not because some theoretical proof says so, but because we can *actually do it*.

## { 5 } Comments

Excellent post! I need to get with the program and audit everything.

A correction: because of the birthday paradox it only takes - roughly - the square root of the keyspace to have a 1/2 chance of choosing a key twice. However, this obviously doesn't apply to any *specific* key. So, to have a collision with 1/2 probability it takes roughly sqrt(2^160) ~ 2^80 by brute force for sha1. Which is still considered cryptographically secure (really anything > 2^64).

In the case of sha1, there are specific attacks that get that to below 2^64, like you mentioned.

Yes, you're correct. However, I'm not necessarily just assuming brute force searches. I'm assuming that whatever methods are used to break SHA1 down to 2^61, we can apply those methods, such that we can brute force the remaining space after our initial methods have been applied. As such, using ASICs strictly for SHA1, we could brute force the entire 2^61 space every 76 seconds.

I should have quoted the portion I was correcting: "Technically, it should take 2^160 operations to find a collision with SHA1".

You can use the birthday paradox with any uniformly distributed random keyspace. For example, sha256 at 2^256, you could randomly generate a little more than 2^128 hashes until you have a 50% chance of finding a collision.

I wasn't making a general correction for your entire article. Like I mentioned in my comment, you talked about far better, specific attacks against sha1.

Ah, I see. Indeed. The birthday paradox does apply to finding collisions in a keyspace. I'll adjust the article. Thanks for the clarification.

## { 2 } Trackbacks

[…] In my previous post, I demonstrated that a key with an output space of 61-bits was far too small. At the time of this writing, the bitcoin network is processing 2^61 SHA256 hashes every 76 seconds, and it's only going to grow, as there is financial gain to be made from mining. […]

[…] quantify this a bit, in a previous post, I demonstrated that a SHA1 hash has an output space of 61-bits due to cryptanalysis techniques, […]

## Post a Comment