1 /***********************************************************************
2 * Copyright (c) 2020 Pieter Wuille *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5 ***********************************************************************/
6
7 #ifndef SECP256K1_MODULE_SCHNORRSIG_TESTS_EXHAUSTIVE_H
8 #define SECP256K1_MODULE_SCHNORRSIG_TESTS_EXHAUSTIVE_H
9
10 #include "include/secp256k1_schnorrsig.h"
11 #include "src/modules/schnorrsig/main_impl.h"
12
13 static const unsigned char invalid_pubkey_bytes[][32] = {
14 /* 0 */
15 {
16 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
17 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
18 },
19 /* 2 */
20 {
21 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
22 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2
23 },
24 /* order */
25 {
26 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
27 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
28 ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 24) & 0xFF,
29 ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 16) & 0xFF,
30 ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 8) & 0xFF,
31 (EXHAUSTIVE_TEST_ORDER + 0UL) & 0xFF
32 },
33 /* order + 1 */
34 {
35 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
36 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
37 ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 24) & 0xFF,
38 ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 16) & 0xFF,
39 ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 8) & 0xFF,
40 (EXHAUSTIVE_TEST_ORDER + 1UL) & 0xFF
41 },
42 /* field size */
43 {
44 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
45 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x2F
46 },
47 /* field size + 1 (note that 1 is legal) */
48 {
49 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
50 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x30
51 },
52 /* 2^256 - 1 */
53 {
54 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
55 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
56 }
57 };
58
59 #define NUM_INVALID_KEYS (sizeof(invalid_pubkey_bytes) / sizeof(invalid_pubkey_bytes[0]))
60
secp256k1_hardened_nonce_function_smallint(unsigned char * nonce32,const unsigned char * msg32,const unsigned char * key32,const unsigned char * xonly_pk32,const unsigned char * algo16,void * data)61 static int secp256k1_hardened_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32,
62 const unsigned char *key32, const unsigned char *xonly_pk32,
63 const unsigned char *algo16, void* data) {
64 secp256k1_scalar s;
65 int *idata = data;
66 (void)msg32;
67 (void)key32;
68 (void)xonly_pk32;
69 (void)algo16;
70 secp256k1_scalar_set_int(&s, *idata);
71 secp256k1_scalar_get_b32(nonce32, &s);
72 return 1;
73 }
74
test_exhaustive_schnorrsig_verify(const secp256k1_context * ctx,const secp256k1_xonly_pubkey * pubkeys,unsigned char (* xonly_pubkey_bytes)[32],const int * parities)75 static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, const secp256k1_xonly_pubkey* pubkeys, unsigned char (*xonly_pubkey_bytes)[32], const int* parities) {
76 int d;
77 uint64_t iter = 0;
78 /* Iterate over the possible public keys to verify against (through their corresponding DL d). */
79 for (d = 1; d <= EXHAUSTIVE_TEST_ORDER / 2; ++d) {
80 int actual_d;
81 unsigned k;
82 unsigned char pk32[32];
83 memcpy(pk32, xonly_pubkey_bytes[d - 1], 32);
84 actual_d = parities[d - 1] ? EXHAUSTIVE_TEST_ORDER - d : d;
85 /* Iterate over the possible valid first 32 bytes in the signature, through their corresponding DL k.
86 Values above EXHAUSTIVE_TEST_ORDER/2 refer to the entries in invalid_pubkey_bytes. */
87 for (k = 1; k <= EXHAUSTIVE_TEST_ORDER / 2 + NUM_INVALID_KEYS; ++k) {
88 unsigned char sig64[64];
89 int actual_k = -1;
90 int e_done[EXHAUSTIVE_TEST_ORDER] = {0};
91 int e_count_done = 0;
92 if (skip_section(&iter)) continue;
93 if (k <= EXHAUSTIVE_TEST_ORDER / 2) {
94 memcpy(sig64, xonly_pubkey_bytes[k - 1], 32);
95 actual_k = parities[k - 1] ? EXHAUSTIVE_TEST_ORDER - k : k;
96 } else {
97 memcpy(sig64, invalid_pubkey_bytes[k - 1 - EXHAUSTIVE_TEST_ORDER / 2], 32);
98 }
99 /* Randomly generate messages until all challenges have been hit. */
100 while (e_count_done < EXHAUSTIVE_TEST_ORDER) {
101 secp256k1_scalar e;
102 unsigned char msg32[32];
103 secp256k1_testrand256(msg32);
104 secp256k1_schnorrsig_challenge(&e, sig64, msg32, pk32);
105 /* Only do work if we hit a challenge we haven't tried before. */
106 if (!e_done[e]) {
107 /* Iterate over the possible valid last 32 bytes in the signature.
108 0..order=that s value; order+1=random bytes */
109 int count_valid = 0, s;
110 for (s = 0; s <= EXHAUSTIVE_TEST_ORDER + 1; ++s) {
111 int expect_valid, valid;
112 if (s <= EXHAUSTIVE_TEST_ORDER) {
113 secp256k1_scalar s_s;
114 secp256k1_scalar_set_int(&s_s, s);
115 secp256k1_scalar_get_b32(sig64 + 32, &s_s);
116 expect_valid = actual_k != -1 && s != EXHAUSTIVE_TEST_ORDER &&
117 (s_s == (actual_k + actual_d * e) % EXHAUSTIVE_TEST_ORDER);
118 } else {
119 secp256k1_testrand256(sig64 + 32);
120 expect_valid = 0;
121 }
122 valid = secp256k1_schnorrsig_verify(ctx, sig64, msg32, &pubkeys[d - 1]);
123 CHECK(valid == expect_valid);
124 count_valid += valid;
125 }
126 /* Exactly one s value must verify, unless R is illegal. */
127 CHECK(count_valid == (actual_k != -1));
128 /* Don't retry other messages that result in the same challenge. */
129 e_done[e] = 1;
130 ++e_count_done;
131 }
132 }
133 }
134 }
135 }
136
test_exhaustive_schnorrsig_sign(const secp256k1_context * ctx,unsigned char (* xonly_pubkey_bytes)[32],const secp256k1_keypair * keypairs,const int * parities)137 static void test_exhaustive_schnorrsig_sign(const secp256k1_context *ctx, unsigned char (*xonly_pubkey_bytes)[32], const secp256k1_keypair* keypairs, const int* parities) {
138 int d, k;
139 uint64_t iter = 0;
140 /* Loop over keys. */
141 for (d = 1; d < EXHAUSTIVE_TEST_ORDER; ++d) {
142 int actual_d = d;
143 if (parities[d - 1]) actual_d = EXHAUSTIVE_TEST_ORDER - d;
144 /* Loop over nonces. */
145 for (k = 1; k < EXHAUSTIVE_TEST_ORDER; ++k) {
146 int e_done[EXHAUSTIVE_TEST_ORDER] = {0};
147 int e_count_done = 0;
148 unsigned char msg32[32];
149 unsigned char sig64[64];
150 int actual_k = k;
151 if (skip_section(&iter)) continue;
152 if (parities[k - 1]) actual_k = EXHAUSTIVE_TEST_ORDER - k;
153 /* Generate random messages until all challenges have been tried. */
154 while (e_count_done < EXHAUSTIVE_TEST_ORDER) {
155 secp256k1_scalar e;
156 secp256k1_testrand256(msg32);
157 secp256k1_schnorrsig_challenge(&e, xonly_pubkey_bytes[k - 1], msg32, xonly_pubkey_bytes[d - 1]);
158 /* Only do work if we hit a challenge we haven't tried before. */
159 if (!e_done[e]) {
160 secp256k1_scalar expected_s = (actual_k + e * actual_d) % EXHAUSTIVE_TEST_ORDER;
161 unsigned char expected_s_bytes[32];
162 secp256k1_scalar_get_b32(expected_s_bytes, &expected_s);
163 /* Invoke the real function to construct a signature. */
164 CHECK(secp256k1_schnorrsig_sign(ctx, sig64, msg32, &keypairs[d - 1], secp256k1_hardened_nonce_function_smallint, &k));
165 /* The first 32 bytes must match the xonly pubkey for the specified k. */
166 CHECK(secp256k1_memcmp_var(sig64, xonly_pubkey_bytes[k - 1], 32) == 0);
167 /* The last 32 bytes must match the expected s value. */
168 CHECK(secp256k1_memcmp_var(sig64 + 32, expected_s_bytes, 32) == 0);
169 /* Don't retry other messages that result in the same challenge. */
170 e_done[e] = 1;
171 ++e_count_done;
172 }
173 }
174 }
175 }
176 }
177
test_exhaustive_schnorrsig(const secp256k1_context * ctx)178 static void test_exhaustive_schnorrsig(const secp256k1_context *ctx) {
179 secp256k1_keypair keypair[EXHAUSTIVE_TEST_ORDER - 1];
180 secp256k1_xonly_pubkey xonly_pubkey[EXHAUSTIVE_TEST_ORDER - 1];
181 int parity[EXHAUSTIVE_TEST_ORDER - 1];
182 unsigned char xonly_pubkey_bytes[EXHAUSTIVE_TEST_ORDER - 1][32];
183 unsigned i;
184
185 /* Verify that all invalid_pubkey_bytes are actually invalid. */
186 for (i = 0; i < NUM_INVALID_KEYS; ++i) {
187 secp256k1_xonly_pubkey pk;
188 CHECK(!secp256k1_xonly_pubkey_parse(ctx, &pk, invalid_pubkey_bytes[i]));
189 }
190
191 /* Construct keypairs and xonly-pubkeys for the entire group. */
192 for (i = 1; i < EXHAUSTIVE_TEST_ORDER; ++i) {
193 secp256k1_scalar scalar_i;
194 unsigned char buf[32];
195 secp256k1_scalar_set_int(&scalar_i, i);
196 secp256k1_scalar_get_b32(buf, &scalar_i);
197 CHECK(secp256k1_keypair_create(ctx, &keypair[i - 1], buf));
198 CHECK(secp256k1_keypair_xonly_pub(ctx, &xonly_pubkey[i - 1], &parity[i - 1], &keypair[i - 1]));
199 CHECK(secp256k1_xonly_pubkey_serialize(ctx, xonly_pubkey_bytes[i - 1], &xonly_pubkey[i - 1]));
200 }
201
202 test_exhaustive_schnorrsig_sign(ctx, xonly_pubkey_bytes, keypair, parity);
203 test_exhaustive_schnorrsig_verify(ctx, xonly_pubkey, xonly_pubkey_bytes, parity);
204 }
205
206 #endif
207