Hash Functions, Their Performance, and HMACs

Other widely used hash functions include 128-bit MD5 from RSA Data Security, Inc., which is a very fast and commonly implemented hash. MD5 is traditionally used to encrypt Linux user passwords (hashes start with the "$1$" character), authenticate routing protocols like RIPv2 and OSPF, create checksums of binaries in RPMs, and verify the integrity of Free/OpenBSD ports files. The specifications of MD5 are available in RFC 1321. Host intrusion detection tools like Tripwire (http://www.tripwire.com) use MD5 to take snapshots of a system's files and preserve them in a database (which must be encrypted) to determine if any of the system's files were modified by crackers. A poor man's Tripwire is the md5sum command available on many UNIX-like systems. A predecessor of MD5, MD4 is very fast, but it was broken in October 1995. Unfortunately, MS-CHAP still uses MD4 hashes even in its second version, and protocols such as 802.1x EAP-LEAP that rely on MS-CHAP can be vulnerable to attacks against MD4. Since 1995, there have been serious doubts about the security of MD5 and other 128-bit cryptographic hash ciphers, and the use of at least 160-bit hashes is recommended. You can check the security of your MD5 hashes using the MD5Crack tool, available for download from http://www.checksum.org/download/MD5Crack (this is the compiled Windows version of the tool; UNIX source code can be downloaded from http://www.packetstormsecurity.org).

Apart from SHA-1 and higher, there are other reasonably secure cryptographic hash ciphers to use, including HAVAL (variable-length hash values), RIPEMD, and Tiger. RIPEMD from the EU project Race Integrity Primitives Evaluation (RIPE) consists of two parallel MD5 processes running for five rounds and producing a 160-bit hash. RIPEMD is considered as secure as SHA-1 and is used by Nessus in conjunction with Twofish. Tiger was designed by the Serpent development team and is optimized to run on 64-bit chips, on which it is approximately 2.8 times faster than RIPEMD and 2.5 times faster than SHA-1. Tiger produces a 192-bit hash, although less-secure 128- and 160-bit variants of this cipher do exist.

Common block symmetric ciphers can also be used as the one-way hashes with few exceptions (e.g., Blowfish). In fact, being able to implement a symmetric cipher as a cryptographic hash was one of the conditions an AES candidate had to meet. Knowing how cryptographic hashes work, it is easy to see that there is nothing supernatural about using a block symmetric cipher in such a role: Supply a constant, use the input data to generate subkeys, and run. However, there is no reason to use AES or MARS, and so on, as a one-way hash when well-designed specific cryptographic hash algorithms like SHA exist.

Cryptographic hash ciphers are designed to quickly process large quantities of data; for example, to hash data and append hashes to packet headers on the fly as the packets are sent over the network. The processing rate of cryptographic hash ciphers in MB/sec is generally comparable to the processing rate of stream ciphers such as RC4 and is 1.5 to 2 times above the processing rate of AES. Obviously, there is a performance penalty for using more secure, larger hashes, and MD5 would have a higher data throughput than Tiger (on 32-bit CPUs) or SHA-1.

Cryptographic hashes are fine to sustain data integrity via data fingerprinting or to identify users against databases of hashed passwords. However, by themselves they do not authenticate the data itself; the attacker can alter the original data before hashing takes place. One possible solution for this problem is using a HMAC, also called a keyed message digest. A HMAC is nothing more than a cryptographic hash and shared secret key combined. Thus, the data gets encrypted before it is hashed, and the attacker would have to break the symmetric cipher key after generating the original message from the hash or break the symmetric cipher key if he or she has access to data before hashing takes place. An example of message authentication code specifically designed for improving wireless security is Michael (MIC).

MIC: Weaker But Faster

The main problem encountered in the design of MIC was developing a HMAC that would run on legacy hardware without imposing significant penalties on network throughput and latency. The client hosts can offload the HMAC computation to the sufficiently powerful laptop or even PDA CPU, even though it is still undesirable! What if a company decides to design and manufacture a tiny 802.11-enabled mobile phone? Besides, many access points do not boast high processing power. Yet, the AP or a wireless bridge should be able to verify both integrity and authenticity of the bypassing packets. Recall the structure of SHA with its 80 iteration rounds and imagine generating such a hash for every packet sent over the wireless network. Would a common access point or a PDA be able to implement that process without significant resource exhaustion? Not very likely!

Thus, an entirely new algorithm called MIC was designed by Niels Ferguson to provide packet integrity checking and forgery detection on TKIP-enabled WLANs. It was designed as a third attempt, after two previous designs called Mickey and Michelle. MIC is a trade-off between security and resource consumption and implementation capability. It runs on older wireless access points and client hardware without imposing a significant performance penalty, but the security level it provides is only 20 bits. As you should understand by now, in modern cryptographic terms this is not a lot.

Before discussing the trade-off and its practical outcome possibilities, learning how MIC works is helpful. The MIC secret key consists of 64 bits and is represented as an 8-byte sequence k₀...k₇. This sequence is converted to two 32-bit little-Endian words, K₀ and K₁. Throughout the MIC design, all conversions between bytes and 32-bit words use the Little-Endian conventions, because the cipher is expected to run on Little-Endian CPUs. In fact, the majority of access points now manufactured use older Intel line chips such as i386 or i486.

MIC operates on the data field, as well as source and destination address fields of the wireless frame. The integrity of IVs is not protected and the data field is not interpreted. Before the cipher runs, the frame is padded at the end with a single byte (value 0x5a), followed by 4 to 7 zero bytes. The number of zero bytes is selected to ensure that the overall length of the padded frame is always a multiple of four. The padding is never transmitted with the frame; it is used only to simplify the computation over the final block. After the padding, the frame is converted into a sequence of 32-bit words M₀...M_N-1, where N = [(n+5)/4]. By design, M_N-1 = 0 and M_N-2 != 0.

The MIC value is computed starting with the key value and applying a block function b for every message word. The cipher loop runs a total of N times (i includes 0 to N-1 values), where N is the number of 32-bit words making up the padded frame. The algorithm produces two words (l,r), which are converted into a sequence of eight Little-Endian octets, the MIC value:

Input: Key (K0, K1) and padded frame (represented as 32-bit words) M0...MN Output: MIC

 value (V0, V1)



MIC <= ((K 0, K1) , (M0,...,MN))

   (l,r) <=(K0, K1)

   for i = 0 to N-1 do

         l <= l ^= Mi

         (l,r) <= b(l,r)

return (l,r)

The MIC value is appended to the frame as data to be sent.

The block function b used by MIC is a tiny Feistel algorithm that employs alternating additions and XORing. The <<<>>> indicates right rotation of 32-bit values, and XSWAP is a function that exchanges the position of the two least significant bytes with the position of the two most significant bytes in a word:

Input: (l,r)

Output: (l,r)

b(L,R) 35



r <= r ^= (l <<< 17)

l <= (l + r) mod 232

r <= r ^= XSWAP(l)

l <= (l + r) mod 232

r <= r ^= (l <<< 3)

l <= (l + r) mod 232

r <= r ^= (l >>> 2)

l <= (l + r) mod 232

return (l, r)

As you can see, the cipher is neither sophisticated nor strong. It was estimated that an attacker has one chance in a million of sneaking in a frame with a compromised payload but correct MIC. One might argue that significant damage can be done by inserting a single modified frame after 1 million frames sent. However, the old WEP ICV (CRC-32) is still used as well, and has to be faked together with MIC. Thus, such attacks are neither easy nor have a high probability of success. Nevertheless, to mitigate their success the so-called TKIP countermeasures were introduced. When more than a single forgery attempt in a second has been detected, the host deletes the groupwise or pairwise key (depending on whenever a unicast or multicast frame was affected), deassociates, and waits for a minute before the reassociation. Thus, the possibility of an evil Joe Cracker sending a few million modified frames to sneak in a few of them undetected is eliminated.

However, the same Joe Cracker might turn desperate and try to send forged frames to trigger the countermeasures and cause a DoS attack, employing not a bug, but a feature. The possibility of such DoS attacks introduced by a new security feature was widely argued. The best example of such discussion is a thread at the Cryptography mail list (http://www.mail-archive.com/cryptography@wasabisystems.com/msg03070.html is the first message in a thread). In this thread Niels Ferguson, the creator of MIC, answers questions considering the possibility of a DoS attack abusing MIC countermeasures. Despite the hullabaloo around the likelihood of this DoS attack and the countermeasures' imperfections, such an attack might not be as realistic and easy to launch as many would think. Remember that the TSC will drop all out-of-sequence frames; the attacker thus has to send a frame with a "future," yet unused, IV. However, recall that the IV is actively used by the TKIP per-packet key generation function. If the IV is changed, the frame will not be decrypted correctly. Because the CRC-32 is still there, it would not give a proper value, leading to the forged frame being eventually dropped. Thus, the attacker has to sniff out valid frames, delete them to prevent them from reaching the receiver, corrupt the MIC, recalculate the CRC-32 to reflect the changes in MIC, and only then forward the "MIC-of-Death" frames to the target (desirably every 59 seconds). Although possible, it is by no means an easy task.

Because the final 802.11i release-compatible hardware will have to be optimized for running AES, using a CBC-MAC HMAC implementing AES as a one-way hash would be more practical and secure than employing some form of MIC or a well-known message digest like SHA. It will also remove all possible problems with MIC just discussed. Thus, in some specific cases, it could be preferable to use symmetric block ciphers for data integrity preservation as well as for data encryption and message authentication.