Page MenuHomeFreeBSD

random: Add PowerPC 'darn' instruction entropy source
ClosedPublic

Authored by jhibbits on Aug 1 2018, 8:29 PM.

Details

Summary

PowerISA 3.0 adds a 'darn' instruction to "deliver a random number".
The driver was modeled after (rather, copied and gutted of) the Ivy Bridge
rdrand driver.

This uses the "Raw Random Number" behavior, rather than the 'Conditioned Random
Number' behavior, so there may exist a bias on input.

Test Plan

Need advice on this. I've only tested that /dev/random still
functions. I'm also not sure which is better: RRN or CRN, as an entropy source.

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

jhibbits created this revision.Aug 1 2018, 8:29 PM

I should add, from the ISA reference:

"The random number generator provided by this
instruction is NIST SP800-90B and SP800-90C
compliant to the extent possible given the completeness
of the standards at the time the hardware
is designed. The random number generator provides
a minimum of 0.5 bits of entropy per bit."

jhibbits updated this revision to Diff 46156.Aug 1 2018, 8:41 PM

Remove x86 names (rdrand, ivy) from the function names. No other changes.

markm accepted this revision.Aug 2 2018, 11:22 AM

Looks good to me!

sys/dev/random/darn.c
68 ↗(On Diff #46156)

I don't know this instruction or its ramifications, so I am presuming its use is correct.

86 ↗(On Diff #46156)

This may work in real hardware, but emulators have been known to break on other architectures. BEWARE!

bdragon added a subscriber: bdragon.Aug 2 2018, 2:31 PM

Attaches fine on my Talos II. Seems to work fine, as far as I can tell.

Did a dieharder pass with the other entropy sources disabled and not seeing any problems so far. I'm not a crypto expert though.

# dieharder/dieharder -f /dev/random -g 201 -a
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|                     /dev/random|  4.18e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.69911695|  PASSED  
      diehard_operm5|   0|   1000000|     100|0.39877393|  PASSED  
  diehard_rank_32x32|   0|     40000|     100|0.04807253|  PASSED  
    diehard_rank_6x8|   0|    100000|     100|0.00220300|   WEAK   
   diehard_bitstream|   0|   2097152|     100|0.79996422|  PASSED  
        diehard_opso|   0|   2097152|     100|0.49471113|  PASSED  
        diehard_oqso|   0|   2097152|     100|0.42896023|  PASSED  
         diehard_dna|   0|   2097152|     100|0.23260902|  PASSED  
diehard_count_1s_str|   0|    256000|     100|0.99569912|   WEAK   
diehard_count_1s_byt|   0|    256000|     100|0.96983427|  PASSED  
 diehard_parking_lot|   0|     12000|     100|0.17940638|  PASSED  
    diehard_2dsphere|   2|      8000|     100|0.15737095|  PASSED  
    diehard_3dsphere|   3|      4000|     100|0.57616095|  PASSED  
     diehard_squeeze|   0|    100000|     100|0.42193082|  PASSED  
        diehard_sums|   0|       100|     100|0.59546840|  PASSED  
        diehard_runs|   0|    100000|     100|0.90991029|  PASSED  
        diehard_runs|   0|    100000|     100|0.12912752|  PASSED  
       diehard_craps|   0|    200000|     100|0.92958876|  PASSED  
       diehard_craps|   0|    200000|     100|0.94894377|  PASSED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.78425628|  PASSED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.91239027|  PASSED  
         sts_monobit|   1|    100000|     100|0.58112895|  PASSED  
            sts_runs|   2|    100000|     100|0.51109946|  PASSED  
          sts_serial|   1|    100000|     100|0.82276441|  PASSED  
          sts_serial|   2|    100000|     100|0.86557688|  PASSED  
          sts_serial|   3|    100000|     100|0.86938216|  PASSED  
          sts_serial|   3|    100000|     100|0.59845722|  PASSED  
          sts_serial|   4|    100000|     100|0.24061951|  PASSED  
          sts_serial|   4|    100000|     100|0.86115418|  PASSED  
          sts_serial|   5|    100000|     100|0.47857415|  PASSED  
          sts_serial|   5|    100000|     100|0.78753816|  PASSED  
          sts_serial|   6|    100000|     100|0.85961258|  PASSED  
          sts_serial|   6|    100000|     100|0.92535418|  PASSED  
          sts_serial|   7|    100000|     100|0.85637865|  PASSED  
          sts_serial|   7|    100000|     100|0.73545194|  PASSED  
          sts_serial|   8|    100000|     100|0.76063191|  PASSED  
          sts_serial|   8|    100000|     100|0.77010759|  PASSED  
          sts_serial|   9|    100000|     100|0.49894167|  PASSED  
          sts_serial|   9|    100000|     100|0.10301442|  PASSED  
          sts_serial|  10|    100000|     100|0.99830004|   WEAK   
          sts_serial|  10|    100000|     100|0.64731099|  PASSED  
          sts_serial|  11|    100000|     100|0.91702747|  PASSED  
          sts_serial|  11|    100000|     100|0.93170932|  PASSED  
          sts_serial|  12|    100000|     100|0.98194277|  PASSED  
          sts_serial|  12|    100000|     100|0.99999737|   WEAK   
          sts_serial|  13|    100000|     100|0.39803588|  PASSED  
          sts_serial|  13|    100000|     100|0.28514807|  PASSED  
          sts_serial|  14|    100000|     100|0.15754153|  PASSED  
          sts_serial|  14|    100000|     100|0.20802489|  PASSED  
          sts_serial|  15|    100000|     100|0.62046572|  PASSED  
          sts_serial|  15|    100000|     100|0.43344158|  PASSED  
          sts_serial|  16|    100000|     100|0.84373821|  PASSED  
          sts_serial|  16|    100000|     100|0.86623208|  PASSED  
         rgb_bitdist|   1|    100000|     100|0.33356013|  PASSED  
         rgb_bitdist|   2|    100000|     100|0.69897588|  PASSED  
         rgb_bitdist|   3|    100000|     100|0.92126651|  PASSED  
         rgb_bitdist|   4|    100000|     100|0.99000386|  PASSED  
         rgb_bitdist|   5|    100000|     100|0.40411765|  PASSED  
         rgb_bitdist|   6|    100000|     100|0.24862754|  PASSED  
         rgb_bitdist|   7|    100000|     100|0.68639708|  PASSED  
         rgb_bitdist|   8|    100000|     100|0.89202030|  PASSED  
         rgb_bitdist|   9|    100000|     100|0.55743840|  PASSED  
         rgb_bitdist|  10|    100000|     100|0.08631105|  PASSED  
         rgb_bitdist|  11|    100000|     100|0.08752150|  PASSED  
         rgb_bitdist|  12|    100000|     100|0.20775392|  PASSED  
rgb_minimum_distance|   2|     10000|    1000|0.90394887|  PASSED  
rgb_minimum_distance|   3|     10000|    1000|0.64369874|  PASSED  
rgb_minimum_distance|   4|     10000|    1000|0.99372934|  PASSED  
rgb_minimum_distance|   5|     10000|    1000|0.03601301|  PASSED  
    rgb_permutations|   2|    100000|     100|0.99593501|   WEAK   
    rgb_permutations|   3|    100000|     100|0.56320651|  PASSED  
    rgb_permutations|   4|    100000|     100|0.83822314|  PASSED  
    rgb_permutations|   5|    100000|     100|0.89281775|  PASSED  
      rgb_lagged_sum|   0|   1000000|     100|0.91937872|  PASSED  
      rgb_lagged_sum|   1|   1000000|     100|0.92678347|  PASSED  
      rgb_lagged_sum|   2|   1000000|     100|0.69557514|  PASSED  
      rgb_lagged_sum|   3|   1000000|     100|0.21126143|  PASSED  
      rgb_lagged_sum|   4|   1000000|     100|0.93110517|  PASSED  
      rgb_lagged_sum|   5|   1000000|     100|0.25499400|  PASSED  
      rgb_lagged_sum|   6|   1000000|     100|0.51833798|  PASSED  
      rgb_lagged_sum|   7|   1000000|     100|0.88552395|  PASSED  
      rgb_lagged_sum|   8|   1000000|     100|0.95324482|  PASSED  
      rgb_lagged_sum|   9|   1000000|     100|0.36948090|  PASSED  
      rgb_lagged_sum|  10|   1000000|     100|0.97142801|  PASSED  
      rgb_lagged_sum|  11|   1000000|     100|0.34498649|  PASSED  
      rgb_lagged_sum|  12|   1000000|     100|0.14386871|  PASSED  
      rgb_lagged_sum|  13|   1000000|     100|0.36969084|  PASSED  
      rgb_lagged_sum|  14|   1000000|     100|0.53271683|  PASSED  
      rgb_lagged_sum|  15|   1000000|     100|0.68518713|  PASSED  
      rgb_lagged_sum|  16|   1000000|     100|0.58691306|  PASSED  
      rgb_lagged_sum|  17|   1000000|     100|0.41468276|  PASSED  
      rgb_lagged_sum|  18|   1000000|     100|0.99927705|   WEAK   
      rgb_lagged_sum|  19|   1000000|     100|0.75588692|  PASSED  
      rgb_lagged_sum|  20|   1000000|     100|0.29024633|  PASSED  
      rgb_lagged_sum|  21|   1000000|     100|0.49798706|  PASSED  
      rgb_lagged_sum|  22|   1000000|     100|0.81814217|  PASSED  
      rgb_lagged_sum|  23|   1000000|     100|0.48908792|  PASSED  
      rgb_lagged_sum|  24|   1000000|     100|0.68475968|  PASSED  
      rgb_lagged_sum|  25|   1000000|     100|0.11647052|  PASSED  
      rgb_lagged_sum|  26|   1000000|     100|0.65130716|  PASSED  
      rgb_lagged_sum|  27|   1000000|     100|0.25758832|  PASSED  
      rgb_lagged_sum|  28|   1000000|     100|0.93261740|  PASSED  
      rgb_lagged_sum|  29|   1000000|     100|0.28195775|  PASSED  
      rgb_lagged_sum|  30|   1000000|     100|0.77776696|  PASSED  
      rgb_lagged_sum|  31|   1000000|     100|0.26310453|  PASSED  
      rgb_lagged_sum|  32|   1000000|     100|0.25564106|  PASSED  
     rgb_kstest_test|   0|     10000|    1000|0.74053801|  PASSED  
     dab_bytedistrib|   0|  51200000|       1|0.57423673|  PASSED  
             dab_dct| 256|     50000|       1|0.47610048|  PASSED  
Preparing to run test 207.  ntuple = 0
        dab_filltree|  32|  15000000|       1|0.40906494|  PASSED  
        dab_filltree|  32|  15000000|       1|0.82481224|  PASSED  
Preparing to run test 208.  ntuple = 0
       dab_filltree2|   0|   5000000|       1|0.83843441|  PASSED  
       dab_filltree2|   1|   5000000|       1|0.22720230|  PASSED  
Preparing to run test 209.  ntuple = 0
        dab_monobit2|  12|  65000000|       1|0.07582957|  PASSED
jhibbits added inline comments.Aug 2 2018, 2:35 PM
sys/dev/random/darn.c
68 ↗(On Diff #46156)

'2' denotes 'Raw random number (unconditioned by hardware/firmware/whatever)'
'1' denotes 'Conditioned random number (remove bias, etc)'

I *think* raw is what we want, but I'm not certain. A RNG expert would know better.

86 ↗(On Diff #46156)

This, along with the vast majority of the skeleton of this, was brought over from ivy.c. I haven't verified it on anything other than the testing I've done on real hardware (running math/dieharder over an array of changes of kern.random.harvest.mask)

Thanks for the heads-up on this.

cem added a subscriber: cem.Aug 8 2018, 8:29 PM

You want conditioned input. For verifying the entropy guarantee's assumption, it would be useful to provide both raw and conditioned values through a dtrace probe or sysctl or something. Then you run the raw (or conditioned) output through something like: https://github.com/usnistgov/SP800-90B_EntropyAssessment

See also earlier testing https://github.com/badfilemagic/fbsd-entropy .

delphij accepted this revision.Aug 9 2018, 7:12 AM
delphij added a subscriber: delphij.

LGTM'ing so we don't become a blocker (the code construction is similar to ivy.c). Please go ahead with commit after 14th August if nobody raises problems that they thinks should block the commit.

sys/dev/random/darn.c
68 ↗(On Diff #46156)

I don't think it really matters due to the construction of Fortuna but I'd defer that to a real cryptographer.

It would be worthy to mention what '2' (or if "conditioned" number is desirable, '1'; personally I think the difference is neglectable, because we would use a SHA256_Update to blend it into the pool, which itself serves as a conditioning procedure, if the "bias" was referring to bits in the number read) means here in the comment or provide a reference to PowerPC ISA by the way.

It's somewhat surprising to me that the designer used ~0 as an indicator that there were something wrong, which would result in a slight bias but due to the range of possible results from darn, if that's an issue we probably have a lot more to worry about.

This revision is now accepted and ready to land.Aug 9 2018, 7:12 AM
jmg added a comment.Aug 9 2018, 12:24 PM

looks fine. Agree that conditioned output should be used. We do our own conditioning so it wouldn't be a major problem to use the raw, but the raw will likely have less entropy.

This revision was automatically updated to reflect the committed changes.