search

tillitis / tillitis-key1

Board designs, FPGA verilog, firmware for TKey, the flexible and open USB security key 🔑
https://www.tillitis.se
382 stars 24 forks source link

Js xorshift init #231

Closed secworks closed 3 weeks ago

secworks commented 4 weeks ago

Use xorshift instead of xorwow.

  1. We need to check impact on boot time and compare to xorwow.
  2. We need to check the quality of the random data generated and compare to xorwow.

We can use this draft PR for documentation.

secworks commented 4 weeks ago

Generating 400 MByte of random data and feeding it to ENT:

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 400000000 byte file by 0 percent.

Chi square distribution for 400000000 samples is 267.52, and randomly
would exceed this value 28.26 percent of the times.

Arithmetic mean value of data bytes is 127.4955 (127.5 = random).
Monte Carlo value for Pi is 3.141922531 (error 0.01 percent).
Serial correlation coefficient is -0.000112 (totally uncorrelated = 0.0).
secworks commented 4 weeks ago

Test results from PractRand:

RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = core, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 3.8 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+0,13-1,T)                  R=+261.5  p =  2.9e-140   FAIL !!!!!
  BCFN(2+1,13-1,T)                  R= +33.3  p =  2.1e-17    FAIL !
  BCFN(2+2,13-2,T)                  R= +18.1  p =  7.7e-9    VERY SUSPICIOUS
  BCFN(2+3,13-2,T)                  R=  +9.4  p =  2.0e-4   unusual
  BCFN(2+4,13-3,T)                  R=  +1.5  p = 0.258     normal
  BCFN(2+5,13-3,T)                  R=  -1.9  p = 0.781     normal
  BCFN(2+6,13-4,T)                  R=  -2.1  p = 0.803     normal
  BCFN(2+7,13-5,T)                  R=  +1.8  p = 0.213     normal
  BCFN(2+8,13-5,T)                  R=  +2.1  p = 0.185     normal
  BCFN(2+9,13-6,T)                  R=  +3.2  p = 0.101     normal
  BCFN(2+10,13-6,T)                 R=  +2.9  p = 0.116     normal
  BCFN(2+11,13-7,T)                 R=  -0.1  p = 0.467     normal
  BCFN(2+12,13-8,T)                 R=  +1.1  p = 0.273     normal
  BCFN(2+13,13-8,T)                 R=  -1.7  p = 0.765     normal
  BCFN(2+14,13-9,T)                 R=  +1.1  p = 0.252     normal
  BCFN(2+15,13-9,T)                 R=  -1.1  p = 0.638     normal
  DC6-9x1Bytes-1                    R= +4057  p =  1e-2380    FAIL !!!!!!!!
  Gap-16:A                          R=  +7.3  p =  1.1e-5   suspicious
  Gap-16:B                          R=  +7.9  p =  8.5e-7   very suspicious
  FPF-14+6/16:(0,14-0)              R=  -5.4  p =1-1.0e-4   normalish
  FPF-14+6/16:(1,14-0)              R=  -4.6  p =1-5.7e-4   normal
  FPF-14+6/16:(2,14-0)              R=  -3.6  p =1-5.2e-3   normal
  FPF-14+6/16:(3,14-0)              R=  -5.0  p =1-2.8e-4   normal
  FPF-14+6/16:(4,14-0)              R=  -4.0  p =1-2.5e-3   normal
  FPF-14+6/16:(5,14-1)              R=  -2.7  p = 0.975     normal
  FPF-14+6/16:(6,14-2)              R=  -1.7  p = 0.893     normal
  FPF-14+6/16:(7,14-2)              R=  -3.1  p = 0.986     normal
  FPF-14+6/16:(8,14-3)              R=  -1.3  p = 0.823     normal
  FPF-14+6/16:(9,14-4)              R=  -0.4  p = 0.604     normal
  FPF-14+6/16:(10,14-5)             R=  -2.3  p = 0.949     normal
  FPF-14+6/16:(11,14-5)             R=  -0.1  p = 0.532     normal
  FPF-14+6/16:(12,14-6)             R=  -2.8  p = 0.982     normal
  FPF-14+6/16:(13,14-7)             R=  -0.3  p = 0.574     normal
  FPF-14+6/16:(14,14-8)             R=  +2.7  p = 0.039     normal
  FPF-14+6/16:(15,14-8)             R=  -1.7  p = 0.897     normal
  FPF-14+6/16:(16,14-9)             R=  +0.2  p = 0.423     normal
  FPF-14+6/16:(17,14-10)            R=  -0.9  p = 0.708     normal
  FPF-14+6/16:(18,14-11)            R=  +0.7  p = 0.257     normal
  FPF-14+6/16:(19,14-11)            R=  +1.1  p = 0.188     normal
  FPF-14+6/16:all                   R= -11.3  p =1-1.1e-10   VERY SUSPICIOUS
    FPF-14+6/16:cross                 R=  +0.7  p = 0.229     normal
  BRank(12):128(4)                  R= +3922  p~=  8e-2087    FAIL !!!!!!!!
  BRank(12):256(4)                  R= +9433  p~=  7e-5018    FAIL !!!!!!!!
  BRank(12):384(1)                  R= +7472  p~=  2e-2250    FAIL !!!!!!!!
  BRank(12):512(2)                  R=+14464  p~=  4e-4355    FAIL !!!!!!!!
  BRank(12):768(1)                  R=+15738  p~=  8e-4739    FAIL !!!!!!!!
  BRank(12):1K(2)                   R=+30051  p~=  2e-9047    FAIL !!!!!!!!
  BRank(12):1536(1)                 R=+32271  p~=  1e-9715    FAIL !!!!!!!!
  BRank(12):2K(1)                   R=+43293  p~= 0           FAIL !!!!!!!!
  mod3n(5):(0,9-0)                  R=  -1.9  p = 0.834     normal
  mod3n(5):(1,9-1)                  R=  -1.4  p = 0.756     normal
  mod3n(5):(2,9-1)                  R=  -0.2  p = 0.540     normal
  mod3n(5):(3,9-2)                  R=  -0.5  p = 0.597     normal
  mod3n(5):(4,9-2)                  R=  +0.1  p = 0.474     normal
  mod3n(5):(5,9-3)                  R=  +0.9  p = 0.311     normal
  mod3n(5):(6,9-3)                  R=  +0.5  p = 0.398     normal
  mod3n(5):(7,9-4)                  R=  -0.9  p = 0.666     normal
  mod3n(5):(8,9-4)                  R=  -0.6  p = 0.598     normal
  mod3n(5):(9,9-5)                  R=  +0.5  p = 0.375     normal
  mod3n(5):(10,9-5)                 R=  -1.9  p = 0.844     normal
  mod3n(5):(11,9-6)                 R=  +0.4  p = 0.358     normal
  mod3n(5):(12,9-6)                 R=  -0.4  p = 0.535     normal
  mod3n(5):(13,9-6)                 R=  +2.0  p = 0.142     normal
  mod3n(5):(14,9-6)                 R=  +1.7  p = 0.172     normal
  mod3n(5):(15,9-6)                 R=  -0.5  p = 0.559     normal
  TMFn(2+0):wl                      R=  -3.1  p~= 0.8       normal
  TMFn(2+1):wl                      R=  -0.4  p~= 0.6       normal
  TMFn(2+2):wl                      R=  -0.5  p~= 0.6       normal
  TMFn(2+3):wl                      R=  +0.4  p~= 0.4       normal
  TMFn(2+4):wl                      R=  +1.2  p~= 0.3       normal
  [Low1/8]BCFN(2+0,13-3,T)          R=  -0.9  p = 0.633     normal
  [Low1/8]BCFN(2+1,13-3,T)          R=  -3.1  p = 0.902     normal
  [Low1/8]BCFN(2+2,13-4,T)          R=  -2.6  p = 0.864     normal
  [Low1/8]BCFN(2+3,13-4,T)          R=  -1.1  p = 0.665     normal
  [Low1/8]BCFN(2+4,13-5,T)          R=  +2.3  p = 0.172     normal
  [Low1/8]BCFN(2+5,13-5,T)          R=  -4.8  p = 0.987     normal
  [Low1/8]BCFN(2+6,13-6,T)          R=  -0.2  p = 0.498     normal
  [Low1/8]BCFN(2+7,13-6,T)          R=  -1.4  p = 0.695     normal
  [Low1/8]BCFN(2+8,13-7,T)          R=  +0.9  p = 0.316     normal
  [Low1/8]BCFN(2+9,13-8,T)          R=  +1.1  p = 0.266     normal
  [Low1/8]BCFN(2+10,13-8,T)         R=  -1.0  p = 0.613     normal
  [Low1/8]BCFN(2+11,13-9,T)         R=  -0.8  p = 0.577     normal
  [Low1/8]BCFN(2+12,13-9,T)         R=  -3.2  p =1-8.1e-3   normal
  [Low1/8]DC6-9x1Bytes-1            R=  +2.5  p = 0.179     normal
  [Low1/8]Gap-16:A                  R=  +3.6  p = 0.017     normalish
  [Low1/8]Gap-16:B                  R=  +1.8  p = 0.105     normal
  [Low1/8]FPF-14+6/16:(0,14-0)      R=  -1.0  p = 0.754     normal
  [Low1/8]BCFN(2+10,13-8,T)         R=  -1.0  p = 0.613     normal
  [Low1/8]BCFN(2+11,13-9,T)         R=  -0.8  p = 0.577     normal
  [Low1/8]BCFN(2+12,13-9,T)         R=  -3.2  p =1-8.1e-3   normal
  [Low1/8]DC6-9x1Bytes-1            R=  +2.5  p = 0.179     normal
  [Low1/8]Gap-16:A                  R=  +3.6  p = 0.017     normalish
  [Low1/8]Gap-16:B                  R=  +1.8  p = 0.105     normal
  [Low1/8]FPF-14+6/16:(0,14-0)      R=  -1.0  p = 0.754     normal
  [Low1/8]FPF-14+6/16:(1,14-0)      R=  -0.7  p = 0.694     normal
  [Low1/8]FPF-14+6/16:(2,14-1)      R=  +2.0  p = 0.083     normal
  [Low1/8]FPF-14+6/16:(3,14-2)      R=  -0.5  p = 0.638     normal
  [Low1/8]FPF-14+6/16:(4,14-2)      R=  +1.3  p = 0.175     normal
  [Low1/8]FPF-14+6/16:(5,14-3)      R=  -0.7  p = 0.691     normal
  [Low1/8]FPF-14+6/16:(6,14-4)      R=  +0.8  p = 0.288     normal
  [Low1/8]FPF-14+6/16:(7,14-5)      R=  +1.4  p = 0.158     normal
  [Low1/8]FPF-14+6/16:(8,14-5)      R=  +0.2  p = 0.435     normal
  [Low1/8]FPF-14+6/16:(9,14-6)      R=  -1.9  p = 0.913     normal
  [Low1/8]FPF-14+6/16:(10,14-7)     R=  +3.0  p = 0.024     normal
  [Low1/8]FPF-14+6/16:(11,14-8)     R=  +0.6  p = 0.328     normal
  [Low1/8]FPF-14+6/16:(12,14-8)     R=  +1.1  p = 0.209     normal
  [Low1/8]FPF-14+6/16:(13,14-9)     R=  -0.8  p = 0.685     normal
  [Low1/8]FPF-14+6/16:(14,14-10)    R=  -0.4  p = 0.561     normal
  [Low1/8]FPF-14+6/16:(15,14-11)    R=  +3.3  p = 0.029     normal
  [Low1/8]FPF-14+6/16:(16,14-11)    R=  -2.0  p = 0.976     normal
  [Low1/8]FPF-14+6/16:all           R=  +0.2  p = 0.448     normal
  [Low1/8]FPF-14+6/16:cross         R=  -0.7  p = 0.761     normal
  [Low1/8]BRank(12):128(4)          R= +3922  p~=  8e-2087    FAIL !!!!!!!!
  [Low1/8]BRank(12):256(2)          R= +6670  p~=  5e-2009    FAIL !!!!!!!!
  [Low1/8]BRank(12):384(1)          R= +7472  p~=  2e-2250    FAIL !!!!!!!!
  [Low1/8]BRank(12):512(2)          R=+14464  p~=  4e-4355    FAIL !!!!!!!!
  [Low1/8]BRank(12):768(1)          R=+15738  p~=  8e-4739    FAIL !!!!!!!!
  [Low1/8]BRank(12):1K(1)           R=+21249  p~=  9e-6398    FAIL !!!!!!!!
  [Low1/8]mod3n(5):(0,9-2)          R=  -1.6  p = 0.788     normal
  [Low1/8]mod3n(5):(1,9-2)          R=  +2.5  p = 0.107     normal
  [Low1/8]mod3n(5):(2,9-3)          R=  -0.8  p = 0.644     normal
  [Low1/8]mod3n(5):(3,9-3)          R=  +3.1  p = 0.063     normal
  [Low1/8]mod3n(5):(4,9-4)          R=  -1.0  p = 0.690     normal
  [Low1/8]mod3n(5):(5,9-4)          R=  -1.9  p = 0.828     normal
  [Low1/8]mod3n(5):(6,9-5)          R=  -0.6  p = 0.597     normal
  [Low1/8]mod3n(5):(7,9-5)          R=  +0.4  p = 0.377     normal
  [Low1/8]mod3n(5):(8,9-6)          R=  -0.4  p = 0.521     normal
  [Low1/8]mod3n(5):(9,9-6)          R=  +1.5  p = 0.193     normal
  [Low1/8]mod3n(5):(10,9-6)         R=  +0.2  p = 0.394     normal
  [Low1/8]mod3n(5):(11,9-6)         R=  +0.1  p = 0.414     normal
  [Low1/8]mod3n(5):(12,9-6)         R=  -1.1  p = 0.692     normal
  [Low1/8]TMFn(2+0):wl              R=  +0.4  p~= 0.4       normal
  [Low1/8]TMFn(2+1):wl              R=  +2.6  p~= 0.2       normal
secworks commented 4 weeks ago

If we look at the results we can see that ENT thinks that xorshift is close in quality to xorwow. But ENT is not able to detect long distans patterns, linear relations. PractRand howerver can. If we compare the results with PR https://github.com/tillitis/tillitis-key1/pull/201 we can see that more tests fails.

For RAM randomization xorshift is probably good enough. However if the difference in execution time is not very different, I'd propose that we select xorwow due to it being better.

Note that one difference between xorwow and xorshift that will reduce execution time is not reading a second time from the TRNG.

secworks commented 4 weeks ago

A quick analysis on the performande. The big difference between xorwow and xorshift are:

  1. One extra read operation from the TRNG (right after the first)
  2. One addition opreration

My guess is that (1) is the one adding most of the difference in execution time. The TRNG bitrate is in order of 3 kHz. The addition operation should map to a single instruction. We will do 32k additions when filling the RAM. At 18 MHz this should take about 0.0017 seconds.

dehanj commented 3 weeks ago

xorshift takes 114 ms to complete.

dehanj commented 3 weeks ago

We will move forward using xorwow instead.