[Cryptography] A TRNG review per day (week?): ATSH204A

[dj at deadhat.com]

On 11/9/14, 5:16 AM, Bill Cox wrote:
>
> "Certain randomness extractors need a random seed."
>
> Huh?  Which randomness extractors require a random seed?  This is a
scary level of ignorance for guys implementing such critical security
code.  If the MiB have a copy of every ATSHA204A's seed, they might be
able to PWN a huge number of routers.
>
> Here's a great quote on this thread from the data sheet:
>
> "Random numbers are generated from a combination of the output of a
hardware random number generator and an internal seed value, which| is
not externally accessible. The internal seed is stored in the EEPROM,
and is normally updated once after every power-up or sleep|wake cycle."
>
> If the TRNG is capable of producing even 200 bits of entropy, then why
do they need the seed at all?  Why bother to "update" it?  Here's what I
think: they only implemented a short counter to save a few gates.  When
it overflows, the device will start spitting out repeated "random"
values.

--

The description is correct. It doesn't indicate whether they are doing
that, or something else, but the math of extractor theory says there is no
such thing as a perfect single source extractor without a 'seed' or
'advice', which is itself a full entropy bit string. This describes a
chicken-and-egg situation. How do you get a full entropy seed for your
full entropy extractor if no full entropy extractor exists until the full
entropy seed exists?

But extractor theory has moved on. Dodis et al showed that you can't have
a perfect single source extactor, but you can show computational bounds on
the attacker and that's good enough for crypto.

Barack, Impagliazzo and Wigdersen '06 showed that you can have a multi
input extractor provided the inputs are independent.

There is a constant stream of new findings and I can't keep up with it.
Dodis gave an excellent extractor paper at EuroCrypt this year, which was
a refreshing change from all the MPC and HE stuff, but the content leaked
out of my ears a while back.

>Here's what I think: they only implemented a short counter to save a few
gates.

That's what I did. SP800-90A says reseed or block at 2^40 generate()s. But
if you're going to reseed long before 2^40, why waste gates on a long
counter?

If they've done a single source extractor with advice, then I don't know
what magic wand they used to create that advice.