The algorithm is trivial. [...]
*Sigh* ... I should have been more specific. I should have said "Find
an algorithm that you can actually *execute* in your lifetime". Of
course, this is the whole point -- yes an algorithm exists, but very
specifically it is supposed to take longer than anyone's lifetime on
the biggest computer network, etc., etc and the claim of its security
is that you cannot do better than that.
OTOH, tokens sold only a few years ago clearly did *not* meet this
criteria. BTW, my token design, except for the excessively short DES
key is perfectly valid - and if you did triple-DES instead, it would
make a fine token.
[...] Whether it's practical or not is a
different issue. Consider a simple security token that just runs DES
in CTR mode against the timestamp value.
Well ok dude, you can't make it *that* easy on yourself. I would
expect, in fact, that they use something better than DES 56 and of
course they can't have all the client generators outputting the same
numbers, so they probably don't just run in counter mode, but insert a
prefix or suffix that uniquely identifies each one.
Actually the approach is to set a different key on each token. And
you can seed the 32 bit counter with any value you want, the sever
that authenticates these just needs to keep track of both values. So
two token don't generate the same sequence even if they used the same
timebase.
You skipped over the point where you had to actually deduce the key
from the final output -- something that's inordinately difficult if
you are reseeding at a rate higher than half the period of a long
period PRNG like the Mersenne Twister. I assume there is an approach,
but nothing comes to mind.
OK, we were talking about tokens, but...
Finding the actual key (or at least the current internal state, which
is close enough) is trivial for the brute force algorithm. In the
case of the example token, it just requires five consecutive samples
(or actually any five with known spacing). Just look at how the EFF
DES Cracker worked. For simplicity of discussion, assume the five
samples are consecutive. You iterate through all 2**88 possible
states to see if they produce the first 20-bit output. About one in a
million attempts will pass. Any that do pass you just tests states (n
+1), (n+2), (n+3) and (n+4) to see if the output from those states
matches the subsequent samples.
But reseeding occasionally does not deal with the theoretical problem
(although for MT brute force would be impractically slow by any
standard). Some 624 generated 32 bit random numbers is enough to
deduce the exact state with very high probability. And reseeding MT
that often is impractical. And since MT is not considered
cryptographically secure, I assume there's a *much* easier way to back
out the state from the 624 outputs. Many things that have been used
for random number generation can been reversed fairly easily, and with
drastically less output than their period - LFSRs are a favorite - you
need only a couple times as many output bits as the state (IOW twice
the length of the shift register or 2n, despite the period being
2**n-1) and they're easy to reverse. And even a function you hope is
cryptographically secure can turn out otherwise - again the original
RSA SecurID tokens* come to mind. And there have been numerous attack
on PRNGs - the famous crack of Netscape's SSL implementation (way back
in 95 or 96) was due to a flawed PNRG implementation. And just
because you can’t reverse your generator today, doesn’t mean you
couldn’t do it tomorrow.
I think the point is that it’s best not to assume that your "random"
data has any more entropy that you actually fed into it.
*Admittedly it's not a perfect attack, but with two months worth of
outputs (about 100,000), you have about a 10% chance of cracking the
Alleged SecurID Hash Function with 2**40 work.
)))