mdw@git.distorted.org.uk Git - secnet/blob - rsa.c

   1 /* This file is part of secnet, and is distributed under the terms of
   2    the GNU General Public License version 2 or later.
   3
   4    Copyright (C) 1995-2002 Stephen Early
   5    Copyright (C) 2001 Simon Tatham
   6    Copyright (C) 2002 Ian Jackson
   7    */
   8
   9 #include <stdio.h>
  10 #include <string.h>
  11 #include <gmp.h>
  12 #include "secnet.h"
  13 #include "util.h"
  14
  15 #define AUTHFILE_ID_STRING "SSH PRIVATE KEY FILE FORMAT 1.1\n"
  16
  17 #define mpp(s,n) do { char *p = mpz_get_str(NULL,16,n); printf("%s 0x%sL\n", s, p); free(p); } while (0)
  18
  19 struct rsapriv {
  20     closure_t cl;
  21     struct rsaprivkey_if ops;
  22     struct cloc loc;
  23     MP_INT n;
  24     MP_INT p, dp;
  25     MP_INT q, dq;
  26     MP_INT w;
  27 };
  28 struct rsapub {
  29     closure_t cl;
  30     struct rsapubkey_if ops;
  31     struct cloc loc;
  32     MP_INT e;
  33     MP_INT n;
  34 };
  35 /* Sign data. NB data must be smaller than modulus */
  36
  37 static const char *hexchars="0123456789abcdef";
  38
  39 static string_t rsa_sign(void *sst, uint8_t *data, int32_t datalen)
  40 {
  41     struct rsapriv *st=sst;
  42     MP_INT a, b, u, v, tmp, tmp2;
  43     char buff[2048];
  44     int msize, i;
  45     string_t signature;
  46
  47     mpz_init(&a);
  48     mpz_init(&b);
  49
  50     /* RSA PKCS#1 v1.5 signature padding:
  51      *
  52      * <------------ msize hex digits ---------->
  53      *
  54      * 00 01 ff ff .... ff ff 00 vv vv vv .... vv
  55      *
  56      *                           <--- datalen -->
  57      *                                 bytes
  58      *                         = datalen*2 hex digits
  59      *
  60      * NB that according to PKCS#1 v1.5 we're supposed to include a
  61      * hash function OID in the data.  We don't do that (because we
  62      * don't have the hash function OID to hand here), thus violating
  63      * the spec in a way that affects interop but not security.
  64      *
  65      * -iwj 17.9.2002
  66      */
  67
  68     msize=mpz_sizeinbase(&st->n, 16);
  69
  70     if (datalen*2+6>=msize) {
  71         fatal("rsa_sign: message too big");
  72     }
  73
  74     strcpy(buff,"0001");
  75
  76     for (i=0; i<datalen; i++) {
  77         buff[msize+(-datalen+i)*2]=hexchars[(data[i]&0xf0)>>4];
  78         buff[msize+(-datalen+i)*2+1]=hexchars[data[i]&0xf];
  79     }
  80
  81     buff[msize-datalen*2-2]= '0';
  82     buff[msize-datalen*2-1]= '0';
  83
  84     for (i=4; i<msize-datalen*2-2; i++)
  85        buff[i]='f';
  86
  87     buff[msize]=0;
  88
  89     mpz_set_str(&a, buff, 16);
  90
  91     /*
  92      * Produce an RSA signature (a^d mod n) using the Chinese
  93      * Remainder Theorem. We compute:
  94      *
  95      *   u = a^dp mod p    (== a^d mod p, since dp == d mod (p-1))
  96      *   v = a^dq mod q    (== a^d mod q, similarly)
  97      *
  98      * We also know w == iqmp * q, which has the property that w ==
  99      * 0 mod q and w == 1 mod p. So (1-w) has the reverse property
 100      * (congruent to 0 mod p and to 1 mod q). Hence we now compute
 101      *
 102      *   b = w * u + (1-w) * v
 103      *     = w * (u-v) + v
 104      *
 105      * so that b is congruent to a^d both mod p and mod q. Hence b,
 106      * reduced mod n, is the required signature.
 107      */
 108     mpz_init(&tmp);
 109     mpz_init(&tmp2);
 110     mpz_init(&u);
 111     mpz_init(&v);
 112
 113     mpz_powm(&u, &a, &st->dp, &st->p);
 114     mpz_powm(&v, &a, &st->dq, &st->q);
 115     mpz_sub(&tmp, &u, &v);
 116     mpz_mul(&tmp2, &tmp, &st->w);
 117     mpz_add(&tmp, &tmp2, &v);
 118     mpz_mod(&b, &tmp, &st->n);
 119
 120     mpz_clear(&tmp);
 121     mpz_clear(&tmp2);
 122     mpz_clear(&u);
 123     mpz_clear(&v);
 124
 125     signature=write_mpstring(&b);
 126
 127     mpz_clear(&b);
 128     mpz_clear(&a);
 129     return signature;
 130 }
 131
 132 static rsa_checksig_fn rsa_sig_check;
 133 static bool_t rsa_sig_check(void *sst, uint8_t *data, int32_t datalen,
 134                             cstring_t signature)
 135 {
 136     struct rsapub *st=sst;
 137     MP_INT a, b, c;
 138     char buff[2048];
 139     int msize, i;
 140     bool_t ok;
 141
 142     mpz_init(&a);
 143     mpz_init(&b);
 144     mpz_init(&c);
 145
 146     msize=mpz_sizeinbase(&st->n, 16);
 147
 148     strcpy(buff,"0001");
 149
 150     for (i=0; i<datalen; i++) {
 151         buff[msize+(-datalen+i)*2]=hexchars[(data[i]&0xf0)>>4];
 152         buff[msize+(-datalen+i)*2+1]=hexchars[data[i]&0xf];
 153     }
 154
 155     buff[msize-datalen*2-2]= '0';
 156     buff[msize-datalen*2-1]= '0';
 157
 158     for (i=4; i<msize-datalen*2-2; i++)
 159         buff[i]='f';
 160
 161     buff[msize]=0;
 162
 163     mpz_set_str(&a, buff, 16);
 164
 165     mpz_set_str(&b, signature, 16);
 166
 167     mpz_powm(&c, &b, &st->e, &st->n);
 168
 169     ok=(mpz_cmp(&a, &c)==0);
 170
 171     mpz_clear(&c);
 172     mpz_clear(&b);
 173     mpz_clear(&a);
 174
 175     return ok;
 176 }
 177
 178 static list_t *rsapub_apply(closure_t *self, struct cloc loc, dict_t *context,
 179                             list_t *args)
 180 {
 181     struct rsapub *st;
 182     item_t *i;
 183     string_t e,n;
 184
 185     st=safe_malloc(sizeof(*st),"rsapub_apply");
 186     st->cl.description="rsapub";
 187     st->cl.type=CL_RSAPUBKEY;
 188     st->cl.apply=NULL;
 189     st->cl.interface=&st->ops;
 190     st->ops.st=st;
 191     st->ops.check=rsa_sig_check;
 192     st->loc=loc;
 193
 194     i=list_elem(args,0);
 195     if (i) {
 196         if (i->type!=t_string) {
 197             cfgfatal(i->loc,"rsa-public","first argument must be a string\n");
 198         }
 199         e=i->data.string;
 200         if (mpz_init_set_str(&st->e,e,10)!=0) {
 201             cfgfatal(i->loc,"rsa-public","encryption key \"%s\" is not a "
 202                      "decimal number string\n",e);
 203         }
 204     } else {
 205         cfgfatal(loc,"rsa-public","you must provide an encryption key\n");
 206     }
 207
 208     i=list_elem(args,1);
 209     if (i) {
 210         if (i->type!=t_string) {
 211             cfgfatal(i->loc,"rsa-public","second argument must be a string\n");
 212         }
 213         n=i->data.string;
 214         if (mpz_init_set_str(&st->n,n,10)!=0) {
 215             cfgfatal(i->loc,"rsa-public","modulus \"%s\" is not a decimal "
 216                      "number string\n",n);
 217         }
 218     } else {
 219         cfgfatal(loc,"rsa-public","you must provide a modulus\n");
 220     }
 221     return new_closure(&st->cl);
 222 }
 223
 224 static uint32_t keyfile_get_int(struct cloc loc, FILE *f)
 225 {
 226     uint32_t r;
 227     r=fgetc(f)<<24;
 228     r|=fgetc(f)<<16;
 229     r|=fgetc(f)<<8;
 230     r|=fgetc(f);
 231     cfgfile_postreadcheck(loc,f);
 232     return r;
 233 }
 234
 235 static uint16_t keyfile_get_short(struct cloc loc, FILE *f)
 236 {
 237     uint16_t r;
 238     r=fgetc(f)<<8;
 239     r|=fgetc(f);
 240     cfgfile_postreadcheck(loc,f);
 241     return r;
 242 }
 243
 244 static list_t *rsapriv_apply(closure_t *self, struct cloc loc, dict_t *context,
 245                              list_t *args)
 246 {
 247     struct rsapriv *st;
 248     FILE *f;
 249     cstring_t filename;
 250     item_t *i;
 251     long length;
 252     uint8_t *b, *c;
 253     int cipher_type;
 254     MP_INT e,d,iqmp,tmp,tmp2,tmp3;
 255     bool_t valid;
 256
 257     st=safe_malloc(sizeof(*st),"rsapriv_apply");
 258     st->cl.description="rsapriv";
 259     st->cl.type=CL_RSAPRIVKEY;
 260     st->cl.apply=NULL;
 261     st->cl.interface=&st->ops;
 262     st->ops.st=st;
 263     st->ops.sign=rsa_sign;
 264     st->loc=loc;
 265
 266     /* Argument is filename pointing to SSH1 private key file */
 267     i=list_elem(args,0);
 268     if (i) {
 269         if (i->type!=t_string) {
 270             cfgfatal(i->loc,"rsa-public","first argument must be a string\n");
 271         }
 272         filename=i->data.string;
 273     } else {
 274         filename=NULL; /* Make compiler happy */
 275         cfgfatal(loc,"rsa-private","you must provide a filename\n");
 276     }
 277
 278     f=fopen(filename,"rb");
 279     if (!f) {
 280         if (just_check_config) {
 281             Message(M_WARNING,"rsa-private (%s:%d): cannot open keyfile "
 282                     "\"%s\"; assuming it's valid while we check the "
 283                     "rest of the configuration\n",loc.file,loc.line,filename);
 284             goto assume_valid;
 285         } else {
 286             fatal_perror("rsa-private (%s:%d): cannot open file \"%s\"",
 287                          loc.file,loc.line,filename);
 288         }
 289     }
 290
 291     /* Check that the ID string is correct */
 292     length=strlen(AUTHFILE_ID_STRING)+1;
 293     b=safe_malloc(length,"rsapriv_apply");
 294     if (fread(b,length,1,f)!=1 || memcmp(b,AUTHFILE_ID_STRING,length)!=0) {
 295         cfgfatal_maybefile(f,loc,"rsa-private","failed to read magic ID"
 296                            " string from SSH1 private keyfile \"%s\"\n",
 297                            filename);
 298     }
 299     free(b);
 300
 301     cipher_type=fgetc(f);
 302     keyfile_get_int(loc,f); /* "Reserved data" */
 303     if (cipher_type != 0) {
 304         cfgfatal(loc,"rsa-private","we don't support encrypted keyfiles\n");
 305     }
 306
 307     /* Read the public key */
 308     keyfile_get_int(loc,f); /* Not sure what this is */
 309     length=(keyfile_get_short(loc,f)+7)/8;
 310     if (length>1024) {
 311         cfgfatal(loc,"rsa-private","implausible length %ld for modulus\n",
 312                  length);
 313     }
 314     b=safe_malloc(length,"rsapriv_apply");
 315     if (fread(b,length,1,f) != 1) {
 316         cfgfatal_maybefile(f,loc,"rsa-private","error reading modulus\n");
 317     }
 318     mpz_init(&st->n);
 319     read_mpbin(&st->n,b,length);
 320     free(b);
 321     length=(keyfile_get_short(loc,f)+7)/8;
 322     if (length>1024) {
 323         cfgfatal(loc,"rsa-private","implausible length %ld for e\n",length);
 324     }
 325     b=safe_malloc(length,"rsapriv_apply");
 326     if (fread(b,length,1,f)!=1) {
 327         cfgfatal_maybefile(f,loc,"rsa-private","error reading e\n");
 328     }
 329     mpz_init(&e);
 330     read_mpbin(&e,b,length);
 331     free(b);
 332
 333     length=keyfile_get_int(loc,f);
 334     if (length>1024) {
 335         cfgfatal(loc,"rsa-private","implausibly long (%ld) key comment\n",
 336                  length);
 337     }
 338     c=safe_malloc(length+1,"rsapriv_apply");
 339     if (fread(c,length,1,f)!=1) {
 340         cfgfatal_maybefile(f,loc,"rsa-private","error reading key comment\n");
 341     }
 342     c[length]=0;
 343
 344     /* Check that the next two pairs of characters are identical - the
 345        keyfile is not encrypted, so they should be */
 346
 347     if (keyfile_get_short(loc,f) != keyfile_get_short(loc,f)) {
 348         cfgfatal(loc,"rsa-private","corrupt keyfile\n");
 349     }
 350
 351     /* Read d */
 352     length=(keyfile_get_short(loc,f)+7)/8;
 353     if (length>1024) {
 354         cfgfatal(loc,"rsa-private","implausibly long (%ld) decryption key\n",
 355                  length);
 356     }
 357     b=safe_malloc(length,"rsapriv_apply");
 358     if (fread(b,length,1,f)!=1) {
 359         cfgfatal_maybefile(f,loc,"rsa-private",
 360                            "error reading decryption key\n");
 361     }
 362     mpz_init(&d);
 363     read_mpbin(&d,b,length);
 364     free(b);
 365     /* Read iqmp (inverse of q mod p) */
 366     length=(keyfile_get_short(loc,f)+7)/8;
 367     if (length>1024) {
 368         cfgfatal(loc,"rsa-private","implausibly long (%ld)"
 369                  " iqmp auxiliary value\n", length);
 370     }
 371     b=safe_malloc(length,"rsapriv_apply");
 372     if (fread(b,length,1,f)!=1) {
 373         cfgfatal_maybefile(f,loc,"rsa-private",
 374                            "error reading decryption key\n");
 375     }
 376     mpz_init(&iqmp);
 377     read_mpbin(&iqmp,b,length);
 378     free(b);
 379     /* Read q (the smaller of the two primes) */
 380     length=(keyfile_get_short(loc,f)+7)/8;
 381     if (length>1024) {
 382         cfgfatal(loc,"rsa-private","implausibly long (%ld) q value\n",
 383                  length);
 384     }
 385     b=safe_malloc(length,"rsapriv_apply");
 386     if (fread(b,length,1,f)!=1) {
 387         cfgfatal_maybefile(f,loc,"rsa-private",
 388                            "error reading q value\n");
 389     }
 390     mpz_init(&st->q);
 391     read_mpbin(&st->q,b,length);
 392     free(b);
 393     /* Read p (the larger of the two primes) */
 394     length=(keyfile_get_short(loc,f)+7)/8;
 395     if (length>1024) {
 396         cfgfatal(loc,"rsa-private","implausibly long (%ld) p value\n",
 397                  length);
 398     }
 399     b=safe_malloc(length,"rsapriv_apply");
 400     if (fread(b,length,1,f)!=1) {
 401         cfgfatal_maybefile(f,loc,"rsa-private",
 402                            "error reading p value\n");
 403     }
 404     mpz_init(&st->p);
 405     read_mpbin(&st->p,b,length);
 406     free(b);
 407
 408     if (fclose(f)!=0) {
 409         fatal_perror("rsa-private (%s:%d): fclose",loc.file,loc.line);
 410     }
 411
 412     /*
 413      * Now verify the validity of the key, and set up the auxiliary
 414      * values for fast CRT signing.
 415      */
 416     valid=False;
 417     i=list_elem(args,1);
 418     mpz_init(&tmp);
 419     mpz_init(&tmp2);
 420     mpz_init(&tmp3);
 421     if (i && i->type==t_bool && i->data.bool==False) {
 422         Message(M_INFO,"rsa-private (%s:%d): skipping RSA key validity "
 423                 "check\n",loc.file,loc.line);
 424     } else {
 425         /* Verify that p*q is equal to n. */
 426         mpz_mul(&tmp, &st->p, &st->q);
 427         if (mpz_cmp(&tmp, &st->n) != 0)
 428             goto done_checks;
 429
 430         /*
 431          * Verify that d*e is congruent to 1 mod (p-1), and mod
 432          * (q-1). This is equivalent to it being congruent to 1 mod
 433          * lcm(p-1,q-1), i.e. congruent to 1 mod phi(n). Note that
 434          * phi(n) is _not_ simply (p-1)*(q-1).
 435          */
 436         mpz_mul(&tmp, &d, &e);
 437         mpz_sub_ui(&tmp2, &st->p, 1);
 438         mpz_mod(&tmp3, &tmp, &tmp2);
 439         if (mpz_cmp_si(&tmp3, 1) != 0)
 440             goto done_checks;
 441         mpz_sub_ui(&tmp2, &st->q, 1);
 442         mpz_mod(&tmp3, &tmp, &tmp2);
 443         if (mpz_cmp_si(&tmp3, 1) != 0)
 444             goto done_checks;
 445
 446         /* Verify that q*iqmp is congruent to 1 mod p. */
 447         mpz_mul(&tmp, &st->q, &iqmp);
 448         mpz_mod(&tmp2, &tmp, &st->p);
 449         if (mpz_cmp_si(&tmp2, 1) != 0)
 450             goto done_checks;
 451     }
 452     /* Now we know the key is valid (or we don't care). */
 453     valid = True;
 454
 455     /*
 456      * Now we compute auxiliary values dp, dq and w to allow us
 457      * to use the CRT optimisation when signing.
 458      *
 459      *   dp == d mod (p-1)      so that a^dp == a^d mod p, for all a
 460      *   dq == d mod (q-1)      similarly mod q
 461      *   w == iqmp * q          so that w == 0 mod q, and w == 1 mod p
 462      */
 463     mpz_init(&st->dp);
 464     mpz_init(&st->dq);
 465     mpz_init(&st->w);
 466     mpz_sub_ui(&tmp, &st->p, 1);
 467     mpz_mod(&st->dp, &d, &tmp);
 468     mpz_sub_ui(&tmp, &st->q, 1);
 469     mpz_mod(&st->dq, &d, &tmp);
 470     mpz_mul(&st->w, &iqmp, &st->q);
 471
 472 done_checks:
 473     if (!valid) {
 474         cfgfatal(loc,"rsa-private","file \"%s\" does not contain a "
 475                  "valid RSA key!\n",filename);
 476     }
 477     mpz_clear(&tmp);
 478     mpz_clear(&tmp2);
 479     mpz_clear(&tmp3);
 480
 481     free(c);
 482     mpz_clear(&e);
 483     mpz_clear(&d);
 484     mpz_clear(&iqmp);
 485
 486 assume_valid:
 487     return new_closure(&st->cl);
 488 }
 489
 490 void rsa_module(dict_t *dict)
 491 {
 492     add_closure(dict,"rsa-private",rsapriv_apply);
 493     add_closure(dict,"rsa-public",rsapub_apply);
 494 }