Next: Credits Up: Crypto.Hash: Hash Functions Previous: Crypto.Hash: Hash Functions Contents
Hashing algorithms are broken by developing an algorithm to compute a string that produces a given hash value, or to find two messages that produce the same hash value. Consider an example where Alice and Bob are using digital signatures to sign a contract. Alice computes the hash value of the text of the contract and signs the hash value with her private key. Bob could then compute a different contract that has the same hash value, and it would appear that Alice signed that bogus contract; she'd have no way to prove otherwise. Finding such a message by brute force takes pow(2, b-1) operations, where the hash function produces b-bit hashes.
If Bob can only find two messages with the same hash value but can't choose the resulting hash value, he can look for two messages with different meanings, such as "I will mow Bob's lawn for 7#71,000,000", and ask Alice to sign the first, innocuous contract. This attack is easier for Bob, since finding two such messages by brute force will take pow(2, b/2) operations on average. However, Alice can protect herself by changing the protocol; she can simply append a random string to the contract before hashing and signing it; the random string can then be kept with the signature.
None of the algorithms implemented here have been completely broken. There are no attacks on MD2, but it's rather slow at 1250 K/sec. MD4 is faster at 44,500 K/sec but there have been some partial attacks on it. MD4 makes three iterations of a basic mixing operation; two of the three rounds have been cryptanalyzed, but the attack can't be extended to the full algorithm. MD5 is a strengthened version of MD4 with four rounds; an attack against one round has been found XXX update this. MD5 is still believed secure at the moment, but people are gravitating toward using SHA1 in new software because there are no known attacks against SHA1. The MD5 implementation is moderately well-optimized and thus faster on x86 processors, running at 35,500 K/sec. MD5 may even be faster than MD4, depending on the processor and compiler you use.
All the MDn algorithms produce 128-bit hashes; SHA1 produces a larger 160-bit hash, and there are no known attacks against it. The first version of SHA had a weakness which was later corrected; the code used here implements the second, corrected, version. It operates at 21,000 K/sec. SHA256 is about as half as fast as SHA1. RIPEMD has a 160-bit output, the same output size as SHA1, and operates at 17,600 K/sec.