Invalid ECDSA signature and public key for private key that is curve order

[guidovranken]

#include <symcrypt.h>
#include <symcrypt_low_level.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
#define CF_CHECK_NE(expr, res) if ( (expr) == (res) ) { goto end; }

void SymCryptFatal(UINT32 fatalCode) {
    (void)fatalCode;

    abort();
}
PVOID SymCryptCallbackAlloc( SIZE_T nBytes ) {
    return malloc(nBytes);
}

VOID SymCryptCallbackFree( VOID * pMem ) {
    free(pMem);
}
SYMCRYPT_CPU_FEATURES
SymCryptCpuFeaturesNeverPresent(void) {
    return 0;
}
SYMCRYPT_ERROR SymCryptCallbackRandom(PBYTE out, SIZE_T size) {
    for (size_t i = 0; i < size; i++) {
        out[i] = rand();
    }
    return SYMCRYPT_NO_ERROR;
}

int main(void)
{
    SYMCRYPT_ECURVE* curve = NULL;
    SYMCRYPT_ECKEY* key = NULL;
    SYMCRYPT_INT* nonce = NULL;

    CF_CHECK_NE(curve = SymCryptEcurveAllocate(SymCryptEcurveParamsNumsP256t1, 0), NULL);
    CF_CHECK_NE(key = SymCryptEckeyAllocate(curve), NULL);
    CF_CHECK_NE(nonce = SymCryptIntAllocate(SymCryptEcurveDigitsofScalarMultiplier(curve)), NULL);
    {
        const uint8_t nonce_bytes[] = {0x0C, 0x0B, 0xF3, 0xED, 0xBA, 31, 78, 0xE3, 0x8E};
        CF_CHECK_EQ(SymCryptIntSetValue(nonce_bytes, sizeof(nonce_bytes), SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, nonce), SYMCRYPT_NO_ERROR);
    }

    {
        const uint8_t priv_bytes[] = {
            0x3F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
            0xFF, 0xFF, 0xFF, 0xFF, 0xBE, 0x6A, 0xA5, 0x5A, 0xD0, 0xA6, 0xBC, 0x64,
            0xE5, 0xB8, 0x4E, 0x6F, 0x11, 0x22, 0xB4, 0xAD};
        CF_CHECK_EQ(SymCryptEckeySetValue(
                priv_bytes, sizeof(priv_bytes),
                NULL, 0,
                SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, SYMCRYPT_ECPOINT_FORMAT_XY,
                0, key), SYMCRYPT_NO_ERROR);
    }

    {
        const size_t sigHalfSize = SymCryptEcurveSizeofScalarMultiplier(curve);
        const size_t sigSize = sigHalfSize * 2;
        uint8_t sig_bytes[sigSize];

        CF_CHECK_EQ(SymCryptEcDsaSignEx(
                    key,
                    NULL,
                    0,
                    nonce,
                    SYMCRYPT_NUMBER_FORMAT_MSB_FIRST,
                    0,
                    sig_bytes,
                    sigSize), SYMCRYPT_NO_ERROR);

        const size_t pubSize = SymCryptEckeySizeofPublicKey(key, SYMCRYPT_ECPOINT_FORMAT_XY);

        const size_t pubHalfSize = pubSize / 2;
        uint8_t pub_bytes[pubSize];

        CF_CHECK_EQ(SymCryptEckeyGetValue(
                    key,
                    NULL, 0,
                    pub_bytes, pubSize,
                    SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, SYMCRYPT_ECPOINT_FORMAT_XY,
                    0), SYMCRYPT_NO_ERROR);

        printf("Pub X:\n");
        for (size_t i = 0; i < pubHalfSize; i++) {
            printf("%02X ", pub_bytes[i]);
        }
        printf("\n");

        printf("Pub Y:\n");
        for (size_t i = 0; i < pubHalfSize; i++) {
            printf("%02X ", pub_bytes[pubHalfSize+i]);
        }
        printf("\n");

        printf("Sig R:\n");
        for (size_t i = 0; i < sigHalfSize; i++) {
            printf("%02X ", sig_bytes[i]);
        }
        printf("\n");

        printf("Sig S:\n");
        for (size_t i = 0; i < sigHalfSize; i++) {
            printf("%02X ", sig_bytes[sigHalfSize+i]);
        }
        printf("\n");
    }

end:
    if ( key ) {
        /* noret */ SymCryptEckeyFree(key);
    }
    if ( curve ) {
        /* noret */ SymCryptEcurveFree(curve);
    }
    if ( nonce ) {
        /* noret */ SymCryptIntFree(nonce);
    }

    return 0;
}

Pub X is 1, Pub Y is 0, Sig S is 0.

Found by Cryptofuzz running on OSS-Fuzz.

[mlindgren]

@samuel-lee-msft, is this fixed with your recent changes?

[samuel-lee-msft]

Yes, @guidovranken, this should be resolved since https://github.com/microsoft/SymCrypt/commit/2829fe90fb846be49c17b503b278691b31e53664 - we now reject attempts to set a Private key of this form (0 modulo the curve's subgroup order) in the SymCryptEckeySetValue call.

I'll close this issue for now, but do let me know if you have further concerns on this!