Mercurial > dropbear

comparison ecdsa.c @ 793:70625eed40c9 ecc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A bit of work on ecdsa for host/auth keys
author Matt Johnston <matt@ucc.asn.au>
date Sun, 14 Apr 2013 00:50:03 +0800
parents e465ed10c51d
children d386defb5376
comparison
equal deleted inserted replaced
768:6e6ce39da2fc 793:70625eed40c9
1 #include "includes.h" 1 #include "includes.h"
2 #include "dbutil.h" 2 #include "dbutil.h"
3 #include "crypto_desc.h" 3 #include "crypto_desc.h"
4 #include "ecc.h" 4 #include "ecc.h"
5 #include "ecdsa.h"
5 6
6 #ifdef DROPBEAR_ECDSA 7 #ifdef DROPBEAR_ECDSA
7 8
8 ecc_key *gen_ecdsa_priv_key(unsigned int bit_size) { 9 ecc_key *gen_ecdsa_priv_key(unsigned int bit_size) {
9 const ltc_ecc_set_type *dp = NULL; // curve domain parameters 10 const ltc_ecc_set_type *dp = NULL; // curve domain parameters
53 struct dropbear_ecc_curve **curve; 54 struct dropbear_ecc_curve **curve;
54 ecc_key *new_key = NULL; 55 ecc_key *new_key = NULL;
55 56
56 // string "ecdsa-sha2-[identifier]" 57 // string "ecdsa-sha2-[identifier]"
57 key_ident = buf_getstring(buf, &key_ident_len); 58 key_ident = buf_getstring(buf, &key_ident_len);
58 // string "ecdsa-sha2-[identifier]" 59 // string "[identifier]"
59 identifier = buf_getstring(buf, &identifier_len); 60 identifier = buf_getstring(buf, &identifier_len);
60 61
61 if (key_ident_len != identifier_len + strlen("ecdsa-sha2-")) { 62 if (key_ident_len != identifier_len + strlen("ecdsa-sha2-")) {
62 TRACE(("Bad identifier lengths")) 63 TRACE(("Bad identifier lengths"))
63 goto out; 64 goto out;
66 TRACE(("mismatching identifiers")) 67 TRACE(("mismatching identifiers"))
67 goto out; 68 goto out;
68 } 69 }
69 70
70 for (curve = dropbear_ecc_curves; *curve; curve++) { 71 for (curve = dropbear_ecc_curves; *curve; curve++) {
71 if (memcmp(identifier, (*curve)->name, strlen((*curve)->name)) == 0) { 72 if (memcmp(identifier, (char*)(*curve)->name, strlen((char*)(*curve)->name)) == 0) {
72 break; 73 break;
73 } 74 }
74 } 75 }
75 if (!*curve) { 76 if (!*curve) {
76 TRACE(("couldn't match ecc curve")) 77 TRACE(("couldn't match ecc curve"))
80 // string Q 81 // string Q
81 q_buf = buf_getstringbuf(buf); 82 q_buf = buf_getstringbuf(buf);
82 new_key = buf_get_ecc_raw_pubkey(q_buf, *curve); 83 new_key = buf_get_ecc_raw_pubkey(q_buf, *curve);
83 84
84 out: 85 out:
85 if (key_ident) { 86 m_free(key_ident);
86 m_free(key_ident); 87 m_free(identifier);
87 }
88 if (identifier) {
89 m_free(identifier);
90 }
91 if (q_buf) { 88 if (q_buf) {
92 buf_free(q_buf); 89 buf_free(q_buf);
93 q_buf = NULL; 90 q_buf = NULL;
94 } 91 }
95 TRACE(("leave buf_get_ecdsa_pub_key")) 92 TRACE(("leave buf_get_ecdsa_pub_key"))
96 return new_key; 93 return new_key;
97 } 94 }
98 95
96 ecc_key *buf_get_ecdsa_priv_key(buffer *buf) {
97 ecc_key *new_key = NULL;
98 TRACE(("enter buf_get_ecdsa_priv_key"))
99 new_key = buf_get_ecdsa_pub_key(buf);
100 if (!new_key) {
101 return NULL;
102 }
103
104 if (buf_getmpint(buf, new_key->k) != DROPBEAR_SUCCESS) {
105 ecc_free(new_key);
106 return NULL;
107 }
108
109 return new_key;
110 }
111
112 void buf_put_ecdsa_pub_key(buffer *buf, ecc_key *key) {
113 struct dropbear_ecc_curve *curve = NULL;
114 unsigned char key_ident[30];
115
116 curve = curve_for_dp(key->dp);
117 snprintf((char*)key_ident, sizeof(key_ident), "ecdsa-sha2-%s", curve->name);
118 buf_putstring(buf, key_ident, strlen(key_ident));
119 buf_putstring(buf, curve->name, strlen(curve->name));
120 buf_put_ecc_raw_pubkey_string(buf, key);
121 }
122
123 void buf_put_ecdsa_priv_key(buffer *buf, ecc_key *key) {
124 buf_put_ecdsa_pub_key(buf, key);
125 buf_putmpint(buf, key->k);
126 }
127
128 void buf_put_ecdsa_sign(buffer *buf, ecc_key *key, buffer *data_buf) {
129 /* Based on libtomcrypt's ecc_sign_hash but without the asn1 */
130 int err = DROPBEAR_FAILURE;
131 struct dropbear_ecc_curve *curve = NULL;
132 hash_state hs;
133 unsigned char hash[64];
134 void *e = NULL, *p = NULL, *s = NULL, *r;
135 unsigned char key_ident[30];
136 buffer *sigbuf = NULL;
137
138 TRACE(("buf_put_ecdsa_sign"))
139 curve = curve_for_dp(key->dp);
140
141 if (ltc_init_multi(&r, &s, &p, &e, NULL) != CRYPT_OK) {
142 goto out;
143 }
144
145 curve->hash_desc->init(&hs);
146 curve->hash_desc->process(&hs, data_buf->data, data_buf->len);
147 curve->hash_desc->done(&hs, hash);
148
149 if (ltc_mp.unsigned_read(e, hash, curve->hash_desc->hashsize) != CRYPT_OK) {
150 goto out;
151 }
152
153 if (ltc_mp.read_radix(p, (char *)key->dp->order, 16) != CRYPT_OK) {
154 goto out;
155 }
156
157 for (;;) {
158 ecc_key R_key; // ephemeral key
159 if (ecc_make_key_ex(NULL, dropbear_ltc_prng, &R_key, key->dp) != CRYPT_OK) {
160 goto out;
161 }
162 if (ltc_mp.mpdiv(R_key.pubkey.x, p, NULL, r) != CRYPT_OK) {
163 goto out;
164 }
165 if (ltc_mp.compare_d(r, 0) == LTC_MP_EQ) {
166 // try again
167 ecc_free(&R_key);
168 continue;
169 }
170 /* k = 1/k */
171 if (ltc_mp.invmod(R_key.k, p, R_key.k) != CRYPT_OK) {
172 goto out;
173 }
174 /* s = xr */
175 if (ltc_mp.mulmod(key->k, r, p, s) != CRYPT_OK) {
176 goto out;
177 }
178 /* s = e + xr */
179 if (ltc_mp.add(e, s, s) != CRYPT_OK) {
180 goto out;
181 }
182 if (ltc_mp.mpdiv(s, p, NULL, s) != CRYPT_OK) {
183 goto out;
184 }
185 /* s = (e + xr)/k */
186 if (ltc_mp.mulmod(s, R_key.k, p, s) != CRYPT_OK) {
187 goto out;
188 }
189 ecc_free(&R_key);
190
191 if (ltc_mp.compare_d(s, 0) != LTC_MP_EQ) {
192 break;
193 }
194 }
195
196 snprintf((char*)key_ident, sizeof(key_ident), "ecdsa-sha2-%s", curve->name);
197 buf_putstring(buf, key_ident, strlen(key_ident));
198 // enough for nistp521
199 sigbuf = buf_new(200);
200 buf_putmpint(sigbuf, (mp_int*)r);
201 buf_putmpint(sigbuf, (mp_int*)s);
202 buf_putbufstring(buf, sigbuf);
203
204 err = DROPBEAR_SUCCESS;
205
206 out:
207 if (r && s && p && e) {
208 ltc_deinit_multi(r, s, p, e, NULL);
209 }
210
211 if (sigbuf) {
212 buf_free(sigbuf);
213 }
214
215 if (err == DROPBEAR_FAILURE) {
216 dropbear_exit("ECC error");
217 }
218 }
219
220 // returns values in s and r
221 // returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE
222 static int buf_get_ecdsa_verify_params(buffer *buf, struct dropbear_ecc_curve *curve,
223 void *r, void* s) {
224 int ret = DROPBEAR_FAILURE;
225 unsigned char* ident = NULL;
226 unsigned int ident_len;
227 unsigned int sig_len;
228 unsigned int sig_pos;
229 unsigned char key_ident[30];
230
231 ident = buf_getstring(buf, &ident_len);
232 snprintf((char*)key_ident, sizeof(key_ident), "ecdsa-sha2-%s", curve->name);
233 if (strlen((char*)key_ident) != ident_len) {
234 goto out;
235 }
236 if (memcmp(key_ident, ident, ident_len) != 0) {
237 goto out;
238 }
239 sig_len = buf_getint(buf);
240 sig_pos = buf->pos;
241 if (buf_getmpint(buf, r) != DROPBEAR_SUCCESS) {
242 goto out;
243 }
244 if (buf_getmpint(buf, s) != DROPBEAR_SUCCESS) {
245 goto out;
246 }
247 if (buf->pos - sig_pos != sig_len) {
248 goto out;
249 }
250 ret = DROPBEAR_SUCCESS;
251
252 out:
253 m_free(ident);
254 return ret;
255 }
256
257
258 int buf_ecdsa_verify(buffer *buf, ecc_key *key, buffer *data_buf) {
259 /* Based on libtomcrypt's ecc_verify_hash but without the asn1 */
260 int ret = DROPBEAR_FAILURE;
261 hash_state hs;
262 struct dropbear_ecc_curve *curve = NULL;
263 unsigned char hash[64];
264 ecc_point *mG = NULL, *mQ = NULL;
265 void *r = NULL, *s = NULL, *v = NULL, *w = NULL, *u1 = NULL, *u2 = NULL,
266 *e = NULL, *p = NULL, *m = NULL;
267 void *mp = NULL;
268
269 /* verify
270 *
271 * w = s^-1 mod n
272 * u1 = xw
273 * u2 = rw
274 * X = u1*G + u2*Q
275 * v = X_x1 mod n
276 * accept if v == r
277 */
278
279 TRACE(("buf_ecdsa_verify"))
280 curve = curve_for_dp(key->dp);
281
282 mG = ltc_ecc_new_point();
283 mQ = ltc_ecc_new_point();
284 if (ltc_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL) != CRYPT_OK
285 || !mG
286 || !mQ) {
287 dropbear_exit("ECC error");
288 }
289
290 if (buf_get_ecdsa_verify_params(buf, curve, r, s) != DROPBEAR_SUCCESS) {
291 goto out;
292 }
293
294 curve->hash_desc->init(&hs);
295 curve->hash_desc->process(&hs, data_buf->data, data_buf->len);
296 curve->hash_desc->done(&hs, hash);
297
298 if (ltc_mp.unsigned_read(e, hash, curve->hash_desc->hashsize) != CRYPT_OK) {
299 goto out;
300 }
301
302 /* get the order */
303 if (ltc_mp.read_radix(p, (char *)key->dp->order, 16) != CRYPT_OK) {
304 goto out;
305 }
306
307 /* get the modulus */
308 if (ltc_mp.read_radix(m, (char *)key->dp->prime, 16) != CRYPT_OK) {
309 goto out;
310 }
311
312 /* check for zero */
313 if (ltc_mp.compare_d(r, 0) == LTC_MP_EQ
314 || ltc_mp.compare_d(s, 0) == LTC_MP_EQ
315 || ltc_mp.compare(r, p) != LTC_MP_LT
316 || ltc_mp.compare(s, p) != LTC_MP_LT) {
317 goto out;
318 }
319
320 /* w = s^-1 mod n */
321 if (ltc_mp.invmod(s, p, w) != CRYPT_OK) {
322 goto out;
323 }
324
325 /* u1 = ew */
326 if (ltc_mp.mulmod(e, w, p, u1) != CRYPT_OK) {
327 goto out;
328 }
329
330 /* u2 = rw */
331 if (ltc_mp.mulmod(r, w, p, u2) != CRYPT_OK) {
332 goto out;
333 }
334
335 /* find mG and mQ */
336 if (ltc_mp.read_radix(mG->x, (char *)key->dp->Gx, 16) != CRYPT_OK) {
337 goto out;
338 }
339 if (ltc_mp.read_radix(mG->y, (char *)key->dp->Gy, 16) != CRYPT_OK) {
340 goto out;
341 }
342 if (ltc_mp.set_int(mG->z, 1) != CRYPT_OK) {
343 goto out;
344 }
345
346 if (ltc_mp.copy(key->pubkey.x, mQ->x) != CRYPT_OK
347 || ltc_mp.copy(key->pubkey.y, mQ->y) != CRYPT_OK
348 || ltc_mp.copy(key->pubkey.z, mQ->z) != CRYPT_OK) {
349 goto out;
350 }
351
352 /* compute u1*mG + u2*mQ = mG */
353 if (ltc_mp.ecc_mul2add == NULL) {
354 if (ltc_mp.ecc_ptmul(u1, mG, mG, m, 0) != CRYPT_OK) {
355 goto out;
356 }
357 if (ltc_mp.ecc_ptmul(u2, mQ, mQ, m, 0) != CRYPT_OK) {
358 goto out;
359 }
360
361 /* find the montgomery mp */
362 if (ltc_mp.montgomery_setup(m, &mp) != CRYPT_OK) {
363 goto out;
364 }
365
366 /* add them */
367 if (ltc_mp.ecc_ptadd(mQ, mG, mG, m, mp) != CRYPT_OK) {
368 goto out;
369 }
370
371 /* reduce */
372 if (ltc_mp.ecc_map(mG, m, mp) != CRYPT_OK) {
373 goto out;
374 }
375 } else {
376 /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */
377 if (ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, m) != CRYPT_OK) {
378 goto out;
379 }
380 }
381
382 /* v = X_x1 mod n */
383 if (ltc_mp.mpdiv(mG->x, p, NULL, v) != CRYPT_OK) {
384 goto out;
385 }
386
387 /* does v == r */
388 if (ltc_mp.compare(v, r) == LTC_MP_EQ) {
389 ret = DROPBEAR_SUCCESS;
390 }
391
392 out:
393 ltc_ecc_del_point(mG);
394 ltc_ecc_del_point(mQ);
395 mp_clear_multi(r, s, v, w, u1, u2, p, e, m, NULL);
396 if (mp != NULL) {
397 ltc_mp.montgomery_deinit(mp);
398 }
399 return ret;
400 }
401
402
99 403
100 #endif // DROPBEAR_ECDSA 404 #endif // DROPBEAR_ECDSA