mbedTLS ECDSA verification fails

Question

I am porting one ECC ECDSA verify library to mbedTLS to benefit from large pool of crypto functions and I'm at a point where after 2 nights, I'm not able to verify the signature. It works well with another lib of mine.

Test program, keys are generated with pycryptodome python library, using script below. It outputs private/public ECC keys and data in C array format, to be later easily used in the mbedTLS test application. There is also SHA256 of the input + signature of the hash signed with private key. Script does verify check which passes sucessfully.

import sys, random, base64, os, json
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Signature import DSS

# Generate random 512-bytes long array for raw data
#data_raw = bytes([random.randint(0, 255) for _ in range(512)])
data_raw = 'This is my input data'.encode('utf-8')
data_raw_hash = SHA256.new(data_raw)
data_raw_hash_digest = data_raw_hash.digest()

# Generate private/public key pair for ECC
key = ECC.generate(curve = 'secp256r1')
private_key = key.export_key(format = 'PEM', compress = True) # Export private key
public_key = key.public_key().export_key(format = 'PEM', compress = True) # Generate public key and export it
public_key_sec1_compressed = key.public_key().export_key(format = 'SEC1', compress = True) # Generate public key and export it
public_key_sec1_uncompressed = key.public_key().export_key(format = 'SEC1', compress = False) # Generate public key and export it

# Sign the hash of raw data with private key
signer = DSS.new(ECC.import_key(private_key), 'fips-186-3')
signature = signer.sign(data_raw_hash)

# Quick signature verification
try:
    DSS.new(ECC.import_key(public_key), 'fips-186-3').verify(data_raw_hash, signature)
    print('Verification is OK')
except:
    print('Signature verification failed')

# Write generated data to files
with open('keys/data_raw_input_array.txt', 'w') as f:               f.write(','.join([hex(i) for i in data_raw]))
with open('keys/data_raw_hash_digest_array.txt', 'w') as f:         f.write(','.join([hex(i) for i in data_raw_hash_digest]))
with open('keys/private.ec.key', 'w') as f:                         f.write(private_key)
with open('keys/public.ec.key', 'w') as f:                          f.write(public_key)
with open('keys/ecc_public_key_compressed_array.txt', 'w') as f:    f.write(','.join([hex(i) for i in public_key_sec1_compressed]))
with open('keys/ecc_public_key_uncompressed_array.txt', 'w') as f:  f.write(','.join([hex(i) for i in public_key_sec1_uncompressed]))
with open('keys/signature_array.txt', 'w') as f:                    f.write(','.join([hex(i) for i in signature]))  # Signature of the hash

Test data

These have been generated by python script

Private key:

-----BEGIN PRIVATE KEY-----
MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQg4WXhmOg/W4F6Rbzd
wYLWdtg6l1eGOutTRHkNF43r3JChRANCAAT9gr7JOiQ9ROCyMY6a66cAB2sGdDJs
i6TVtGkYE5jcymhNLSIN92YtMyLUmA6lEuP+pvfY9ksKZQAPOKcS2yLe
-----END PRIVATE KEY-----

Public key:

-----BEGIN PUBLIC KEY-----
MDkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDIgAC/YK+yTokPUTgsjGOmuunAAdrBnQy
bIuk1bRpGBOY3Mo=
-----END PUBLIC KEY-----

Compressed, 33-bytes long, ECC public key - first byte is 0x02. This one is used in my existing library:

0x2,0xfd,0x82,0xbe,0xc9,0x3a,0x24,0x3d,0x44,0xe0,0xb2,0x31,0x8e,0x9a,0xeb,0xa7,0x0,0x7,0x6b,0x6,0x74,0x32,0x6c,0x8b,0xa4,0xd5,0xb4,0x69,0x18,0x13,0x98,0xdc,0xca

Un-compressed, 65-bytes long, ECC public key - first byte is 0x04. This one is apparently required by mbedTLS:

0x4,0xfd,0x82,0xbe,0xc9,0x3a,0x24,0x3d,0x44,0xe0,0xb2,0x31,0x8e,0x9a,0xeb,0xa7,0x0,0x7,0x6b,0x6,0x74,0x32,0x6c,0x8b,0xa4,0xd5,0xb4,0x69,0x18,0x13,0x98,0xdc,0xca,0x68,0x4d,0x2d,0x22,0xd,0xf7,0x66,0x2d,0x33,0x22,0xd4,0x98,0xe,0xa5,0x12,0xe3,0xfe,0xa6,0xf7,0xd8,0xf6,0x4b,0xa,0x65,0x0,0xf,0x38,0xa7,0x12,0xdb,0x22,0xde

