7 ms·

How a Bad Random Number Generator Froze Sway (2020)

57 points by askl 6y ago

nightowl_games 6y ago
Shouldn't the correct fix be to remove the infinite loop?
- fluix 6y ago
  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.
  - nightowl_games 6y ago
    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.
    - tbr1 6y ago
      (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.
- kelnos 6y ago
  The correct fix is to remove the use of RDRAND entirely.
captaincrowbar 6y ago
Why does a JSON parser need a random number generator anyway?
- SolarNet 6y ago
  The only usage is here: https://github.com/json-c/json-c/blob/df27756491abf9ecce648c3aa85d6a70feb4c600/linkhash.c#L469 https://github.com/json-c/json-c/blob/df27756491abf9ecce648c... Which appears to be part of the hashtable implementation for the json objects.
- dajoh 6y ago
  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/df27756491abf9ecce648c3aa85d6a70feb4c600/linkhash.c#L469 https://github.com/json-c/json-c/blob/df27756491abf9ecce648c...
  - benlivengood 6y ago
    > 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.
    - fluix 6y ago
      > [...] 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/041cef434afe0d0c6da8b6ac1d1fa26087246dda/random_seed.c#L324 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.
krastanov 6y ago
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.
- fluix 6y ago
  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/301e7cd047c8d07715d5dc37f713e8aa031581b4/src/basic/random-util.c#L43 https://github.com/systemd/systemd/blob/301e7cd047c8d07715d5... [2]: https://github.com/json-c/json-c/blob/31f1ab2be1142d982fc9b8c8913bfd1233599ebb/random_seed.c#L230 https://github.com/json-c/json-c/blob/31f1ab2be1142d982fc9b8...

57 points by askl 6y ago

nightowl_games 6y ago

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

fluix 6y ago
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.
- nightowl_games 6y ago
  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.
  - tbr1 6y ago
    (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.
kelnos 6y ago
The correct fix is to remove the use of RDRAND entirely.

captaincrowbar 6y ago

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

SolarNet 6y ago
The only usage is here: https://github.com/json-c/json-c/blob/df27756491abf9ecce648c3aa85d6a70feb4c600/linkhash.c#L469 https://github.com/json-c/json-c/blob/df27756491abf9ecce648c... Which appears to be part of the hashtable implementation for the json objects.
dajoh 6y ago
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/df27756491abf9ecce648c3aa85d6a70feb4c600/linkhash.c#L469 https://github.com/json-c/json-c/blob/df27756491abf9ecce648c...
- benlivengood 6y ago
  > 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.
  - fluix 6y ago
    > [...] 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/041cef434afe0d0c6da8b6ac1d1fa26087246dda/random_seed.c#L324 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.

krastanov 6y ago

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.

fluix 6y ago
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/301e7cd047c8d07715d5dc37f713e8aa031581b4/src/basic/random-util.c#L43 https://github.com/systemd/systemd/blob/301e7cd047c8d07715d5... [2]: https://github.com/json-c/json-c/blob/31f1ab2be1142d982fc9b8c8913bfd1233599ebb/random_seed.c#L230 https://github.com/json-c/json-c/blob/31f1ab2be1142d982fc9b8...