Re: [Cfrg] Curve manipulation, revisited

Adam Langley <agl@imperialviolet.org> Thu, 25 December 2014 21:05 UTC

Return-Path: <alangley@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 62CD61A887A for <cfrg@ietfa.amsl.com>; Thu, 25 Dec 2014 13:05:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 g4Q4bCfF5tyv for <cfrg@ietfa.amsl.com>; Thu, 25 Dec 2014 13:05:30 -0800 (PST)
Received: from mail-la0-x22b.google.com (mail-la0-x22b.google.com [IPv6:2a00:1450:4010:c03::22b]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EA7891A8874 for <cfrg@irtf.org>; Thu, 25 Dec 2014 13:05:29 -0800 (PST)
Received: by mail-la0-f43.google.com with SMTP id s18so8312763lam.16 for <cfrg@irtf.org>; Thu, 25 Dec 2014 13:05:28 -0800 (PST)
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=0oYfvOnCfwInncqW35wCQZAwHVeyU6f/mQIYUO7r0Hg=; b=ksENiRUfNPQiq0Qt6rLF662QwVhXDe1UzCVkq7qM7ebNcdDchuKzq6V7lIgtBJgA9M sUbIlFIB8ByiwEBIrVdfFo4SE8DYkTSyDZhAiZ9JQ9dWkwB7gCrV01H7TO7HTTb4tuRm SNX/39bn3XlzF6eyVpKhfty5LjK9LKKemzBnKciqk294IihIsP3OH9mHggeo5zJcAgtr 9T1fFLaXKQhYfyTARa39q8MPTkq+1ZGu1ontTyUREb2Xnpq3+ycoRIM2XwZRvu2xGFpN u4gQGqu/W4cc19qvmmSfB0UA7M1P63hJc3grp4LJskK+Vzf098DYcedH2xc6j+EeJN55 23nA==
MIME-Version: 1.0
X-Received: by 10.153.5.1 with SMTP id ci1mr34778331lad.67.1419541528409; Thu, 25 Dec 2014 13:05:28 -0800 (PST)
Sender: alangley@gmail.com
Received: by 10.112.114.225 with HTTP; Thu, 25 Dec 2014 13:05:27 -0800 (PST)
In-Reply-To: <1725646678.805875.1419539885135.JavaMail.yahoo@jws100115.mail.ne1.yahoo.com>
References: <CAMfhd9W684XMmXn3ueDmwrsQ_ZdiFG+VqYLxkvs7qDwiJdpk6w@mail.gmail.com> <1725646678.805875.1419539885135.JavaMail.yahoo@jws100115.mail.ne1.yahoo.com>
Date: Thu, 25 Dec 2014 21:05:27 +0000
X-Google-Sender-Auth: J_xVyXnSUwMCHKv8b5fX_Wyz74U
Message-ID: <CAMfhd9Ua5fFZk46Xx1AN2VgyJ=Yng6fnO8aN-_ZfzXQn0Xbxhg@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
To: David Gil <dgil@yahoo-inc.com>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Z7gNdJVb5BjJMv2kh6YD6buaikc
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Curve manipulation, revisited
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, 25 Dec 2014 21:05:31 -0000

> I don't think this is quite right. Imagine we could improve the square
> root in Pollard rho to cube root via some algebraic geometry. Then
> 255/3=85, but 448/3=150. Even ignoring the possibility of algorithmic
> improvements, progress in computing power may mean data that has to be
> confidential for centuries needs a larger curve. The NSA did pick P384
> for a reason.

If we are positing a cube root algorithm for discrete-log, can't we
posit a 4th root one?

But, yes, there is a possibility of an attack that's *just* right:
weak enough not to break a larger curve but strong enough to break a
smaller one. On the other hand, each additional curve dilutes
implementation resources and implementation bugs happen. I'm judging
that the risk of a bug due to the additional curve is larger than the
benefit of hedging against that specific sort of analytic breakthough.

And, if you want to keep data safe for centuries, isn't post-quantum a
requirement?

On Thu, Dec 25, 2014 at 8:38 PM, David Gil <dgil@yahoo-inc.com>; wrote:
> In particular, w.r.t. Yahoo's eventual release of an End-to-End
> messaging extension, we will generate EC keys for extension users
> on a curve subgroup with log2(#K) >= 376. The additional computational expense is, frankly, negligible.

I think my argument here is the same as above. (Although, in this
situation, you would have the advantage of being able to use the
simplest, clearest code possible because performance isn't a concern.)

> It's absurd to ignore the fact that the organization with the most mathematicians working on ECC[^fbfw] does not trust a bit-length
> 256 curve for data they consider important. See [NSA Suite B
> Cryptography][suiteb].

TOP SECRET just needed to have a bigger number than SECRET :)


Cheers

AGL

-- 
Adam Langley agl@imperialviolet.org https://www.imperialviolet.org