[cryptography] [liberationtech] Random number generator failure in Rasperri Pis?

Russell Leidich pkejjy at gmail.com
Sat Jul 20 12:17:32 EDT 2013


I agree, in theory. But:

1. How many register reads would one need in order to show Birthday
compliance? (It's not the usual "root of the state space", because a single
collision isn't convincing.) These reads tend to be slow, because the
circuit designers generally need to guardband their entropy accrual to meet
some particular minimum. In particular, we're looking for "good" evidence
of a Poisson distribution, so we're up against a "lot" of reads relative to
what Birthday attacks would suggest. If we don't have enough bits in memory
to map the whole entropy register state space with acceptable access
latency, then we have to do a realtime index-and-lookup of historical
values, which is increasingly expensive over time. Even having generated
said distribution successfully, the temperature and EMI background change
with the wind. So wash, rinse, repeat.

2. More simply, we could generate a PRNG with a nice Poisson profile. While
the initial read might be somewhat random in order to spoof a decent TRNG,
subsequent reads would just iterate the PRNG, facilitating differential
attacks. But this wouldn't be easy to detect if, say, I had 128 bits of
state backing up a 32-bit fake TRNG register.

3. The hardware TRNG characterization process cannot be parallelized,
because we need to determine the trustworthiness of the particular CPU in
question. By contrast, an individual userspace TRNG (UTRNG) can be verified
by simply comparing a hash of its executable code against expected public
values. But we can't take the hash of a physical circuit.

4. Having verified that an individual UTRNG instance is identical to what's
expected, the only remaining question is how fast it can generate entropy
in the least entropic possible use case. That's not a trivial question to
answer, but at least, parallel processing can accelerate this
characterization. If it turns out to be a "good" TRNG, then at runtime, we
can simply check the hash, rather than repeating the characterization
because the physical environment is different.

Again, I'm no quantum denialist. There's plenty of noise out there. But
it's always nice to keep the trust radius to a manageable minimum.

On Sat, Jul 20, 2013 at 12:59 PM, Dean, James <Jdean at lsuhsc.edu> wrote:
>
> Ø  If my 64-bit hardware TRNG can only generate 1% of 64-bit numbers
(probably because I hacked it), how are you going to discover that anytime
soon?
>
>
>
> Test for more collisions than predicted by the birthday paradox.
>
>
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130720/b1f98719/attachment.html>


More information about the cryptography mailing list