>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...
If that is case, maybe RDRAND shouldn't be used for uniqueness.
The intrinsic used is the 32-bit version of RDRAND, which is... suboptimal... for a test like this. As you've noted.
Even then, RDRAND has no entropy guarantees (again: see my top comment about RDSEED vs RDRAND).
>> 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/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.
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.
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.
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.
And everyone runs on unreliable hardware.
So yes, I did compare them. Do you have a reason I shouldn't?
If cosmic rays will cause one collision per decade, and "allowed" random collisions will cause one collision per million years, then why care about the increase in risk?
And let's be clear. This github issue is not happening because of using truly random numbers to generate full-size UUIDs. The problem is something else.
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).