tests: Add Wycheproof ECDH vectors #1492

pull RandomLattice wants to merge 2 commits into bitcoin-core:master from RandomLattice:wycheproof-ecdh changing 10 files +10707 −11
  1. 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

  2. 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>
    f26c323250
  3. 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
  4. 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.

  5. real-or-random added the label assurance on Feb 22, 2024
  6. 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
  7. 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.
  8. in src/modules/ecdh/tests_impl.h:164 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”.
  9. 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.

  10. real-or-random commented at 2:51 pm on April 19, 2024: contributor
    Concept ACK
  11. 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 :-)
  12. RandomLattice force-pushed on Oct 17, 2024
  13. PR feedback: add more wycheproof ECDH test cases 
    Co-authored-by: Sean Andersen <6730974+andozw@users.noreply.github.com>
    3cba981aef
  14. RandomLattice force-pushed on Oct 17, 2024
  15. 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 real-or-random

Labels
assurance

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-21 18:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me