Hacker News Reader

Comment by jart | Hacker News Reader

Why is random so hard? If we assume best intentions then:

    uint64_t lemur64(void) {
      static uint128_t s =
        (uint128_t)426679527491843471ull << 64 | 2131259787901769494ull;
      return (s *= 15750249268501108917ull) >> 64;
    }

Passes bigcrush and PractRand and it won't ever cause your system to hang on boot.

View on HN

Yeah, but it always returns the same pseudo random sequence of numbers. THAT'S part of what they're trying to fix by including entropy.

what if you add timestamp?

From what source? That’s the hard part.

Think of it in terms of VM snapshots. If you boot from a snapshot, there’s no way to get any timestamp guaranteed to be secure.

But “secure” in this context is misleading. I subscribe to the “just use urandom” school of thought. It’s sufficiently secure in practice that no real security threats have emerged (can anyone point to a CVE?) and it seems like a waste of time to focus on this rather than the hundreds of other cases that cause dozens of CVEs.

The source shouldn't be an issue even if the timestamp is reused. Timestamps just don't add a ton of entropy - a timestamp is generally 64bits, so even if it were actually random you could only ever get 64bits of entropy. And it's obviously way way way less than that since the clock is probably somewhat accurate, the computer is probably less than ~10 years old, and it's probably not way in the future.

So it should be fine to add in, but I don't know how many bits you'd want to count that as.

Insufficient entropy is the root cause of this:

https://factorable.net/weakkeys12.extended.pdf

which is still happening:

https://www.quintessencelabs.com/wp-content/uploads/2020/03/...

That would also make it predictable. Essentially, if you get a sequence of random numbers, it should be quite hard to predict what the next one would be.

Yep, that is a good idea! But a timestamp only adds a little bit of entropy, and you want a few hundred if not a few thousand bits.

Then if I know about when you turned your computer on, I can guess every random number you'll ever generate.

Not all computers have a RTC.

The presence or absence of a real-time clock doesn't significantly change the problem here.

If they used a timestamp then all you really need is a couple random numbers to find the seed. Just keep guessing timestamps until you find a sequence that matches.

Here's a fun article about hacking online poker, in part by taking advantage of a time-based seed:

https://www.developer.com/guides/how-we-learned-to-cheat-at-...

"The system clock seed gave us an idea that reduced the number of possible shuffles even further. By synchronizing our program with the system clock on the server generating the pseudo-random number, we are able to reduce the number of possible combinations down to a number on the order of 200,000 possibilities. After that move, the system is ours, since searching through this tiny set of shuffles is trivial and can be done on a PC in real time."

What it will also do is to allow anyone to predict your pseudo random numbers with high accuracy. (which is bad, as the use case here is for security)

What kind of wizardry is this doing?! :)

Seems that's one of these: https://en.wikipedia.org/wiki/Lehmer_random_number_generator

It's one of the simplest ways to make random numbers. Multiply state by a constant, return the upper bits/digits of state.

There's some math that goes into picking a good constant, but honestly that's optional. Usually you'd also add a constant each round but this is going for absolute simplicity.

And the line with 'static' is just an awkward way of initializing the state integer.

Those numbers are not random.

> There's some math that goes into picking a good constant, but honestly that's optional.

It isn’t optional. For example, if your constant is even, every iteration adds another zero to the end of your state, and after (in this case) 127 iterations, you’ll start returning zeroes forever.

Also, if your multiplier is smallish, the lower order ones of the current value can be used to (somewhat) predict the higher order ones of the next value.

Yes it has to be odd and it has to be the size asked for. I don't count checking that as math.

If you're particularly worried about the top couple digits of the number being undersized you could return fewer bits or use a wider multiplier.

It’s a multiplicative congruential generator (MCG), a subset of linear congruential generators (LCG). Basically a multipy (and for LCG, an add) between each generated number. Very fast, small state requirements.

Wholly unsuitable for cryptographic random numbers.

Reply on news.ycombinator.com