Re: [Cfrg] Hardware requirements for elliptic curves

Alyssa Rowan <akr@akr.io> Sun, 14 September 2014 18:36 UTC

Return-Path: <akr@akr.io>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DAB521A0174 for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 11:36:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.798
X-Spam-Level:
X-Spam-Status: No, score=0.798 tagged_above=-999 required=5 tests=[BAYES_50=0.8, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8Barfo_gtT81 for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 11:36:04 -0700 (PDT)
Received: from entima.net (entima.net [78.129.143.175]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F05281A0173 for <cfrg@irtf.org>; Sun, 14 Sep 2014 11:36:03 -0700 (PDT)
Message-ID: <5415E017.5070906@akr.io>
Date: Sun, 14 Sep 2014 19:36:07 +0100
From: Alyssa Rowan <akr@akr.io>
MIME-Version: 1.0
To: cfrg@irtf.org
References: <54116278.3080901@gmx.net>
In-Reply-To: <54116278.3080901@gmx.net>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/9Ec4R3ANijZ8nkFJjRz0vTlhlXQ
Subject: Re: [Cfrg] Hardware requirements for elliptic curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 14 Sep 2014 18:36:07 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 11/09/2014 09:51, Torsten Schuetze wrote:

>> Respectfully, I do not think that conservative approach delivers
>>  sufficient assurance where the integrity of the base is properly
>> in question: you don't add a conservatory to fix uncertain 
>> foundations.
> Respectfully, could you please elaborate on what is an uncertain 
> foundation with a general modular multiplier that computes Z=M*C
> mod N for general modulus structure of N and arbitrary multiplier M
> and multiplicand C?

I haven't evaluated, and am unfamiliar with, your particular hardware.

A generic modular multiplier that may exhibit poorer side-channel
resistance when asked to operate over sparse prime moduli may well have
room for improvement, if it is to be suitable for use with such moduli.

But you could always do it in firmware with the same ladders regular
software would use, and hopefully get good characteristics there?

What I meant, however, was the far more general question - although I'm
not sure to what extent the foundations of what essentially is a secure
computing platform falls under (or outside) the auspices of this
group, as such.

> What do you mean with "an uncertain pedigree which has not also
> been designed, audited, and certified as openly as possible from
> its inception"?

Precisely what I say.

> Smart cards, i.e., its coprocessors and its ECC software 
> implementations, are always certified by Common Criteria, usually 
> with rather high assurance level. Don't you trust this
> certification in principle?

I think a high-assurance platform, post-Snowden, now ought to consider
the troubling implications of the BULLRUN (and EDGE HILL, etc)
compartments; more precisely the "SIGINT Enabling" (backdoors) which
encompass (some of) their sources.

Your customers surely also have very deep concerns about that,
especially given recent events? (They ought to, at least.)

The threat model has been shown to be much wider than previously known,
and to sometimes encompass deep and subtle subversion of the design and
evaluation processes. A truly high-assurance platform now finds itself
in the position of clearly demonstrating to all that any assurance
provided has never been thus subverted: a challenging assertion for the
EALs, and one in my opinion they were not really designed to meet.

In absence of that, neither vendors nor certifiers should be considered
unconditionally trustworthy for a high-assurance platform. I suggest a
dramatically open, independently-auditable process: but that's the
opposite of the way many have done it so far, and there are very many
potential challenges facing any such approach - some of which you talk
about.

> Shall everything be open-source?

At the very least it ought to be openly source-available for review.
Yes, open-source would be a very good idea.

> Do you trust your compiler when compiling your specialized 
> highly-optimized elliptic curve arithmetic?

Not really, no. I don't even particularly trust normal compilers to
zeroise memory reliably, in the absence of specific fixes for that.

> Or do you perform a formal verification before hand?

That would definitely be one helpful component of the process, amongst
several, but not a panacea by itself.

> Do you trust your Intel processor?

Which one? The hypothetical Haswell on my desktop? The hypothetical
80C51 in the smartcard on my bench? Any of the chips in the chipset?

Questions have indeed even arisen about the feasibility of microcode
trojans: I have seen one demonstrated in controlled conditions. It's
vaguely feasible with a big enough budget or tight enough targeting -
and some nation state adversaries have _very_ big budgets.

And even if you evaluate hardware right down to the mask level, there
have been demonstrations of subverting RNGs without altering the mask,
but merely the doping of a few transistors.
[Stealthy Dopant-Level Hardware Trojans, CHES2013:
<http://sharps.org/wp-content/uploads/BECKER-CHES.pdf>]

Assuring your supply chain against all of that, as well as people
potentially opening your mail to clients and trojaning it en-route,
does, I admit, seem daunting: but that is the extent of the challenge if
you really want to go "high-assurance" now. We'll see if anyone can rise
to it?

>> I'm not aware of any cryptoprocessor vendor who has shipped any
>> new hardware like that, but I would heartily welcome and
>> encourage it.
> As I have said, they do this regularly, i.e., ship "new" hardware 
> that has been evaluated and certified by defined processes.

As above, I don't think those existing processes are sufficient to
contain the revised threat model, given the disclosures of the past year.

> By the way, in a mail from Sep 02 you wrote "I think it would be a
>  mistake to allow old hardware implementations to (yet again) 
> needlessly overshadow improved software ones"
> 
> Only the multiplier is in hardware, everything else is in 
> software/firmware. What is old hardware for you?

I could not speak about your hardware, as I haven't reviewed it.

I would - purely by way of hypothetical example, of course - hesitate in
calling a platform based on the 8051 "new", by any measure.

> Do you know the product and development cycles/costs for
> ASICs/smart cards?

Vendors seem to consider that commercially-sensitive information, for
some reason. <g> It varies - wildly. Not particularly cheap, certainly.

Bitcoin mining seems to have reduced the cost out of China for some.
That brings us inexorably back, of course, to supply chains.

> We do not want and we will not design a new public-key coprocessor,
> a new RNG, a new symmetric coprocessor, a new memory encryption
> unit, etc. every new year.

It's not the age that bothers me: one good one would be fine.

But given the changed threat model, incremental changes and incremental
evaluations on existing implementations do not provide a level of
assurance that I'd feel comfortable calling "high".

I maintain those who requested and are likely to use any new
recommendation from us, are unlikely to be too satisfied by the
assurances provided by existing crypto hardware without a fresh start
being made - so whether pre-existing hardware can adapt to the new
recommendations trivially is, perhaps, not as relevant as you fear.

Your customers may have other ideas - but if they like Brainpool-style
curves (and they seem to?), as others have said, there's nothing to
stop anyone using whatever they'd like.

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJUFeAXAAoJEOyEjtkWi2t6kZQQAJbdpBAjZyl3cZdisF/2sPzQ
/MQJRypGalXcTpZrHMg98JWxaWbek18uYI5UV1orwCa7SkqlXsSl5Z2ZDctwT/xw
wepRjM/S1l2skXAH4hYj7WZQr4nNM6SSa/fAVmAEiZtc+NuA9okB/0xzwTQhlvw2
If04JJzIFj5djmDdxLzkgLRQrBQV35CsyJP0WuOA8G/Fq1MplkwwH1wrCPubA+0Z
7kA097VvYtY/x2AQpPIi1YvELnM4P+rVaqzomPWD82OQ5k8vD2o77CovG5BfGo2M
au4kx7xpGxzG6wLs2dHVrbQYGtj18NIHidRVTsZZfYlb5K1oZqEu6hEfaj9qYKEG
p8N3TNAO+yy49+8m5Pc6heNyJvGbVHNHQOpgLEsvM3WDbdyZxSw3kNAtXdPy3hi/
J3Q9+cJZc00XzgBeBGP3nCLL5oMp97Lwv/qkLphGTtKtoGlHjJCzCIKHK1W1AAAz
YJGmus4KA4oeI7VF5rvFHwrmXVLHN9JV/XF4Jc2AKZ4QeMKmxu+Qd+mountOB1XF
Qmi+GPE7iiQ/8q86RIjSsu8ywDF0TVU6UzPGMf+2huMMQ9yoMlVjPlUJ/N+8De76
6mIIklAg451JpJGhGtG6sr61RnH7yq4XVEicn0Iwz77KfwfTAJqUPtGTGKUH9DPi
Tae8c9tYGfoUx8BXbUWZ
=35r3
-----END PGP SIGNATURE-----