A few days ago at EuroCrypt 2009, security researchers announced an attack on the SHA-1 hashing algorithm. The attack is a fairly serious one and it is a strong signal for software vendors to move away from SHA-1.
For almost all cryptographic algorithms, if the digest length is n, it means that there are 2n different possible values for the message digest (cipher text in the case of an encryption algorithm). Taking the possibility of birthday attacks into account, we can safely assume that breaking these digests will take at least 2n/2 operations.
If n = 160 (as in the case of SHA-1), it will take 280 calculations to break the code. Even if we assume that a computer can do 220 operations per second, it will take a whopping 36 billion years to crack the code. Our secrets and systems are kept secure by these algorithms which are supposed to resist the best computers for 36 billion years from cracking code.
Then someone very smart comes along, finds a weakness in the algorithm itself rather than trying to do brute force attack, and the security of our documents, signatures and protocols are jeopardized. We are forced to find better alternatives and design better algorithms.
In the real world, cryptographic algorithms become obsolete or broken in 10-25 years rather than the theoretical time frame of 36 billion years.
As a precautionary step you may want to make the algorithms/protocols used in your application easily replaceable. This will make your life easier when the algorithm is broken and you want to replace it. Also, as a programmer you should understand that even if the algorithm is not yet broken, your implementation may be flawed. Most of the security vulnerabilities are caused by crappy implementations of secure algorithms/protocols.
And did I mention that you should not write your own encryption algorithm?
Of course in the real world things are entirely different:
As you probably know, none of the algorithms in the world will help you if I know your mother’s maiden name.
SHA-1 has been considered broken ever since the SHA-0 attack several years ago.
And the XKCD comic is fairly stupid; I mean it’s clearly a joke and ignores the real world, everyday, totally valid uses of encryption.
The “make your algorithms replaceable” approach has two edges.
On one hand it means that your software and protocols can outlast the algorithm (so you’re creating software intended to be functional and secure in 10-25 years time without modifying its protocols and/or data formats in that time).
On the other hand the pluggable algorithm approach introduces a completely new class of errors and insecurity:
- You introduce an additional layer of abstraction that must be coded securely, increasing the footprint of highly trusted code.
- Is the protocol negotiation secure with respect to algorithm choice, or can an attacker force the use of a weak algorithm, defeating the entire point of pluggable algorithms?
- Can the attacker mix & match algorithms (e.g. use the same RSA keypair with SHA1, SHA256 and SHA512)? This can provide a way to extract sensitive information from the system.
- Deciding what algorithm(s) to use is always a trade-off. This approach moves part of the trade-off decision from the developer to the end-user, but most end-users are completely unable to take an appropriate decision.
It is also well-worth noting that SHA-1 was never meant to be secure for “36 billion years”. If you take a look at NIST SP800-57 you will see that a 160-bit hash function has 80 bits of security in digital signatures and hash-only applications, and should only be used for a security lifetime ending in 2010! Applied cryptographers have long considered 80 bits of security to be insufficient for long-term (10-20 years) security.
NISTs computations take into account the current state of the art (approx. 2^54 computations per second on dedicated hardware by a hostile adversary with government-level resources), Moore’s law, historical rate of breakthroughs in algorithm or number analysis, and other factors.