[Cfrg] Schnorr just as vulnerable to bad RNG

Dan Brown <dbrown@certicom.com> Fri, 25 July 2014 13:17 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 2D61D1A028A for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 06:17:45 -0700 (PDT)
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 FE3_rAzW7WhI for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 06:17:43 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id E46601A0250 for <cfrg@irtf.org>; Fri, 25 Jul 2014 06:17:42 -0700 (PDT)
Received: from xct107cnc.rim.net ([10.65.161.207]) by mhs213cnc.rim.net with ESMTP/TLS/AES128-SHA; 25 Jul 2014 09:17:41 -0400
Received: from XCT114CNC.rim.net (10.65.161.214) by XCT107CNC.rim.net (10.65.161.207) with Microsoft SMTP Server (TLS) id 14.3.174.1; Fri, 25 Jul 2014 09:17:39 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT114CNC.rim.net ([::1]) with mapi id 14.03.0174.001; Fri, 25 Jul 2014 09:17:38 -0400
From: Dan Brown <dbrown@certicom.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Schnorr just as vulnerable to bad RNG
Thread-Index: Ac+oCs6QZBW0IZyiTTSZYsiyVXkKCw==
Date: Fri, 25 Jul 2014 13:17:38 +0000
Message-ID: <20140725131738.6639765.60290.17138@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="===============1966393139=="
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/K-UhIP_nonLglY0-Y2pRjssTK1E
Subject: [Cfrg] Schnorr just as vulnerable to bad RNG
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, 25 Jul 2014 13:17:45 -0000

‎In the SAAG meeting yesterday, it was suggested that Schnorr signatures better resist bad RNG than ECDSA, citing a flawed ECDSA implementation. 

Just like (EC)DSA, if the ephemeral key is exposed or repeated, then the Schnorr static key is exposed, which then can lead to forgery.

So this one implementation failure is not a reason to prefer Schnorr signatures, as an algorithm. 

The importance of proper ephemeral key generation is why ANSI‎ X9.62-2005 for ECDSA added a requirement (not in the1998 version) that the ephemeral key be generated using HMAC DRBG and that it be properly seeded, or else use another ANSI approved RNG. The 1998 version instead said something like unique and unpredictable. 

Some people propose using deriving the ephemerals from the message and a long term key. This does not seem any better as an algorithm than the DRBG approach, provided the X9.62 algorithm is adhered to.

There's an RFC melding both these ideas, but that is trying fix something that is not broken, at the algorithm level.

If a flawed implementation uses a DRBG in compliance with X9.62-2005, but fails to update DRBG state fails between signed messages‎, then the signing key is leaked. If a flawed implementation opts to also use deterministic ephemeral keys for encryption, then repeated messages leak info via repeated ciphertexts.  So, standards should amply warn implementers if these pitfalls. 

So I think there are issues with ease of implementation, clarity of standards, and making standards  error resistant, but the algorithm security is not significant.

In theory, some security proofs, may give different assurances, depending on the determinism, but I'll defer that issue to future discussion. 

‎Procedurally, I think signature algorithm choice, and method to generate ephemerals is a CFRG issue, not a SAAG issue.

Best regards, 

-- Dan