[Cfrg] Recommendations Regarding Deterministic Signatures

[John Mattsson <[e-mail]>]

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