edgecase_datafeed2322021-11-17
This is the date at the time of creation of this datafeed article. A checkpoint article containing a hash of this datafeed article may be created on this date or at a later date.215102021-04-10bitcoinfe062b308ad6254b71ae4af5bbe8ec485105ebb9ae9cf1b905b115f596dd827a6786071HtwyqFWNVDoSEVqZwjBRRAV2oEsi8aQXr13MfGs39pR5aEK4iKdoLjVYXKwi6Y3uyPq1Hdv9WprSk5ugh12TpsLvEt6tfdSmnz1SGECDSA_Deterministic_Signingnicholas_piano_22021-09-19yes
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
hyperlinkhttp://github.com/tlsfuzzer/python-ecdsa/blob/c7b5e063447e5d67acc61ec35d9521fa0fce7a24/src/ecdsa/keys.py#L1346-L1407github.com/tlsfuzzer/python-ecdsa/blob/c7b5e063447e5d67acc61ec35d9521fa0fce7a24/src/ecdsa/keys.py#L1346-L1407hyperlinkhttp://medium.com/@simonwarta/signature-determinism-for-blockchain-developers-dbd84865a93emedium.com/@simonwarta/signature-determinism-for-blockchain-developers-dbd84865a93ehyperlinkhttp://datatracker.ietf.org/doc/html/rfc6979datatracker.ietf.org/doc/html/rfc6979hyperlinkhttp://billatnapier.medium.com/ecdsa-weakness-where-nonces-are-reused-2be63856a01abillatnapier.medium.com/ecdsa-weakness-where-nonces-are-reused-2be63856a01a
iQIcBAABAgAGBQJhiYWRAAoJED8P6ID17071OwMP/AuN5weoG0YGH1R8Kc3S2cPm
h46prD5yL/96l3bBLrV9QwU4sa3c3aaBGiwDOt/EkLzDS65Q38uAubcjR5T7Jq7M
PDG0BRLluTskJPw2ZY0h/petLxTngdSeOAfip4RN45xpoEn6M6DNyIbj2+VTKgfi
hseS1ljFwpwfoQIpDM3OKr69iFwy0Dpnm8FgV0qZ34J4hnFhAIeOMZrYrzjrquUk
nZ7fLMTK9dZJcsdElGXqt1GLhBXr41paydz9XNaQwXG4vu58tbXIwmkrk4GX/ujv
Eh6UfpD70Uo+od3T8boPtgGOJxZ1HeqP8SSAvKWs0LqHBj6BFjGLO0EhZO4KCxB1
YckeweEBCyAqA864zRTZLGSAuxPt7Kq2OGQU0Qjsxistul/n6VwlxGz1lmRCEsoF
BIOjCnxaXXeg60o3VQ9YoPKVf2kBLskM0J2SZ9TbVYzXtMC/GuH0S8JRkc8xAM0d
aUHyqREhjkOIzWgzdEKwiIu2XNcnUiS/I8y+h4T+eep0qWzJdrnuA87bddhZiDEI
eRZ56F3hoBDXEgjbQ0NZ9Hs3x8Igz5jbctIddRDw7bNCMPJgy2n+0W5ihZeFKwMl
0em9i0aL/rbnAjy6r/NKeVZMMDcjTEWgILXp6NOpAEwEs8I+FyfyhVKVIklkBokT
yL9AmoWclGrnTo72rKae
=jNP4
iQIcBAABCgAGBQJhlSOLAAoJECL1OzZgiBhw5wgP/AywPV7IPrHZ9YdXCKv/cvAB
02DtdVqGpHGoTNIExoVCWdqMa2k0iNEDSI33znnVFJagjNcjPY7ECsFLZoxq5TdZ
9UUwzVT9TiJghHMYjB4QktAp7y5+Ne5iYa2N0QUqRQzE2Zw4TVLQXiVkLT1k2OpP
AqDAYCXMhsN2zVjFX/8lp3u7m0/VE8VdLVeoj1b/z1S8JkgYe+sfxU0vk5OhG46F
DgifJOwx2/Ud91OKGnk0wA/z5yVNEy0Q8X5ZIC/v3cHx2l1X7LU/gUCwq+JywqVo
7JjMMmK8mjMN3Dm/iMjP4lFNLzryqjFwHFVi3aVmk7gWzkNVqBAE80YpkwarTEqR
LSuDinV4KuyqKBakFIw5FMwJTa2mCDIvbmcxsxVlVI2Z5T4d9UY3xj552918hx1d
P9Cv5cIY+nrZj2Gki2RyX63QKxNMcFuytlgHgTc3x6ZsrPq//D9RADf429/o0oMz
BOQ5l1nrxCepuY895Y6dWF3GCwKlMzkz6XUFWItI8Q+oOh6ZXfyG2yP3CrKRXGsV
9Bwd9Vw+ENNvx/mxVsQdJBU1mf1UQ50KMqgo9F9rtZL/KPzNuwzVOEt0YVMsdrSw
sJUulX36fabk7Zdf/gE6Ojq2w4Jwi15kG/fZEHWMU2vI19c2qdFQXE3ah4YxYsIl
pbOjB7k1robnCTqcqIGE
=BYFg