Input data in hex:

0x54,0x68,0x69,0x73,0x20,0x69,0x73,0x20,0x6d,0x79,0x20,0x69,0x6e,0x70,0x75,0x74,0x20,0x64,0x61,0x74,0x61

SHA-256 hash of the input data:

0xa7,0x3f,0x26,0xf4,0xa1,0xe4,0x61,0x61,0x0,0x1a,0x29,0xdf,0xd2,0xaf,0x7d,0xa,0x25,0x91,0xbb,0xcc,0x1f,0xbc,0xfb,0xdb,0x43,0xdb,0x57,0xf9,0x8d,0x94,0xeb,0x81

Signature of the hash of input data, signed with private key:

0xec,0x1b,0xc,0xab,0x7e,0x7f,0x95,0x3d,0x66,0x98,0xd5,0xdd,0xe1,0x53,0x70,0x2,0x58,0xd9,0x12,0xc7,0xa,0x10,0x78,0x85,0x61,0xb8,0xf8,0xc8,0x42,0x73,0xf4,0x6d,0x1b,0x97,0x75,0x7c,0x6f,0x8f,0x63,0x58,0x2,0xdc,0x31,0x85,0x23,0x77,0x62,0xd1,0x9b,0x2d,0x56,0xe9,0xd4,0xe1,0x34,0xeb,0x4f,0x91,0x45,0xa1,0x68,0x87,0x24,0x19

C test

Test is done under Windows environment, with GCC compiler. In the test, I add my existing code (using compressed SEC1 public key format) and mbedTLS code.

#include <stdio.h>
#include <string.h>
#include "ecc.h"
#include "sha3.h"
#include "aes.h"
#include "windows.h"

#include "mbedtls_config.h"
#include "mbedtls/ecdsa.h"
#include "mbedtls/aes.h"
#include "mbedtls/sha256.h"
#include "mbedtls/pk.h"

/* Raw input data*/
uint8_t data_raw_input[] = {
#include "keys/data_raw_input_array.txt"
};

/* SHA256 of raw input data */
const uint8_t data_raw_hash_digest[] = {
#include "keys/data_raw_hash_digest_array.txt"
};

/* Signature of hash of raw data with private key */
const uint8_t signature[] = {
#include "keys/signature_array.txt"
};

/* ECDSA public key - compressed binary */
const uint8_t ecc_public_key_compressed_bin[] = {
#include "keys/ecc_public_key_compressed_array.txt"
};

/* ECDSA public key - uncompressed binary */
const uint8_t ecc_public_key_uncompressed_bin[] = {
#include "keys/ecc_public_key_uncompressed_array.txt"
};

int
main(void) {
    volatile int res;
    mbedtls_ecdsa_context ctx;

    /* mbedTLS */
    printf("mbedTLS way start\r\n");
    mbedtls_ecdsa_init(&ctx);
    mbedtls_ecp_group_load(&ctx.private_grp, MBEDTLS_ECP_DP_SECP256R1);
    res = mbedtls_ecp_point_read_binary(&ctx.private_grp, &ctx.private_Q, ecc_public_key_uncompressed_bin,
                                        sizeof(ecc_public_key_uncompressed_bin));
    if (res != 0) {
        printf("ECP point read binary failed: %d\r\n", res);
    }

    res = mbedtls_ecdsa_read_signature(&ctx, data_raw_hash_digest, sizeof(data_raw_hash_digest), signature,
                                       sizeof(signature));
    if (res == 0) {
        printf("mbedTLS Verification is OK...\r\n");
    } else {
        printf("mbedTLS Verification failed...: %d\r\n", res);
    }
    printf("mbedTLS way end\r\n");

    /* Custom way... */
    if (ecdsa_verify(ecc_public_key_compressed_bin, data_raw_hash_digest, signature)) {
        printf("Custom ECDSA lib verification is OK\r\n");
    }
    return 0;
}

Test fails

mbedTLS way start
mbedTLS Verification failed...: -20450
mbedTLS way end
Custom ECDSA lib verification is OK

Code -20450 indicates invalid signature. I do not understand what is wrong - key loading with mbedTLS works well - verified with compiler.

Repl.IT code: https://replit.com/@TilenMajerle/mbedTLSplayroundecdsa?v=1

Conclusion

Following the great reply of @Topaco, below is the python scrript to generate inputs, and C implementation in mbedTLS for verification.

Python:

import sys, random, base64, os, json
from Crypto.PublicKey import ECC
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Signature import DSS

