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

41–50 of 52 posts

Re: Designing a New PRNG

#41

Post by omoikane »

tptacek wrote: post #39
omoikane wrote: post #14

Earlier quoted context omitted.

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.

My reading of both:

- Vigna claims small differences in internal states don't have avalanche effects, and the rebuttal says those small differences in internal states don't occur normally, not with the proper seeding steps.

- Vigna claims to be able to predict one particular variant of PCG, and the rebuttal said that that was one of the weaker variants that specifically has "insecure" in the name.

It's persuasive to me in suggesting that Vigna's claims are perhaps not that clear cut.

I am not an expert in PRNG and I wouldn't say this makes PCG win over Xorshiro or not, I just think it's unfortunate that the issue above linked only one side of the argument, especially since I find the other side more pleasant to read.

Re: Designing a New PRNG

#42

Post by loeg »

ttybird2 wrote: post #40
omoikane wrote: post #14

Earlier quoted context omitted.

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"?

It is a bit odd. I think the PCG authors are talking about reduced-round variants below 8[1] re: statistical quality. I agree it doesn't belong in a row labeled "ChaCha20." It seems obvious that chacha below 4 rounds is total garbage[2] but I don't know much about 4-7 rounds. The Too Much Crypto guy likes 8 rounds for cryptographic purposes.

[1]: https://www.pcg-random.org/other-rngs.html#id7

[2]: https://cr.yp.to/snuffle/diffusion.html

Re: Designing a New PRNG

#43

Post by adgjlsfhk1 »

matthewdgreen wrote: post #24
foxfluff wrote: post #20

Earlier quoted context omitted.

So did PCG or xoroshiro leave the airbag out of MCGs or what? Or are you one of those who pretend that there was never any legitimate use case for any non-cryptographic PRNG?

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…

point 1 is just false. some examples where it's perfectly acceptable to use a bad rng in a safety critical system

factoring/prime checking algorithms

any type of stimulation (eg for drug dosing/particle stimulation)

sorting algorithms

most graph based algorithms.

in short, many real works problems are best solved by random algorithms, but the randomness can be of fairly low quality without causing problems.

Re: Designing a New PRNG

#44

Post by kittywav »

nullc wrote: post #10
failrate wrote: post #8

I've used noise functions as good noncryptographic PRNG. E.g. Squirrel3 hash Fast and cheap with no apparent periods.

Every RNG with a fixed size state has a period. If the period is not known, it's probably seed dependent and there may be some seeds with very small period. If 'very small' is small enough (such as 2 or 5) then those seeds will cause some ordinary uses to fail badly in obvious ways. If bad seeds are common enough (say 1 in 2^64) then you could actually see rare failures in production. (Cryptographic RNGs tend to avoi…

Just a small comment: you can do things to ensure that the period of a PRNG is longer than a certain lower bound for any input seed. For example, if you make the state-mixing function depend on a 64-bit counter, you'll ensure that the period is at least 2^64 (assuming the state-mixing function is reversible).

Re: Designing a New PRNG

#45

Post by jcelerier »

noiddicle wrote: post #33
jcelerier wrote: post #22

Earlier quoted context omitted.

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 horrif…

> Should developers who are writing code that involves cryptography know better?

but cryptography is just one small use case of RNGs. Grepping through my home for e.g. random_engine, less than 1% seems to be related to crypto use cases, the bulk are being taken by noise generation for various artistic use cases, games, compilers, schedulers, and tests. Stuff like shuffling a playlist, making particles move in random directions, randomness in paint brushes, etc.

If I want to generate a white noise texture for a video game do you think I care more about cryptographically-secureness or the operation not taking 10 seconds for a 4k texture ?

Re: Designing a New PRNG

#46

Post by jcelerier »

matthewdgreen wrote: post #24
foxfluff wrote: post #20

Earlier quoted context omitted.

So did PCG or xoroshiro leave the airbag out of MCGs or what? Or are you one of those who pretend that there was never any legitimate use case for any non-cryptographic PRNG?

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…

