Mercurial > dropbear

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