Mercurial > dropbear
comparison rsa.c @ 284:eed26cff980b
propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
to branch 'au.asn.ucc.matt.dropbear' (head fff0894a0399405a9410ea1c6d118f342cf2aa64)
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Wed, 08 Mar 2006 13:23:49 +0000 |
parents | 3cea9d789cca |
children | 454a34b2dfd1 9a789fc03f40 |
comparison
equal
deleted
inserted
replaced
283:bd240aa12ba7 | 284:eed26cff980b |
---|---|
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 */ |