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 int ret = DROPBEAR_FAILURE; 52 TRACE(("enter buf_get_rsa_pub_key")) 53 dropbear_assert(key != NULL); 54 key->e = m_malloc(sizeof(mp_int)); 55 key->n = m_malloc(sizeof(mp_int)); 56 m_mp_init_multi(key->e, key->n, NULL); 57 key->d = NULL; 58 key->p = NULL; 59 key->q = NULL; 60 61 buf_incrpos(buf, 4+SSH_SIGNKEY_RSA_LEN); /* int + "ssh-rsa" */ 62 63 if (buf_getmpint(buf, key->e) == DROPBEAR_FAILURE 64 || buf_getmpint(buf, key->n) == DROPBEAR_FAILURE) { 65 TRACE(("leave buf_get_rsa_pub_key: failure")) 66 goto out; 67 } 68 69 if (mp_count_bits(key->n) < MIN_RSA_KEYLEN) { 70 dropbear_log(LOG_WARNING, "rsa key too short"); 71 goto out; 72 } 73 74 TRACE(("leave buf_get_rsa_pub_key: success")) 75 ret = DROPBEAR_SUCCESS; 76 out: 77 if (ret == DROPBEAR_FAILURE) { 78 m_free(key->e); 79 m_free(key->n); 80 } 81 return ret; 82 } 83 84 /* Same as buf_get_rsa_pub_key, but reads private bits at the end. 85 * Loads a private rsa key from a buffer 86 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 87 int buf_get_rsa_priv_key(buffer* buf, rsa_key *key) { 88 int ret = DROPBEAR_FAILURE; 89 90 TRACE(("enter buf_get_rsa_priv_key")) 91 dropbear_assert(key != NULL); 92 93 if (buf_get_rsa_pub_key(buf, key) == DROPBEAR_FAILURE) { 94 TRACE(("leave buf_get_rsa_priv_key: pub: ret == DROPBEAR_FAILURE")) 95 return DROPBEAR_FAILURE; 96 } 97 98 key->d = NULL; 99 key->p = NULL; 100 key->q = NULL; 101 102 key->d = m_malloc(sizeof(mp_int)); 103 m_mp_init(key->d); 104 if (buf_getmpint(buf, key->d) == DROPBEAR_FAILURE) { 105 TRACE(("leave buf_get_rsa_priv_key: d: ret == DROPBEAR_FAILURE")) 106 goto out; 107 } 108 109 if (buf->pos == buf->len) { 110 /* old Dropbear private keys didn't keep p and q, so we will ignore them*/ 111 } else { 112 key->p = m_malloc(sizeof(mp_int)); 113 key->q = m_malloc(sizeof(mp_int)); 114 m_mp_init_multi(key->p, key->q, NULL); 115 116 if (buf_getmpint(buf, key->p) == DROPBEAR_FAILURE) { 117 TRACE(("leave buf_get_rsa_priv_key: p: ret == DROPBEAR_FAILURE")) 118 goto out; 119 } 120 121 if (buf_getmpint(buf, key->q) == DROPBEAR_FAILURE) { 122 TRACE(("leave buf_get_rsa_priv_key: q: ret == DROPBEAR_FAILURE")) 123 goto out; 124 } 125 } 126 127 ret = DROPBEAR_SUCCESS; 128 out: 129 if (ret == DROPBEAR_FAILURE) { 130 m_free(key->d); 131 m_free(key->p); 132 m_free(key->q); 133 } 134 TRACE(("leave buf_get_rsa_priv_key")) 135 return ret; 136 } 137 138 139 /* Clear and free the memory used by a public or private key */ 140 void rsa_key_free(rsa_key *key) { 141 142 TRACE(("enter rsa_key_free")) 143 144 if (key == NULL) { 145 TRACE(("leave rsa_key_free: key == NULL")) 146 return; 147 } 148 if (key->d) { 149 mp_clear(key->d); 150 m_free(key->d); 151 } 152 if (key->e) { 153 mp_clear(key->e); 154 m_free(key->e); 155 } 156 if (key->n) { 157 mp_clear(key->n); 158 m_free(key->n); 159 } 160 if (key->p) { 161 mp_clear(key->p); 162 m_free(key->p); 163 } 164 if (key->q) { 165 mp_clear(key->q); 166 m_free(key->q); 167 } 168 m_free(key); 169 TRACE(("leave rsa_key_free")) 170 } 171 172 /* Put the public rsa key into the buffer in the required format: 173 * 174 * string "ssh-rsa" 175 * mp_int e 176 * mp_int n 177 */ 178 void buf_put_rsa_pub_key(buffer* buf, rsa_key *key) { 179 180 TRACE(("enter buf_put_rsa_pub_key")) 181 dropbear_assert(key != NULL); 182 183 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN); 184 buf_putmpint(buf, key->e); 185 buf_putmpint(buf, key->n); 186 187 TRACE(("leave buf_put_rsa_pub_key")) 188 189 } 190 191 /* Same as buf_put_rsa_pub_key, but with the private "x" key appended */ 192 void buf_put_rsa_priv_key(buffer* buf, rsa_key *key) { 193 194 TRACE(("enter buf_put_rsa_priv_key")) 195 196 dropbear_assert(key != NULL); 197 buf_put_rsa_pub_key(buf, key); 198 buf_putmpint(buf, key->d); 199 200 /* new versions have p and q, old versions don't */ 201 if (key->p) { 202 buf_putmpint(buf, key->p); 203 } 204 if (key->q) { 205 buf_putmpint(buf, key->q); 206 } 207 208 209 TRACE(("leave buf_put_rsa_priv_key")) 210 211 } 212 213 #ifdef DROPBEAR_SIGNKEY_VERIFY 214 /* Verify a signature in buf, made on data by the key given. 215 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 216 int buf_rsa_verify(buffer * buf, rsa_key *key, const unsigned char* data, 217 unsigned int len) { 218 219 unsigned int slen; 220 DEF_MP_INT(rsa_s); 221 DEF_MP_INT(rsa_mdash); 222 DEF_MP_INT(rsa_em); 223 int ret = DROPBEAR_FAILURE; 224 225 TRACE(("enter buf_rsa_verify")) 226 227 dropbear_assert(key != NULL); 228 229 m_mp_init_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL); 230 231 slen = buf_getint(buf); 232 if (slen != (unsigned int)mp_unsigned_bin_size(key->n)) { 233 TRACE(("bad size")) 234 goto out; 235 } 236 237 if (mp_read_unsigned_bin(&rsa_s, buf_getptr(buf, buf->len - buf->pos), 238 buf->len - buf->pos) != MP_OKAY) { 239 TRACE(("failed reading rsa_s")) 240 goto out; 241 } 242 243 /* check that s <= n-1 */ 244 if (mp_cmp(&rsa_s, key->n) != MP_LT) { 245 TRACE(("s > n-1")) 246 goto out; 247 } 248 249 /* create the magic PKCS padded value */ 250 rsa_pad_em(key, data, len, &rsa_em); 251 252 if (mp_exptmod(&rsa_s, key->e, key->n, &rsa_mdash) != MP_OKAY) { 253 TRACE(("failed exptmod rsa_s")) 254 goto out; 255 } 256 257 if (mp_cmp(&rsa_em, &rsa_mdash) == MP_EQ) { 258 /* signature is valid */ 259 TRACE(("success!")) 260 ret = DROPBEAR_SUCCESS; 261 } 262 263 out: 264 mp_clear_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL); 265 TRACE(("leave buf_rsa_verify: ret %d", ret)) 266 return ret; 267 } 268 269 #endif /* DROPBEAR_SIGNKEY_VERIFY */ 270 271 /* Sign the data presented with key, writing the signature contents 272 * to the buffer */ 273 void buf_put_rsa_sign(buffer* buf, rsa_key *key, const unsigned char* data, 274 unsigned int len) { 275 276 unsigned int nsize, ssize; 277 unsigned int i; 278 DEF_MP_INT(rsa_s); 279 DEF_MP_INT(rsa_tmp1); 280 DEF_MP_INT(rsa_tmp2); 281 DEF_MP_INT(rsa_tmp3); 282 283 TRACE(("enter buf_put_rsa_sign")) 284 dropbear_assert(key != NULL); 285 286 m_mp_init_multi(&rsa_s, &rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL); 287 288 rsa_pad_em(key, data, len, &rsa_tmp1); 289 290 /* the actual signing of the padded data */ 291 292 #ifdef RSA_BLINDING 293 294 /* With blinding, s = (r^(-1))((em)*r^e)^d mod n */ 295 296 /* generate the r blinding value */ 297 /* rsa_tmp2 is r */ 298 gen_random_mpint(key->n, &rsa_tmp2); 299 300 /* rsa_tmp1 is em */ 301 /* em' = em * r^e mod n */ 302 303 /* rsa_s used as a temp var*/ 304 if (mp_exptmod(&rsa_tmp2, key->e, key->n, &rsa_s) != MP_OKAY) { 305 dropbear_exit("rsa error"); 306 } 307 if (mp_invmod(&rsa_tmp2, key->n, &rsa_tmp3) != MP_OKAY) { 308 dropbear_exit("rsa error"); 309 } 310 if (mp_mulmod(&rsa_tmp1, &rsa_s, key->n, &rsa_tmp2) != MP_OKAY) { 311 dropbear_exit("rsa error"); 312 } 313 314 /* rsa_tmp2 is em' */ 315 /* s' = (em')^d mod n */ 316 if (mp_exptmod(&rsa_tmp2, key->d, key->n, &rsa_tmp1) != MP_OKAY) { 317 dropbear_exit("rsa error"); 318 } 319 320 /* rsa_tmp1 is s' */ 321 /* rsa_tmp3 is r^(-1) mod n */ 322 /* s = (s')r^(-1) mod n */ 323 if (mp_mulmod(&rsa_tmp1, &rsa_tmp3, key->n, &rsa_s) != MP_OKAY) { 324 dropbear_exit("rsa error"); 325 } 326 327 #else 328 329 /* s = em^d mod n */ 330 /* rsa_tmp1 is em */ 331 if (mp_exptmod(&rsa_tmp1, key->d, key->n, &rsa_s) != MP_OKAY) { 332 dropbear_exit("rsa error"); 333 } 334 335 #endif /* RSA_BLINDING */ 336 337 mp_clear_multi(&rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL); 338 339 /* create the signature to return */ 340 buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN); 341 342 nsize = mp_unsigned_bin_size(key->n); 343 344 /* string rsa_signature_blob length */ 345 buf_putint(buf, nsize); 346 /* pad out s to same length as n */ 347 ssize = mp_unsigned_bin_size(&rsa_s); 348 dropbear_assert(ssize <= nsize); 349 for (i = 0; i < nsize-ssize; i++) { 350 buf_putbyte(buf, 0x00); 351 } 352 353 if (mp_to_unsigned_bin(&rsa_s, buf_getwriteptr(buf, ssize)) != MP_OKAY) { 354 dropbear_exit("rsa error"); 355 } 356 buf_incrwritepos(buf, ssize); 357 mp_clear(&rsa_s); 358 359 #if defined(DEBUG_RSA) && defined(DEBUG_TRACE) 360 printhex("RSA sig", buf->data, buf->len); 361 #endif 362 363 364 TRACE(("leave buf_put_rsa_sign")) 365 } 366 367 /* Creates the message value as expected by PKCS, see rfc2437 etc */ 368 /* format to be padded to is: 369 * EM = 01 | FF* | 00 | prefix | hash 370 * 371 * where FF is repeated enough times to make EM one byte 372 * shorter than the size of key->n 373 * 374 * prefix is the ASN1 designator prefix, 375 * hex 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14 376 * 377 * rsa_em must be a pointer to an initialised mp_int. 378 */ 379 static void rsa_pad_em(rsa_key * key, 380 const unsigned char * data, unsigned int len, 381 mp_int * rsa_em) { 382 383 /* ASN1 designator (including the 0x00 preceding) */ 384 const unsigned char rsa_asn1_magic[] = 385 {0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 386 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14}; 387 const unsigned int RSA_ASN1_MAGIC_LEN = 16; 388 389 buffer * rsa_EM = NULL; 390 hash_state hs; 391 unsigned int nsize; 392 393 dropbear_assert(key != NULL); 394 dropbear_assert(data != NULL); 395 nsize = mp_unsigned_bin_size(key->n); 396 397 rsa_EM = buf_new(nsize-1); 398 /* type byte */ 399 buf_putbyte(rsa_EM, 0x01); 400 /* Padding with 0xFF bytes */ 401 while(rsa_EM->pos != rsa_EM->size - RSA_ASN1_MAGIC_LEN - SHA1_HASH_SIZE) { 402 buf_putbyte(rsa_EM, 0xff); 403 } 404 /* Magic ASN1 stuff */ 405 memcpy(buf_getwriteptr(rsa_EM, RSA_ASN1_MAGIC_LEN), 406 rsa_asn1_magic, RSA_ASN1_MAGIC_LEN); 407 buf_incrwritepos(rsa_EM, RSA_ASN1_MAGIC_LEN); 408 409 /* The hash of the data */ 410 sha1_init(&hs); 411 sha1_process(&hs, data, len); 412 sha1_done(&hs, buf_getwriteptr(rsa_EM, SHA1_HASH_SIZE)); 413 buf_incrwritepos(rsa_EM, SHA1_HASH_SIZE); 414 415 dropbear_assert(rsa_EM->pos == rsa_EM->size); 416 417 /* Create the mp_int from the encoded bytes */ 418 buf_setpos(rsa_EM, 0); 419 bytes_to_mp(rsa_em, buf_getptr(rsa_EM, rsa_EM->size), 420 rsa_EM->size); 421 buf_free(rsa_EM); 422 } 423 424 #endif /* DROPBEAR_RSA */ 425
