[Cryptography] grand principles and niggling details

Tue Dec 20 23:20:48 EST 2016

On 12/20/2016 04:15 PM, I wrote:

> Principle #1:  In the security business, there are very few grand 
> principles.  Mostly what we have is a boatload of niggling details.
> 
> Principle #2: The details matter.  You have to get the details
> right.

Here's another principle that all-too-often gets overlooked:

3) There is no such thing as a random number.

  You can have a random /distribution/ over numbers, but then the
  randomness is in the distribution, not in any number that may
  have been drawn from such a distribution.

  A distribution is different from a number in the way that an infinite-
  dimensional vector is different from a scalar.  It's a significant
  difference.

  You can also have a distribution over shapes, or colors, or other
  non-numerical things.

This has been well understood for more than 80 years\1,2,3\.  I trust
that most people on this list understand this, but more generally it
is astounding how many people didn't get the memo.

BTW:  I don't mind when people speak of a Random Number Generator, so
long as they diagram the sentence correctly:  It's a random generator
of numbers, not a generator of random numbers.  It might be better to
call it a Randomness Generator or Random Distribution Generator.

--------

4) There are some problems that cannot be solved in software ... yet
 can be readily solved by other means.

 Randomness is the poster child for this category of problems.  State
 of sin and all that.\3\

Here's a more prosaic example:  According to the HD Audio specification,
the plug-sense circuitry is «supposed» to be independent of the audio
signal circuitry.  (This differs from the old AC'97 specification, where
plug-sense was accomplished by shorting the audio signal to ground.)

In particular, HD Audio is «supposed» to be highly software-configurable,
up to and including reconfiguring input jacks to become output jacks.

In the real world, however, when dealing with security and so many other
things, what *is* differs from what is «supposed» to be.  Apparently some
super-genius decided it would be fun to make a combination audio panel
module, such that pulling the plug activates the plug-sense wire *and*
shorts the signal wire to ground.  I kid thee not.  I have seen this on
laptops from otherwise-competent manufacturers.

>From a randomness-generation point of view, this is a pain.  When the
pin is shorted to ground in hardware, there is nothing the software
can do about it.

The problem is however easy to solve at the hardware level.  My local
Ace Hardware store sells 1/8" diameter wooden dowel rods, 36" long, for
59 cents.  You can get the same thing at the hobby/model store, for a
slightly higher price.  One such rod is enough to make plugs that will
open-circuit the Mic input on several dozen computers.

Again the point is:  Sometimes a couple pennies' worth of hardware
will solve a problem that simply cannot be solved in software.

ON THE OTHER HAND ... these days, more and more machines do a decent
job of complying with the spirit of the HD Audio specification.  That
means if you ask nicely, you can record from the Mic input even when
nothing is plugged in.  So yes, /sometimes/ problems can be solved
in software.  You have to cook up a .fw file to put in /lib/firmware,
and cook up a .conf file to put in /etc/modprobe.d/, then you have
to unload and reload the hda-intel module.  It's kinda mysterious at
first, but it's permanent and works nicely.  You're aiming for this:
	[hint]
	jack_detect = false
	add_jack_modes = true

which gives you much finer control over the audio hardware, as
documented here:
  https://www.kernel.org/doc/Documentation/sound/alsa/HD-Audio.txt

This means you might not need to spend 59¢ on a dowel rod, and
confers other benefits as well.

> putting a lot of effort into designing and tuning a HWRNG is
> pointless
[...]
> provided you have an accurate lower bound on the entropy content

The key word there is «provided».  That's quite some proviso.  Is
there an easy way to obtain an «accurate lower bound»?  If so,
please explain.

Turbid is something like 35,000 lines of code at the moment, of which
only a tiny percentage has to do with actually collecting randomness.
The rest has to do with characterizing the hardware, i.e. trying to
obtain a decent bound on the amount of adamance in the raw signal.  I
don't know how to do that automatically.  Turbid does however offer
some powerful tools that an expert can use.  The task is difficult for
an expert, and well-nigh impossible for a non-expert, although I'm
trying to cook up a GUI and a set of procedures that will make it not
quite so impossible.  As for «accuracy», turbid doesn't need a tight
lower bound;  all it needs is a number that is low enough to be a
genuine lower bound yet high enough to provide decent throughput.

