1.25.2007

Hash SHA-1 compromised...

This isn't really new news, but the hash SHA-1 (Secure Hash Algorithm-1) has been significantly compromised! So...what does that mean to you?

Hashes are a list of characters that "represent" the contents of a message or file and are intended to represent those contents uniquely. Hashes are expected to have two important properties:

  • If I have a hash value, I can't recreate the message or file in a reasonable amount of time
  • I should not be able to find two different files that create the same hash value
For example, take the word "HASH". If I use the following values for the letters in HASH

H=1.1
A=3.1
S=4.1

I can use a special formula to create a value that represents the word "HASH".

For example, my (totally fictitious) formula might be:
  • sum of the (locations X values)
Where I multiply a number that stands for the location of the letter within the word by the value of the letter and then take the sum of the results.
  • the first H is the first letter and has a value of 1.1 => 1 X 1.1 = 1.1
  • A is the second letter and has a value of 3.1 => 2 X 3.1 = 6.2
  • S is the third letter and has a value of 4.1 => 3 X 4.1 = 12.3
  • the last H is the fourth letter and has a value of 1.1 => 4 X 1.1 = 4.4
Adding all of these up gives me 24.0.

The letters SAHH would give me a value of
  • the first S is the first letter and has a value of 4.1 => 1 X 4.1 = 4.1
  • A is the second letter and has a value of 3.1 => 2 X 3.1 = 6.2
  • H is the third letter and has a value of 1.1 => 3 X 1.1 = 3.3
  • the last H is the fourth letter and has a value of 1.1 => 4 X 1.1 = 4.4
Adding all of these gives me...18.0, even though the letters in the word are the same...thus we can calculate the hash value and prove that the words are different.

Why is this important? A workable hashing algorithm can help prove that something has not changed since it was created. For example:
  • You send a contract to a client and they alter it slightly...something subtle that you wouldn't notice right away...compare the hash value of the two files and you can prove they altered it.
  • Many popular files are hosted on multiple sites (called mirrors), but those sites may not be controlled by the author of the file. Once you download the file, you can take the hash value and compare it to the hash value posted by the author - if they don't match, you can tell you have a file that was corrupted during the download or worse yet, has been tampered with by the bad guys.
  • Monitoring software on your computer can use hashes to tell that a virus or trojan has altered your files or programs, by periodically checking your current files against baseline values it keeps in a database. Any change to your program results in a different hash and your monitoring software can alert you to the change.
Now that SHA-1 has been compromised, there is the threat (albeit, very remote) that someone can create two different files that have the same value. The computing power and time necessary to do this are outside the realm of normal folks, so no need to panic yet. The folks at the National Institute of Standards and Technology (NIST) are working on creating a new hashing algorithm and should have one in about 3 years.

The take home message:
  • don't panic yet
  • look for hash values when you download files (especially from mirror sites)
  • compare the hash value of the file to the author's hash value
  • keep your eyes out for future versions of hash algorithms
For more info on hashes, see these articles/sites:
  1. Software to calculate hashes: HashCalc
  2. Example of a site that lists hash values of their software (the SHA-1 values are listed before each of the "filenames" that end in .iso)
  3. More details on hashes by Bruce Schneier
  4. NIST's write-up on SHA-1
Chalmer

No comments:

Google