# Input string - make it 16 bytes aligned for future AES test
data_raw = 'This is my input data 0123456789'
data_raw_encoded = data_raw.encode('utf-8')

# Calculate SHA-256 hash option of it and get its digest
data_raw_hash = SHA256.new(data_raw_encoded)
data_raw_hash_digest = data_raw_hash.digest()

# Generate private/public key pair for ECC
# Use various formats for one curve -> PEM, compressed, uncompressed, ...
key = ECC.generate(curve = 'secp256r1')
private_key = key.export_key(format = 'PEM', compress = False) # Export private key
public_key = key.public_key().export_key(format = 'PEM', compress = False) # Generate public key and export it
public_key_sec1_compressed = key.public_key().export_key(format = 'SEC1', compress = True) # Generate public key and export it
public_key_sec1_uncompressed = key.public_key().export_key(format = 'SEC1', compress = False) # Generate public key and export it in uncompressed mode -> used by mbedTLS

# Sign the hash of raw data with private key
# Sign in P1363 format
print('Signature with P1363 format')
signer_p1363 = DSS.new(ECC.import_key(private_key), 'fips-186-3')
signature_p1363 = signer_p1363.sign(data_raw_hash)
print('signature _p1363', ''.join(['{:02X}'.format(i) for i in signature_p1363]))
print('len _p1363', len(signature_p1363))
# Sign in DER format - default for mbedTLS
print('Signature with DER format')
signer_der = DSS.new(ECC.import_key(private_key), 'fips-186-3', encoding = 'der')
signature_der = signer_der.sign(data_raw_hash)
print('signature _der', ''.join(['{:02X}'.format(i) for i in signature_der]))
print('len _der', len(signature_der))

# Quick signature verification
try:
    DSS.new(ECC.import_key(public_key), 'fips-186-3').verify(data_raw_hash, signature_p1363)
    print('Verification is OK - P1363')
except:
    print('Signature verification failed - P1363')
try:
    DSS.new(ECC.import_key(public_key), 'fips-186-3', encoding = 'der').verify(data_raw_hash, signature_der)
    print('Verification is OK - DER')
except:
    print('Signature verification failed - DER')

# Write generated data to files
with open('keys/data_raw_input_str.txt', 'w') as f:                 f.write(data_raw)
with open('keys/data_raw_input_array.txt', 'w') as f:               f.write(','.join([hex(i) for i in data_raw_encoded]))
with open('keys/data_raw_hash_digest_array.txt', 'w') as f:         f.write(','.join([hex(i) for i in data_raw_hash_digest]))
with open('keys/private.ec.key', 'w') as f:                         f.write(private_key)
with open('keys/public.ec.key', 'w') as f:                          f.write(public_key)
with open('keys/private.ec.oneline.key', 'w') as f:                 f.write('"' + str(private_key).replace('\n', '\\r\\n') + '"')
with open('keys/public.ec.oneline.key', 'w') as f:                  f.write('"' + str(public_key).replace('\n', '\\r\\n') + '"')
with open('keys/ecc_public_key_compressed_array.txt', 'w') as f:    f.write(','.join([hex(i) for i in public_key_sec1_compressed]))
with open('keys/ecc_public_key_uncompressed_array.txt', 'w') as f:  f.write(','.join([hex(i) for i in public_key_sec1_uncompressed]))
with open('keys/signature_der_array.txt', 'w') as f:                f.write(','.join([hex(i) for i in signature_der]))      # Signature of the hash
with open('keys/signature_p1363_array.txt', 'w') as f:              f.write(','.join([hex(i) for i in signature_p1363]))    # Signature of the hash

C implementation - mbedTLS v3.3

#include <stdio.h>
#include <string.h>
#include "windows.h"

#include "mbedtls_config.h"
#include "mbedtls/ecdsa.h"
#include "mbedtls/aes.h"
#include "mbedtls/sha256.h"
#include "mbedtls/pk.h"

/* Raw input data*/
const uint8_t data_raw_input[] = {
#include "keys/data_raw_input_array.txt"
};

/* SHA256 of raw input data */
const uint8_t data_raw_hash_digest[] = {
#include "keys/data_raw_hash_digest_array.txt"
};

/* Signature of hash of raw data with private key */
const uint8_t signature_der[] = {
#include "keys/signature_der_array.txt"
};
const uint8_t signature_p1363[] = {
#include "keys/signature_p1363_array.txt"
};

/* ECC public key - compressed binary */
const uint8_t ecc_public_key_compressed_bin[] = {
#include "keys/ecc_public_key_compressed_array.txt"
};

