Cracking random number generators (xoroshiro128+)

https://lemire.me/blog/2017/08/22/cracking-random-number-generators-xoroshiro128/

by johndcook • 9 years ago

109 56 9 years ago

pbnjay3• 9 years ago

Author's title should be "Cracking PSEUDO-random number generators" - We should all basically assume that any PRNG will be easily cracked like this and not use them for anything important to security!

Always use a cryptographic RNG for important code!

anfractuosity2• 9 years ago

Aren't cryptographic random number generators, still PRNGs.

It sounds a fun problem, predicting the future random numbers, going to have to have a play later at trying it.

hlieberman• 9 years ago

Yes. GP is mistaken here; this is novel work that is somewhat concerning -- mostly in how it might apply to other similarly state-based RNGs.

DiThi5• 9 years ago

Strong crypto RNGs use PRNGs but combines sources of entropy, environmental noise from devices such as the number of CPU cycles between user keystrokes. T̶h̶a̶t̶'̶s̶ ̶t̶h̶e̶ ̶d̶i̶f̶f̶e̶r̶e̶n̶c̶e̶ ̶b̶e̶t̶w̶e̶e̶n̶ ̶/̶d̶e̶v̶/̶r̶a̶n̶d̶o̶m̶ ̶a̶n̶d̶ ̶/̶d̶e̶v̶/̶u̶r̶a̶n̶d̶o̶m̶ ̶i̶n̶ ̶L̶i̶n̶u̶x̶.̶

tptacek7• 9 years ago

This shouldn't have been downvoted because it is exactly correct.

Cryptographic generators don't work like PCG and xoroshiro and Mersenne Twister. They're generally built by taking a cryptographically secure cipher or hash core, "keying" it with secret entropy, and running it in a streaming configuration (like CTR mode).

A properly designed CSPRNG can only be "cracked" in a few specific scenarios:

1. The primitive it's built on (or the streaming construction it's configured in) is broken, in which case the news for cryptography as a field is significantly bigger than the fact that an RNG has a flaw.

2. An attacker has exploited a systems flaw to directly disclose the contents of the memory the CSPRNG is operating out of, in which case you have bigger problems than your CSPRNG.

3. The secrets that key the generator have become predictable. This is in practice the only way CSPRNGs get broken (unintentionally), and, in practice, always means the CSPRNG wasn't initialized properly (the "cold start entropy problem").

You should use the getrandom() system call, or read from /dev/urandom, to the exclusion of all other mechanisms.

baby• 9 years ago

FWIW you rarely hear the term CSPRNG in crypto I find. I always call these PRNGs but I can see how having a naming distinction could help prevent misuse in the applied world.

Edit: thinking a bit more about it. I guess it wouldn't make sense to call anything "crypto" in crypto. It's like calling fries "french fries" in France. There they're just fries. I know this is a bad example because french fries are probably not from France :o)

IanCal• 9 years ago

I'd have called that a PRNG, because to me there were only two main categories. Pseudo-random, where it's designed to be unpredictable, and actually random where it is based on an external hardware source of true random information.

A CSPRNG is surely a type of PRNG. Is that not right?

Their comment doesn't really seem correct to me. The title is "Cracking random number generators (xoroshiro128+)" which seems pretty accurate to me. The article definitely doesn't seem to say it's breaking anything other than a very specific, flawed random number generator.

imaginenore2• 9 years ago

Can you crack this PRNG without knowing the seed?

    f(1) = 1 // seed

    f(n) = sha512(f(n-1) . f(1))

sdevlin• 9 years ago

I guess it depends what you mean by “crack”. Given f(1), which I assume is public, you can predict all future outputs.

mdpopescu• 9 years ago

This is similar to Yarrow / Fortuna (internal state is a counter, output is the hash of the state) so I'm guessing it's not breakable, at least not trivially.

VikingCoder• 9 years ago

"Always use a cryptographic PSUEDO-RNG for important code!"

Just because it's "cryptographic" doesn't mean it's not pseudo-random.

TACIXAT• 9 years ago

Hey, author of the SMT attack here. There is probably a clever way to go after XorShift128+ as well, symbolic execution using an SMT solver is basically a brute-force solution.

I'll have to give this challenge a shot later.

aj7• 9 years ago

Ha ha! By going to your predictions page I can crack you! Great post.

xoroshiro• 9 years ago

As someone who first learned how to program by implementing PRNGs but never really digging deeper into it, I found this post very interesting to read. I do have an idea about some (small portion) of the things behind it, but I have no background in cryptography.

Looking at the other posts, it seems like most PRNGs are fine for non-cryptographic applications, but what are other ways to make PRNG's though? Everything I've learned (mostly simple stuff; Linear Congruential, Midsquare, etc.) seem to need to store a state to work, because otherwise, wouldn't you just output the same thing over and over again? I know there's stuff like /dev/random (though I'm unsure how that works), but that doesn't seem like a good idea for getting a lot of numbers.

andrewla• 9 years ago

Professor O'Neill (mentioned in the article) has written a PRNG [1]. The jury is still out on how powerful it is in general. There continue to be fights between what it means to be random for cryptographic purposes vs. numerical analysis purposes.

That said, the PDF on that site that serves as a writeup for PCG contains a nice discussion of the links between the size of the state held and the strength of the algorithm, including a discussion of the state of the art for crypto- and non-crypto- PRNGs.

[1] http://www.pcg-random.org/

tptacek7• 9 years ago

There is in fact no real debate about what's required for an RNG to be suitable for security purpose. The standard for security is cryptographic. To design a new secure RNG, you effectively need to design a new cryptographic primitive (most likely, a new native stream cipher).

There may indeed be some debate about the requirements for non-security numerical analysis applications.

Most development platforms should be defaulting to secure random number generators, and most developers should be reaching for secure random number generators as their default choice. Neither PCG nor xorshiro128 are examples of these.

nolemurs• 9 years ago

The article is a serious waste of time.

It can be summarized as "Non cryptographic PRNGs can be predicted! Look, I cracked this one! I'm not going to tell you how I did it though."

There's no exposition describing non cryptographic PRNGs, nor any evidence given for why they're not sound beyond the author's assertion that he cracked one.

To be clear, non cryptographic PRNGs are often predictable, and shouldn't be used if that's a problem, but if you're interested in learning more about that, this article isn't going to help you much.

Skip the read.

zb3• 9 years ago

This problem can be solved using Z3: https://gist.github.com/zb3/c59cf596ce80c501db5ca16c31a1c3a7

I don't know whether autor used solver or some other magic method... Solutions should be available to those who want to see them.

edflsafoiewq• 9 years ago

Does anyone know how the constants in xoroshiro128+ were chosen?

Cracking random number generators (xoroshiro128+)

Related Stories