Re: [Cfrg] Hardware requirements for elliptic curves

[Watson Ladd <[e-mail]>]

On Tue, Sep 2, 2014 at 4:43 AM, Joppe Bos <[e-mail]> wrote:
> 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 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

>
> Joppe Bos
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>



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