They got the first 103 keys with batch GCD. After that, they found many more keys by looking at patterns in the keys and doing trial division by keys that were similar to the patterns. A better PRNG would make that harder (to reverse-engineer the patterns in the seed) and a slower PRNG makes it slower.
Yeah that might have been an exaggeration. But as I recall, once you have the MT seeded and fired up, getting a new number requires little more than a bit shift. Anyway it was substantially faster than simple alternatives I tried (including other PRNGs). One early theory I had was that using a faster PRNG than MT could lead to a better result even if it wasn't as evenly distributed. I think MT proved to be the best solution though.
A better (i.e., not completely utterly horribly broken) PRNG would have made it impossible to observe and associate patterns in the output, even with poorly seeded entropy. There's no reason such a PRNG needs to be any slower than a fast cipher or hash function such as AES or SHA-2.
"The length of time that Dual_EC_DRBG takes can be seen as a virtue: it also slows down an attacker trying to guess the seed."
If a system's seed is weak, one attack is to try all likely seeds, run them through the PRNG to generate keys, and see if any of the keys work. A slow PRNG indeed slows down this process.
For instance, it would have slowed down the attack on the Taiwan Cryptocards, which exploited patterns in the seed that appear directly in the key, reported here: http://smartfacts.cr.yp.to/smartfacts-20130916.pdf
I'm not 100% sure if that was tongue-in-cheek or not, so I'll clarify: I was disagreeing with aortega. This is not a typical PRNG, where the seed generally marks the initial point of the same sequence. Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. It is akin to running a block cipher in OFB mode with a different key each time.
What they are doing modulo 2^32 + 15 is IMO the simplest way to achieve that goal. Yes, you could do it without overflowing 2^32 using a binary field; you could also cook your own mini block-cipher. But that increases the complexity of the code and is not really faster everywhere.
The point is, you can be handed 1) the entire source code of the PRNG, and 2) six outputs from it, and it's impossible to know what the starting state of the PRNG was because six outputs could have come from many different starting states. You could brute force every single starting state and find every one that would produce those 6 outputs but it still doesn't let you know the next value.
Did you misread my statement as saying hashing the output will magically give another 80 bits of entropy? No, I'm saying to get another 80 bits before your PRNG repeats. I know you can infer things like linear congruential generators. I implemented such an inference program in grad school from someone else's thesis, then demoed it on a crypto USENET newsgroup. The hash is going to make inferring the seed much harder. Using a cryptographic PRNG will make even the unhashed output hard to infer. Using both is going to be way beyond the ability of most attackers.
Because PRNG constructions tend to run the whole key schedule when they refresh their state; for instance, CTR_DRBG uses inputs to derive a nonce and a whole new key.
> If you have enough entropy to fill a high entropy RNG, why not use all that entropy to generate the output in the first place?
Problem is the entropy generation rate. PRNG even with large space typically is running at 10 or better Gbit/sec. PCG with 256/64bit could generate decent numbers at 50Gbit/sec
All PRNGs all just repeating sequences. Usually they are just longer and use clever math to generate the next term of the sequence instead of just storing it in array. But always it repeats itself eventually.
For Doom speed was more important than length of the sequence so they just made it a lookup table.
It seems to me that the only major issue here is using a seed which can be trivially brute forced. Even if you don't look around the expected server time in order to guess the seed more quickly, 32 bits is really not hard at all to brute force these days.
I don't believe the number of bits the PRNG can generate is an issue here since we only need to uniformly get a number between 1 and 52, though what may be questionable is the cycle length of the PRNG if it weren't using an easily brute forced seed.
I'm not entirely convinced the off-by-1 is substantial, nor the fact that the shuffle produces duplicate shuffles (I can't intuit a significant bias, so I may well be wrong here).
So to summarize: never seed a PRNG with a small and easily brute forced value.
I think the main advantage is that this RNG gives you the same results as a crypto-strong PRNG, but much faster. That said, I didn't see any benchmarks on their site.
Netscape was using a related method for seeing the PRNG to the one you mention, which was still a small enough space of possible seed values that when the resulting values were using in cryptography, an attacker could brute-force the seed.
Eh, the slowness comes come from it being based on group primitives normally reserved for public key crypto. In a sense, basing a PRNG on a general believed-hard problem is nicer than on a believed-hard instance of bit shufflings, so the idea does have merit despite low adoption due to performance.
What I have to wonder is the implications for all of the other random generators.. The NSA has been studying symmetric crypto far longer and far harder than the public. Symmetric crypto is both sufficient for state security (hierarchal+opsec), and breaking it is sufficient to snoop on the public's communications (the bulk encryption and PRNGs).
On the other hand, academics love neatly defined problems, so their interest is heavily skewed towards studying asymmetric crypto where foundations of open mathematical problems and implementations based on nice closed-form number theory.
The same backdooring approach may have been applied to other NIST generators (which would be sufficient for the NSA to preserve its dragnet snooping and still secure against other attackers), and we simply don't have the analytical tools to see this (what is the entropy diminishment of a nothing-up-my-sleeve-number when the explanation is chosen a posteriori?). Dual_DC_DRBG comes across as so ham-fisted only because we have the ability to analyze it.
Something about using a PRNG with a large internal state just to generate an output in a large space of possibilities feels wrong to me. If you have enough entropy to fill a high entropy RNG, why not use all that entropy to generate the output in the first place?
Also I'm curious how they generate the latin squares, their claims require a uniform distribution of some kind, which is interesting.
reply