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

Inverting the Xorshift128 random number generator

littlemaninmyhead.wordpress.com

Post reply on HN
Print view View original

21–30 of 54 posts

Re: Inverting the Xorshift128 random number generator

#21

Post by kstrauser »

thomasmg wrote: post #15
kstrauser wrote: post #11

Earlier quoted context omitted.

I think some naming conventions could go a long way. If you want to import `fast_unsafe_random`, you might think twice.

I agree, why would you slow down things for everybody if it's only a problem for cryptographic purposes. Xorshift128+ etc are around 10 to 30 times faster than ChaCha20. The challenge is things that don't _obviously_ need cryptographically secure generators. For example, do you need a secure generator for the seed of a hash table, or a sorting algorithm? (For those that do use a seed). Some will argue that yes, this…

Good point about the hashing. Python does the right thing by making you select the one you want when writing your own code. If it had a default option, make that SHA-256 so that all users get the strong one by default. But yes, if you’re not actually doing crypto stuff, say if you only want to see if two locally generated files have the same content, there are lots of much faster alternatives.

Re: Inverting the Xorshift128 random number generator

#22

Post by bazzargh »

tptacek wrote: post #18
bazzargh wrote: post #17

Earlier quoted context omitted.

A word of caution. A few years ago we had a production impact event where customers were getting identical cookies (and so started seeing each others sessions). When I took a look at the code, what I found was that they were doing something very like your code - using a time() based seed and an PRNG. Whenever we deployed new nginx configs, those servers would roll out and restart, getting _similar_ time() results in…

Why would you ever use an insecure RNG to generate a cookie?

In the code I saw, at least twice in its history people had introduced a "pure lua" solution for speed, and were clearly unaware of the shotgun they'd just pointed at their feet. (as in, somebody saw the issue and fixed it, and then someone else _fixed it back_ before I came along).

But in case _I'm_ messing up here, I'll bow to your expertise: libuuid uses /dev/random, which uses a CSPRNG (ChaCha20) with entropy ingested via Blake2 from whatever sources the system can get, right?

We did actually do a bunch of before/after testing showing the collision rates (zero after), and I believe the cookie in question has been replaced with a third party identity system in the intervening years - but if we did it wrong, I'd like to know.

Re: Inverting the Xorshift128 random number generator

#23

Post by Dylan16807 »

thomasmg wrote: post #15
kstrauser wrote: post #11

Earlier quoted context omitted.

I think some naming conventions could go a long way. If you want to import `fast_unsafe_random`, you might think twice.

I agree, why would you slow down things for everybody if it's only a problem for cryptographic purposes. Xorshift128+ etc are around 10 to 30 times faster than ChaCha20. The challenge is things that don't _obviously_ need cryptographically secure generators. For example, do you need a secure generator for the seed of a hash table, or a sorting algorithm? (For those that do use a seed). Some will argue that yes, this…

> why would you slow down things for everybody

Secure generators are still fast and the number of programs where you'd see a difference is very small.

Re: Inverting the Xorshift128 random number generator

#24

Post by akerl_ »

bazzargh wrote: post #22
tptacek wrote: post #18

Earlier quoted context omitted.

Why would you ever use an insecure RNG to generate a cookie?

In the code I saw, at least twice in its history people had introduced a "pure lua" solution for speed, and were clearly unaware of the shotgun they'd just pointed at their feet. (as in, somebody saw the issue and fixed it, and then someone else _fixed it back_ before I came along). But in case _I'm_ messing up here, I'll bow to your expertise: libuuid uses /dev/random, which uses a CSPRNG (ChaCha20) with entropy ing…

I think the question isn’t “why switch it to libuuid”, it’s “why is anybody ever setting it to a time-based non-CS PRNG”.

Re: Inverting the Xorshift128 random number generator

#25

Post by jandrewrogers »

bazzargh wrote: post #17
delduca wrote: post #8

I have recently replaced Lua's random for this implemetation https://nullonerror.org/2025/08/02/replacing-lua-s-math-rand...

A word of caution. A few years ago we had a production impact event where customers were getting identical cookies (and so started seeing each others sessions). When I took a look at the code, what I found was that they were doing something very like your code - using a time() based seed and an PRNG. Whenever we deployed new nginx configs, those servers would roll out and restart, getting _similar_ time() results in…

UUIDv4 is banned in some environments because of how common it is to find someone using weak PRNGs to generate them. It happens way more often than it should.

Re: Inverting the Xorshift128 random number generator

#26

Post by caspper69 »

kstrauser wrote: post #20
tptacek wrote: post #16

Earlier quoted context omitted.

I think people overthink this, and we should just have a library standard full-strength CSPRNG, and then people with fussy fast-randomness needs (Monte Carlo or whatever) can just pull in libraries. "Don't need secure random and can't use it " is a very niche problem space. It'll never happen in Go though! They're over a decade committed to this library shape.

I strongly agree here. The default should be strong, “slow” randomness. If you know you need something different in your specific use case, and just can’t abide the safe version, import something else.

I agree. .NET is the opposite of Go. Calls to System.Random use Xoshiro128++ under the hood (as of .NET 6 I believe). On the other hand, calls to RandomNumberGenerator.GetBytes() are cryptographically secure, using the Windows kernel cryptographic provider on Windows and /dev/urandom (chacha20) on Linux and arc4random_buf() on MacOS (which also uses chacha20 under the hood).

I ported around 20 RNGs to C# (all non-cs), and there are tons of uses for non-cryptographic RNGs, so I'm a little torn. I guess in modern development most people who need an RNG need it for crypto purposes (I would guess salts, keys and nonces mostly), but I'd hate to see all the Xoshiros, Mersenne Twisters, PCGs, and MWCs, etc. go the way of the dodo simply because they are not deemed fit for crypto purposes. Games, simulations, non-cryptographic hashes all need deterministic and high performance RNGs, and don't need all of the cryptographic guarantees.

