Re: [Cfrg] Hardware requirements for elliptic curves

Watson Ladd <watsonbladd@gmail.com> Sat, 06 September 2014 18:42 UTC

Return-Path: <watsonbladd@gmail.com>
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 1B3D91A03B5 for <cfrg@ietfa.amsl.com>; Sat, 6 Sep 2014 11:42:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.7
X-Spam-Level:
X-Spam-Status: No, score=0.7 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=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 ONprStaMsNdP for <cfrg@ietfa.amsl.com>; Sat, 6 Sep 2014 11:42:06 -0700 (PDT)
Received: from mail-yk0-x230.google.com (mail-yk0-x230.google.com [IPv6:2607:f8b0:4002:c07::230]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2365E1A0028 for <cfrg@irtf.org>; Sat, 6 Sep 2014 11:42:05 -0700 (PDT)
Received: by mail-yk0-f176.google.com with SMTP id 19so7770409ykq.21 for <cfrg@irtf.org>; Sat, 06 Sep 2014 11:42:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=lLJaWdVJMY80n4X7Mt5uTo0RDiRHEqFtS/JaY4i0Y+k=; b=pU7AEvVoHar6YPKjvdVm9solTbZSIN40imMpqT5v3EQ8c4mqUjagDh6uF4HK/fWIxp MSHzrFkL07gmwqfIz0K9JvLmN5j1Ew3N8EoFyqdRWyAZO2/dSE6jsBFX24eZYSd8ThtF bGrQkM0dfLsof2mfcP3nE5Q1AEFrrxD0h+JZKEkuj3/5uNxJSEj4is+nxlLXYbFEeCVo Dve1cZrqXD9qOBUPbnZnD0N6u5Zr0xvsE4ZzIAvtyuAInhb1txqOTZEmTZwFqMl7Lhnp UddwaMg/2FvHP5X94BVYOr8JHUF72zU9RFztrhAwt1PeSomRxtFDML83Qy2VJs5cF27Q 2VRw==
MIME-Version: 1.0
X-Received: by 10.236.19.101 with SMTP id m65mr2400058yhm.134.1410028924417; Sat, 06 Sep 2014 11:42:04 -0700 (PDT)
Received: by 10.170.202.2 with HTTP; Sat, 6 Sep 2014 11:42:04 -0700 (PDT)
In-Reply-To: <85d1c59362684615b0beeea1c2a48dd8@AMSPR04MB518.eurprd04.prod.outlook.com>
References: <85d1c59362684615b0beeea1c2a48dd8@AMSPR04MB518.eurprd04.prod.outlook.com>
Date: Sat, 6 Sep 2014 11:42:04 -0700
Message-ID: <CACsn0ckhLJjQeAiSJ4tUdEXinvo8XDBTrX5NHhHTXm7D8Gib4g@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Joppe Bos <joppe.bos@nxp.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/rz3FYHDHaHWlDiRFILrBUOTZ0TU
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
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: Sat, 06 Sep 2014 18:42:08 -0000

On Tue, Sep 2, 2014 at 4:43 AM, Joppe Bos <joppe.bos@nxp.com>; 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
> Cfrg@irtf.org
> 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