/* ECC public key - uncompressed binary */
const uint8_t ecc_public_key_uncompressed_bin[] = {
#include "keys/ecc_public_key_uncompressed_array.txt"
};

/* ECC public key full text */
const uint8_t ecc_public_key_text[] = {
#include "keys/public.ec.oneline.key"
};

/* ECC private key full text */
const uint8_t ecc_private_key_text[] = {
#include "keys/private.ec.oneline.key"
};

int
main(void) {
    volatile int res;
    mbedtls_ecdsa_context ecdsa_ctx;
    mbedtls_pk_context pubkey_ctx;

    /* Test HASH - calculate hash of raw data and compare with calculated one from python script */
    {
        uint8_t hash_calculated[32];

        printf("HASH SHA256 calculation\r\n");
        res = mbedtls_sha256(data_raw_input, sizeof(data_raw_input), hash_calculated, 0);
        printf("mbedtls_sha256: %d\r\n", res);
        if (memcmp(hash_calculated, data_raw_hash_digest, sizeof(hash_calculated)) == 0) {
            printf("Hash is equal\r\n");
        } else {
            printf("Hash does not match\r\n");
        }
        printf("-----\r\n");
    }

    /*
     * Public key cryphography playground shows different way of parsing
     * actual public key (DER format (string) or binary format) and 
     * different types of signature representation (DER or P1363).
     */

    /*
     * Read this SO post for details:
     *
     * https://stackoverflow.com/questions/75635019/mbedtls-ecdsa-verification-fails/75641568#
     */

    /* 
     * Public key format:   DER/PEM (String based public key, --- BEGIN PUBLIC KEY --- type of message)
     * Signature format :   DER     (70, 71 or 72 bytes long)
     */
    {
        mbedtls_pk_init(&pubkey_ctx);
        res = mbedtls_pk_parse_public_key(&pubkey_ctx, ecc_public_key_text, sizeof(ecc_public_key_text));
        printf("mbedtls_pk_parse_public_key: %d\r\n", res);
        res = mbedtls_pk_verify(&pubkey_ctx, MBEDTLS_MD_SHA256, data_raw_hash_digest, sizeof(data_raw_hash_digest),
                                signature_der, sizeof(signature_der));
        printf("mbedtls_pk_verify: %d\r\n", res);
        printf("-----\r\n");
    }

    /* 
     * Public key format:   binary  (65-bytes long, 0x04 as first byte)
     * Signature format :   DER     (70, 71 or 72 bytes long)
     */
    {
        printf("Public key - ECDSA verification with binary format\r\n");
        mbedtls_ecdsa_init(&ecdsa_ctx);
        mbedtls_ecp_group_load(&ecdsa_ctx.private_grp, MBEDTLS_ECP_DP_SECP256R1);
        res = mbedtls_ecp_point_read_binary(&ecdsa_ctx.private_grp, &ecdsa_ctx.private_Q,
                                            ecc_public_key_uncompressed_bin, sizeof(ecc_public_key_uncompressed_bin));
        printf("mbedtls_ecp_point_read_binary: %d\r\n", res);
        res = mbedtls_ecdsa_read_signature(&ecdsa_ctx, data_raw_hash_digest, sizeof(data_raw_hash_digest),
                                           signature_der, sizeof(signature_der));
        printf("mbedtls_ecdsa_read_signature: %d\r\n", res);
        printf("-----\r\n");
    }

    /* 
     * Public key format:   binary  (65-bytes long, 0x04 as first byte)
     * Signature format :   P1363   (64-bytes long, r|s)
     */
    {
#define SIGNATURE_LEN (sizeof(signature_p1363))

        /* Parse public key in binary format */
        printf("Parse public key in binary format\r\n");
        mbedtls_ecdsa_init(&ecdsa_ctx);
        mbedtls_ecp_group_load(&ecdsa_ctx.private_grp, MBEDTLS_ECP_DP_SECP256R1);
        res = mbedtls_ecp_point_read_binary(&ecdsa_ctx.private_grp, &ecdsa_ctx.private_Q,
                                            ecc_public_key_uncompressed_bin, sizeof(ecc_public_key_uncompressed_bin));
        printf("mbedtls_ecp_point_read_binary: %d\r\n", res);
        printf("-----\r\n");

        /* Now parse signature that is in P1363 format and run verification */
        printf("Parse signature in P1363 format to r and s big numbers\r\n");
        mbedtls_mpi r, s;
        mbedtls_mpi_init(&r);
        mbedtls_mpi_init(&s);
        mbedtls_mpi_read_binary(&r, signature_p1363, SIGNATURE_LEN / 2);
        mbedtls_mpi_read_binary(&s, signature_p1363 + SIGNATURE_LEN / 2, SIGNATURE_LEN / 2);

        res = mbedtls_ecdsa_verify(&ecdsa_ctx.private_grp, data_raw_hash_digest, sizeof(data_raw_hash_digest),
                                   &ecdsa_ctx.private_Q, &r, &s);
        printf("mbedtls_ecdsa_verify: %d\r\n", res);
        printf("-----\r\n");
        mbedtls_mpi_free(&r);
        mbedtls_mpi_free(&s);
#undef SIGNATURE_LEN
    }
    return 0;
}

