Subject: [Cfrg] Hardware requirements for elliptic curves

From: Joppe Bos <[email-masked]>
Date: Tue, 2 Sep 2014 11:43:19 +0000

The current discussion around the requirements, and the performance aspects,
have mainly been approached from a software implementation point of view. As
one of the authors of the NUMS curves, I have been responsible for this as
well. With this message I would like to provide a hardware perspective: more
specifically, I would like to put forward some requirements which are
concerned with hardware specific attacks. 

The current discussion is focused around deciding upon a set of requirements
in order to select new elliptic curves for usage in the TLS protocol.
However, this choice of curves can potentially have a significant impact on
the choice of the new "standard" elliptic curves used in a broader setting.
This is why a different (i.e. hardware) point of view might be a relevant
addition in the current discussion.

In the hardware setting, when implementing curve based cryptography, one
often has access to a generic modular multiplication (hardware)
implementation on a secure crypto co-processor. In this scenario, the
performance of a multiplication modulo a random prime is identical to the
performance of multiplication modulo a prime of a special shape. Not only
does the usage of specially shaped moduli not increase performance, it makes
it a lot harder to use a set of common counter-measures against certain
types of side-channel attacks (a requirement for meeting certain standards
such as Common Criteria and EMVCo). For example, scalar blinding is a
technique in which one adds a random multiple of the group order to the
scalar. If the prime p (in the definition of the finite field F_p) has a
special shape, then this shape carries (largely) over to the order of the
elliptic curve (by the Hasse-Weil bound). It is known that one can take
advantage of this special shape and attack schemes that apply scalar
blinding (e.g. see  <https://eprint.iacr.org/2014/191.pdf>
https://eprint.iacr.org/2014/191.pdf and the references therein). Therefore,
(also) specifying curves defined over random prime fields (more precisely,
an elliptic curve defined over the finite field F_p where p is a random
prime) would be a preferable additional design requirement from a hardware
point of view.

We will need to support prime order Weierstrass curves in the future since
we will need to keep supporting the NIST curves. Adding dedicated support
for curve arithmetic in different curve models (Edwards / Montgomery) would
increase the code size which in turn increases maintenance effort.
Furthermore, since Edwards / Montgomery curves cannot have prime order, this
requires changes to the current implementations in order to avoid
small-subgroup attacks. 
It is unclear (and an interesting question) if implementing the more
efficient group law on these different curve models is worth the increase in
code size, since the potential speedup is expected to be between a factor
one and two. Supporting Edwards / Montgomery curves in their corresponding
Weierstrass form has no advantage from a performance point of view and adds
complexity due to the composite group order. 

In conclusion, we think the current ongoing discussion about the
requirements needed for selecting new elliptic curves is very important.
Selecting new curves in a transparent fashion, which are more secure
compared to the current set of standardized curves by NIST, is the right
thing to do. From a hardware perspective, defining elliptic curves over
primes of a special shape has no positive performance effect and even rules
out using some common countermeasures to guard against types of side-channel
attacks. We have a strong preference for prime-order Weierstrass curves
defined over random primes. If this is not an option and if different curve
models are proposed then also providing such a curve defined over a random
prime field would be preferable. In this latter setting, it is not clear if
we would adapt the implementations to the curve model or transform to
Weierstrass form.

I hope this additional point of view is useful and will lead to further
discussion. 

Joppe Bos

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 02 Sep 2014 14:05:43 +0100

>concerned with hardware specific attacks.

Thank you; an interesting perspective, if I may say so.

Of course, there's more than one way to do it. Vendors seem to use a variety of techniques for side-channel countermeasures, and other techniques prefer different environments.

For example, balanced dual-rail logic and smaller constant-time/power implementations (along with an awful lot of dead junk gates, for reasons I can't quite fathom but that may be a poor attempt at DFA countermeasures?).

Or several other implementations from multiple vendors that are actually based on either specialised microcontrollers or commodity CPUs with specialised firmware, resulting in what may be more accurately characterised as a constrained/specialised software implementation: I think this may be the overall general approach that is the most flexible, modular and reusable, which may be why it's the most favoured approach by most other smart card & HSM vendors, from what I've seen?

Random primes have unfortunate software performance, including constrained performance.

We are not concerned with EMV "security" here in CFRG at all, but with making suggestions for *internet* protocols.

I think it would be a mistake to allow old hardware implementations to (yet again) needlessly overshadow improved software ones: the majority of implementations on the internet will invariably be software. I feel we are being asked for new recommendations here, not old ones, but of course, that's only my perspective.

- --
/akr

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 2 Sep 2014 09:31:56 -0700

I agree with Alyssa that hardware performance isn’t our concern here.

However, I’m curious about Joppe Bos’ assertion that random primes are just as fast and more secure in hardware.  What kind of hardware are you thinking about?  Some kind of residue number system?  Or a bit-at-a-time reduction system?

I have some limited experience in crypto hardware design, in particular working with a hardware modulo multiplier.  If I recall correctly, adding support for a handful of the NIST primes (192, 224, 256 and 384 maybe?) cost about 10% area overhead in our lightweight design, for double the performance.

That said, this hardware used a Montgomery reduction, so the same support would have required more work for a 2^big-small prime.  But I’m sure it can still be done.

— Mike

> On Sep 2, 2014, at 6:05 AM, Alyssa Rowan <[email-masked]> wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> -----BEGIN PGP SIGNATURE-----
> Version: APG v1.1.1
> 
> iQI3BAEBCgAhBQJUBcCnGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE
> jtkWi2t6o9sQAJpzXq7NOEzN8GMtwLI5tleXrlrNKDaJnAjVnV3Um8jMjXQR7EKS
> pVUKMykomMhRvTAqfAQGWPBNIij9kRV5nT+3k+LYy6R1uuhS7Bdk3qV7DEEhmi06
> shBK0uW2nic7PiXfwNpBBfrDPdLC2V035dLYD/uRtGPxWg69O4har82sjsIa7Bpm
> ACnZwGxkgn1Mqem6IitSu6zs3XbnBTRVHvD3ttoi7gG5vD9MrQOCsHcWsqvkYIuD
> 6E8N1ioL+5Yv4KhpVmv7NseP4Vl/anXYm5PEXyqVkcZlXtoaDXfJMbZAlolSCiPq
> oaS4yGsGJV+g1HRMUr080jtlNuJKz3QiQqka91stvz83/fMIYhB3Y9Gy7z/0ojMF
> GbKgkt9u31G4srPioFkDZjYPng7RQpwQz0Js3hWje3IVGiG0igEx1MlDrlCuIvlf
> t2DBoxm61FCv+uRbZjXcZI7t/2orAB+5U75jx7yy9rO4WDcZx+QPEa1r3utQ1gBm
> p48lc2NlDsxF7lQUPvpsmtnboYa7yISMefV+rLHX1hf+mgDMd1f9Wm/Dv3t8p53l
> L0rFx0hPv9Lk4Kx/U21QZBa3rNldGyR9V+asBQz65G2C027rWv2K1mrzFMQwphfq
> xJubu9iKqT/JTzk0brRQCd9tY3ljLSW8Y0v9y4enCb5Z015tFno2oIlm
> =Fk5G
> -----END PGP SIGNATURE-----
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 4 Sep 2014 14:55:20 +0200

> I agree with Alyssa that hardware performance isn’t our concern here.

I disagree with this oversimplification. Currently, the fraction of TLS implementations based on HW is relatively
small but not negligible. And in the future it will increase:

1. Heartbleed has shown that it is dangerous to keep private keys in software. Hopefully, this lesson has been learned.

2. There are security critical infrastructures emerging, where TLS will be used with hardware crypto
implementations. Examples are car2car and car2X, health care infrastructures, smart meter,
e-government communications services.

3. In the foreseeable future, we will see a huge number of constrained devices in the IoT potentially deploying TLS
(e.g. for home automation, sensor networks).

Furthermore, other IETF protocols are well within the scope of our effort. (As Kenny wrote in his announcement of the
current effort "We regard this as a major work item for CFRG and one where CFRG can provide real value to the TLS WG
and the IETF more widely.") For IPSec, there is indeed a significant number of implementations based on smart cards or
small HW crypto modules (for instance from my employer).

-- 
Johannes

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 4 Sep 2014 08:21:50 -0700

> On Sep 4, 2014, at 5:55 AM, Johannes Merkle <[email-masked]> wrote:
> 

You know what?  I spoke too soon on this, and you changed my mind.  Hardware does matter, even though it isn’t the main focus of this research group.

But I still don’t understand why hardware favors short Weierstrass curves or random primes.  Short Weierstrass really doesn’t seem simpler than Edwards to me.  It’s slower, less regular, and doesn’t parallelize as well (if you have high perf hardware).  It wants a halve() operation for best performance in addition to add/sub/mul, and you can’t just use one unified formula for everything if you’re complexity constrained.  The cofactor is potentially an issue, but you can just wipe out the cofactor first and then check against the identity.

And random primes aren’t better either: they’re still much slower than special primes in hardware, and it’s more complex to invert mod them (more complex Fermat’s Little Theorem, or have to implement EGCD), and you can’t switch between Barrett and Montgomery reduction as easily.  From Joppe Bos' email, it sounds like primes make one blinding technique more effective.  But if you suddenly have double the performance budget (from a faster prime) can you not do even better?

The hardware I’ve seen uses Montgomery reduction.  If everyone else does this too, it might be a minor strike against 2^big - small primes.  Other hardware folks: how do you do your reductions?  And how much of a pain would it be to switch to 2^big - small?  Am I missing something about short Weierstrass, cofactor problems or special primes?

Cheers,
— Mike

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 04 Sep 2014 18:44:16 +0100

On 04/09/2014 13:55, Johannes Merkle wrote:

> I disagree with this oversimplification.

Mm, I do think that's an oversimplification. Let me clarify.

I don't think hardware performance should be _completely_ disregarded
- - merely that it shouldn't be a _primary_ consideration for us (as it
clearly is, for - for example - NIST & NSA, due to their own needs).

• The vast majority of users overall use software crypto
  implementations. That will probably continue, although the exact
  proportion may change. (Heartbleed may indeed encourage increased HSM
  adoption.)

• Many 'hardware crypto' implementations (HSMs/smartcards/etc) I've
  seen myself more closely resemble, or literally are, microcontrollers/
  microprocessors running highly specialist firmware. This approach has
  several advantages: much greater algorithmic agility versus "glacial"
  hardware cycles via firmware updates; the ability for more
  comprehensive side-channel protection; the potential for
  'correctness' proofs of the software, etc.

• Use of actual fixed-function hardware crypto's relatively rare.
  There's lots of (no offence intended) earlier generations of hardware
  with a few conservative iterative changes. (e.g. Hardware RSA/3DES
  /SHA-1/AES, but firmware secp224r1 & secp256r1, to give one concrete
  example: the firmware's actually faster, and I would say has a lower
  side-channel profile.)

• I think any such device implementing anything we choose is most
  likely to be either a brand-new fixed-function implementation (such
  as the X25519 one contributed to cryptech.is?) - in which case it
  isn't glued to a side-channel defence which performs well only with
  random primes (...not even Solinas primes? Hmm...), but can use _new_
  ones which work with whatever we do choose - or it's going to do it
  in the firmware because fixed-function hardware often tends to be,
  fairly, well... _fixed_.

I don't think we should consider ourselves needlessly hobbled by
inflexible, legacy hardware implementations: they are not really our
new recommendations' primary target audience, as much as software is -
and if hardware is, it's likely to be _new_ generations of hardware,
not the old stuff.

So let's pick something which performs well in both software _and_
hardware - and that weighs against random primes, in my estimation.

- -- 
/akr

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 4 Sep 2014 10:57:22 -0700

>   'correctness' proofs of the software, etc.

To add to this point, I expect that we'll see a lot more adoption of
hardware-protected software crypto in the relatively near future.
This could involve tricks like using TrustZone on phones (not
open-source friendly, essentially unauditable, and inflexible) or
virtual tokens using Intel SGX (IMO a vastly superior solution).

For this type of hardware-protected security, the performance
considerations will be almost exactly the same as for software crypto.

--Andy

---

From: Robert Ransom <[email-masked]>
Date: Thu, 4 Sep 2014 20:18:48 -0700

On 9/2/14, Joppe Bos <[email-masked]> wrote:

> thing to do.

I don't see why you are presupposing that new curves must be selected
-- surely the IETF should not rule out the use of previously chosen
curves such as Curve25519 and the ‘Brainpool’ curves merely because
they have multiple independent, interoperable implementations.  In
particular, the rest of your message argues for a set of curves which
(a) are defined over random-prime-order coordinate fields, and (b)
have prime order, and the Brainpool curves satisfy both of those
criteria *and* are already implemented.

(I'll leave the question of whether those properties are as desirable
in hardware implementations as you claim they are to people who have
studied those, but having prime order is the most important security
risk of the NSA curves in software implementations, so I don't see why
you are criticizing those curves' security in the same message in
which you propose retaining that security risk in newly chosen
curves.)

Perhaps you don't consider the Brainpool curves to have been chosen
‘in a transparent fashion’?  If that is your concern, I'm sure that
someone from the Brainpool consortium would be interested in
commenting on exactly how transparent their process was.

Additionally, you're raising the issue that new curves should be
chosen ‘in a transparent fashion’.  Since you are one of the authors
of <https://eprint.iacr.org/2014/130>, which ‘select[s] new curves’,
would you, and the rest of Microsoft Research, be willing to publish
all of your internal communications and records (e-mails, memoranda,
meeting notes, phone conversations, etc.) regarding that paper and
your efforts to promote adoption of the curves, algorithms, and
software described in that paper?  That would allow people who share
your concern about the transparency of the selection process to
seriously consider the curves specified in your paper.

(I don't consider transparency of the selection process to be nearly
as important as other criteria such as cross-platform performance,
efficiency of constrained implementations, support for simple
algorithms, support for efficient, simple constant-time
sum-of-scalar-multiple algorithms, and the availability of multiple
independent, interoperable implementations, all of which argue against
the curves specified in that paper.  But you, and other members of
Microsoft Research, have raised ‘transparency’ as a concern, and other
people may indeed consider transparency to be important.)

Robert Ransom

---

From: "Lochter, Manfred" <[email-masked]>
Date: Fri, 5 Sep 2014 12:58:11 +0200

> criteria *and* are already implemented.

I agree that there are sets of established curve parameters and that the use 
of these curves in IETF protocols should not be prohibited by the selection 
of new curves by the IETF. 

There are people who propose that for each security level (i.e. 128 bit, 192 
bit, 256 bit) one curve should be chosen and be used by everyone. To me this 
seems to be a dangerous approach. I admit that today most cryptographers 
believe that hypothetical future attacks on elliptic curves will be generic.  
But no one can rule out the possibility of new efficient attacks on special 
classes of elliptic curves. (Think of the Satoh-Araki-Smart attack on 
anomalous curves.)

Therefore I believe that protocols should offer a wide flexibility in choosing 
(and changing) elliptic curves.

> which you propose retaining that security risk in newly chosen

See also RFC 6989! Indeed, using curve types that require a (small) cofactor 
introduces an additional risk.
> commenting on exactly how transparent their process was.

As I was the editor of the Brainpool paper I would like to take the 
opportunity to elaborate on the Brainpool process: The open Brainpool group 
consists of members from academia, industry and government. Its major goal is 
to promote the usage of ECC as well as to enhance the security of 
ECC-implementations. 
Around 2004 we identified industry demand for additional  standardized curve 
parameters. We spent several meetings to solicit and select criteria that 
these curves should fulfill. These criteria were selected taking into account
	mathematical security
	security against side-channel attacks
	avoidance of implementation errors. 
Scientists participating include Gerhard Frey, Johannes Buchmann, Tanja Lange 
and Elisabeth Oswald, to name some. 
We also believed that the curve generation should be verifiable. Thus we came 
up with a construction process based on the X.9.62 standard. We based this 
fully rigid process on the two natural constants e and pi.
Details can be found in 
http://www.ecc-brainpool.org/download/Domain-parameters.pdf
At the ECC 2005 conference we invited the international ECC-community to 
comment on this paper, but received no comments. Since 2005 the Brainpool 
curves became widely used.
As a next step we successfully initiated standardization of the Brainpool 
curves for IETF use (RFC 5639, 6954, 7027). 
 
> people may indeed consider transparency to be important.)

Personally I believe that it is impossible to have a process that is accepted 
as transparent and rigid by everyone and at every point in time. To give an 
example: Only recently we have been implicitely  criticized for not using 
Keccak in the Brainpool curve generation process. But Keccak  was not even 
available in 2005. From my perspective this observation underlines the 
necessity of standards  allowing for a flexible use of curves. 
> Robert Ransom

Manfred

Lochter, Manfred
--------------------------------------------
Bundesamt für Sicherheit in der Informationstechnik (BSI)
Referat K21
Godesberger Allee 185 -189
53175 Bonn

Postfach 20 03 63
53133 Bonn

Telefon: +49 (0)228 99 9582 5643
Telefax: +49 (0)228 99 10 9582 5643
E-Mail: [email-masked]
Internet:
www.bsi.bund.de
www.bsi-fuer-buerger.de

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 5 Sep 2014 13:34:36 +0200

> But I still don’t understand why hardware favors short Weierstrass curves or random primes.  Short Weierstrass really doesn’t seem simpler than Edwards to me.  It’s slower, less regular, and doesn’…

I am not at all a hardware expert. But we just had a meeting of the ECC Brainpool, where several hardware vendors are
represented. What I understood is that they do not want to specialize their hardware to minimize their investment while
being fully flexible (algorithm agile). Remember that multipliers are also needed for RSA where the numbers do not have
a special shape. Furthermore, I guess that new implementations can be built easier based on existing ones.

> And random primes aren’t better either: they’re still much slower than special primes in hardware, and it’s more complex to invert mod them (more complex Fermat’s Little Theorem, or have to impleme…
The point is that flexible (non-specialized) hardware multipliers do not take advantage of specialized primes.
Specialized multipliers are certainly possible but are less agile w.r.t algorithms / curves. Flexibility is particularly
important due to the long development / certification cycles and the tremendous costs involved.

-- 
Johannes

---

From: <[email-masked]>
Date: Sat, 6 Sep 2014 12:18:47 +0000

First of  all, I would like to thank Joppe for bringing up the topic of hardware requirements. I fully agree with his
opinion. If we assume that the current discussion should not only be concerned with requirements
for elliptic curves for usage in the TLS protocol but also for general usage, new questions arise:
On what kind of plattforms will the elliptic curves be implemented?
Are they running in a, what one could call, secure environment? If not,
how about side channel attacks (SCA)?
Of course, one could say: People know SCA for more than a decade. They will be able to secure implementations of new curves as well. ---
This might be true, but one has to look at the details to see the problems:
Specially shaped curves (and implementations) may completely loose their (performance)
advantage if they have to be secured against SCA. Joppe already mentioned the problems  concerning randomizing the (secret) scalar for a scalar multiplication.
One could say: Ok, then you have one randomization method less, but people will find other.
Well, this could be true. But personally, I believe this will be not so easy.
If one asks a guy from evaluation labs, they will probably  tell you that handling a constant secret value again and again in an unrandomized manner, this is a very dangerous thing to do. --- At least, if SCAs are applicable.
This often holds, even if other randomization techniques are used, e.g., if you have
implemented constant timing formulae, or maybe even if you have a carefully designed
hardware (dual rail etc.), or everything together. (By the way, I would like to add that
constant timing may make other attacks easier...)
If one accepts the consequence that a scalar has to be randomized, then Joppe already
mentioned that special shape primes (as the characteristic) may immediately force you to
use a randomization that prolongs your scalar by say 50% - and the performance goes down
by the same factor. This holds in the case where the scalar k is randomized in the form
k' := k + rand * n. If the prime p (and therefore the order n) is rather random,
a random value rand of moderate length (eg. 32 bits) may be sufficient.
Of course, one can use the primitive randomization k = k1 + k2, with a random split,
then one needs even two scalar multiplications, and the computation time goes up by 100%.
I only can think of one other generic randomization technique, but there are patent
issues --- besides some additional minor technical issues.
If one hopes other randomization techniques are sufficient, let's think about what else one can actually do:
All computations break down to operations like (a * b mod p). Here, one could compute
instead something like
( (a + rand1*p) * (b + rand2*p) mod (rand3*p) ) mod p.
But in this case, you loose your special shape of your module. - If it has one.
Specially  taylored hardware or software will pobably not work with (rand*p) instead of p.
For a special purpose hardware realizing a modular multiplication with general p
this is not an additional hardship.
So maybe one has to look for other SCA countermeasures, maybe on a higher level.
I hope people will finde some. (And then, I am concerned, they probably will file the ideas
for a patent and the technique will be blocked for the next 20 years. So we have again a
situation which we already slowly overcome regarding the many old patents.)
This all holds for implementations in software as well as in hardware!
I don't want to say that this scenario holds for all security applications.
Maybe in products with moderate security requirements the situation is not as bad as
described... Maybe...
One word on hardware implementations (away from the SCA topic):
Usually one can choose one of two directions to design a co-processor for pkc applications.
For a very application-specific hardware with high volume, it may be an advantage to
build a very specific co-processor. One decides for one elliptic curve (and protocol) and
tries to make the hardware as small/fast as possible. One classic example are the GF(2^n)
modular multipliers which are similar to an LFSR. But they only work on one distinct curve.
And if anything "happens with the curve" that was used, one is not able to change the
protocol (parameters) if the product is out in the field.
Alternatively, one can design a general purpose co-processor. These are designed to realize
in hardware operations like a*b mod p, for generic a,b,p. These co-processors usually don't
have an advantage if the input values have a special shape. But on the other hand, they are
able to handle whole classes of elliptic ccurves. They even might be able to handle RSA
additionally. For hardware manufacturers it is very hard to support many different
co-processors, so their choice is often a general purpose co-processor (maybe with their
individual implementation of a modular multiplication)  
This is the reason why Joppe mentioned that a special taylored elliptic curve (or p)
will not increase performance.
In all, I therfore think it might be a good idea to define two (sets of) elliptic curves:
One that are easy to implement in software running on hardware without special security
needs (except for constant timing or so). And one with random parameters for the rest.
At the moment I see the danger that only curves suitable for TLS are choosen and then the
rest of the (security) world will have to live with it.

Wieland

Am 05.09.2014 um 20:34 schrieb "Johannes Merkle" <[email-masked]>:

-- 
Johannes

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 06 Sep 2014 15:52:54 +0100

On 05/09/2014 12:34, Johannes Merkle wrote:

> What I understood is that [hardware vendors] do not want to 
> specialize their hardware to minimize their investment while being
>  fully flexible (algorithm agile). […] Furthermore, I guess that
> new implementations can be built easier based on existing ones.

Quite. For decades, many vendors of cryptoprocessors have been basing
their implementations almost directly on existing ones with very few,
extremely conservative changes, presumably minimising their investment
by reusing as much as possible.

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.

While some existing hardware could indeed be adapted, whether abusing
the RSA multiplier where possible or (more likely, I feel) implementing
it entirely in firmware, I suggest those seeking these recommendations
for new elliptic curves, via an open process like this, should also have
plenty of concerns about crypto implementations presented as a closed
"black box" with an uncertain pedigree which has not also been designed,
audited, and certified as openly as possible from its inception. Rusty,
closed crypto hardware with new paintwork is, I feel, unlikely to meet
those needs.

I'm not aware of any cryptoprocessor vendor who has shipped any new
hardware like that, but I would heartily welcome and encourage it.

I gather a few efforts are under way from private teams, as has been
previously discussed.

- -- 
/akr

---

From: Watson Ladd <[email-masked]>
Date: Sat, 6 Sep 2014 11:42:04 -0700

On Tue, Sep 2, 2014 at 4:43 AM, Joppe Bos <[email-masked]> wrote:
> the choice of the new “standard” elliptic curves used in a broader setting.
> blinding (e.g. see https://eprint.iacr.org/2014/191.pdf and the references
> therein). Therefore, (also) specifying curves defined over random prime
> fields (more precisely, an elliptic curve defined over the finite field F_p
> where p is a random prime) would be a preferable additional design
> requirement from a hardware point of view.
>
>

I don't think the above argument is quite correct: the hardware
designed to protect a public key against incompetent coders by
removing it is replacing software that was not designed to deal with
power-measurement side-channels, and so we shouldn't require it to
stand up to such side channels. This isn't to say that side-channel
resistance isn't desirable in all cases, but the people who care about
side-channels already have hardware. (Timing is a special case:
remotely observable.)

While it would be desirable to address this issue of random primes,
the Brainpool curves did, and I don't see wide uptake in hardware of
(then again, I don't know much about the hardware market, so could be
wrong). Conversely, the NIST curves, which were influence by hardware
considerations didn't, but this could be due to new advances in the
cat-and-mouse game of side-channels. I'm also not sure that scalar
blinding is
the last word on protections against SCA.

On the software side the costs of random primes and Weierstrass form
are very clear: we get Brainpool, which is much slower than the NIST
curves. Performance is a security concern: crypto that is disabled for
being too slow protects nothing.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Patrick Georgi <[email-masked]>
Date: Sat, 06 Sep 2014 21:18:46 +0200

Am 06.09.2014 um 20:42 schrieb Watson Ladd:
> wrong).
http://dev.openecard.org/attachments/download/327/10-45-sign-me_OpenIdentitySummit2013.pdf indicates use of Brainpool in Germany's national ID cards. That will be some 60 million active smartcards in a couple of years (when older id cards expired). Some European passports seem to use it as well (as claimed on http://bugs.java.com/bugdatabase/view_bug.do?bug_id=7007966).

The ID cards in particular include an opt-in feature that allows users to identify themselves electronically, eg. to provide an electronic equivalent to a signature for contracts signed online (The idea is to eliminate the need to snail mail hand-signed paperwork, at least for those using the system).

That feature makes it relevant for internet standards (unlike "internal" smartcard deployments that will never interact with a system inspired by IETF standards).

Patrick

---

From: Paul Lambert <[email-masked]>
Date: Sun, 7 Sep 2014 22:25:57 -0700

On 9/2/14, 9:31 AM, "Michael Hamburg" <[email-masked]> wrote:

>I agree with Alyssa that hardware performance isn¹t our concern here.
>
>However, I¹m curious about Joppe Bos¹ assertion that random primes are
>just as fast and more secure in hardware.  What kind of hardware are you
>thinking about?  Some kind of residue number system?  Or a bit-at-a-time
>reduction system?

I work at a chip company Š checking on design considerations:
 - random primes and special run at the same speed
 - flexibility and die size are more important than prime specific
optimization

Hardware performance should not be used as a reason to eliminate random
primes.

Paul

>
>I have some limited experience in crypto hardware design, in particular
>working with a hardware modulo multiplier.  If I recall correctly, adding
>support for a handful of the NIST primes (192, 224, 256 and 384 maybe?)
>cost about 10% area overhead in our lightweight design, for double the
>performance.
>
>That said, this hardware used a Montgomery reduction, so the same support
>would have required more work for a 2^big-small prime.  But I¹m sure it
>can still be done.
>
>‹ Mike
>
>> Of course, there's more than one way to do it. Vendors seem to use a
>>variety of techniques for side-channel countermeasures, and other
>>techniques prefer different environments.
>> 
>> For example, balanced dual-rail logic and smaller constant-time/power
>>implementations (along with an awful lot of dead junk gates, for reasons
>>I can't quite fathom but that may be a poor attempt at DFA
>>countermeasures?).
>> 
>> Or several other implementations from multiple vendors that are
>>actually based on either specialised microcontrollers or commodity CPUs
>>with specialised firmware, resulting in what may be more accurately
>>characterised as a constrained/specialised software implementation: I
>>think this may be the overall general approach that is the most
>>flexible, modular and reusable, which may be why it's the most favoured
>>approach by most other smart card & HSM vendors, from what I've seen?
>> 
>> We are not concerned with EMV "security" here in CFRG at all, but with
>>making suggestions for *internet* protocols.
>> 
>> I think it would be a mistake to allow old hardware implementations to
>>(yet again) needlessly overshadow improved software ones: the majority
>>of implementations on the internet will invariably be software. I feel
>>we are being asked for new recommendations here, not old ones, but of
>>course, that's only my perspective.
>> 
>> - --
>> /akr

---

From: Torsten Schuetze <[email-masked]>
Date: Thu, 11 Sep 2014 10:00:31 +0200

On Sep 7, 2014, at 22:25:57 -0700 Paul Lambert <paul at marvell.com>
wrote:

> On 9/2/14, 9:31 AM, "Michael Hamburg" <mike at shiftleft.org> wrote:
>
>> I agree with Alyssa that hardware performance isn't our concern here.
>>
>> However, I'm curious about Joppe Bos' assertion that random primes are
> I work at a chip company checking on design considerations:

I fully agree with Paul's statement on flexibility and random primes.
I work at Rohde & Schwarz SIT in the high-security/high-assurance
crypto business. We use ASICs, FPGAs and smart cards and even some
software crypto implementations in our products. Our requirements on
ECC are (in this order) 1. flexibility, 2. security, and, only then 3.
performance.

First, I would like to add, that in my opinion the discussion in this
thread should not be about software versus hardware rather than

       software in a secure environment, e.g., on a secured server,
       i.e., where only the global timing as side-channel is relevant

       versus

       software on constrained devices or hardware in a hostile
       environment, i.e., where the full set of local and global
       side-channels applies.

Most of the discussion until Joppe Bos' thread was on the first group
only. I represent the second group, for short, hardware.

Some proponents of highly optimized curves with special primes seem
only be focused on the software scenario with supposedly fast ability
for bug fixes (and short product cycles?). But TLS meanwhile is not
only used in the typical web server scenario. In Germany, it is
standardized for smart metering communication (with much longer
product cycles than typical Internet business and, later,
thousands/millions of devices rolled out in the field). ECC will be
used in Car2X and in digital tachographs (where even the legitimate
driver is a potential attacker).

Let's now come to the flexibility issue: In our company we must be
able to work with hitherto unknown domain parameters, i.e., arbitrary
random primes. The only thing we can assume is that the curves are
Brainpool like. Beyond that, the curves are part of the crypto setup.
This is a hard requirement of the government agency, Federal Office of
Information Security in our case, and is required by some (not all)
other nations as part of the crypto customization.

I suppose that crypto customization may sound strange to some people
on the list who think that we can live with one and only one curve.
But that's the reality in high-assurance crypto.

Besides that we have to use different curves (all in short Weierstrass
form, not different curve types as Montgomery etc.) for signature and
ECDH. Additional measures are taken, for example, for ECDH such that
an attacker cannot easily learn the domain parameters from the data on
the wire (point compression not for the sake of saving bandwidth,
additional symmetric schemes).

As a company representative I could relax and say that we are not
affected by standardization of Edwards-, Montgomery- or even Brainpool
curves as we have to use Brainpool-like curves. But my concerns go a
step further: I'm afraid that we as a crypto community are heading
for the wrong direction. We need flexibility, i.e., no curves with a
very special structure, especially no curves with a specific prime
structure as NIST-primes or other proposed primes.

The last statement was common consensus at the recent Brainpool
meeting. Other discussed features were not that unanimously. Most of
the participants could live with twist-secure curves, less favorable
would be the neglection of the property b non-square mod p (because of
distinguished point attacks), even less favorable the cofactor
question. But it seems to me that all these specific questions can be
solved, but the random primes issue is a remaining one. All three
participating hardware manufactures (two smart card manufacturers, NXP
and Infineon, and one HSM manufacturer) stated that they currently use
(and will use) random primes in their coprocessors.

Finally, let's come to the question of Mike Hamburg. I can only speak
about the Infineon coprocessor as I was involved in that. NXP and
other smart card manufacturers use completely different designs.

The current Infineon coprocessor is a unified coprocessor for GF(p)
and GF(2^n) based on a serial-parallel multiplier which can work with
up to 2303 bit (smaller bit length are possible and favorable for ECC).
Essentially all ECC (and RSA) operations boil down to a number of
modular multiplications Z=M*C mod N. This is the essential operation
of the coprocessor.

The algorithms of all other operations, e. g., operations in
GF(2)[x]/<N[x]> aka GF(2^n), can be derived from this basic algorithm.

The algorithm for modular multiplication basically consists of a
modified Booth algorithm with variable shift length for multiplication
coarsely interleaved with a modular reduction. For modular reduction,
the ZDN-principle developed by Sedlak is used. This reduction is based
on the repeated comparison of intermediate results Z with the value Zwei
Drittel N, i.e. 2/3*N. At the end of each step we have

2/3 N < |Z| <= 4/3 N

The multiplication part results in

Z=Z+a*2^{s_C}*C

with "sign" a = -1,0,+1 and shift 0<= s_c <= const_1.
The reduction part results in

Z=Z+b*2^{s_N}*N

with "sign" b=-1,0,+1 and shift -const_2 <= s_N <= const_2. These two
operational parts are combined into a Three Operand Addition

(#) Z=Z+a*2^{s_C}*C + b*2^{s_N}*N

The difficult algorithmic part is the data-dependent determination of
optimal "signs" a,b and shift values s_C, s_N. It should be noted that
the described scheme is that of the old ACE (i.e. before 2002), the
new Crypto@2304T uses further, rather technical refinements.

The 3-Operand-Addition is done by transformation into Carry-Save
Addition form -> (C,S) (fully parallelized) and further Carry Look
Ahead Adders.

The nice fact about this coprocessor is that in every step
approximately E(s_z,s_C) \approx 2.7 ... 2.8 bits of the multiplier
are processed and that Booth and ZDN are in a certain sense
optimal/dual.

One can easily see from (#) that a special structure of the modulus N
is of no use here. This can be verified by simulations and
measurements (take an arbitrary IFX smart card with public-key
coprocessor).

To sum up, especially for hardware vendors special primes are of no
use and can even be dangerous, see the separate mail by Wieland
Fischer on blinding issues.

Regards,

Torsten
-- 
ROHDE & SCHWARZ SIT GmbH
Hemminger Str. 41
D-70499 Stuttgart/Weilimdorf
Tel ++ 49 711 69945 183
Fax ++ 49 711 69945 170
http://www.sit.rohde-schwarz.com
mailto:[email-masked]

---

From: Torsten Schuetze <[email-masked]>
Date: Thu, 11 Sep 2014 10:51:04 +0200

On 06/09/2014 15:52:54 +0100, Alyssa Rowan <akr at akr.io> wrote:

>>  fully flexible (algorithm agile). [...] Furthermore, I guess that

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?

> closed crypto hardware with new paintwork is, I feel, unlikely to meet

Only the multiplier is in hardware. ECC on smart cards is usually done
in firmware, as you call it. Companies like Gemalto or Giesecke &
Devrient do this regularly, if you don't trust the hardware vendor like
NXP, Samsung, Infineon, etc.

What do you mean with "an uncertain pedigree which has not also been
designed, audited, and certified as openly as possible from its
inception"? 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? Shall everything be open-source? Do you trust your compiler
when compiling your specialized highly-optimized elliptic curve
arithmetic? Or do you perform a formal verification before hand? Do
you trust your Intel processor?

> 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.

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? Do you know the
product and development cycles/costs for ASICs/smart cards? 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. Besides that, the software on the smart cards has much
shorter cycles. For example, the German scheme for qualified digital
signatures, the highest security requirements in the public sector,
has cycle times about 7-8 years, i.e., 2-3 years development and
evaluation, 5 years in the field.

> I gather a few efforts are under way from private teams, as has been

We as high-security/hardware crypto community certainly welcome new
ideas. Competition is always good for security.

Regards,
  Torsten

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 11 Sep 2014 07:58:35 -0700

> other nations as part of the crypto customization.

What's the actual issue here?  Presumably this means that your device
will work just as well on e.g. GP(2^255-19) as on any other prime of
similar size.  It won't be faster the way that software implementation
can be faster, but that doesn't seem like it will cause a problem.

> structure as NIST-primes or other proposed primes.

CFRG and/or IETF aren't about to give you flexibility no matter what
curves are chosen.  All signs point to choosing a very small number of
curves.

Why is this a problem?  If you need to support arbitrary curves,
you'll do this regardless.

If, on the other hand, you were implementing, e.g., a CFRG-recommended
Edwards-coordinate cryptosystem, could you convert to Weierstrass
coordinates and then use your hardware?  Obviously you can't
interoperate with someone expecting Edwards coordinates if you do
this, but if you need a specific wire format for some compliance
reason, then you can't interoperate with anyone who doesn't use that
wire format regardless.  Nonetheless, I think you could convert the
format and still have your hardware work fine.

> (and will use) random primes in their coprocessors.

Can anyone explain why "random" primes are better for blinding?  Keep
in mind that, from the point of view of an attacker, no common ECC
protocol uses a random prime; they just use primes without much
interesting structure.  The adversary knows the prime.

--Andy

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 11 Sep 2014 09:22:53 -0700

Sent from my phone.  Please excuse brevity and typos.

> On Sep 11, 2014, at 7:58, Andy Lutomirski <[email-masked]> wrote:
> 

With an unstructured prime, adding a small random multiple of p or the group order q will change every bit of the addend.  With a sparse prime, it will not.  This makes blinding a less effective countermeasure when p is sparse. 

Torsten, thanks for the description of smart card hardware and concerns.  It was very educational.  I expected something looking more like a specialized CPU, where a sparse prime reduction unit could be bolted on easily. 

You should keep in mind, though, that the curves being proposed are designed for security against local side channels as well as global ones. The submitted implementations are designed not to leak against an adversary who can see all memory addresses accessed and instructions executed, even without blinding. That's a lot easier than power and fault defense, but we're not slacking on the software side either.

-- Mike

---

From: Torsten Schuetze <[email-masked]>
Date: Thu, 11 Sep 2014 20:06:51 +0200

On Sep 11, 2014 09:22:53 -0700 Mike Hamburg <mike at shiftleft.org>
wrote:

>> On Sep 11, 2014, at 7:58, Andy Lutomirski <luto at amacapital.net> wrote:
>>
>>
>> Can anyone explain why "random" primes are better for blinding?
>>
>> --Andy
>
> With an unstructured prime, adding a small random multiple of p or
> the group order q will change every bit of the addend.  With a
> sparse prime, it will not.  This makes blinding a less effective
> countermeasure when p is sparse.

Mike, thanks for explaining.

> Torsten, thanks for the description of smart card hardware and
> concerns. It was very educational. I expected something looking
> more like a specialized CPU, where a sparse prime reduction unit
> could be bolted on easily.

The only thing I know in this direction are FPGA proposals like
Güneysu:Paar:2008 CHES 2008 'Ultra High Performance ECC over NIST
Primes on Commercial FPGAs' and even Sasdrich:Güneysu:2014 ARC 2014
'Efficient ECC using Curve25519' which both use the specific DSPs on
the FPGAs.

These are both great papers with very good performance results. But
they show what I mean with flexibility: it is not easily possible to
use 'random' or unstructured primes or even use the original primes
with enough blinding (because the blinding disturbs the structure).

Some years ago, I was looking for a general GF(p) crypto coprocessor
on a FPGA (Car2X standardization, like IEEE 1609.2, but without NIST
primes). The only thing I came up with was Nele Mentens Phd, 2007
(Montgomery multiplication, coarsely integrated operand scanning) and
the CHES 2010 paper by N. Guillermin (RNS). Unfortunately, I could not
find direct comparisons of, say, Brainpool and NIST curves on these
architectures.

> You should keep in mind, though, that the curves being proposed are
> designed for security against local side channels as well as global
> ones. The submitted implementations are designed not to leak against
> an adversary who can see all memory addresses accessed and
> instructions executed, even without blinding.

It all depends on the adversarial model.

> That's a lot easier than power and fault defense, but we're not
> slacking on the software side either.

But you surely know from your company background Cryptography
Research that electromagnetic attacks in a template like fashion are
currently the most advanced attacks. And I don't see that one can
solve this issue without heavy blinding.

Torsten

---

From: Watson Ladd <[email-masked]>
Date: Thu, 11 Sep 2014 18:56:54 -0700

So I don't understand why you are asking for something that the
brainpool curves don't already give you. We are not removing curves
from TLS, and we already knew that FIPS users were likely to not adopt
the new curves, so nonsupport isn't an issue. Even if we had only the
NIST curves, and did nothing, you would be in the same position. There
is an enormous performance benefit in software for special primes, and
the sort of side channel attacks that require special blinding don't
matter on servers, even if the curve is implemented on hardware.

I think it's clear that the desired properties are different enough
that there is no way to satisfy everyone.

Sincerely,
Watson Ladd

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 12 Sep 2014 03:11:58 -0700

> find direct comparisons of, say, Brainpool and NIST curves on these
This is interesting but fairly far afield, so I might rather continue 
this part of the thread offlist.
> It all depends on the adversarial model.
The adversarial model of most crypto software these days is that the 
attacker is running on the same machine as you, as an unprivileged user, 
and through timing channels he can see enough of your data access and 
control flow patterns that they had better not correlate with secret 
data.  This is at least true for OpenSSL (it fails sometimes, though), 
Curve25519 (NaCl, Donna), Goldilocks, and MS NUMS.
> solve this issue without heavy blinding.
Right, of course.  And by "power", I meant to include EM, the attacks 
and defenses being very similar in nature.

Thanks for the info,
-- Mike

---

From: Alyssa Rowan <[email-masked]>
Date: Sun, 14 Sep 2014 19:36:07 +0100

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

>>  sufficient assurance where the integrity of the base is properly
>> in question: you don't add a conservatory to fix uncertain 
>> foundations.
> 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.

> 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

---

From: "Lochter, Manfred" <[email-masked]>
Date: Mon, 15 Sep 2014 12:53:28 +0200

Watson,

you are right when you assume that Brainpool users can live with what they 
have, if Brainpool-like curves will be mandatory to implement for TLS 1.3.

If this will not be the case  the crucial points are interoperability and 
cost:

Assume a server using software optimized code wants to talk to a smart card  
implementation of ECC, supporting random primes.
Which curve will be selected for this communication by TLS? 
I see three possible solutions:

a) The special prime curve is selected. This means that the smart card has to 
be certified (e.g. according to the Common Criteria) for use with this curve. 
Note that certificates usually specify which curve has to be used. 
Adding new curves increases the cost of certification. It has also turned out 
that protection of hardware implementations of ECC over special prime fields 
is more costly.
b) The random prime curve is selected. In this case the software side has to 
provide a second implementation of ECC that supports random primes. This 
leads to a small increase of cost on the software side.
c) Client and server do not support a common curve. In this case  no secure 
communication can be established. This course is counterproductive and should 
not be chosen.

