Re: [Cfrg] revised requirements for new curves

Phillip Hallam-Baker <phill@hallambaker.com> Sun, 14 September 2014 14:22 UTC

Return-Path: <hallam@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 946521A03C1 for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 07:22:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.621
X-Spam-Level:
X-Spam-Status: No, score=0.621 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=no
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 B4oSeGw837kq for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 07:22:54 -0700 (PDT)
Received: from mail-la0-x233.google.com (mail-la0-x233.google.com [IPv6:2a00:1450:4010:c03::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1014C1A03BF for <cfrg@irtf.org>; Sun, 14 Sep 2014 07:22:53 -0700 (PDT)
Received: by mail-la0-f51.google.com with SMTP id gi9so3246759lab.24 for <cfrg@irtf.org>; Sun, 14 Sep 2014 07:22:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=BWe7Mkn0/JCD/6JBVdauTzAmOxFkleTg0Gf7MO0yBss=; b=EMZWlGSBCXh5/ghdIHfNtcZv5HS6tAGslF+/zMDBoA7u2bqPpD1poipfZtXUNDgEDx q8WB8pGrkF5K7VynTiiI7JV6ste/A+jBGD4AXqJwrvnN1uMFzWNnpPIihXnKSDcw2oC9 qxQ1oxq9xe7wpC3d4eymDzuCBLWAxNRrRpbG06f0T/BqPVk6mySFtq6JVVXYDylg+qL6 SfGluCYd7DBL3Y9RDYU0g6N/UMSx+fyajRMtEjW7f29H9Q8Mdv2h7h0at8H3jfptU5L8 GKbYPx4ncV+3ab+69onIm/R20QLzJIVoTSev644VKdOAfDEKfS0fW0khjiNOE8hNHIko JB0Q==
MIME-Version: 1.0
X-Received: by 10.112.204.197 with SMTP id la5mr19915542lbc.2.1410704571309; Sun, 14 Sep 2014 07:22:51 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.112.122.51 with HTTP; Sun, 14 Sep 2014 07:22:51 -0700 (PDT)
In-Reply-To: <CAMfhd9UaJtcaRurEOtN289ribT7ZH6OUB55or+T1NN6U8jv9Rw@mail.gmail.com>
References: <CAMfhd9UaJtcaRurEOtN289ribT7ZH6OUB55or+T1NN6U8jv9Rw@mail.gmail.com>
Date: Sun, 14 Sep 2014 10:22:51 -0400
X-Google-Sender-Auth: s7PiSJ6G0r3uhY-BIOHmSrf2aRs
Message-ID: <CAMm+LwhATMG9Pco-Bt1n-rgr3vEmgFKbpbvA0f9V9fW9t36UVw@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/FHPN7TJhissiZFfRqyqwQDxbopw
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] revised requirements for new 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 14:22:55 -0000

On Tue, Sep 9, 2014 at 4:23 PM, Adam Langley <agl@imperialviolet.org> wrote:

> Although flexibility should be eliminated where possible, we believe
> that forgoing sensible optimisations because of a fear that someone
> might know a magic attack on a subset of curves and might be guiding
> the selection them that would be a mistake. We are not looking for a
> replacement for P-256 because we seriously worry that the NSA
> backdoored it.

Well maybe not. BUT one of the main advantages of moving to new curves
is that the deployment of ECC has been gradual and incremental and has
taken an enormous amount of time. And one of the main points to a flag
day is not just burning the old ones, it is getting everyone to buy
and hang the new.


>We're looking for a replacement because we think that
> we can get something much faster and simpler.

Case in point here, can anyone who has these facts at their disposal
tell us what sort of leverage random curves are believed to provide
over primes close to a power of 2.

The issue here is cryptographic leverage. I am prepared to do more
work to increase the work factor for the attacker. But should I pick
(say) a fast curve with 256 bits or a slower curve with 192 bits?

If the two curves give exactly the same work factor or take exactly as
long with different security, then the comparison is easy. But things
rarely turn out so simple, chances are that the fast but bigger curve
turns out to be a little bit slower and a bit more secure than the
smaller one... oops.


The basis for comparison is a little tricky...

If I am doing RSA 2048 then I an doing four times the work of RSA 1028
But if I am doing a symmetric cipher then 256 bits is more likely to
take about double 128

Oh and RSA 2048 does not give anywhere close to the square of the work
factor of RSA1024 (i.e. double the bits). In fact that is one of the
main reasons we have to look beyond RSA.


But if we plot the points on graphs of defender effort vs attacker
work factor and look at the curves we can probably see quite easily
what we are buying with the different approaches.