ECDSA verification fails when the payload is all-bits-zero

[gilles-peskine-arm]

ECDSA verification (mbedtls_ecdsa_verify or mbedtls_ecdsa_read_signature) returns MBEDTLS_ERR_ECP_INVALID_KEY when the payload (which should be a hash) is all-bits zero. The curve is a short Weierstrass curve.

This is a corner case that shouldn't happen if the function is used properly, but I don't think it's right. I expect verification to succeed when the signature is the output of a signature generation with the matching private key.

The error is triggered with the following call stack:

mbedtls_mpi_cmp_int( d, 1 ) → -1 because d = 0
mbedtls_ecp_check_privkey
mbedtls_ecp_mul of ecp.c
mbedtls_ecp_mul_shortcuts
mbedtls_ecp_muladd
mbedtls_ecdsa_verify

In mbedtls_ecdsa_verify, u1 is zero, which causes mbedtls_ecp_muladd( grp, &R, &u1, &grp->G, &u2, Q ) to fail.

Code to reproduce, tested with Mbed TLS 2.11:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "mbedtls/ctr_drbg.h"
#include "mbedtls/ecdsa.h"
#include "mbedtls/entropy.h"
#include "mbedtls/error.h"
#include "mbedtls/pk.h"

#define CHECK( x )                                                      \
    do {                                                                \
        int CHECK__ret_ = ( x );                                        \
        if( CHECK__ret_ != 0 )                                          \
        {                                                               \
            char CHECK__error_[100];                                    \
            mbedtls_strerror( CHECK__ret_,                              \
                              CHECK__error_, sizeof( CHECK__error_ ) ); \
            printf( "%s -> %s\n", #x, CHECK__error_ );                  \
            exit( EXIT_FAILURE );                                       \
        }                                                               \
    } while( 0 )

/* tests/data_files/ec_256_prv.pem */
static const char ec_key_pem[] =
    "-----BEGIN EC PRIVATE KEY-----\n"
    "MHcCAQEEIEnJqMGMS4hWOMQxzx3xyZQTFgm1gNT9Q6DKsX2y8T7uoAoGCCqGSM49\n"
    "AwEHoUQDQgAEd3Jlb4FLOZJ51eHxeB+sbwmaPFyhsONTUYNLCLZeC1clkM2vj3aT\n"
    "YbzzSs/BHl4HToQmvd4Evm5lOUVElhfeRQ==\n"
    "-----END EC PRIVATE KEY-----\n";

int main( void )
{
    mbedtls_entropy_context entropy;
    mbedtls_ctr_drbg_context ctr_drbg;
    mbedtls_pk_context pk;
    unsigned char payload[32] = { 0 };
    unsigned char sig[MBEDTLS_ECDSA_MAX_LEN];
    size_t sig_len;

    mbedtls_entropy_init( &entropy );
    mbedtls_ctr_drbg_init( &ctr_drbg );
    mbedtls_pk_init( &pk );
    CHECK( mbedtls_ctr_drbg_seed( &ctr_drbg,
                                  mbedtls_entropy_func, &entropy,
                                  NULL, 0 ) );

    CHECK( mbedtls_pk_parse_key( &pk,
                                 (unsigned char *) ec_key_pem,
                                 strlen( ec_key_pem ) + 1,
                                 NULL, 0 ) );

    CHECK( mbedtls_ecdsa_write_signature( mbedtls_pk_ec( pk ),
                                          MBEDTLS_MD_SHA256,
                                          payload, sizeof( payload ),
                                          sig, &sig_len,
                                          mbedtls_ctr_drbg_random,
                                          &ctr_drbg ) );

    CHECK( mbedtls_ecdsa_read_signature( mbedtls_pk_ec( pk ),
                                         payload, sizeof( payload ),
                                         sig, sig_len ) );

    mbedtls_pk_free( &pk );
    mbedtls_ctr_drbg_free( &ctr_drbg );
    mbedtls_entropy_free( &entropy );

    return( EXIT_SUCCESS );
}

[mpg]

This is a corner case that shouldn't happen if the function is used properly, but I don't think it's right.

I agree. I think this could be easily solved by special-casing d == 0 in mbedtls_ecp_mul_shortcuts(), whose very purpose is to shortcut special cases.

The root of the issue is that in this corner-case of ECDSA, ecp_mul() happens to be a bit too defensive. I like ecp_mul() to be defensive in general, but fortunately ECDSA never calls it directly, so we have an appropriate layer to handle the mismatch in assumptions.

[ciarmcom]

ARM Internal Ref: IOTSSL-2377

[gilles-peskine-arm]

There's no fix available. ca45c35 is a workaround, not a fix.

[AleksanderGali]

Please, assign this task to me.