[Cryptography] Whitening Algorithm

[John Denker]

On 07/22/2015 07:50 PM, Rob Seward wrote:

> I’m trying to whiten a random noise source (a reverse biased transistor)
> with a low-powered microprocessor. I figured out a technique that seems to
> work well, and I want to know if there is anything insecure or subpar about
> it.

This is the proverbial elephant.  It can be approached
from a number of different directions.  It's a lot 
easier to grasp part of the problem than to understand
the whole thing.

Here's one leg of the elephant.  IF (big IF) you look
at it as a purely mathematical cryptography question,
a whitener is virtually indistinguishable from a hash
function.  So the basic question becomes finding a
cryptologically strong hash function that doesn't
burden the CPU.

The best you can hope to achieve by such a process
is a PRNG.  Given a hash function, using it as the
basis for a decent PRNG is non-obvious.  I recommend
reading something like
   Elaine Barker and John Kelsey,
   NIST Special Publication: 
   “Recommendation for Random Number Generation Using Deterministic Random Bit Generators”
   http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
   http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90b.pdf

There's a lot of complexity there, and at first glance
you might think you can come up with something simpler
... but there are very specific attacks that those
complicated features are meant to defend against.  So
it quickly comes down to the old question:  WYTM?
What's your threat model?  If you're defending against
only one particular narrow threat, it's easy to come
up with something that works.  OTOH if you're trying
to defend against an advanced persistent threat, you 
need to do a lot of detailed analysis.  Even if you
stick to using tried-and-true crypto primitives, the
way in which you combine the primitives matters a
great deal.


Here's a completely different way of approaching the
elephant.  It's impossible in principle to design a
decent RNG unless you know a lot about the hardware
and about the underlying physics.  This includes the
physics of normal operation, the physics of plausible
natural degradation, and the physics of possible
attacks.  So for sake of argument, let's suppose you
know absolutely that the transistor puts out 1/f 
noise.  Then you can run that through a digital 
filter and get out nice white noise ... no crypto 
required.  The required filter requires very little
computation.

Let's be clear:  There are approaches that rely on
crypto with almost no physics ... and approaches
that rely on physics with almost no crypto.  I
tend to prefer designs that get the physics right
/and/ get the crypto right.

On 07/23/2015 07:07 AM, dj at deadhat.com made a number
of good points.

>> What you want it an entropy extractor.

Well, yes, no, and maybe.  It depends on what you
mean by entropy ... and it depends on your threat
model.  There are plenty of situations where the
honest-to-goodness physics entropy is not what you
want.  You might need something more along the 
lines of the H_∞ Rényi functional.  Some folks
consider that some kind "generalized" entropy but 
I'm not at all convinced that's a good idea.  Most 
people who throw around the word "entropy" have 
no idea what it means.

Calibrating a piece of hardware to ascertain how
much entropy (or whatever) it produces is a lot 
of work.

=========

Last but not least, what's really going on here?
What's the motivation?  What's the objective?  TRNG
or CSPRNG or ....?   What are the real constraints? 
What's the threat model?  Unless you have some very 
specialized high-volume low-cost application in mind,
there are other solutions that cost less and work 
better (compared to custom hardware).