[Cryptography] Fun with hardware RNGS: the Infinite Noise Multiplier

[Bill Cox]

On Sun, Dec 8, 2013 at 10:23 PM, Phillip Hallam-Baker <hallam at gmail.com>wrote:

> What about RF emissions made by the circuit?
>
> This contraption seems like it would bleed its output into the RF
> spectrum.
>
> --
> Website: http://hallambaker.com/
>

Like any clocked digital chip, it will put out some RF, though I expect it
to be low.  This is a slow low power .35u CMOS process, with about 0.4
milliwatt of power per Infinite Noise Multiplier, and there will be 16 of
those.  The clocked comparator in each INM is differential, and should
generate nearly the same power spike for a 1 or a 0.  All other power drawn
by each INM is in the form of constant current sources in the voltage
buffers, so they should be very hard to read from noise on external power
pins.  Shorting the .1pF caps to each other on clock edges doesn't impact
AVDD or AVSS currents, and also should not be detectable from external
power pins.  I do not know if this would be detectable from outside the
package with an RF detector.  Does anyone have a cool application for
microcontroller with a true RNG that needs super-secret random data that
remains secret even when the attacker has a logic analyzer attached to the
chip and some sort of RF detector?  I would need advice on what sorts of
on-chip events are detectable.  I don't have any equipment capable of
detecting such low level RF spikes.

I had some fun yesterday and wrote code to predict the output bits based on
the previous 8.  It achieved a 74.5% success rate predicting the SPICE
output, which is about what I expected.  Today wrote code to eliminate most
of the bias and correlations as a post-process, and it defeats my
prediction code.  The algorithm is pretty cool.  I think I can get the data
to be around 99% free of correlation and bias, while compressing this data
by about 2X.  This would make the bias drop by a factor of 0.02 for each
compressed bit XORed together, rather than the 0.5 I get now, meaning I get
about a 2.8X improvement in output rate at the same quality.  That would
provide bits with no more than about 1e-24 of non-randomness leading to a
rate of about 5 M-bits/sec.

The bias/correlation removal algorithm has two parts.  First, read about a
megabyte (8 seconds worth) from a given channel, and use it to gather
prediction statistics.  For each place a given 8-bit sequence occurs,
record how many times the next bit is a 1 and how many times it's a 0 in
arrays called 'zeros' and 'ones'.  Then, as bits come in, I run the
following C code to remove the detected bias and correlation:

void removeBias(int *data, int length) {
    double prob, lower = 0.0, upper = 1.0;
    int i;
    unsigned char value = 0;
    for(i = 0; i < length; i++) {
        if(data[i]) {
            prob = ((double)zeros[value])/(ones[value] + zeros[value]);
            lower += prob*(upper - lower);
        } else {
            prob = ((double)ones[value])/(ones[value] + zeros[value]);
            upper -= prob*(upper - lower);
        }
        while(lower >= 0.5 || upper <= 0.5) {
            if(upper <= 0.5) {
                upper *= 2.0;
                lower *= 2.0;
                printf("0");
            } else {
                printf("1");
                upper = 2.0*upper - 1.0;
                lower = 2.0*lower - 1.0;
            }
        }
        value <<= 1;
        if(data[i]) {
            value |= 1;
        }
    }
    printf("\n");
}

For use in one-time-pad encryption or generating keys, I'd still want to
XOR 14 of these 2-to-1 compressed bits together, and then run a
cryptographic randomizer on the results.  I don't think I use any hash
function like SHA-256 which is not reversible, unless someone convinces me
that it does not introduce correlations.  Any permutation should be fine,
such as encrypting the random data with block-chained AES-256 and a random
key.  Does that sound reasonable?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131209/d2d4a0e8/attachment.html>