The Unreliability of MD5-based OTPs

An integral part of generating the one-time passwords commonly used for two-factor authentication is computing an HMAC of the token secret and counter values¹. Any cryptographic hash function can be used in computing the HMAC², so in developing the Authenticator app, I included support for four common hash functions: SHA-1, SHA-256, SHA-512, and MD5. On close examination, however, it becomes clear that MD5 cannot be used to consistently produce valid one-time passwords.

Neither of the RFCs which define the common one-time password algorithms mentions MD5 as a possible hash function; the HOTP RFC specifically uses SHA-1³, and the TOTP RFC adds the option to use SHA-256 or SHA-512⁴. While not explicitly mentioned in the OTP specificactions, MD5 is one of the algorithm options supported by the Google-designed OTP key URI format, and since Authenticator was originally designed as an open-source replacement for Google’s own authenticator app, it seemed important to support MD5 as an option.

The Problem

The source of the problem is the length of the hash produced by MD5. At 16 bytes, it is shorter than the hash values produced by any of the SHA hash functions. Because of the way the one-time password algorithm derives a password from the hash, it is possible for a password to be extracted from memory that lies outside of an MD5 hash.

As described in RFC 4226, the HOTP algorithm first computes a hash from the secret and counter values, and then extracts a four-byte segment of the hash value to use as the basis for the password. The choice of which four bytes to extract is made by casting the last four bits of the hash as an integer and using that integer value as an offset into the hash. Starting at this offset, the next four bytes are read from the hash and used in further computation to produce the password.

Because the offset integer is specified by only four bits, it must be one of the integer values that can be represented in four bits, in the range [0, 15]. This is a problem when the hash function used is MD5, because the length of its hash is 16 bytes. If the offset integer is 13 or greater, part of the four bytes extracted will extend beyond the end of the hash, reading from memory not produced by the hash function. Depending on the contents of this memory, the passwords produced will be inconsistent and unreliable.

An Example

Consider the OTP token represented by this URL:

otpauth://hotp/MD5?algorithm=MD5&secret=AEAAAAA&counter=1

The hash value is computed as follows:

secret = <01000000>
counter = <00000000 00000001>
hash = HMAC-MD5(secret, counter)

The hash value produced is:

<650c4bfb 740d273d 51d51866 a874b2ae>

When broken down by byte as is done in the RFC:

Byte Number  00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
            -------------------------------------------------
Hash Value   65 0c 4b fb 74 0d 27 3d 51 d5 18 66 a8 74 b2 ae 

The last four bits of the hash are represented by the final hexidecimal character (“e”) and produce an offset value of 14. As is clear from the byte table above, selecting four bytes from the 16-byte hash starting at byte 14 would overrun the end of the hash, producing a truncated value of b2 ae ?? ?? where the “?” characters represent nondeterministic and invalid bits.

No More MD5

Because of the flaw described below, I am removing support for MD5-based one-time passwords from Authenticator. I haven’t encountered any web sites which actually use MD5-based OTPs, and any website which has tried likely noticed how unreliable the OTPs were. For this reason – among others – I’d suggest that any other developers dealing with one-time passwords avoid using – or even supporting – MD5.