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)
x25519_fe64_subfails, in particular, when subtracting0xffff....fffffrom0. The result should be0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffb5(modulo 2^256-38) but it is instead0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdb.All of
x25519_fe64_add,x25519_fe64_sub, andx25519_fe64_tobyteshave problems.x25519_fe64_tobytesdid not properly normalize every 256-bit integer to the appropriate range.x25519_fe64_addandx25519_fe64_subare 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.