sshdss.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4
   5 #include "ssh.h"
   6
   7 #define GET_32BIT(cp) \
   8     (((unsigned long)(unsigned char)(cp)[0] << 24) | \
   9     ((unsigned long)(unsigned char)(cp)[1] << 16) | \
  10     ((unsigned long)(unsigned char)(cp)[2] << 8) | \
  11     ((unsigned long)(unsigned char)(cp)[3]))
  12
  13 #define PUT_32BIT(cp, value) { \
  14     (cp)[0] = (unsigned char)((value) >> 24); \
  15     (cp)[1] = (unsigned char)((value) >> 16); \
  16     (cp)[2] = (unsigned char)((value) >> 8); \
  17     (cp)[3] = (unsigned char)(value); }
  18
  19 #if 0
  20 #define DEBUG_DSS
  21 #else
  22 #define diagbn(x,y)
  23 #endif
  24
  25 static void getstring(char **data, int *datalen, char **p, int *length)
  26 {
  27     *p = NULL;
  28     if (*datalen < 4)
  29         return;
  30     *length = GET_32BIT(*data);
  31     *datalen -= 4;
  32     *data += 4;
  33     if (*datalen < *length)
  34         return;
  35     *p = *data;
  36     *data += *length;
  37     *datalen -= *length;
  38 }
  39 static Bignum getmp(char **data, int *datalen)
  40 {
  41     char *p;
  42     int length;
  43     Bignum b;
  44
  45     getstring(data, datalen, &p, &length);
  46     if (!p)
  47         return NULL;
  48     if (p[0] & 0x80)
  49         return NULL;                   /* negative mp */
  50     b = bignum_from_bytes(p, length);
  51     return b;
  52 }
  53
  54 static Bignum get160(char **data, int *datalen)
  55 {
  56     Bignum b;
  57
  58     b = bignum_from_bytes(*data, 20);
  59     *data += 20;
  60     *datalen -= 20;
  61
  62     return b;
  63 }
  64
  65 struct dss_key {
  66     Bignum p, q, g, y;
  67 };
  68
  69 static void *dss_newkey(char *data, int len)
  70 {
  71     char *p;
  72     int slen;
  73     struct dss_key *dss;
  74
  75     dss = smalloc(sizeof(struct dss_key));
  76     if (!dss)
  77         return NULL;
  78     getstring(&data, &len, &p, &slen);
  79
  80 #ifdef DEBUG_DSS
  81     {
  82         int i;
  83         printf("key:");
  84         for (i = 0; i < len; i++)
  85             printf("  %02x", (unsigned char) (data[i]));
  86         printf("\n");
  87     }
  88 #endif
  89
  90     if (!p || memcmp(p, "ssh-dss", 7)) {
  91         sfree(dss);
  92         return NULL;
  93     }
  94     dss->p = getmp(&data, &len);
  95     dss->q = getmp(&data, &len);
  96     dss->g = getmp(&data, &len);
  97     dss->y = getmp(&data, &len);
  98
  99     return dss;
 100 }
 101
 102 static void dss_freekey(void *key)
 103 {
 104     struct dss_key *dss = (struct dss_key *) key;
 105     freebn(dss->p);
 106     freebn(dss->q);
 107     freebn(dss->g);
 108     freebn(dss->y);
 109     sfree(dss);
 110 }
 111
 112 static char *dss_fmtkey(void *key)
 113 {
 114     struct dss_key *dss = (struct dss_key *) key;
 115     char *p;
 116     int len, i, pos, nibbles;
 117     static const char hex[] = "0123456789abcdef";
 118     if (!dss->p)
 119         return NULL;
 120     len = 8 + 4 + 1;                   /* 4 x "0x", punctuation, \0 */
 121     len += 4 * (bignum_bitcount(dss->p) + 15) / 16;
 122     len += 4 * (bignum_bitcount(dss->q) + 15) / 16;
 123     len += 4 * (bignum_bitcount(dss->g) + 15) / 16;
 124     len += 4 * (bignum_bitcount(dss->y) + 15) / 16;
 125     p = smalloc(len);
 126     if (!p)
 127         return NULL;
 128
 129     pos = 0;
 130     pos += sprintf(p + pos, "0x");
 131     nibbles = (3 + bignum_bitcount(dss->p)) / 4;
 132     if (nibbles < 1)
 133         nibbles = 1;
 134     for (i = nibbles; i--;)
 135         p[pos++] =
 136             hex[(bignum_byte(dss->p, i / 2) >> (4 * (i % 2))) & 0xF];
 137     pos += sprintf(p + pos, ",0x");
 138     nibbles = (3 + bignum_bitcount(dss->q)) / 4;
 139     if (nibbles < 1)
 140         nibbles = 1;
 141     for (i = nibbles; i--;)
 142         p[pos++] =
 143             hex[(bignum_byte(dss->q, i / 2) >> (4 * (i % 2))) & 0xF];
 144     pos += sprintf(p + pos, ",0x");
 145     nibbles = (3 + bignum_bitcount(dss->g)) / 4;
 146     if (nibbles < 1)
 147         nibbles = 1;
 148     for (i = nibbles; i--;)
 149         p[pos++] =
 150             hex[(bignum_byte(dss->g, i / 2) >> (4 * (i % 2))) & 0xF];
 151     pos += sprintf(p + pos, ",0x");
 152     nibbles = (3 + bignum_bitcount(dss->y)) / 4;
 153     if (nibbles < 1)
 154         nibbles = 1;
 155     for (i = nibbles; i--;)
 156         p[pos++] =
 157             hex[(bignum_byte(dss->y, i / 2) >> (4 * (i % 2))) & 0xF];
 158     p[pos] = '\0';
 159     return p;
 160 }
 161
 162 static char *dss_fingerprint(void *key)
 163 {
 164     struct dss_key *dss = (struct dss_key *) key;
 165     struct MD5Context md5c;
 166     unsigned char digest[16], lenbuf[4];
 167     char buffer[16 * 3 + 40];
 168     char *ret;
 169     int numlen, i;
 170
 171     MD5Init(&md5c);
 172     MD5Update(&md5c, "\0\0\0\7ssh-dss", 11);
 173
 174 #define ADD_BIGNUM(bignum) \
 175     numlen = (bignum_bitcount(bignum)+8)/8; \
 176     PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \
 177     for (i = numlen; i-- ;) { \
 178         unsigned char c = bignum_byte(bignum, i); \
 179         MD5Update(&md5c, &c, 1); \
 180     }
 181     ADD_BIGNUM(dss->p);
 182     ADD_BIGNUM(dss->q);
 183     ADD_BIGNUM(dss->g);
 184     ADD_BIGNUM(dss->y);
 185 #undef ADD_BIGNUM
 186
 187     MD5Final(digest, &md5c);
 188
 189     sprintf(buffer, "ssh-dss %d ", bignum_bitcount(dss->p));
 190     for (i = 0; i < 16; i++)
 191         sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",
 192                 digest[i]);
 193     ret = smalloc(strlen(buffer) + 1);
 194     if (ret)
 195         strcpy(ret, buffer);
 196     return ret;
 197 }
 198
 199 static int dss_verifysig(void *key, char *sig, int siglen,
 200                          char *data, int datalen)
 201 {
 202     struct dss_key *dss = (struct dss_key *) key;
 203     char *p;
 204     int slen;
 205     char hash[20];
 206     Bignum r, s, w, gu1p, yu2p, gu1yu2p, u1, u2, sha, v;
 207     int ret;
 208
 209     if (!dss->p)
 210         return 0;
 211
 212 #ifdef DEBUG_DSS
 213     {
 214         int i;
 215         printf("sig:");
 216         for (i = 0; i < siglen; i++)
 217             printf("  %02x", (unsigned char) (sig[i]));
 218         printf("\n");
 219     }
 220 #endif
 221     /*
 222      * Commercial SSH (2.0.13) and OpenSSH disagree over the format
 223      * of a DSA signature. OpenSSH is in line with the IETF drafts:
 224      * it uses a string "ssh-dss", followed by a 40-byte string
 225      * containing two 160-bit integers end-to-end. Commercial SSH
 226      * can't be bothered with the header bit, and considers a DSA
 227      * signature blob to be _just_ the 40-byte string containing
 228      * the two 160-bit integers. We tell them apart by measuring
 229      * the length: length 40 means the commercial-SSH bug, anything
 230      * else is assumed to be IETF-compliant.
 231      */
 232     if (siglen != 40) {                /* bug not present; read admin fields */
 233         getstring(&sig, &siglen, &p, &slen);
 234         if (!p || slen != 7 || memcmp(p, "ssh-dss", 7)) {
 235             return 0;
 236         }
 237         sig += 4, siglen -= 4;         /* skip yet another length field */
 238     }
 239     diagbn("p=", dss->p);
 240     diagbn("q=", dss->q);
 241     diagbn("g=", dss->g);
 242     diagbn("y=", dss->y);
 243     r = get160(&sig, &siglen);
 244     diagbn("r=", r);
 245     s = get160(&sig, &siglen);
 246     diagbn("s=", s);
 247     if (!r || !s)
 248         return 0;
 249
 250     /*
 251      * Step 1. w <- s^-1 mod q.
 252      */
 253     w = modinv(s, dss->q);
 254     diagbn("w=", w);
 255
 256     /*
 257      * Step 2. u1 <- SHA(message) * w mod q.
 258      */
 259     SHA_Simple(data, datalen, hash);
 260     p = hash;
 261     slen = 20;
 262     sha = get160(&p, &slen);
 263     diagbn("sha=", sha);
 264     u1 = modmul(sha, w, dss->q);
 265     diagbn("u1=", u1);
 266
 267     /*
 268      * Step 3. u2 <- r * w mod q.
 269      */
 270     u2 = modmul(r, w, dss->q);
 271     diagbn("u2=", u2);
 272
 273     /*
 274      * Step 4. v <- (g^u1 * y^u2 mod p) mod q.
 275      */
 276     gu1p = modpow(dss->g, u1, dss->p);
 277     diagbn("gu1p=", gu1p);
 278     yu2p = modpow(dss->y, u2, dss->p);
 279     diagbn("yu2p=", yu2p);
 280     gu1yu2p = modmul(gu1p, yu2p, dss->p);
 281     diagbn("gu1yu2p=", gu1yu2p);
 282     v = modmul(gu1yu2p, One, dss->q);
 283     diagbn("gu1yu2q=v=", v);
 284     diagbn("r=", r);
 285
 286     /*
 287      * Step 5. v should now be equal to r.
 288      */
 289
 290     ret = !bignum_cmp(v, r);
 291
 292     freebn(w);
 293     freebn(sha);
 294     freebn(gu1p);
 295     freebn(yu2p);
 296     freebn(gu1yu2p);
 297     freebn(v);
 298     freebn(r);
 299     freebn(s);
 300
 301     return ret;
 302 }
 303
 304 static unsigned char *dss_public_blob(void *key, int *len)
 305 {
 306     struct dss_key *dss = (struct dss_key *) key;
 307     int plen, qlen, glen, ylen, bloblen;
 308     int i;
 309     unsigned char *blob, *p;
 310
 311     plen = (bignum_bitcount(dss->p) + 8) / 8;
 312     qlen = (bignum_bitcount(dss->q) + 8) / 8;
 313     glen = (bignum_bitcount(dss->g) + 8) / 8;
 314     ylen = (bignum_bitcount(dss->y) + 8) / 8;
 315
 316     /*
 317      * string "ssh-dss", mpint p, mpint q, mpint g, mpint y. Total
 318      * 27 + sum of lengths. (five length fields, 20+7=27).
 319      */
 320     bloblen = 27 + plen + qlen + glen + ylen;
 321     blob = smalloc(bloblen);
 322     p = blob;
 323     PUT_32BIT(p, 7);
 324     p += 4;
 325     memcpy(p, "ssh-dss", 7);
 326     p += 7;
 327     PUT_32BIT(p, plen);
 328     p += 4;
 329     for (i = plen; i--;)
 330         *p++ = bignum_byte(dss->p, i);
 331     PUT_32BIT(p, qlen);
 332     p += 4;
 333     for (i = qlen; i--;)
 334         *p++ = bignum_byte(dss->q, i);
 335     PUT_32BIT(p, glen);
 336     p += 4;
 337     for (i = glen; i--;)
 338         *p++ = bignum_byte(dss->g, i);
 339     PUT_32BIT(p, ylen);
 340     p += 4;
 341     for (i = ylen; i--;)
 342         *p++ = bignum_byte(dss->y, i);
 343     assert(p == blob + bloblen);
 344     *len = bloblen;
 345     return blob;
 346 }
 347
 348 static unsigned char *dss_private_blob(void *key, int *len)
 349 {
 350     return NULL;                       /* can't handle DSS private keys */
 351 }
 352
 353 static void *dss_createkey(unsigned char *pub_blob, int pub_len,
 354                            unsigned char *priv_blob, int priv_len)
 355 {
 356     return NULL;                       /* can't handle DSS private keys */
 357 }
 358
 359 static void *dss_openssh_createkey(unsigned char **blob, int *len)
 360 {
 361     return NULL;                       /* can't handle DSS private keys */
 362 }
 363
 364 static int dss_openssh_fmtkey(void *key, unsigned char *blob, int len)
 365 {
 366     return -1;                         /* can't handle DSS private keys */
 367 }
 368
 369 unsigned char *dss_sign(void *key, char *data, int datalen, int *siglen)
 370 {
 371     return NULL;                       /* can't handle DSS private keys */
 372 }
 373
 374 const struct ssh_signkey ssh_dss = {
 375     dss_newkey,
 376     dss_freekey,
 377     dss_fmtkey,
 378     dss_public_blob,
 379     dss_private_blob,
 380     dss_createkey,
 381     dss_openssh_createkey,
 382     dss_openssh_fmtkey,
 383     dss_fingerprint,
 384     dss_verifysig,
 385     dss_sign,
 386     "ssh-dss",
 387     "dss"
 388 };