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

Dan Brown <dbrown@certicom.com> Wed, 31 December 2014 15:44 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 546551A00E9 for <cfrg@ietfa.amsl.com>; Wed, 31 Dec 2014 07:44:30 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=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 I3GX-5zzYyUB for <cfrg@ietfa.amsl.com>; Wed, 31 Dec 2014 07:44:28 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id CB2601A00CD for <cfrg@irtf.org>; Wed, 31 Dec 2014 07:44:27 -0800 (PST)
Received: from xct107cnc.rim.net ([10.65.161.207]) by mhs214cnc.rim.net with ESMTP/TLS/AES128-SHA; 31 Dec 2014 10:44:22 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT107CNC.rim.net ([fe80::b815:71ef:9f8f:e07c%16]) with mapi id 14.03.0210.002; Wed, 31 Dec 2014 10:44:21 -0500
From: Dan Brown <dbrown@certicom.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, Adam Langley <agl@imperialviolet.org>, Christoph Anton Mitterer <calestyo@scientia.net>
Thread-Topic: [Cfrg] malicious DH base points [was Re: should the CFRG really strive for consensus?]
Thread-Index: AdAlEKR+A6afVSjDUE2VN8MZfIEDUw==
Date: Wed, 31 Dec 2014 15:44:20 +0000
Message-ID: <20141231154418.6639764.33790.24403@certicom.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="===============1819635569=="
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/UZUE-nZyvhbp7NltRNzaXF5lUt4
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: Wed, 31 Dec 2014 15:44:30 -0000

Right, I should have said hypothetical rather possible (which can also be read as able).

So, under the paper's unlikely MDH hypothesis, a fast generator could be weak, or worse, an unexplained random-looking generator could be weak. To me, the best countermeasure to this hypothetical attack would be an explainable randomish base point. Or, one can just use the fastest base point, and argue this hypothesis is too unlikely to fret over.

Aside: I think X9.62-2005 added an option to have pseudorandom base points...

Best regards, 

-- Dan
From: Scott Fluhrer (sfluhrer)
Sent: Wednesday, December 31, 2014 10:30 AM
To: Dan Brown; Adam Langley; Christoph Anton Mitterer
Cc: cfrg@irtf.org
Subject: RE: [Cfrg] malicious DH base points [was Re: should the CFRG really strive for consensus?]

Actually, that paper doesn’t actually say “it’s possible to pick a malicious generator from a prime-sized group”.  Instead, it (actually, claim 9) says “if we knew of a generator/KDF pair which made deriving the shared secret easy, someone setting up the group could use that to select a random-looking generator that, with that KDF, contains a trap door that he could exploit”.
 
If anything, that paper can be construed to be an argument for a nonrandom-looking generator (because that doesn’t give anyone a chance to build in the above trap door).
 
 
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Dan Brown
Sent: Wednesday, December 31, 2014 10:07 AM
To: Adam Langley; Christoph Anton Mitterer
Cc: cfrg@irtf.org
Subject: [Cfrg] malicious DH base points [was Re: should the CFRG really strive for consensus?]
 
‎The paper talks about the possibility of malicious base points for DH:


Boaz Tsaban: Fast generators for the Diffie-Hellman key agreement protocol and malicious standards. IACR Cryptology ePrint Archive 2005: 231 (2005)
 
It may be far-fetched, but the paper seems to show that the independence of DH from the base point is ‎not quite a mathematical certainty, unless the paper has been refuted in further research. 
 
Best regards, 

-- Dan
From: Adam Langley
Sent: Wednesday, December 31, 2014 9:45 AM
To: Christoph Anton Mitterer
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] should the CFRG really strive for consensus?
 
On Dec 31, 2014 1:50 PM, "Christoph Anton Mitterer" <calestyo@scientia.net> wrote:
> I think it's really a bad idea for the CFRG to strive so much for
> consensus.

If you believe in the security of curve25519 then you also believe in the security of Microsoft's current position at ~128 bits. They have the same structure and thus strictly the same strength.

There's /no/ possibility of weakening anything, mathematically, with a different base point (in the correct subgroup) or by using an isogeny.

IRTF groups do not, technically, have to reach consensus. However, everyone does have to function on the same Internet at the end of the day.

Cheers

AGL