Subject: [saag] Recommendations Regarding Deterministic Signatures

From: John Mattsson <[email-masked]>
Date: Wed, 27 Nov 2019 11:13:55 +0000

IRTF/IETF has the last years heavily promoted purely deterministic signatures:

  RFC 8152 (EdDSA):
    "EdDSA signatures are deterministic."

  RFC 8152 and RFC8152bis (COSE): 
    "Implementations SHOULD use a deterministic version of ECDSA"

    "Note: Use of a deterministic signature technique is a good idea
     even when good random number generation exists."

  RFC 8446 (TLS 1.3)
    "It is RECOMMENDED that implementations implement "deterministic ECDSA""

NIST has just released FIPS 186-5 (Draft) where they plan to include deterministic ECDSA but does not recommend it in general due to side-channel and fault injection attacks:

  "recent security research has found that implementations of
   these deterministic signature algorithms may be vulnerable
   to certain kinds of side-channel or fault injection attacks."

  "The use of deterministic ECDSA may be desirable for devices
   that do not have a good source of quality random numbers." 

  https://www.federalregister.gov/documents/2019/10/31/2019-23742/request-for-comments-on-fips-186-5-and-sp-800-186

  https://csrc.nist.gov/publications/detail/fips/186/5/draft

Recent research papers on deterministic signatures:

  [1] https://eprint.iacr.org/2017/975
  [2] https://eprint.iacr.org/2017/1014
  [3] https://link.springer.com/chapter/10.1007/978-3-319-44524-3_11

Countermeasures discussed in both [1] and [2] is to add some "additional randomness" / "noise" to the deterministic calculation of 'k'.

My current view is that best practice seems to be to use deterministic algorithms (deterministic ECDSA or EdDSA) with "additional randomness" / "noise" like in XEdDSA. This also mitigates attacks on theoretical use cases where deterministically signing the same message twice leaks information.

https://signal.org/docs/specifications/xeddsa/

The additional randomness (and all other randomness) should be generated with a construction like draft-irtf-cfrg-randomness-improvements that feeds a pseudo random number generator with a random seed, a secret key, a context string, and a nonce.

For global companies like Ericsson that would like to be compliant with both RFCs and NIST publications, it would be good with alignment between IRTF/IETF/NIST.

Cheers,
John

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 27 Nov 2019 09:10:27 -0800

On Wed, Nov 27, 2019 at 3:14 AM John Mattsson <john.mattsson=
[email-masked]> wrote:

> My current view is that best practice seems to be to use deterministic
> algorithms (deterministic ECDSA or EdDSA) with "additional randomness" /
> "noise" like in XEdDSA.

I'll +1 this, but also noting that for existing deterministic signature
algorithms, one potential mitigation for fault injection attacks against
these algorithms (depending on whether circumstances / threat models permit
it) is verifying generated signatures before releasing them.

That doesn't help with the issue of leaking message equivalence, however
I'll also note that some applications of deterministic signatures I work on
personally benefit from the determinism from a fault-tolerance perspective,
as it allows for recomputing a signature on a message which may or may not
have been lost in a protocol where inconsistent signature generation in and
of itself is considered a fault.

-- 
Tony Arcieri

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 28 Nov 2019 11:38:01 -0800

> NIST has just released FIPS 186-5 (Draft) where they plan to include deterministic ECDSA but does not recommend it in general due to side-channel and fault injection attacks:

Can anyone comment on the relative weight that NIST gives to hardware vs.
software-only implementations?  My understanding is that these attacks can
be quite severe for hardware implementations.

> My current view is that best practice seems to be to use deterministic algorithms (deterministic ECDSA or EdDSA) with "additional randomness" / "noise" like in XEdDSA. This also mitigates attacks o…

This does seem like an attractive proposition on first inspection.

Thanks,

Ben