ECDSA: Elliptic Curve Signatures

The ECDSA (Elliptic Curve Digital Signature Algorithm) is a cryptographically secure digital signature scheme, based on the elliptic-curve cryptography (ECC). ECDSA relies on the math of the cyclic groups of elliptic curves over finite fields and on the difficulty of the ECDLP problem (elliptic-curve discrete logarithm problem). The ECDSA sign / verify algorithm relies on EC point multiplication and works as described below. ECDSA keys and signatures are shorter than in RSA for the same security level. A 256-bit ECDSA signature has the same security strength like 3072-bit RSA signature. ECDSA uses cryptographic elliptic curves (EC) over finite fields in the classical Weierstrass form.

These curves are described by their EC domain parameters, specified by various cryptographic standards such as SECG: SEC 2. Elliptic curves, used in cryptography, define:

Generator point G, used for scalar multiplication on the curve (multiply integer by ECpoint)
Order n of the subgroup of EC points, generated by G, which defines the length of the private keys (e.g. 256 bits)

For example, the 256-bit elliptic curve secp256r1 has:

Order n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 (prime number)
Generator point G {x = 48439561293906451759052585252797914202762949526041747995844080717082404635286, y =36134250956749795798585127919587881956611106672985015071877198253568414405109}

Key Generation

The ECDSA key-pair consists of:

private key (integer): privKey
public key (EC point): pubKey = privKey * G

The private key is generated as a random integer in the range [0...n-1]. The public key pubKey is a point on the elliptic curve, calculated by the EC point multiplication: pubKey = privKey * G (the private key, multiplied by the generator point G).

The public key EC point {x, y} can be compressed to just one of the coordinates + 1 bit (parity).

For the secp256r1 curve, the private key is 256-bit integer (32 bytes) and the compressed public key is 257-bit integer (~ 33 bytes).

Signing

The ECDSA signing algorithm (RFC 6979) takes as input a message msg + a private key privKey and produces as output a signature, which consists of a pair of integers {r, s}. The ECDSA signing algorithm is based on the ElGamal signature scheme and works as follows (with minor simplifications):

Calculate the message hash, using a cryptographic hash function like SHA-256: h = hash(msg)
Generate securely a random number k in the range [1..n-1]

In the case of deterministic-ECDSA, the value k is HMAC-derived from h + privKey (see RFC 6979)

Calculate the random point R = k * G and take its x-coordinate: r = R.x
Calculate the signature proof: s = k−1 ∗ (h+r ∗ privKey)(modn)

The modular inverse k−1(modn) is an integer, such that k ∗ k−1≡1(modn)

Return the signature {r, s}.

The calculated signature {r, s} is a pair of integers, each in the range [1...n-1]. It encodes the random point R = k * G, along with a proof s, confirming that the signer knows the message h and the private key privKey. The proof s is by idea verifiable using the corresponding pubKey. ECDSA signatures are 2 times longer than the signer's private key for the curve used during the signing process. For example, for 256-bit elliptic curves (like secp256r1) the ECDSA signature is 512 bits (64 bytes) and for 521-bit curves (like secp521r1) the signature is 1042 bits.

Verify Signature

The algorithm to verify a ECDSA signature takes as input the signed message msg + the signature {r, s} produced from the signing algorithm + the public key pubKey, corresponding to the signer's private key. The output is boolean value: valid or invalid signature. The ECDSA signature verify algorithm works as follows (with minor simplifications):

Calculate the message hash, with the same cryptographic hash function used during the signing: h = hash(msg)
Calculate the modular inverse of the signature proof: s1 = s−1(modn)
Recover the random point used during the signing: R' = (h * s1) * G + (r * s1) * pubKey
Take from R' its x-coordinate: r' = R'.x
Calculate the signature validation result by comparing whether r' == r

The general idea of the signature verification is to recover the point R' using the public key and check whether it is the same point R, generated randomly during the signing process.

How Does it Work?

The ECDSA signature {r, s} has the following simple explanation:

The signing signing encodes a random point R (represented by its x-coordinate only)

through elliptic-curve transformations using the private key privKey and the message hash h into a number s, which is the proof that the message signer knows the private key privKey.

The signature {r, s} cannot reveal the private key due to the difficulty of the ECDLP

problem.

The signature verification decodes the proof number s from the signature back to its original point R, using the public key pubKey and the message hash h and compares the x-coordinate of the recovered R with the r value from the signature.

Public Key Recovery from Signature

It is important to know that the ECDSA signature scheme allows the public key to be recovered from the signed message together with the signature. The recovery process is based on some mathematical computations (described in the SECG: SEC 1 standard) and returns 0, 1 or 2 possible EC points that are valid public keys, corresponding to the signature. To avoid this ambiguity, some ECDSA implementations add one additional bit v to the signature during the signing process and it takes the form {r, s, v}. From this extended ECDSA signature {r, s, v} + the signed message, the signer's public key can be restored with confidence.

