Re: [Cfrg] Progress on curve recommendations for TLS WG

"D. J. Bernstein" <djb@cr.yp.to> Sat, 16 August 2014 03:25 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 C7FBA1A0B78 for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 20:25:20 -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_40=-0.001, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=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 GUAYmBzoC35i for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 20:25:19 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 10E3F1A0927 for <cfrg@irtf.org>; Fri, 15 Aug 2014 20:25:18 -0700 (PDT)
Received: (qmail 24176 invoked by uid 1011); 16 Aug 2014 03:25:18 -0000
Received: from unknown (unknown) by unknown with QMTP; 16 Aug 2014 03:25:18 -0000
Received: (qmail 9073 invoked by uid 1001); 16 Aug 2014 03:23:02 -0000
Date: 16 Aug 2014 03:23:02 -0000
Message-ID: <20140816032302.9071.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: <53EDEB0D.9040304@secunet.com>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/IpBdfVMkqcTOh1bypUt1RS2BwrQ
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
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, 16 Aug 2014 03:25:20 -0000

Is anyone actually planning to propose "random" curves here? Dan Brown
said he would but didn't follow through. Brainpool already has RFCs.

Johannes Merkle writes:
> Pi and e are by far the most prominent mathematical constants, while
> cosinus(1) (used in that analysis) is quite arbitrarily chosen.

MD5 uses sin(1). This is one of several "nothing up my sleeve numbers"
cited in http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number.

Please point to the cryptographic papers disputing this "nothing up my
sleeves" designation and arguing that switching MD5 from sin(1) to e
would be less suspicious. Surely you're not claiming that the public
would have been more suspicious of cos(1) than of sin(1)?

> Keccak wasn't even invented at the time the Brainpool curves were
> generated.

Sure, but Brainpool could easily have argued for switching to the 1996
European hash function RIPEMD-160 from famed cryptographers Dobbertin,
Bosselaers, and Preneel. The SHA-1 critique in

   http://homes.esat.kuleuven.be/~bosselae/ripemd160.html

includes items from 2004 as the last three sentences but is otherwise
pre-2000 material. Do you seriously believe that switching from NSA's
SHA-1 to respectable RIPEMD-160 would have made people reject the
Brainpool curves as being potentially backdoored?

How about 192-bit Tiger, from famed cryptographers Anderson and Biham,
for extra security? Or RIPEMD-256? Or RIPEMD-320? Or one of the versions
of Whirlpool, from famed cryptographers Rijmen and Barreto? Or, back in
the NSA universe, SHA-256 or SHA-384 or SHA-512?

If you count carefully you'll see 11 different hash functions here, more
than the 10 Keccak versions that were used to manipulate BADA55-VPR-224.

> The method used to generate the coefficients of the Brainpool curves
> was taken from ANSI X9.62

http://projectbullrun.org/dual-ec/dualec-author.html illustrates NSA's
influence over ANSI. Anyway, what relevance does the identity of the
curve generator (or generators) have to the measurement of rigidity?

> There is only the slight deviation

So you're admitting that Brainpool _didn't_ actually take the same
method; it manipulated the method (to simplify it, you say). Even
without this admission, how exactly is the Brainpool procedure less
suspicious than the BADA55-VPR-224 procedure?

There's a "BADA55" in the BADA55-VPR-224 output, but a real attack along
the same lines wouldn't have anything obvious. Meanwhile the Brainpool
procedure has an embarrassing 26DC5C6CE94A4B44F330B5D9 overlap, which
you previously admitted was "unfortunate".

> But it is not ok to imply that the Brainpool curves could potentially
> have been designed with a backdoor built in.

The statement you're responding to is that the curve generator had the
flexibility to secretly choose from among more than 1000000 curves for
any particular prime. If the curve generator secretly knew a weakness in
just one of these >1000000 curves then the curve generator could have
chosen that curve.

You seem to think that the flexibility was somewhat less because (e.g.)
the public wouldn't have accepted cos(1). But this doesn't fundamentally
change the picture. I don't mean to exaggerate the risk here---note that
SafeCurves marks Brainpool's rigidity as an acceptable "mostly rigid"---
but I don't see how you can justify your claim of zero risk.

---Dan