Lab Notes

Bruce Schneier is reporting that a research team has broken SHA-1. This is big news in the world of cryptography. Here's why:

SHA-1 is a hash function. Hash functions, along with cipher algorithms (like DES, RC4, AES, et. al.) and public key algorithms (e.g., RSA, Diffie-Hellman, DSA), are one of the building blocks of modern cryptographic protocols. Hash functions are used to compute a "fingerprint" of a block of data. In a typical crypto protocol, one party uses a hash function to generate a fingerprint of a given chunk of data, digitally signs that fingerprint, then transmits the data and the fingerprint to a second party. The second party takes the chunk of data, and runs the same hash function to generate its own fingerprint. By comparing the two fingerprints, the receiving party can tell whether or not the data has been altered in transit.

To be considered secure for cryptographic use, a hash function must possess two main properties:

• It must be one-way: Given a chunk of data, it must be possible to generate a fingerprint, but given the fingerprint, it must not be possible to generate the data. That is, the hash function is not reversible. If an attacker has access to the fingerprint but not the data chunk, the fingerprint alone should not give any hint as to the contents of the data chunk.
• It must not have collisions: The hash function must always generate the same fingerprint for the same chunk of data, and always generate different fingerprints for different chunks of data. If a slight change is made in the data being fingerprinted, it must result in a completely different fingerprint. Further, it must be infeasible to find two different chunks of data that result in the same fingerprint.

It is with the second property, collision resistance, that SHA-1 has been found lacking. The new attack can find a collision in 2^69 tries, compared with the 2^80 tries that were necessary before this attack was developed. That may not seem like much of a breakthrough, but keep in mind that for each power of 2 you can knock off the running time, you make an attack twice as easy. It would still take either a lot of computing power or a lot of time to find a coliision, but by moving from 2^80 to 2^69, an attack on SHA-1 went from being impractical for everyone to being practical for quite a few organizations. Another thing to keep in mind is that attacks like the one on SHA-1 frequently improve in their effectiveness as more research is performed and the attack is optimized.

The problem is further exacerbated by the fact that hash functions play a critical role in digital signatures, and digital signatures must be strong for years. For instance, many certificate authorities have used SHA-1 in their root certificates, and some of these certificates are valid for decades. If one of these roots is compromised, then every digital certificate signed by one of these roots is compromised.

SHA-1 is the current standard hash function in just about every crypto protocol in widespread use. Coming on the heels of the MD5 attack of last year, this leaves us with no widely deployed hash function that hasn't been proven weak. MD2, MD4, MD5, SHA-0, HAVAL, and RIPEMD-160 all suffer from flaws. SHA-1's successors, SHA-256, SHA-384, and SHA-512 have no major attacks on them, but neither have they been widely deployed nor have they been as scrutinized as the other hash functions.

So how does this relate to Wi-Fi security like WPA Enterprise? Hash functions are used in several places in the protocol:

• At the RADIUS level, the response authenticator, which proves that the RADIUS packet has not been tampered with, uses MD5. However, the Message-Authenticator attribute, which performs the same function for EAP-based RADIUS authentication (like that in WPA Enterprise), uses HMAC-MD5, a keyed hash function that is not currently vulnerable to attack.
• TLS records are hashed using HMAC-SHA1, which, according to the Schneier article, is not vulnerable.
• TLS session keys are derived using a combination of HMAC-SHA1 and HMAC-MD5, so again, not vulnerable.
• Servers are authenticated using digital certificates that incorporate a hash function in their digital signature. This is the primary vulnerability with regards to Wi-Fi security.
• For EAP-TLS, where clients authenticate themselves using a digital certificate, their certificate is vulnerable in the same manner as the server's. During the TLS handshake the client proves that it hold the private key associated with its certificate by signing SHA-1 and MD5 hashes of the TLS handshake messages. This is not a concern for the immediate future, as it would require both hashes to be breakable in real time.
• Finally, the password protocols use hash functions: CHAP and EAP-MD5-Challenge use MD5, while MS-CHAP-V2 uses MD4. These are encrypted inside the TLS channel, greatly diminishing their vulnerability to attack.

Right now, there is precious little detail about the nature of the new SHA-1 attack, but you can expect to start seeing major changes in crypto protocols in the near future in response to it. After the MD5 attack was published last year, those of us in the crypto community took a lot of comfort in knowing that MD5 was already being phased out and that SHA-1 was a viable replacement. With this new attack, there is no immediate replacement, and crypto products are going to require re-engineering.