To top it off, there is no standard definition of what makes an RNG cryptographically secure, so it's a slightly loaded question anyway. Everything I've read says an algo needs the following properties: forward secrecy (unable to guess future outputs given the current state), backward secrecy (if I know current outputs, I shouldn't be able to recover previous internal state or previous outputs), and the output must be indistinguishable from true random bits, even with a chosen-input attack. This is where I politely defer to the expert mathematicians and cryptographers, because I'm not equipped to perform such an analysis.

I can understand why things have developed this way though- people have needed random numbers far longer than they've needed cryptographically secure random numbers, so the default is the non-cryptographically secure variant. A language created tomorrow would likely follow in Go's footsteps and default to the cryptographically secure.

Re: Inverting the Xorshift128 random number generator

#27

Post by magicalhippo »

bazzargh wrote: post #17
delduca wrote: post #8

I have recently replaced Lua's random for this implemetation https://nullonerror.org/2025/08/02/replacing-lua-s-math-rand...

A word of caution. A few years ago we had a production impact event where customers were getting identical cookies (and so started seeing each others sessions). When I took a look at the code, what I found was that they were doing something very like your code - using a time() based seed and an PRNG. Whenever we deployed new nginx configs, those servers would roll out and restart, getting _similar_ time() results in…

Had this issue on a ray tracer I worked on. Since sampling was supposed to be random, you could fire it up on multiple machines and just average the result to get a lower noise image.

Except the distributed code fired it up all worker instances almost simultaneously and the code used time() to seed the RNG, so many workers ended up using the same seed and hence averaging those results did nothing.

Re: Inverting the Xorshift128 random number generator

#28

Post by tptacek »

caspper69 wrote: post #26
kstrauser wrote: post #20

Earlier quoted context omitted.

I strongly agree here. The default should be strong, “slow” randomness. If you know you need something different in your specific use case, and just can’t abide the safe version, import something else.

I agree. .NET is the opposite of Go. Calls to System.Random use Xoshiro128++ under the hood (as of .NET 6 I believe). On the other hand, calls to RandomNumberGenerator.GetBytes() are cryptographically secure, using the Windows kernel cryptographic provider on Windows and /dev/urandom (chacha20) on Linux and arc4random_buf() on MacOS (which also uses chacha20 under the hood). I ported around 20 RNGs to C# (all non-cs)…

No, CSPRNG vs. RNG isn't a loaded question. Every RNG that says "this isn't an according-to-Hoyle cryptographically random number generator, but..." isn't one. Most modern CSPRNGs are designed with well-understood cryptographic primitives, so they draft off those security properties. Establishing those properties for a novel set of primitives is a major undertaking.

It's a little frustrating, because there are definitely fast RNGs that have tried to blur this line. A reasonable first approximation of the current situation is that a CSPRNG should have somewhere in its core a mixing function based on an actual cryptographic hash or permutation function; if the design has to explain what that function is and how it works (as opposed to just saying "this is ChaCha20"), it's not secure. These fast RNGs, like Xorshiro and PCG, all get there by not having cryptographically strong mixing functions at their core.

For what it's worth, I think the "GetBytes() means secure, IntN() means it's not secure" is a clever misfeature. Just make all the standard library random interfaces back onto a real CSPRNG, and let people pull in PCG or whatever if they have specialized needs for fast insecure RNGs.

Re: Inverting the Xorshift128 random number generator

#29

Post by viraNtor »

tptacek wrote: post #6
Retr0id wrote: post #5

If you represent the state as a 128-long vector of GF(2) elements, you can model the state transition function as a matrix multiplication. This allows you to describe any output bit (at any offset in the output stream) as a function of the 128 initial state elements. Treating the initial state vector as 128 unknown variables, you can solve for them (via gaussian elimination) with any 128 bits from the output stream,…

If you follow the ChatGPT log, that's the angle he takes as well.

Which ChatGPT version was used? 4o? 5? It's clear from the log it suffers from serious context problems, keeps forgetting/hallucinating functions and forgetting arguments to functions is has already written.

Re: Inverting the Xorshift128 random number generator

#30

Post by 01HNNWZ0MV43FF »

magicalhippo wrote: post #27
bazzargh wrote: post #17

Earlier quoted context omitted.

A word of caution. A few years ago we had a production impact event where customers were getting identical cookies (and so started seeing each others sessions). When I took a look at the code, what I found was that they were doing something very like your code - using a time() based seed and an PRNG. Whenever we deployed new nginx configs, those servers would roll out and restart, getting _similar_ time() results in…

Had this issue on a ray tracer I worked on. Since sampling was supposed to be random, you could fire it up on multiple machines and just average the result to get a lower noise image. Except the distributed code fired it up all worker instances almost simultaneously and the code used time() to seed the RNG, so many workers ended up using the same seed and hence averaging those results did nothing.

I am reminded of an article about a poker site:

"There are 52-factorial ways to shuffle a deck of cards, but the site's PRNG only has 32 bits of state. 4 billion is alarmingly less than 52-factorial! But even worse, the PRNG is seeded using the number of milliseconds since midnight. 86 million is alarmingly less than 4 billion!"

So the actual entropy on the card table was equivalent to about 5 cards' worth. After seeing the 2 cards in his hand, and the 3 cards in the flop, he could use a program to solve for every other card in everyone's hand and in the entire deck!

(I may have mixed up many details - If anyone has an archive of the article please post it!)

Post reply on HN