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

Designing a New PRNG

tom-kaitchuck.medium.com

Post reply on HN
Print view View original

31–40 of 52 posts

Re: Designing a New PRNG

#31

Post by loeg »

oconnor663 wrote: post #28

> After some minor optimizing, on my laptop here are benchmarks on filling a 1kb byte array: > > Mwc-256-X-X-A-64 (This algorithm): 100.98 ns That comes to 10 GB/s. For comparison, I think ChaCha8 implemented with AVX-512 should run at a similar speed. Maybe a bit faster in short-ish, single-threaded benchmarks. To be clear, there are plenty of caveats in making this comparison: ChaCha8 won't hit that throughput on a…

Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.

Re: Designing a New PRNG

#32

Post by maqp »

foxfluff wrote: post #26
matthewdgreen wrote: post #24

Earlier quoted context omitted.

There are perfectly legitimate use case (in a tiny niche area) for non-cryptographic RNGs - however, three points: 1. Non-cryptographic RNGs, should they be incorporated in security-critical applications are dangerous . If you insist on manufacturing poisonous chemicals that look appetizing and say “Kool-Aid” on them, kids are going to drink them. And this is your damned fault. 2. Non-cryptographic RNGs should not be…

I agree on all three points. I might even agree on the proposed name; not that I care too much. All I'm saying is that I'm happy the state of art of fast (but insecure) generators is improving and people have better options than cranky old LCGs or Mersenne Twister (ugh!). I don't know why they brought up non-invertibility. But, at a glance, I see a new RNG that might be at least twice as fast as a comparable variant…

It's great that insecure fast RNGs are improving, but it's extremely important to be responsible about how they should be promoted.

1. Insecurity needs to be in the name: Make it Insecure. This is extremely important. Since the intended use-context is going to be non-security critical, anyway, it's actually good that it states it's insecure. That way you know you're not accidentally using RNG where security properties might cause any bottle-necks. At the same time the misuse resistance of the RNG increases significantly.

2. Make sure this is not default, but something that needs to be imported separately from non-security context, such as module about statistics, simulation etc.

Re: Designing a New PRNG

#33

Post by noiddicle »

jcelerier wrote: post #22
dogecoinbase wrote: post #19

Earlier quoted context omitted.

Saving some weight by leaving the airbag out of your car doesn't mean that it going faster is a good thing.

There's no such thing as "a good thing". There are only goals, security is just a goal among other that not everyone have.

The problem that we have is that a minority of people realize that not all random implementations are actually fit for purpose for cryptographic security.

See CWE-338 for an enumerated list of these things in the wild.

I found 300+ examples of CVEs with little effort.

Should developers who are writing code that involves cryptography know better? Sure - but they don't. They cut and paste from stackoverflow with horrific results.

Re: Designing a New PRNG

#34

Post by kevingadd »

loeg wrote: post #31
oconnor663 wrote: post #28

> After some minor optimizing, on my laptop here are benchmarks on filling a 1kb byte array: > > Mwc-256-X-X-A-64 (This algorithm): 100.98 ns That comes to 10 GB/s. For comparison, I think ChaCha8 implemented with AVX-512 should run at a similar speed. Maybe a bit faster in short-ish, single-threaded benchmarks. To be clear, there are plenty of caveats in making this comparison: ChaCha8 won't hit that throughput on a…

Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.

If you actually care about performance you should be generating batches of output and pulling entropy out of it, not invoking the PRNG every time you need a random byte. The icache and dcache impact of running all that prng code is going to eat into the performance of your actual software in a way that microbenchmarks won't show. So the need to do that with chacha isn't necessarily a problem, it may be pushing you towards a better design.

Re: Designing a New PRNG

#35

Post by [deleted] »

loeg wrote: post #31
oconnor663 wrote: post #28

> After some minor optimizing, on my laptop here are benchmarks on filling a 1kb byte array: > > Mwc-256-X-X-A-64 (This algorithm): 100.98 ns That comes to 10 GB/s. For comparison, I think ChaCha8 implemented with AVX-512 should run at a similar speed. Maybe a bit faster in short-ish, single-threaded benchmarks. To be clear, there are plenty of caveats in making this comparison: ChaCha8 won't hit that throughput on a…

Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.

[deleted]

Re: Designing a New PRNG

#36

Post by berkut »

Yeah, I really don't understand why security properties are that important for a non-cryptographic PRNG anyway either...

Also, I'd personally argue that 'k-Dimensional Equidistribution' *is* actually fairly useful for a PRNG - certainly I'd argue it's more useful than secure properties in the use cases of simulation or MC...

Re: Designing a New PRNG

#37

Post by comex »

kevingadd wrote: post #34
loeg wrote: post #31

Earlier quoted context omitted.

Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.

If you actually care about performance you should be generating batches of output and pulling entropy out of it, not invoking the PRNG every time you need a random byte. The icache and dcache impact of running all that prng code is going to eat into the performance of your actual software in a way that microbenchmarks won't show. So the need to do that with chacha isn't necessarily a problem, it may be pushing you to…

Dcache impact? Of accessing the state which, for a non-cryptographically-secure PRNG, is often 128 bits? I'm not seeing it. Even CSPRNGs don't usually have state that's all that much larger. Surely there would be much higher dcache impact from storing and loading the batches of output. On the other hand, I can buy icache, along with function call overhead and lack of parallelism...

Re: Designing a New PRNG

#38

Post by loeg »

kevingadd wrote: post #34
loeg wrote: post #31

Earlier quoted context omitted.

Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.

If you actually care about performance you should be generating batches of output and pulling entropy out of it, not invoking the PRNG every time you need a random byte. The icache and dcache impact of running all that prng code is going to eat into the performance of your actual software in a way that microbenchmarks won't show. So the need to do that with chacha isn't necessarily a problem, it may be pushing you to…

MCG (like pcg64_fast) is like a single 128-bit mul and a mask. There’s not a lot of icache impact.

Re: Designing a New PRNG

#39

Post by tptacek »

omoikane wrote: post #14
zokier wrote: post #9

Earlier quoted context omitted.

Seems that vigna (author of the xoshiro family of rngs) mostly agrees with you > Personally, I don't believe in the "middle ground" of "difficult-to-predict-but-not-crypto": usually it just means it is so easy to break that nobody https://github.com/rust-random/rand/issues/905#issuecomment-...

I wish that issue would also link to the rebuttal: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html

Do you find that rebuttal persuasive? For someone who doesn't care at all about anyone's "tone", and just wants to know what the hell is going on with these constructions, I didn't find much there.

Re: Designing a New PRNG

#40

Post by ttybird2 »

omoikane wrote: post #14
zokier wrote: post #9

Earlier quoted context omitted.

Seems that vigna (author of the xoshiro family of rngs) mostly agrees with you > Personally, I don't believe in the "middle ground" of "difficult-to-predict-but-not-crypto": usually it just means it is so easy to break that nobody https://github.com/rust-random/rand/issues/905#issuecomment-...

I wish that issue would also link to the rebuttal: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html

https://www.pcg-random.org/

PCG's statistical quality is "excellent" but chacha20's just "good"?

Post reply on HN