6 ms·

>If an existing session has the same ID as the new number, WireGuard asks RDRAND for another "random" number, checks it for uniqueness, and so on. Since RDRAND

>If an existing session has the same ID as the new number, WireGuard asks RDRAND for another "random" number, checks it for uniqueness, and so on. Since RDRAND on my system—and any non-microcode-updated Ryzen 3000 system—always returned 0xFFFFFFFF no matter what, that means infinite loop. I'm pretty surprised that so much software seems to rely on external (be it from the CPU, or the OS) random number generation directly instead of simply using a software PRNG and seeding it with external sources (and maybe additional creative sources if desired). That seems like a way more predictable system to me, in the sense that at least you get guaranteed uniformly distributed numbers, even if the external seeds are not uniformly distributed at all.

amelius 7y ago
I guess you should use both methods. The hardware method for seeding, and the prng method for the uniform-ness. Also, it is very easy to shoot yourself in the foot when being "creative" with random numbers, especially in the domain of security.
deleted 7y ago
[deleted]
gargravarr 7y ago
My understanding is that implementing a PRNG in software results in a very small entropy pool. At the OS level, it can collect entropy from a vast number of sources, including things that an application won't have access to, which is why the OS exposes the RNG to applications. It also means maintaining such a PRNG in your software. Basically, it's the same old dependency argument again - there is nothing inherently wrong with using the tools the environment provides for you rather than building your own, but it does mean that the tools have to work properly. This is especially critical for cryptographically-secure PRNGs - those are things you really do not want to be maintaining yourself if you can access a high-quality source of random data, but again, if the PRNG doesn't work, you're in deep trouble (see for example Yubico's broken PRNG chips on the Yubikey 4). Hardware PRNGs on the CPU itself were supposed to dramatically improve the state of random data provisioning, but when bugs like this hit, it shows the weakness of depending on the stack beneath.
- pingyong 7y ago
  > This is especially critical for cryptographically-secure PRNGs - those are things you really do not want to be maintaining yourself My conclusion would be exactly the opposite: If your RNG is so important that it has to be cryptographically secure, you owe it to your users to put in the time and effort of maintaining a proper implementation yourself, or at the very least use an open source library that provides this functionality in software. Otherwise you're always going to be at the mercy of a potentially misbehaving environment. In terms of entropy, you don't really need to "maintain a pool" for CSPRNGs. You either have enough entropy to feed it with, or you don't. Once it is properly seeded, you can squeeze as many random bits out of it as you want (or at least, as many as anyone would ever reasonably need). It's really no different from a stream cipher, the key is the seed, and you're just encrypting zeroes. You don't need to suddenly get another randomly generated key after encrypting 100 MiB to encrypt the next 100 MiB securely. Another great thing about entropy is that you can't reduce it. Which is why you really don't have to spend any time thinking about whether a particular entropy source is well behaved or uniformly distributed or anything like that at all. You just have to be certain that you have overall enough entropy that nobody can guess the entire seed. So anything the OS can give you? Dump it in there. Any kind of user interaction? Dump it in there. The time? CPU jitter? Network jitter? Just put it all in there. 100 MiBs of 0s? You know what why not, just put it on top because you literally can't make it worse, only better.
- ChrisSD 7y ago
  To be clear, you only need some random bytes to seed your cryptographic PRNG. This should of course be gathered from the OS but after that you only need to reseed once in a blue moon. Of course you shouldn't write and maintain a CPRNG yourself but there are many widely used, maintained and scrutinized libraries for this purpose. For example, seeding ChaCha with 256bits will give you 1 ZiB of output before cycling. That should keep you going for awhile.
- throw0101a 7y ago
  > My understanding is that implementing a PRNG in software results in a very small entropy pool. A lot of PRNG are now implemented as the output of stream ciphers or block cipher in counter mode: * https://en.wikipedia.org/wiki/Fortuna_(PRNG) https://en.wikipedia.org/wiki/Fortuna_(PRNG) So 128 bits is all that is needed to get going. Re-key every so often to ensure forward security in case there is a kernel-level compromise. With AES-NI instructions in most CPUs, several GB/s can be achieved.
moviuro 7y ago
WireGuard is a Linux module, so it makes sense for it to rely directly on HW instead of a userspace PRNG . https://wireguard.com https://wireguard.com
owenmarshall 7y ago
Because your intuition about the ease of building random number generators is wrong, especially if they need to be cryptographically secure. I trust my OS’ RNG functions[1] far more than I trust third party code to be right, and I trust it a million times more than I trust myself to get it right. Trusting a small core of validated code is far more likely to be correct in the long term. Wireguard’s mistake was not using what the OS gave them; I’m not sure why they didn’t. [1]: https://man.openbsd.org/arc4random.3 https://man.openbsd.org/arc4random.3
- Tharre 7y ago
  WireGuard is a kernel module, it already uses what the kernel gave it, which is get_random_u32(). Note that this is NOT used for anything crypto related, it's just used in the hashtable code.
  - owenmarshall 7y ago
    Amazing. Apologies to the Wireguard folks: first for casting aspersions, second that they have to deal with such a trash heap of an API.
- a1369209993 7y ago
  No, building random number generators is easy; the reason arc4random was (it's been fixed) insecure was because arc4 was insecure. If you have a secure stream cipher, you have a secure RNG. Not "can build", they're the same thing. If you only have block ciphers, the security proof is less trivial, but in practice "decrypt /dev/zero" still works. If you don't have a secure (symmetric) cipher, you have bigger crypographic problems than bad random numbers.
- pingyong 7y ago
  Just to follow up on this funnily enough, the Wireguard guys actually did call a kernel function: https://news.ycombinator.com/item?id=21391308 https://news.ycombinator.com/item?id=21391308 And again, like before, the reaction to this is just hilarious to me. "It's a kernel bug." - Yeah, sure, but your users don't care, and your users shouldn't have to care. Because this an easy problem to fix, and if you're worth your salt as a developer you should fix it. Evidently Wireguard isn't worth it's salt.
pwg 7y ago
That just changes the issue from "how do I get good quality random numbers" to "how do I get a good quality seed". Yes, less data is needed for just a seed, but this is not a perfect solution for every case either.
- pingyong 7y ago
  >That just changes the issue from "how do I get good quality random numbers" to "how do I get a good quality seed". This is completely true, but there is a property that your random numbers have to have that your seed doesn't need in any way: Being uniformly distributed. If you need a random 64 bit number, you want every single bit in that number to have a 50% chance of being 0 or 1. This requirement doesn't exist at all for seed data, the entropy of all your seed data together just needs to be large enough for it to be computationally infeasible to calculate it from the outside. I would say that is a pretty big difference. Also, if you just need uniformly distributed random IDs but those IDs aren't secret and don't need to be unpredictable, you don't even need a seed. Or at least, you can just use a constant as a seed. No interaction with the outside world needed at all.
blihp 7y ago
Depends on what you're looking for. Often you don't want 'guaranteed uniformly distributed numbers', you want random numbers. The reason for using hardware is that some processors can now provide greater (at least theoretically) entropy and/or greater performance in doing so than a software-only PRNG.
wyldfire 7y ago
> Since RDRAND on my system—and any non-microcode-updated Ryzen 3000 system—always returned 0xFFFFFFFF no matter what, that means infinite loop Gee what if instead when it hit a threshold, it disabled the feature and called BUG()?
zx2c4 7y ago
WireGuard uses the correct kernel function, get_random_u32(). WireGuard does not use RdRand directly. WireGuard instead uses the proper kernel function for asking for a unsigned 32-bit number. The kernel implements get_random_u32() under the hood using a variety of backends for it. One of them is RdRand. Other facilities in the kernel, such as ASLR, also use get_random_u32(). Many things in the kernel use get_random_u32(). That's the proper function to use. When presented with this bug, the upstream kernel maintainers chose not to fix get_random_u32(), due to the availability (?) of microcode updates for AMD chips. That's not my decision. WireGuard is just a mere consumer of get_random_u32(), like all other modules. This is an upstream kernel bug.

amelius 7y ago

I guess you should use both methods. The hardware method for seeding, and the prng method for the uniform-ness. Also, it is very easy to shoot yourself in the foot when being "creative" with random numbers, especially in the domain of security.

deleted 7y ago

[deleted]

gargravarr 7y ago

My understanding is that implementing a PRNG in software results in a very small entropy pool. At the OS level, it can collect entropy from a vast number of sources, including things that an application won't have access to, which is why the OS exposes the RNG to applications. It also means maintaining such a PRNG in your software. Basically, it's the same old dependency argument again - there is nothing inherently wrong with using the tools the environment provides for you rather than building your own, but it does mean that the tools have to work properly. This is especially critical for cryptographically-secure PRNGs - those are things you really do not want to be maintaining yourself if you can access a high-quality source of random data, but again, if the PRNG doesn't work, you're in deep trouble (see for example Yubico's broken PRNG chips on the Yubikey 4). Hardware PRNGs on the CPU itself were supposed to dramatically improve the state of random data provisioning, but when bugs like this hit, it shows the weakness of depending on the stack beneath.

pingyong 7y ago
> This is especially critical for cryptographically-secure PRNGs - those are things you really do not want to be maintaining yourself My conclusion would be exactly the opposite: If your RNG is so important that it has to be cryptographically secure, you owe it to your users to put in the time and effort of maintaining a proper implementation yourself, or at the very least use an open source library that provides this functionality in software. Otherwise you're always going to be at the mercy of a potentially misbehaving environment. In terms of entropy, you don't really need to "maintain a pool" for CSPRNGs. You either have enough entropy to feed it with, or you don't. Once it is properly seeded, you can squeeze as many random bits out of it as you want (or at least, as many as anyone would ever reasonably need). It's really no different from a stream cipher, the key is the seed, and you're just encrypting zeroes. You don't need to suddenly get another randomly generated key after encrypting 100 MiB to encrypt the next 100 MiB securely. Another great thing about entropy is that you can't reduce it. Which is why you really don't have to spend any time thinking about whether a particular entropy source is well behaved or uniformly distributed or anything like that at all. You just have to be certain that you have overall enough entropy that nobody can guess the entire seed. So anything the OS can give you? Dump it in there. Any kind of user interaction? Dump it in there. The time? CPU jitter? Network jitter? Just put it all in there. 100 MiBs of 0s? You know what why not, just put it on top because you literally can't make it worse, only better.
ChrisSD 7y ago
To be clear, you only need some random bytes to seed your cryptographic PRNG. This should of course be gathered from the OS but after that you only need to reseed once in a blue moon. Of course you shouldn't write and maintain a CPRNG yourself but there are many widely used, maintained and scrutinized libraries for this purpose. For example, seeding ChaCha with 256bits will give you 1 ZiB of output before cycling. That should keep you going for awhile.
throw0101a 7y ago
> My understanding is that implementing a PRNG in software results in a very small entropy pool. A lot of PRNG are now implemented as the output of stream ciphers or block cipher in counter mode: * https://en.wikipedia.org/wiki/Fortuna_(PRNG) https://en.wikipedia.org/wiki/Fortuna_(PRNG) So 128 bits is all that is needed to get going. Re-key every so often to ensure forward security in case there is a kernel-level compromise. With AES-NI instructions in most CPUs, several GB/s can be achieved.

moviuro 7y ago

WireGuard is a Linux module, so it makes sense for it to rely directly on HW instead of a userspace PRNG . https://wireguard.com https://wireguard.com

owenmarshall 7y ago

Because your intuition about the ease of building random number generators is wrong, especially if they need to be cryptographically secure. I trust my OS’ RNG functions[1] far more than I trust third party code to be right, and I trust it a million times more than I trust myself to get it right. Trusting a small core of validated code is far more likely to be correct in the long term. Wireguard’s mistake was not using what the OS gave them; I’m not sure why they didn’t. [1]: https://man.openbsd.org/arc4random.3 https://man.openbsd.org/arc4random.3

Tharre 7y ago
WireGuard is a kernel module, it already uses what the kernel gave it, which is get_random_u32(). Note that this is NOT used for anything crypto related, it's just used in the hashtable code.
- owenmarshall 7y ago
  Amazing. Apologies to the Wireguard folks: first for casting aspersions, second that they have to deal with such a trash heap of an API.
a1369209993 7y ago
No, building random number generators is easy; the reason arc4random was (it's been fixed) insecure was because arc4 was insecure. If you have a secure stream cipher, you have a secure RNG. Not "can build", they're the same thing. If you only have block ciphers, the security proof is less trivial, but in practice "decrypt /dev/zero" still works. If you don't have a secure (symmetric) cipher, you have bigger crypographic problems than bad random numbers.
pingyong 7y ago
Just to follow up on this funnily enough, the Wireguard guys actually did call a kernel function: https://news.ycombinator.com/item?id=21391308 https://news.ycombinator.com/item?id=21391308 And again, like before, the reaction to this is just hilarious to me. "It's a kernel bug." - Yeah, sure, but your users don't care, and your users shouldn't have to care. Because this an easy problem to fix, and if you're worth your salt as a developer you should fix it. Evidently Wireguard isn't worth it's salt.

pwg 7y ago

That just changes the issue from "how do I get good quality random numbers" to "how do I get a good quality seed". Yes, less data is needed for just a seed, but this is not a perfect solution for every case either.

pingyong 7y ago
>That just changes the issue from "how do I get good quality random numbers" to "how do I get a good quality seed". This is completely true, but there is a property that your random numbers have to have that your seed doesn't need in any way: Being uniformly distributed. If you need a random 64 bit number, you want every single bit in that number to have a 50% chance of being 0 or 1. This requirement doesn't exist at all for seed data, the entropy of all your seed data together just needs to be large enough for it to be computationally infeasible to calculate it from the outside. I would say that is a pretty big difference. Also, if you just need uniformly distributed random IDs but those IDs aren't secret and don't need to be unpredictable, you don't even need a seed. Or at least, you can just use a constant as a seed. No interaction with the outside world needed at all.

blihp 7y ago

Depends on what you're looking for. Often you don't want 'guaranteed uniformly distributed numbers', you want random numbers. The reason for using hardware is that some processors can now provide greater (at least theoretically) entropy and/or greater performance in doing so than a software-only PRNG.

wyldfire 7y ago

> Since RDRAND on my system—and any non-microcode-updated Ryzen 3000 system—always returned 0xFFFFFFFF no matter what, that means infinite loop Gee what if instead when it hit a threshold, it disabled the feature and called BUG()?

zx2c4 7y ago

WireGuard uses the correct kernel function, get_random_u32(). WireGuard does not use RdRand directly. WireGuard instead uses the proper kernel function for asking for a unsigned 32-bit number. The kernel implements get_random_u32() under the hood using a variety of backends for it. One of them is RdRand. Other facilities in the kernel, such as ASLR, also use get_random_u32(). Many things in the kernel use get_random_u32(). That's the proper function to use. When presented with this bug, the upstream kernel maintainers chose not to fix get_random_u32(), due to the availability (?) of microcode updates for AMD chips. That's not my decision. WireGuard is just a mere consumer of get_random_u32(), like all other modules. This is an upstream kernel bug.