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

https://www.grc.com/otg/uheprng.htm

by Medea • 3 years ago

67 57 3 years ago

ttctciyf• 3 years 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• 3 years 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• 3 years ago

Someone have claimed that this is broken: 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• 3 years 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

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.

contravariant2• 3 years 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• 3 years 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

contravariant2• 3 years 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• 3 years 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• 3 years ago

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

daniel-s• 3 years ago

What's wrong with Shieldsup? My experience is that it works perfectly fine.

codazoda• 3 years ago

Is this still a thing?!?

heleninboodler6• 3 years 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

InCityDreams• 3 years ago

I still use the DNS speed finder.

CyberDildonics3• 3 years ago

Is this a joke? What does that mean?

MertsA2• 3 years ago

Forget "ShieldsUp!" This is the guy who still sells SpinRite for $90 when it hasn't seen an update since 2004. It's old enough to vote at this point and Steve Gibson is always spouting off blatant lies about how it's great for recovering SSDs. He's claimed that it can magically read uncorrectable sectors on modern drives (SATA, not SAS, no SCSI READ LONG here and no ancient IDE drives that still supported READ LONG for ATA) and compare results to figure out what the original data was. He claims that it's data recovery software and that people should run it on a failing hard drive before trying to copy data off of it with a real data recovery program! That piece of garbage doesn't even support writing data to a separate disk, the only thing it can do is write the data the drive was able to read back to the failing drive itself.

The technical documentation claims stuff like that it disables bad sector allocation. That's actually a thing, but if you read the man page for some reputable software like hdparm you'll see a nice little note:

Control of this feature via the -D option is not supported for most modern drives since ATA-4; thus this command may fail.

ATA-4 was standardized in 1998. It can probably actually disable write caching, but it's not like that's unique to SpinRite in the slightest. It's even trivial to change that on Windows which is otherwise horrible for anything low level involving disks. SpinRite doesn't even use LBA48 addressing so if your drive can't address the full capacity in ye olde CHS then too bad, but SpinRite will try to spin that as a problem with your BIOS, a problem with your SATA controller, etc.

I don't see why anyone respects anything he says given his long history of selling snake oil and other shyster tactics. Even the Wikipedia page for SpinRite looks astroturfed and the talk section has a bunch of responses from an unregistered user that all seem to have a similar tone and be suspiciously supportive of some of SpinRite's dubious claims.

If Steve Gibson told me that the sky was blue I think I'd have to go outside and check.

http://www.hddoracle.com/viewtopic.php?f=181&t=2929

pdonis3• 3 years ago

For a similar take on Gibson, see here:

https://radsoft.net/news/roundups/grc/

SixDouble53216• 3 years ago

Doesn't sound like you have used Spinrite, but if you don't think it's worth the money don't buy it. Not sure what makes you think a developer has to reduce the price of their software, just because it's old. Adobe has done no such thing. The software still does what it did when it was first made. If you have a bug report, file it, my guess is that you don't.

tom-thistime• 3 years 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• 3 years 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• 3 years 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?

tenebrisalietum2• 3 years 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• 3 years 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• 3 years ago

Wasn't there a company that used lava lamps to generate supposedly truly random numbers at one point?

_joel2• 3 years ago

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

SixDouble53216• 3 years ago

My guess is that you didn't need it anyway, and we didn't need your baseless ad hominem.

_joel2• 3 years ago

Baseless? You clearly know nothing about Steve Gibson then.

aappleby2• 3 years 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.

aappleby2• 3 years ago

Oh dear what is mash() even doing.....

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

Related Stories