publickey_crypto.c 13.9 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
2
/* publickey_crypto.c
 *
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 *
 *
 * $Id$ */

/* lsh, an implementation of the ssh protocol
 *
 * Copyright (C) 1998 Niels Mller
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
Niels Möller's avatar
Niels Möller committed
24
25
26
 */

#include "atoms.h"
27
28
29
30
#include "bignum.h"
#include "crypto.h"
#include "format.h"
#include "parse.h"
Niels Möller's avatar
Niels Möller committed
31
#include "publickey_crypto.h"
32
33
34
35
#include "sha.h"
#include "ssh.h"
#include "werror.h"
#include "xalloc.h"
Niels Möller's avatar
Niels Möller committed
36
37

/* DSS signatures */
Niels Möller's avatar
Niels Möller committed
38
39
40

struct dss_public
{
Niels Möller's avatar
Niels Möller committed
41
42
43
44
  mpz_t p;
  mpz_t q;
  mpz_t g;
  mpz_t y;
Niels Möller's avatar
Niels Möller committed
45
46
47
48
49
50
51
};

struct dss_signer
{
  struct signer super;
  struct randomness *random;
  struct dss_public public;
52
  mpz_t a; 		/* Private key */
Niels Möller's avatar
Niels Möller committed
53
54
55
56
57
58
59
60
61
62
63
64
65
66
};

struct dss_verifier
{
  struct verifier super;
  struct dss_public public;
};
  
struct dss_algorithm
{
  struct signature_algorithm super;
  struct randomness *random;
};

Niels Möller's avatar
Niels Möller committed
67
static void dss_hash(mpz_t h, UINT32 length, UINT8 *msg)
68
69
{
  /* Compute hash */
70
71
72
  struct hash_instance *hash = MAKE_HASH(&sha_algorithm);
  UINT8 *digest = alloca(hash->hash_size);
  HASH_UPDATE(hash, length, msg);
73
  HASH_DIGEST(hash, digest);
Niels Möller's avatar
Niels Möller committed
74

75
  bignum_parse_u(h, hash->hash_size, digest);
76
77
78
79

  lsh_free(hash);
}

80
static struct lsh_string *do_dss_sign(struct signer *c,
81
82
				      UINT32 length,
				      UINT8 *msg)
Niels Möller's avatar
Niels Möller committed
83
{
84
  struct dss_signer *closure = (struct dss_signer *) c;
Niels Möller's avatar
Niels Möller committed
85
  mpz_t k, r, s, tmp;
Niels Möller's avatar
Niels Möller committed
86
87
88
89
90
91
92
  struct lsh_string *signature;
  
  /* Select k, 0<k<q, randomly */
  mpz_init_set(tmp, closure->public.q);
  mpz_sub_ui(tmp, tmp, 1);

  mpz_init(k);
93
  bignum_random(k, closure->random, tmp);
Niels Möller's avatar
Niels Möller committed
94
95
  mpz_add_ui(k, k, 1);

96
  /* Compute r = (g^k (mod p)) (mod q) */
Niels Möller's avatar
Niels Möller committed
97
  mpz_init(r);
98
99
  mpz_powm(r, closure->public.g, k, closure->public.p);
  mpz_tdiv_r(r, r, closure->public.q);
Niels Möller's avatar
Niels Möller committed
100
101
  
  /* Compute hash */
102
  dss_hash(tmp, length, msg);
Niels Möller's avatar
Niels Möller committed
103
104

  /* Compute k^-1 (mod q) */
105
106
107
108
109
110
111
112
  if (!mpz_invert(k, k, closure->public.q))
    {
      werror("do_dss_sign: k non-invertible\n");
      mpz_clear(tmp);
      mpz_clear(k);
      mpz_clear(r);
      return NULL;
    }
Niels Möller's avatar
Niels Möller committed
113
114
115

  /* Compute signature s = k^-1(h + ar) (mod q) */
  mpz_init(s);
116
  mpz_mul(s, r, closure->a);
Niels Möller's avatar
Niels Möller committed
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
  mpz_tdiv_r(s, s, closure->public.q);
  mpz_add(s, s, tmp);
  mpz_mul(s, s, k);
  mpz_tdiv_r(s, s, closure->public.q);
  
  /* Build signature */
  signature = ssh_format("%a%n%n", ATOM_SSH_DSS, r, s);

  mpz_clear(k);
  mpz_clear(r);
  mpz_clear(s);
  mpz_clear(tmp);

  return signature;
}

