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