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.
