nicholas_piano_2 2021-09-19 yes Introduction The ECDSA signature scheme requires fresh, high-quality entropy for each signature generation. This presents two problems: 1. The availability of a source of high-quality entropy for signing 2. The inability of automated tests to verify that a signature was created using sufficiently high-quality entropy The solution is to use a deterministic method of the producing the required entropy. That is, an entropy value that is a pure function of the data to be signed. The required value for each signing operation is commonly known as k. Firstly, non-deterministic ECDSA signing will be discussed, followed by the deterministic variant and some of its disadvantages. Non-deterministic signing Signature generation begins with a randomly chosen point on an elliptic curve. This point is calculated by using a random value k, starting from a known generator point G. The first part of the signature r is simply: r = kG This equation relies on elliptic curve arithmetic. r represents the x-coordinate of the resulting point on the curve. The second part of the signature s is calculated as follows: s = (k^-1) * (H(M) + r * secret) Where: 1. H(M) is the hash of the message M converted to an integer 2. secret is the secret key of the signer The concatenation of the two values r and s is the signature. Given two messages signed using the same secret key and the same nonce k (hence the same r), the secret key can be recovered as follows: h1 = H(M1) h2 = H(M2) secret = (s2 * h1 + s1 * h2) / [r * (s1 + s2)] It is therefore imperative that a different nonce k be used for each signature. Deterministic signing The objective of deterministic signing is to avoid the need to generate a new value k for each operation. In short, the means of doing this involves combining the secret key with the hash of the message, yielding a value that cannot be known unless the secret key is known. Note: This does provide less security than using a fresh value for k. 1 unknown highly-random value (the secret) is technically easier to guess than 2 unknown highly-random values (the secret and the random k value). Algorithm According to RFC6979, the steps to generate a value k from the message and secret are as follows: 1. Hash the message h1 = H(M) 2. Begin first initialisation of V and K parameters - Initialise V to all 1s equal to the length of the hash V = 0x01 0x01 0x01 ... 0x01 For SHA-256, this equates to 32 octets set to 1. - Initialise K to all 0s equal to the length of the hash K = 0x00 0x00 0x00 ... 0x00 3. Begin second initialisation - Set the value of K = HMAC_K(V || 0x00 || int2octets(secret) || bits2octets(h1)) Where: - HMAC_K is the HMAC function using the same hash as step (1) with key K - || denotes concatenation - Set the value of V = HMAC_K(V) 4. Begin third initialisation - Set the value of K = HMAC_K(V || 0x01 || int2octets(secret) || bits2octets(h1)) Only the second concatenation, 0x01 has changed. - Set the value of V = HMAC_K(V) 5. Begin main loop - Set T to an empty sequence such that the length of T is 0 - While length(T) \< length(secret): - V = HMAC_K(V) - T = T || V 6. Finally, k = bits2int(T) 7. If the value of k is not within the range [1, secret-1] (i.e. the value of r is 0), the following should be run: - K = HMAC_K(V || 0x00) - V = HMAC_K(V) - Return to step (4) It should be noted that, while possible, this scenario is vanishingly unlikely to occur. Conclusion The deterministic signing scheme can be used in place of the normal signing schema for ECDSA. Sources hyperlink http://github.com/tlsfuzzer/python-ecdsa/blob/c7b5e063447e5d67acc61ec35d9521fa0fce7a24/src/ecdsa/keys.py#L1346-L1407 github.com/tlsfuzzer/python-ecdsa/blob/c7b5e063447e5d67acc61ec35d9521fa0fce7a24/src/ecdsa/keys.py#L1346-L1407 hyperlink http://medium.com/@simonwarta/signature-determinism-for-blockchain-developers-dbd84865a93e medium.com/@simonwarta/signature-determinism-for-blockchain-developers-dbd84865a93e hyperlink http://datatracker.ietf.org/doc/html/rfc6979 datatracker.ietf.org/doc/html/rfc6979 hyperlink http://billatnapier.medium.com/ecdsa-weakness-where-nonces-are-reused-2be63856a01a billatnapier.medium.com/ecdsa-weakness-where-nonces-are-reused-2be63856a01a