Niels Möller's avatar
Niels Möller committed
133
134
135
136
137
138
static struct lsh_string *dss_public_key(struct signer *dss)
{
  struct 
  return ssh_format("%a%n%n%n%n", ATOM_SSH_DSS, dss->p, dss->q, dss->g, dss->y);
}

139
int do_dss_verify(struct verifier *c,
Niels Möller's avatar
Niels Möller committed
140
		  UINT32 length,
141
		  UINT8 *msg,
Niels Möller's avatar
Niels Möller committed
142
143
144
		  UINT32 signature_length,
		  UINT8 * signature_data)
{
145
  struct dss_signer *closure = (struct dss_signer *) c;
Niels Möller's avatar
Niels Möller committed
146
147
  struct simple_buffer buffer;

148
149
  int res;
  
Niels Möller's avatar
Niels Möller committed
150
  int atom;
Niels Möller's avatar
Niels Möller committed
151
  mpz_t r, s;
152

153
  mpz_t w, tmp, v;
Niels Möller's avatar
Niels Möller committed
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
  
  simple_buffer_init(&buffer, signature_length, signature_data);
  if (!parse_atom(&buffer, &atom)
      || (atom != ATOM_SSH_DSS) )
    return 0;

  mpz_init(r);
  mpz_init(s);
  if (! (parse_bignum(&buffer, r)
	 && parse_bignum(&buffer, s)
	 && parse_eod(&buffer)
	 && (mpz_sgn(r) == 1)
	 && (mpz_sgn(s) == 1)
	 && (mpz_cmp(r, closure->public.q) < 0)
	 && (mpz_cmp(s, closure->public.q) < 0) ))
    {
      mpz_clear(r);
      mpz_clear(s);
      return 0;
    }

175
176
  /* Compute w = s^-1 (mod q) */
  mpz_init(w);
177
  if (!mpz_invert(w, s, closure->public.q))
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
    {
      werror("do_dss_verify: s non-invertible.\n");
      mpz_clear(r);
      mpz_clear(s);
      mpz_clear(w);
      return 0;
    }

  /* Compute hash */
  mpz_init(tmp);
  dss_hash(tmp, length, msg);

  /* g^{w * h (mod q)} (mod p)  */

  mpz_init(v);

  mpz_mul(tmp, tmp, w);
  mpz_tdiv_r(tmp, tmp, closure->public.q);

  mpz_powm(v, closure->public.g, tmp, closure->public.p);

  /* y^{w * r (mod q) } (mod p) */
  mpz_mul(tmp, r, w);
  mpz_tdiv_r(tmp, tmp, closure->public.q);
  mpz_powm(tmp, closure->public.y, tmp, closure->public.p);

  /* (g^{w * h} * y^{w * r} (mod p) ) (mod q) */
  mpz_mul(v, v, tmp);
  mpz_tdiv_r(v, v, closure->public.q);

  res = mpz_cmp(v, r);

  mpz_clear(r);
  mpz_clear(s);
  mpz_clear(w);
  mpz_clear(tmp);
  mpz_clear(v);

  return !res;
}

int parse_dss_public(struct simple_buffer *buffer, struct dss_public *public)
{
#if 0
  mpz_init(public->p);
  mpz_init(public->q);
  mpz_init(public->g);
  mpz_init(public->y);
#endif
  
228
229
  return (parse_bignum(buffer, public->p)
	  && parse_bignum(buffer, public->p)
230
	  && (mpz_sgn(public->p) == 1)
231
	  && parse_bignum(buffer, public->q)
232
233
	  && (mpz_sgn(public->q) == 1)
	  && (mpz_cmp(public->q, public->p) < 0) /* q < p */ 
234
	  && parse_bignum(buffer, public->g)
235
236
	  && (mpz_sgn(public->g) == 1)
	  && (mpz_cmp(public->g, public->p) < 0) /* g < p */ 
237
	  && parse_bignum(buffer, public->y) 
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
	  && (mpz_sgn(public->y) == 1)
	  && (mpz_cmp(public->y, public->p) < 0) /* y < p */  );
#if 0
      mpz_clear(public->p);
      mpz_clear(public->q);
      mpz_clear(public->g);
      mpz_clear(public->y);
      return 0;
#endif
}

