Background

The original implementation of DSA-type signature algorithms (including ECDSA) requires a random number that belongs to the same type of mathematical object as the private key (an element of GF(p), where p is a prime number). This random number must satisfy the following three properties:

• Randomness: It cannot be inferred solely from the signed data (hereinafter referred to as “payload”) and the generated signature.
• Confidentiality: It must not be leaked outside the signing process.
• Uniqueness: The random number must be different for different payloads.

Otherwise, an attacker could potentially deduce the private key from the payload and the signature.

If this random number comes from a flawed random number generator, ensuring randomness and uniqueness becomes difficult—an attacker might find patterns in the random number generator by collecting enough payload-signature pairs, thereby deducing the private key.

One solution to this problem is to deterministically derive this “random number” from the hash value of the private key and the payload using a one-way algorithm (such as a hash function or message authentication code). The involvement of the private key in the derivation process ensures properties 1 and 3, as long as the private key itself is not leaked. This method has been standardized as RFC 6979. Additionally, EdDSA does not use a random number generator at all; the “random number” used in the process is entirely deterministically derived from the hash values of the private key and the payload.

If it cannot be guaranteed that the random number generator is free of defects, any (EC)DSA implementation that does not comply with RFC 6979 may have the potential to leak the private key through the aforementioned issues.

The FIPS 186-5 published on February 3, 2023, includes deterministic ECDSA compliant with RFC 6979, as well as EdDSA and curves Ed25519 and Ed448. However, its historical versions explicitly specified the non-deterministic implementation of (EC)DSA. Therefore, to comply with the old regulations, many TLS libraries hesitate to implement deterministic ECDSA or choose to hide their implementation or not use it by default.

Validation

If an algorithm is deterministic (where all inputs are user-controllable and the output is uniquely determined by the inputs), then under the condition that the payload and private key remain unchanged, the generated signature should be exactly the same. Therefore, if an (EC)DSA implementation produces different signatures while the payload and private key remain constant, that implementation must not comply with RFC 6979. We have previously addressed methods for testing HSM whether they are determinisitic or not.

PKI certificate requests include signatures corresponding to the private key, and the payload does not contain a timestamp. Generally, the functions called are the same as those used in the TLS protocol, making them suitable for testing the determinism of the signature algorithm: by using the same auxiliary information to generate multiple certificate requests for the same private key, if the signature algorithm is deterministic, all generated certificate requests should be exactly the same.

To generate an ECDSA private key for testing, you can use GnuTLS Certtool:

$ certtool -p --ecc --outfile /path/to/test.key

You can add the –curve option to specify the elliptic curve to be used, such as –curve=secp521r1 (the default is SECP256R1).

Then, you can use various tools provided by TLS libraries to generate certificate requests for that private key and verify the results by calculating the hashes to ensure they are exactly the same.

Mbed-TLS

Mbed-TLS provides a simple tool for generating certificate requests. After compiling, you can test it with the following command (keeping the auxiliary information at default):

$ cert_req filename=/path/to/test.key

The generated certificate request file will be fixed as cert.req in the current directory.

By hashing, you can confirm that the contents of the generated certificate requests are exactly the same each time.

Analyzing the code reveals that Mbed-TLS uses mbedtls_pk_sign() to issue the certificate request, which is also used in the TLS protocol. Therefore, the process of generating ECDSA signatures during the execution of the TLS protocol in Mbed-TLS is also deterministic.

GnuTLS

The GnuTLS Certtool can be used to issue certificate requests, but it requires the auxiliary information to be written in a template file (see its Man page for the format); otherwise, manual input is needed:

$ certtool -q --template /path/to/test.tmpl --load-privkey /path/to/test.key --outfile /path/to/test.csr

If using an RSA private key, it can generate exactly the same certificate request each time. However, the certificate requests generated with an ECDSA private key are different each time, indicating that its ECDSA signature does not yet support RFC 6979.

Delving into the GnuTLS code and issues reveals that as early as version 3.6.10, GnuTLS provided support for RFC 6979 at the level of the general private key signing function gnutls_privkey_sign*(), as long as the GNUTLS_PRIVKEY_FLAG_REPRODUCIBLE flag is enabled when calling these functions. However, GnuTLS does not enable this flag when internally calling the function, resulting in the issuance of certificate requests and signing in the TLS protocol not using deterministic ECDSA.

Currently, there are requests for GnuTLS to allow the use of EdDSA and deterministic ECDSA in FIPS-compliant mode to meet FIPS 186-5.

OpenSSL

The 1st RFC6979 implementation of OpenSSL was in 2019, but it was not merged into the upstream until version 3.2 in 2022. In the command line, you can provide a minimal auxiliary information for testing:

$ openssl req -sha512 -new -subj "/CN=MyCSR" -key /path/to/test.key -out /path/to/test.key

If using an RSA private key, you can generate an identical certificate request, but the certificate requests generated with an ECDSA private key will be different each time. However, after compiling the latest version of OpenSSL from GitHub for testing, and adding the -sigopt nonce-type:1 option, the certificate requests generated with the ECDSA private key become identical.

Delving into the code, it can be seen that in the latest version of OpenSSL, the signing operations related to the private key type have been separated into the corresponding provider implementations. The (EC)DSA provider reads the signing option nonce-type, and when its value is set to 1, it uses an implementation that conforms to RFC 6979. Therefore, as long as the parameter is set to a certain (EC)DSA private key’s EVP_PKEY_CTX object using EVP_PKEY_CTX_ctrl_str(evp_pkey_ctx, “nonce-type”, “1”) in a program that uses the OpenSSL library, all (EC)DSA signing operations using that object will employ a deterministic implementation, provided that the private key comes from a file rather than an Engine.

openssl ecparam -genkey -name secp384r1 -out private.key
openssl dgst -sha256  -sign private.key -sigopt nonce-type:1 -out test.sig  test.data

Conclusion

The risk associated with cryptographic signatures is often overlooked by many organizations. Notably, Edwards-curve algorithms, such as Ed25519 and Ed448, are resistant to random oracle attacks in signature scheme, and is able to use the same key in encryption scheme by converting to algorithms like X25519. Similarly, typical elliptic curves (P256 to P521) used in encryption schemes are also not vulnerable to random oracle attacks. However, when using EC keys for digital signatures, caution is warranted, even with a trusted random number generator (TRNG). Our review of Hardware Security Modules (HSMs) a few years ago revealed that some cryptography products are exposed to this serious exploit vector, which can be more severe than individual vulnerabilities.