Test using with test vectors

[sijohans]

Hello,

I looked into RFC7748 and found some test vectors:

  Test vector:

   Alice's private key, a:
     77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a
   Alice's public key, X25519(a, 9):
     8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a
   Bob's private key, b:
     5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb
   Bob's public key, X25519(b, 9):
     de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f
   Their shared secret, K:
     4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742

Using these values i get different result for the shared secret between bob and alice. Also, none of the calculated shared secrets will match the shared secret from test vectors.

Am i missing something here? Endianess?

static int testx25519WithVectors(void) {

    int r = 0;

    uint8_t alice_sec[X25519_KEY_SIZE] = { /* 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a*/
        0x77, 0x07, 0x6d, 0x0a, 0x73, 0x18, 0xa5, 0x7d,
        0x3c, 0x16, 0xc1, 0x72, 0x51, 0xb2, 0x66, 0x45,
        0xdf, 0x4c, 0x2f, 0x87, 0xeb, 0xc0, 0x99, 0x2a,
        0xb1, 0x77, 0xfb, 0xa5, 0x1d, 0xb9, 0x2c, 0x2a
    };

    uint8_t alice_pub[X25519_KEY_SIZE] = { /* 8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a*/
        0x85, 0x20, 0xf0, 0x09, 0x89, 0x30, 0xa7, 0x54,
        0x74, 0x8b, 0x7d, 0xdc, 0xb4, 0x3e, 0xf7, 0x5a,
        0x0d, 0xbf, 0x3a, 0x0d, 0x26, 0x38, 0x1a, 0xf4,
        0xeb, 0xa4, 0xa9, 0x8e, 0xaa, 0x9b, 0x4e, 0x6a
    };

    uint8_t bob_sec[X25519_KEY_SIZE] = { /* 5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb*/
        0x5d, 0xab, 0x08, 0x7e, 0x62, 0x4a, 0x8a, 0x4b,
        0x79, 0xe1, 0x7f, 0x8b, 0x83, 0x80, 0x0e, 0xe6,
        0x6f, 0x3b, 0xb1, 0x29, 0x26, 0x18, 0xb6, 0xfd,
        0x1c, 0x2f, 0x8b, 0x27, 0xff, 0x88, 0xe0, 0xeb
    };

    uint8_t bob_pub[X25519_KEY_SIZE] = { /* de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f*/
        0xde, 0x9e, 0xdb, 0x7d, 0x7b, 0x7d, 0xc1, 0xb4,
        0xd3, 0x5b, 0x61, 0xc2, 0xec, 0xe4, 0x35, 0x37,
        0x3f, 0x83, 0x43, 0xc8, 0x5b, 0x78, 0x67, 0x4d,
        0xad, 0xfc, 0x7e, 0x14, 0x6f, 0x88, 0x2b, 0x4f
    };

    uint8_t expected_shared[X25519_KEY_SIZE] = { /* 4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742*/
        0x4a, 0x5d, 0x9d, 0x5b, 0xa4, 0xce, 0x2d, 0xe1,
        0x72, 0x8e, 0x3b, 0xf4, 0x80, 0x35, 0x0f, 0x25,
        0xe0, 0x7e, 0x21, 0xc9, 0x47, 0xd1, 0x9e, 0x33,
        0x76, 0xf0, 0x9b, 0x3c, 0x1e, 0x16, 0x17, 0x42
    };

    uint8_t shared1[X25519_SHARED_SIZE];
    uint8_t shared2[X25519_SHARED_SIZE];

    compact_x25519_shared(shared1, alice_sec, bob_pub);
    compact_x25519_shared(shared2, bob_sec, alice_pub);

    for (uint8_t i = 0; i < 32; i++)
    {
        printf("%02x", shared1[i]);
    } printf("\r\n");

    for (uint8_t i = 0; i < 32; i++)
    {
        printf("%02x", shared2[i]);
    } printf("\r\n");

    if (memcmp(shared1, shared2, X25519_SHARED_SIZE) != 0) {
        printf("Fail\n");
        r--;
    }

    if (memcmp(shared1, expected_shared, X25519_KEY_SIZE) != 0) {
        printf("Fail\n");
        r--;
    }

    return r;

[DavyLandman]

Interesting.

I've used golang as a way to "verify" if it worked:

https://github.com/DavyLandman/compact25519/blob/master/test/algamize-test.go

But I didn't port the reference values.

[DavyLandman]

I don't have time this week to take a look. Can you try recalculating the Public key from the private key if that works as expected?

And I'm assuming you ruled out typo's in the key arrays?

[sijohans]

At least i think so, always good to have another pair of eyes looking at it. I also tried reverting the order of the input if it was wrong endinaness or so, but i didn't get any better result.

Should the seed from the RFCs give the same keys if using this library?

[iotanbo]

The above mentioned test vectors are for X25519, not Ed25519. Nice post that describes the difference: X25519 vs Ed25519

[DavyLandman]

@iotanbo thanks for taking the time to check them out. I kept on forgetting to validate them.

@sijohans I'm closing this issue, feel free to open if I've misunderstood your issue.

[iotanbo]

Actually, it turned out that @sijohans was right.

The reason why the test vector given in RFC7748 section 5 doesn't work is because the provided secret keys are raw, i.e. BEFORE clamping applied to them.

Adding

c25519_prepare(alice_sec);
c25519_prepare(bob_sec);

before calling compact_x25519_shared in his code fixes the issue.

At the same time, the tests provided by this library work fine because clamping is applied to secret keys immediately after their creation.

In order to fix this issue, I suggest to call c25519_prepare inside compact_x25519_shared function as well. c25519_prepare can be safely applied multiple times to the secret key, and it is very short so no extra performance penalty will occur.

https://www.jcraige.com/an-explainer-on-ed25519-clamping

[iotanbo]

P.S. Please, check if I am correct this time :)

[DavyLandman]

Okay, reopening until I have time to take a look.

[DavyLandman]

Also, note that my goals is not compliance with a single RFC. There exists multiple RFCs that use Curve25619 operations.

We maybe we could develop some specific wrappers that make it compatible with specific RFCs?

[iotanbo]

As I understand, the library is already compatible with that RFC. This issue is a minor bug which can be fixed with a single line of code. If you want, I can can do it and create a pull request.

[DavyLandman]

This page already contains description of two different constrains between RFCs: https://www.dlbeer.co.nz/oss/c25519.html

I'm fine with reviewing a PR, however, the test should still work. I would like to remain compatible with the go library.

[DavyLandman]

Okay, we can close the issue, primarily due to the help of @iotanbo who took the time to figure out what went wrong.

In essence, the API assumption was that you would always use keys calculated bye the compact_x25519_keygen function. (if you would have run the private key through that first it would have worked). We're now taking a more safe API approach, to always re-clamp the key (at the cost of an extra memory copy, but compared to the rest of the code, that's negligible).

[DavyLandman]

There's a new release out: https://github.com/DavyLandman/compact25519/releases/tag/v1.1.0