16 ms·

Gibson Research Corporation's Ultra-High Entropy Pseudo-Random Number Generator

67 points by Medea 4y ago

ttctciyf 4y ago
> Latin Squares are ‘n’x‘n’ grids containing exactly one of each of ‘n’ symbols in every horizontal row and vertical column [...] > Although mathematicians have been unable to determine how many different 26x26 [Latin] Squares can be created, they have been able to determine that the number is at least 9.337 x 10^426, or approximately 2^1418 Seems surprising that the number hasn't been calculated exactly. I'd have guessed it's a mechanically solvable but tedious combinatorics problem, but obviously not.
- ddulaney 4y ago
  It’s mechanically solvable but not in any practical timescale. A naive approach would be to check every square with no repeats in the rows, which requires (26!)^26 attempts, or roughly 5e691. Obviously you can improve that by exploiting symmetry, shifts, etc, but that only gets you a few orders of magnitude. There are much cleverer techniques, but when your baseline is so ludicrously impossible you need a real breakthrough to make any progress.
zinekeller 4y ago
Someone have claimed that this is broken: https://github.com/Sc00bz/break-uheprng https://github.com/Sc00bz/break-uheprng The first criticism, while valid, is an anachronism as there wasn't Web Crypto when this RNG was written. The other criticisms are fully valid though and should at least make everyone do a double take whether this is fine for their needs or not.
- panax 4y ago
  It is snake oil crypto. It is not safe for cryptographic use. I didn't see them claim that it can be used for cryptographic use on OP's page but they do claim it is a CSPRNG in the header in their js implementation: https://www.grc.com/js/uheprng.js https://www.grc.com/js/uheprng.js >This is GRC's cryptographically strong PRNG (pseudo-random number generator) Don't use it for security or crypto. A CSPRNG should not allow the internal state to be determined from observing the output. The hash function Mash() they use is not one-way and this break can reverse it. It does not provide prediction resistance or backtracking resistance.
contravariant 4y ago
Something about using a PRNG with a large internal state just to generate an output in a large space of possibilities feels wrong to me. If you have enough entropy to fill a high entropy RNG, why not use all that entropy to generate the output in the first place? Also I'm curious how they generate the latin squares, their claims require a uniform distribution of some kind, which is interesting.
- Iwan-Zotow 4y ago
  > If you have enough entropy to fill a high entropy RNG, why not use all that entropy to generate the output in the first place? Problem is the entropy generation rate. PRNG even with large space typically is running at 10 or better Gbit/sec. PCG with 256/64bit could generate decent numbers at 50Gbit/sec
  - contravariant 4y ago
    That's not entropy that is data. You fundamentally can't increase entropy, hence why they wanted to use a PRNG with a big internal state so they can put more entropy in. So if your argument is that you want a big entropy PRNG to get more possible outputs then the generation rate can't be the problem because that's entirely dependent on you being able to generate a big enough seed.
- dfox 4y ago
  The issue is that you cannot directly pick one of the outputs using the entropy, you have to use some kind of probabilistic algorithm to traverse the state space and find valid output. When the PRNG's cycle is smaller than the output space then the output distribution is obviously non-uniform. This might seem like inconsequential observation with CSPRNG, but depending on how exactly the state traversal works, such constructions can have real output spaces that are several orders of magnitude smaller than cycle of the used RNG. (to the extent that when used with (CS)PRNG with 128b state the output bias is observable from practical amount of outputs)
medimikka 4y ago
If the maker of ShieldsUp! claims anything, I am deeply, deeply, unconvinced.
- daniel-s 4y ago
  What's wrong with Shieldsup? My experience is that it works perfectly fine.
  - codazoda 4y ago
    Is this still a thing?!?
  - heleninboodler 4y ago
    I don't know if there's anything wrong with Sheildsup (other than my recollection of it being a pretty run of the mill tool for reporting open ports), but the guy who makes Shieldsup is, in my opinion, basically a charlatan. He writes loads and loads of technical-sounding blather on his website that is very transparently designed to make him look like an expert on security to people who don't know any better. He's made a career out of selling tools people don't need but which are hyped up to make them sound critically important. Here's an example of some hype I just found about a device he "invented" that is supposed to really put home routers through their paces, because he's the only one looking out for us. [1] Of course, it maybe doesn't exist, and his claims of what it's going to do sound far-fetched and misguided, but it sure does seem aimed to make him sound like a real security expert. Not sure if he ever made any claims about having evaluated any routers with it. [1] https://www.grc.com/r&d/assimilator.htm https://www.grc.com/r&d/assimilator.htm
    - ay 4y ago
      FWIW, he’s been at it for about 20 years.
      - killjoywashere 4y ago
        > he’s been at it for about 20 years. At least. I remember finding his site back in 2004 and it felt long in the tooth then. Complete with blink tags.
tom-thistime 4y ago
Sorry to belabor something lots of readers already know: The long key may (or may not) be packed with entropy. But a pseudo-random number generator at best preserves the entropy in the key.
- Mattasher 4y ago
  Very well put and worth reinforcing by thinking of PRNGs as entropy reduction functions on the original seeds, that ideally loose as little entropy as possible per generation cycle.