A possible solution would thus be to make at least one curve over a random 
prime field mandatory (for each security level). This solution implies that 
there will be more than one standard curve. 

Sincerely
Manfred Lochter

__________ ursprüngliche Nachricht __________

Von:		Watson Ladd <[email-masked]>
Datum:	Freitag, 12. September 2014, 03:56:54
An:		Torsten Schuetze <[email-masked]>
Kopie:	"[email-masked]" <[email-masked]>
Betr.:	Re: [Cfrg] Hardware requirements for elliptic curves

Postfach 20 03 63
53133 Bonn

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 15 Sep 2014 13:50:33 +0100

>have, if Brainpool-like curves will be mandatory to implement for TLS

The question of what should be MTI in TLS 1.3 and why is plainly a matter for the upstream TLS list to debate, not CFRG.

If people want random primes, Brainpool already gives you those - that's Watson's point. I don't think that's what upstream are looking for, though. If people wanted that, they'd be using it already: yet UTA actually removed Brainpool from their draft recommendations recently due to its rarity and performance.

It just doesn't look like the pendulum's swinging that way, and I can see why: the relatively poor performance of Brainpool-class random primes in software; the difficulty of securing generic elliptic curve software routines against timing side-channels; and the sheer cost-multiplication potential of a proposal to mandate the option of using relatively-inefficient crypto near-universally across the web - including at CDN scale!? I think personally you'd face a massive uphill struggle arguing for random curve support to ever be anything better than MAY. But that's something I reckon you should take over to those lists if you *really* want to raise it? (I'll bring marshmallows! <g>)

If your hardware is truly securely flexible, then you can adapt with no trouble; if it's not flexible enough to securely work with efficient sparse primes that also perform well in software, well, you probably need to consider at least updating it so it is (how is it with the NIST "Solinas primes"? Equally bad, one would have thought? Yet they're the most deployed by far...).