The public key recovery from the ECDSA signature is very useful in bandwidth-constrained or storage-constrained environments (such as blockchain systems), when transmission or storage of the public keys cannot be afforded. For example, the Ethereum blockchain uses extended signatures {r,s, v} for the signed transactions on the chain to save storage and bandwidth.

Public key recovery is possible for signatures, based on the ElGamal signature scheme (such as DSA and ECDSA).

Signature malleability

For any message hash there are two valid signatures. It is possible to calculate the second valid signature with the private key, just by knowing the first signature, which is public. One can take any transaction, flip the s value from s to n - s, flip the v value ( 27 -> 28, 28 -> 27), and the resulting signature would still be valid.

Therefore allowing transactions with any s value with 0 < s < n, opens a transaction malleability concern. This is not a serious security flaw, especially since Ethereum uses addresses and not transaction hashes as the input to an ether value transfer or other transaction, but all Ethereum nodes, including Besu, will only allow signatures where s <= n/2 . This makes sure that only one of the two possible valid signatures will be accepted. As any ECDSA library, that is not focused on Blockchains (e.g. libcrypto from OpenSSL), will not take this constraint into consideration, any created signature has to be normalized after the creation of the signature to fit the above mentioned criteria.

Implementation in Besu

The elliptic curve signature is made available in Besu via the interface org.hyperledger.besu.crypto.SignatureAlgorithm. It is injected in various places across the different modules. There are two classes that implement the interface:

org.hyperledger.besu.crypto.SECP256K1
org.hyperledger.besu.crypto.SECP256R1

As the names of the classes suggest, they implement the SECP256K1 or SECP256R1 signature algorithms. SECP256K1 is the default signature algorithm, as it is used in Ethereum Mainnet and all public testnets. SECP256R1 has been added as an alternative for private networks as it is NIST compliant while SECP256K1 is not.

The only difference between SECP256K1 and SECP256R1 is the curve parameters of their respective elliptic curves. Therefore all calculations are exactly the same, only the input parameters are different. Because of this, the class org.hyperledger.besu.crypto.AbstractSECP256 contains all the logic of the ECDSA calculations and the classes SECP256K1 and SECP256R1 are extending it.

Native library

Because of performance reasons an implementation of the SECP256R signature algorithm has been created in C, as an addition to the Java implementation. The repository can be found at: https://github.com/ConsenSys/besu-native-ec

The library uses libcrypto from OpenSSL which contains all necessary functionality for the ECDSA signature algorithm. The functions for signing and verifying the signature are directly provided by libcrypto. The public key recovery is implemented using the elliptic curve operations provided by libcrypto.

Debugging the library

For debugging the library gdb can be used. A basic tutorial for gdb can be found here: gdb tutorial

It needs an executable in order to work. The tests can be used for this purpose, as they are executables. They are in the directory build and have the file extension out.

To debug for example the tests for signing it would be started with:

gdb build/test_ec_sign.out

Testing for memory leaks

In C the memory management is a responsibility of the developer. Therefore it can happen easily that memory leaks are introduced. The pipeline in the repository is testing for it, to avoid that any memory leaks are introduced in the code.

To test for them locally valgrind can be used. As gdb it needs an executable as well. Therefore the test can be used here as well.

For example to test the tests for signing for memory leaks the following command can be used:

valgrind --leak-check=full build/test_ec_sign.out

If a memory leak is detected an error similar to the following is displayed

==586133==
==586133== 26,780 (2,280 direct, 24,500 indirect) bytes in 15 blocks are definitely lost in loss record 64 of 64
==586133== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==586133== by 0x4A086AD: CRYPTO_zalloc (in /home/daniel/projects/besu-native-ec/build/libs/libbesu_native_ec_crypto.so)
==586133== by 0x49EE8EB: EVP_PKEY_new (in /home/daniel/projects/besu-native-ec/build/libs/libbesu_native_ec_crypto.so)
==586133== by 0x49F3A3D: EVP_PKEY_fromdata (in /home/daniel/projects/besu-native-ec/build/libs/libbesu_native_ec_crypto.so)
==586133== by 0x10F567: create_key (ec_key.c:89)
==586133== by 0x10F73D: create_key_pair (ec_key.c:40)
==586133== by 0x10B483: sign (ec_sign.c:65)
==586133== by 0x10B6B9: p256_sign (ec_sign.c:36)
==586133== by 0x10AB7B: p256_sign_should_create_valid_signatures (test_ec_sign.c:44)
==586133== by 0x10ACF0: p256_sign_should_create_valid_signatures_from_sha224_hashes (test_ec_sign.c:76)
==586133== by 0x10F105: UnityDefaultTestRun (in /home/daniel/projects/besu-native-ec/build/test_ec_sign.out)
==586133== by 0x10A94B: main (test_ec_sign.c:118)
==586133==
==586133== LEAK SUMMARY:
==586133== definitely lost: 9,120 bytes in 60 blocks
==586133== indirectly lost: 95,600 bytes in 2,352 blocks
==586133== possibly lost: 0 bytes in 0 blocks
==586133== still reachable: 0 bytes in 0 blocks
==586133== suppressed: 0 bytes in 0 blocks
==586133==

