Re: [Cfrg] Hardware requirements for elliptic curves

Andy Lutomirski <luto@amacapital.net> Thu, 11 September 2014 14:59 UTC

Return-Path: <luto@amacapital.net>
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 892B51A00C3 for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 07:59:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.979
X-Spam-Level:
X-Spam-Status: No, score=-1.979 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7, 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 CEUrr_UGX8io for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 07:59:02 -0700 (PDT)
Received: from mail-la0-f43.google.com (mail-la0-f43.google.com [209.85.215.43]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D2AC81A00BB for <cfrg@irtf.org>; Thu, 11 Sep 2014 07:59:01 -0700 (PDT)
Received: by mail-la0-f43.google.com with SMTP id gi9so11999858lab.30 for <cfrg@irtf.org>; Thu, 11 Sep 2014 07:58:55 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=ilc/U6OckZ+qpHvHaG4uAyIW9w8TwnXSUE4IO3Er3ic=; b=GlEiscxXn0b/Mds4UdS9BUfKQclL1NZXc+mFuWoma/rciCHWH6taJjAehthYiT2/Rz DTG35l+LkTdba3o4xBEN8mPFVySYkellSpV73im/I5BnFO5pQLubpYVZcglhDsBKUTYI y01JCkwjMGH4XzkkhJtcrzEDcoSbjLK5/wmZokfdccDGN4YPIoFGxY6Weh3+e1LJXo0M bzqzJ2uh93qLz1nVCMSiorvdb9K2I5FlRzvdeJWnZOqKzeXfyMaoAY9/hPbq2Cs77x78 KzUzhAsdnyRY7Vyz5cqCEMJhlzdyEDCL39puJ9vrbzoMEuSUTBg4m+Iz7/Ad6/fzbbf8 AmgQ==
X-Gm-Message-State: ALoCoQmTCdZj6K786XUQRVkfjFhvYK/Nw7SjLJ8HSPe2P6PGN64l38kO31GPWDT0LtGFsh63VVGU
X-Received: by 10.112.210.138 with SMTP id mu10mr1597112lbc.81.1410447535577; Thu, 11 Sep 2014 07:58:55 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.152.36.106 with HTTP; Thu, 11 Sep 2014 07:58:35 -0700 (PDT)
In-Reply-To: <5411569F.6080102@gmx.net>
References: <12A4E7B4-8303-449F-A04B-8366BBC5B1E3@shiftleft.org> <5411569F.6080102@gmx.net>
From: Andy Lutomirski <luto@amacapital.net>
Date: Thu, 11 Sep 2014 07:58:35 -0700
Message-ID: <CALCETrWWoQJn58nJucvC1YM_3gi_hZvzY5c-QbA19huMOabyYQ@mail.gmail.com>
To: Torsten Schuetze <torsten.schuetze@gmx.net>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/BSd9J1Pe3M6SloWfSt7EGjunpao
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: Thu, 11 Sep 2014 14:59:03 -0000

On Thu, Sep 11, 2014 at 1:00 AM, Torsten Schuetze
<torsten.schuetze@gmx.net>; wrote:
>
> 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.

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.

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

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.


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

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