putty/SSHDSS.C

   1 /*\r
   2  * Digital Signature Standard implementation for PuTTY.\r
   3  */\r
   4 \r
   5 #include <stdio.h>\r
   6 #include <stdlib.h>\r
   7 #include <assert.h>\r
   8 \r
   9 #include "ssh.h"\r
  10 #include "misc.h"\r
  11 \r
  12 static void sha_mpint(SHA_State * s, Bignum b)\r
  13 {\r
  14     unsigned char lenbuf[4];\r
  15     int len;\r
  16     len = (bignum_bitcount(b) + 8) / 8;\r
  17     PUT_32BIT(lenbuf, len);\r
  18     SHA_Bytes(s, lenbuf, 4);\r
  19     while (len-- > 0) {\r
  20         lenbuf[0] = bignum_byte(b, len);\r
  21         SHA_Bytes(s, lenbuf, 1);\r
  22     }\r
  23     smemclr(lenbuf, sizeof(lenbuf));\r
  24 }\r
  25 \r
  26 static void sha512_mpint(SHA512_State * s, Bignum b)\r
  27 {\r
  28     unsigned char lenbuf[4];\r
  29     int len;\r
  30     len = (bignum_bitcount(b) + 8) / 8;\r
  31     PUT_32BIT(lenbuf, len);\r
  32     SHA512_Bytes(s, lenbuf, 4);\r
  33     while (len-- > 0) {\r
  34         lenbuf[0] = bignum_byte(b, len);\r
  35         SHA512_Bytes(s, lenbuf, 1);\r
  36     }\r
  37     smemclr(lenbuf, sizeof(lenbuf));\r
  38 }\r
  39 \r
  40 static void getstring(char **data, int *datalen, char **p, int *length)\r
  41 {\r
  42     *p = NULL;\r
  43     if (*datalen < 4)\r
  44         return;\r
  45     *length = toint(GET_32BIT(*data));\r
  46     if (*length < 0)\r
  47         return;\r
  48     *datalen -= 4;\r
  49     *data += 4;\r
  50     if (*datalen < *length)\r
  51         return;\r
  52     *p = *data;\r
  53     *data += *length;\r
  54     *datalen -= *length;\r
  55 }\r
  56 static Bignum getmp(char **data, int *datalen)\r
  57 {\r
  58     char *p;\r
  59     int length;\r
  60     Bignum b;\r
  61 \r
  62     getstring(data, datalen, &p, &length);\r
  63     if (!p)\r
  64         return NULL;\r
  65     if (p[0] & 0x80)\r
  66         return NULL;                   /* negative mp */\r
  67     b = bignum_from_bytes((unsigned char *)p, length);\r
  68     return b;\r
  69 }\r
  70 \r
  71 static Bignum get160(char **data, int *datalen)\r
  72 {\r
  73     Bignum b;\r
  74 \r
  75     if (*datalen < 20)\r
  76         return NULL;\r
  77 \r
  78     b = bignum_from_bytes((unsigned char *)*data, 20);\r
  79     *data += 20;\r
  80     *datalen -= 20;\r
  81 \r
  82     return b;\r
  83 }\r
  84 \r
  85 static void dss_freekey(void *key);    /* forward reference */\r
  86 \r
  87 static void *dss_newkey(char *data, int len)\r
  88 {\r
  89     char *p;\r
  90     int slen;\r
  91     struct dss_key *dss;\r
  92 \r
  93     dss = snew(struct dss_key);\r
  94     getstring(&data, &len, &p, &slen);\r
  95 \r
  96 #ifdef DEBUG_DSS\r
  97     {\r
  98         int i;\r
  99         printf("key:");\r
 100         for (i = 0; i < len; i++)\r
 101             printf("  %02x", (unsigned char) (data[i]));\r
 102         printf("\n");\r
 103     }\r
 104 #endif\r
 105 \r
 106     if (!p || slen != 7 || memcmp(p, "ssh-dss", 7)) {\r
 107         sfree(dss);\r
 108         return NULL;\r
 109     }\r
 110     dss->p = getmp(&data, &len);\r
 111     dss->q = getmp(&data, &len);\r
 112     dss->g = getmp(&data, &len);\r
 113     dss->y = getmp(&data, &len);\r
 114     dss->x = NULL;\r
 115 \r
 116     if (!dss->p || !dss->q || !dss->g || !dss->y ||\r
 117         !bignum_cmp(dss->q, Zero) || !bignum_cmp(dss->p, Zero)) {\r
 118         /* Invalid key. */\r
 119         dss_freekey(dss);\r
 120         return NULL;\r
 121     }\r
 122 \r
 123     return dss;\r
 124 }\r
 125 \r
 126 static void dss_freekey(void *key)\r
 127 {\r
 128     struct dss_key *dss = (struct dss_key *) key;\r
 129     if (dss->p)\r
 130         freebn(dss->p);\r
 131     if (dss->q)\r
 132         freebn(dss->q);\r
 133     if (dss->g)\r
 134         freebn(dss->g);\r
 135     if (dss->y)\r
 136         freebn(dss->y);\r
 137     if (dss->x)\r
 138         freebn(dss->x);\r
 139     sfree(dss);\r
 140 }\r
 141 \r
 142 static char *dss_fmtkey(void *key)\r
 143 {\r
 144     struct dss_key *dss = (struct dss_key *) key;\r
 145     char *p;\r
 146     int len, i, pos, nibbles;\r
 147     static const char hex[] = "0123456789abcdef";\r
 148     if (!dss->p)\r
 149         return NULL;\r
 150     len = 8 + 4 + 1;                   /* 4 x "0x", punctuation, \0 */\r
 151     len += 4 * (bignum_bitcount(dss->p) + 15) / 16;\r
 152     len += 4 * (bignum_bitcount(dss->q) + 15) / 16;\r
 153     len += 4 * (bignum_bitcount(dss->g) + 15) / 16;\r
 154     len += 4 * (bignum_bitcount(dss->y) + 15) / 16;\r
 155     p = snewn(len, char);\r
 156     if (!p)\r
 157         return NULL;\r
 158 \r
 159     pos = 0;\r
 160     pos += sprintf(p + pos, "0x");\r
 161     nibbles = (3 + bignum_bitcount(dss->p)) / 4;\r
 162     if (nibbles < 1)\r
 163         nibbles = 1;\r
 164     for (i = nibbles; i--;)\r
 165         p[pos++] =\r
 166             hex[(bignum_byte(dss->p, i / 2) >> (4 * (i % 2))) & 0xF];\r
 167     pos += sprintf(p + pos, ",0x");\r
 168     nibbles = (3 + bignum_bitcount(dss->q)) / 4;\r
 169     if (nibbles < 1)\r
 170         nibbles = 1;\r
 171     for (i = nibbles; i--;)\r
 172         p[pos++] =\r
 173             hex[(bignum_byte(dss->q, i / 2) >> (4 * (i % 2))) & 0xF];\r
 174     pos += sprintf(p + pos, ",0x");\r
 175     nibbles = (3 + bignum_bitcount(dss->g)) / 4;\r
 176     if (nibbles < 1)\r
 177         nibbles = 1;\r
 178     for (i = nibbles; i--;)\r
 179         p[pos++] =\r
 180             hex[(bignum_byte(dss->g, i / 2) >> (4 * (i % 2))) & 0xF];\r
 181     pos += sprintf(p + pos, ",0x");\r
 182     nibbles = (3 + bignum_bitcount(dss->y)) / 4;\r
 183     if (nibbles < 1)\r
 184         nibbles = 1;\r
 185     for (i = nibbles; i--;)\r
 186         p[pos++] =\r
 187             hex[(bignum_byte(dss->y, i / 2) >> (4 * (i % 2))) & 0xF];\r
 188     p[pos] = '\0';\r
 189     return p;\r
 190 }\r
 191 \r
 192 static char *dss_fingerprint(void *key)\r
 193 {\r
 194     struct dss_key *dss = (struct dss_key *) key;\r
 195     struct MD5Context md5c;\r
 196     unsigned char digest[16], lenbuf[4];\r
 197     char buffer[16 * 3 + 40];\r
 198     char *ret;\r
 199     int numlen, i;\r
 200 \r
 201     MD5Init(&md5c);\r
 202     MD5Update(&md5c, (unsigned char *)"\0\0\0\7ssh-dss", 11);\r
 203 \r
 204 #define ADD_BIGNUM(bignum) \\r
 205     numlen = (bignum_bitcount(bignum)+8)/8; \\r
 206     PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \\r
 207     for (i = numlen; i-- ;) { \\r
 208         unsigned char c = bignum_byte(bignum, i); \\r
 209         MD5Update(&md5c, &c, 1); \\r
 210     }\r
 211     ADD_BIGNUM(dss->p);\r
 212     ADD_BIGNUM(dss->q);\r
 213     ADD_BIGNUM(dss->g);\r
 214     ADD_BIGNUM(dss->y);\r
 215 #undef ADD_BIGNUM\r
 216 \r
 217     MD5Final(digest, &md5c);\r
 218 \r
 219     sprintf(buffer, "ssh-dss %d ", bignum_bitcount(dss->p));\r
 220     for (i = 0; i < 16; i++)\r
 221         sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",\r
 222                 digest[i]);\r
 223     ret = snewn(strlen(buffer) + 1, char);\r
 224     if (ret)\r
 225         strcpy(ret, buffer);\r
 226     return ret;\r
 227 }\r
 228 \r
 229 static int dss_verifysig(void *key, char *sig, int siglen,\r
 230                          char *data, int datalen)\r
 231 {\r
 232     struct dss_key *dss = (struct dss_key *) key;\r
 233     char *p;\r
 234     int slen;\r
 235     char hash[20];\r
 236     Bignum r, s, w, gu1p, yu2p, gu1yu2p, u1, u2, sha, v;\r
 237     int ret;\r
 238 \r
 239     if (!dss->p)\r
 240         return 0;\r
 241 \r
 242 #ifdef DEBUG_DSS\r
 243     {\r
 244         int i;\r
 245         printf("sig:");\r
 246         for (i = 0; i < siglen; i++)\r
 247             printf("  %02x", (unsigned char) (sig[i]));\r
 248         printf("\n");\r
 249     }\r
 250 #endif\r
 251     /*\r
 252      * Commercial SSH (2.0.13) and OpenSSH disagree over the format\r
 253      * of a DSA signature. OpenSSH is in line with RFC 4253:\r
 254      * it uses a string "ssh-dss", followed by a 40-byte string\r
 255      * containing two 160-bit integers end-to-end. Commercial SSH\r
 256      * can't be bothered with the header bit, and considers a DSA\r
 257      * signature blob to be _just_ the 40-byte string containing\r
 258      * the two 160-bit integers. We tell them apart by measuring\r
 259      * the length: length 40 means the commercial-SSH bug, anything\r
 260      * else is assumed to be RFC-compliant.\r
 261      */\r
 262     if (siglen != 40) {                /* bug not present; read admin fields */\r
 263         getstring(&sig, &siglen, &p, &slen);\r
 264         if (!p || slen != 7 || memcmp(p, "ssh-dss", 7)) {\r
 265             return 0;\r
 266         }\r
 267         sig += 4, siglen -= 4;         /* skip yet another length field */\r
 268     }\r
 269     r = get160(&sig, &siglen);\r
 270     s = get160(&sig, &siglen);\r
 271     if (!r || !s) {\r
 272         if (r)\r
 273             freebn(r);\r
 274         if (s)\r
 275             freebn(s);\r
 276         return 0;\r
 277     }\r
 278 \r
 279     if (!bignum_cmp(s, Zero)) {\r
 280         freebn(r);\r
 281         freebn(s);\r
 282         return 0;\r
 283     }\r
 284 \r
 285     /*\r
 286      * Step 1. w <- s^-1 mod q.\r
 287      */\r
 288     w = modinv(s, dss->q);\r
 289     if (!w) {\r
 290         freebn(r);\r
 291         freebn(s);\r
 292         return 0;\r
 293     }\r
 294 \r
 295     /*\r
 296      * Step 2. u1 <- SHA(message) * w mod q.\r
 297      */\r
 298     SHA_Simple(data, datalen, (unsigned char *)hash);\r
 299     p = hash;\r
 300     slen = 20;\r
 301     sha = get160(&p, &slen);\r
 302     u1 = modmul(sha, w, dss->q);\r
 303 \r
 304     /*\r
 305      * Step 3. u2 <- r * w mod q.\r
 306      */\r
 307     u2 = modmul(r, w, dss->q);\r
 308 \r
 309     /*\r
 310      * Step 4. v <- (g^u1 * y^u2 mod p) mod q.\r
 311      */\r
 312     gu1p = modpow(dss->g, u1, dss->p);\r
 313     yu2p = modpow(dss->y, u2, dss->p);\r
 314     gu1yu2p = modmul(gu1p, yu2p, dss->p);\r
 315     v = modmul(gu1yu2p, One, dss->q);\r
 316 \r
 317     /*\r
 318      * Step 5. v should now be equal to r.\r
 319      */\r
 320 \r
 321     ret = !bignum_cmp(v, r);\r
 322 \r
 323     freebn(w);\r
 324     freebn(sha);\r
 325     freebn(u1);\r
 326     freebn(u2);\r
 327     freebn(gu1p);\r
 328     freebn(yu2p);\r
 329     freebn(gu1yu2p);\r
 330     freebn(v);\r
 331     freebn(r);\r
 332     freebn(s);\r
 333 \r
 334     return ret;\r
 335 }\r
 336 \r
 337 static unsigned char *dss_public_blob(void *key, int *len)\r
 338 {\r
 339     struct dss_key *dss = (struct dss_key *) key;\r
 340     int plen, qlen, glen, ylen, bloblen;\r
 341     int i;\r
 342     unsigned char *blob, *p;\r
 343 \r
 344     plen = (bignum_bitcount(dss->p) + 8) / 8;\r
 345     qlen = (bignum_bitcount(dss->q) + 8) / 8;\r
 346     glen = (bignum_bitcount(dss->g) + 8) / 8;\r
 347     ylen = (bignum_bitcount(dss->y) + 8) / 8;\r
 348 \r
 349     /*\r
 350      * string "ssh-dss", mpint p, mpint q, mpint g, mpint y. Total\r
 351      * 27 + sum of lengths. (five length fields, 20+7=27).\r
 352      */\r
 353     bloblen = 27 + plen + qlen + glen + ylen;\r
 354     blob = snewn(bloblen, unsigned char);\r
 355     p = blob;\r
 356     PUT_32BIT(p, 7);\r
 357     p += 4;\r
 358     memcpy(p, "ssh-dss", 7);\r
 359     p += 7;\r
 360     PUT_32BIT(p, plen);\r
 361     p += 4;\r
 362     for (i = plen; i--;)\r
 363         *p++ = bignum_byte(dss->p, i);\r
 364     PUT_32BIT(p, qlen);\r
 365     p += 4;\r
 366     for (i = qlen; i--;)\r
 367         *p++ = bignum_byte(dss->q, i);\r
 368     PUT_32BIT(p, glen);\r
 369     p += 4;\r
 370     for (i = glen; i--;)\r
 371         *p++ = bignum_byte(dss->g, i);\r
 372     PUT_32BIT(p, ylen);\r
 373     p += 4;\r
 374     for (i = ylen; i--;)\r
 375         *p++ = bignum_byte(dss->y, i);\r
 376     assert(p == blob + bloblen);\r
 377     *len = bloblen;\r
 378     return blob;\r
 379 }\r
 380 \r
 381 static unsigned char *dss_private_blob(void *key, int *len)\r
 382 {\r
 383     struct dss_key *dss = (struct dss_key *) key;\r
 384     int xlen, bloblen;\r
 385     int i;\r
 386     unsigned char *blob, *p;\r
 387 \r
 388     xlen = (bignum_bitcount(dss->x) + 8) / 8;\r
 389 \r
 390     /*\r
 391      * mpint x, string[20] the SHA of p||q||g. Total 4 + xlen.\r
 392      */\r
 393     bloblen = 4 + xlen;\r
 394     blob = snewn(bloblen, unsigned char);\r
 395     p = blob;\r
 396     PUT_32BIT(p, xlen);\r
 397     p += 4;\r
 398     for (i = xlen; i--;)\r
 399         *p++ = bignum_byte(dss->x, i);\r
 400     assert(p == blob + bloblen);\r
 401     *len = bloblen;\r
 402     return blob;\r
 403 }\r
 404 \r
 405 static void *dss_createkey(unsigned char *pub_blob, int pub_len,\r
 406                            unsigned char *priv_blob, int priv_len)\r
 407 {\r
 408     struct dss_key *dss;\r
 409     char *pb = (char *) priv_blob;\r
 410     char *hash;\r
 411     int hashlen;\r
 412     SHA_State s;\r
 413     unsigned char digest[20];\r
 414     Bignum ytest;\r
 415 \r
 416     dss = dss_newkey((char *) pub_blob, pub_len);\r
 417     if (!dss)\r
 418         return NULL;\r
 419     dss->x = getmp(&pb, &priv_len);\r
 420     if (!dss->x) {\r
 421         dss_freekey(dss);\r
 422         return NULL;\r
 423     }\r
 424 \r
 425     /*\r
 426      * Check the obsolete hash in the old DSS key format.\r
 427      */\r
 428     hashlen = -1;\r
 429     getstring(&pb, &priv_len, &hash, &hashlen);\r
 430     if (hashlen == 20) {\r
 431         SHA_Init(&s);\r
 432         sha_mpint(&s, dss->p);\r
 433         sha_mpint(&s, dss->q);\r
 434         sha_mpint(&s, dss->g);\r
 435         SHA_Final(&s, digest);\r
 436         if (0 != memcmp(hash, digest, 20)) {\r
 437             dss_freekey(dss);\r
 438             return NULL;\r
 439         }\r
 440     }\r
 441 \r
 442     /*\r
 443      * Now ensure g^x mod p really is y.\r
 444      */\r
 445     ytest = modpow(dss->g, dss->x, dss->p);\r
 446     if (0 != bignum_cmp(ytest, dss->y)) {\r
 447         dss_freekey(dss);\r
 448         freebn(ytest);\r
 449         return NULL;\r
 450     }\r
 451     freebn(ytest);\r
 452 \r
 453     return dss;\r
 454 }\r
 455 \r
 456 static void *dss_openssh_createkey(unsigned char **blob, int *len)\r
 457 {\r
 458     char **b = (char **) blob;\r
 459     struct dss_key *dss;\r
 460 \r
 461     dss = snew(struct dss_key);\r
 462 \r
 463     dss->p = getmp(b, len);\r
 464     dss->q = getmp(b, len);\r
 465     dss->g = getmp(b, len);\r
 466     dss->y = getmp(b, len);\r
 467     dss->x = getmp(b, len);\r
 468 \r
 469     if (!dss->p || !dss->q || !dss->g || !dss->y || !dss->x ||\r
 470         !bignum_cmp(dss->q, Zero) || !bignum_cmp(dss->p, Zero)) {\r
 471         /* Invalid key. */\r
 472         dss_freekey(dss);\r
 473         return NULL;\r
 474     }\r
 475 \r
 476     return dss;\r
 477 }\r
 478 \r
 479 static int dss_openssh_fmtkey(void *key, unsigned char *blob, int len)\r
 480 {\r
 481     struct dss_key *dss = (struct dss_key *) key;\r
 482     int bloblen, i;\r
 483 \r
 484     bloblen =\r
 485         ssh2_bignum_length(dss->p) +\r
 486         ssh2_bignum_length(dss->q) +\r
 487         ssh2_bignum_length(dss->g) +\r
 488         ssh2_bignum_length(dss->y) +\r
 489         ssh2_bignum_length(dss->x);\r
 490 \r
 491     if (bloblen > len)\r
 492         return bloblen;\r
 493 \r
 494     bloblen = 0;\r
 495 #define ENC(x) \\r
 496     PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \\r
 497     for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i);\r
 498     ENC(dss->p);\r
 499     ENC(dss->q);\r
 500     ENC(dss->g);\r
 501     ENC(dss->y);\r
 502     ENC(dss->x);\r
 503 \r
 504     return bloblen;\r
 505 }\r
 506 \r
 507 static int dss_pubkey_bits(void *blob, int len)\r
 508 {\r
 509     struct dss_key *dss;\r
 510     int ret;\r
 511 \r
 512     dss = dss_newkey((char *) blob, len);\r
 513     if (!dss)\r
 514         return -1;\r
 515     ret = bignum_bitcount(dss->p);\r
 516     dss_freekey(dss);\r
 517 \r
 518     return ret;\r
 519 }\r
 520 \r
 521 static unsigned char *dss_sign(void *key, char *data, int datalen, int *siglen)\r
 522 {\r
 523     /*\r
 524      * The basic DSS signing algorithm is:\r
 525      * \r
 526      *  - invent a random k between 1 and q-1 (exclusive).\r
 527      *  - Compute r = (g^k mod p) mod q.\r
 528      *  - Compute s = k^-1 * (hash + x*r) mod q.\r
 529      * \r
 530      * This has the dangerous properties that:\r
 531      * \r
 532      *  - if an attacker in possession of the public key _and_ the\r
 533      *    signature (for example, the host you just authenticated\r
 534      *    to) can guess your k, he can reverse the computation of s\r
 535      *    and work out x = r^-1 * (s*k - hash) mod q. That is, he\r
 536      *    can deduce the private half of your key, and masquerade\r
 537      *    as you for as long as the key is still valid.\r
 538      * \r
 539      *  - since r is a function purely of k and the public key, if\r
 540      *    the attacker only has a _range of possibilities_ for k\r
 541      *    it's easy for him to work through them all and check each\r
 542      *    one against r; he'll never be unsure of whether he's got\r
 543      *    the right one.\r
 544      * \r
 545      *  - if you ever sign two different hashes with the same k, it\r
 546      *    will be immediately obvious because the two signatures\r
 547      *    will have the same r, and moreover an attacker in\r
 548      *    possession of both signatures (and the public key of\r
 549      *    course) can compute k = (hash1-hash2) * (s1-s2)^-1 mod q,\r
 550      *    and from there deduce x as before.\r
 551      * \r
 552      *  - the Bleichenbacher attack on DSA makes use of methods of\r
 553      *    generating k which are significantly non-uniformly\r
 554      *    distributed; in particular, generating a 160-bit random\r
 555      *    number and reducing it mod q is right out.\r
 556      * \r
 557      * For this reason we must be pretty careful about how we\r
 558      * generate our k. Since this code runs on Windows, with no\r
 559      * particularly good system entropy sources, we can't trust our\r
 560      * RNG itself to produce properly unpredictable data. Hence, we\r
 561      * use a totally different scheme instead.\r
 562      * \r
 563      * What we do is to take a SHA-512 (_big_) hash of the private\r
 564      * key x, and then feed this into another SHA-512 hash that\r
 565      * also includes the message hash being signed. That is:\r
 566      * \r
 567      *   proto_k = SHA512 ( SHA512(x) || SHA160(message) )\r
 568      * \r
 569      * This number is 512 bits long, so reducing it mod q won't be\r
 570      * noticeably non-uniform. So\r
 571      * \r
 572      *   k = proto_k mod q\r
 573      * \r
 574      * This has the interesting property that it's _deterministic_:\r
 575      * signing the same hash twice with the same key yields the\r
 576      * same signature.\r
 577      * \r
 578      * Despite this determinism, it's still not predictable to an\r
 579      * attacker, because in order to repeat the SHA-512\r
 580      * construction that created it, the attacker would have to\r
 581      * know the private key value x - and by assumption he doesn't,\r
 582      * because if he knew that he wouldn't be attacking k!\r
 583      *\r
 584      * (This trick doesn't, _per se_, protect against reuse of k.\r
 585      * Reuse of k is left to chance; all it does is prevent\r
 586      * _excessively high_ chances of reuse of k due to entropy\r
 587      * problems.)\r
 588      * \r
 589      * Thanks to Colin Plumb for the general idea of using x to\r
 590      * ensure k is hard to guess, and to the Cambridge University\r
 591      * Computer Security Group for helping to argue out all the\r
 592      * fine details.\r
 593      */\r
 594     struct dss_key *dss = (struct dss_key *) key;\r
 595     SHA512_State ss;\r
 596     unsigned char digest[20], digest512[64];\r
 597     Bignum proto_k, k, gkp, hash, kinv, hxr, r, s;\r
 598     unsigned char *bytes;\r
 599     int nbytes, i;\r
 600 \r
 601     SHA_Simple(data, datalen, digest);\r
 602 \r
 603     /*\r
 604      * Hash some identifying text plus x.\r
 605      */\r
 606     SHA512_Init(&ss);\r
 607     SHA512_Bytes(&ss, "DSA deterministic k generator", 30);\r
 608     sha512_mpint(&ss, dss->x);\r
 609     SHA512_Final(&ss, digest512);\r
 610 \r
 611     /*\r
 612      * Now hash that digest plus the message hash.\r
 613      */\r
 614     SHA512_Init(&ss);\r
 615     SHA512_Bytes(&ss, digest512, sizeof(digest512));\r
 616     SHA512_Bytes(&ss, digest, sizeof(digest));\r
 617 \r
 618     while (1) {\r
 619         SHA512_State ss2 = ss;         /* structure copy */\r
 620         SHA512_Final(&ss2, digest512);\r
 621 \r
 622         smemclr(&ss2, sizeof(ss2));\r
 623 \r
 624         /*\r
 625          * Now convert the result into a bignum, and reduce it mod q.\r
 626          */\r
 627         proto_k = bignum_from_bytes(digest512, 64);\r
 628         k = bigmod(proto_k, dss->q);\r
 629         freebn(proto_k);\r
 630         kinv = modinv(k, dss->q);              /* k^-1 mod q */\r
 631         if (!kinv) {                           /* very unlikely */\r
 632             freebn(k);\r
 633             /* Perturb the hash to think of a different k. */\r
 634             SHA512_Bytes(&ss, "x", 1);\r
 635             /* Go round and try again. */\r
 636             continue;\r
 637         }\r
 638 \r
 639         break;\r
 640     }\r
 641 \r
 642     smemclr(&ss, sizeof(ss));\r
 643 \r
 644     smemclr(digest512, sizeof(digest512));\r
 645 \r
 646     /*\r
 647      * Now we have k, so just go ahead and compute the signature.\r
 648      */\r
 649     gkp = modpow(dss->g, k, dss->p);   /* g^k mod p */\r
 650     r = bigmod(gkp, dss->q);           /* r = (g^k mod p) mod q */\r
 651     freebn(gkp);\r
 652 \r
 653     hash = bignum_from_bytes(digest, 20);\r
 654     hxr = bigmuladd(dss->x, r, hash);  /* hash + x*r */\r
 655     s = modmul(kinv, hxr, dss->q);     /* s = k^-1 * (hash + x*r) mod q */\r
 656     freebn(hxr);\r
 657     freebn(kinv);\r
 658     freebn(k);\r
 659     freebn(hash);\r
 660 \r
 661     /*\r
 662      * Signature blob is\r
 663      * \r
 664      *   string  "ssh-dss"\r
 665      *   string  two 20-byte numbers r and s, end to end\r
 666      * \r
 667      * i.e. 4+7 + 4+40 bytes.\r
 668      */\r
 669     nbytes = 4 + 7 + 4 + 40;\r
 670     bytes = snewn(nbytes, unsigned char);\r
 671     PUT_32BIT(bytes, 7);\r
 672     memcpy(bytes + 4, "ssh-dss", 7);\r
 673     PUT_32BIT(bytes + 4 + 7, 40);\r
 674     for (i = 0; i < 20; i++) {\r
 675         bytes[4 + 7 + 4 + i] = bignum_byte(r, 19 - i);\r
 676         bytes[4 + 7 + 4 + 20 + i] = bignum_byte(s, 19 - i);\r
 677     }\r
 678     freebn(r);\r
 679     freebn(s);\r
 680 \r
 681     *siglen = nbytes;\r
 682     return bytes;\r
 683 }\r
 684 \r
 685 const struct ssh_signkey ssh_dss = {\r
 686     dss_newkey,\r
 687     dss_freekey,\r
 688     dss_fmtkey,\r
 689     dss_public_blob,\r
 690     dss_private_blob,\r
 691     dss_createkey,\r
 692     dss_openssh_createkey,\r
 693     dss_openssh_fmtkey,\r
 694     dss_pubkey_bits,\r
 695     dss_fingerprint,\r
 696     dss_verifysig,\r
 697     dss_sign,\r
 698     "ssh-dss",\r
 699     "dss"\r
 700 };\r