/* FIXME: Outside of the protocol transactions, keys should be stored
 * in SPKI-style S-expressions. */
struct signer *make_dss_signer(struct signature_algorithm *closure,
			       UINT32 public_length,
			       UINT8 *public,
254
255
			       UINT32 private_length,
			       UINT8 *private)
256
257
{
  struct dss_signer *res;
258
259
  struct simple_buffer public_buffer;
  struct simple_buffer private_buffer;  
260
261
  int atom;

262
263
  simple_buffer_init(&public_buffer, public_length, public);
  if (!parse_atom(&public_buffer, &atom)
264
265
      || (atom != ATOM_SSH_DSS) )
    return 0;
266
267
  
  simple_buffer_init(&private_buffer, private_length, private);
268
269
270
271
272
273
274

  res = xalloc(sizeof(struct dss_signer));

  mpz_init(res->public.p);
  mpz_init(res->public.q);
  mpz_init(res->public.g);
  mpz_init(res->public.y);
275
  mpz_init(res->a);
276
  
277
278
  if (! (parse_dss_public(&public_buffer, &res->public)
  	 && parse_bignum(&private_buffer, res->a)
279
	 /* FIXME: Perhaps do some more sanity checks? */
280
281
	 && (mpz_sgn(res->a) == 1)
	 && parse_eod(&private_buffer) ))
282
283
284
285
286
    {
      mpz_clear(res->public.p);
      mpz_clear(res->public.q);
      mpz_clear(res->public.g);
      mpz_clear(res->public.y);
287
      mpz_clear(res->a);
288
289
290
      lsh_free(res);
      return NULL;
    }
Niels Möller's avatar
Niels Möller committed
291
  
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
  res->super.sign = do_dss_sign;
  return &res->super;
}

struct verifier *make_dss_verifier(struct signature_algorithm *closure,
				   UINT32 public_length,
				   UINT8 *public)
{
  struct dss_verifier *res;
  struct simple_buffer buffer;
  int atom;

  simple_buffer_init(&buffer, public_length, public);
  if (!parse_atom(&buffer, &atom)
      || (atom != ATOM_SSH_DSS) )
    return 0;

  res = xalloc(sizeof(struct dss_verifier));
Niels Möller's avatar
Niels Möller committed
310

311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
  mpz_init(res->public.p);
  mpz_init(res->public.q);
  mpz_init(res->public.g);
  mpz_init(res->public.y);
  
  if (!parse_dss_public(&buffer, &res->public))
    /* FIXME: Perhaps do some more sanity checks? */
    {
      mpz_clear(res->public.p);
      mpz_clear(res->public.q);
      mpz_clear(res->public.g);
      mpz_clear(res->public.y);
          lsh_free(res);
      return NULL;
    }

  res->super.verify = do_dss_verify;
  return &res->super;
}

331
struct signature_algorithm *make_dss_algorithm(struct randomness *random)
332
{
333
  struct dss_algorithm *dss = xalloc(sizeof(struct dss_algorithm));
334
335
336
337
338
339
340
341

  dss->super.make_signer = make_dss_signer;
  dss->super.make_verifier = make_dss_verifier;
  dss->random = random;

  return &dss->super;
}
    
Niels Möller's avatar
Niels Möller committed
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
/* Groups */

struct group_zn  /* Z_n^* */
{
  struct group super;
  mpz_t modulo;
};

static int zn_member(struct group *c, mpz_t x)
{
  struct group_zn *closure = (struct group_zn *) c;

  return ( (mpz_sgn(x) == 1) && (mpz_cmp(x, closure->modulo) < 0) );
}

static void zn_invert(struct group *c, mpz_t res, mpz_t x)
{
  struct group_zn *closure = (struct group_zn *) c;

  if (!mpz_invert(res, x, closure->modulo))
    fatal("zn_invert: element is non-invertible\n");
}

