4 ms·
"As a bonus, all the other algorithms are apparently faster and that’s generally a desirable property." I apologize for discussing a technical topic in whats l
by VLM 13y ago
"As a bonus, all the other algorithms are apparently faster and that’s generally a desirable property."
I apologize for discussing a technical topic in whats likely to be a political crypto-rage flamewar, but I've been digesting some thoughts about this and the figure of merit of processing required per bit of randomness is probably interesting, in that for a given set of professional grade RNGs (not algorithms implemented by idiots) the more processing required to generate a bit of randomness, the more likely it is someone's sticking a nasty backdoor in.
Or rephrased the more time you spend sticking magic "nothing up my sleeves" constants into a bit, the more likely something unpleasant is getting stuck in there.
(edited to add I'm talking about "real" RNGs not implying the worlds simplest shortest LFSR is magically better than a real RNG just because its really fast... I'm talking about more "in class" performance comparisons than joke vs real.)
- Guvante 13y agoIt depends on what you are talking about, sometimes you want a slow protocol, since it makes bruteforcing the original value more complicated. I can't wrap my head around why that would matter for a PRNG, but it sometimes does have value.
- ogreyonder 13y agoAnd that's exactly what had everyone else scratching their heads, too! There are plenty of slow random number generators. They're easily built from cryptographic hash functions [1]. Heck, use something like Bcrypt as your hash and you can get as many seconds per number as you like. The reason we don't use them even though they work perfectly well is that they are too slow. The challenge is making a fast PRNG that can maintains the properties of cryptographic randomness. That's why everyone was so confused with dual EC. [1] http://en.wikipedia.org/wiki/Cryptographic_hash_function#Use_in_building_other_cryptographic_primitives http://en.wikipedia.org/wiki/Cryptographic_hash_function#Use...
- bradleyjg 13y agoAs I understand it the whole reason you use a PRNG rather than just using your source entropy with some conditioning, is speed -- or maybe the risk of stalling, which is related to speed. So if you want slow, you can forget the seeding-a-deterministic-algorithm part altogether.
- marcosdumay 13y agoAnother important reason for using a PRNG is when you don't trust your hardware RNG, what've become way too common lately.
- mindslight 13y agoEh, 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.
- makomk 13y agoThe idea has of an EC-based PRNG apparently has merit, however the Dual_DC_DRBG implemntation doesn't. Supposedly there are similar designs out there which have nice security proofs which the NSA one lacked, most likely due to the backdoor.