Curve x448 has wrong order value

[polhenarejos]

Summary

When curve x448 is loaded via mbedtls_ecp_group_load, the N value is wrong. Instead of being set to 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d is set to 2^446 + 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d (note sign), giving another different number.

It does not seem to break anything important, since curve x448 does not use N for arithmetics (EdDSA does!), but in any case, it takes a wrong value. This is produced because mbedtls_ecp_group_load frees the mpi and the bit sign is not set up later.

System information

Mbed TLS version (number or commit id): 2d89b40
Operating system and version: all
Configuration (if not default, please attach mbedtls_config.h): default
Compiler and options (if you used a pre-built binary, please indicate how you obtained it): just make
Additional environment information:

Expected behavior

N should be 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

Actual behavior

N is 2^446 + 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

Steps to reproduce

#include "common.h"
#include "mbedtls/private_access.h"

#include "mbedtls/build_info.h"
#include "mbedtls/ecp.h"

#define DEBUG_BUF(p,s) { \
    printf("Payload %s (%d bytes):\r\n", #p,(int)s);\
    for (int i = 0; i < s; i += 16) {\
        for (int j = 0; j < 16; j++) {\
            if (j < s-i) printf("%02x ",(p)[i+j]);\
            else printf("   ");\
            if (j == 7) printf(" ");\
            } \
            printf("\r\n");\
        } printf("\r\n"); \
    }

int main() 
{
    int ret; 
    mbedtls_ecp_group grp;
    mbedtls_mpi N, Ns;
    uint8_t bf[56];
    static const unsigned char curve448_part_of_n[] = {
        0x83, 0x35, 0xDC, 0x16, 0x3B, 0xB1, 0x24,
        0xB6, 0x51, 0x29, 0xC9, 0x6F, 0xDE, 0x93,
        0x3D, 0x8D, 0x72, 0x3A, 0x70, 0xAA, 0xDC,
        0x87, 0x3D, 0x6D, 0x54, 0xA7, 0xBB, 0x0D,
    };
    
    mbedtls_mpi_init( &N );
    mbedtls_mpi_init( &Ns );
    mbedtls_ecp_group_init( &grp );
    
    /* N = 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d */
    MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &N, 446, 1 ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &Ns,
                        curve448_part_of_n, sizeof( curve448_part_of_n ) ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &N, &N, &Ns ) );
    
    MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_CURVE448 ) );
    
    printf( "Are equal? %s\n\n", mbedtls_mpi_cmp_mpi( &N, &grp.N ) == 0 ? "YES!" : "Oh no... :(" );

    mbedtls_mpi_write_binary( &grp.N, bf, sizeof( bf ) );
    DEBUG_BUF( bf, sizeof( bf ) );
    mbedtls_mpi_write_binary( &N, bf, sizeof( bf ) );
    DEBUG_BUF( bf, sizeof( bf ) );
    cleanup:
    mbedtls_mpi_free( &N );
    mbedtls_mpi_free( &Ns );
    return 0;
}

Additional information

[hanno-becker]

I think this is a bug in mbedtls_ecp_group_load(): In incorrectly zeroizes the group via mbedtls_ecp_group_free() at the beginning, which corrupts the MPIs by clearing their sign-bit to the invalid value of 0. This is an artifact of the (annoying) fact that initialization != zeroization for MPIs. The symptom here is due to mbedtls_mpi_sub_mpi() interpreting s==0 as s==-1, thus adding instead of subtracting. ISTM that the right fix would be to expand mbedtls_ecp_group_free() into mbedtls_ecp_group_free(); mbedtls_ecp_group_init() at the beginning of mbedtls_ecp_group_load().

[polhenarejos]

That's the point. Actually it "affects" to all curves, since ecp_group_load() calls ecp_group_free(). Fortunately, many curves use ecp_mpi_load() which set X-> = 1 explicitly or mbedtls_mpi_lset() (curve25519), which also sets X-> = 1, and the bug is "masked". But this is not the case for curve448 and theres when the bug is visible.
mbedtls_ecp_group_init() is not even called at any place in ecp_curves.c, where the curves are loaded. I agree that the most effective solution is to call mbedtls_group_init() after the group is freed. I'll update the PR.

[tom-cosgrove-arm]

Note: the "needs: backports" is to let us know that the backport needs to be reviewed and approved