Re: [perpass] Traitor Keys and certified hardware

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

On Mon, Nov 18, 2013 at 12:53 PM, Phillip Hallam-Baker <[e-mail]>wrote:

> 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.
>
>
It just occurred to me that a party can obtain even greater security by
using multiple random generators with different initial seeds.

We could even generate new curves annually.

We can still use the RSA modulus side channel to specify which curves were
used, it just becomes a list of hashes or the hash of a list. The important
thing is that if we ever were to suspect a set of curves had been jiggered
we can identify the RSA keys that it was used to generate and revoke the
certs.

It would be a good idea to put the hash of the ISO build in the modulus as
well.

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