News for hackers. Stuff that matters.
Re:Problems emerge for a unified /dev/*random by codeflo on Tuesday March 29, 2022 @07:03PM (#30849446)
These random/urandom blocking/nonblocking discussions have been going on for at least a decade at this point, maybe even longer. I get that RNG algorithms are hard. What’s surprising to me is that it seems so hard to even figure out the desired interface of such a basic thing in the kernel. Security in entropy-starved environments seems to be very hard to square with backwards compatibility.
Re:Problems emerge for a unified /dev/*random by tptacek on Tuesday March 29, 2022 @08:24PM (#30850109)
It's not hard by itself. These interfaces are actually pretty straightforward to design and implement; Linux made things hard for itself by designing a weirdly complicated interface with an entropy credit system, an idea that's more or less discredited now.

What's hard is accurately surveying the last 15 years of systems built on top of Linux's needlessly-complicated LRNG and making changes that don't violate the expectations of those systems. Nobody should be running "jitter entropy daemons" in userland (userland RNGs are essentially the source of all practical CSPRNG vulnerabilities in the past 2 decades), but people do, and if those systems exceeded some threshold of security before Donenfeld's patches, you can't merge those patches if they push security below that threshold.

It's a really irritating problem.

Re:Problems emerge for a unified /dev/*random by yxhuvud on Wednesday March 30, 2022 @12:33AM (#30851507)
Also,the problems seems mostly to be around Linux running in a VM rather than on actual hardware. Would it be possible to have the host urandom show up as a hw random number generator to the VM and then use that for initiating things? Seems less hacky than having to fiddle with seeds. Dunno how possible that is though.
Re:Problems emerge for a unified /dev/*random by pm215 on Wednesday March 30, 2022 @05:53AM (#30853198)
You can do that where for instance the VM has PCI and can plug in a virtio RNG device. But a lot of the QEMU setups Guenter Roeck reported issues with are emulating real (usually old) hardware which didn't have a PCI bus, or any other hardware RNG interface.
Re:Problems emerge for a unified /dev/*random by mjevans on Wednesday March 30, 2022 @06:19AM (#30853340)
Also lighter systems such as routers (E.G. many OpenWRT targets)
Re:Problems emerge for a unified /dev/*random by loeg on Wednesday March 30, 2022 @01:43AM (#30851825)
Re:Problems emerge for a unified /dev/*random by AnssiH on Wednesday March 30, 2022 @05:18AM (#30852978)
Yes, and that is commonly used.

But Linux must continue to work even on VMs without that, and that is the hard part.

Re:Problems emerge for a unified /dev/*random by loeg on Wednesday March 30, 2022 @10:46AM (#30855935)
The VMs described in the article are (faithfully) emulating real hardware lacking unpredictable timers or other sources of entropy. It’s not exclusively a VM problem; it’s a weird/old hardware problem, too.
Re:Problems emerge for a unified /dev/*random by cperciva on Tuesday March 29, 2022 @09:19PM (#30850483)
an entropy credit system, an idea that's more or less discredited now

... no pun intended, I'm sure.

Re:Problems emerge for a unified /dev/*random by tptacek on Tuesday March 29, 2022 @09:45PM (#30850627)
Nope, just coming off a migraine and not catching stuff like that. :)
Re:Problems emerge for a unified /dev/*random by rocqua on Wednesday March 30, 2022 @04:31AM (#30852694)
> userland RNGs are essentially the source of all practical CSPRNG vulnerabilities in the past 2 decades

Is your point that CSPRNGs should not be implemented in userland, but instead should just read from /dev/random or do the equivalent on non-linux opperating systems?

Re:Problems emerge for a unified /dev/*random by loeg on Wednesday March 30, 2022 @10:48AM (#30855957)
Yes, that’s been Thomas’s position for many years[1]. And I mostly agree with him on that.

[1]: https://sockpuppet.org/blog/2014/02/25/safely-generate-rando...

Re:Problems emerge for a unified /dev/*random by raverbashing on Wednesday March 30, 2022 @06:22AM (#30853350)
> What's hard is accurately surveying the last 15 years of systems built on top of Linux's needlessly-complicated LRNG and making changes that don't violate the expectations of those systems.

Sounds like they need a compatibility or feature (cmdline) flag.

Add the flag and you can use the new improved system. Establish dates for when the old method will not be the default anymore (but can be used with the flag) and when it will be deprecated for good

Re:Problems emerge for a unified /dev/*random by larusso on Wednesday March 30, 2022 @06:39AM (#30853447)
That won‘t align with the never break the user mantra. And honestly I hate these timebomb solutions some API vendors put up. In a never breaking system you can‘t remove anything only add things or change stuff internally to make it work like before. They never said to get rid of /dev/random or /dev/urandom just that both would practically be the same. From reading about the problem and the different usecases and expectations it looks like it will stay like this for another decade or more.
Re:Problems emerge for a unified /dev/*random by amelius on Wednesday March 30, 2022 @05:26AM (#30853034)
> Nobody should be running "jitter entropy daemons" in userland (userland RNGs are essentially the source of all practical CSPRNG vulnerabilities in the past 2 decades), but people do, and if those systems exceeded some threshold of security before Donenfeld's patches, you can't merge those patches if they push security below that threshold.

Why not break their code? Seems justified in this case.

Re:Problems emerge for a unified /dev/*random by Quekid5 on Wednesday March 30, 2022 @06:37AM (#30853427)
For better or worse Linux doesn't break userland.
Re:Problems emerge for a unified /dev/*random by jonhohle on Tuesday March 29, 2022 @07:39PM (#30849753)
I ran into it the first time in 2005 and it was a widely known issue, easy to find if you could find where your program was pseudo-randomly blocking (pun intended). FreeBSD already had unified random/urandom by that point.

I’m not sure if the Linux folks find something wrong with existing, time tested approaches or if there’s some NIH going on, but it doesn’t seem like a multi-decade problem.

Re:Problems emerge for a unified /dev/*random by adastra22 on Tuesday March 29, 2022 @08:08PM (#30849984)
Pedantic question: would it be pseudo-randomly blocking or randomly blocking?
Re:Problems emerge for a unified /dev/*random by mobiletoss1337 on Tuesday March 29, 2022 @10:03PM (#30850734)
It would be somewhat deterministic and predictable and therefore pseudo-random.
Re:Problems emerge for a unified /dev/*random by staticassertion on Tuesday March 29, 2022 @07:14PM (#30849546)
I don't think it's hard to figure out the desired interface. As you said, the hard part is changing the interface to what's desired decades later.
Re:Problems emerge for a unified /dev/*random by throwaway81523 on Wednesday March 30, 2022 @05:08AM (#30852935)
You'd be amazed at how much stupidity lingers about this issue. I don't know if the present-day kernel devs are affected by it, but an awful lot of users are.
Re:Problems emerge for a unified /dev/*random by jart on Tuesday March 29, 2022 @07:43PM (#30849796)
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.
Re:Problems emerge for a unified /dev/*random by anonymousiam on Tuesday March 29, 2022 @07:50PM (#30849851)
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.
Re:Problems emerge for a unified /dev/*random by FrenchDevRemote on Tuesday March 29, 2022 @07:54PM (#30849873)
what if you add timestamp?
Re:Problems emerge for a unified /dev/*random by richdougherty on Wednesday March 30, 2022 @05:58AM (#30853218)
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."

Re:Problems emerge for a unified /dev/*random by sillysaurusx on Tuesday March 29, 2022 @07:58PM (#30849897)
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.

Re:Problems emerge for a unified /dev/*random by caf on Wednesday March 30, 2022 @12:56AM (#30851624)
Re:Problems emerge for a unified /dev/*random by staticassertion on Tuesday March 29, 2022 @08:18PM (#30850072)
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.

Re:Problems emerge for a unified /dev/*random by AnonHP on Tuesday March 29, 2022 @07:59PM (#30849909)
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.
Re:Problems emerge for a unified /dev/*random by stouset on Tuesday March 29, 2022 @09:37PM (#30850581)
Then if I know about when you turned your computer on, I can guess every random number you'll ever generate.
Re:Problems emerge for a unified /dev/*random by postalrat on Tuesday March 29, 2022 @11:32PM (#30851252)
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.
Re:Problems emerge for a unified /dev/*random by anonymousiam on Tuesday March 29, 2022 @10:41PM (#30850984)
Not all computers have a RTC.
Re:Problems emerge for a unified /dev/*random by woodruffw on Tuesday March 29, 2022 @11:15PM (#30851185)
The presence or absence of a real-time clock doesn't significantly change the problem here.
Re:Problems emerge for a unified /dev/*random by staticassertion on Tuesday March 29, 2022 @08:09PM (#30849999)
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.
Re:Problems emerge for a unified /dev/*random by noselasd on Wednesday March 30, 2022 @04:53AM (#30852821)
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)
Re:Problems emerge for a unified /dev/*random by aprdm on Tuesday March 29, 2022 @07:50PM (#30849845)
What kind of wizardry is this doing?! :)
Re:Problems emerge for a unified /dev/*random by Dylan16807 on Tuesday March 29, 2022 @10:30PM (#30850914)
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.

Re:Problems emerge for a unified /dev/*random by Someone on Wednesday March 30, 2022 @10:13AM (#30855483)
> 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.

Re:Problems emerge for a unified /dev/*random by Dylan16807 on Wednesday March 30, 2022 @04:23PM (#30860326)
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.

Re:Problems emerge for a unified /dev/*random by tirpen on Wednesday March 30, 2022 @05:17AM (#30852971)
Those numbers are not random.
Re:Problems emerge for a unified /dev/*random by loeg on Wednesday March 30, 2022 @10:56AM (#30856054)
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.

Re:Problems emerge for a unified /dev/*random by llimllib on Tuesday March 29, 2022 @08:00PM (#30849917)