Push-Button Random Number Generator

Reprint of an email to team building a Bitcoin hardware wallet, who had asked me for help with their RNG design:

> - floating ADC inputs, as Peter suggested;
> - five independent RC oscillators.

I’ve got another idea that requires no extra hardware. I think has a solid theoretical basis which I’ve explored below in sufficient detail to raise suspicions that I miss my old line of work¹:

tl;dr: Record the \(dt\) time between button clicks, adding \(dt\) to the accumulator each time by hashing it into the persistent state.

Theoretical Basis

We assume that the timing accuracy of a button click has a normal distribution. That is even a human deliberately trying to maintain a consistent tempo, \(dt\), between clicks will in fact have a normally distributed error. Humans can be remarkably accurate when they want to be, but timing data from studies of drumming²³ and throwing⁴ suggests that assuming 1ms jitter in muscle timing accuracy is very generous. Assuming that jitter is normally distributed is reasonable.

We can easily measure the time between clicks with a interrupt driven polling function. You’re probably using something like a 12MHz clock for your μC due to the USB interface. Incrementing a timing counter, checking the button pin state, and saving that counter if the pin state has changed should take under 16 cycles or so; triggering the interrupt every 256 cycles is likely quite reasonable giving us a button sampling frequency of \(12MHz/256 \approx 50kHz\). The button itself is an RC circuit; \(C=100pF\) and \(R=4.7kΩ\) is perfectly reasonable for the circuit on its own, but let’s bump that to \(C=1nF\) to account for human body capacitance.

Input low and input high are generally \(0.15 \cdot V_{DD}\) and \(0.85 \cdot V_{DD}\) respectively. Thus if we’re to accurately record the state of the button on a high→low transition we need to wait:

Exactly what this means for your circuit is kinda complex - Are inputs re-synchronized with the usual clock-domain crossing flip-flops? - but to say it results in a max sampling rate of 100kHz isn’t unreasonable; our 50kHz number above looks fine.

The worst case scenario for RNG generation is when our user is a skilled drummer listening to machine-made techno music who can’t help but do everything exactly according to the impersonal machine rhythm. Our mean μ is that rhythm - likely around 150BPM if they have good taste - and as per the above data we’ll assume one standard deviation, σ, is 1ms. This means that there is a 68% chance that a given sample will be within ±1mS; put another way there is a 32% chance that the sample will yield a random value. Thus hand-wave a bit and say this sample represents 0.32 bits of uncertainty (in that which side of the gaussian curve the sample “landed on” was unknown).

The next bit of our measurement is even better: ±0.5ms is half a standard deviation with a 61.8% chance the sample will yield an unknown value, ±0.25ms 80% etc. Basically the measurement is far more accurate than the user, so the LSBs of the measurement are random noise. The proposed 50kHz sampling rate means that we get about four or five bits of entropy per button press; we certainly get at least one bit.

Why can we trust this source of entropy?

1. We know exactly what is generating the random noise - the user’s inherent inability to accurately press a button. There are no conceivable circumstances where that noise source would fail to exist.

2. The source is very difficult for the attacker to observe. The phase resolution required to accurately pick up the lowest-order bits of the button press with, say, a microphone exceeds that available in standard audio equipment by a good margin even in the worst-case; better if the sampling rate is increased. The miniscule amount of charge moved per button press is highly unlikely to be the worst contributor to a power analysis attacker’s success.

3. The electrical design steers well clear of anything that can be influenced by external noise. The 4.7kΩ pull-up makes the switch essentially immune to external noise; if noise is influencing the RNG the device obviously fails anyway. The switch is immune to anything short of high vibration, whose exact phase would be certainly unknown to the attacker anyway.

4. The firmware design is simple and requires nothing more than a free-running counter.

5. Testing the design is easy: just record \(dt\) for many button presses in a row and plot the ratio of 1:0 for each bit, MSB to LSB. If the RNG source is working the LSB’s will tend towards 0.5

User Experience

Every time you press the new key button, an adorable kitten working for the NSA sheds a single tear. We recommend you make that kitten shed at least 32 tears, 128 if you’re feeling paranoid.

References