static void zn_combine(struct group *c, mpz_t res, mpz_t a, mpz_t b)
{
  struct group_zn *closure = (struct group_zn *) c;

  mpz_mul(res, a, b);
  mpz_tdiv_r(res, res, closure->modulo);
}

static void zn_power(struct group *c, mpz_t res, mpz_t g, mpz_t e)
{
  struct group_zn *closure = (struct group_zn *) c;

  mpz_powm(res, g, e, closure->modulo);
}

/* Assumes p is a prime number */
struct group *make_zn(mpz_t p)
{
  struct group_zn *res = xalloc(sizeof(struct group_zn));

  res->super.member = zn_member;
  res->super.invert = zn_invert;
  res->super.combine = zn_combine;
  res->super.power = zn_power;     /* Pretty Mutation! Magical Recall! */
  
390
391
392
  mpz_init_set(res->modulo, p);
  mpz_init_set(res->super.order, p);
  mpz_sub_ui(res->super.order, res->super.order, 1);
Niels Möller's avatar
Niels Möller committed
393
394
395
396
397
  return &res->super;
}

/* diffie-hellman */

398
399
400
401
402
403
404
405
406
407
408
void init_diffie_hellman_instance(struct diffie_hellman_method *m,
				  struct diffie_hellman_instance *self,
				  struct ssh_connection *c)
{
  mpz_init(self->e);
  mpz_init(self->f);
  mpz_init(self->secret);
  mpz_init(self->K);
  
  self->method = m;
  self->hash = MAKE_HASH(m->H);
409
410
  self->exchange_hash = NULL;
  
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
  HASH_UPDATE(self->hash,
	      c->client_version->length,
	      c->client_version->data);
  HASH_UPDATE(self->hash,
	      c->server_version->length,
	      c->server_version->data);
  HASH_UPDATE(self->hash,
	      c->literal_kexinits[CONNECTION_CLIENT]->length,
	      c->literal_kexinits[CONNECTION_CLIENT]->data);
  HASH_UPDATE(self->hash,
	      c->literal_kexinits[CONNECTION_SERVER]->length,
	      c->literal_kexinits[CONNECTION_SERVER]->data);
  
  lsh_string_free(c->literal_kexinits[CONNECTION_CLIENT]);
  lsh_string_free(c->literal_kexinits[CONNECTION_SERVER]);

  c->literal_kexinits[CONNECTION_SERVER] = NULL;
  c->literal_kexinits[CONNECTION_CLIENT] = NULL;
}

Niels Möller's avatar
Niels Möller committed
431
432
struct diffie_hellman_instance *
make_diffie_hellman_instance(struct diffie_hellman_method *m,
433
			     struct ssh_connection *c)
Niels Möller's avatar
Niels Möller committed
434
435
436
437
{
  struct diffie_hellman_instance *res
    = xalloc(sizeof(struct diffie_hellman_instance));

438
439
  init_diffie_hellman_instance(m, res, c);

Niels Möller's avatar
Niels Möller committed
440
441
442
  return res;
}

443
struct diffie_hellman_method *make_dh1(struct randomness *r)
Niels Möller's avatar
Niels Möller committed
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
{
  struct diffie_hellman_method *res
    = xalloc(sizeof(struct diffie_hellman_method));

  mpz_t p;
  
  mpz_init_set_str(p,
		   "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
		   "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
		   "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
		   "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
		   "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
		   "FFFFFFFFFFFFFFFF", 16);

  res->G = make_zn(p);
  mpz_clear(p);

  mpz_init_set_ui(res->generator, 2);

463
  res->H = &sha_algorithm;
Niels Möller's avatar
Niels Möller committed
464
465
466
467
468
469
470
471
472
473
  res->random = r;
  
  return res;
}

void dh_generate_secret(struct diffie_hellman_instance *self,
			mpz_t r)
{
  mpz_t tmp;

474
475
476
477
478
  /* Generate a random number, 1 < x <= p-1 = O(G) */
  mpz_init_set(tmp, self->method->G->order);  
  mpz_sub_ui(tmp, tmp, 1);
  bignum_random(self->secret, self->method->random, tmp);
  mpz_add_ui(self->secret, self->secret, 1);
Niels Möller's avatar
Niels Möller committed
479
480
  mpz_clear(tmp);

481
  GROUP_POWER(self->method->G, r, self->method->generator, self->secret);
Niels Möller's avatar
Niels Möller committed
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
}