Also, please don't forget: FIPS 140-2 (/3?) evaluations/certifications are not exclusive to hardware, and neither are Common Criteria EAL*: both happen for certain software implementations.

- --
/akr

---

From: Dirk Feldhusen <[email-masked]>
Date: Mon, 15 Sep 2014 16:34:11 +0200

Am 15.09.2014 14:50, schrieb Alyssa Rowan:
> The question of what should be MTI in TLS 1.3 and why is plainly a
matter for the upstream TLS list to debate, not CFRG.
>
> If people want random primes, Brainpool already gives you those -
that's Watson's point. I don't think that's what upstream are looking
for, though. If people wanted that, they'd be using it already: yet UTA
actually removed Brainpool from their draft recommendations recently due
to its rarity and performance.
>
> It just doesn't look like the pendulum's swinging that way, and I can
see why: the relatively poor performance of Brainpool-class random
primes in software; the difficulty of securing generic elliptic curve
software routines against timing side-channels; and the sheer
cost-multiplication potential of a proposal to mandate the option of
using relatively-inefficient crypto near-universally across the web -
including at CDN scale!? I think personally you'd face a massive uphill
struggle arguing for random curve support to ever be anything better
than MAY. But that's something I reckon you should take over to those
lists if you *really* want to raise it? (I'll bring marshmallows! <g>)

I don't understand why securing generic elliptic curve implementation
should be harder. Regularised scalar multiplication methods are
quite standard in security implementations. But (nearly) time constant
modular multiplication or LIM routines for fixed bit length I've seen up
to now only in hardware. Contrariwise for software implementations, see
the for instance bunch of publications on RSA timing attacks. Why there
are no time dependencies on the arguments for  modular multiplication
with special primes?
Even when the algorithm is time constant in theory there could be
properties of the hardware which could complicate the situation, for
instance the bug attacks (Crypto 2008) or cache timing attacks on the AES.
Side channel resistance is a property of the software together with the
underlying hardware.

Cheers,
Dirk

(where are the marshmallows?)

---

From: "Lochter, Manfred" <[email-masked]>
Date: Mon, 15 Sep 2014 17:43:19 +0200

Von:		Alyssa Rowan <[email-masked]>
Datum:	Montag, 15. September 2014, 14:50:33
An:		[email-masked]
Kopie:	
Betr.:	Re: [Cfrg] Hardware requirements for elliptic curves

>
> It just doesn't look like the pendulum's swinging that way, and I can see
> why: the relatively poor performance of Brainpool-class random primes in
> software; the difficulty of securing generic elliptic curve software
> routines against timing side-channels;

Actually I don' t see your point here. Watson's mail was about special primes 
versus random primes. The use of special primes does not harden 
implementations against timing attacks. But the use of special primes makes 
additional SCA countermeasures necessary, thus increasing implementation 
cost.

> and the sheer cost-multiplication 
> potential of a proposal to mandate the option of using
> relatively-inefficient crypto near-universally across the web - including
> at CDN scale!?

What is your measure for inefficiency? Cost per Signature? Or time per 
signature? Or something different? Relatively to what?

> I think personally you'd face a massive uphill struggle 
> arguing for random curve support to ever be anything better than MAY. But
> that's something I reckon you should take over to those lists if you
> *really* want to raise it? (I'll bring marshmallows! <g>)

Can we agree on licorice?

>
> If your hardware is truly securely flexible, then you can adapt with no
> trouble; if it's not flexible enough to securely work with efficient sparse
> primes that also perform well in software, well, you probably need to
> consider at least updating it so it is (how is it with the NIST "Solinas
> primes"? Equally bad, one would have thought? Yet they're the most deployed
> by far...).

This is not a hardware question. Actually the problem is that curves over 
special primes need more SCA countermesures. This is also true for software 
running on a general purpose processor.
In fact the discussion here is not about hardware or software. It is about 
different hardware platforms (e.g. server, smart card) on which ECC is 
running under different attack models. 
>
> Also, please don't forget: FIPS 140-2 (/3?) evaluations/certifications are
> not exclusive to hardware, and neither are Common Criteria EAL*: both
> happen for certain software implementations.

Oh, really? Then you have a CC protection profile for TLS running in software 
available for review? At which EAL?

Postfach 20 03 63
53133 Bonn

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 15 Sep 2014 20:26:37 +0300

> signature? Or something different? Relatively to what?

Both cost per signature and cost per verification of signature. Can fairly
easily be 2x cost.

And nobody wants that sort of cost, unless 1) Legally mandated to. 2) Having
to interoperate.

