openssl: X25519 Incorrect Key Exchange

While integrating the wycheproof tests into another project I stumbled across what appears to be an issue with the x86_64 assembly implementation for x25519. The following code works fine on OpenSSL 1.1.0 and early 1.1.1 betas, but fails after commit https://github.com/openssl/openssl/commit/0e5c8d566029a995d1fa23cac0f828c39519d97f (when the x25519 assembly is enabled). The tcId numbers in the code below can be correlated to the x25519 wycheproof vectors to see a bit more context.

Edit: This is reproducible on an Intel i7-6820HQ CPU

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <openssl/crypto.h>
#include <openssl/evp.h>
#include <openssl/x509.h>


int main(void) {
    OPENSSL_init();
    int res;
    int ret = 0;
    unsigned char *public[5];
    unsigned char *private[5];
    unsigned char *shared[5];
    /* pkcs8 prefix added to the private keys: 302e020100300506032b656e04220420 */
    /* tcId: 50 */
    public[0] = OPENSSL_hexstr2buf("f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f", NULL);
    private[0] = OPENSSL_hexstr2buf("302e020100300506032b656e04220420288796bc5aff4b81a37501757bc0753a3c21964790d38699308debc17a6eaf8d", NULL);
    shared[0] = OPENSSL_hexstr2buf("b4e0dd76da7b071728b61f856771aa356e57eda78a5b1655cc3820fb5f854c5c", NULL);
    /* tcId: 62 */
    public[1] = OPENSSL_hexstr2buf("f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", NULL);
    private[1] = OPENSSL_hexstr2buf("302e020100300506032b656e0422042060887b3dc72443026ebedbbbb70665f42b87add1440e7768fbd7e8e2ce5f639d", NULL);
    shared[1] = OPENSSL_hexstr2buf("38d6304c4a7e6d9f7959334fb5245bd2c754525d4c91db950206926234c1f633", NULL);
    /* tcId: 67 */
    public[2] = OPENSSL_hexstr2buf("0ab4e76380d84dde4f6833c58f2a9fb8f83bb0169b172be4b6e0592887741a36", NULL);
    private[2] = OPENSSL_hexstr2buf("302e020100300506032b656e04220420a0a4f130b98a5be4b1cedb7cb85584a3520e142d474dc9ccb909a073a976bf63", NULL);
    shared[2] = OPENSSL_hexstr2buf("0200000000000000000000000000000000000000000000000000000000000000", NULL);
    /* tcId: 68 */
    public[3] = OPENSSL_hexstr2buf("89e10d5701b4337d2d032181538b1064bd4084401ceca1fd12663a1959388000", NULL);
    private[3] = OPENSSL_hexstr2buf("302e020100300506032b656e04220420a0a4f130b98a5be4b1cedb7cb85584a3520e142d474dc9ccb909a073a976bf63", NULL);
    shared[3] = OPENSSL_hexstr2buf("0900000000000000000000000000000000000000000000000000000000000000", NULL);
    /* tcId: 69 */
    public[4] = OPENSSL_hexstr2buf("2b55d3aa4a8f80c8c0b2ae5f933e85af49beac36c2fa7394bab76c8933f8f81d", NULL);
    private[4] = OPENSSL_hexstr2buf("302e020100300506032b656e04220420a0a4f130b98a5be4b1cedb7cb85584a3520e142d474dc9ccb909a073a976bf63", NULL);
    shared[4] = OPENSSL_hexstr2buf("1000000000000000000000000000000000000000000000000000000000000000", NULL);
    for (int i=0; i < 5; i++) {
        printf("Iteration %d\n", i);
        EVP_PKEY *pkey = EVP_PKEY_new();
        assert(pkey != NULL);

        res = EVP_PKEY_set_type(pkey, NID_X25519);
        assert(res != 0);

        res = EVP_PKEY_set1_tls_encodedpoint(pkey, public[i], 32);
        assert(res != 0);

        BIO *private_bio = BIO_new_mem_buf(private[i], 48);
        assert(private_bio != NULL);

        EVP_PKEY *skey = d2i_PrivateKey_bio(private_bio, NULL);
        assert(skey != NULL);

        EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new(skey, NULL);
        assert(ctx != NULL);

        res = EVP_PKEY_derive_init(ctx);
        assert(res == 1);

        res = EVP_PKEY_derive_set_peer(ctx, pkey);
        assert(res == 1);

        size_t keylen = 32;
        unsigned char buf[32] = {0};
        res = EVP_PKEY_derive(ctx, buf, &keylen);
        assert(res == 1);
        res = memcmp(buf, shared[i], 32);
        if (res != 0) {
            printf("Shared key does not match expectation\n");
            printf("computed: %s\n", OPENSSL_buf2hexstr(buf, 32));
            printf("expected: %s\n", OPENSSL_buf2hexstr(shared[i], 32));
            ret = 1;
        } else {
            printf("Test case iteration %d passed\n", i);
        }
    }
    exit(ret);
}

(This test code obviously leaks memory like a sieve, but that doesn’t matter for this purpose)

About this issue

  • Original URL
  • State: closed
  • Created 6 years ago
  • Comments: 20 (20 by maintainers)

Most upvoted comments

x25519_fe64_sub fails, in particular, when subtracting 0xffff....ffff from 0. The result should be 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffb5 (modulo 2^256-38) but it is instead 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdb.

All of x25519_fe64_add, x25519_fe64_sub, and x25519_fe64_tobytes have problems. x25519_fe64_tobytes did not properly normalize every 256-bit integer to the appropriate range. x25519_fe64_add and x25519_fe64_sub are missing one last carry handling step in the rare case where the addition/subtraction by 38 overflows once again. Fixing this, with another conditional addition/subtraction of 38, fixes all failing tests.

It remains to be determined whether these are the only incorrect functions. I have noticed no other cases so far.