search

travisgoodspeed / goodwatch

Replacement board for Casio Calculator Watches using the CC430F6147
504 stars 55 forks source link

RNG Quality Control #67

Closed travisgoodspeed closed 6 years ago

travisgoodspeed commented 6 years ago

A quick check of the true_rand() function as a scatterplot of the high and low bytes shows awkward grouping. I think that we might need to let the clocks drift further, or perhaps whiten the data through the hardware-accelerated AES module.

image

Use this issue to track the RNG tests, and close it when we're convinced that the samples are good.

travisgoodspeed commented 6 years ago

The plot above can be recreated like so.

x270% ./goodwatch.py --randdump samples2.txt
Fetching samples.
x270% gnuplot
Terminal type set to 'qt'
gnuplot> plot 'samples2.txt'
gnuplot>
ea commented 6 years ago

I've run some tests as well. Could it be that "turbo" mode has a significant effect on this?

I've tested the output with rngtest from rng-tools which implements standard FIPS 140-2 tests and here are my results.

First, testing true_rand as it is:

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 265280
rngtest: FIPS 140-2 successes: 0
rngtest: FIPS 140-2 failures: 13
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 13
rngtest: FIPS 140-2(2001-10-10) Runs: 13
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=9.313; avg=17.296; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=61.133; avg=62.473; max=63.367)Mibits/s
rngtest: Program run time: 4128 microseconds

That's not too bad. All blocks are failing "poker" and "runs" tests, while passing others. If I stop messing with ACLK divider, I get the following:

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 109440
rngtest: FIPS 140-2 successes: 3
rngtest: FIPS 140-2 failures: 2
rngtest: FIPS 140-2(2001-10-10) Monobit: 1
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=9.313; avg=15.522; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=57.974; avg=58.257; max=58.869)Mibits/s
rngtest: Program run time: 1874 microseconds

So, it might look a bit better. If I also don't mess with DCORSEL in each loop the results look even better :

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 654080
rngtest: FIPS 140-2 successes: 26
rngtest: FIPS 140-2 failures: 6
rngtest: FIPS 140-2(2001-10-10) Monobit: 6
rngtest: FIPS 140-2(2001-10-10) Poker: 1
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=6.209; avg=14.538; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=57.450; avg=58.318; max=60.551)Mibits/s
rngtest: Program run time: 10735 microseconds

Last run was longest and 26 out of 32 blocks passed. 6 failed monobit tests which would suggest some bias to either ones or zeroes.

In conclusion, it seems like messing with clocks on each loop makes things worse, but even so the RNG seems "good enough" for what it is. Any actual crypto use would definitely need whitening.

ea commented 6 years ago

Here's a plot without last two lines in the loop:

plot2

Indeed looks much better.

Just to be clear, SLAA338 give 3 ways of adding randomness:

Second two of these correspond to UCSCTL1 += 5; and UCSCTL5 ^= ((seed & 3) << 8) respectively. It seems like skipping these two steps makes for better results in this particular case.

ea commented 6 years ago

I found the bug. UCSCTL1 += 5; is incorrect, I misread the docs. The CC430 in question has DCORSEL bits at bit 4-6 of UCSCTL1 , not 0-3.

plot4

I'll run longer rngtest tests and see what we get.

ea commented 6 years ago

After running more tests, simply skipping omitting the two lines that mess with DCO speed and dividers seems to yield the best results. plot_both_disabled_many

Minor differences cannot be seen from this simple plot , but running rngtest on about 16k samples gives the following:

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 262144
rngtest: FIPS 140-2 successes: 9
rngtest: FIPS 140-2 failures: 4
rngtest: FIPS 140-2(2001-10-10) Monobit: 4
rngtest: FIPS 140-2(2001-10-10) Poker: 2
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=6.209; avg=12.107; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=54.340; avg=58.315; max=61.133)Mibits/s
rngtest: Program run time: 5350 microseconds

This still isn't ideally uniform, but I'd judge it "good enough" for current purposes. Any actual cryptographic use would warrant whitening via hash function or available hardware accelerated AES.