struct lsh_string *dh_make_client_msg(struct diffie_hellman_instance *self)
{
  dh_generate_secret(self, self->e);
  return ssh_format("%c%n", SSH_MSG_KEXDH_INIT, self->e);
}

int dh_process_client_msg(struct diffie_hellman_instance *self,
			  struct lsh_string *packet)
{
  struct simple_buffer buffer;
  UINT8 msg_number;
  
  simple_buffer_init(&buffer, packet->length, packet->data);

498
499
500
501
502
503
504
505
506
507
  if (! (parse_uint8(&buffer, &msg_number)
	 && (msg_number == SSH_MSG_KEXDH_INIT)
	 && parse_bignum(&buffer, self->e)
	 && (mpz_cmp_ui(self->e, 1) > 0)
	 && (mpz_cmp(self->e, self->method->G->order) <= 0)
	 && parse_eod(&buffer) ))
    return 0;

  GROUP_POWER(self->method->G, self->K, self->e, self->secret);
  return 1;
Niels Möller's avatar
Niels Möller committed
508
509
510
511
512
513
514
515
516
517
518
}

void dh_hash_update(struct diffie_hellman_instance *self,
		    struct lsh_string *packet)
{
  HASH_UPDATE(self->hash, packet->length, packet->data);
}

/* Hashes server key, e and f */
void dh_hash_digest(struct diffie_hellman_instance *self, UINT8 *digest)
{
519
520
521
522
  struct lsh_string *s = ssh_format("%S%n%n%n",
				    self->server_key,
				    self->e, self->f,
				    self->K);
Niels Möller's avatar
Niels Möller committed
523
524
525
526

  HASH_UPDATE(self->hash, s->length, s->data);
  lsh_string_free(s);

527
  HASH_DIGEST(self->hash, digest);
Niels Möller's avatar
Niels Möller committed
528
529
530
531
532
533
534
}

struct lsh_string *dh_make_server_msg(struct diffie_hellman_instance *self,
				      struct signer *s)
{
  dh_generate_secret(self, self->f);

535
536
  self->exchange_hash = lsh_string_alloc(self->hash->hash_size);
  
Niels Möller's avatar
Niels Möller committed
537
  dh_hash_digest(self, self->exchange_hash->data);
Niels Möller's avatar
Niels Möller committed
538
539
540
541

  return ssh_format("%c%S%n%fS",
		    SSH_MSG_KEXDH_REPLY,
		    self->server_key,
542
543
544
		    self->f, SIGN(s,
				  self->exchange_hash->length,
				  self->exchange_hash->data));
Niels Möller's avatar
Niels Möller committed
545
546
547
548
549
550
551
552
553
554
}

int dh_process_server_msg(struct diffie_hellman_instance *self,
			  struct lsh_string *packet)
{
  struct simple_buffer buffer;
  UINT8 msg_number;
  
  simple_buffer_init(&buffer, packet->length, packet->data);

555
556
557
558
559
560
561
562
563
564
565
566
  if (!(parse_uint8(&buffer, &msg_number)
	&& (msg_number == SSH_MSG_KEXDH_REPLY)
	&& (self->server_key = parse_string_copy(&buffer))
	&& (parse_bignum(&buffer, self->f))
	&& (mpz_cmp_ui(self->f, 1) > 0)
	&& (mpz_cmp(self->f, self->method->G->order) <= 0)
	&& (self->signature = parse_string_copy(&buffer))
	&& parse_eod(&buffer)))
    return 0;

  GROUP_POWER(self->method->G, self->K, self->f, self->secret);
  return 1;
Niels Möller's avatar
Niels Möller committed
567
568
569
570
571
572
573
574
}
	  
int dh_verify_server_msg(struct diffie_hellman_instance *self,
			 struct verifier *v)
{
  UINT8 *digest;
  
  digest = alloca(self->hash->hash_size);
575
  dh_hash_digest(self, digest);
Niels Möller's avatar
Niels Möller committed
576
577
578
579

  return VERIFY(v, self->hash->hash_size, digest,
		self->signature->length, self->signature->data);
}
Niels Möller's avatar
Niels Möller committed
580