Mercurial > dropbear

comparison rsa.c @ 640:76097ec1a29a dropbear-tfm

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
- Bring in original tomsfastmath patch against 0.52 from Peter Turczak in 2008
author Matt Johnston <matt@ucc.asn.au>
date Mon, 21 Nov 2011 19:19:57 +0800
parents a124aff0cbf1
children 2b1bb792cd4d
comparison
equal deleted inserted replaced
518:ce104c8b0be1 640:76097ec1a29a
38 38
39 #ifdef DROPBEAR_RSA 39 #ifdef DROPBEAR_RSA
40 40
41 static void rsa_pad_em(rsa_key * key, 41 static void rsa_pad_em(rsa_key * key,
42 const unsigned char * data, unsigned int len, 42 const unsigned char * data, unsigned int len,
43 mp_int * rsa_em); 43 fp_int * rsa_em);
44
44 45
45 /* Load a public rsa key from a buffer, initialising the values. 46 /* Load a public rsa key from a buffer, initialising the values.
46 * The key will have the same format as buf_put_rsa_key. 47 * The key will have the same format as buf_put_rsa_key.
47 * These should be freed with rsa_key_free. 48 * These should be freed with rsa_key_free.
48 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 49 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
49 int buf_get_rsa_pub_key(buffer* buf, rsa_key *key) { 50 int buf_get_rsa_pub_key(buffer* buf, rsa_key *key) {
50 51
51 int ret = DROPBEAR_FAILURE; 52 int ret = DROPBEAR_FAILURE;
52 TRACE(("enter buf_get_rsa_pub_key")) 53 TRACE(("enter buf_get_rsa_pub_key"))
53 dropbear_assert(key != NULL); 54 dropbear_assert(key != NULL);
54 key->e = m_malloc(sizeof(mp_int)); 55 key->e = m_malloc(sizeof(fp_int));
55 key->n = m_malloc(sizeof(mp_int)); 56 key->n = m_malloc(sizeof(fp_int));
56 m_mp_init_multi(key->e, key->n, NULL); 57 fp_init(key->e);
58 fp_init(key->n);
57 key->d = NULL; 59 key->d = NULL;
58 key->p = NULL; 60 key->p = NULL;
59 key->q = NULL; 61 key->q = NULL;
60 62
61 buf_incrpos(buf, 4+SSH_SIGNKEY_RSA_LEN); /* int + "ssh-rsa" */ 63 buf_incrpos(buf, 4+SSH_SIGNKEY_RSA_LEN); /* int + "ssh-rsa" */
62 64
63 if (buf_getmpint(buf, key->e) == DROPBEAR_FAILURE 65 if (buf_getfpint(buf, key->e) == DROPBEAR_FAILURE
64 || buf_getmpint(buf, key->n) == DROPBEAR_FAILURE) { 66 || buf_getfpint(buf, key->n) == DROPBEAR_FAILURE) {
65 TRACE(("leave buf_get_rsa_pub_key: failure")) 67 TRACE(("leave buf_get_rsa_pub_key: failure"))
66 goto out; 68 goto out;
67 } 69 }
68 70
69 if (mp_count_bits(key->n) < MIN_RSA_KEYLEN) { 71 if (fp_count_bits(key->n) < MIN_RSA_KEYLEN) {
70 dropbear_log(LOG_WARNING, "rsa key too short"); 72 dropbear_log(LOG_WARNING, "rsa key too short");
71 goto out; 73 goto out;
72 } 74 }
73 75
74 TRACE(("leave buf_get_rsa_pub_key: success")) 76 TRACE(("leave buf_get_rsa_pub_key: success"))
97 99
98 key->d = NULL; 100 key->d = NULL;
99 key->p = NULL; 101 key->p = NULL;
100 key->q = NULL; 102 key->q = NULL;
101 103
102 key->d = m_malloc(sizeof(mp_int)); 104 key->d = m_malloc(sizeof(fp_int));
103 m_mp_init(key->d); 105 fp_init(key->d);
104 if (buf_getmpint(buf, key->d) == DROPBEAR_FAILURE) { 106 if (buf_getfpint(buf, key->d) == DROPBEAR_FAILURE) {
105 TRACE(("leave buf_get_rsa_priv_key: d: ret == DROPBEAR_FAILURE")) 107 TRACE(("leave buf_get_rsa_priv_key: d: ret == DROPBEAR_FAILURE"))
106 goto out; 108 goto out;
107 } 109 }
108 110
109 if (buf->pos == buf->len) { 111 if (buf->pos == buf->len) {
110 /* old Dropbear private keys didn't keep p and q, so we will ignore them*/ 112 /* old Dropbear private keys didn't keep p and q, so we will ignore them*/
111 } else { 113 } else {
112 key->p = m_malloc(sizeof(mp_int)); 114 key->p = m_malloc(sizeof(fp_int));
113 key->q = m_malloc(sizeof(mp_int)); 115 key->q = m_malloc(sizeof(fp_int));
114 m_mp_init_multi(key->p, key->q, NULL); 116 fp_init(key->p);
115 117 fp_init(key->q);
116 if (buf_getmpint(buf, key->p) == DROPBEAR_FAILURE) { 118
119 if (buf_getfpint(buf, key->p) == DROPBEAR_FAILURE) {
117 TRACE(("leave buf_get_rsa_priv_key: p: ret == DROPBEAR_FAILURE")) 120 TRACE(("leave buf_get_rsa_priv_key: p: ret == DROPBEAR_FAILURE"))
118 goto out; 121 goto out;
119 } 122 }
120 123
121 if (buf_getmpint(buf, key->q) == DROPBEAR_FAILURE) { 124 if (buf_getfpint(buf, key->q) == DROPBEAR_FAILURE) {
122 TRACE(("leave buf_get_rsa_priv_key: q: ret == DROPBEAR_FAILURE")) 125 TRACE(("leave buf_get_rsa_priv_key: q: ret == DROPBEAR_FAILURE"))
123 goto out; 126 goto out;
124 } 127 }
125 } 128 }
126 129
144 if (key == NULL) { 147 if (key == NULL) {
145 TRACE(("leave rsa_key_free: key == NULL")) 148 TRACE(("leave rsa_key_free: key == NULL"))
146 return; 149 return;
147 } 150 }
148 if (key->d) { 151 if (key->d) {
149 mp_clear(key->d); 152 fp_zero(key->d);
150 m_free(key->d); 153 m_free(key->d);
151 } 154 }
152 if (key->e) { 155 if (key->e) {
153 mp_clear(key->e); 156 fp_zero(key->e);
154 m_free(key->e); 157 m_free(key->e);
155 } 158 }
156 if (key->n) { 159 if (key->n) {
157 mp_clear(key->n); 160 fp_zero(key->n);
158 m_free(key->n); 161 m_free(key->n);
159 } 162 }
160 if (key->p) { 163 if (key->p) {
161 mp_clear(key->p); 164 fp_zero(key->p);
162 m_free(key->p); 165 m_free(key->p);
163 } 166 }
164 if (key->q) { 167 if (key->q) {
165 mp_clear(key->q); 168 fp_zero(key->q);
166 m_free(key->q); 169 m_free(key->q);
167 } 170 }
168 m_free(key); 171 m_free(key);
169 TRACE(("leave rsa_key_free")) 172 TRACE(("leave rsa_key_free"))
170 } 173 }
171 174
172 /* Put the public rsa key into the buffer in the required format: 175 /* Put the public rsa key into the buffer in the required format:
173 * 176 *
174 * string "ssh-rsa" 177 * string "ssh-rsa"
175 * mp_int e 178 * fp_int e
176 * mp_int n 179 * fp_int n
177 */ 180 */
178 void buf_put_rsa_pub_key(buffer* buf, rsa_key *key) { 181 void buf_put_rsa_pub_key(buffer* buf, rsa_key *key) {
179 182
180 TRACE(("enter buf_put_rsa_pub_key")) 183 TRACE(("enter buf_put_rsa_pub_key"))
181 dropbear_assert(key != NULL); 184 dropbear_assert(key != NULL);
182 185
183 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN); 186 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN);
184 buf_putmpint(buf, key->e); 187 buf_putfpint(buf, key->e);
185 buf_putmpint(buf, key->n); 188 buf_putfpint(buf, key->n);
186 189
187 TRACE(("leave buf_put_rsa_pub_key")) 190 TRACE(("leave buf_put_rsa_pub_key"))
188 191
189 } 192 }
190 193
193 196
194 TRACE(("enter buf_put_rsa_priv_key")) 197 TRACE(("enter buf_put_rsa_priv_key"))
195 198
196 dropbear_assert(key != NULL); 199 dropbear_assert(key != NULL);
197 buf_put_rsa_pub_key(buf, key); 200 buf_put_rsa_pub_key(buf, key);
198 buf_putmpint(buf, key->d); 201 buf_putfpint(buf, key->d);
199 202
200 /* new versions have p and q, old versions don't */ 203 /* new versions have p and q, old versions don't */
201 if (key->p) { 204 if (key->p) {
202 buf_putmpint(buf, key->p); 205 buf_putfpint(buf, key->p);
203 } 206 }
204 if (key->q) { 207 if (key->q) {
205 buf_putmpint(buf, key->q); 208 buf_putfpint(buf, key->q);
206 } 209 }
207 210
208 211
209 TRACE(("leave buf_put_rsa_priv_key")) 212 TRACE(("leave buf_put_rsa_priv_key"))
210 213
215 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 218 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
216 int buf_rsa_verify(buffer * buf, rsa_key *key, const unsigned char* data, 219 int buf_rsa_verify(buffer * buf, rsa_key *key, const unsigned char* data,
217 unsigned int len) { 220 unsigned int len) {
218 221
219 unsigned int slen; 222 unsigned int slen;
220 DEF_MP_INT(rsa_s); 223 DEF_FP_INT(rsa_s);
221 DEF_MP_INT(rsa_mdash); 224 DEF_FP_INT(rsa_mdash);
222 DEF_MP_INT(rsa_em); 225 DEF_FP_INT(rsa_em);
223 int ret = DROPBEAR_FAILURE; 226 int ret = DROPBEAR_FAILURE;
224 227
225 TRACE(("enter buf_rsa_verify")) 228 TRACE(("enter buf_rsa_verify"))
226 229
227 dropbear_assert(key != NULL); 230 dropbear_assert(key != NULL);
228 231
229 m_mp_init_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL); 232 fp_init(&rsa_mdash);
233 fp_init(&rsa_s);
234 fp_init(&rsa_em);
230 235
231 slen = buf_getint(buf); 236 slen = buf_getint(buf);
232 if (slen != (unsigned int)mp_unsigned_bin_size(key->n)) { 237 if (slen != (unsigned int)fp_unsigned_bin_size(key->n)) {
233 TRACE(("bad size")) 238 TRACE(("bad size"))
234 goto out; 239 goto out;
235 } 240 }
236 241
237 if (mp_read_unsigned_bin(&rsa_s, buf_getptr(buf, buf->len - buf->pos), 242 fp_read_unsigned_bin(&rsa_s, buf_getptr(buf, buf->len - buf->pos),
238 buf->len - buf->pos) != MP_OKAY) { 243 buf->len - buf->pos);
239 TRACE(("failed reading rsa_s"))
240 goto out;
241 }
242 244
243 /* check that s <= n-1 */ 245 /* check that s <= n-1 */
244 if (mp_cmp(&rsa_s, key->n) != MP_LT) { 246 if (fp_cmp(&rsa_s, key->n) != FP_LT) {
245 TRACE(("s > n-1")) 247 TRACE(("s > n-1"))
246 goto out; 248 goto out;
247 } 249 }
248 250
249 /* create the magic PKCS padded value */ 251 /* create the magic PKCS padded value */
250 rsa_pad_em(key, data, len, &rsa_em); 252 rsa_pad_em(key, data, len, &rsa_em);
251 253
252 if (mp_exptmod(&rsa_s, key->e, key->n, &rsa_mdash) != MP_OKAY) { 254 if (fp_exptmod(&rsa_s, key->e, key->n, &rsa_mdash) != FP_OKAY) {
253 TRACE(("failed exptmod rsa_s")) 255 TRACE(("failed exptmod rsa_s"))
254 goto out; 256 goto out;
255 } 257 }
256 258
257 if (mp_cmp(&rsa_em, &rsa_mdash) == MP_EQ) { 259 if (fp_cmp(&rsa_em, &rsa_mdash) == FP_EQ) {
258 /* signature is valid */ 260 /* signature is valid */
259 TRACE(("success!")) 261 TRACE(("success!"))
260 ret = DROPBEAR_SUCCESS; 262 ret = DROPBEAR_SUCCESS;
261 } 263 }
262 264
263 out: 265 out:
264 mp_clear_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL); 266 fp_zero(&rsa_mdash);
267 fp_zero(&rsa_s);
268 fp_zero(&rsa_em);
269
265 TRACE(("leave buf_rsa_verify: ret %d", ret)) 270 TRACE(("leave buf_rsa_verify: ret %d", ret))
266 return ret; 271 return ret;
267 } 272 }
268 273
269 #endif /* DROPBEAR_SIGNKEY_VERIFY */ 274 #endif /* DROPBEAR_SIGNKEY_VERIFY */
273 void buf_put_rsa_sign(buffer* buf, rsa_key *key, const unsigned char* data, 278 void buf_put_rsa_sign(buffer* buf, rsa_key *key, const unsigned char* data,
274 unsigned int len) { 279 unsigned int len) {
275 280
276 unsigned int nsize, ssize; 281 unsigned int nsize, ssize;
277 unsigned int i; 282 unsigned int i;
278 DEF_MP_INT(rsa_s); 283 DEF_FP_INT(rsa_s);
279 DEF_MP_INT(rsa_tmp1); 284 DEF_FP_INT(rsa_tmp1);
280 DEF_MP_INT(rsa_tmp2); 285 DEF_FP_INT(rsa_tmp2);
281 DEF_MP_INT(rsa_tmp3); 286 DEF_FP_INT(rsa_tmp3);
282 287
283 TRACE(("enter buf_put_rsa_sign")) 288 TRACE(("enter buf_put_rsa_sign"))
284 dropbear_assert(key != NULL); 289 dropbear_assert(key != NULL);
285 290
286 m_mp_init_multi(&rsa_s, &rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL); 291 fp_init(&rsa_s);
292 fp_init(&rsa_tmp1);
293 fp_init(&rsa_tmp2);
294 fp_init(&rsa_tmp3);
287 295
288 rsa_pad_em(key, data, len, &rsa_tmp1); 296 rsa_pad_em(key, data, len, &rsa_tmp1);
289 297
290 /* the actual signing of the padded data */ 298 /* the actual signing of the padded data */
291 299
293 301
294 /* With blinding, s = (r^(-1))((em)*r^e)^d mod n */ 302 /* With blinding, s = (r^(-1))((em)*r^e)^d mod n */
295 303
296 /* generate the r blinding value */ 304 /* generate the r blinding value */
297 /* rsa_tmp2 is r */ 305 /* rsa_tmp2 is r */
298 gen_random_mpint(key->n, &rsa_tmp2); 306 gen_random_fpint(key->n, &rsa_tmp2);
299 307
300 /* rsa_tmp1 is em */ 308 /* rsa_tmp1 is em */
301 /* em' = em * r^e mod n */ 309 /* em' = em * r^e mod n */
302 310
303 /* rsa_s used as a temp var*/ 311 /* rsa_s used as a temp var*/
304 if (mp_exptmod(&rsa_tmp2, key->e, key->n, &rsa_s) != MP_OKAY) { 312 if (fp_exptmod(&rsa_tmp2, key->e, key->n, &rsa_s) != FP_OKAY) {
305 dropbear_exit("rsa error"); 313 dropbear_exit("rsa error");
306 } 314 }
307 if (mp_invmod(&rsa_tmp2, key->n, &rsa_tmp3) != MP_OKAY) { 315 if (fp_invmod(&rsa_tmp2, key->n, &rsa_tmp3) != FP_OKAY) {
308 dropbear_exit("rsa error"); 316 dropbear_exit("rsa error");
309 } 317 }
310 if (mp_mulmod(&rsa_tmp1, &rsa_s, key->n, &rsa_tmp2) != MP_OKAY) { 318 if (fp_mulmod(&rsa_tmp1, &rsa_s, key->n, &rsa_tmp2) != FP_OKAY) {
311 dropbear_exit("rsa error"); 319 dropbear_exit("rsa error");
312 } 320 }
313 321
314 /* rsa_tmp2 is em' */ 322 /* rsa_tmp2 is em' */
315 /* s' = (em')^d mod n */ 323 /* s' = (em')^d mod n */
316 if (mp_exptmod(&rsa_tmp2, key->d, key->n, &rsa_tmp1) != MP_OKAY) { 324 if (fp_exptmod(&rsa_tmp2, key->d, key->n, &rsa_tmp1) != FP_OKAY) {
317 dropbear_exit("rsa error"); 325 dropbear_exit("rsa error");
318 } 326 }
319 327
320 /* rsa_tmp1 is s' */ 328 /* rsa_tmp1 is s' */
321 /* rsa_tmp3 is r^(-1) mod n */ 329 /* rsa_tmp3 is r^(-1) mod n */
322 /* s = (s')r^(-1) mod n */ 330 /* s = (s')r^(-1) mod n */
323 if (mp_mulmod(&rsa_tmp1, &rsa_tmp3, key->n, &rsa_s) != MP_OKAY) { 331 if (fp_mulmod(&rsa_tmp1, &rsa_tmp3, key->n, &rsa_s) != FP_OKAY) {
324 dropbear_exit("rsa error"); 332 dropbear_exit("rsa error");
325 } 333 }
326 334
327 #else 335 #else
328 336
329 /* s = em^d mod n */ 337 /* s = em^d mod n */
330 /* rsa_tmp1 is em */ 338 /* rsa_tmp1 is em */
331 if (mp_exptmod(&rsa_tmp1, key->d, key->n, &rsa_s) != MP_OKAY) { 339 if (fp_exptmod(&rsa_tmp1, key->d, key->n, &rsa_s) != FP_OKAY) {
332 dropbear_exit("rsa error"); 340 dropbear_exit("rsa error");
333 } 341 }
334 342
335 #endif /* RSA_BLINDING */ 343 #endif /* RSA_BLINDING */
336 344
337 mp_clear_multi(&rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL); 345 fp_zero(&rsa_tmp1);
346 fp_zero(&rsa_tmp2);
347 fp_zero(&rsa_tmp3);
338 348
339 /* create the signature to return */ 349 /* create the signature to return */
340 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN); 350 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN);
341 351
342 nsize = mp_unsigned_bin_size(key->n); 352 nsize = fp_unsigned_bin_size(key->n);
343 353
344 /* string rsa_signature_blob length */ 354 /* string rsa_signature_blob length */
345 buf_putint(buf, nsize); 355 buf_putint(buf, nsize);
346 /* pad out s to same length as n */ 356 /* pad out s to same length as n */
347 ssize = mp_unsigned_bin_size(&rsa_s); 357 ssize = fp_unsigned_bin_size(&rsa_s);
348 dropbear_assert(ssize <= nsize); 358 dropbear_assert(ssize <= nsize);
349 for (i = 0; i < nsize-ssize; i++) { 359 for (i = 0; i < nsize-ssize; i++) {
350 buf_putbyte(buf, 0x00); 360 buf_putbyte(buf, 0x00);
351 } 361 }
352 362
353 if (mp_to_unsigned_bin(&rsa_s, buf_getwriteptr(buf, ssize)) != MP_OKAY) { 363 fp_to_unsigned_bin(&rsa_s, buf_getwriteptr(buf, ssize));
354 dropbear_exit("rsa error"); 364
355 }
356 buf_incrwritepos(buf, ssize); 365 buf_incrwritepos(buf, ssize);
357 mp_clear(&rsa_s); 366 fp_zero(&rsa_s);
358 367
359 #if defined(DEBUG_RSA) && defined(DEBUG_TRACE) 368 #if defined(DEBUG_RSA) && defined(DEBUG_TRACE)
360 printhex("RSA sig", buf->data, buf->len); 369 printhex("RSA sig", buf->data, buf->len);
361 #endif 370 #endif
362 371
372 * shorter than the size of key->n 381 * shorter than the size of key->n
373 * 382 *
374 * prefix is the ASN1 designator prefix, 383 * prefix is the ASN1 designator prefix,
375 * hex 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14 384 * hex 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14
376 * 385 *
377 * rsa_em must be a pointer to an initialised mp_int. 386 * rsa_em must be a pointer to an initialised fp_int.
378 */ 387 */
379 static void rsa_pad_em(rsa_key * key, 388 static void rsa_pad_em(rsa_key * key,
380 const unsigned char * data, unsigned int len, 389 const unsigned char * data, unsigned int len,
381 mp_int * rsa_em) { 390 fp_int * rsa_em) {
382 391
383 /* ASN1 designator (including the 0x00 preceding) */ 392 /* ASN1 designator (including the 0x00 preceding) */
384 const unsigned char rsa_asn1_magic[] = 393 const unsigned char rsa_asn1_magic[] =
385 {0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 394 {0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b,
386 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14}; 395 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14};
390 hash_state hs; 399 hash_state hs;
391 unsigned int nsize; 400 unsigned int nsize;
392 401
393 dropbear_assert(key != NULL); 402 dropbear_assert(key != NULL);
394 dropbear_assert(data != NULL); 403 dropbear_assert(data != NULL);
395 nsize = mp_unsigned_bin_size(key->n); 404 nsize = fp_unsigned_bin_size(key->n);
396 405
397 rsa_EM = buf_new(nsize-1); 406 rsa_EM = buf_new(nsize-1);
398 /* type byte */ 407 /* type byte */
399 buf_putbyte(rsa_EM, 0x01); 408 buf_putbyte(rsa_EM, 0x01);
400 /* Padding with 0xFF bytes */ 409 /* Padding with 0xFF bytes */
412 sha1_done(&hs, buf_getwriteptr(rsa_EM, SHA1_HASH_SIZE)); 421 sha1_done(&hs, buf_getwriteptr(rsa_EM, SHA1_HASH_SIZE));
413 buf_incrwritepos(rsa_EM, SHA1_HASH_SIZE); 422 buf_incrwritepos(rsa_EM, SHA1_HASH_SIZE);
414 423
415 dropbear_assert(rsa_EM->pos == rsa_EM->size); 424 dropbear_assert(rsa_EM->pos == rsa_EM->size);
416 425
417 /* Create the mp_int from the encoded bytes */ 426 /* Create the fp_int from the encoded bytes */
418 buf_setpos(rsa_EM, 0); 427 buf_setpos(rsa_EM, 0);
419 bytes_to_mp(rsa_em, buf_getptr(rsa_EM, rsa_EM->size), 428 bytes_to_fp(rsa_em, buf_getptr(rsa_EM, rsa_EM->size),
420 rsa_EM->size); 429 rsa_EM->size);
421 buf_free(rsa_EM); 430 buf_free(rsa_EM);
422 } 431 }
423 432
424 #endif /* DROPBEAR_RSA */ 433 #endif /* DROPBEAR_RSA */