Cryptography for embedded systems - Part 1: Security level categories & hashing

People on both sides of the law (and with varying levels of ethics) are racing to discover flaws in the most commonly used algorithms. After all, boatloads of money can be made if a security breach is discovered. For the "good" guys, the rewards are recognition and (hopefully) prompt fixing of the issue. The "bad" guys profit in numerous different ways. The end result is always the same, however: If an algorithm is broken, it usually means it's useless from that point on.

This insane virtual arms race has revealed that it is extremely hard to develop secure cryptographic algorithms (it's easy to write broken cryptographic algorithms), and it appears that hashing may be among the most difficult. The two major hash algorithms in use today (notably by SSL and TLS) are MD5 and SHA-1. At the time of the writing of this text, MD5 is considered "mostly broken" and SHA-1 is "sorta broken." What does that mean? Well, there are various ways a hash algorithm could be broken from a cryptographic standpoint. Some of these are:

• Take two arbitrary but different messages and hash them. If you can easily calculate a hash value that is the same for these different messages (a "hash collision" ), then the algorithm is somewhat broken, and potentially seriously broken.

• Given a hash value, compute an arbitrary message to hash to that value. If this is easy, then the algorithm is a little more broken, since this starts to get into the area where the flaw can be exploited.

• Generate a meaningful message that generates a hash collision with another meaningful message. If this is easy, then the algorithm is mostly broken, and it is highly likely it provides no security whatsoever. If this is true for an algorithm, it is very easy to fool someone into accepting incorrect information (or worse, damaging information such as a virus or Trojan horse).

Each of the above levels of compromise is based on the idea that performing these operations on the algorithm is "hard" (infeasible given current technology and future technology for at least a few years). They all feed into one another as well, so if you can find an arbitrary hash collision, it is often easier to discover the other attacks.

Unfortunately, both MD5 and SHA-1 have been discovered to have vulnerabilities. For MD5 there are several demonstrations of ways to generate different meaningful messages that generate the same MD5 hash value. Granted, these operations are currently somewhat contrived and generally a little tricky, but it is only a matter of time until someone figures out how to do it fast and easy. Generally speaking, we don't need to rush out and pull MD5 out of all our applications, but if it isn't too difficult to do so, it is recommended. MD5 should not be used in new applications whenever possible.

The MD5 algorithm is fairly broken, but fortunately for us (and the rest of the world), SHA-1 is not as broken (yet). Researchers have discovered something akin to the first vulnerability (the arbitrary hash collision) in SHA-1, but as yet, there does not seem to be a way to translate that vulnerability into a security breach (as seems to be the case with MD5). Possibly by the time you read this, however, both SHA-1 and MD5 will be considered obsolete and will be replaced by something new (or at least in the process of being replaced).

SHA-1 and MD5, albeit broken, are still in heavy use today and will continue to be for some time. They are so integrated into the security mechanisms that we have come to rely on that it will take years to pull them all out and replace them. Even then, many legacy systems may still require them in some capacity. This scenario obviously assumes there is a decent replacement. There are some contenders in the same family as SHA-1, but if that algorithm fails, it may be hard to tell if the SHA-1 vulnerabilities translate to its brethren.

One ray of hope, however, is that there may be another competition to develop a new cryptographic algorithm as was done with AES. Only this time, the target would be a hashing algorithm to replace the aging and ailing MD5 and the slightly less damaged SHA-1. Only time will tell what ends up happening with this. Heck, we might see a quantum computer implemented in the next few years that could make all of our current strategies obsolete overnight. We still need something in the meantime, however, and it worked for AES, so it may work for this too.

Coming up in Part 2: To Optimize or Not to Optimize...

Printed with permission from Newnes, a division of Elsevier. Copyright 2008. "Wireless Security: Know it All" by Praphul Chandra, Alan Bensky et al. For more information about this title and other similar books, please visit www.elsevierdirect.com.

Related links:
Practical Embedded Security - Part 1: PPP, Ethernet and ARP | Part 2: Transport and Internet Layer Protocols | Part 3: Wireless technologies
What you need to know about embedded systems security
Fundamentals of Embedded Systems Security
Security Protocols for the Embedded Internet
Implementing secure digital data transfer in portable handheld embedded devices: Part 1 | Part 2 | Part 3