Re: [Cfrg] ECC desiderata

"D. J. Bernstein" <djb@cr.yp.to> Sat, 09 August 2014 04:31 UTC

Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
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 842481A0AAD for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 21:31:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.677
X-Spam-Level:
X-Spam-Status: No, score=-1.677 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RAZOR2_CHECK=0.922, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=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 XQY7l7rlF_vv for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 21:31:26 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 220531A0AA4 for <cfrg@irtf.org>; Fri, 8 Aug 2014 21:31:25 -0700 (PDT)
Received: (qmail 17191 invoked by uid 1011); 9 Aug 2014 04:31:25 -0000
Received: from unknown (unknown) by unknown with QMTP; 9 Aug 2014 04:31:25 -0000
Received: (qmail 10800 invoked by uid 1001); 9 Aug 2014 04:31:16 -0000
Date: 9 Aug 2014 04:31:16 -0000
Message-ID: <20140809043116.10798.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <CADMpkcKRvi7WcbR==XF1G5b94jN7Y5+a2j_zDE8AZFTzy_UERg@mail.gmail.com>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/jN_JOChWkuSUkxhi-j_XZaeP2RM
Subject: Re: [Cfrg] ECC desiderata
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, 09 Aug 2014 04:31:30 -0000

Bodo Moeller writes:
> As the example of TLS with its protocol flaws shows (see the unknown
> key-share attacks in https://secure-resumption.com/tlsauth.pdf), it is
> possible to end up in a situation in which public-key validation
> *does* matter; it's easier to get right with cofactor 1.

Are you sure that patching this protocol with (patented) public-key
validation is actually easier to get right with cofactor 1 than with,
e.g., Curve25519? For Curve25519 a simple check for ladder output 0
detects all "non-contributory" inputs, thanks to

   (1) the theorem guaranteeing that scalar multiplication works for all
       inputs and
   (2) the factor 8 in the local scalar.

For cofactor 1 the implementor has to go digging through obscure, poorly
tested code to figure out how the point at infinity might end up being
communicated (e.g., does the implementation treat input points off the
curve as infinity?) and then represented internally.

Isn't TLS actually moving to something much more confidence-inspiring
than such patches, namely hashing more inputs? Hashing stops the attack
without public-key validation and without the implementor having an
oportunity to screw up public-key validation. Isn't hashing also what
the attack authors recommended?

Anyway, these are evaluation questions, and all of them fit within my
suggested statement of desiderata:

   D1. Speed and simplicity (and speed-simplicity combinations) for
   secure implementations.

   D2. Avoiding speed incentives and simplicity incentives towards
   insecure implementations.

When you argue that in some situations cofactor 1 produces secure
implementations more simply than larger cofactors do, you're arguing
that to some extent cofactor 1 scores well on simplicity for secure
implementations and avoids simplicity incentives towards insecure
implementations (whereas I'm arguing that this evaluation is incorrect
and in any case is outweighed by the much more common situations in
which cofactor 1 scores very badly). This seems to be a confirming
example of D1+D2 as capturing the real desiderata: we're discussing the
simplicity of secure implementations and of insecure implementations.

---Dan