> But my baseline recommendation if you want to be exceptionally
> paranoid is to make an audio recording of some white-ish noise (e.g.
> record yourself saying “Shhh”) and then extract 1% or 0.1% of the
> result.

I don't think that should be the baseline recommendation.  That
might make sense in an unusual emergency situation.  Usually it
is better to _avoid_ emergency situations.  In particular, the
sneakernet / sourdough method mentioned on 12/20/2016 04:15 PM
is generally more convenient and more reliable, at least in the
situations I tend to run into ... and more suitable for becoming
a built-in feature on standard systems.

Also as mentioned on 12/20/2016 04:15 PM, the details matter.  In
particular, it matters what parameters you pass to the recording
program.

Here's a constructive suggestion:  In an emergency, try either:
        :; sox -r 48000 -b 32 -t alsa hw:0  -c 1 noise.wav  trim .1 3
or
        :; arecord -D hw:0 --disable-softvol -f S32_LE -r 48000 -V mono -d 3 noise.wav
then
        :; aplay noise.wav
        :; od -t x4 noise.wav

You may be wondering, why so complicated?   Why not just
	:; arecord noise.wav  ???

Well, as I said earlier, you have to get the details right.  A
list of pithy axioms is nice, but it diverts attention from the
other 99% of what you need to know.

 -- If you leave off the -r 48000, you are likely to get 8000
  frames per second, which costs you a factor of 6 in randomness
  productivity.  On the other hand, recording at a much higher
  rate wouldn't buy you much, because the noise bandwidth is
  limited by the $RC$ time constant of the input network.  I
  have a machine that will happily do 192000 frames per second.
  That's more samples, but it's not more randomness.  These are
  just a couple of the grotty details you need to know.

 -- If you leave off the -f S32_LE, you get 16-bit words, which
  is a disaster, because there is a great deal of randomness in
  the lower-order bits.  I have a desktop that gives 25 bits, and
  a laptop that gives 'only' 23 bits when digitizing the Mic-in
  signal.  You don't want to be throwing away 7 or 9 bits of
  randomness per sample.

 -- If you leave off the -D hw:0, it is quite possible that the
  'default' alsa device screws up the signal, e.g. by truncating
  it to 16 bits, even though the bits are delivered in a 32-bit
  word.  Don't ask me why it does this.  Turbid is careful to ask
  for the raw hardware device, but when you're using arecord from
  the command line, a lot of things can go wrong.

 -- If you leave off the --disable-softvol, you might get all zeros
  in the output file.  Don't ask me what arecord thinks it's doing.

 -- Overall sox is a better program, simultaneously easier to use
  (for me, anyway) and much more capable.  However I mention the
  corresponding arecord command also, because in a "Live CD"
  environment you might have arecord available but not sox.

 -- If you don't check your work, using at least od and aplay, all
  kinds of bad things could be happening and you wouldn't know.
  In a non-emergency situation, I would insist on doing a lot
  more checks than that, including impedance, gain, bandwidth,
  quantization, etc.

References:

\1\  Andrey Nikolaevich Kolmogorov,
     _Grundbegriffe der Wahrscheinlichkeitsrechnung_ (1933)
     aka _Foundations of the Theory of Probability_
     http://www.kolmogorov.com/Foundations.html

\2\ For a relatively gentle, undergraduate-level introduction, see:
     Tom M. Apostol,
     _Calculus_
     2 volumes, Wiley (2nd. ed. 1962)

\3\  John von Neumann,
     “Various Techniques Used in Connection With Random Digits”
     page 36 in _Monte Carlo Method_
     proceedings of a symposium June 29 – July, 1, 1949
     A.S. Householder, G.E. Forsythe, and H.H. Germond (eds.)
     Institute for Numerical Analysis (published 1951)