The output has to be read starting at the bottom:

Lines 16 - 21 tell us that a memory leak has occurred and how many bytes have not been freed.

Line 14 is the starting point to the stack trace. It tells us that in line 7 that in the file ec_key.c in line 89 memory was allocated, by calling functions from the library besu_native_ec_crypto.so (see lines 4 -6). Because this has caused an error, it means that this allocated memory was never freed.

Now that we know where the memory leak occurs, we need to free the memory at the appropriate place. In almost all cases this will be at the end of the function which has the memory allocated or if the allocated memory is the return value at the end of the calling function.

Integration of the native library in Besu

The native library is integrated via another repository: https://github.com/hyperledger/besu-native

This repository uses JNA to create the bridge between the native library and Java. The corresponding code can be found here: https://github.com/hyperledger/besu-native/tree/main/secp256r1

The code calls the corresponding functions of the native library and converts the results to basic Java data types. Further it needs to convert the received parameters from the representation in Java to one that the native library expects.

Especially important are the functions convertToNonNegativeRepresentation and convertToNativeRepresentation. They are responsible for converting the signatures into the correct representation. The native library expects a big-endian encoded byte array which is always positive, while in Java byte arrays can be positive or negative. The leftmost bit of an byte array needs to be tested in order to verify if a conversion is needed or not.

Testing local versions of besu-native

For development it can be necessary to test a new version of a besu-native library. This can be done locally. The following steps are necessary:

Create a new jar file by executing in besu-native:

cd secp256r1 ../gradlew build

This creates a new jar file in secp256r1/build/libs

Create a directory for the jar file in besu:

mkdir libs

Copy the jar file from step 1 from besu-native to the newly created directory:

cp $BESU_NATIVE_DIR/secp256r1/build/libs/besu-native-secp256r1-$VERSION.jar $BESU_DIR/libs

Add the newly created directory as a Gradle repository in besu. Modify $BESU_DIR/build.gradle:

repositories {

// … flatDir {

dirs 'libs'

}

Add the dependency to the crypto module. Modify $BESU_DIR/crypto/build.gradle:

dependencies {

// …

api 'org.hyperledger.besu:secp256r1:$VERSION_OF_JAR_FILE'

}

In past occasions the gradle task checkLicenses was failing when a local jar file was added like this. To avoid the error the task has to be excluded:

// for example ./gradlew build -x checkLicenses

Adding an additional signature algorithm

The native library currently only supports SECP256R1, but it is prepared to be extended to allow other ECDSA signature algorithms. To extend it the following steps have to be taken:

The 3 new functions to sign, verify and recover the public key have to be defined in /src/besu_native_ec.h. They can be directly copied from the existing ones for SECP256R1 (P256) and only have to be renamed.
The public key recovery function, which was just defined, needs to be implemented in src/ec_key_recovery.c. The existing function p256_key_recovery can be copied. It calls the function key_recovery. The new function needs to set the correct parameters for curve_nidand curve_byte_length. The correct value for curve_nid can be found in the file openssl/obj_mac.h
The signing function, which was just defined, needs to be implemented in src/ec_sign.c. The existing function p256_sign can be copied. It calls the function sign. The new function needs to set the correct parameters for private_key_len, public_key_len, group_name and curve_nid. The parameter for curve_nid is the same as in the public key recovery function. The correct value for group_name can be found as well in openssl/obj_mac.h
The verification function, which was just defined, needs to be implemented in src/ec_verify.c. The existing function p256_verify can be copied. It calls the function verify. The new function needs to set the correct parameters for public_key_len,group_name and curve_nid. The parameters group_name and curve_nid are the same as in the signing function.

SECP256R1 support in 3rd party libraries

All Ethereum libraries support per default only SECP256K1 as this is the signature algorithm, which is used in the public Ethereum networks. The support for SECP256R1 is not existing and has to be added.

Web3J

In Web3J the support can be added by using a custom transaction manager. The transaction manager is responsible for decoding, signing and sending a transaction. Therefore replacing the signing functions to use SECP256R1 are sufficient to add basic support.

A working version has been already created here: https://github.com/daniel-iobuilders/besu-secp256r1-demo/tree/master/app/src/main/java/org/hyperledger/besu/secp256r1/demo/Web3jNist

To use the custom transaction manager it has to be provided as a parameter for the functions deploy and load.

Truffle

In Truffle transactions are handled by so- called providers. The standard provider for Truffle is called hdwallet-provider. It’s implementation can be found here: https://github.com/trufflesuite/truffle/tree/develop/packages/hdwallet-provider

To add functionality for SECP256R1, the hdwallet-provider could be used as a basis and the signing functions would need to be changed to use SECP256R1.

This newly created provider needs to be set in the network configuration in truffle-config.js

SECP256R1 Support