How a Bad Random Number Generator Froze Sway (2020) | Hacker News Reader

How a Bad Random Number Generator Froze Sway (2020)

theavid.dev

57 pointsaskl19 comments

Why is rng not handled by a standard library or with a call to /dev/*random? Feels weird to me that average userspace code should even know about CPU instructions.

Author here. Not particularly sure myself, even systemd says it only does so because it does things early in the boot process[1]. Using it for it's purpose here is probably alright, but the odd part is prioritizing it[2] over /dev/urandom.

[1]: https://github.com/systemd/systemd/blob/301e7cd047c8d07715d5... [2]: https://github.com/json-c/json-c/blob/31f1ab2be1142d982fc9b8...

Why does a JSON parser need a random number generator anyway?

It seems json-c uses a random number generator to get a seed that it then uses for string hashing. This is one way of protecting yourself against hash denial-of-service attacks.

https://github.com/json-c/json-c/blob/df27756491abf9ecce648c...

> This is one way of protecting yourself against hash denial-of-service attacks.

Ironic, in this case. And the fix isn't much better; there's no guarantee that RDRAND won't revert to the -1 behavior after the check runs, perhaps after a VM migration or resume from suspend or what-not.

Overall RDRAND seems to be a terrible userspace instruction. Special-casing its use sounds more complicated then proper multi-platform support for system RNGs.

> [...] there's no guarantee that RDRAND won't revert to the -1 behavior after the check runs, perhaps after a VM migration or resume from suspend or what-not.

Author here. This is true and is an issue with some CPUs (breaking RDRAND after resume), but every call to RDRAND is guarded[1] by a check that it works.

[1]: https://github.com/json-c/json-c/blob/041cef434afe0d0c6da8b6...

Edit: Ah, I just realized you stated "after the check runs" and you're correct, there's no way that can be guaranteed.

Edit 2: Well, if RDRAND returns a value json-c can't use (-1) it won't be used.

Most unixes on x86 optionally use RDRAND to add entropy to the /dev/random pool and I see that Win32 is also covered in json-c, so I don't see the benefit of explicit support for RDRAND in the critical path at least.

RDRAND may also be slow: https://www.phoronix.com/scan.php?page=news_item&px=RdRand-3...

Ultimately I think it was a mistake for Intel to try to provide user-level hardware random number generation. It's apparently not an easily solved problem and requires complete trust in the hardware and a fallback TRNG/HRNG that's just as secure if the hardware reports that it's not working. Why not just use the fallback all the time? System-level entropy pools are pretty well-studied at this point.

I think it was a mistake for Intel to try to provide user-level hardware random number generation.

They probably did this for speed. Faster than library calls or system calls.

It's apparently not an easily solved problem

Apparently too hard for the clowns at AMD. AFAIK it's a "solved problem" on Intel hardware. (Has there ever been a problem with the hardware in any Intel CPU?)

We wouldn't be having this discussion if AMD hadn't royally fucked this up.

> (Has there ever been a problem with the hardware in any Intel CPU?)

FOOF...

( https://en.wikipedia.org/wiki/Pentium_F00F_bug Admittedly that was in the 90s... )

Sorry about that. FOOF did cause some people headaches.

I should have more specifically said, "has there been a problem with RDRAND hardware in any Intel CPU?"

FOOF wasn't a "real" problem for an average user, it had some workarounds. It wasn't even triggered unless you tried to execute an invalid instruction.

Much much much worse was the Intel FDIV bug. That one caused Intel to recall processors and cost them $475 million. https://en.wikipedia.org/wiki/Pentium_FDIV_bug

Lots of jokes resulted. E.g.: We are Pentium of Borg. Division is futile. You will be approximated.

As for RDRAND, Intel put a lot of thought into it. It wasn't just a hack.

Here's a high level presentation. (A friend of mine at Intel thought highly of Dr. George Cox, who was a long time Intel employee). https://old.hotchips.org/wp-content/uploads/hc_archives/hc23...

Here's a little more detail: https://spectrum.ieee.org/computing/hardware/behind-intels-n...

> They probably did this for speed. Faster than library calls or system calls.

Xorshift is faster than RDRAND and json-c is using lookup3 for hashing (unless I'm missing some other use of the RDRAND data) so it doesn't need cryptographic RNG.

> Apparently too hard for the clowns at AMD. AFAIK it's a "solved problem" on Intel hardware. (Has there ever been a problem with the hardware in any Intel CPU?)

Meltdown/Spectre of course. As I posted earlier there's also an Intel microcode update that makes RDRAND much slower. https://www.phoronix.com/scan.php?page=news_item&px=RdRand-3...

rdrand besides most likely backdoored is not fast. It's like 1000x slower than the slowest prng call on an unpatched Ryzen. https://rurban.github.io/dieharder/QUALITY.html

Ugh, this is... unfortunate. Are there really any systems for which all the other options for randomness are not available? I really think there aren't. RDRAND should be near the bottom of the list of things it tries (or just be dropped entirely), not the top.

Wasting time trying to patch over its misbehaviors is just overengineering.

The only usage is here:

https://github.com/json-c/json-c/blob/df27756491abf9ecce648c...

Which appears to be part of the hashtable implementation for the json objects.

Shouldn't the correct fix be to remove the infinite loop?

The correct fix is to remove the use of RDRAND entirely.

Author here. I believe it's kept because at the end of the day, they _must_ get a valid value form it; however, the chances of that loop having to run more than once are astronomically low.

I understand that, but an infinite loop is not a valid response to a program's preconditions being unfulfilled.

The infinite loop is a landmine left in the field.

Handling the negative -1 with a log error and an assert, would be better than an infinite loop.

Infinite loops can damage even other programs by hogging the cpu. They are far worse than an exception or an std::exit.

I think in the authors example, having sway fail to parse JSON would have been a better fallback than having the entire system lock up.

I don't want to be over dramatic but leaving that infinite loop in there is the type of mindset that leads to horrendous code bases decades from now.

Sway and Wayland was created to get away from the warts of X11. This infinite loop is bringing the new effort closer in line with its ugly older cousin.

(Sway dev mentioned in the article here.)

To be clear, this loop doesn't exist in Sway proper: it lives in json-c, a third-party library used by a lot more than just Sway. A lockup bug was reported to a lot of projects using json-c at the same time.

This really wasn't a Sway/Wayland thing, we just happened to be the first to diagnose and contribute a fix upstream.

Reply on news.ycombinator.com