tests: Add Wycheproof ECDH vectors

RandomLattice commented at 2:06 am on February 4, 2024: contributor

Adds a test for the ECDH module using the Wycheproof vectors as outlined in #1106.

This commit adds 479 ECDH test vectors. All test vectors pass. The vectors cover:

edge cases in the shared secret
edge cases in the ephemeral public keys
edge cases in arithmetic operations

We use a python script to convert the JSON-formatted vectors into C code, in the same spirit as https://github.com/bitcoin-core/secp256k1/pull/1245

in src/modules/ecdh/tests_impl.h:11 in f26c323250 outdated

 6@@ -7,6 +7,14 @@
 7 #ifndef SECP256K1_MODULE_ECDH_TESTS_H
 8 #define SECP256K1_MODULE_ECDH_TESTS_H
 9 
10+static int ecdh_hash_function_test_xpassthru(unsigned char *output, const unsigned char *x, const unsigned char *y, void *data) {
11+    (void)x;

real-or-random commented at 6:31 pm on February 22, 2024:

You use x below.

(just a random comment, I haven’t really reviewed the code so far)

RandomLattice commented at 10:06 am on October 17, 2024:

Thanks, addressed

real-or-random commented at 6:34 pm on February 22, 2024: contributor

Awesome, Concept ACK

I think most contributors here are currently busy with other projects, but we’ll come back to this for sure.

real-or-random added the label assurance on Feb 22, 2024

in src/modules/ecdh/tests_impl.h:174 in f26c323250 outdated

169+        parsed_ok = secp256k1_ec_pubkey_parse(CTX, &point, pk, testvectors[t].pk_len);
170+
171+        expected_result = testvectors[t].expected_result;
172+
173+        /* fail if public key is valid, but doesn't parse */
174+        CHECK(parsed_ok || expected_result == 0);

real-or-random commented at 2:07 pm on April 19, 2024:

I think this should be tighter:

0        CHECK(parsed_ok == expected_result);

The missing case is parsed_ok == 1 and expected_result == 0. If I’m not mistaken, then the entire test doesn’t fail currently:

the CHECK here passes
we don’t continue
but then the CHECK(secp256k1_memcmp_var)…passes vacuously becausetestvectors[t].shared_len == 0`

RandomLattice commented at 10:06 am on October 17, 2024:

Thanks, addressed

in src/wycheproof/WYCHEPROOF_COPYING:9 in f26c323250 outdated

2@@ -3,9 +3,18 @@
3   `b063b4aedae951c69df014cd25fa6d69ae9e8cb9`, see
4   https://github.com/google/wycheproof/blob/b063b4aedae951c69df014cd25fa6d69ae9e8cb9/testvectors_v1/ecdsa_secp256k1_sha256_bitcoin_test.json
5 
6+* The file `ecdh_secp256k1_test.json` in this directory
7+  comes from Google's project Wycheproof with git commit
8+  `d9f6ec7d8bd8c96da05368999094e4a75ba5cb3d`, see
9+  https://github.com/google/wycheproof/blob/d9f6ec7d8bd8c96da05368999094e4a75ba5cb3d/testvectors_v1/ecdh_secp256k1_test.json

real-or-random commented at 2:13 pm on April 19, 2024:

Wycheproof ownership was recently moved to C2SP (https://github.com/C2SP/wycheproof community maintenance), so this should be updated to the new URL.) See @FiloSottile’s talk https://archive.org/details/oscw-2024-fillippo-valsorda-cryptographic-test-vectors for background.)

You could update the other URLs in a separate commit, and update the ECDSA vectors, see https://github.com/C2SP/wycheproof/pull/91 (if you’re willing to care of this in this PR).

RandomLattice commented at 10:07 am on October 17, 2024:

Sure thing, we will open a concurrent PR to update this. I think it will be cleaner.

real-or-random commented at 8:38 am on March 24, 2025:

If you’re still interested, then I think a proper version of the abandoned (?) #1638 could be included in this PR. It should be trivial.

in src/modules/ecdh/tests_impl.h:163 in f26c323250 outdated

159+        const unsigned char *pk;
160+        const unsigned char *sk;
161+        const unsigned char *expected_shared_secret;
162+        unsigned char output_ecdh[65] = { 0 };
163+
164+        int expected_result;

real-or-random commented at 2:18 pm on April 19, 2024:

Can we rename this to expected_parses or similar? result is a bit imprecise.

RandomLattice commented at 10:08 am on October 17, 2024:

I agree result is a bit imprecise, but it’s what wycheproof uses in their test vectors (and it is used for different purposes all together, so it seems a bit hard to fix this for them…). Let me know if this is not acceptable, happy to change it to something else. We use it for “expected parses” but also “expected ECDH function outcome”.

in tools/tests_wycheproof_generate_ecdh.py:17 in f26c323250 outdated

12+from binascii import hexlify, unhexlify
13+from wycheproof_utils import to_c_array
14+
15+def should_skip(test_vector_flags):
16+    # skip these vectors because they are for ASN.1 encoding issues and other curves
17+    flags_to_skip = {"InvalidAsn", "InvalidCurveAttack", "InvalidEncoding", "WrongCurve", "UnnamedCurve"}

real-or-random commented at 2:47 pm on April 19, 2024:

I’m not sure about all of these.

“InvalidAsn’: :heavy_check_mark:
“InvalidCurveAttack”. the json says “The point of the public key is not on the curve.” – shouldn’t we have these? (How is this different from “InvalidPublic”? I assume the keys in case of “InvalidCurveAttack” are on some other curve.)
What is “InvalidEncoding”?
“WrongCurve”: I really don’t understand the JSON here. For example, test case 492 says: “public key has invalid point of order 2 on secp256r1. The point of the public key is a valid on secp256k1. “, but then says “invalid”?! Do you know what they have in mind?
“UnnamendCurve”: Have you tried these? If we reject correctly, let’s just include them? Again, I can’t follow the JSON entirely. :/ For example, test case 511 has “public key of order 3” with “WeakPublicKey”, “InvalidPublic”, “UnnamedCurve”. How can it be invalid and at the same time have an order? How can the order be 3 on our curve? (Shouldn’t it have InvalidCurveAttack then? …)

RandomLattice commented at 10:13 am on October 17, 2024:

“InvalidCurveAttack”. the json says “The point of the public key is not on the curve.” – shouldn’t we have these? (How is this different from “InvalidPublic”? I assume the keys in case of “InvalidCurveAttack” are on some other curve.

You’re right – we should have these. We changed it so that we’re no longer skipping InvalidCurveAttack test vectors.

What is “InvalidEncoding”?

We are now including this test case.

“WrongCurve”: I really don’t understand the JSON here. For example, test case 492 says: “public key has invalid point of order 2 on secp256r1. The point of the public key is a valid on secp256k1. “, but then says “invalid”?! Do you know what they have in mind?

All these 20 cases of WrongCurve have a public key whose ASN.1 representation carries an OID for a different curve (not secp256k1). None of the libsecp256k1 code parses this ASN.1 structure so we are not including these in the test cases.

In that specific case (tcId 492) they encode public key bytes that in secp256r1 coincide with a point of order 2 but in secp256k1 is a valid point (is in the (prime) group). We are just skipping this since this confusion is at an abstraction level higher than libsecp256k1. Again, none of the libsecp256k1 code parses this ASN.1 where the confusion (may) happen.

“UnnamendCurve”: Have you tried these? If we reject correctly, let’s just include them?

These are now included.

test case 511 has “public key of order 3” with “WeakPublicKey”, “InvalidPublic”, “UnnamedCurve”. How can it be invalid and at the same time have an order?

I guess their definition of invalid here is “does not lie in the proper subgroup”. This is consistent with the SEC (see §3.2.2.1 step 4 of https://www.secg.org/sec1-v2.pdf - ensures that the order or the point is large).

We are now skipping tcID 496, 497, 502, 503, 504, 505, 507. All these public keys have a custom ASN.1 encoding that explicitly encodes some curve parameters (including the order). Again, libsecp256k1 never parses these so we don’t care about these. In the tests we skip them.

For example, tcId 496 has the following public key:

 0openssl asn1parse -in 496.bin -i -inform DR -dump
 1    0:d=0  hl=4 l= 307 cons: SEQUENCE
 2    4:d=1  hl=3 l= 236 cons:  SEQUENCE
 3    7:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
 4   16:d=2  hl=3 l= 224 cons:   SEQUENCE
 5   19:d=3  hl=2 l=   1 prim:    INTEGER           :01
 6   22:d=3  hl=2 l=  44 cons:    SEQUENCE
 7   24:d=4  hl=2 l=   7 prim:     OBJECT            :prime-field
 8   33:d=4  hl=2 l=  33 prim:     INTEGER           :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
 9   68:d=3  hl=2 l=  68 cons:    SEQUENCE
10   70:d=4  hl=2 l=  32 prim:     OCTET STRING
11      0000 - 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
12      0010 - 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
13  104:d=4  hl=2 l=  32 prim:     OCTET STRING
14      0000 - 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
15      0010 - 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 07   ................
16  138:d=3  hl=2 l=  65 prim:    OCTET STRING
17      0000 - 04 79 be 66 7e f9 dc bb-ac 55 a0 62 95 ce 87 0b   .y.f~....U.b....
18      0010 - 07 02 9b fc db 2d ce 28-d9 59 f2 81 5b 16 f8 17   .....-.(.Y..[...
19      0020 - 98 48 3a da 77 26 a3 c4-65 5d a4 fb fc 0e 11 08   .H:.w&..e]......
20      0030 - a8 fd 17 b4 48 a6 85 54-19 9c 47 d0 8f fb 10 d4   ....H..T..G.....
21      0040 - b8                                                .
22  205:d=3  hl=2 l=  33 prim:    INTEGER           :-FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
23  240:d=3  hl=2 l=   1 prim:    INTEGER           :01
24  243:d=1  hl=2 l=  66 prim:  BIT STRING
25      0000 - 00 04 49 c2 48 ed c6 59-e1 84 82 b7 10 57 48 a4   ..I.H..Y.....WH.
26      0010 - b9 5d 3a 46 95 2a 5b a7-2d a0 d7 02 dc 97 a6 4e   .]:F.*[.-......N
27      0020 - 99 79 9d 8c ff 7a 5c 4b-92 5e 43 60 ec e2 5c cf   .y...z\K.^C`..\.
28      0030 - 30 7d 7a 9a 70 63 28 6b-bd 16 ef 64 c6 5f 54 67   0}z.pc(k...d._Tg
29      0040 - 57 e2

For reference this is the ASN.1 encoding:

 0xxd 496.bin
 100000000: 3082 0133 3081 ec06 072a 8648 ce3d 0201  0..30....*.H.=..
 200000010: 3081 e002 0101 302c 0607 2a86 48ce 3d01  0.....0,..*.H.=.
 300000020: 0102 2100 ffff ffff ffff ffff ffff ffff  ..!.............
 400000030: ffff ffff ffff ffff ffff ffff ffff fffe  ................
 500000040: ffff fc2f 3044 0420 0000 0000 0000 0000  .../0D. ........
 600000050: 0000 0000 0000 0000 0000 0000 0000 0000  ................
 700000060: 0000 0000 0000 0000 0420 0000 0000 0000  ......... ......
 800000070: 0000 0000 0000 0000 0000 0000 0000 0000  ................
 900000080: 0000 0000 0000 0000 0007 0441 0479 be66  ...........A.y.f
1000000090: 7ef9 dcbb ac55 a062 95ce 870b 0702 9bfc  ~....U.b........
11000000a0: db2d ce28 d959 f281 5b16 f817 9848 3ada  .-.(.Y..[....H:.
12000000b0: 7726 a3c4 655d a4fb fc0e 1108 a8fd 17b4  w&..e]..........
13000000c0: 48a6 8554 199c 47d0 8ffb 10d4 b802 21ff  H..T..G.......!.
14000000d0: 0000 0000 0000 0000 0000 0000 0000 0001  ................
15000000e0: 4551 2319 50b7 5fc4 402d a173 2fc9 bebf  EQ#.P._.@-.s/...
16000000f0: 0201 0103 4200 0449 c248 edc6 59e1 8482  ....B..I.H..Y...
1700000100: b710 5748 a4b9 5d3a 4695 2a5b a72d a0d7  ..WH..]:F.*[.-..
1800000110: 02dc 97a6 4e99 799d 8cff 7a5c 4b92 5e43  ....N.y...z\K.^C
1900000120: 60ec e25c cf30 7d7a 9a70 6328 6bbd 16ef  `..\.0}z.pc(k...
2000000130: 64c6 5f54 6757 e2                        d._TgW.

Here the order of the curve is encoded as explicit parameter (which is the “wrong” order): -115792089237316195423570985008687907852837564279074904382605163141518161494337 or -FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.

All other skipped cases are analogous.

real-or-random commented at 8:30 am on March 24, 2025:

Nice, thanks a lot for going through all of this!

real-or-random commented at 2:51 pm on April 19, 2024: contributor

Concept ACK

RandomLattice commented at 4:14 pm on April 30, 2024: contributor

Thanks @real-or-random for the review. We’re going to have a look and come back here soon to take care of this PR :-)

RandomLattice force-pushed on Oct 17, 2024

RandomLattice commented at 12:25 pm on October 17, 2024: contributor

@real-or-random it took a bit longer than expected but here we are. We addressed the main points of the review in https://github.com/bitcoin-core/secp256k1/pull/1492/commits/3cba981aef2b5c64581f750d929775e30ab34616, PTAL whenever you’ve a chance. Thanks!

RandomLattice requested review from real-or-random on Jan 8, 2025

RandomLattice commented at 8:37 am on January 8, 2025: contributor

friendly ping to review this whenever you’ve a chance @real-or-random. Thanks!

RandomLattice commented at 7:33 am on March 21, 2025: contributor

@real-or-random this is ready for review, wondering if we could have some eyes. Thank you so much in advance!

in src/modules/ecdh/tests_impl.h:174 in 3cba981aef outdated

171+
172+        CHECK(parsed_ok == expected_result);
173+
174+        if (!parsed_ok && expected_result == 0) {
175+            continue;
176+        }

real-or-random commented at 7:36 am on March 24, 2025:

nit:

0        expected_result = testvectors[t].expected_result;
1        CHECK(parsed_ok == expected_result);
2        if (!parsed_ok) {
3            continue;
4        }

Now this can be simplified, plus I think there’s more vertical whitespace than common. :)

RandomLattice commented at 1:37 pm on April 9, 2025:

Thanks, added

wlad76 commented at 2:08 pm on April 9, 2025:

Ok

in tools/tests_wycheproof_generate_ecdh.py:86 in 3cba981aef outdated

81+public_keys = ""
82+cache_sks = {}
83+cache_public_keys = {}
84+
85+for i in range(num_groups):
86+    group = doc['testGroups'][i]

real-or-random commented at 8:16 am on March 24, 2025:

0for group in doc['testGroups']

And then we can remove num_groups = len(doc['testGroups'])

RandomLattice commented at 1:37 pm on April 9, 2025:

Absolutely!

in tools/tests_wycheproof_generate_ecdh.py:91 in 3cba981aef outdated

86+    group = doc['testGroups'][i]
87+    num_tests = len(group['tests'])
88+    assert group["type"] == "EcdhTest"
89+    assert group["curve"] == "secp256k1"
90+    for j in range(num_tests):
91+        test_vector = group['tests'][j]

real-or-random commented at 8:16 am on March 24, 2025:

0    for test_vector in group['tests']:

And then we can remove num_tests = len(group['tests'])

RandomLattice commented at 1:37 pm on April 9, 2025:

you’re right, addressed

in tools/tests_wycheproof_generate_ecdh.py:78 in 3cba981aef outdated

73+
74+num_groups = len(doc['testGroups'])
75+
76+num_vectors = 0
77+offset_sk_running, offset_pk_running, offset_shared = 0, 0, 0
78+out = ""

real-or-random commented at 8:18 am on March 24, 2025:

out is a bit ambigous. test_vectors_out?

RandomLattice commented at 1:38 pm on April 9, 2025:

sounds good. addressed

in tools/tests_wycheproof_generate_ecdh.py:57 in 3cba981aef outdated

52+        return parse_der_pk(value)
53+    raise ValueError("unknown tag")
54+
55+def parse_public_key(pk):
56+    der_pub_key = parse_der_pk(unhexlify(pk))   # Convert back to str and strip off the `0x`
57+    return hexlify(der_pub_key).decode('utf-8')[2:]

real-or-random commented at 8:19 am on March 24, 2025:

0    return hexlify(der_pub_key).decode()[2:]

utf-8 is the default

RandomLattice commented at 1:38 pm on April 9, 2025:

aha! thanks, addressed

in tools/tests_wycheproof_generate_ecdh.py:45 in 3cba981aef outdated

40+            L = 256*int(s[2]) + int(s[3])
41+            offset = 2
42+        else:
43+            raise ValueError("invalid L")
44+    value = s[(offset+2):(L+2+offset)]
45+    rest = s[(L+2+offset):]

real-or-random commented at 8:20 am on March 24, 2025:

just a micronit, but I’d prefer spacing around the operators

RandomLattice commented at 1:38 pm on April 9, 2025:

done, thanks

in tools/wycheproof_utils.py:11 in 3cba981aef outdated

 6+'''
 7+
 8+def to_c_array(x):
 9+    if x == "":
10+        return ""
11+    s = ',0x'.join(a+b for a,b in zip(x[::2], x[1::2]))

real-or-random commented at 8:21 am on March 24, 2025:

0    s = ',0x'.join(a + b for a, b in zip(x[::2], x[1::2]))

RandomLattice commented at 1:38 pm on April 9, 2025:

sounds good, thanks

in tools/tests_wycheproof_generate_ecdh.py:105 in 3cba981aef outdated

100+        # // 2 to convert hex to byte length
101+        shared_size = len(test_vector['shared']) // 2
102+        sk_size = len(private_key) // 2
103+        pk_size = len(public_key) // 2
104+
105+        shared_secrets += ",\n  " if num_vectors and shared_size else ""

real-or-random commented at 8:25 am on March 24, 2025:

move this down just above the other modification of shared_secrets?

RandomLattice commented at 1:38 pm on April 9, 2025:

yes, addressed, thanks

in tools/tests_wycheproof_generate_ecdh.py:62 in 3cba981aef outdated

57+    return hexlify(der_pub_key).decode('utf-8')[2:]
58+
59+def normalize_private_key(sk):
60+    # Ensure the private key is at most 64 characters long, retaining the last 64 if longer.
61+    normalized = sk[-64:].zfill(64)
62+    assert len(normalized) == 64, "private key must be exactly 64 characters long."

real-or-random commented at 8:27 am on March 24, 2025:

0    if len(normalized) != 64:
1        raise ValueError("private key must be exactly 64 characters long.")

(Don’t rely on assertions being enabled)

RandomLattice commented at 1:38 pm on April 9, 2025:

good idea, addressed

in tools/tests_wycheproof_generate_ecdh.py:59 in 3cba981aef outdated

55+def parse_public_key(pk):
56+    der_pub_key = parse_der_pk(unhexlify(pk))   # Convert back to str and strip off the `0x`
57+    return hexlify(der_pub_key).decode('utf-8')[2:]
58+
59+def normalize_private_key(sk):
60+    # Ensure the private key is at most 64 characters long, retaining the last 64 if longer.

real-or-random commented at 8:29 am on March 24, 2025:

How could it ever be longer?

RandomLattice commented at 1:39 pm on April 9, 2025:

in the particular way wycheproof encodes scalars, there may be leading zeroes. added a comment to clarify.

in tools/tests_wycheproof_generate_ecdh.py:26 in 3cba981aef outdated

22+    We skip some test case IDs that have a public key whose custom ASN.1 representation explicitly
23+    encodes some curve parameters that are invalid. libsecp256k1 never parses this part so we do
24+    not care testing those. See https://github.com/bitcoin-core/secp256k1/pull/1492#discussion_r1572491546
25+    '''
26+    tcids_to_skip = [496, 497, 502, 503, 504, 505, 507]
27+    return test_vector_tcid in tcids_to_skip

real-or-random commented at 8:32 am on March 24, 2025:

consistency: docstring vs comment. (I’d just stick to the comment).

RandomLattice commented at 1:39 pm on April 9, 2025:

good idea, addressed

in tools/tests_wycheproof_generate_ecdh.py:18 in 3cba981aef outdated

12+from binascii import hexlify, unhexlify
13+from wycheproof_utils import to_c_array
14+
15+def should_skip_flags(test_vector_flags):
16+    # skip these vectors because they are for ASN.1 encoding issues and other curves
17+    flags_to_skip = {"InvalidAsn", "WrongCurve"}

real-or-random commented at 8:33 am on March 24, 2025:

A short description list of all the (unclear) categories would be nice. This has confused us, and I assume it will confuse others in the future. (Or just add another reference to #1492 (review) )

RandomLattice commented at 1:39 pm on April 9, 2025:

thanks, added a reference to the link as a comment.

real-or-random commented at 8:36 am on March 24, 2025: contributor

Nice! All I have is some nits, and I believe this is ready. It should perhaps get the eyes of another reviewer, but I don’t think another in-depth review is necessary. In the end, this “just” adds tests.

Sorry, that this too so long.

RandomLattice commented at 2:58 pm on April 9, 2025: contributor

@real-or-random thanks for the review! We’ve addressed all changes (all minor).

Can you please take a quick look whenever you’ve a chance? Thanks

RandomLattice requested review from real-or-random on Apr 14, 2025

real-or-random commented at 2:14 pm on April 14, 2025: contributor

@real-or-random thanks for the review! We’ve addressed all changes (all minor).

Great!

Can you please take a quick look whenever you’ve a chance? Thanks

I don’t have the time this week, but next week should work. :)

real-or-random approved

real-or-random commented at 9:55 am on April 22, 2025: contributor

ACK https://github.com/bitcoin-core/secp256k1/pull/1492/commits/fe5f1e3bbf3247a56a85a33f637dad475b8f9836 I’ve also tested that changing a vector in the json files makes the test fail @RandomLattice Could you squash this?

tests: Add Wycheproof ECDH vectors

Adds a test for the ECDH module using the Wycheproof vectors.
We use a python script to convert the JSON-formatted vectors
into C code, in the same spirit as https://github.com/bitcoin-core/secp256k1/pull/1245

Co-authored-by: Sean Andersen <6730974+andozw@users.noreply.github.com>

fba627bea1

RandomLattice force-pushed on Apr 23, 2025

RandomLattice commented at 11:46 pm on April 23, 2025: contributor

@real-or-random : Thanks for the review. Squashed into a single commit.

real-or-random approved

real-or-random commented at 7:17 am on April 24, 2025: contributor

ACK fba627bea1829e34c63113f87091866b1c408156

tests: Add Wycheproof ECDH vectors #1492