5 ms·

please don't over complicate this: >you're right, after I've generated many randoms, I was able to get collisions. RDRAND() = 0x0081da17 RDRAND() = 0x0081da17

• 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 ago
    I 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 ago
      32-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 ago
  It's literally just the birthday paradox. You get collisions very quickly for 32-bit numbers. This test finds collisions on Intel too.
  • edwintorok 6y ago
    A better test is to use dieharder, see here: https://github.com/systemd/systemd/issues/18184#issuecomment-758271053 https://github.com/systemd/systemd/issues/18184#issuecomment...
    • rurban 6y ago
      I tested it with dieharder here. It's atrocious without the BiOS patch. https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html
      • mzs 6y ago
        yep was a FW HW issue: https://github.com/systemd/systemd/issues/18184#event-4203184584 https://github.com/systemd/systemd/issues/18184#event-420318...
  • mzs 6y ago
    That was before sort was used, but then the later tests were no longer sound.
• holtalanm 6y ago
  I read through the comments on the issue -- correct me if I'm wrong, but with the program they were running (generating 2000 random numbers) isn't there a 5% chance of generating duplicates, even with RDRAND working as intended? If that is case, maybe RDRAND shouldn't be used for uniqueness.
  • dragontamer 6y ago
    RDRAND can output a 64-bit number. 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).