Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Need a PRNG? Use a CSPRNG

sortingsearching.com

Post reply on HN
Print view View original

91–100 of 105 posts

Re: Need a PRNG? Use a CSPRNG

#91

Post by tczajka »

bsder wrote: post #60
tczajka wrote: post #48

Earlier quoted context omitted.

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.

Because it is conceivable that you could extract patterns from the underlying data because you know what the highly correlated, short-cycle writing pattern was. In reality, genuinely writing (as opposed to just pretending it was written which is a hazard on any modern storage) any single byte (even just all 0 or all 255) to every position on the disk seems to be more than sufficient to thwart even the NSA.

Isn't it also similarly conceivable that if you write a predictable PRNG sequence such the outputs of Mersenne Twister you could also potentially extract patterns? Mersenne Twister is essentially as predictable as a short cycle.

Re: Need a PRNG? Use a CSPRNG

#92

Post by tczajka »

glitchc wrote: post #45
josephg wrote: post #31

Earlier quoted context omitted.

That might be convenient so you don’t have to go fishing for 3rd party libraries - which is especially a problem in C/C++. But I expect the result will be much slower than using an optimized csrng like chacha.

Well, ChaCha is actually a hash function. Specifically it was a candidate for SHA3 but was beaten by Keccak in the final spec. Additionally, aes-ctr-128 has the same performance as ChaCha (1.5 GB/s). All I was trying to illustrate was that in general, pairing a PRNG with a block cipher or hash function is sufficient to create a CSPRNG, and any developers worried about their PRNGs can couple rand() with a readily avai…

As alright2565 already mentioned, sticking rand() in there doesn't add any benefit over a key + counter.

Without rand() it would be something like SHA3-CTR -- it's not standardized which is why I would prefer ChaCha20, but it has been proposed for standardization and yes it's probably a fine algorithm.

Re: Need a PRNG? Use a CSPRNG

#94

Post by josephg »

tczajka wrote: post #92
glitchc wrote: post #45

Earlier quoted context omitted.

Well, ChaCha is actually a hash function. Specifically it was a candidate for SHA3 but was beaten by Keccak in the final spec. Additionally, aes-ctr-128 has the same performance as ChaCha (1.5 GB/s). All I was trying to illustrate was that in general, pairing a PRNG with a block cipher or hash function is sufficient to create a CSPRNG, and any developers worried about their PRNGs can couple rand() with a readily avai…

As alright2565 already mentioned, sticking rand() in there doesn't add any benefit over a key + counter. Without rand() it would be something like SHA3-CTR -- it's not standardized which is why I would prefer ChaCha20, but it has been proposed for standardization and yes it's probably a fine algorithm.

> it's probably a fine algorithm.

Yeah. I'm nervous about inventing my own RNG. It seems like one of those things thats much more difficult than it appears on the surface. Especially an RNG thats aiming to be crypto-secure.

Re: Need a PRNG? Use a CSPRNG

#95

Post by nmstoker »

nneonneo wrote: post #84
nmstoker wrote: post #71

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?

Hah, if you’re referring to the fact that repetitive digits show up in 2FA codes, this is a great example of a randomness illusion. Of the 1000000 possible 6-digit numbers: 151200 have six unique digits 453600 have five unique digits 327600 have four unique digits 64800 have three unique digits 2790 have two unique digits 10 have only one unique digit Almost 40% of the time you will have a 2FA code that has at most f…

Good point - I definitely need to record them and see if the patterns are really there (it's possible I'm naively noticing only when it fits!)

Re: Need a PRNG? Use a CSPRNG

#96

Post by nmstoker »

sweetjuly wrote: post #75
nmstoker wrote: post #71

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?

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, tha…

Thanks a lot - this is helpful!

Re: Need a PRNG? Use a CSPRNG

#98

Post by loeg »

fanf2 wrote: post #8
boulos wrote: post #2

It's been over a decade since I looked at this, but in real-time Monte Carlo path tracing the speed of your RNG is material. In simple enough scenes, probably something like 5-10% IIRC when using MT. I appreciate that you had a note about performance, but you were pretty quick to dismiss that there's a large quality difference between rand() and any modern PRNG. Plenty of these are fine enough and paying for a CSPRNG…

There are several PRNGs that are faster and more random than Mersenne Twister.

The other big nuisance of the MT is that its state is huge -- the most common version, MT19937, has ~2500 bytes of state and generates 32-bit numbers. A very good 64-bit PRNG only needs 16 bytes of state and a very good 32-bit PRNG only needs 8 bytes of state. That's >300x smaller. This is somewhat related to it being slow, of course, but also somewhat orthogonal.

Re: Need a PRNG? Use a CSPRNG

#99

Post by loeg »

nmstoker wrote: post #71

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?

Sort of, but think many many samples. BigCrush / PractRand / DieHarder are all in this space. https://stackoverflow.com/questions/9780267/testing-the-qual...

Re: Need a PRNG? Use a CSPRNG

#100

Post by loeg »

sneak wrote: post #72
tczajka wrote: post #48

Earlier quoted context omitted.

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.

> This is why they [non-CS PRNGs] are sometimes called DRBGs

CSPRNGs are also sometimes called DRBGs. Classically, "Dual_EC_DRBG" but also NIST SP 800-90A "(AES_)CTR_DRBG," which is what the Windows 10 kernel random device uses.

Post reply on HN