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

Watson Ladd <watsonbladd@gmail.com> Sat, 03 January 2015 22:24 UTC

Return-Path: <watsonbladd@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 066081A875C for <cfrg@ietfa.amsl.com>; Sat, 3 Jan 2015 14:24:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-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 gjKm1GXrzNl6 for <cfrg@ietfa.amsl.com>; Sat, 3 Jan 2015 14:24:35 -0800 (PST)
Received: from mail-yh0-x22f.google.com (mail-yh0-x22f.google.com [IPv6:2607:f8b0:4002:c01::22f]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6A0821A6F30 for <cfrg@irtf.org>; Sat, 3 Jan 2015 14:24:35 -0800 (PST)
Received: by mail-yh0-f47.google.com with SMTP id f73so9638716yha.6 for <cfrg@irtf.org>; Sat, 03 Jan 2015 14:24:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=19dkMF7dWM/00KHDzjVJ2/K22a3py4fp2vlzPpxq4cE=; b=f3m+qfOLc98n82j8Ug81e7Grvm/s47lkGRRPVdeSKtCWNc+Gp4KcEMSB6sf0K0g30s t6VxZS06//Ej+LJeD1jInY9bXJUX7av19JRh6pi9hDZSWOaG92OXCigGSAqO+LOgnabW qrHGlOpKP20R4Sy21FM4r0eHB4vV0FVn8sN3HLhaznO91Q6Jl4kb5zqjjARl5zPOKlML vU5IErT/4mO7oTsvz6sTmQI0sNjGh5kpsTPpX7wP3neSQiO2n/lAgIv0hUAqocHGJeGk 5J38w7OeLWEpSEI95JK3ePJy61RYf69EdKfP/Se68qExMF9kDb8mofklM+GSRAkU8Kxe 21Kg==
MIME-Version: 1.0
X-Received: by 10.236.30.168 with SMTP id k28mr37481293yha.163.1420323874612; Sat, 03 Jan 2015 14:24:34 -0800 (PST)
Received: by 10.170.207.6 with HTTP; Sat, 3 Jan 2015 14:24:34 -0800 (PST)
In-Reply-To: <CALqxMTG86KinerYYDABeKy=OwDqPOXyxmZ7tvP-evgz0Qd55Mg@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>
Date: Sat, 3 Jan 2015 17:24:34 -0500
Message-ID: <CACsn0c=2EAgBi391yakqi_4Y_Kewz9+Ky+KWPmktP1DMzdn8Eg@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Adam Back <adam@cypherspace.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/oBJV7In5MpC8h2BIz19XUZ96TII
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:24:38 -0000

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