A Brief History of Random Numbers • Hacker News Board

Re: A Brief History of Random Numbers

#51

Post by oconnor663 » Sun, Feb 19, 2023, 6:02 AM UTC

SideQuark wrote: post #44

nemo1618 wrote: post #42

Earlier quoted context omitted.

> There's not an infinite amount of crypto secure randomness available for all processes to go nuts sucking it up In fact, there is! The idea that your kernel has some finite amount of entropy that can be "used up" is a persistent myth. See https://www.2uo.de/myths-about-urandom/ Okay, it's technically not infinite , but 128 bits of "true entropy" is enough to seed a CSPRNG that will generate as many random numbers a…

>The idea that your kernel has some finite amount of entropy that can be "used up" is a persistent myth Thomas' Digital Garden blog is not really the place to find good advice on this. Crypto researchers are the place to look. The quality of how Linux handles this is quite open to debate, and researchers routinely question the choies made. Here's [1] one of many. Use Google Scholar, enter urandom, and limit the searc…

> Thomas' Digital Garden blog is not really the place to find good advice on this.

I prefer DJB's blog on this: https://blog.cr.yp.to/20140205-entropy.html

>> The Linux /dev/urandom manual page claims that without new entropy the user is "theoretically vulnerable to a cryptographic attack", but (as I've mentioned in various venues) this is a ludicrous argument—how can anyone simultaneously believe that

>> - we can't figure out how to deterministically expand one 256-bit secret into an endless stream of unpredictable keys (this is what we need from urandom), but

>> - we can figure out how to use a single key to safely encrypt many messages (this is what we need from SSL, PGP, etc.)?

Re: A Brief History of Random Numbers

#52

Post by espadrine » Sun, Feb 19, 2023, 9:43 AM UTC

camel-cdr wrote: post #30

espadrine wrote: post #25

Earlier quoted context omitted.

Not all of them, but ChaCha8 (which many renowned cryptographers consider secure[0]) is in the same ballpark as the most common ones[1]. (A few notes on the second link: I wouldn’t recommend xoshiro256+x8 since it is very weak statistically, same for xoshiro256 IMO. Also, disclaimer, I wrote SHISHUA.) [0]: https://eprint.iacr.org/2019/1492.pdf [1]: https://github.com/espadrine/shishua#comparison

Wasn't xoshiro256+ mostly weak in the lower bits, and recommended to use to generate floating point numbers? I suppose that this is probably indicative of a more fundamental weakness, but for reference the upper bits should be way higher quality that the Messene Twister (As that one fails PractRand while the upper bits of xoshiro256+ don't IIRC)

Yes, but it is also weak in terms of seed correlation, which makes xoshiro256+x8 weak in many more bits.

That said, there are certainly use-cases for it! I just like the idea that we can have our cake and eat it too: something closer to the Pareto frontier, that doesn’t have those caveats, and yet is faster.

Re: A Brief History of Random Numbers

#53

Post by nemo1618 » Sun, Feb 19, 2023, 5:51 PM UTC

SideQuark wrote: post #44

nemo1618 wrote: post #42

Earlier quoted context omitted.

> There's not an infinite amount of crypto secure randomness available for all processes to go nuts sucking it up In fact, there is! The idea that your kernel has some finite amount of entropy that can be "used up" is a persistent myth. See https://www.2uo.de/myths-about-urandom/ Okay, it's technically not infinite , but 128 bits of "true entropy" is enough to seed a CSPRNG that will generate as many random numbers a…

>The idea that your kernel has some finite amount of entropy that can be "used up" is a persistent myth Thomas' Digital Garden blog is not really the place to find good advice on this. Crypto researchers are the place to look. The quality of how Linux handles this is quite open to debate, and researchers routinely question the choies made. Here's [1] one of many. Use Google Scholar, enter urandom, and limit the searc…

> Developers have decided to conflate actual entropy with "hard to compute," which is simply not true.

True, they are different, but there is no meaningful distinction between a value that is "truly random" and a value that can be computed with a computer larger than the universe.

> eventually, like all crypto, the method will break

