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 #include "includes.h" 26 #include "dbutil.h" 27 #include "bignum.h" 28 #include "dss.h" 29 #include "buffer.h" 30 #include "ssh.h" 31 #include "random.h" 32 33 /* Handle DSS (Digital Signature Standard), aka DSA (D.S. Algorithm), 34 * operations, such as key reading, signing, verification. Key generation 35 * is in gendss.c, since it isn't required in the server itself. 36 * 37 * See FIPS186 or the Handbook of Applied Cryptography for details of the 38 * algorithm */ 39 40 #ifdef DROPBEAR_DSS 41 42 /* Load a dss key from a buffer, initialising the values. 43 * The key will have the same format as buf_put_dss_key. 44 * These should be freed with dss_key_free. 45 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 46 int buf_get_dss_pub_key(buffer* buf, dss_key *key) { 47 48 TRACE(("enter buf_get_dss_pub_key")) 49 dropbear_assert(key != NULL); 50 key->p = m_malloc(sizeof(mp_int)); 51 key->q = m_malloc(sizeof(mp_int)); 52 key->g = m_malloc(sizeof(mp_int)); 53 key->y = m_malloc(sizeof(mp_int)); 54 m_mp_init_multi(key->p, key->q, key->g, key->y, NULL); 55 key->x = NULL; 56 57 buf_incrpos(buf, 4+SSH_SIGNKEY_DSS_LEN); /* int + "ssh-dss" */ 58 if (buf_getmpint(buf, key->p) == DROPBEAR_FAILURE 59 || buf_getmpint(buf, key->q) == DROPBEAR_FAILURE 60 || buf_getmpint(buf, key->g) == DROPBEAR_FAILURE 61 || buf_getmpint(buf, key->y) == DROPBEAR_FAILURE) { 62 TRACE(("leave buf_get_dss_pub_key: failed reading mpints")) 63 return DROPBEAR_FAILURE; 64 } 65 66 if (mp_count_bits(key->p) < MIN_DSS_KEYLEN) { 67 dropbear_log(LOG_WARNING, "DSS key too short"); 68 TRACE(("leave buf_get_dss_pub_key: short key")) 69 return DROPBEAR_FAILURE; 70 } 71 72 TRACE(("leave buf_get_dss_pub_key: success")) 73 return DROPBEAR_SUCCESS; 74 } 75 76 /* Same as buf_get_dss_pub_key, but reads a private "x" key at the end. 77 * Loads a private dss key from a buffer 78 * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 79 int buf_get_dss_priv_key(buffer* buf, dss_key *key) { 80 81 int ret = DROPBEAR_FAILURE; 82 83 dropbear_assert(key != NULL); 84 85 ret = buf_get_dss_pub_key(buf, key); 86 if (ret == DROPBEAR_FAILURE) { 87 return DROPBEAR_FAILURE; 88 } 89 90 key->x = m_malloc(sizeof(mp_int)); 91 m_mp_init(key->x); 92 ret = buf_getmpint(buf, key->x); 93 if (ret == DROPBEAR_FAILURE) { 94 m_free(key->x); 95 } 96 97 return ret; 98 } 99 100 101 /* Clear and free the memory used by a public or private key */ 102 void dss_key_free(dss_key *key) { 103 104 TRACE(("enter dsa_key_free")) 105 if (key == NULL) { 106 TRACE(("enter dsa_key_free: key == NULL")) 107 return; 108 } 109 if (key->p) { 110 mp_clear(key->p); 111 m_free(key->p); 112 } 113 if (key->q) { 114 mp_clear(key->q); 115 m_free(key->q); 116 } 117 if (key->g) { 118 mp_clear(key->g); 119 m_free(key->g); 120 } 121 if (key->y) { 122 mp_clear(key->y); 123 m_free(key->y); 124 } 125 if (key->x) { 126 mp_clear(key->x); 127 m_free(key->x); 128 } 129 m_free(key); 130 TRACE(("leave dsa_key_free")) 131 } 132 133 /* put the dss public key into the buffer in the required format: 134 * 135 * string "ssh-dss" 136 * mpint p 137 * mpint q 138 * mpint g 139 * mpint y 140 */ 141 void buf_put_dss_pub_key(buffer* buf, dss_key *key) { 142 143 dropbear_assert(key != NULL); 144 buf_putstring(buf, SSH_SIGNKEY_DSS, SSH_SIGNKEY_DSS_LEN); 145 buf_putmpint(buf, key->p); 146 buf_putmpint(buf, key->q); 147 buf_putmpint(buf, key->g); 148 buf_putmpint(buf, key->y); 149 150 } 151 152 /* Same as buf_put_dss_pub_key, but with the private "x" key appended */ 153 void buf_put_dss_priv_key(buffer* buf, dss_key *key) { 154 155 dropbear_assert(key != NULL); 156 buf_put_dss_pub_key(buf, key); 157 buf_putmpint(buf, key->x); 158 159 } 160 161 #ifdef DROPBEAR_SIGNKEY_VERIFY 162 /* Verify a DSS signature (in buf) made on data by the key given. 163 * returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ 164 int buf_dss_verify(buffer* buf, dss_key *key, const unsigned char* data, 165 unsigned int len) { 166 167 unsigned char msghash[SHA1_HASH_SIZE]; 168 hash_state hs; 169 int ret = DROPBEAR_FAILURE; 170 DEF_MP_INT(val1); 171 DEF_MP_INT(val2); 172 DEF_MP_INT(val3); 173 DEF_MP_INT(val4); 174 char * string = NULL; 175 int stringlen; 176 177 TRACE(("enter buf_dss_verify")) 178 dropbear_assert(key != NULL); 179 180 m_mp_init_multi(&val1, &val2, &val3, &val4, NULL); 181 182 /* get blob, check length */ 183 string = buf_getstring(buf, &stringlen); 184 if (stringlen != 2*SHA1_HASH_SIZE) { 185 goto out; 186 } 187 188 /* hash the data */ 189 sha1_init(&hs); 190 sha1_process(&hs, data, len); 191 sha1_done(&hs, msghash); 192 193 /* create the signature - s' and r' are the received signatures in buf */ 194 /* w = (s')-1 mod q */ 195 /* let val1 = s' */ 196 bytes_to_mp(&val1, &string[SHA1_HASH_SIZE], SHA1_HASH_SIZE); 197 198 if (mp_cmp(&val1, key->q) != MP_LT) { 199 TRACE(("verify failed, s' >= q")) 200 goto out; 201 } 202 /* let val2 = w = (s')^-1 mod q*/ 203 if (mp_invmod(&val1, key->q, &val2) != MP_OKAY) { 204 goto out; 205 } 206 207 /* u1 = ((SHA(M')w) mod q */ 208 /* let val1 = SHA(M') = msghash */ 209 bytes_to_mp(&val1, msghash, SHA1_HASH_SIZE); 210 211 /* let val3 = u1 = ((SHA(M')w) mod q */ 212 if (mp_mulmod(&val1, &val2, key->q, &val3) != MP_OKAY) { 213 goto out; 214 } 215 216 /* u2 = ((r')w) mod q */ 217 /* let val1 = r' */ 218 bytes_to_mp(&val1, &string[0], SHA1_HASH_SIZE); 219 if (mp_cmp(&val1, key->q) != MP_LT) { 220 TRACE(("verify failed, r' >= q")) 221 goto out; 222 } 223 /* let val4 = u2 = ((r')w) mod q */ 224 if (mp_mulmod(&val1, &val2, key->q, &val4) != MP_OKAY) { 225 goto out; 226 } 227 228 /* v = (((g)^u1 (y)^u2) mod p) mod q */ 229 /* val2 = g^u1 mod p */ 230 if (mp_exptmod(key->g, &val3, key->p, &val2) != MP_OKAY) { 231 goto out; 232 } 233 /* val3 = y^u2 mod p */ 234 if (mp_exptmod(key->y, &val4, key->p, &val3) != MP_OKAY) { 235 goto out; 236 } 237 /* val4 = ((g)^u1 (y)^u2) mod p */ 238 if (mp_mulmod(&val2, &val3, key->p, &val4) != MP_OKAY) { 239 goto out; 240 } 241 /* val2 = v = (((g)^u1 (y)^u2) mod p) mod q */ 242 if (mp_mod(&val4, key->q, &val2) != MP_OKAY) { 243 goto out; 244 } 245 246 /* check whether signatures verify */ 247 if (mp_cmp(&val2, &val1) == MP_EQ) { 248 /* good sig */ 249 ret = DROPBEAR_SUCCESS; 250 } 251 252 out: 253 mp_clear_multi(&val1, &val2, &val3, &val4, NULL); 254 m_free(string); 255 256 return ret; 257 258 } 259 #endif /* DROPBEAR_SIGNKEY_VERIFY */ 260 261 #ifdef DSS_PROTOK 262 /* convert an unsigned mp into an array of bytes, malloced. 263 * This array must be freed after use, len contains the length of the array, 264 * if len != NULL */ 265 static unsigned char* mptobytes(mp_int *mp, int *len) { 266 267 unsigned char* ret; 268 int size; 269 270 size = mp_unsigned_bin_size(mp); 271 ret = m_malloc(size); 272 if (mp_to_unsigned_bin(mp, ret) != MP_OKAY) { 273 dropbear_exit("mem alloc error"); 274 } 275 if (len != NULL) { 276 *len = size; 277 } 278 return ret; 279 } 280 #endif 281 282 /* Sign the data presented with key, writing the signature contents 283 * to the buffer 284 * 285 * When DSS_PROTOK is #defined: 286 * The alternate k generation method is based on the method used in PuTTY. 287 * In particular to avoid being vulnerable to attacks using flaws in random 288 * generation of k, we use the following: 289 * 290 * proto_k = SHA512 ( SHA512(x) || SHA160(message) ) 291 * k = proto_k mod q 292 * 293 * Now we aren't relying on the random number generation to protect the private 294 * key x, which is a long term secret */ 295 void buf_put_dss_sign(buffer* buf, dss_key *key, const unsigned char* data, 296 unsigned int len) { 297 298 unsigned char msghash[SHA1_HASH_SIZE]; 299 unsigned int writelen; 300 unsigned int i; 301 #ifdef DSS_PROTOK 302 unsigned char privkeyhash[SHA512_HASH_SIZE]; 303 unsigned char *privkeytmp; 304 unsigned char proto_k[SHA512_HASH_SIZE]; 305 DEF_MP_INT(dss_protok); 306 #endif 307 DEF_MP_INT(dss_k); 308 DEF_MP_INT(dss_m); 309 DEF_MP_INT(dss_temp1); 310 DEF_MP_INT(dss_temp2); 311 DEF_MP_INT(dss_r); 312 DEF_MP_INT(dss_s); 313 hash_state hs; 314 315 TRACE(("enter buf_put_dss_sign")) 316 dropbear_assert(key != NULL); 317 318 /* hash the data */ 319 sha1_init(&hs); 320 sha1_process(&hs, data, len); 321 sha1_done(&hs, msghash); 322 323 m_mp_init_multi(&dss_k, &dss_temp1, &dss_temp2, &dss_r, &dss_s, 324 &dss_m, NULL); 325 #ifdef DSS_PROTOK 326 /* hash the privkey */ 327 privkeytmp = mptobytes(key->x, &i); 328 sha512_init(&hs); 329 sha512_process(&hs, "the quick brown fox jumped over the lazy dog", 44); 330 sha512_process(&hs, privkeytmp, i); 331 sha512_done(&hs, privkeyhash); 332 m_burn(privkeytmp, i); 333 m_free(privkeytmp); 334 335 /* calculate proto_k */ 336 sha512_init(&hs); 337 sha512_process(&hs, privkeyhash, SHA512_HASH_SIZE); 338 sha512_process(&hs, msghash, SHA1_HASH_SIZE); 339 sha512_done(&hs, proto_k); 340 341 /* generate k */ 342 m_mp_init(&dss_protok); 343 bytes_to_mp(&dss_protok, proto_k, SHA512_HASH_SIZE); 344 if (mp_mod(&dss_protok, key->q, &dss_k) != MP_OKAY) { 345 dropbear_exit("dss error"); 346 } 347 mp_clear(&dss_protok); 348 m_burn(proto_k, SHA512_HASH_SIZE); 349 #else /* DSS_PROTOK not defined*/ 350 gen_random_mpint(key->q, &dss_k); 351 #endif 352 353 /* now generate the actual signature */ 354 bytes_to_mp(&dss_m, msghash, SHA1_HASH_SIZE); 355 356 /* g^k mod p */ 357 if (mp_exptmod(key->g, &dss_k, key->p, &dss_temp1) != MP_OKAY) { 358 dropbear_exit("dss error"); 359 } 360 /* r = (g^k mod p) mod q */ 361 if (mp_mod(&dss_temp1, key->q, &dss_r) != MP_OKAY) { 362 dropbear_exit("dss error"); 363 } 364 365 /* x*r mod q */ 366 if (mp_mulmod(&dss_r, key->x, key->q, &dss_temp1) != MP_OKAY) { 367 dropbear_exit("dss error"); 368 } 369 /* (SHA1(M) + xr) mod q) */ 370 if (mp_addmod(&dss_m, &dss_temp1, key->q, &dss_temp2) != MP_OKAY) { 371 dropbear_exit("dss error"); 372 } 373 374 /* (k^-1) mod q */ 375 if (mp_invmod(&dss_k, key->q, &dss_temp1) != MP_OKAY) { 376 dropbear_exit("dss error"); 377 } 378 379 /* s = (k^-1(SHA1(M) + xr)) mod q */ 380 if (mp_mulmod(&dss_temp1, &dss_temp2, key->q, &dss_s) != MP_OKAY) { 381 dropbear_exit("dss error"); 382 } 383 384 buf_putstring(buf, SSH_SIGNKEY_DSS, SSH_SIGNKEY_DSS_LEN); 385 buf_putint(buf, 2*SHA1_HASH_SIZE); 386 387 writelen = mp_unsigned_bin_size(&dss_r); 388 dropbear_assert(writelen <= SHA1_HASH_SIZE); 389 /* need to pad to 160 bits with leading zeros */ 390 for (i = 0; i < SHA1_HASH_SIZE - writelen; i++) { 391 buf_putbyte(buf, 0); 392 } 393 if (mp_to_unsigned_bin(&dss_r, buf_getwriteptr(buf, writelen)) 394 != MP_OKAY) { 395 dropbear_exit("dss error"); 396 } 397 mp_clear(&dss_r); 398 buf_incrwritepos(buf, writelen); 399 400 writelen = mp_unsigned_bin_size(&dss_s); 401 dropbear_assert(writelen <= SHA1_HASH_SIZE); 402 /* need to pad to 160 bits with leading zeros */ 403 for (i = 0; i < SHA1_HASH_SIZE - writelen; i++) { 404 buf_putbyte(buf, 0); 405 } 406 if (mp_to_unsigned_bin(&dss_s, buf_getwriteptr(buf, writelen)) 407 != MP_OKAY) { 408 dropbear_exit("dss error"); 409 } 410 mp_clear(&dss_s); 411 buf_incrwritepos(buf, writelen); 412 413 mp_clear_multi(&dss_k, &dss_temp1, &dss_temp2, &dss_r, &dss_s, 414 &dss_m, NULL); 415 416 /* create the signature to return */ 417 418 TRACE(("leave buf_put_dss_sign")) 419 } 420 421 #endif /* DROPBEAR_DSS */ 422
