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