Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: [Phys-L] real-world physics : electronic privacy requires physics, not just algorithms



I am not sure how to react to this longish email. Everything John says is true, yet very little of it seems relevant to the issue of cryptography.

1. Yes. All computer-based "random generators" are really pseudo-random generators. That's what makes them useful.

2. Yes. Some pseudo-random generators are better than others in certain "random" characteristics, and it is clear that the NSA tried to make sure none is "too good." It did it starting with DES forty years back, and even then everyone who cared to know knew it.

3. One can reasonably easily get true randomness from physical processes but it has little value for cryptography, except as a "seed" for a pseudo-random generator. One can generate true random strings to do -- in effect -- a one-time-pad, but key distribution becomes as complex as sending the message itself. So, with a very few exceptions, it is useless for crypto.

All this is well known and well understood by people dealing with crypto.

So what exactly was the purpose of the message? What exactly it has to do with physics?

Ze'ev

On 9/29/2013 6:22 PM, John Denker wrote:
Hi Folks --

Here is a story about physics in the real world, ripped from the
headlines. It helps explain to non-physicists why they ought
to know some physics. Conversely, it helps explain to physics
majors why knowing just physics is not nearly enough. Interesting
applications are almost always interdisciplinary.

Executive summary: Modern cryptography requires randomness
but the world of algorithms cannot generate it. The randomness
has to come from another world, the world of physics.

================
In more detail:

We start from the premise that security is a concern for anybody
who might ever communicate with a doctor, lawyer, banker, political
leader, activist, journalist, et cetera.
In contrast: Senator Lindsey Graham has argued that if you
have never done anything wrong, you have no reason to be
keeping secrets ... but I say that is just ridiculous.
Businesses have trade secrets. Political campaigns have strategies.
Doctors keep lots and lots of private records. Merchants depend
on e-commerce. People need to be able to store and communicate
things electronically without letting outsiders spy on them or
tamper with them.

It has recently been revealed that the NSA has buggered the
protocols that are used for securing electronic storage and
communications. Details are lacking, but there are strong
indications that they messed with the randomness generators
(among other things). In the wake of these revelations, NIST
officially retracted some cryptography standards, and a major
vendor (RSA) has advised customers not to use certain of its
products.

Modern crypto is heavily dependent on having a good randomness
generator. For decades, since the dawn of the computer age,
mathematicians and algorithm designers have tried /and failed/
to come up with a good randomess generator. Back in 1951 John
von Neumann said:
"Anyone who considers arithmetical methods of producing
random digits is, of course, in a state of sin."

That remains true ... but people keep trying to do it!

One of the things the NSA apparently messed with is called
EC_DRBG -- elliptic curve deterministic random bit generator.
How anybody can use "deterministic" and "random" together in
this way is something I will never understand, but that's
standard practice.

People have built /hardware/ random number generators. The
idea is to rely on the fluctuations in real-world physical
processes. The problem has to do with figuring out how
much randomness there is in such a source. If you look at
(say) a lava lamp, some of the motion is predictable and
some of it is not.

People have come up with all sorts of statistical tests to
try to measure the amount of randomness, but these all have
a fatal flaw: Statistics provides only an /upper bound/ on
the amount of randomness; it can never provide a lower bound,
which is what we need.

That's where physics comes in. The laws of physics guarantee
that any electrical resistor will always produce a certain
amount of thermal noise, i.e. Johnson noise. This is a
guaranteed lower bound on the amount of noise. You measure
the temperature and the resistance and the bandwidth, and
then you can calculate a reliable lower bound.

Please do not tell me about radioactivity. Guess what?
I've already thought of that. As a source of randomness,
it is in no way better and in many ways worse than Johnson
noise.

To repeat: You can measure the statistics if you want, but
that will never solve the problem. You are much better off
measuring the physics, i.e. the temperature, resistance, and
bandwidth.

To begin solving a problem like this requires an interdisciplinary
approach:
a) You need to have a clue about cryptography, so you can
realize what the problem is; and
b) You need to have a clue about physics, so you can
realize what the solution is.

That creates an opening. This phase of the job /cannot/ be
done by a team; it requires one person who can see the problem
and see the beginnings of a solution.

To /finish/ solving a problem like this is even harder. It
requires physics (including thermodynamics plus the classical
theory of fields), cryptologic algorithms, analog electronics,
digital signal processing (including z-transforms), real-time
programming, et cetera. It requires a tremendous amount of
attention to detail.

This second phase can make use of teamwork. You don't need
to have one person who has all those skills. You just need
somebody who can pull together a team with all those skills.
Or you need somebody who can learn all those skills when
needed.

Cryptographers tend to be very smart. They have to be very
mathematical and also very applied. However, your average
cryptographer would never be able to come up with a good
physics-based randomess generator ... and even has trouble
understanding it when you explain it. You start talking
about the field in the resistor, and enumerating the modes
of the field, and each mode has fluctuations, namely a half
kT per degree of freedom ... and they don't understand a
single word you just said.

The world would be a better place if everybody knew a
reasonable amount of physics.

============================

Tangential remark: Please never talk about "random numbers"
... not in front of students or anywhere else. There is no
such thing as a random number.
*) If it's a number, it's not random.
*) If it's random, it's not a number.
--> You can have a random distribution over numbers, but then
the randomness is in the distribution, not in any particular
number drawn from the distribution.
http://www.av8n.com/physics/probability-intro.htm
_______________________________________________
Forum for Physics Educators
Phys-l@phys-l.org
http://www.phys-l.org/mailman/listinfo/phys-l