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

Dan Brown <dbrown@certicom.com> Fri, 15 August 2014 17:36 UTC

Return-Path: <dbrown@certicom.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 D062F1A0110 for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 10:36:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] 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 3fHkPCR1pxQ1 for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 10:36:06 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 4EBA51A0102 for <cfrg@irtf.org>; Fri, 15 Aug 2014 10:36:05 -0700 (PDT)
Received: from smtp-pop.rim.net (HELO XCT103CNC.rim.net) ([10.65.161.203]) by mhs213cnc.rim.net with ESMTP/TLS/AES128-SHA; 15 Aug 2014 13:36:01 -0400
Received: from XCT104CNC.rim.net (10.65.161.204) by XCT103CNC.rim.net (10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.174.1; Fri, 15 Aug 2014 13:36:01 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT104CNC.rim.net ([::1]) with mapi id 14.03.0174.001; Fri, 15 Aug 2014 13:36:01 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Progress on curve recommendations for TLS WG
Thread-Index: AQHPrSkVFDDUD0tW0keHIpwhcB27wpvR3EOAgAAXPgCAAB3vgIAAAdUAgAAk/YD//7820A==
Date: Fri, 15 Aug 2014 17:36:00 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5CCD05A@XMB116CNC.rim.net>
References: <20140801013659.11640.qmail@cr.yp.to> <53EDEB0D.9040304@secunet.com> <925e123f-d396-443f-9fc7-b1f6601bcd4c@email.android.com> <53EE17A9.7080408@secunet.com> <CACsn0c=eS-=6dapjrw07uEbxW0MHqn6=3caftfA6geZNOUcu9w@mail.gmail.com> <53EE3839.7010009@secunet.com>
In-Reply-To: <53EE3839.7010009@secunet.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_00FA_01CFB88D.DA119A80"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/yM35MNzxfjn6HJUE2GlzzZ5npek
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: Fri, 15 Aug 2014 17:36:11 -0000

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Johannes Merkle
> Sent: Friday, August 15, 2014 12:41 PM
> To: Watson Ladd
> Cc: cfrg@irtf.org
> Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
> 
> >>
> >> curve25519, but this would only introduce more unjustified discredit
> >> and
> > FUD.
> >>
> >
> 
> being straightforward. So we would arrive at an example that does not
really
> show anything but could be easily mistaken by someone with less insight
(e.g.
> the press) to wrongly conclude that the seed-less approach is generally
> suspicious.
> This FUD effect would be bad.
> 
> For this reason, I tried to appeal to stop this unfortunate discussion in
which
> contrived examples are used to discredit much more straightforward
> approaches, but unfortunately, my post seem to have stimulated it.
> 

I disagree with some of the points above.  So: 

Contrived examples are useful when abstractions get too numerous and
difficult and hard to compare. They can more efficient at conveying an idea,
in using fewer words.  I hope that the CFRG will not misunderstand the
contrivances, but rather try to see the points they demonstrate.  I agree
that contrivances may not be interesting to be engineering and the general
public, who are more concerned with the end results, but researchers should
be able to consider them if it is for the purposes of clarity.

Nobody will ever be able to fully resolve the possibility of secret attacks.
So rather than dismissing the possibility as FUD, we should try to do what
we can to minimize this threat.  That's the whole reason for being of the
disciplines of public cryptanalysis and of provable security.  If any time
somebody proposes an algorithm with no published attacks, then they should
not be able dismiss any criticisms by crying FUD, right?

CFRG are neither the press nor the end user. I expect CFRG to be able to
engage in technical discussions, without censuring itself because of
possible misunderstanding by non-technical.

My BARC example was merely meant to demonstrate that rigidity alone does not
support the security of Curve25519 against secret attacks.  Rather, if the
maturity of cryptanalysis suggests that all known attacks are public, then
Curve25519 is secure.  Or, perhaps maturity of public cryptanalysis only
suggests that any weak curve classes differ from the Pohlig--Hellman and MOV
weak classes in the sense that the secret class is only reachable by trying
multiple curves and we heuristically expect it to apply to all curves with
equal probability.  In fact, I already tried make this abstract argument
long ago on the TLS and CFRG lists: that one needs to assume that some
secret attack which Curve25519 can resists is an attack that affects all
curves with equally likelihood, which sounds like a plausible assumption,
and indeed is a weaker assumption than assuming no secret attacks. That
said, it is not true for the some of the known attacks, at least the PH and
MOV attacks.  I'm not sure if this abstract argument sounded believable, so
I provided the BARC example as a demonstration.  

The 56-bit secure y^2 = x^3 + x^2 + x variant of Curve25519 may perhaps only
demonstrate something vastly weaker abstract idea: that a rigid curve can be
weaker than expected curve just by a fluke, in other words, that bad luck is
possible.  I don't know enough to be completely sure whether this particular
example is much worse than average, or if it qualifies as a one-in-a-million
type of fluke.  Of course, once a random curve is selected, it can suffer
from bad luck too.  In the case of a fixed random curve, at least we can
form an argument about a priori probabilities.  So, that's why I'm saying
that this is a much weak abstract idea, because it hinges on the notion of a
priori probabilities.  Selecting random curves more often would be costly,
but would improve this particular aspect.

Best regards,

Dan