[perpass] Traitor Keys and certified hardware

[Phillip Hallam-Baker <[e-mail]>]

I have been thinking through the possible origins of the NIST/NSA elliptic
curve random number generator with a backdoor. My first reaction was 'what
were they thinking'. Followed by essentially the same conclusion as
everyone else.

But coming back to the problem I realized this morning that we might be
missing something in Dual_EC_DRBG. There is actually an advantage to the
scheme, provided that you generate your own curve and keep it safe.

Let us suppose for the sake of argument that Dual_EC_DRBG was originally
designed for the sole purpose of protecting US government secrets better
and that there either was never an intention to exploit the backdoor or
that was a change that occurred subsequently. What advantage would that
give?

If the generator is seeded from a simple static seed, the main effect of
having a backdoor in the randomness prep is that it makes the process
deterministic. An external auditor can use the backdoor to recover the seed
and then run the device for an extended period to see if the behavior of
the device is fully consistent with that seed choice.

If there is a side channel in the purported DRNG, the party who knows the
backdoor can check it very quickly.

If the generator seeding is dynamic, acquiring >X bits of new seed before
outputting X new bits of output, the backdoor doesn't help. But that would
mean it wasn't a DRNG.


Using such a scheme if the potential attacker knows the backdoor key is
obviously bad. But within the narrow requirements of the NIST
specification, the scheme does have clear advantages for the government. It
means that they can buy commodity hardware and quickly check to see if it
has been compromised during manufacture.

So the real lesson here might be that people should use Dual_EC_DRBG but
with hardware that allows end users to choose their own curves. Which is
incidentally what NIST actually advised.


So now lets turn to the idea of some sort of open source crypto hardware
platform, how might we apply this scheme?

Lets imagine for the sake of argument that we are using Raspberry Pi
computers which are a commodity computer that is (1) cheap, (2) boots from
an SD card (no BIOS), (3) supports a mouse, keyboard and HDMI display.
Cheap matters here because several of these machines are going to be
burners (literally).

The device does not have tempest shielding etc. But I am assuming here that
we are taking other precautions to prevent that sort of attack. It is easy
enough to build a Faraday cage you can sit in.


We start the process with a collection of commodity SD cards bought from a
randomly chosen retail vendor and an ISO image of our favored stripped down
O/S. We have two separate applications that we would run.

1) The key manager to audit.
2) The curve generation and audit code.

We install the programs on separate ISO images on separate machines. Then
we write the images out, fingerprint them and publish the full sources, etc.

We then boot the curve generation machine and generate a curve, we give the
curve to the key manager machine, run it through the full suite of tests
and check that the outputs exactly match what they are supposed to using
the backdoor to the curves. the key manager device is going to dump out a
statement giving the curves used each time as part of its output. For
example, pass the hash of the curve spec in the upper bits of the RSA
modulus using Moti Young's technique.

The whole process is precisely deterministic and therefore auditable. The
program does not know if it is being run as a test or for real. So a device
that defects only one in ten or one in a thousand times can be caught.

This is the reason I don't want to switch from ASN.1 for certs despite it
being such a pain, the distinguished encoding is good for exactly one thing
and that is eliminating side channels.


Before we can use the device we have to establish a trustworthy set of
curves. Fortunately this is something that only needs to be done once,
though if people doubt the trustworthiness of the curves used they could
follow the script and repeat the process.

To do this properly we need a ceremony.

One of the functions of a ceremony is to ensure that things are done
repeatably. Bronowski's Ascent of Man has an example of a Samurai sword
being made which is a formal ceremony.

The two requirements would be to ensure that the seeds used for generating
the curve are completely random and that all physical hardware that has
touched them is destroyed after use.

The Raspberry Pi is low power enough to run on batteries. A steel box for a
Faraday Cage is simple enough for blocking E-M radiation. Can add in a
noise generator

Turns out that thermite is not quite hot enough to melt silicon. But
Oxy-Acetelyne is.

The trickiest problem with disposal is likely going to be disposing of the
battery safely.

-- 
Website: http://hallambaker.com/