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

101–105 of 105 posts

Re: Need a PRNG? Use a CSPRNG

#101

Post by KolenCh »

isilofi wrote: post #6

For many kinds of Monte Carlo algorithms, CSPRNGs are stupidly slow. The author compares two handpicked examples of a fast CSPRNG and a very slow PRNG, arriving at a factor of 4. In practice, e.g. comparing to very simple stuff like multiply-add RNGs, it is more like a factor of 4000. Only to then claim that "But that would only be true if generating random bits was the hot spot, the bottleneck of your program. It ne…

For Monte Carlo and if you need for speed, consider Quasi Monte Carlo. For the right kind of problems the speed up in convergence is huge (ie given same accuracy it will be faster.)

Re: Need a PRNG? Use a CSPRNG

#102

Post by bsder »

tczajka wrote: post #91
bsder wrote: post #60

Earlier quoted context omitted.

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.

Correlating a short cycle is much more difficult than correlating a long cycle even if you have complete information about the long cycle. If the bits on the disk have a pattern, it is much more likely to repeat against a short cycle.

However, as I pointed out, it's all pretty much moot. I've never seen anybody cough up evidence that a disk could be recovered after even a single write with merely zeroes. In fact, there was a competition and prize for a while that could be won if you could demonstrated reconstruction of a disk after even a single platter write. Nobody ever managed to claim it.

Re: Need a PRNG? Use a CSPRNG

#103

Post by tatersolid »

josephg wrote: post #94
tczajka wrote: post #92

Earlier quoted context omitted.

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.

> I'm nervous about inventing my own RNG.

You should be, but in this case you’re actually not inventing your own CSPRNG.

NIST SP 800-90A defines HASH_DRBG as hashing a seed (aka key) plus a counter and it is defined for basically any cryptographic hash function.

Re: Need a PRNG? Use a CSPRNG

#104

Post by gonzo »

tptacek wrote: post #63
schoen wrote: post #54

Earlier quoted context omitted.

> that cannot use NIST cryptography Do you mean as a matter of Donenfeld's engineering decisions (that those algorithms are unavailable in WireGuard)?

Yes: they use, for lack of a better term, DJB cryptography, and like many modern cryptosystems they eschew negotiation, so it's not straightforward to fit NIST algorithms in.

it's entirely straight-forward to substitute AES-256-GCM for ChaCha20/Poly1305 in Wireguard, and the result, while not "wireguard" is substantially faster than Wireguard.

Re: Need a PRNG? Use a CSPRNG

#105

Post by Thorham »

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…

ChaChah is a stream cipher and was never a SHA3 candidate.
Post reply on HN