January 22nd, 2007
Putting the cracking of SHA-1 in perspective
SHA-1 is one of the most prevalent forms of a secure hash algorithm used in the legal and security industry. Now that Professor Xiaoyun Wang and her associates in Tsinghua University and Shandong University of Technology have officially cracked the SHA-1 hashing algorithm, the fallout will begin. This won't actually be due to security concerns for the most part, but the legal ramifications may be severe.
Background:
A digital hash is basically a fingerprint of a data file. The perfect hashing algorithm will always produce a unique-enough finger print for a particular data stream that it is practically impossible to find a different data stream matching that finger print. Professor Wang did just that and found a different data stream with an identical finger print that matches the SHA-1 hash of the original data stream. While hashes have been broken before, the SHA-1 hash was published by the NIST in the1995 and was believed to be solid for a long time to come. But professor Wang surprised the cryptographic community in early 2005 with the announcement that she and her team had figured out a way to speed up the cracking process by more than 11 orders of magnitude.
Before I continue, I want to make it clear that the work of Professor Wang and her team is probably one of the biggest accomplishments in the field of cryptanalysis in recent years and is very well respected by her peers. But to put this event in the proper perspective, the finding of a hash collision does not mean the end of the world if your current security products use the SHA-1 hashing algorithm. Just because a hash collision is found doesn't necessarily mean hackers can start exploiting this. Not only does it still requires a massive amount of computing fire power to find a single hash collision but more importantly; finding a hash collision doesn't necessarily mean that a hacker has something useful.
For example: If a legal contract was digitally signed using SHA-1, the fact that you can produce a hash collision doesn't mean you have the ability to generate an arbitrary contract that conflicts with the original contract. Just because you have a blob of data that happens to have an identical SHA-1 hash isn't the same as being able to produce a different legal contract that calls the original contract in to question. That blog you produce will most likely not even be a legible computer document by any sense of the imagination. That's not to say it couldn't ever be done, but it's certainly not trivial. So if John Doe had a prenuptial agreement with his wife that was digitally signed with SHA-1 and time stamped which stated that his wife only gets $10,000, the wife can't reasonably claim that because one SHA-1 hash collision was found by professor Wang that the original prenuptial agreement was actually a forgery. She certainly won't be able to produce another prenuptial document that showed that she was suppose to get $1,000,000 which has an identical SHA-1 hash. The science of finger print forensics or even genetic DNA matching is far less reliable than SHA-1 hashing but perfectly legitimate in the courts.
The problem is that lawyers can certainly try to use the argument that SHA-1 is flawed and juries and even courts have proven to be extremely gullible in the past regardless of what science says. Take the infamous case of the "MD5 defense". A Sydney Magistrate threw out the digitally time stamped photos in a speeding ticket case because the Roads and Traffic authority failed to produce an expert to testify that its speed camera images were secure. The motorist's defense lawyer took advantage of the courts ignorance and argued that the MD5 hashing algorithm was a discredited piece of technology and therefore the speeding photos were invalid. Never mind that the defense never proved any actual tampering by the police department or explained how hash collisions in MD5 could possibly be used to fake photographs, it didn't matter because the judge was ignorant and the traffic authority was incompetent in their prosecution of the case. We lock people away for life with photographs and audio recordings all the time that have NO digital signatures but because a piece of police evidence used a less than perfect MD5 hashing algorithm in the digital signature the entire case was thrown out. With SHA-1 being officially cracked by Chinese researchers, the "MD5 defense" just became the MD5/SHA-1 defense.
It would be interesting how lawyers view this case and I'm going to ask some of them what they think in terms of the legal ramifications. There seems to be some legal precedent in Australia because of one stupid court room but I don't think that's supposed to affect the United States or any other country. The problem is that the US Supreme Court recently cited a foreign legal precedent though not without protest from Justice Scalia and other constitutionalists. Hopefully we can get some sanity back in to the legal system.
George Ou is Technical Director of ZDNet. See his full profile and disclosure of his industry affiliations.
