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

Andy Lutomirski <luto@amacapital.net> Fri, 15 August 2014 18:50 UTC

Return-Path: <luto@amacapital.net>
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 21CA71A02D6 for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 11:50:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.379
X-Spam-Level:
X-Spam-Status: No, score=-1.379 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, J_CHICKENPOX_14=0.6, RCVD_IN_DNSWL_LOW=-0.7, 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 2Da3WG-w7pNF for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 11:50:53 -0700 (PDT)
Received: from mail-la0-f47.google.com (mail-la0-f47.google.com [209.85.215.47]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C06881A0290 for <cfrg@irtf.org>; Fri, 15 Aug 2014 11:50:52 -0700 (PDT)
Received: by mail-la0-f47.google.com with SMTP id mc6so2573272lab.6 for <cfrg@irtf.org>; Fri, 15 Aug 2014 11:50:50 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=Qq8idpEAl/IJ5R0F/lD3+7Soi22eYBdHTOUNBrSZy9Q=; b=C6JxEym+qB5BV9Y5IKblQ9YT7VrRCkWpxt+6MNb3dDPngSw+im5gJSifbCDe3WzpAN +dAbaOmpMf0VrK8E//jsonVI6foDEPDkSc1BX32QOEeCESf1VKNAZyyV+EQs/MZONp8J LlpkrW2kFuAJtNzujAqYJdsxBVclAhxllXCoW8KD1Z7cKS4rf7K+HXHtR2rCXVxjllIy rUC8XY6oqJHmrCOIjSQiY2LIKQUCY2jwhCWXoqsvVk13f8O+zMaMd3V9WFsSqT++1FM/ LjFIGAPpF/8dcKbrnBgE2rZodXIr8IGTiubOshnNTPmVVYDWUfJKEG8i2s/NtXkgorF9 kZMg==
X-Gm-Message-State: ALoCoQlvCTJ8kMR+lUIZnumRPDMhCOoDNv/NC3PFfMs0E/XyEXu4EKUACnWImho10ffCFRs+UKFq
X-Received: by 10.152.25.170 with SMTP id d10mr13367964lag.37.1408128650905; Fri, 15 Aug 2014 11:50:50 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.152.36.106 with HTTP; Fri, 15 Aug 2014 11:50:30 -0700 (PDT)
In-Reply-To: <CACsn0cndH3hF-hvFFYnik2Bxs3+sm7ALHLTxSPCZNzJ1bLJMjg@mail.gmail.com>
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> <CACsn0c=hEwPPL_zrXnoXnWfQ6oQPE-U8P3mGCA3a7=djfXAAqw@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5CCD0ED@XMB116CNC.rim.net> <CACsn0cndH3hF-hvFFYnik2Bxs3+sm7ALHLTxSPCZNzJ1bLJMjg@mail.gmail.com>
From: Andy Lutomirski <luto@amacapital.net>
Date: Fri, 15 Aug 2014 11:50:30 -0700
Message-ID: <CALCETrV8_fRNq2gw8DNoWD7=k1aKff7+9R-SuXXf60i=qGgzGg@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/58jHZbdiwJDD15CO0T4dJcIWAWA
Cc: Dan Brown <dbrown@certicom.com>, "cfrg@irtf.org" <cfrg@irtf.org>
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 18:50:54 -0000

On Fri, Aug 15, 2014 at 11:23 AM, Watson Ladd <watsonbladd@gmail.com> wrote:
>
> On Aug 15, 2014 10:59 AM, "Dan Brown" <dbrown@certicom.com> wrote:
>>
>> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Watson Ladd
>> > The reason Dan Brown's example isn't convincing is that having only
>> > prime
>> > factors of not that small size is common.
>>
>> Right about it being common: Dickman's function says the chance of the
>> largest
>> prime factor of that size is about 15%.
>>
>> Wrong about it being unconvincing: the severity of the attack is what
>> matters,
>> not how common it is.  Why would anybody care whether it took six or
>> one-million trials to a find a weak 56-bit curve?
>
> What is it convincing of? If it takes 6 trials all randomly generated curves
> are likely to fail. If it's 1 in a million, then rigidity or lack thereof is
> more important to prevent underhandedness.
>
>>
>> Also, I assume that you are not referring to my BARC example, in which the
>> largest prime factor is two.   Maybe BARC is unconvincing for another
>> reason,
>> which is?
>
> The endomorphism ring was shockingly large, NUMS isn't a property of a curve
> but a generation method, etc. Really the only argument was supersingular
> curves, which I admit being mildly convinced by.
>

If CFRG is going to seriously consider random curves, can we at least
generate good random curves?  I don't think it's *that* hard.  Choose
a good algorithm to turn a seed into a curve, and then use something
like H(next week's top NY Times headline, next week's top Al-Jazeera
headline, next week's S&P 500 close, next week's weather, etc...).

The point being that there are lots of degrees of freedom this way,
but no one (not even the NSA) would be able to control enough of them
to select for any property of the curve.

--Andy