Re: [Cfrg] malicious DH base points [was Re: should the CFRG really strive for consensus?]

Adam Back <adam@cypherspace.org> Sat, 03 January 2015 22:52 UTC

Return-Path: <adam.back@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 3C8971A0390 for <cfrg@ietfa.amsl.com>; Sat, 3 Jan 2015 14:52:26 -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 6wz7FyPx2jBK for <cfrg@ietfa.amsl.com>; Sat, 3 Jan 2015 14:52:24 -0800 (PST)
Received: from mail-qg0-x236.google.com (mail-qg0-x236.google.com [IPv6:2607:f8b0:400d:c04::236]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6C3391A036D for <cfrg@irtf.org>; Sat, 3 Jan 2015 14:52:24 -0800 (PST)
Received: by mail-qg0-f54.google.com with SMTP id l89so14141232qgf.13 for <cfrg@irtf.org>; Sat, 03 Jan 2015 14:52:23 -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=gl7PX9rVdSa9qbORxAiiMdhl1nGY54bg84xFBrrEpgQ=; b=X+eLUOtVjYwm6l5XHEo+tGwbUfufx3HlU3vAdy7WcZEc4S3ujM4cJknk/S/AS7CvEn Cw3o3Sq/okZGFKVxtjLGMH6ynbEw+O4Wo642LO7j7K8+S4o0rw7FMq3LBsXIeupXmlmS P7rHt2Sll2nI73eX7iXHMJ9dEwwY5Oc5ZHfnMKz5kJo0EhI0sHzG/T9rVuHomWkgHvGC x0xTSFna0FV/racUptGKf9yTQxTEd4sE2unKtpF1yRoKmMTFKlAdGT7Mp9eXrsTKawY7 jFrQe0oUOtLb15+HuDzfYkHGzYhbjSbybfDvE4B35kR11HZFZ0orE+tunRIfIriB6slk ZIYQ==
MIME-Version: 1.0
X-Received: by 10.229.178.67 with SMTP id bl3mr134090713qcb.18.1420325543504; Sat, 03 Jan 2015 14:52:23 -0800 (PST)
Sender: adam.back@gmail.com
Received: by 10.96.189.10 with HTTP; Sat, 3 Jan 2015 14:52:23 -0800 (PST)
In-Reply-To: <CACsn0c=2EAgBi391yakqi_4Y_Kewz9+Ky+KWPmktP1DMzdn8Eg@mail.gmail.com>
References: <20141231154418.6639764.33790.24403@certicom.com> <D0C9CE59.3B14A%kenny.paterson@rhul.ac.uk> <CALqxMTHaBg-XRWpQiLN5zo11=b24q8OgE6g0X_7F2nbtS+6FnA@mail.gmail.com> <1420132477.4562.6.camel@scientia.net> <D0CDD192.3B6AB%kenny.paterson@rhul.ac.uk> <CALqxMTG86KinerYYDABeKy=OwDqPOXyxmZ7tvP-evgz0Qd55Mg@mail.gmail.com> <CACsn0c=2EAgBi391yakqi_4Y_Kewz9+Ky+KWPmktP1DMzdn8Eg@mail.gmail.com>
Date: Sat, 03 Jan 2015 23:52:23 +0100
X-Google-Sender-Auth: _y7dSsyojOwV9Z9SZCfRPumMT4c
Message-ID: <CALqxMTEDv1XEd-r63Z7eRauLiF4HopjGZzChkFf6Bs61z_5G=w@mail.gmail.com>
From: Adam Back <adam@cypherspace.org>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/7VnD9x5ehRTlXIxg1kjh95BRsQA
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] malicious DH base points [was Re: should the CFRG really strive for consensus?]
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, 03 Jan 2015 22:52:26 -0000

It can be possible to know the discrete log of 9 wrt H(9), if you
chose the curve to make it so.

You are assuming there is insufficient wriggle room in the rest of the
design to make this so, which is a weaker assumption.

Adam

On 3 January 2015 at 23:24, Watson Ladd <watsonbladd@gmail.com> wrote:
> On Sat, Jan 3, 2015 at 3:48 PM, Adam Back <adam@cypherspace.org> wrote:
>> On 3 January 2015 at 18:28, Paterson, Kenny <Kenny.Paterson@rhul.ac.uk> wrote:
>>>>On Thu, 2015-01-01 at 13:39 +0100, Adam Back wrote:
>>>>> Seems like on
>>>>> topic and to the point, not spam.
>>>
>>> And as Adam Langley and others have pointed out, no-one seriously
>>> believes that the choice of base point has any security impact (a more
>>> refined statement about this to which I can subscribe can be found at the
>>> bottom of the safecurves page here:
>>
>> Nevertheless I think it should be part of the NUMS generation.
>>
>> Apart from the academic paper which hypothesises a combined weakness
>> between the generator and the KDF for key-exchange (which again, is
>> NOT off-topic), there are situations where you need pairs of
>> generators which no one knows the discrete log of (for example like
>> EC_DBRG, a backdooring topic known to all; or u-prove/Brands
>> representation problem a DL/ECDL schnorr-extension attribute
>> certificate, which has multiple bases, probably there are other
>> examples)
>>
>> If those are mixed with the main base point which is chosen using
>> unexplained randomness, then it maybe that even if we use G (the main
>> and non-NUMS base) plus H which given its intended to demonstrate lack
>> of knowledge wrt to H, would be generated with NUMS, that still fails
>> because maybe the person who generated G chose it such that it is the
>> discrete log of H (or vice-versa -- its the same thing).
>>
>> I dont see what motive we can have for not NUMS the G parameter to for
>> the avoidance of doubt - its not as if there's a big cost to that.
>
> 9 is the minimal x coordinate that gives a prime order point on the
> Montgomery model of Curve25519. I just checked this a moment ago with
> PARI, so there is no reason to view the NUMS generator as more rigid.
>
> As for the two-generator protocols, I agree there are issues with how
> one would generate two generators. But I've not heard serious
> objections to using a hash function: it's the way that Certicom for
> instance, generated challenges for finding discrete logs, or the way
> that one would close the Dual_EC backdoor. It's true that the attack
> you mentioned is possible if we simply pick a generator, and then try
> to generate another point.
>
> Sincerely,
> Watson
>
>>
>> Adam
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
>
>
>
> --
> "Those who would give up Essential Liberty to purchase a little
> Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin