Mercurial > dropbear

comparison rsa.c @ 285:1b9e69c058d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3) to branch 'au.asn.ucc.matt.dropbear' (head fdf4a7a3b97ae5046139915de7e40399cceb2c01)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 08 Mar 2006 13:23:58 +0000
parents 3cea9d789cca
children 454a34b2dfd1 9a789fc03f40
comparison
equal deleted inserted replaced
281:997e6f7dc01e 285:1b9e69c058d2
1 /*
2 * Dropbear - a SSH2 server
3 *
4 * Copyright (c) 2002,2003 Matt Johnston
5 * All rights reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE. */
24
25 /* Perform RSA operations on data, including reading keys, signing and
26 * verification.
27 *
28 * The format is specified in rfc2437, Applied Cryptography or The Handbook of
29 * Applied Cryptography detail the general algorithm. */
30
31 #include "includes.h"
32 #include "dbutil.h"
33 #include "bignum.h"
34 #include "rsa.h"
35 #include "buffer.h"
36 #include "ssh.h"
37 #include "random.h"
38
39 #ifdef DROPBEAR_RSA
40
41 static void rsa_pad_em(rsa_key * key,
42 const unsigned char * data, unsigned int len,
43 mp_int * rsa_em);
44
45 /* 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 * These should be freed with rsa_key_free.
48 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
49 int buf_get_rsa_pub_key(buffer* buf, rsa_key *key) {
50
51 TRACE(("enter buf_get_rsa_pub_key"))
52 dropbear_assert(key != NULL);
53 key->e = m_malloc(sizeof(mp_int));
54 key->n = m_malloc(sizeof(mp_int));
55 m_mp_init_multi(key->e, key->n, NULL);
56 key->d = NULL;
57 key->p = NULL;
58 key->q = NULL;
59
60 buf_incrpos(buf, 4+SSH_SIGNKEY_RSA_LEN); /* int + "ssh-rsa" */
61
62 if (buf_getmpint(buf, key->e) == DROPBEAR_FAILURE
63 || buf_getmpint(buf, key->n) == DROPBEAR_FAILURE) {
64 TRACE(("leave buf_get_rsa_pub_key: failure"))
65 return DROPBEAR_FAILURE;
66 }
67
68 if (mp_count_bits(key->n) < MIN_RSA_KEYLEN) {
69 dropbear_log(LOG_WARNING, "rsa key too short");
70 return DROPBEAR_FAILURE;
71 }
72
73 TRACE(("leave buf_get_rsa_pub_key: success"))
74 return DROPBEAR_SUCCESS;
75
76 }
77
78 /* Same as buf_get_rsa_pub_key, but reads a private "x" key at the end.
79 * Loads a private rsa key from a buffer
80 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
81 int buf_get_rsa_priv_key(buffer* buf, rsa_key *key) {
82
83 dropbear_assert(key != NULL);
84
85 TRACE(("enter buf_get_rsa_priv_key"))
86
87 if (buf_get_rsa_pub_key(buf, key) == DROPBEAR_FAILURE) {
88 TRACE(("leave buf_get_rsa_priv_key: pub: ret == DROPBEAR_FAILURE"))
89 return DROPBEAR_FAILURE;
90 }
91
92 key->d = m_malloc(sizeof(mp_int));
93 m_mp_init(key->d);
94 if (buf_getmpint(buf, key->d) == DROPBEAR_FAILURE) {
95 TRACE(("leave buf_get_rsa_priv_key: d: ret == DROPBEAR_FAILURE"))
96 return DROPBEAR_FAILURE;
97 }
98
99 /* old Dropbear private keys didn't keep p and q, so we will ignore them*/
100 if (buf->pos == buf->len) {
101 key->p = NULL;
102 key->q = NULL;
103 } else {
104 key->p = m_malloc(sizeof(mp_int));
105 key->q = m_malloc(sizeof(mp_int));
106 m_mp_init_multi(key->p, key->q, NULL);
107
108 if (buf_getmpint(buf, key->p) == DROPBEAR_FAILURE) {
109 TRACE(("leave buf_get_rsa_priv_key: p: ret == DROPBEAR_FAILURE"))
110 return DROPBEAR_FAILURE;
111 }
112
113 if (buf_getmpint(buf, key->q) == DROPBEAR_FAILURE) {
114 TRACE(("leave buf_get_rsa_priv_key: q: ret == DROPBEAR_FAILURE"))
115 return DROPBEAR_FAILURE;
116 }
117 }
118
119 TRACE(("leave buf_get_rsa_priv_key"))
120 return DROPBEAR_SUCCESS;
121 }
122
123
124 /* Clear and free the memory used by a public or private key */
125 void rsa_key_free(rsa_key *key) {
126
127 TRACE(("enter rsa_key_free"))
128
129 if (key == NULL) {
130 TRACE(("leave rsa_key_free: key == NULL"))
131 return;
132 }
133 if (key->d) {
134 mp_clear(key->d);
135 m_free(key->d);
136 }
137 if (key->e) {
138 mp_clear(key->e);
139 m_free(key->e);
140 }
141 if (key->n) {
142 mp_clear(key->n);
143 m_free(key->n);
144 }
145 if (key->p) {
146 mp_clear(key->p);
147 m_free(key->p);
148 }
149 if (key->q) {
150 mp_clear(key->q);
151 m_free(key->q);
152 }
153 m_free(key);
154 TRACE(("leave rsa_key_free"))
155 }
156
157 /* Put the public rsa key into the buffer in the required format:
158 *
159 * string "ssh-rsa"
160 * mp_int e
161 * mp_int n
162 */
163 void buf_put_rsa_pub_key(buffer* buf, rsa_key *key) {
164
165 TRACE(("enter buf_put_rsa_pub_key"))
166 dropbear_assert(key != NULL);
167
168 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN);
169 buf_putmpint(buf, key->e);
170 buf_putmpint(buf, key->n);
171
172 TRACE(("leave buf_put_rsa_pub_key"))
173
174 }
175
176 /* Same as buf_put_rsa_pub_key, but with the private "x" key appended */
177 void buf_put_rsa_priv_key(buffer* buf, rsa_key *key) {
178
179 TRACE(("enter buf_put_rsa_priv_key"))
180
181 dropbear_assert(key != NULL);
182 buf_put_rsa_pub_key(buf, key);
183 buf_putmpint(buf, key->d);
184
185 /* new versions have p and q, old versions don't */
186 if (key->p) {
187 buf_putmpint(buf, key->p);
188 }
189 if (key->q) {
190 buf_putmpint(buf, key->q);
191 }
192
193
194 TRACE(("leave buf_put_rsa_priv_key"))
195
196 }
197
198 #ifdef DROPBEAR_SIGNKEY_VERIFY
199 /* Verify a signature in buf, made on data by the key given.
200 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
201 int buf_rsa_verify(buffer * buf, rsa_key *key, const unsigned char* data,
202 unsigned int len) {
203
204 unsigned int slen;
205 DEF_MP_INT(rsa_s);
206 DEF_MP_INT(rsa_mdash);
207 DEF_MP_INT(rsa_em);
208 int ret = DROPBEAR_FAILURE;
209
210 TRACE(("enter buf_rsa_verify"))
211
212 dropbear_assert(key != NULL);
213
214 m_mp_init_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL);
215
216 slen = buf_getint(buf);
217 if (slen != (unsigned int)mp_unsigned_bin_size(key->n)) {
218 TRACE(("bad size"))
219 goto out;
220 }
221
222 if (mp_read_unsigned_bin(&rsa_s, buf_getptr(buf, buf->len - buf->pos),
223 buf->len - buf->pos) != MP_OKAY) {
224 TRACE(("failed reading rsa_s"))
225 goto out;
226 }
227
228 /* check that s <= n-1 */
229 if (mp_cmp(&rsa_s, key->n) != MP_LT) {
230 TRACE(("s > n-1"))
231 goto out;
232 }
233
234 /* create the magic PKCS padded value */
235 rsa_pad_em(key, data, len, &rsa_em);
236
237 if (mp_exptmod(&rsa_s, key->e, key->n, &rsa_mdash) != MP_OKAY) {
238 TRACE(("failed exptmod rsa_s"))
239 goto out;
240 }
241
242 if (mp_cmp(&rsa_em, &rsa_mdash) == MP_EQ) {
243 /* signature is valid */
244 TRACE(("success!"))
245 ret = DROPBEAR_SUCCESS;
246 }
247
248 out:
249 mp_clear_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL);
250 TRACE(("leave buf_rsa_verify: ret %d", ret))
251 return ret;
252 }
253
254 #endif /* DROPBEAR_SIGNKEY_VERIFY */
255
256 /* Sign the data presented with key, writing the signature contents
257 * to the buffer */
258 void buf_put_rsa_sign(buffer* buf, rsa_key *key, const unsigned char* data,
259 unsigned int len) {
260
261 unsigned int nsize, ssize;
262 unsigned int i;
263 DEF_MP_INT(rsa_s);
264 DEF_MP_INT(rsa_tmp1);
265 DEF_MP_INT(rsa_tmp2);
266 DEF_MP_INT(rsa_tmp3);
267
268 TRACE(("enter buf_put_rsa_sign"))
269 dropbear_assert(key != NULL);
270
271 m_mp_init_multi(&rsa_s, &rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL);
272
273 rsa_pad_em(key, data, len, &rsa_tmp1);
274
275 /* the actual signing of the padded data */
276
277 #ifdef RSA_BLINDING
278
279 /* With blinding, s = (r^(-1))((em)*r^e)^d mod n */
280
281 /* generate the r blinding value */
282 /* rsa_tmp2 is r */
283 gen_random_mpint(key->n, &rsa_tmp2);
284
285 /* rsa_tmp1 is em */
286 /* em' = em * r^e mod n */
287
288 mp_exptmod(&rsa_tmp2, key->e, key->n, &rsa_s); /* rsa_s used as a temp var*/
289 mp_invmod(&rsa_tmp2, key->n, &rsa_tmp3);
290 mp_mulmod(&rsa_tmp1, &rsa_s, key->n, &rsa_tmp2);
291
292 /* rsa_tmp2 is em' */
293 /* s' = (em')^d mod n */
294 mp_exptmod(&rsa_tmp2, key->d, key->n, &rsa_tmp1);
295
296 /* rsa_tmp1 is s' */
297 /* rsa_tmp3 is r^(-1) mod n */
298 /* s = (s')r^(-1) mod n */
299 mp_mulmod(&rsa_tmp1, &rsa_tmp3, key->n, &rsa_s);
300
301 #else
302
303 /* s = em^d mod n */
304 /* rsa_tmp1 is em */
305 if (mp_exptmod(&rsa_tmp1, key->d, key->n, &rsa_s) != MP_OKAY) {
306 dropbear_exit("rsa error");
307 }
308
309 #endif /* RSA_BLINDING */
310
311 mp_clear_multi(&rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL);
312
313 /* create the signature to return */
314 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN);
315
316 nsize = mp_unsigned_bin_size(key->n);
317
318 /* string rsa_signature_blob length */
319 buf_putint(buf, nsize);
320 /* pad out s to same length as n */
321 ssize = mp_unsigned_bin_size(&rsa_s);
322 dropbear_assert(ssize <= nsize);
323 for (i = 0; i < nsize-ssize; i++) {
324 buf_putbyte(buf, 0x00);
325 }
326
327 if (mp_to_unsigned_bin(&rsa_s, buf_getwriteptr(buf, ssize)) != MP_OKAY) {
328 dropbear_exit("rsa error");
329 }
330 buf_incrwritepos(buf, ssize);
331 mp_clear(&rsa_s);
332
333 #if defined(DEBUG_RSA) && defined(DEBUG_TRACE)
334 printhex("RSA sig", buf->data, buf->len);
335 #endif
336
337
338 TRACE(("leave buf_put_rsa_sign"))
339 }
340
341 /* Creates the message value as expected by PKCS, see rfc2437 etc */
342 /* format to be padded to is:
343 * EM = 01 | FF* | 00 | prefix | hash
344 *
345 * where FF is repeated enough times to make EM one byte
346 * shorter than the size of key->n
347 *
348 * prefix is the ASN1 designator prefix,
349 * hex 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14
350 *
351 * rsa_em must be a pointer to an initialised mp_int.
352 */
353 static void rsa_pad_em(rsa_key * key,
354 const unsigned char * data, unsigned int len,
355 mp_int * rsa_em) {
356
357 /* ASN1 designator (including the 0x00 preceding) */
358 const unsigned char rsa_asn1_magic[] =
359 {0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b,
360 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14};
361 const unsigned int RSA_ASN1_MAGIC_LEN = 16;
362
363 buffer * rsa_EM = NULL;
364 hash_state hs;
365 unsigned int nsize;
366
367 dropbear_assert(key != NULL);
368 dropbear_assert(data != NULL);
369 nsize = mp_unsigned_bin_size(key->n);
370
371 rsa_EM = buf_new(nsize-1);
372 /* type byte */
373 buf_putbyte(rsa_EM, 0x01);
374 /* Padding with 0xFF bytes */
375 while(rsa_EM->pos != rsa_EM->size - RSA_ASN1_MAGIC_LEN - SHA1_HASH_SIZE) {
376 buf_putbyte(rsa_EM, 0xff);
377 }
378 /* Magic ASN1 stuff */
379 memcpy(buf_getwriteptr(rsa_EM, RSA_ASN1_MAGIC_LEN),
380 rsa_asn1_magic, RSA_ASN1_MAGIC_LEN);
381 buf_incrwritepos(rsa_EM, RSA_ASN1_MAGIC_LEN);
382
383 /* The hash of the data */
384 sha1_init(&hs);
385 sha1_process(&hs, data, len);
386 sha1_done(&hs, buf_getwriteptr(rsa_EM, SHA1_HASH_SIZE));
387 buf_incrwritepos(rsa_EM, SHA1_HASH_SIZE);
388
389 dropbear_assert(rsa_EM->pos == rsa_EM->size);
390
391 /* Create the mp_int from the encoded bytes */
392 buf_setpos(rsa_EM, 0);
393 bytes_to_mp(rsa_em, buf_getptr(rsa_EM, rsa_EM->size),
394 rsa_EM->size);
395 buf_free(rsa_EM);
396 }
397
398 #endif /* DROPBEAR_RSA */