Mercurial > dropbear
comparison ecdsa.c @ 793:70625eed40c9 ecc
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 |