For those of you Slashdot readers out there, you may have heard by now that ‘SHA1 is broken’. Recently I did some security videos for Microsoft, and decided that SHA1 was the best hash function for the example (modifying an existing application to store hashed passwords).
The videos I did were part of the “How Do I” series, and not exactly the place to explain why it was appropriate to use SHA1. But for those of you looking to understand the why behind the example, I’ll take a few minutes to explain it.
What exactly is SHA1?
SHA1 is a hashing algorithm, also known as a one way function. A one way function is where given any value of x, it is easy to find f(x), but given f(x) it is unrealistic to find x. One way functions allow us to take a ‘fingerprint’ of data without storing the data itself. In a password scheme, instead of storing a user’s password (x) we instead store a hash of the password (f(x)). Later when the user wants to login, he again supplies a password which we hash and compare against our stored value.
It’s also useful for ensuring the integrity of data. When a message is sent over an unsecured channel, a hash of the message can also be used to check the message once it reaches its destination. If the message does not match the hash, then we assume it was modified in transit.
Designed Strength of SHA1
When we hash data, the range of values for x is infinite. The hash on the other hand is a fixed size. Therefore, for each value in the range of our hash, there are an infinite number of possible values for x.
This range of possible values determines the odds of guessing a value x to match a known value f(x). If the size of the hash value was 21, there would be a 50/50 chance that the valued guessed would match our known f(x). That’s why SHA1 utilizes a very large hash size of 2160. To put that in perspective, the Earth is composed of 2170 atoms. It’s computationally unrealistic that anyone would be able to beat those one in 2160 odds to find a value x which matches our known value f(x) (with today’s technology).
The Birthday Paradox
Some of you may be asking yourself, “but I read on Wikipedia that SHA1 has a strength of 280?” This is true, but to understand why, we will first look at the birthday paradox.
How many people must be in a room before the odds are even that one of them shares your birthday?
How many people must be in a room before the odds are even that two of them share the same birthday?
In the first question, we are looking to match a specific value, while in the second we were just looking for any 2 matches. The answers are 253 and 23. The reason for the difference is that between the 23 people, there are 253 unique combinations. In one way functions, this is the difference between finding what we call a pre-image value versus a collision.
The reason we say the strength of SHA1 is 280, is because we are talking about finding collisions (any two values for x with the same f(x)). When we are hashing passwords, we are asking the person logging in to match a specific f(x), and the strength of SHA1 in that situation would be 2160.
The Current Strength of SHA1
The analysis of SHA1 shows that collisions were found in 263. It’s now becoming computationally feasible to find two values of x that match an f(x). It’s still short of being probable that those two matches found would allow an attacker to compromise an encryption system, but the worry is that SHA1’s strength will continue to decline.
Until the strength of SHA1 drops to 240, it is still a valid way to protect against pre-image attacks.
Why Did I Choose SHA1?
In addition to SHA1 being secure in the example, there were a couple of other reasons I choose to use it instead of something like SHA256 (2256). The first reason was that in the example, I was showing how to modify an existing application, by simply changing the value in the password field from a password to the base64 string representation of the hash, which is 28 characters in length (for SHA256, it would be 44 characters). If the database allowed passwords that size, then it’s trivial to add support for hashing.
The other reason is that there are far easier ways of attacking a password field than targeting SHA1. An offline dictionary attack against the users’ passwords is several orders of magnitude easier. SHA1 protects the hash against brute force attacks. It does nothing to protect a user who chooses a poor password.
A system is only as strong as its weakest link.
-Eric Marvets
