Re: [Cfrg] Schnorr just as vulnerable to bad RNG

Michael Hamburg <> Fri, 25 July 2014 17:49 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id D18871A03F1 for <>; Fri, 25 Jul 2014 10:49:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id iKKHiM1r3YjM for <>; Fri, 25 Jul 2014 10:49:32 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2518D1A03ED for <>; Fri, 25 Jul 2014 10:49:31 -0700 (PDT)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id B88243AA13; Fri, 25 Jul 2014 10:47:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1406310446; bh=C5DkFcan2YB3IDx+hXdtayUXiEqp8jRT2bR7d55KqUM=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=daGVGDzwkE4B5P700x29nymLNe/Lf9hq9n05G+i92xQUd5fYn4Kon0R0NO5nyGeeq bskIvD7pgvvvmbNTGyjMJVY1k7Kz4T4l0FakXXtuDKI72qyLS6XK/I9tiBZtqijmv8 Wqa+NTEBPuT2oprpgrZ470HS2MyKc2DQYoixT+kE=
Content-Type: multipart/alternative; boundary="Apple-Mail=_8A30548B-9BCC-425D-AE0B-71A4BB749F3C"
Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
From: Michael Hamburg <>
In-Reply-To: <>
Date: Fri, 25 Jul 2014 10:49:28 -0700
Message-Id: <>
References: <>
To: Dan Brown <>
X-Mailer: Apple Mail (2.1878.6)
Cc: "" <>
Subject: Re: [Cfrg] Schnorr just as vulnerable to bad RNG
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 25 Jul 2014 17:49:34 -0000

Bringing in the results of a discussion from the curves list.  I think when generating signatures of short messages, the most conservative strategy is to use a PRF with a secret key, a random number, and the message.

That way if your RNG breaks, unless it’s malicious and omniscient*, at worst it will leak that a message has been repeated.  If your RNG doesn’t break and your PRF isn’t terrible, it will ensure that the nonce is unbiased and that repeated messages aren’t evident.

Some people on the curves list favor PRF(message) xor random(), but it’s more vulnerable to a broken RNG.

Schnorr doesn’t add anything to this or take anything away.  It’s just easier to implement securely because it doesn’t have that pesky inversion mod the group order, and it has a slightly better security argument.

— Mike

* Some people care about a model where a malicious RNG is trying to leak your key by influencing the ultimate output of the algorithm.  It’s more of a concern with nonces.

On Jul 25, 2014, at 6:17 AM, Dan Brown <> wrote:

> ‎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
> _______________________________________________
> Cfrg mailing list