Designing a New PRNG(tom-kaitchuck.medium.com)
tom-kaitchuck.medium.com
Designing a New PRNG
https://tom-kaitchuck.medium.com/designing-a-new-prng-1c4ffd27124d
52 comments
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-...
> 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"?
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
[1]: https://www.pcg-random.org/other-rngs.html#id7
[2]: https://cr.yp.to/snuffle/diffusion.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.
- 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.
I think the allure here is the same as with ciphers. Everyone can create a cipher they cannot break, but cryptographers can break easily.
Likewise, it's easy to invent another PRNG, but not so easy to figure out that, say, its output always falls on one of seventeen parallel planes when treated as consecutive (x, y, z) coordinates.
If you want random numbers that are fast and almost-cryptographically-strong, you can take some ARX block cipher and reduce number of rounds as you see fit. But it's not nearly as much fun.
Likewise, it's easy to invent another PRNG, but not so easy to figure out that, say, its output always falls on one of seventeen parallel planes when treated as consecutive (x, y, z) coordinates.
If you want random numbers that are fast and almost-cryptographically-strong, you can take some ARX block cipher and reduce number of rounds as you see fit. But it's not nearly as much fun.
From what I understand of the matter, the crux of it is that there are two modern PRNG families whose creators are running around telling you to use their PRNG over the other's because <technical reasons>, where a) both of them are correct, and b) the <technical reasons> don't elucidate the tradeoffs being made to people whose prior understanding amounts to "I just want a source of random numbers!" This is contrast to something like a linear congruential generator, where the failure mode of the random data is pretty easy to explain.
I think you misread tptacek's line of questioning. It's not about the quality / superiority of what over what, but the initial motivation for rand switching away from PCG:
> This was done after some concerns were raised by the author of xoshiro, who posted a blog entry on PCG and also raised an issue on the possibility of PCG being invertible.
PCG and the XOR family are both non-cryptographic RNGs, how is predictability or invertibility relevant then? If those are concerns, surely a CSPRNG should be used?
The "quality" of randomness is very much a concern in non-secure contexts e.g. patterns in an RNG can bias your simulation, but it doesn't seem like it'd matter if somebody can recover even your simulation seed.
> This was done after some concerns were raised by the author of xoshiro, who posted a blog entry on PCG and also raised an issue on the possibility of PCG being invertible.
PCG and the XOR family are both non-cryptographic RNGs, how is predictability or invertibility relevant then? If those are concerns, surely a CSPRNG should be used?
The "quality" of randomness is very much a concern in non-secure contexts e.g. patterns in an RNG can bias your simulation, but it doesn't seem like it'd matter if somebody can recover even your simulation seed.
[deleted]
I agree that the motivation is pretty confused. One of the straightforward goals is to be faster than PCG-64 or xoshiro256++ -- that seems reasonable.
Seriously. Cut this shit out. Design a cryptographic RNG or decide precisely how you intend to justify a non-cryptographic RNG that has cryptographic security properties (but like, not all of them.)
The interesting angle here is 2x performance vs pcg64_fast or xoshiro256++, with competitive quality in that space. It’s a simulation PRNG, not a CSPRNG. I agree the introduction to the article is somewhat confused (i.e., mentioning invertibility), but it never claims to be a CSPRNG.
The vast majority of the article is pretty interesting, if you can get past the first couple paragraphs and some typos.
The context is Rust’s SmallRng[1]. The top-level description of that is:
> A small-state, fast non-crypto PRNG
[1]: https://docs.rs/rand/0.8.4/rand/rngs/struct.SmallRng.html
The vast majority of the article is pretty interesting, if you can get past the first couple paragraphs and some typos.
The context is Rust’s SmallRng[1]. The top-level description of that is:
> A small-state, fast non-crypto PRNG
[1]: https://docs.rs/rand/0.8.4/rand/rngs/struct.SmallRng.html
If you want to design a cryptographic RNG that falls between LCGs and PCG in speed, please have a go at it. Meanwhile we'll use our small and fast PRNGs and strive to make them as good as they can possibly be for non-cryptographic uses.
I beg you to define what “good” means in a way that doesn’t imply security properties. And if you must demand security properties, god help you if you designed something that can’t provide them.
Say I want to numerically approximate a high dimensional integral with MC sampling, say in a computational fluid dynamics simulation, or in a ray traced render.
For this, I need consequent samples from a PRNG to be really uncorrelated and fast. But there is no adversary relationship, so I don't need cryptographic strength. I just cannot have any spurious correlations between samples, as they might throw off convergence speed or worse, introduce error.
For this, I need consequent samples from a PRNG to be really uncorrelated and fast. But there is no adversary relationship, so I don't need cryptographic strength. I just cannot have any spurious correlations between samples, as they might throw off convergence speed or worse, introduce error.
You don't need to define good in an absolute sense to see how one thing can be better than another.
The flaws of an MCG or LCG are easily witnessed, so it's totally fair for someone to go find out if it's possible to do better (i.e. remove obvious patterns, fix low period of low order bits, improve statistical quality) without sacrificing much performance; and indeed perhaps making it faster than a large-state LCG of comparable quality would be.
If you admit that there are any legitimate uses for non-cryptographic PRNGs then I guess a 32 bit MCG (or "42") is just perfect for you (otherwise you'd know what's better and you don't need to ask anyone to define good). You're easy to please.
If you think there are no legitimate use cases for these fast generators at all, then I'm sorry but a lot of people disagree and they will never rewrite their sims, noise generators, world generators, etcetra to use a CSPRNG no matter how much you whine about it.
The flaws of an MCG or LCG are easily witnessed, so it's totally fair for someone to go find out if it's possible to do better (i.e. remove obvious patterns, fix low period of low order bits, improve statistical quality) without sacrificing much performance; and indeed perhaps making it faster than a large-state LCG of comparable quality would be.
If you admit that there are any legitimate uses for non-cryptographic PRNGs then I guess a 32 bit MCG (or "42") is just perfect for you (otherwise you'd know what's better and you don't need to ask anyone to define good). You're easy to please.
If you think there are no legitimate use cases for these fast generators at all, then I'm sorry but a lot of people disagree and they will never rewrite their sims, noise generators, world generators, etcetra to use a CSPRNG no matter how much you whine about it.
Saving some weight by leaving the airbag out of your car doesn't mean that it going faster is a good thing.
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 evaluated and improved so as to (appear to provide) security properties. Non-invertability is a security property. Anyone who needs this property probably wants something that has been properly evaluated by experts to provide it. This construction has not been, and it is appropriate to assume that against a sufficiently-motivated adversary it will not provide it. Assuming otherwise is stupid and dangerous.
3. People who can use a non-cryptographic RNG but can’t afford the compute of a full cryptographic RNG are a very small subset of all users with very specific computing limitations. If you must target them with something, you should justify your computing speedup.
My proposal is that this type of non-cryptographic RNG should have a name that is not easily confused with safe cryptographic PRNGs. Perhaps “statistical sequence generator”. Moreover, people designing these systems should not be playing with security properties. Do one thing or the other, but not both things badly.
The set of people who need fast statistical (but insecure) sequence generators is small. They know who they are and what they need. Stop littering the school yard with poisonous chemicals that say “Kool Aid” in an effort to reach a few hundred laboratory chemists who are perfectly capable of calling you and ordering exactly the ingredients they know they need.
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 evaluated and improved so as to (appear to provide) security properties. Non-invertability is a security property. Anyone who needs this property probably wants something that has been properly evaluated by experts to provide it. This construction has not been, and it is appropriate to assume that against a sufficiently-motivated adversary it will not provide it. Assuming otherwise is stupid and dangerous.
3. People who can use a non-cryptographic RNG but can’t afford the compute of a full cryptographic RNG are a very small subset of all users with very specific computing limitations. If you must target them with something, you should justify your computing speedup.
My proposal is that this type of non-cryptographic RNG should have a name that is not easily confused with safe cryptographic PRNGs. Perhaps “statistical sequence generator”. Moreover, people designing these systems should not be playing with security properties. Do one thing or the other, but not both things badly.
The set of people who need fast statistical (but insecure) sequence generators is small. They know who they are and what they need. Stop littering the school yard with poisonous chemicals that say “Kool Aid” in an effort to reach a few hundred laboratory chemists who are perfectly capable of calling you and ordering exactly the ingredients they know they need.
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 of PCG while offering similar or better statistical performance. That's exactly the kind of development I like to see.
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 of PCG while offering similar or better statistical performance. That's exactly the kind of development I like to see.
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<Your RNG Name Here>. 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.
1. Insecurity needs to be in the name: Make it Insecure<Your RNG Name Here>. 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.
[deleted]
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.
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.
> 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.
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.
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.
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.
> 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 ?
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 ?
> 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 any output size smaller than 1 KiB. AVX-512 requires a very recent processor. Most library implementations don't include AVX-512 support. Power usage will be high. Downclocking will be an issue, especially with multithreading. Etc. etc.
But in exchange, you get all the security properties.
I think one takeaway here is that the gap between cryptographic and non-cryptographic is smaller than many people think, which argues in favor of secure defaults. (Though to be clear, I don't think OP or anyone in this thread is opposed to secure defaults.) Another takeaway is that a lot of these blockers, like hardware and library support, will continue to improve over time. So if you find that a CSPRNG isn't fast enough for your use case today, make sure to check again in a few years. And of course, as always, it's important to benchmark your specific use case if you're worried about performance.
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 any output size smaller than 1 KiB. AVX-512 requires a very recent processor. Most library implementations don't include AVX-512 support. Power usage will be high. Downclocking will be an issue, especially with multithreading. Etc. etc.
But in exchange, you get all the security properties.
I think one takeaway here is that the gap between cryptographic and non-cryptographic is smaller than many people think, which argues in favor of secure defaults. (Though to be clear, I don't think OP or anyone in this thread is opposed to secure defaults.) Another takeaway is that a lot of these blockers, like hardware and library support, will continue to improve over time. So if you find that a CSPRNG isn't fast enough for your use case today, make sure to check again in a few years. And of course, as always, it's important to benchmark your specific use case if you're worried about performance.
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.
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...
Depends on the algorithm, I suppose? Many algorithms that consume randomness in a way that is performance sensitive, like audio or image synthesis, are going to be processing streams of data and in that context being able to just stream random bits out of a cache line and into registers and through operations without making a bunch of calls is going to produce some advantages, even if a modern out of order processor can hide a lot of that. TBH I doubt the function call overhead even matters so much as the overall structure being something that will approach the maximum throughput of your hardware.
It's a big advantage that the internal state of some PRNGs is very small, but you're still mutating the internal state, which means now you're creating dependency chains and dirtying a cache line, etc. Someone who's actually built chips before would know far better than me whether all of that adds up to a 1% hit to throughput or a 10% hit, though.
It's a big advantage that the internal state of some PRNGs is very small, but you're still mutating the internal state, which means now you're creating dependency chains and dirtying a cache line, etc. Someone who's actually built chips before would know far better than me whether all of that adds up to a 1% hit to throughput or a 10% hit, though.
MCG (like pcg64_fast) is like a single 128-bit mul and a mask. There’s not a lot of icache impact.
[deleted]
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...
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...
Dumb question: Why not just use AES? Most platforms have hardware acceleration so it should be pretty fast. Then there's no worrying about output quality.
(Is there an application for which AES is not fast enough? Has it been benchmarked for speed against the various PRNG options?)
(Is there an application for which AES is not fast enough? Has it been benchmarked for speed against the various PRNG options?)
Using AES-NI for small integer hashing in the Rust compiler was found to result in a measurable slowdown.
I think the biggest gains from AES-NI are when you can use the vectorized versions. So random byte generation would benefit, but small integer hashing probably not? (Unless you could arrange to hash a vector of integers at once.) But this isn't something I've tried myself.
Portability, most likely. I've seen AES-NI used as a convenient and fast PRNG but it would be a pretty sub-optimal choice for hardware platforms that don't have hardware acceleration.
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).
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 avoid this risk just by having a pretty gigantic and well mixed state, so any bad seed-- if one exists-- would be extremely unlikely to be hit. They also usually have structures that are 'close' to permutations which makes it hard for them to have small periods.)
For insecure small state RNGs the risk of small periods makes it useful to build RNGs based on structures that make it easy to know the period. Unfortunately, those same structures also tend to do things like make the RNG efficiently invertible.
Invertibility itself shouldn't be a problem since these sorts of non-cryptographic RNGs should never be used where security is a factor, but the existence of invertibility has a bad smell even when you're just concerned that the pattern of the RNG may trigger pathological behavior in the underlying system (as the structure of LCGs often does).
If it's not obvious to you why invertibility (or predictability in general) is a bad smell, think of it this way: Using the inversion I can create a randomness test that the RNG will fail (by recovering the state and checking it) and I can create an application that will fail using it. The application would be contrived, for sure, but it would exist. If we don't know how to predict the RNG then we also probably don't know how to create an application that will fail with it, even a contrived one (assuming the RNG otherwise has good statistical properties).
Though this only goes so far, because with a small state every RNG is going to be invertible (up to seeds with equal output) by an exhaustive test.
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 avoid this risk just by having a pretty gigantic and well mixed state, so any bad seed-- if one exists-- would be extremely unlikely to be hit. They also usually have structures that are 'close' to permutations which makes it hard for them to have small periods.)
For insecure small state RNGs the risk of small periods makes it useful to build RNGs based on structures that make it easy to know the period. Unfortunately, those same structures also tend to do things like make the RNG efficiently invertible.
Invertibility itself shouldn't be a problem since these sorts of non-cryptographic RNGs should never be used where security is a factor, but the existence of invertibility has a bad smell even when you're just concerned that the pattern of the RNG may trigger pathological behavior in the underlying system (as the structure of LCGs often does).
If it's not obvious to you why invertibility (or predictability in general) is a bad smell, think of it this way: Using the inversion I can create a randomness test that the RNG will fail (by recovering the state and checking it) and I can create an application that will fail using it. The application would be contrived, for sure, but it would exist. If we don't know how to predict the RNG then we also probably don't know how to create an application that will fail with it, even a contrived one (assuming the RNG otherwise has good statistical properties).
Though this only goes so far, because with a small state every RNG is going to be invertible (up to seeds with equal output) by an exhaustive test.
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.
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.
> 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
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
I don't disagree with anything specific that you said, but the reliance on "reasonable" means that you don't get a trivial guarantee about the lack of a short period from the structure itself.
The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.
The counter and truncated permutation will do so if the permutation is reasonable. If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.
The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.
The counter and truncated permutation will do so if the permutation is reasonable. If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.
> I don't disagree with anything specific that you said, but the reliance on "reasonable" means that you don't get a trivial guarantee about the lack of a short period from the structure itself.
I'm using "reasonable" here, because if the state-update function is an extremely weak and far-from-random permutation, like the identity, then the least-significant bits of the state will obviously display short cycles and, then, if your output function is also weak (e.g. simple truncation of most-significant bits), you may have short cycles in your output.
But, again, in such a case, you have a much bigger problem than "lack of lower bound on cycle length": your state-update function is not mixing your state, so you are 100% reliant on your output function to mix the state+counter. Also, if you go ahead and remove the counter, then you get a PRNG that always outputs the same thing (regardless of the chosen output function): clearly, you haven't picked a "reasonable" state-update function.
In a nutshell: if you don't actually have a PRNG (because both your state-update and output functions are trivially weak and non-mixing), then adding a counter won't magically turn it into a PRNG.
> The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.
...and you get that guarantee from the fact that a LFSR is a counter. So you're just reinforcing what I said, and what is stated in the paper I linked to: adding a counter to a (stateful or stateless) nonlinear function is the best/easiest way to ensure a lower bound on the cycle length of a PRNG of arbitrary structure.
> If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.
The chosen permutation does not have to have any special properties other than the ones that are already required for any usual PRNG (things like "changing a bit in the input should change each output bit with a probability of about 1/2").
The concrete definition of a "reasonable" PRNG is: either the state-update function or the output function of the PRNG must effectively mix the state (or both). Adding a counter will not turn an "unreasonable" PRNG into a "reasonable" PRNG: it will only take a "reasonable" PRNG and turn it into a "reasonable PRNG with lower bound on its cycle lengths".
I'm using "reasonable" here, because if the state-update function is an extremely weak and far-from-random permutation, like the identity, then the least-significant bits of the state will obviously display short cycles and, then, if your output function is also weak (e.g. simple truncation of most-significant bits), you may have short cycles in your output.
But, again, in such a case, you have a much bigger problem than "lack of lower bound on cycle length": your state-update function is not mixing your state, so you are 100% reliant on your output function to mix the state+counter. Also, if you go ahead and remove the counter, then you get a PRNG that always outputs the same thing (regardless of the chosen output function): clearly, you haven't picked a "reasonable" state-update function.
In a nutshell: if you don't actually have a PRNG (because both your state-update and output functions are trivially weak and non-mixing), then adding a counter won't magically turn it into a PRNG.
> The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.
...and you get that guarantee from the fact that a LFSR is a counter. So you're just reinforcing what I said, and what is stated in the paper I linked to: adding a counter to a (stateful or stateless) nonlinear function is the best/easiest way to ensure a lower bound on the cycle length of a PRNG of arbitrary structure.
> If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.
The chosen permutation does not have to have any special properties other than the ones that are already required for any usual PRNG (things like "changing a bit in the input should change each output bit with a probability of about 1/2").
The concrete definition of a "reasonable" PRNG is: either the state-update function or the output function of the PRNG must effectively mix the state (or both). Adding a counter will not turn an "unreasonable" PRNG into a "reasonable" PRNG: it will only take a "reasonable" PRNG and turn it into a "reasonable PRNG with lower bound on its cycle lengths".
This was always my complaint with PCG, that it talked about "difficulty to predict" and its suitability for... some kinds? of security applications? I don't know what those applications are, but somehow PCG targets them? If you care about this stuff, you should simply be using getrandom(2).
For what it's worth: I get why you'd want a high-quality generator of insecure random data (for simulations and stuff), and that there's an interesting discussion to have about what generator does the best job at handling that workload. I'm just saying it seems to have nothing to do with invertibility and crackability.