> There are perfectly legitimate use case (in a tiny niche area) for non-cryptographic RNGs - however, three points:

no, crypto IS the niche area. The vast majority of random code in existence has absolutely nothing to do with crypto. It's cryptographic use-cases which should be marked specifically.

Re: Designing a New PRNG

#47

Post by nmadden »

adgjlsfhk1 wrote: post #43
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…

point 1 is just false. some examples where it's perfectly acceptable to use a bad rng in a safety critical system factoring/prime checking algorithms any type of stimulation (eg for drug dosing/particle stimulation) sorting algorithms most graph based algorithms. in short, many real works problems are best solved by random algorithms, but the randomness can be of fairly low quality without causing problems.

He said security-critical not safety-critical. Security-critical implies an adversarial setting.

Re: Designing a New PRNG

#48

Post by guimplen »

It is funny how the LCG is getting overlooked. As far as I know 128 bit state Lehmerthat outputs higher 64 bits works for every application. The problem with the old LCG wath that they had extremely small state (16 bit) and they just gave it right away. The 128 bit Lehmer is dead simple, very well studied and should work fast on any modern CPU (one 128 bit multiplication).

Re: Designing a New PRNG

#49

Post by nullc »

kittywav wrote: post #44
nullc wrote: post #10

Earlier quoted context omitted.

Every RNG with a fixed size state has a period. If the period is not known, it's probably seed dependent and there may be some seeds with very small period. If 'very small' is small enough (such as 2 or 5) then those seeds will cause some ordinary uses to fail badly in obvious ways. If bad seeds are common enough (say 1 in 2^64) then you could actually see rare failures in production. (Cryptographic RNGs tend to avoi…

Just a small comment: you can do things to ensure that the period of a PRNG is longer than a certain lower bound for any input seed. For example, if you make the state-mixing function depend on a 64-bit counter, you'll ensure that the period is at least 2^64 (assuming the state-mixing function is reversible).

Assuming its a permutation and you output the whole thing.

However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant).

In that case the 'state' has a long period, true, but the output doesn't. If instead you use a construction where the output is guaranteed to have a known (large) period, you can follow that up with whatever permutation you want, but to preserve the period all of the permutation must be output.

Re: Designing a New PRNG

#50

Post by kittywav »

nullc wrote: post #49
kittywav wrote: post #44

Earlier quoted context omitted.

Just a small comment: you can do things to ensure that the period of a PRNG is longer than a certain lower bound for any input seed. For example, if you make the state-mixing function depend on a 64-bit counter, you'll ensure that the period is at least 2^64 (assuming the state-mixing function is reversible).

Assuming its a permutation and you output the whole thing. However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant). In that case the 'state' has a long period, true, but the output d…

> Assuming its a permutation and you output the whole thing.

I'm assuming the state-mixing function is a permutation (i.e. the counter affects the whole state in a reversible way), but it is not required that the whole state is outputted.

> However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant).

The counter will always have the full period of 2^N (assuming N-bit counter), regardless of how it is initialized (i.e. regardless of seeding), as long as it is a simple "i = (i + 1) mod 2^N" counter.

What this does is to effectively change the (presumably fixed) state permutation function: instead of using a fixed one, you're applying a repeating sequence of 2^N slightly different state permutation functions, which ensures that the period of the state should be at least as large as that (and probably much larger).

Assuming the chosen state permutation function is reasonable (and does indeed mix the counter effectively), truncating the state to provide output should not lead to short cycles: if it does, then your permutation is probably not reasonable as primitive for a PRNG (i.e. you have worse problems in your generator than "small period").

For more information on the use of counters to ensure lower bounds on the periods of stream ciphers and PRNG, take a look at Rabbit [1] (or, in general, at the concept of "counter-assisted stream ciphers" [2]).

[1] https://www.ecrypt.eu.org/stream/rabbitpf.html

[2] https://arxiv.org/abs/cs/0112014v5

Post reply on HN