5 ms·
Hmmm... Well, first problem is using RDRAND in this case. RDRAND isn't meant for seeds, its for a random number. If you're seeding something, you're supposed
by dragontamer 6y ago
Hmmm...
Well, first problem is using RDRAND in this case. RDRAND isn't meant for seeds, its for a random number.
If you're seeding something, you're supposed to use RDSEED, which has more guarantees about seeding / entropy behavior. I don't think RDRAND was ever intended to be used as an entropy source.
(Think of it this way: RDSEED is kinda like /dev/random, while RDRAND is kinda-like /dev/urandom)
------
RDRAND is an older instruction than RDSEED. So that then brings up the question: what is the proper startup behavior of systems without RDSEED but with RDRAND? Well, since RDRAND never had entropy guarantees, I guess its up to other sources of entropy (see clock-entropy, such as RDTSC).
RDTSC isn't a source of entropy, its just a clock. But as a GHz-level precise timer, it can be used to capture entropy from some other source that does have time-based entropy. (IE: hard drive response rates, or something).
Will the hard drive respond in 10,000,000 clock ticks? Or 10,000,020 clock ticks? That's a source of entropy, a bad one, but maybe you have enough hard drive I/O going on that you can get enough entropy to boot up Systemd.
EDIT: Hmm... hard drives may not be on all systems. In that case, DRAM-latency could possibly be the answer. DRAM refreshes on a regular basis, locking the CPU out temporarily. As such, the amount of time it takes to access data from DRAM is actually somewhat random (in the scope of a GHz clock anyway). Maybe that could be used as an entropy-source of last resort? (as long as RDTSC exists anyway).
- mzs 6y agoplease don't over complicate this: >you're right, after I've generated many randoms, I was able to get collisions. RDRAND() = 0x0081da17 RDRAND() = 0x0081da17 RDRAND() = 0x0178d2ea RDRAND() = 0x0178d2ea RDRAND() = 0x02a91db5 RDRAND() = 0x02a91db5 RDRAND() = 0x06c4385b RDRAND() = 0x06c4385b RDRAND() = 0x095d1bf8 RDRAND() = 0x095d1bf8 RDRAND() = 0x0990b335 RDRAND() = 0x0990b335 RDRAND() = 0x0ab033e4 RDRAND() = 0x0ab033e4 RDRAND() = 0x0ac21fae RDRAND() = 0x0ac21fae RDRAND() = 0x0d39390b RDRAND() = 0x0d39390b RDRAND() = 0x0df2f5ce RDRAND() = 0x0df2f5ce RDRAND() = 0x109e5c8a RDRAND() = 0x109e5c8a https://github.com/systemd/systemd/issues/18184#issuecomment-758155962 https://github.com/systemd/systemd/issues/18184#issuecomment...
- dragontamer 6y ago>> https://github.com/systemd/systemd/issues/18184#issuecomment-758213876 https://github.com/systemd/systemd/issues/18184#issuecomment... >> If you can, please try it without using the C intrinsic. I have seen multiple compiler bug reports--https://patchwork.ozlabs.org/project/gcc/patch/20120520170426.GA7774@intel.com/ https://patchwork.ozlabs.org/project/gcc/patch/2012052017042... is the easiest to find--that indicate that the intrinsics don't always return the right value. Hypothetically, the sequence discussed there could be a compiler-bug, unrolling the loop and failing to treat the results of RDRAND as volatile. So... yeah. Lets not overcomplicate things, but lets not undercomplicate things either. Without an actual disassembly of the code posted, there's no proof yet.
- rcxdude 6y agoI doubt it, a compiler bug like failing to consider rdrand volatile would not occasionally fail, but would fail consistently (perhaps every nth iteration, but it would have a pattern). I struggle to see how a compiler could miscompile it to make it inconsistent.
- dragontamer 6y ago32-bit is also a pretty bad RNG to test in this manner. Birthday paradox says that you'll only need 2^16 (65,536) runs before you get a collision. 64-bit would have a collision in one in 2^32 (4-billion). With 2000 x 10 tests (== 20,000 tests per run), there's a pretty high chance of a collision actually. There's a lot of issues complicating the testing of something like this. I'm sure the core fact (that RDRAND might be doing something wrong) is there. But to properly vet all issues and actually get to the bottom of this bug will take some effort.
- floatboth 6y agoIt's literally just the birthday paradox. You get collisions very quickly for 32-bit numbers. This test finds collisions on Intel too.
- 6y ago
- lrossi 6y agoThey are using it only to generate UUIDs. They could have avoided collisions using the clock or even a counter as part of the uuid. But for some reason systemd is always creating a lot of drama before they accept they were wrong and fix the bug (which doesn’t always happen).
- Dylan16807 6y agoActual UUID? 122 random bits? Using random numbers to make a UUID is not a bug. If you think you see multiple separate UUID collisions then you know for sure you have an implementation or hardware problem, not an algorithm problem.
- rasz 6y ago>Using random numbers to make a UUID is not a bug. the thing about randomness is you can get two 0x00 answers in a row and they are 100% valid. Using random numbers for something which required Unique numbers is crazy.
- Dylan16807 6y agoNo matter what, you could get hit with a cosmic ray or spark of static or a bug could corrupt your program's memory. The state of "we somehow generated two identical UUIDs" cannot be prevented in the real world. You can only reduce the chance to acceptable levels. Compared to the risks that are accepted in basically all devices, the danger from using big random numbers is negligible. Which makes it not crazy to do.
- rasz 6y agoDid you just compare normal operation (true randomness allowing for a string of duplicate outputs) to a bug caused by stray cosmic ray in an effort to excuse brain dead decision by systemd?
- Dylan16807 6y ago
- jhanschoo 6y ago> RDRAND isn't meant for seeds, its for a random number. In more precise mathematical language, RDRAND isn't meant for random numbers, it's for an arbitrary number.