+ /*
+ * The basic DSS signing algorithm is:
+ *
+ * - invent a random k between 1 and q-1 (exclusive).
+ * - Compute r = (g^k mod p) mod q.
+ * - Compute s = k^-1 * (hash + x*r) mod q.
+ *
+ * This has the dangerous properties that:
+ *
+ * - if an attacker in possession of the public key _and_ the
+ * signature (for example, the host you just authenticated
+ * to) can guess your k, he can reverse the computation of s
+ * and work out x = r^-1 * (s*k - hash) mod q. That is, he
+ * can deduce the private half of your key, and masquerade
+ * as you for as long as the key is still valid.
+ *
+ * - since r is a function purely of k and the public key, if
+ * the attacker only has a _range of possibilities_ for k
+ * it's easy for him to work through them all and check each
+ * one against r; he'll never be unsure of whether he's got
+ * the right one.
+ *
+ * - if you ever sign two different hashes with the same k, it
+ * will be immediately obvious because the two signatures
+ * will have the same r, and moreover an attacker in
+ * possession of both signatures (and the public key of
+ * course) can compute k = (hash1-hash2) * (s1-s2)^-1 mod q,
+ * and from there deduce x as before.
+ *
+ * - the Bleichenbacher attack on DSA makes use of methods of
+ * generating k which are significantly non-uniformly
+ * distributed; in particular, generating a 160-bit random
+ * number and reducing it mod q is right out.
+ *
+ * For this reason we must be pretty careful about how we
+ * generate our k. Since this code runs on Windows, with no
+ * particularly good system entropy sources, we can't trust our
+ * RNG itself to produce properly unpredictable data. Hence, we
+ * use a totally different scheme instead.
+ *
+ * What we do is to take a SHA-512 (_big_) hash of the private
+ * key x, and then feed this into another SHA-512 hash that
+ * also includes the message hash being signed. That is:
+ *
+ * proto_k = SHA512 ( SHA512(x) || SHA160(message) )
+ *
+ * This number is 512 bits long, so reducing it mod q won't be
+ * noticeably non-uniform. So
+ *
+ * k = proto_k mod q
+ *
+ * This has the interesting property that it's _deterministic_:
+ * signing the same hash twice with the same key yields the
+ * same signature.
+ *
+ * (It doesn't, _per se_, protect against reuse of k. Reuse of
+ * k is left to chance; all it does is prevent _excessively
+ * high_ chances of reuse of k due to entropy problems.)
+ *
+ * Thanks to Colin Plumb for the general idea of using x to
+ * ensure k is hard to guess, and to the Cambridge University
+ * Computer Security Group for helping to argue out all the
+ * fine details.
+ */
+ struct dss_key *dss = (struct dss_key *) key;
+ SHA512_State ss;
+ unsigned char digest[20], digest512[64];
+ Bignum proto_k, k, gkp, hash, kinv, hxr, r, s;
+ unsigned char *bytes;
+ int nbytes, i;
+
+ SHA_Simple(data, datalen, digest);
+
+ /*
+ * Hash some identifying text plus x.
+ */
+ SHA512_Init(&ss);
+ SHA512_Bytes(&ss, "DSA deterministic k generator", 30);
+ sha512_mpint(&ss, dss->x);
+ SHA512_Final(&ss, digest512);
+
+ /*
+ * Now hash that digest plus the message hash.
+ */
+ SHA512_Init(&ss);
+ SHA512_Bytes(&ss, digest512, sizeof(digest512));
+ SHA512_Bytes(&ss, digest, sizeof(digest));
+ SHA512_Final(&ss, digest512);
+
+ memset(&ss, 0, sizeof(ss));
+
+ /*
+ * Now convert the result into a bignum, and reduce it mod q.
+ */
+ proto_k = bignum_from_bytes(digest512, 64);
+ k = bigmod(proto_k, dss->q);
+ freebn(proto_k);
+
+ memset(digest512, 0, sizeof(digest512));
+
+ /*
+ * Now we have k, so just go ahead and compute the signature.
+ */
+ gkp = modpow(dss->g, k, dss->p); /* g^k mod p */
+ r = bigmod(gkp, dss->q); /* r = (g^k mod p) mod q */
+ freebn(gkp);
+
+ hash = bignum_from_bytes(digest, 20);
+ kinv = modinv(k, dss->q); /* k^-1 mod q */
+ hxr = bigmuladd(dss->x, r, hash); /* hash + x*r */
+ s = modmul(kinv, hxr, dss->q); /* s = k^-1 * (hash + x*r) mod q */
+ freebn(hxr);
+ freebn(kinv);
+ freebn(hash);
+
+ /*
+ * Signature blob is
+ *
+ * string "ssh-dss"
+ * string two 20-byte numbers r and s, end to end
+ *
+ * i.e. 4+7 + 4+40 bytes.
+ */
+ nbytes = 4 + 7 + 4 + 40;
+ bytes = smalloc(nbytes);
+ PUT_32BIT(bytes, 7);
+ memcpy(bytes + 4, "ssh-dss", 7);
+ PUT_32BIT(bytes + 4 + 7, 40);
+ for (i = 0; i < 20; i++) {
+ bytes[4 + 7 + 4 + i] = bignum_byte(r, 19 - i);
+ bytes[4 + 7 + 4 + 20 + i] = bignum_byte(s, 19 - i);
+ }
+ freebn(r);
+ freebn(s);
+
+ *siglen = nbytes;
+ return bytes;
projects / u / mdw / putty / commitdiff