And nobody is proposing to remove the Brainpool codepoints from TLS. Special
servers that communicate with smartcards or whatever (most don't!) can
implement those.

Having to implement random curves would be RFC6919 "MUST (but we know you
won't)".

> running on a general purpose processor.

One problem here is that general purpose CPUs are hugely complex, so it is
very difficult to know how various operations affect side channels like EM
or PA. But withstanding software-only attacks (and that goes far beyond
global timing) is likely a huge help here.

And those software-only attacks are not jokes. Modern CPUs and OSes tend
to be extremely vulernable.

Special-purpose crypto chips can at least be designed at hardware level to
reduce SCA attacks (sometimes well, sometimes badly).

-Ilari

---

From: Watson Ladd <[email-masked]>
Date: Tue, 16 Sep 2014 18:59:52 -0700

> additional SCA countermeasures necessary, thus increasing implementation

Most users do not need power or EM SCA protection: they rely on
distance together with physical controls, or are so screwed anyway
that it doesn't matter.

Amazon's Cloud HSM doesn't have RSA blinding turned on by default,
showing the extent to which side channels are a concern.
> running under different attack models.

Exactly right: the costs are so wildly different that the best
solution when you don't worry about power analysis is very different
from when you do. That's an argument for two different solutions, not
one that satisfies no one.

Sincerely,
Watson Ladd