# Cost of attacking Mobile OTP with a fake server

You want to obtain a 74-bit secret $K$. There is an oracle that will provide you with the following value for several values of $T$:

$$(\mathrm{MD5}(T_{\mathrm{dec}}||K_{\mathrm{hex}}))_{\mathrm{hex}}[0..5]$$

• $T_{\mathrm{dec}}$ is the number of seconds since 1970 divided by 10 (i.e. it's the current time in units of 10s), written out in decimal notation and encoded into bytes in ASCII;
• $K_{\mathrm{hex}}$ is $K$ written out in hexadecimal notation and encoded into bytes in ASCII;
• $x_{\mathrm{hex}}[0..n-1]$ means the first $n$ hexadecimal digits of $x$.

In other words, the oracle provides the first 6 digits of the MD5 hash of a time-dependent string concatenated with the secret.

The practical application is that you are impersonating a mobile OTP server, and the oracle is a client tricked into attempting to authenticate with you. $K$ is the client secret (in-device secret plus user PIN) which you are trying to obtain. And this question is inspired by Mobile OTP - Secure? on Security Stack Exchange.

Since each value from the oracle provides 24 bits, with $4$ values from the oracle, you should have enough information to brute-force $K$. (Assume $T$ is perfectly known, i.e. your clock is synchronized with the client's, but can't influence it.) The cost of a brute-force search is $2^{74}$ MD5 computations.

Are there known weaknesses that make finding $K$ less expensive? (We're taking the MD5 hash of several strings with a common prefix and a common suffix.) Would more values from the oracle help?

-
If MD5 was a random oracle, 4 outputs would have approximately a 1/4194305 probability of not determining $K$. $\:$ Since MD5 is not a random oracle, I imagine the actual probability will be slightly greater than that. $\;\;$ –  Ricky Demer Mar 2 '12 at 3:19

If $\mathrm{MD5}$ had been computationally indistinguishable from a random oracle (for the fixed message size under consideration), there would demonstrably be no method better than brute force search of $K$ to recover $K$ or otherwise predict the next outputs of the function.

However, $\mathrm{MD5}$ is known to fall short of this goal. In particular, we know how to quickly make 1-block collisions, and there is a theoretical preimage attack slightly better than brute force.

Thus there is no insurance that the function described is secure, but I do not see that any current result on $\mathrm{MD5}$ endangers it. Perhaps there is a differential attack of some kind with enough $(\mathrm{T}, (\mathrm{MD5}(T_{\mathrm{dec}}||K_{\mathrm{hex}}))_{\mathrm{hex}}[0..5])$ pairs, but I do not see that as a practical threat even with thousands on pairs, in light of the short key $\mathrm{K}$.

On the other hand there are several truly worrying aspects of the scheme:

• there is no salt (the same $\mathrm{K}$ and $\mathrm{T}$ yield the same cryptogram regardless of user or other parameter);
• there is no other attempt to slow down brute force search;
• the 74-bit key is short.

These three cardinal errors combined make the scheme quite vulnerable to a brute-force attack. Assuming $n$ users have used their authenticating device at the same known time $\mathrm{T}$ once, and have used it at three other known times (not necessarily the same among users), and the cryptograms have been gathered, the key of one user is recovered with better than 50% odds, and fair confidence against false positive, after an effort of $0.7 \cdot 2^{74}/n$ $\mathrm{MD5}$ rounds. That's simply by trying keys for the common $\mathrm{T}$ and, in the rare case that the result is a match for a user, further testing the key with other known data points for this user.

Also, the key generation is not specified here. If the key was not true random but, say, a password, or generated by a poorly seeded RNG, that would be a further weakness. Update: We learn that $K$ consists of 64 bits chosen at random, plus 10 bits from a 4-digit $\mathrm{PIN}$. If the users choose their $\mathrm{PIN}$, then $0000$, other $\mathrm{PIN}$s with 4 identical digits, and birth years, are going to be strongly overrepresented. That can be used to speed up a brute-force attack, significantly.

Rather than this scheme, it would be better to use industry standard primitives fit for the job, like $\mathrm{PBKDF2}$ or, better, $\mathrm{Scrypt}$. At the very least, the user ID or some form of salt should be part of the cryptogram's input.

Update: For example, with $\mathrm{PBKDF2}$ and keeping $\mathrm{MD5}$ as the underlying primitive, the function generating the one-time password could be replaced with $\mathrm{PBKDF2}(\mathrm{PRF}\leftarrow\mathrm{HMAC\_MD5}, \mathrm{Password}\leftarrow K||\mathrm{PIN}, \mathrm{Salt}\leftarrow\mathrm{UserID}, \mathrm{Count}\leftarrow 512, dkLen\leftarrow 3 \mathrm{bytes})$

Rationale: Using $\mathrm{Salt}$ (e.g. a User ID) insures that a brute force attack can not be leveraged against multiple users, avoiding the $/n$ factor above. The $\mathrm{Count}$ parameter is a compromise between increasing the effective key length (doubling $\mathrm{Count}$ has the same effect on a brute force attack as growing $K$ by one bit), and the computational cost of an authentication (growing linearly with $\mathrm{Count}$ on both the device and server side). With the given parameters, assuming 1000 users in the same 10 seconds, the scheme is about a million times harder to break than the original. Using $\mathrm{HMAC}$ increases assurance against theoretical attacks, even though $\mathrm{MD5}$ is less than perfect.

-
I might have oversimplified my presentation a bit; this is a one-time password scheme, and $K$ consists of 64 bits chosen at random and (in many use cases) stored in a tamper-resistant device plus 10 bits from a 4-digit PIN. It is meant to resist online attacks, $K$ is a shared secret between the client and the server and no security is expected in case of a server leak. In light of this, where would an attempt to slow brute force search or a salt fit in? How do you get from a key strengthening function like PBKDF2 to an OTP scheme? –  Gilles Mar 2 '12 at 11:34
@Gilles: I updated the answer to explain how the PIN might weaken the scheme against brute force; and how PBKDF2 could be used to construct a much better One Time Password scheme. That might need adaptation to match what existing tamper-resistant hardware accepts to perform. Again, the single most important thing is to add salt somewhere in the input of the cryptogram! –  fgrieu Mar 2 '12 at 14:46

Given that the 64 bit secret and 10 bit PIN are truly random, we are talking about brute forcing 2^74 MD5s (and we will have to do this multiple times, as each 6 digit one time password intercepted will have billions of collissions). Given a fast hardware that can do 200 Million MD5s per second, each one time password and each round will take 3 Million years to find the collissions. How many rounds will we need? Do we have enough time?

To make a point: Choose a good PIN. If you are overly halfhearted, then choose the 128 bit secret. In any case Mobile-OTP will be one of the strongest elements of your overall security design.

-
Welcome to crypto :) Just a quick note - if you ever need to add additional detail to an answer, there's an edit link underneath you can use at any time. Do feel free to use this to provide additional detail/clarifications/improvements, rather than adding comments :) –  Ninefingers Mar 22 '12 at 12:09