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

From: Dan Brown <[email-masked]>
Date: Tue, 29 Jul 2014 20:58:47 +0000

‎In ECDSA or Schnorr, if the ephemeral private key k depends on the message bring signed, precomputation of kG, an efficiency advantage (reduced latency?), and possibly effective side channel countermeasure (harder to time precomputation), seems precluded. Not being an efficiency or side channel expert, I ask: Does this downside sound right?

If so, deterministic signatures ought to be a SHOULD or MAY, not a MUST (or none of the above, since thus is not an interoperability issue).

Best regards, 

-- Dan

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 29 Jul 2014 14:19:01 -0700

On Jul 29, 2014, at 1:58 PM, Dan Brown <[email-masked]> wrote:

> — Dan

Sound right to me.

-- Mike

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 29 Jul 2014 17:19:55 -0400

Right. I don't think that deterministic signatures should be required. I
think having the ephemeral scalar depend on the message is an (often
useful) implementation technique, but probably not something to be imposed
as a protocol variant in its own right.

Bodo

2014-07-29 16:58 GMT-04:00 Dan Brown <[email-masked]>:

> ‎In ECDSA or Schnorr, if the ephemeral private key k depends on the
> message bring signed, precomputation of kG, an efficiency advantage
> (reduced latency?), and possibly effective side channel countermeasure
> (harder to time precomputation), seems precluded. Not being an efficiency
> or side channel expert, I ask: Does this downside sound right?
>
> If so, deterministic signatures ought to be a SHOULD or MAY, not a MUST
> (or none of the above, since thus is not an interoperability issue).
>
> Best regards,
>
> -- Dan
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 29 Jul 2014 22:53:16 +0100

On 29 July 2014 21:58:47 BST, Dan Brown <[email-masked]> wrote:
>(harder to time precomputation), seems precluded. Not being an
>efficiency or side channel expert, I ask: Does this downside sound
>right?

On the other hand, deterministic signatures can have test vectors - a big win - and they don't need an RNG. Less baggage, less worry about implementation fingerprinting or even potential kleptography (although obviously you should always avoid black boxes too where that last one could be a risk!).

You also obviously have to store precomputed values around if you choose that (of course you have to keep the key around too, but you're probably not writing that as frequently).

Conversely, you may need to be careful about leaking lengths in deterministic forms like RFC 6979. (Moot if they're visible anyway, but still worthy of mention.)

Deterministic is the most sensible implementation choice. In fact, it's how you SHOULD do it, I think. But having a perfect RNG also works, so I wouldn't on balance make deterministic a MUST: but random k is the most hazardous choice overall, as you're just 2-4 predictable bits away from the precipice of disaster. (...if anyone chooses that route, scrutinise it.)

There's also the hybrid approach chosen by BoringSSL (and current LibReSSL), which depends on RNG and the message. No test vectors possible, but still a hedge against RNG imperfection.

- --
/akr

---

From: Robert Ransom <[email-masked]>
Date: Wed, 30 Jul 2014 12:30:26 -0700

On 7/29/14, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> On the other hand, deterministic signatures can have test vectors - a big
> win - and they don't need an RNG. Less baggage, less worry about
> implementation fingerprinting or even potential kleptography (although
> obviously you should always avoid black boxes too where that last one could
> be a risk!).

Exactly.  I would make deterministic signatures a MUST for any
interoperable long-term signing key, and make an interoperable
deterministic signature generation specification and interoperable
storage/transport format for the associated secret key material a must
for any signature scheme specification.

For *short-term* signing keys which will never be written to disk, it
may make sense to store a counter along with the secret key, and use
that to precompute ephemeral keys for non-deterministic signature
generation.  (I've considered this as part of a key-agreement
protocol.)  But I can't support this approach for any key which may be
written to disk, or which may need to be used in more than one
signature-generation implementation.

Robert Ransom

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 30 Jul 2014 13:18:29 -0700

> signature-generation implementation.

Why not make it a SHOULD in the signature standard, and then other standards can upgrade it to MUST if they don’t need low-latency or streaming signatures?

— Mike

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 30 Jul 2014 18:38:36 -0700

On Tue, Jul 29, 2014 at 1:58 PM, Dan Brown <[email-masked]> wrote:

> (harder to time precomputation), seems precluded.
>

Okay, so the argument is: efficiency. The counterargument is: private key
exposure, loss of all security, abandon all hope ye who enter here, etc.

 Does this downside sound right?

>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.

We can blame the cryptographic user for these mistakes, or we can blame the
standard for placing dubious objectives like efficiency ahead of security.

Relevant: http://cr.yp.to/talks/2012.08.08/slides.pdf

-- 
Tony Arcieri

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 31 Jul 2014 00:40:18 -0700

> On Jul 30, 2014, at 6:38 PM, Tony Arcieri <[email-masked]> 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

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 31 Jul 2014 10:08:58 -0700

On Thu, Jul 31, 2014 at 12:40 AM, Michael Hamburg <[email-masked]>
wrote:

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

Are there any other examples of collision attacks in the wild? Also note
this attack required a nationstate-level effort.

Attacks on bad nonces are comparatively common and relatively easy, e.g.
someone automated stealing of other's Bitcoins by detecting nonce reuse in
the BitCoin block chain:

https://bitcointalk.org/index.php?topic=271486.0

>  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.
>

I think you're correct

> Or should we drop protection from collision attacks?

Probably, unless there's evidence they're a real threat.

-- 
Tony Arcieri

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 31 Jul 2014 13:23:05 -0400

> this attack required a nationstate-level effort.

sure:

  http://www.win.tue.nl/hashclash/rogue-ca/

and other instances from the same group, including the cheeky:

  http://www.win.tue.nl/hashclash/Nostradamus/

neither of these required nationstate-level effort, and they date back
to 2008.

	--dkg

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 31 Jul 2014 14:09:02 -0700

On Thu, Jul 31, 2014 at 10:23 AM, Daniel Kahn Gillmor <[email-masked]

> neither of these required nationstate-level effort, and they date back

Okay, let me put it this way instead:

Collisions:

- Can be used to alter the content of individual messages
- This requires that the design of the hash function itself be broken

Bad nonces:

- Leak the private key which can then be used to forge as many messages as
you wish
- Can be the result of bad RNGs/implementation errata even if the algorithm
and the rest of its implementation is sound

Which is worse?

-- 
Tony Arcieri