Re: [Cfrg] A downside of deterministic DL signatures?

Michael Hamburg <> Thu, 31 July 2014 07:40 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 4AE211A038A for <>; Thu, 31 Jul 2014 00:40:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 2.755
X-Spam-Level: **
X-Spam-Status: No, score=2.755 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, J_CHICKENPOX_12=0.6, J_CHICKENPOX_42=0.6, 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 4yPAOhNEZCGl for <>; Thu, 31 Jul 2014 00:40:24 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 11D871A0382 for <>; Thu, 31 Jul 2014 00:40:24 -0700 (PDT)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 30A583AA12; Thu, 31 Jul 2014 00:40:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1406792405; bh=FOMkEPdXWoGL7lsSgUxQbQjeAP5hpyCj4q5rvtEvYPU=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=EiHJsq1p1eNeurqPW8qnsH3rDD3QYgeoYPnB7sd3ph7+XO6A5Xw+TQ88QR+ASuWJc pa81XtYpmGH6MWwIOXHgjj95igUHpHS5+71MUUoKpw1tEpRszhfTqbc5DHCmQJzEFf D6W4vMfKcOJvOsX/sZVnutsHN6mE43WQetCfm3dw=
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1971.5\))
From: Michael Hamburg <>
In-Reply-To: <>
Date: Thu, 31 Jul 2014 00:40:18 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <>
To: Tony Arcieri <>
X-Mailer: Apple Mail (2.1971.5)
Cc: Dan Brown <>, IRTF Crypto Forum Research Group <>
Subject: Re: [Cfrg] A downside of deterministic DL signatures?
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: Thu, 31 Jul 2014 07:40:25 -0000

> On Jul 30, 2014, at 6:38 PM, Tony Arcieri <> wrote:
> From a technical perspective, yes. From an objective perspective: it is extremely dangerous and has lead to multiple key compromises *in practice*, including the PS3 master key.

Indeed.  But collision attacks have also broken signature schemes *in practice*, for example the Flame malware.

You can have any two of determinism, one-pass signatures, and protection from collision attacks.  So far as I know, you can’t have all three, at least not with a Schnorr scheme.  Please correct me if I’m wrong.

The collision protection comes from the order things are passed to the hash function during signing/verification and deterministic nonce generation (i.e. H(pk || nonce || message) resp HMAC(sk, message)), so if we are going to have it in a given scheme, it will be a mandatory part of the spec.

Determinism isn’t part of the verification algorithm or the message format.  It just affects nonce generation.  So it could be a SHOULD, or it could be a MUST if the committee feels strongly that it should be required.

If it’s a MUST, it follows that implementors MUST NOT provide a streaming API for signatures.  This means that they can’t sign messages that come in on a pipe without unbounded buffering, and they can’t sign messages that don’t fit in the memory of your (possibly constrained) device.

Should a signature scheme declare that it MUST NOT be implemented with a streaming API, even though it’s possible to do that securely?  Or should we drop protection from collision attacks?  How much confidence do you have in SHA3?  Or am I missing a way to get all of these?

— Mike