1 /**********************************************************************
2 * Copyright (c) 2013-2015 Pieter Wuille *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5 **********************************************************************/
6
7 #ifndef _SECP256K1_MODULE_RECOVERY_TESTS_
8 #define _SECP256K1_MODULE_RECOVERY_TESTS_
9
test_ecdsa_recovery_end_to_end(void)10 void test_ecdsa_recovery_end_to_end(void) {
11 unsigned char extra[32] = {0x00};
12 unsigned char privkey[32];
13 unsigned char message[32];
14 secp256k1_ecdsa_signature signature[5];
15 secp256k1_ecdsa_recoverable_signature rsignature[5];
16 unsigned char sig[74];
17 secp256k1_pubkey pubkey;
18 secp256k1_pubkey recpubkey;
19 int recid = 0;
20
21 /* Generate a random key and message. */
22 {
23 secp256k1_scalar msg, key;
24 random_scalar_order_test(&msg);
25 random_scalar_order_test(&key);
26 secp256k1_scalar_get_b32(privkey, &key);
27 secp256k1_scalar_get_b32(message, &msg);
28 }
29
30 /* Construct and verify corresponding public key. */
31 CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1);
32 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1);
33
34 /* Serialize/parse compact and verify/recover. */
35 extra[0] = 0;
36 CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[0], message, privkey, NULL, NULL) == 1);
37 CHECK(secp256k1_ecdsa_sign(ctx, &signature[0], message, privkey, NULL, NULL) == 1);
38 CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[4], message, privkey, NULL, NULL) == 1);
39 CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[1], message, privkey, NULL, extra) == 1);
40 extra[31] = 1;
41 CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[2], message, privkey, NULL, extra) == 1);
42 extra[31] = 0;
43 extra[0] = 1;
44 CHECK(secp256k1_ecdsa_sign_recoverable(ctx, &rsignature[3], message, privkey, NULL, extra) == 1);
45 CHECK(secp256k1_ecdsa_recoverable_signature_serialize_compact(ctx, sig, &recid, &rsignature[4]) == 1);
46 CHECK(secp256k1_ecdsa_recoverable_signature_convert(ctx, &signature[4], &rsignature[4]) == 1);
47 CHECK(memcmp(&signature[4], &signature[0], 64) == 0);
48 CHECK(secp256k1_ecdsa_verify(ctx, &signature[4], message, &pubkey) == 1);
49 memset(&rsignature[4], 0, sizeof(rsignature[4]));
50 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsignature[4], sig, recid) == 1);
51 CHECK(secp256k1_ecdsa_recoverable_signature_convert(ctx, &signature[4], &rsignature[4]) == 1);
52 CHECK(secp256k1_ecdsa_verify(ctx, &signature[4], message, &pubkey) == 1);
53 /* Parse compact (with recovery id) and recover. */
54 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsignature[4], sig, recid) == 1);
55 CHECK(secp256k1_ecdsa_recover(ctx, &recpubkey, &rsignature[4], message) == 1);
56 CHECK(memcmp(&pubkey, &recpubkey, sizeof(pubkey)) == 0);
57 /* Serialize/destroy/parse signature and verify again. */
58 CHECK(secp256k1_ecdsa_recoverable_signature_serialize_compact(ctx, sig, &recid, &rsignature[4]) == 1);
59 sig[secp256k1_rand_bits(6)] += 1 + secp256k1_rand_int(255);
60 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsignature[4], sig, recid) == 1);
61 CHECK(secp256k1_ecdsa_recoverable_signature_convert(ctx, &signature[4], &rsignature[4]) == 1);
62 CHECK(secp256k1_ecdsa_verify(ctx, &signature[4], message, &pubkey) == 0);
63 /* Recover again */
64 CHECK(secp256k1_ecdsa_recover(ctx, &recpubkey, &rsignature[4], message) == 0 ||
65 memcmp(&pubkey, &recpubkey, sizeof(pubkey)) != 0);
66 }
67
68 /* Tests several edge cases. */
test_ecdsa_recovery_edge_cases(void)69 void test_ecdsa_recovery_edge_cases(void) {
70 const unsigned char msg32[32] = {
71 'T', 'h', 'i', 's', ' ', 'i', 's', ' ',
72 'a', ' ', 'v', 'e', 'r', 'y', ' ', 's',
73 'e', 'c', 'r', 'e', 't', ' ', 'm', 'e',
74 's', 's', 'a', 'g', 'e', '.', '.', '.'
75 };
76 const unsigned char sig64[64] = {
77 /* Generated by signing the above message with nonce 'This is the nonce we will use...'
78 * and secret key 0 (which is not valid), resulting in recid 0. */
79 0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8,
80 0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96,
81 0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63,
82 0x17, 0x9A, 0x7D, 0xD1, 0x7B, 0xD2, 0x35, 0x32,
83 0x4B, 0x1B, 0x7D, 0xF3, 0x4C, 0xE1, 0xF6, 0x8E,
84 0x69, 0x4F, 0xF6, 0xF1, 0x1A, 0xC7, 0x51, 0xDD,
85 0x7D, 0xD7, 0x3E, 0x38, 0x7E, 0xE4, 0xFC, 0x86,
86 0x6E, 0x1B, 0xE8, 0xEC, 0xC7, 0xDD, 0x95, 0x57
87 };
88 secp256k1_pubkey pubkey;
89 /* signature (r,s) = (4,4), which can be recovered with all 4 recids. */
90 const unsigned char sigb64[64] = {
91 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
92 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
93 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
94 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
95 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
96 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
97 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
98 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
99 };
100 secp256k1_pubkey pubkeyb;
101 secp256k1_ecdsa_recoverable_signature rsig;
102 secp256k1_ecdsa_signature sig;
103 int recid;
104
105 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 0));
106 CHECK(!secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32));
107 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 1));
108 CHECK(secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32));
109 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 2));
110 CHECK(!secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32));
111 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sig64, 3));
112 CHECK(!secp256k1_ecdsa_recover(ctx, &pubkey, &rsig, msg32));
113
114 for (recid = 0; recid < 4; recid++) {
115 int i;
116 int recid2;
117 /* (4,4) encoded in DER. */
118 unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04};
119 unsigned char sigcder_zr[7] = {0x30, 0x05, 0x02, 0x00, 0x02, 0x01, 0x01};
120 unsigned char sigcder_zs[7] = {0x30, 0x05, 0x02, 0x01, 0x01, 0x02, 0x00};
121 unsigned char sigbderalt1[39] = {
122 0x30, 0x25, 0x02, 0x20, 0x00, 0x00, 0x00, 0x00,
123 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
124 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
125 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
126 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
127 };
128 unsigned char sigbderalt2[39] = {
129 0x30, 0x25, 0x02, 0x01, 0x04, 0x02, 0x20, 0x00,
130 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
131 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
132 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
133 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
134 };
135 unsigned char sigbderalt3[40] = {
136 0x30, 0x26, 0x02, 0x21, 0x00, 0x00, 0x00, 0x00,
137 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
138 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
139 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
140 0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
141 };
142 unsigned char sigbderalt4[40] = {
143 0x30, 0x26, 0x02, 0x01, 0x04, 0x02, 0x21, 0x00,
144 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
145 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
146 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
147 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
148 };
149 /* (order + r,4) encoded in DER. */
150 unsigned char sigbderlong[40] = {
151 0x30, 0x26, 0x02, 0x21, 0x00, 0xFF, 0xFF, 0xFF,
152 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
153 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC,
154 0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E,
155 0x8C, 0xD0, 0x36, 0x41, 0x45, 0x02, 0x01, 0x04
156 };
157 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigb64, recid) == 1);
158 CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyb, &rsig, msg32) == 1);
159 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder)) == 1);
160 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 1);
161 for (recid2 = 0; recid2 < 4; recid2++) {
162 secp256k1_pubkey pubkey2b;
163 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigb64, recid2) == 1);
164 CHECK(secp256k1_ecdsa_recover(ctx, &pubkey2b, &rsig, msg32) == 1);
165 /* Verifying with (order + r,4) should always fail. */
166 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderlong, sizeof(sigbderlong)) == 1);
167 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0);
168 }
169 /* DER parsing tests. */
170 /* Zero length r/s. */
171 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder_zr, sizeof(sigcder_zr)) == 0);
172 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder_zs, sizeof(sigcder_zs)) == 0);
173 /* Leading zeros. */
174 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt1, sizeof(sigbderalt1)) == 0);
175 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt2, sizeof(sigbderalt2)) == 0);
176 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt3, sizeof(sigbderalt3)) == 0);
177 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt4, sizeof(sigbderalt4)) == 0);
178 sigbderalt3[4] = 1;
179 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt3, sizeof(sigbderalt3)) == 1);
180 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0);
181 sigbderalt4[7] = 1;
182 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbderalt4, sizeof(sigbderalt4)) == 1);
183 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0);
184 /* Damage signature. */
185 sigbder[7]++;
186 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder)) == 1);
187 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0);
188 sigbder[7]--;
189 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, 6) == 0);
190 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder) - 1) == 0);
191 for(i = 0; i < 8; i++) {
192 int c;
193 unsigned char orig = sigbder[i];
194 /*Try every single-byte change.*/
195 for (c = 0; c < 256; c++) {
196 if (c == orig ) {
197 continue;
198 }
199 sigbder[i] = c;
200 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigbder, sizeof(sigbder)) == 0 || secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyb) == 0);
201 }
202 sigbder[i] = orig;
203 }
204 }
205
206 /* Test r/s equal to zero */
207 {
208 /* (1,1) encoded in DER. */
209 unsigned char sigcder[8] = {0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01};
210 unsigned char sigc64[64] = {
211 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
212 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
213 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
214 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
215 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
216 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
217 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
218 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
219 };
220 secp256k1_pubkey pubkeyc;
221 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigc64, 0) == 1);
222 CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyc, &rsig, msg32) == 1);
223 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder, sizeof(sigcder)) == 1);
224 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyc) == 1);
225 sigcder[4] = 0;
226 sigc64[31] = 0;
227 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigc64, 0) == 1);
228 CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyb, &rsig, msg32) == 0);
229 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder, sizeof(sigcder)) == 1);
230 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyc) == 0);
231 sigcder[4] = 1;
232 sigcder[7] = 0;
233 sigc64[31] = 1;
234 sigc64[63] = 0;
235 CHECK(secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rsig, sigc64, 0) == 1);
236 CHECK(secp256k1_ecdsa_recover(ctx, &pubkeyb, &rsig, msg32) == 0);
237 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigcder, sizeof(sigcder)) == 1);
238 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg32, &pubkeyc) == 0);
239 }
240 }
241
run_recovery_tests(void)242 void run_recovery_tests(void) {
243 int i;
244 for (i = 0; i < 64*count; i++) {
245 test_ecdsa_recovery_end_to_end();
246 }
247 test_ecdsa_recovery_edge_cases();
248 }
249
250 #endif
251