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

[Eugen Leitl]

----- Forwarded message from Russell Leidich <pkejjy at gmail.com> -----

Date: Sat, 20 Jul 2013 16:17:32 +0000
From: Russell Leidich <pkejjy at gmail.com>
To: cryptography at randombit.net
Subject: Re: [cryptography] [liberationtech] Random number generator failure in Rasperri Pis?

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
>

_______________________________________________
cryptography mailing list
cryptography at randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography


----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5