4 ms·

Even so, systemd should be able to deal with name collisions even with numbers coming from a true RNG. That causing errors is a design issue, IMO.

by ginko 6y ago

johncolanduoni 6y ago
Most cryptographic constructs you feed CSPRNG data into break spectacularly if they receive colliding data so I guess they all have design issues too. Including the TLS connection you’re typing your comment through.
tadfisher 6y ago
That would be a non-deterministic failure case scaling to O(n) in both space and time. But it's not just UUIDs, it's also required for seeding systemd's internal hash tables, which would degrade from O(1) lookups to O(n) should an attacker exploit known RNG flaws. So, a PRNG with a semi-decent (not perfect) entropy pool is required at boot time, and systemd needs to run in environments where seeding that pool in software could take on the order of minutes. This is why RDRAND is used to seed the pool during boot. https://github.com/systemd/systemd/blob/61bd7d1ed595a98e5fbfeb75b530539c4834f6a4/src/basic/random-util.c#L40-L98 https://github.com/systemd/systemd/blob/61bd7d1ed595a98e5fbf...
- aidenn0 6y ago
  1. UUIDs are stored somewhere so there's already O(n) space in use. Checking for collisions is only O(log n) in time. 2. Use a tree instead of a hash-table; or just use RDRAND and hope you aren't presented with malicious inputs. The comment in the code[1] about RDRAND being sufficient for the use-case of UUIDs is empirically false. To continue to rely upon it is to insist that the rest of the world conform to your beliefs, rather than to adjust your beliefs to match the rest of the world. 1: https://github.com/systemd/systemd/blob/bcac754d66374782a85a8de39fd543c1eaf9fa82/src/basic/random-util.c#L40-L98 https://github.com/systemd/systemd/blob/bcac754d66374782a85a...
  - tadfisher 6y ago
    > The comment in the code[1] about RDRAND being sufficient for the use-case of UUIDs is empirically false. Ipse dixit. Can you provide an explanation?
    - aidenn0 6y ago
      1. TFA 2. https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/ https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd... 3. https://linuxreviews.org/RDRAND_stops_returning_random_values_on_older_AMD_CPUs_after_suspend https://linuxreviews.org/RDRAND_stops_returning_random_value... 4. There are also comments elsewhere on this page that older Intel RDRAND implementations had similar issues, but they did not cite their source.

Even so, systemd should be able to deal with name collisions even with numbers coming from a true RNG. That causing errors is a design issue, IMO.

by ginko 6y ago

Even so, systemd should be able to deal with name collisions even with numbers coming from a true RNG. That causing errors is a design issue, IMO.

johncolanduoni 6y ago

Most cryptographic constructs you feed CSPRNG data into break spectacularly if they receive colliding data so I guess they all have design issues too. Including the TLS connection you’re typing your comment through.

tadfisher 6y ago

That would be a non-deterministic failure case scaling to O(n) in both space and time. But it's not just UUIDs, it's also required for seeding systemd's internal hash tables, which would degrade from O(1) lookups to O(n) should an attacker exploit known RNG flaws. So, a PRNG with a semi-decent (not perfect) entropy pool is required at boot time, and systemd needs to run in environments where seeding that pool in software could take on the order of minutes. This is why RDRAND is used to seed the pool during boot. https://github.com/systemd/systemd/blob/61bd7d1ed595a98e5fbfeb75b530539c4834f6a4/src/basic/random-util.c#L40-L98 https://github.com/systemd/systemd/blob/61bd7d1ed595a98e5fbf...

aidenn0 6y ago
1. UUIDs are stored somewhere so there's already O(n) space in use. Checking for collisions is only O(log n) in time. 2. Use a tree instead of a hash-table; or just use RDRAND and hope you aren't presented with malicious inputs. The comment in the code[1] about RDRAND being sufficient for the use-case of UUIDs is empirically false. To continue to rely upon it is to insist that the rest of the world conform to your beliefs, rather than to adjust your beliefs to match the rest of the world. 1: https://github.com/systemd/systemd/blob/bcac754d66374782a85a8de39fd543c1eaf9fa82/src/basic/random-util.c#L40-L98 https://github.com/systemd/systemd/blob/bcac754d66374782a85a...
- tadfisher 6y ago
  > The comment in the code[1] about RDRAND being sufficient for the use-case of UUIDs is empirically false. Ipse dixit. Can you provide an explanation?
  - aidenn0 6y ago
    1. TFA 2. https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/ https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd... 3. https://linuxreviews.org/RDRAND_stops_returning_random_values_on_older_AMD_CPUs_after_suspend https://linuxreviews.org/RDRAND_stops_returning_random_value... 4. There are also comments elsewhere on this page that older Intel RDRAND implementations had similar issues, but they did not cite their source.