7 ms·
Author's title should be "Cracking PSEUDO-random number generators" - We should all basically assume that any PRNG will be easily cracked like this and not use
by pbnjay 9y ago
Author's title should be "Cracking PSEUDO-random number generators" - We should all basically assume that any PRNG will be easily cracked like this and not use them for anything important to security!
Always use a cryptographic RNG for important code!
- anfractuosity 9y agoAren't cryptographic random number generators, still PRNGs. It sounds a fun problem, predicting the future random numbers, going to have to have a play later at trying it.
- hlieberman 9y agoYes. GP is mistaken here; this is novel work that is somewhat concerning -- mostly in how it might apply to other similarly state-based RNGs.
- pbnjay 9y agoI made no comment on the work done here, it is novel and concerning if you use the outputs for important things. My comment is that non-cryptographic random number generators should not be used for security-critical functions. These functions are specifically built for speed, not security.
- karanlyons 9y agoI wouldn’t say this work is novel in the general case of “PRNGs are not CSPRNGs”. You can throw a constraint solver at most any PRNG and given sufficient output determine the state fairly easily. As a datapoint, doing this for xoroshiro took me half an hour: https://gist.github.com/karanlyons/805dbcc9e898dbd17e06f2627d5f9111 https://gist.github.com/karanlyons/805dbcc9e898dbd17e06f2627...
- anfractuosity 9y agoHeh, that sounds cool. I'll save opening that link for later.
- karanlyons 9y agoDon’t worry, it’s safe: I didn’t put the actual solver, just proof that I solved it. Wouldn’t want to spoil the fun for anyone else :)
- DiThi 9y agoStrong crypto RNGs use PRNGs but combines sources of entropy, environmental noise from devices such as the number of CPU cycles between user keystrokes. T̶h̶a̶t̶'̶s̶ ̶t̶h̶e̶ ̶d̶i̶f̶f̶e̶r̶e̶n̶c̶e̶ ̶b̶e̶t̶w̶e̶e̶n̶ ̶/̶d̶e̶v̶/̶r̶a̶n̶d̶o̶m̶ ̶a̶n̶d̶ ̶/̶d̶e̶v̶/̶u̶r̶a̶n̶d̶o̶m̶ ̶i̶n̶ ̶L̶i̶n̶u̶x̶.̶
- Tomte 9y agoNo, that difference (between /dev/random and /dev/urandom) does not exist, has never existed and will never exist. Please don't spread those myths.
- andruby 9y agoAs I am uninformed on the subject, could you tell me the difference between /dev/random and /dev/urandom?
- filleokus 9y agoQuite a long read, but I think it explains the situation quite well: https://www.2uo.de/myths-about-urandom/ https://www.2uo.de/myths-about-urandom/
- snakeanus 9y agoAlso an interesting and related article https://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ https://sockpuppet.org/blog/2014/02/25/safely-generate-rando...
- Tomte 9y agoUnfortunately, the article isn't in the best shape right now. Back when it was written, things were clear: random and urandom are the same. Then came getrandom as a distraction. Now urandom is based on chacha. So it's different (but not worse – still, harder to explain). The article's structure couldn't easily accomodate those changes, and time was and is in short supply, and so it's not wrong, but much less forceful and clear than it used to be. I hope it shapes up soon, but don't promise anything! Still, I don't know a more up-to-date article. Maybe Thomas Pornin has something newer on StackOverflow?
- tptacek 9y agoThis shouldn't have been downvoted because it is exactly correct. Cryptographic generators don't work like PCG and xoroshiro and Mersenne Twister. They're generally built by taking a cryptographically secure cipher or hash core, "keying" it with secret entropy, and running it in a streaming configuration (like CTR mode). A properly designed CSPRNG can only be "cracked" in a few specific scenarios: 1. The primitive it's built on (or the streaming construction it's configured in) is broken, in which case the news for cryptography as a field is significantly bigger than the fact that an RNG has a flaw. 2. An attacker has exploited a systems flaw to directly disclose the contents of the memory the CSPRNG is operating out of, in which case you have bigger problems than your CSPRNG. 3. The secrets that key the generator have become predictable. This is in practice the only way CSPRNGs get broken (unintentionally), and, in practice, always means the CSPRNG wasn't initialized properly (the "cold start entropy problem"). You should use the getrandom() system call, or read from /dev/urandom, to the exclusion of all other mechanisms.
- baby 9y agoFWIW you rarely hear the term CSPRNG in crypto I find. I always call these PRNGs but I can see how having a naming distinction could help prevent misuse in the applied world. Edit: thinking a bit more about it. I guess it wouldn't make sense to call anything "crypto" in crypto. It's like calling fries "french fries" in France. There they're just fries. I know this is a bad example because french fries are probably not from France :o)
- gwbas1c 9y agoBut, it's important to make the decision because a "crypto" psudorandom number generator may be significantly slower than an insecure generator. This is critical for performance-sensitive operations. For example, certain audio and video codecs need to simulate noise. In these cases, high performance is much more important than cryptographic security.
- tptacek 9y agoIn the overwhelming majority of cases, cryptographic random bit generation performs perfectly adequately. Insecure random number generation is wildly overused in our industry. CSPRNGs should be the default application RNGs on most platforms, and should always be the default choice for developers. Which makes stuff like PCG even weirder! Because in most cases, what you want is a somewhat slower generator that has better failsafe behavior.
- imaginenore 9y agoCan you crack this PRNG without knowing the seed? f(1) = 1 // seed f(n) = sha512(f(n-1) . f(1))
- sdevlin 9y agoI guess it depends what you mean by “crack”. Given f(1), which I assume is public, you can predict all future outputs.
- IshKebab 9y agoThat is not what we mean by "crack". Read the article.
- imaginenore 9y agoI said without knowing the seed, so f(1) is not public, only f(n) formula is.
- benchaney 9y agof(1) is the first batch of output.
- mdpopescu 9y agoThis is similar to Yarrow / Fortuna (internal state is a counter, output is the hash of the state) so I'm guessing it's not breakable, at least not trivially.
- VikingCoder 9y ago"Always use a cryptographic PSUEDO-RNG for important code!" Just because it's "cryptographic" doesn't mean it's not pseudo-random.