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

[Michael Hamburg <[e-mail]>]

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