jrm4 4y ago
Can someone explain to me the value of this? Like, is there value in the "pseudo" that you don't get from a "real" one? Like, I'm thinking of e.g. the Cloudflare lava lamp thing, and like, isn't that better in every way?
- tenebrisalietum 4y ago
  Pure software can't actually generate mathematically-provable random numbers unless given purely random data to start with. So pseudo removes total dependency on physical events. Why you don't want to be dependent on physical events: - You never know if physical events are truly random unless you test them. Your physical RNG source may be broken or compromised. - A good strategy is to use multiple physical sources of randomness, and this can be any number of things, including modern CPUs with RDRAND (if you trust them), USB attached devices, sampling ADC noise on your sound card, timing network events, etc. Any/all of that has to be combined somehow anyway. Getting data from some of these may be slow. - So if an operating system needs random numbers quickly, for SSL key generation, UUIDs, nonces, etc. it should use properly seeded pseduorandom numbers.
  - ChrisSD 4y ago
    I'd also emphasise that fortunately most modern cryptography (outside of one time pads) does not rely on truly random numbers. So long as the sequence is unpredictable enough it's fine (i.e. you can't use known values to more reliably guess unknown values). The PRNG in the linked page isn't very good but in general PRNGs are super useful in the real world even if they aren't truly random, just so long as they have some source of entropy to occasionally mix into the PRNG.
  - RobotToaster 4y ago
    Wasn't there a company that used lava lamps to generate supposedly truly random numbers at one point?
    - tenebrisalietum 4y ago
      I want to say that was Cloudflare.
_joel 4y ago
Hrm, yea, sorry Steve but your dodgy practices mean that I'm not going to touch this with a barge pole.
- SixDouble5321 4y ago
  My guess is that you didn't need it anyway, and we didn't need your baseless ad hominem.
  - _joel 4y ago
    Baseless? You clearly know nothing about Steve Gibson then.
    - SixDouble5321 4y ago
      I welcome the opportunity to be enlightened. I can see people are mad about something, but usually that's the extent of it. Someone complained that there are no discounts on spinrite, even though it's old. Some people talk about how much salt you take Steve's words with. I have yet to read anything that explains the haters that come out of the woodwork with the shit posts any time he pops up.
aappleby 4y ago
This is not a good way to generate "secure" random numbers, and the "visits every possible state" is not a good metric. Computing the cryptographic hash of a 1536-bit counter will have better properties (and less handwaving) than this function.
- aappleby 4y ago
  Oh dear what is mash() even doing.....

67 points by Medea 4y ago

> Latin Squares are ‘n’x‘n’ grids containing exactly one of each of ‘n’ symbols in every horizontal row and vertical column [...] > Although mathematicians have been unable to determine how many different 26x26 [Latin] Squares can be created, they have been able to determine that the number is at least 9.337 x 10^426, or approximately 2^1418 Seems surprising that the number hasn't been calculated exactly. I'd have guessed it's a mechanically solvable but tedious combinatorics problem, but obviously not.

ddulaney 4y ago
It’s mechanically solvable but not in any practical timescale. A naive approach would be to check every square with no repeats in the rows, which requires (26!)^26 attempts, or roughly 5e691. Obviously you can improve that by exploiting symmetry, shifts, etc, but that only gets you a few orders of magnitude. There are much cleverer techniques, but when your baseline is so ludicrously impossible you need a real breakthrough to make any progress.

zinekeller 4y ago

Someone have claimed that this is broken: https://github.com/Sc00bz/break-uheprng https://github.com/Sc00bz/break-uheprng The first criticism, while valid, is an anachronism as there wasn't Web Crypto when this RNG was written. The other criticisms are fully valid though and should at least make everyone do a double take whether this is fine for their needs or not.

panax 4y ago
It is snake oil crypto. It is not safe for cryptographic use. I didn't see them claim that it can be used for cryptographic use on OP's page but they do claim it is a CSPRNG in the header in their js implementation: https://www.grc.com/js/uheprng.js https://www.grc.com/js/uheprng.js >This is GRC's cryptographically strong PRNG (pseudo-random number generator) Don't use it for security or crypto. A CSPRNG should not allow the internal state to be determined from observing the output. The hash function Mash() they use is not one-way and this break can reverse it. It does not provide prediction resistance or backtracking resistance.

contravariant 4y ago

Something about using a PRNG with a large internal state just to generate an output in a large space of possibilities feels wrong to me. If you have enough entropy to fill a high entropy RNG, why not use all that entropy to generate the output in the first place? Also I'm curious how they generate the latin squares, their claims require a uniform distribution of some kind, which is interesting.

Iwan-Zotow 4y ago
> If you have enough entropy to fill a high entropy RNG, why not use all that entropy to generate the output in the first place? Problem is the entropy generation rate. PRNG even with large space typically is running at 10 or better Gbit/sec. PCG with 256/64bit could generate decent numbers at 50Gbit/sec
- contravariant 4y ago
  That's not entropy that is data. You fundamentally can't increase entropy, hence why they wanted to use a PRNG with a big internal state so they can put more entropy in. So if your argument is that you want a big entropy PRNG to get more possible outputs then the generation rate can't be the problem because that's entirely dependent on you being able to generate a big enough seed.
dfox 4y ago
The issue is that you cannot directly pick one of the outputs using the entropy, you have to use some kind of probabilistic algorithm to traverse the state space and find valid output. When the PRNG's cycle is smaller than the output space then the output distribution is obviously non-uniform. This might seem like inconsequential observation with CSPRNG, but depending on how exactly the state traversal works, such constructions can have real output spaces that are several orders of magnitude smaller than cycle of the used RNG. (to the extent that when used with (CS)PRNG with 128b state the output bias is observable from practical amount of outputs)

medimikka 4y ago

If the maker of ShieldsUp! claims anything, I am deeply, deeply, unconvinced.

daniel-s 4y ago
What's wrong with Shieldsup? My experience is that it works perfectly fine.
- codazoda 4y ago
  Is this still a thing?!?
- heleninboodler 4y ago
  I don't know if there's anything wrong with Sheildsup (other than my recollection of it being a pretty run of the mill tool for reporting open ports), but the guy who makes Shieldsup is, in my opinion, basically a charlatan. He writes loads and loads of technical-sounding blather on his website that is very transparently designed to make him look like an expert on security to people who don't know any better. He's made a career out of selling tools people don't need but which are hyped up to make them sound critically important. Here's an example of some hype I just found about a device he "invented" that is supposed to really put home routers through their paces, because he's the only one looking out for us. [1] Of course, it maybe doesn't exist, and his claims of what it's going to do sound far-fetched and misguided, but it sure does seem aimed to make him sound like a real security expert. Not sure if he ever made any claims about having evaluated any routers with it. [1] https://www.grc.com/r&d/assimilator.htm https://www.grc.com/r&d/assimilator.htm
  - ay 4y ago
    FWIW, he’s been at it for about 20 years.
    - killjoywashere 4y ago
      > he’s been at it for about 20 years. At least. I remember finding his site back in 2004 and it felt long in the tooth then. Complete with blink tags.

tom-thistime 4y ago

Sorry to belabor something lots of readers already know: The long key may (or may not) be packed with entropy. But a pseudo-random number generator at best preserves the entropy in the key.

Mattasher 4y ago
Very well put and worth reinforcing by thinking of PRNGs as entropy reduction functions on the original seeds, that ideally loose as little entropy as possible per generation cycle.

jrm4 4y ago

Can someone explain to me the value of this? Like, is there value in the "pseudo" that you don't get from a "real" one? Like, I'm thinking of e.g. the Cloudflare lava lamp thing, and like, isn't that better in every way?

tenebrisalietum 4y ago
Pure software can't actually generate mathematically-provable random numbers unless given purely random data to start with. So pseudo removes total dependency on physical events. Why you don't want to be dependent on physical events: - You never know if physical events are truly random unless you test them. Your physical RNG source may be broken or compromised. - A good strategy is to use multiple physical sources of randomness, and this can be any number of things, including modern CPUs with RDRAND (if you trust them), USB attached devices, sampling ADC noise on your sound card, timing network events, etc. Any/all of that has to be combined somehow anyway. Getting data from some of these may be slow. - So if an operating system needs random numbers quickly, for SSL key generation, UUIDs, nonces, etc. it should use properly seeded pseduorandom numbers.
- ChrisSD 4y ago
  I'd also emphasise that fortunately most modern cryptography (outside of one time pads) does not rely on truly random numbers. So long as the sequence is unpredictable enough it's fine (i.e. you can't use known values to more reliably guess unknown values). The PRNG in the linked page isn't very good but in general PRNGs are super useful in the real world even if they aren't truly random, just so long as they have some source of entropy to occasionally mix into the PRNG.
- RobotToaster 4y ago
  Wasn't there a company that used lava lamps to generate supposedly truly random numbers at one point?
  - tenebrisalietum 4y ago
    I want to say that was Cloudflare.

_joel 4y ago

Hrm, yea, sorry Steve but your dodgy practices mean that I'm not going to touch this with a barge pole.

SixDouble5321 4y ago
My guess is that you didn't need it anyway, and we didn't need your baseless ad hominem.
- _joel 4y ago
  Baseless? You clearly know nothing about Steve Gibson then.
  - SixDouble5321 4y ago
    I welcome the opportunity to be enlightened. I can see people are mad about something, but usually that's the extent of it. Someone complained that there are no discounts on spinrite, even though it's old. Some people talk about how much salt you take Steve's words with. I have yet to read anything that explains the haters that come out of the woodwork with the shit posts any time he pops up.

aappleby 4y ago

This is not a good way to generate "secure" random numbers, and the "visits every possible state" is not a good metric. Computing the cryptographic hash of a 1536-bit counter will have better properties (and less handwaving) than this function.

aappleby 4y ago
Oh dear what is mash() even doing.....