Are there accessible techniques to establish if a number sequence is from a good RNG or not?
I appreciate that people are probably bad judges of randomness but I keep noticing odd patterns with a supposedly random number generated as part of an MFA process.. I'm interested in seeing if there's a problem or if it's actually working effectively. What terms should I search for to find out more on this?
Need a PRNG? Use a CSPRNG
71–80 of 105 posts
Re: Need a PRNG? Use a CSPRNG
#72There are lots of cases where a PRNG is more appropriate than a CSPRNG. Wiping disks is one of them, as the CSPRNG becomes the bottleneck with large arrays. Testing i/o or network throughput is another; you don’t want your algorithm tainting the results. I like the thrust of the article but if you’re going to be particular, you should also be correct. CSPRNGs are not suitable replacements in 100% of cases. Engineerin…
If a predictable PRNG is sufficient for wiping disks, why do we care that the data is random at all? How about writing 0, 1, 2, ..., 255, 0, 1, 2, ... to consecutive bytes? Or -- generate 1 kb of good quality random data, and write the same 1 Kb repeatedly? It's not clear to me what we're trying to achieve in this scenario.
What you just described is, in theory, just a really bad non-CS PRNG. In that sense we are in agreement that a CSPRNG is not necessary.
To your point, a non-CS PRNG seeded with a static value isn’t “random at all”.
This is why they are sometimes called DRBGs: deterministic random bit generators. You just described two such functions.
Re: Need a PRNG? Use a CSPRNG
#73Are there accessible techniques to establish if a number sequence is from a good RNG or not? I appreciate that people are probably bad judges of randomness but I keep noticing odd patterns with a supposedly random number generated as part of an MFA process.. I'm interested in seeing if there's a problem or if it's actually working effectively. What terms should I search for to find out more on this?
[deleted]
Re: Need a PRNG? Use a CSPRNG
#74Earlier quoted context omitted.
The same is true for CSPRNG. Same seed -> same output.
I'm confused; if you can predict the output, then isn't it by definition not secure? Or is the seed so hard to brute force that it's equivalent to breaking the underlying cryptography.
As hinkley said, it is basically impossible to get the seed from the output of the generator without breaking the algorithm itself.
CSPRNG can also be used as the basis for a stream cipher. The output must be the same for the receiver of the message to be able to decrypt it. Being able to extract the seed would be problematic because an attacker could know some part of the message being sent, calculate the CSPRNG output from it and get the seed, thus being able to read all the messages.
CSPRNG are specifically designed to be a one-way function. Calculating the output from the seed should be easy, but calculating the seed from any output must be impossible.
Re: Need a PRNG? Use a CSPRNG
#75Are there accessible techniques to establish if a number sequence is from a good RNG or not? I appreciate that people are probably bad judges of randomness but I keep noticing odd patterns with a supposedly random number generated as part of an MFA process.. I'm interested in seeing if there's a problem or if it's actually working effectively. What terms should I search for to find out more on this?
For CSPRNGs, we tend to use hardness proofs (i.e. prove that an attacker cannot predict the CSPRNG output in polynomial time). To understand these, you'll need to figure out what the algorithm in use is. This isn't particularly relevant to TOTPs since they are built on unforgeable message authentication codes (TOTP usually uses HMAC) so the proof would usually be less about predicting a bit (though, if you could, that would be a valid security break) and more about proving an attacker cannot forge a signature on a message without violating the hardness assumptions.
For regular ol PRNGs (i.e. non-cryptographically secure), there are various tools [1] which let you feed in enormous amounts of samples and then automatically apply a variety of known techniques to try to find correlations. But, generally, you wouldn't expect a PRNG to pass these tests. Instead, you should focus on getting a distribution and behavior that is helpful to your use case.
Re: Need a PRNG? Use a CSPRNG
#76The reason not to use CSPRNG is performance and efficiency. There are many applications where you only need randomness, and don't care about the resiliency provided by the CSRPNG. I mean, I'm not going to run a cryptographically secure generator on a GPU just to scatter a few rays for my raytracer. IMO, suggesting that CSPRNG should be the default choice is a bad engineering advice. This leads to software burning pro…
Perhaps. But one could equally well argue that it should be the default simply because for the small number of applications where performance is really constrained by RNG performance one can still override with a less secure algorithm, while having the default the other way opens many applications to security flaws because of plain old oversights. Many programming language or STL features are somewhat less efficient than they could be by default out of similar concerns.
Re: Need a PRNG? Use a CSPRNG
#77I'm going to keep using quick insecure PRNGs for my NES games rather than write a 6502 implementation of a CSPRNG... I guess this isn't something that's safe to assume for all game development by any means, but in my case if someone really can predict the future actions based off of visual observation they deserve the slight advantage they get.
We can probably assume that writing assembly for a machine the better part of 40 years old was not what the author had in mind when writing.
Re: Need a PRNG? Use a CSPRNG
#78The reason not to use CSPRNG is performance and efficiency. There are many applications where you only need randomness, and don't care about the resiliency provided by the CSRPNG. I mean, I'm not going to run a cryptographically secure generator on a GPU just to scatter a few rays for my raytracer. IMO, suggesting that CSPRNG should be the default choice is a bad engineering advice. This leads to software burning pro…
The author does address the perf & efficiency concerns, though I have no opinion on the strength of their conclusions.
But I think this is like everything else: don't prematurely optimize. If you start with a CSPRNG, you're more likely to know that your algorithm is correct, and that you're getting good, random results. If you later profile your code and see that the CSPRNG is a bottleneck, you can swap it out with something faster. And then you'll also have a baseline for comparison, so you'll know if using a weaker PRNG actually has a negative impact on whatever it is you're doing.
(And even if you don't do that profiling, you can swap out the CSPRNG just to see what happens, and get a good idea if the quality of the randomness produced by the PRNG is good enough, based on your experience with the CSPRNG.)
Re: Need a PRNG? Use a CSPRNG
#79I'm surprised I'm not seeing mention of the reduced round ChaCha8 version of ChaCha, that's what I'd recommend for Monte Carlo use. It's available in Rust at https://docs.rs/rand_chacha/0.3.1/rand_chacha/struct.ChaCha8... . I recommend seeding it from a high quality random source, but it could be fixed in your source code, generated with `openssl rand -base64 32` or similar.
The article does at least mention the ChaCha12 impl in that same rust crate:
> The de-facto standard Rust library for random numbers, rand, uses ChaCha12, a reduced-round variant of ChaCha20, as its default PRNG.
Re: Need a PRNG? Use a CSPRNG
#80Even simpler than implementing a cryptographic PRNG yourself, just use /dev/urandom, which will provide an infinite, non-blocking stream of cryptographically-strong pseudorandom bytes. All platforms currently have known-good implementations of /dev/urandom -- Linux uses ChaCha and MacOS and BSDs use Bruce Schneier's Fortuna.
/dev/urandom is really slow compared to a userland CSPRNG, though. And if you are doing simulations or fuzz testing, you need to be able to seed your PRNG to get reproducible results.
You can always pre-fetch random bytes in larger blocks. Read a few kB of random bytes at a time, store them in a buffer, and refresh the buffer when you run out.
Agreed on the need for using a predictable seed for testing/simulations, though. Technically you can seed /dev/urandom, but it's per-system, not per-process, so you can't guarantee some other process isn't "interrupting" your random stream.