ECDSA algorithms – Digital Signatures
9.4.3 ECDSA algorithms
The ECDSA algorithms ecdsa˙secp256r1˙sha256, ecdsa˙secp384r1˙sha384 as well as ecdsa˙secp521r1˙sha512 are defined in the American National Standards Institute (ANSI) X9.62 standard [6]. The corresponding elliptic curves are defined in the ANSI X9.62 and FIPS 186-4 [128] standards, and the hash functions are defined in the FIPS 180-4 standard [129].
We already learned how ECDSA works in principle earlier in this chapter. The ECDSA algorithm instances supported in TLS 1.3 are merely variations based on specific elliptic curves, secp256r1, secp384r1, and secp521r1, and the specific hash functions, SHA-256, SHA-384, and SHA-512, respectively.
The ECDSA digital signature scheme was originally proposed by the Canadian mathematician and cryptographer Scott Vanstone in 1992 in response to NIST’s initial DSS proposal.
In 1998, ECDSA was accepted as International Standards Organization (ISO) standard 14888-3. One year later, it was accepted as ANSI standard X9.62. Finally, in the year 2000, ECDSA was accepted as Institute of Electrical and Electronics Engineers (IEEE) standard 1363-2000 and FIPS standard 186-2 [91].
The ANSI X9.62 standard contains instructions for generating the elliptic curve to be used with ECDSA verifiably at random. This is crucial for the trustworthiness of any cryptographic algorithm based on elliptic curves. Without this property, Eve could undermine the algorithm’s security by joining the standardization process and proposing a weak elliptic curve for which she knows a secret attack.
To ensure an elliptic curve was generated at random, X9.62 describes a procedure where the domain parameters of the curve are outputs of a cryptographic hash function, namely SHA-1. The input to the hash function serves as proof that the elliptic curve was indeed generated at random.
Another argument that has been put forward for generating curves verifiably at random concerns future cryptanalytic advances in elliptic curves. If, so the argument goes, there are rare classes of weak elliptic curves that will be discovered by cryptanalysts in the future, the likelihood that such a curve would be generated at random is very low.
Today, the SHA-1 hash function is no longer secure. However, even replacing it with a cryptographically secure alternative, such as SHA-512, does not provide any serious security guarantees in the age of cloud computing where computing resources are available in abundance, at least if one is willing to pay the corresponding bill. With enough computational power at hand, Eve could simply hash random inputs and generate elliptic curves using the hash function’s output as domain parameters until she finds a weak curve.
Consequently, the fact that Alice and Bob can verify the domain parameters of an elliptic curve to be the output of a cryptographic hash function applied to some input does not, in itself, guarantee that the curve is secure. In addition, the choice of the input must be rigid: the argument for choosing that specific input must be as simple as possible [22].
Unfortunately, renowned cryptographers are skeptical about the security of the ECDSA algorithms ecdsa˙secp256r1˙sha256, ecdsa˙secp384r1˙sha384, and ecdsa˙secp521r1˙sha512 included in the TLS 1.3 standard because the NIST curves secp256r1, secp384r1, and secp521r1 were not generated in a rigid process.
Dan Bernstein refers to these NIST curves as manipulatable [22] because their generation process uses a large unexplained input and, as a result, Eve has a large number of possible curves to choose from.
To illustrate this, Bernstein provides a hypothetical example where the procedure for generating a curve takes the equation y2 = x3 − 3x + h(s), with s being a large random seed and h being a cryptographic hash function. Regardless of how strong h is, Eve can run the generation process for a large number of values for s and check each resulting curve y2 = x3 − 3x + h(s) for vulnerability to the secret attack known to Eve. Given today’s computing resources, this would work even if only one curve in a billion is susceptible to Eve’s secret attack [22].