Answer 1

mbedTLS expects signature in DER format -> 2 integer components, with first hex value starting with 0x30.

Python signer function must therefore be updated to

# From
signer = DSS.new(ECC.import_key(private_key), 'fips-186-3')

# To
signer = DSS.new(ECC.import_key(private_key), 'fips-186-3', encoding = 'der')

And we have success!

Answer 2

The cause of the problem has already been described in the posted answer: The Python and C code use different ECDSA signature formats (see here for more details on both formats).
In the Python code, the P1363 format (r|s) is used. In the C code, the mbedtls_ecdsa_read_signature() function requires the ASN.1/DER encoded signature.
As fix, the signature format in the Python code is changed from P1363 to ASN.1/DER by explicitly specifying the encoding in DSS.new() with encoding='der'.

Alternatively, the signature format can be kept in the Python code and the adaptation made in the C code. Since this might be interesting for future readers, I additionally post this way here. The adaptation in the C code is possible in two ways:

• Option 1: Mbed TLS provides the mbedtls_ecdsa_verify() function which accepts r and s as big numbers, allowing processing of the P1363 format:

  #include "mbedtls/ecdsa.h"
  
  ...
  // Convert rs to r and s big numbers (MPI/Bignum)
  size_t len_rs = sizeof(signature) / 2;
  mbedtls_mpi r;
  mbedtls_mpi_init(&r);
  mbedtls_mpi_read_binary(&r, signature, len_rs);
  mbedtls_mpi s;
  mbedtls_mpi_init(&s);
  mbedtls_mpi_read_binary(&s, signature + len_rs, len_rs);
  
  // Verify with mbedtls_ecdsa_verify
  res = mbedtls_ecdsa_verify(&ctx.private_grp, data_raw_hash_digest, sizeof(data_raw_hash_digest), &ctx.private_Q, &r, &s);
  ...
  

• Option 2: The ecdsa_signature_to_asn1() function can be used to convert the P1363 signature to an ASN.1/DER encoded signature, so that mbedtls_ecdsa_read_signature() can still be applied. ecdsa_signature_to_asn1() requires r and s as big numbers:

  #include "mbedtls/ecdsa.h"
  #include "mbedtls/asn1write.h"
  #include "mbedtls/error.h"
  
  ...
  // Convert rs to r and s big numbers (MPI/Bignum)
  size_t len_rs = sizeof(signature) / 2;
  mbedtls_mpi r;
  mbedtls_mpi_init(&r);
  mbedtls_mpi_read_binary(&r, signature, len_rs);
  mbedtls_mpi s;
  mbedtls_mpi_init(&s);
  mbedtls_mpi_read_binary(&s, signature + len_rs, len_rs);
  
  // Convert signature format from P1363 to ASN.1/DER 
  uint8_t signature_der[MBEDTLS_ECDSA_MAX_LEN];
  size_t sig_der_len;
  ecdsa_signature_to_asn1(&r, &s, signature_der, sizeof(signature_der), &sig_der_len);
  
  // Verify with mbedtls_ecdsa_read_signature
  res = mbedtls_ecdsa_read_signature(&ctx, data_raw_hash_digest, sizeof(data_raw_hash_digest), signature_der, sig_der_len);
  ...
  

  with

  int ecdsa_signature_to_asn1(const mbedtls_mpi* r, const mbedtls_mpi* s, unsigned char* sig, size_t sig_size, size_t* slen)
  {
      int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
      unsigned char buf[MBEDTLS_ECDSA_MAX_LEN] = { 0 };
      unsigned char* p = buf + sizeof(buf);
      size_t len = 0;
  
      MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, s));
      MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, r));
  
      MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_len(&p, buf, len));
      MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_tag(&p, buf, MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE));
  
      if (len > sig_size) {
          return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
      }
  
      memcpy(sig, p, len);
      *slen = len;
  
      return 0;
  }
  

  ecdsa_signature_to_asn1() is defined in ecdsa.c as static function (so a copy is to be used).