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  $\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.