SHA1 concerns and implementing SHA256 and beyond

By now, I am sure you have seen or heard the news about SHA1 being broken.

In a somewhat timely fashion, I had been (re)reading Bruce Schnier and Niels Ferguson's book Practical Cryptography and Bruce Schnier's Applied Cryptography book (both excellent resources) for a couple of weeks for one of my projects before the SHA1 news. Schnier and Keith Brown have both been saying for awhile we should avoid SHA1 and go with SHA256 or SHA512. Now, from what I have heard/read, the government is advocating this as well.

What do we do now? Obviously, there are a lot of solutions already built using SHA1, and since these are one-way hashes, you can't easily "decrypt" a value to get the original value back.

Looking around, I notice a lot of language choices to implement SHA1, but not SHA256 or SHA512. Microsoft .NET offers SHA256 AND SHA512 as options, but what if you are communicating with another applications that doesn't implement these later hash algorithms? One reason MD5 (also broken last summer) and SHA1 were so popular was because they were fast, much faster than the later variations (called SHA-2 implementations). So, no one thought to implement these later versions as SHA1 was thought to be secure enough for awhile.

This past weekend I spent some time going through the algorithm specs to convert a SHA1 algorithm implementation to a SHA256 implementation (in a non-.NET language). It wasn't too difficult, but I imagine this will need to be done more for other languages as we shift away from SHA1 in the near future.

Published Wednesday, February 23, 2005 1:18 PM by RHurlbut
Filed under: , ,

Comments

Wednesday, February 23, 2005 4:12 PM by Valery Pryamikov

# re: SHA1 concerns and implementing SHA256 and beyond

Robert,
break of SHA1 is very important from scientific/cryptographic point of view, but it is not quite practical threat to the security of existing systems... 2^69 is a very big number - 32 times stronger than MD5 is ever supposed to be against simple brute force collision search... and no one has ever constructed MD5 collision by simple brute force yet. Wang's attack on MD5 seems to be similar to what they used to attack SHA1... and last year breaking of MD4 was much lesser effort than 2^64 (about 2^34 if I remember it correctly).
2^69 - 2^70 is achievable, but way too expensive for constructing two random collisions. That doesn't pay off! Just for comparison you can check the effort distributed net is taking to break 72 bits key. Several thousands computers (with quite serious horse power among them) are working together for 813 days and only managed to search about 2^63 key combinations: http://stats.distributed.net/projects.php?project_id=8.
FPGA chips (that was used on DES Cracker) didn't seem to follow Moore's law (at least as it looks to me). To build a massive parallel VLSI board full of FPGA chips to make 2^69, 2^70 operations in one year timeframe would cost at least several millions... and all that just for conveying an attack which has very low probability of success. It would be much chipper to bug the processor or the mother board or use some side channel/tempest, or install rootkit or ... whatever... to get guaranteed results

-Valery.
Wednesday, February 23, 2005 4:20 PM by Robert Hurlbut

# re: SHA1 concerns and implementing SHA256 and beyond

Valery,

Agreed. But, consider this attack getting easier and cheaper (Moore's Law withstanding) as the years go by. How long does hashed data need to stay secret? If I remember, estimates were something like 50 years lifetime on some of these hashes, but they have now been reduced by significant factors based on the latest research. Does that make a difference? Not for everything, of course, but it could for some very sensitive data.

Robert
Friday, February 25, 2005 5:57 AM by Valery Pryamikov

# re: SHA1 concerns and implementing SHA256 and beyond

Yes, attack will get better in years to come (just as an old NSA's saying that "attacks always get better; they never get worse"). However when it concerns SHA-1 collision resistance, even improving this attack 32 times still means that would be harder than MD5 has ever supposed to be. If we say that attack techniques will be improved to speed it four-five times then to compensate rest of 32/4 speed increase Moore's law will require at least 12-16 years. But Moore law would not hold forever (man can't do anithing against phisical limits like speed of light and size of electron)... Moore's law already started to shows significant cracks. And attack will be quite expensive regardless of progress - it will always be easier to bribe the guy.
Sunday, February 27, 2005 4:19 PM by TrackBack

# More on SHA1, MD5 and other hash algorithms with .Net

More on SHA1, MD5 and other hash algorithms with .Net