It's disheartening to see this claim being made by someone who regularly works on crypto code. When it comes to symmetric encryption, the war between cryptographers and cryptanalysts is over -- and the cryptographers have won. The security margin provided by modern ciphers like ChaCha20 is so high, and attacks on them so pitiful, that there are now calls for reducing the strength of ciphers in order to increase performance without sacrificing a meaningful amount of security: https://eprint.iacr.org/2019/1492

ChaCha20 will not be broken in our lifetime; probably it will never be broken, in the sense that an attacker will be able to observe any subset of the keystream and predict the next block (which is what we need from a CSPRNG).

Anyway, given these premises (which AFAIK we both agree on):

  1) There is no "one-size-fits-all" RNG
  2) Using a PRNG instead of a CSPRNG may lead to security vulnerabilities
  3) Using a CSPRNG instead of a PRNG may lead to performance degradation

Which type of RNG should be the default (e.g. the one you get if you type 'import rng'), and which type should the programmer have to ask for specifically? That's the question at hand here.

Re: A Brief History of Random Numbers

#54

Post by SideQuark » Mon, Feb 20, 2023, 6:42 PM UTC

oconnor663 wrote: post #51

SideQuark wrote: post #44

Earlier quoted context omitted.

>The idea that your kernel has some finite amount of entropy that can be "used up" is a persistent myth Thomas' Digital Garden blog is not really the place to find good advice on this. Crypto researchers are the place to look. The quality of how Linux handles this is quite open to debate, and researchers routinely question the choies made. Here's [1] one of many. Use Google Scholar, enter urandom, and limit the searc…

> Thomas' Digital Garden blog is not really the place to find good advice on this. I prefer DJB's blog on this: https://blog.cr.yp.to/20140205-entropy.html >> The Linux /dev/urandom manual page claims that without new entropy the user is "theoretically vulnerable to a cryptographic attack", but (as I've mentioned in various venues) this is a ludicrous argument—how can anyone simultaneously believe that >> - we can't…

So you'll believe a 2014 djb blog post over the following near decade of peer-reviewed research?

That's how we got here.....

Re: A Brief History of Random Numbers

#55

Post by SideQuark » Mon, Feb 20, 2023, 7:10 PM UTC

nemo1618 wrote: post #53

SideQuark wrote: post #44

Earlier quoted context omitted.

>The idea that your kernel has some finite amount of entropy that can be "used up" is a persistent myth Thomas' Digital Garden blog is not really the place to find good advice on this. Crypto researchers are the place to look. The quality of how Linux handles this is quite open to debate, and researchers routinely question the choies made. Here's [1] one of many. Use Google Scholar, enter urandom, and limit the searc…

> Developers have decided to conflate actual entropy with "hard to compute," which is simply not true. True, they are different, but there is no meaningful distinction between a value that is "truly random" and a value that can be computed with a computer larger than the universe. > eventually, like all crypto, the method will break It's disheartening to see this claim being made by someone who regularly works on cry…

>True, they are different, but there is no meaningful distinction between a value that is "truly random" and a value that can be computed with a computer larger than the universe.

Sloppy thinking and conflating different ideas are not a good way to think about computer security.

>ChaCha20 will not be broken in our lifetime; probably it will never be broken

As was said of the zillion currently broken cryptosystems, hashes, and all manner of security schemes......

> the cryptographers have won.

Is this why NIST routinely is asking for better crypto systems? Because crypto is solved?

> there are now calls for reducing the strength https://eprint.iacr.org/2019/1492

Yet followup papers often invent new methods of attack https://eprint.iacr.org/2022/695. It's almost as if theoretical advances can change the unproven-yet-assumed strength of previous methods.

>Which type of RNG should be the default (e.g. the one you get if you type 'import rng')

I already demonstrated that answer is PRNG for pretty much all widely use languages, which I agree with. There's simply no CSPRNG possible that ports over the widespread systems these languages are used for, so it's silly to continue to argue that they should default to a CSPRNG. CSPRNGs are not used by default, have never been, there is no trend to move that way I can find, all for the reasons I gave my very first reply in this thread.