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

31–40 of 54 posts

Re: Inverting the Xorshift128 random number generator

#31

Post by layer8 »

chaboud wrote: post #12
Aardwolf wrote: post #10

Xorshift128+ is not a cryptographic rng though, so at least this isn't a cryptographic attack... Should programming languages use cryptographic rngs like a ChaCha20 based one in their standard libraries to stop accidental use of non cryptographic rngs for cryptographic purposes? But that comes at the cost of speed

Perhaps put a warning in the name since the folks who don’t read the docs are the ones you’re trying to protect? For example: Math.RandomNotCrypto() When someone uses that in production for cryptographic purposes (and, yes someone is going to do that), they have to wear a dunce cap to the office for a month.

People are likely to use it in security-relevant ways without being aware that the use case constitutes “crypto”.

Re: Inverting the Xorshift128 random number generator

#32

Post by kevin_thibedeau »

Aardwolf wrote: post #10

Xorshift128+ is not a cryptographic rng though, so at least this isn't a cryptographic attack... Should programming languages use cryptographic rngs like a ChaCha20 based one in their standard libraries to stop accidental use of non cryptographic rngs for cryptographic purposes? But that comes at the cost of speed

No. Sometimes you want a reproducible PRNG sequence. These efforts to harden generators break the existing specifications with a rug pull.

Re: Inverting the Xorshift128 random number generator

#33

Post by wahern »

tptacek wrote: post #28
caspper69 wrote: post #26

Earlier quoted context omitted.

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

> Just make all the standard library random interfaces back onto a real CSPRNG

That's what OpenBSD has done for the traditional C and POSIX randomness APIs.

Also, re your earlier comment, OpenBSD's arc4random API is everywhere now except linux/musl and Windows. POSIX now has getentropy, which on recent Linux kernel will be as fast as arc4random_buf. But it would be nice if musl got the arc4random API, which includes arc4random_uniform for generating 32-bit numbers in the interval [0, N), minimizing the risk of people screwing that up.

Unlikely vendors will takes OpenBSD's approach to the historic PRNG APIs, but they're almost all there for the arc4random API. Also, the former approach is less ideal than it sounds; the latest versions of PUC Lua, for example, use an included non-CSPRNG rather than merely binding the historic C APIs. Explicitly using the arc4random API means the semantics are explicit, too, and you can more easily audit code. It's conspicuously missing an API for floating point intervals, but perhaps that'll come along.

Re: Inverting the Xorshift128 random number generator

#34

Post by hannob »

Aardwolf wrote: post #10

Xorshift128+ is not a cryptographic rng though, so at least this isn't a cryptographic attack... Should programming languages use cryptographic rngs like a ChaCha20 based one in their standard libraries to stop accidental use of non cryptographic rngs for cryptographic purposes? But that comes at the cost of speed

> But that comes at the cost of speed

That is mostly a myth.

I mean... technically, yes. But the cost is so marginal that you will have a hard time even measuring it unless you generate gigabytes of data.

For pretty much all common use cases like generation of ids, tokens, etc., you can use a secure random number generator and it will not impact your performance in any meaningful way.

Re: Inverting the Xorshift128 random number generator

#35

Post by m1el »

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

Exactly. I've implemented a xorshift-based rng inverter previously, and here's the implementation for the algorithm in the article:

https://github.com/m1el/samaras/blob/master/src/xorshift128....

Re: Inverting the Xorshift128 random number generator

#36

Post by Retr0id »

m1el wrote: post #35
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,…

Exactly. I've implemented a xorshift-based rng inverter previously, and here's the implementation for the algorithm in the article: https://github.com/m1el/samaras/blob/master/src/xorshift128....

Seeing your comment with the precomputed matrix reminded me of this visualisation I made: https://bsky.app/profile/retr0.id/post/3kc2rz7i7fm2y

Re: Inverting the Xorshift128 random number generator

#37

Post by Retr0id »

chaboud wrote: post #12
Aardwolf wrote: post #10

Xorshift128+ is not a cryptographic rng though, so at least this isn't a cryptographic attack... Should programming languages use cryptographic rngs like a ChaCha20 based one in their standard libraries to stop accidental use of non cryptographic rngs for cryptographic purposes? But that comes at the cost of speed

Perhaps put a warning in the name since the folks who don’t read the docs are the ones you’re trying to protect? For example: Math.RandomNotCrypto() When someone uses that in production for cryptographic purposes (and, yes someone is going to do that), they have to wear a dunce cap to the office for a month.

Math.random is a web API so you can't just rename it without breaking a large chunk of the web.

A non-breaking change would be to upgrade Math.random to be cryptographically secure - these days we know how to do this with minimal performance impact.

Re: Inverting the Xorshift128 random number generator

#38

Post by degamad »

01HNNWZ0MV43FF wrote: post #30
magicalhippo wrote: post #27

Earlier quoted context omitted.

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

I assume you're talking about

https://web.archive.org/web/20140210072712/http://www.laurad...

Previously on HN

https://news.ycombinator.com/item?id=7207851

Re: Inverting the Xorshift128 random number generator

#39

Post by Dylan16807 »

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

What's your threshold for "high performance"? A modern CPU can use a secure algorithm and produce more than one byte per cycle. Xorshift is a bit faster but not much faster.

Re: Inverting the Xorshift128 random number generator

#40

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…

> Xorshift128+ etc are around 10 to 30 times faster than ChaCha20.

What methods, what CPU? Is that using chacha20 a couple bytes at a time? If you generate your random bytes in medium size blocks you'll probably see a much smaller difference.

Post reply on HN