Re: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

The way I see it (and I confess that I didn’t dive into this at all ;):

 
Security of randomized signatures depends on availability of a good RNG on the platform.
To mitigate the absence of a good reliable RNG, people defined deterministic signatures. 
Deterministic signatures appear vulnerable to side-channel attacks.
To mitigate these side-channel risks without re-introducing the need for a good RNG, “some” randomness is added.
 

So, to the Dan’s point – it’s  not a “reversal”, because it doesn’t expect a great RNG to be present. It merely hopes to get “some” randomness sufficient to mitigate side-channel attacks. While the “mostly” deterministic algorithm foils cryptographic attacks that exploit poor randomness.

 

Did I get it right? ;-)

 

From: Cfrg <[e-mail]> on behalf of Natanael <[e-mail]>
Date: Thursday, May 7, 2020 at 05:59
To: Dan Brown <[e-mail]>
Cc: CFRG <[e-mail]>, "[e-mail]" <[e-mail]>
Subject: Re: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

 

 

Den ons 6 maj 2020 19:49Dan Brown <[e-mail]> skrev:

It seems fine to adopt this, but a few things should be checked.

Procedurally, randomizing signatures is a *reversal* of CFRG consensus towards determinism, so maybe past discussions on CFRG are worth reviewing (I have forgotten the arguments). Maybe determinism proponents are too busy to check here, and should be briefly queried. 

>From my reading & in my layman's opinion, the primary goal of deterministic designs is to reduce the risk of bad entropy sources breaking the system. So it wouldn't be too much of a change of course when the goal is to increase robustness of the use of entropy, IMHO. But acknowledging the change makes sense. 

 

I wonder if some applications of signatures now rely on non-standard, off-label properties of signatures, e.g. determinism (or non-determinism for older applications).  (Non-standard here means something 

different from Goldwasser-Micali-Rivest unforgeability against adaptive chosen message attacks.)  For example, maybe EdDSA is somewhere being used like a verifiable hash?  (Ok, any verifier reliance on determinism is probably insecure, because the signer switch over to non-determinism.)

 

There's a separate class of functions called VRF (verifiable random functions) that should be used if what you need specifically is something that is equivalent to reliably deterministic signatures. 

 

I've seen cryptocurrency projects rely on assumptions of deterministic signatures and getting attacked because of it, but these designs were flawed from the start and probably shouldn't be catered to. People making assumptions like this needs to verify if the algorithm / implementation actually provides those properties before using them. It would be much better in cases like this to explicitly explain which properties are provided and which aren't, so that flawed choices like this aren't made by implementors in the first place. 

 

Should we continue to name these “deterministic” signatures, if the plan is to make them non-deterministic? 

How about message-dependent signatures, since both components of the signature (R,S) will depend on the message? Or message-keyed, to emphase that R must depend on M, not just S.  (Multi-word phrases have precedents, I am reminded of nonce-misuse resistance, thought does not fit here.)

 

I'm reminded of the term "ciphertext stealing" from the XTS cipher mode. The signature (it parts of it) always was message dependent, but maybe "entropy stealing" or similar phrasing could be used since we take secret randomness from additional sources to make the signature algorithm more robust. 

 

Maybe a more neutral term like "entropy combining" would work better. "Entropy combining signatures".