Mbed-TLS / mbedtls

An open source, portable, easy to use, readable and flexible TLS library, and reference implementation of the PSA Cryptography API. Releases are on a varying cadence, typically around 3 - 6 months between releases.
https://www.trustedfirmware.org/projects/mbed-tls/
Other
5.54k stars 2.6k forks source link

Valid inputs get rejected by Curve25519/Curve448 APIs #5965

Open ivq opened 2 years ago

ivq commented 2 years ago

Summary

mbedtls_ecp_mul() is rejecting legal input R that is used to store result of point multiplication on Curve25519/Curve448.

System information

Mbed TLS version: at least latest development branch is affected Operating system and version: Arch Linux x86-64 Configuration: default Compiler and options: cmake defaults

Expected behavior

mbedtls_ecp_mul() should not complain about its input R if it has been initialized.

Actual behavior

If X or Z coordinate of R has many limbs before calling mbedtls_ecp_mul(), R gets rejected with error code MBEDTLS_ERR_ECP_BAD_INPUT_DATA.

Steps to reproduce

int main()
{
    int ret;
    mbedtls_ecp_group grp;
    mbedtls_mpi d;
    mbedtls_ecp_point P;
    // A valid "private key" for both SECP256R1 and Curve25519
    const char *scalar_str = "79F0B0DF885989A8C269EC780174B761F49242C3FCC292CF0D623FA85A8DA3C8";
    mbedtls_entropy_context entropy;
    mbedtls_ctr_drbg_context ctr_drbg;

    mbedtls_ecp_group_init(&grp);
    mbedtls_mpi_init(&d);
    mbedtls_ecp_point_init(&P);
    mbedtls_entropy_init(&entropy);
    mbedtls_ctr_drbg_init(&ctr_drbg);

    MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_SECP256R1));
    MBEDTLS_MPI_CHK(mbedtls_ctr_drbg_seed(&ctr_drbg, mbedtls_entropy_func, &entropy, NULL, 0));
    MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&d, 16, scalar_str));
    // Do some calc to make P have many limbs in it
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &P, &d, &grp.G, mbedtls_entropy_func, &entropy));

    MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE25519));
    // P is clearly valid "initialized" input to mbedtls_ecp_mul()
    if ((ret = mbedtls_ecp_mul(&grp, &P, &d, &grp.G, mbedtls_entropy_func, &entropy))) {
        // But I got output: ecp mul failed on Curve25519, error code -0x4f80(MBEDTLS_ERR_ECP_BAD_INPUT_DATA)
        printf("ecp mul failed on Curve25519, error code -0x%x\n", -ret);
    }
cleanup:
    mbedtls_ecp_group_free(&grp);
    mbedtls_mpi_free(&d);
    mbedtls_ecp_point_free(&P);
    mbedtls_ctr_drbg_free(&ctr_drbg);
    mbedtls_entropy_free(&entropy);

    return 0;
}

Calling stack:

ecp_mod_p255 ecp_curves.c:5229
ecp_modp ecp.c:1052
mbedtls_mpi_mul_mod ecp.c:1099
ecp_double_add_mxz ecp.c:2470
ecp_mul_mxz ecp.c:2542
ecp_mul_restartable_internal ecp.c:2615
mbedtls_ecp_mul_restartable ecp.c:2653
mbedtls_ecp_mul ecp.c:2667
main main.cpp:53

Additional information

It seems that Short Weierstrass curves are not affected.

bensze01 commented 2 years ago

Reopening to track this issue - we will need to test the new implementation of bignum we are working on to see if the rewrite fixed this test case.