Lines Matching +full:k +full:- +full:to +full:- +full:j
2 * Program to generate cryptographic keys for ntp clients and servers
7 * followed by a type-specific descriptive label and PEM-encoded data
18 * MD5 (128-bit) keys used to compute message digests in symmetric
35 * RSA: RSA-MD2, RSA-MD5, RSA-SHA, RSA-SHA1, RSA-MDC2, EVP-RIPEMD160
36 * DSA: DSA-SHA, DSA-SHA1
53 * Guillou-Quisquater (GQ) identity parameters and keys
57 * Mu-Varadharajan (MV) identity parameters and keys
60 * fails to generate and verify some cryptographic data, as indicated by
61 * exit status -1. In this case simply run the program again. If the
73 * 1000 took something over nine minutes to generate and verify the
77 * As described in the OpenSSL documentation, the file name defaults to
98 #include "ntp-keygen-opts.h"
190 * Don't try to follow symbolic links on Windows. Assume link == file.
203 * Don't try to create symbolic links on Windows, that is supported on
205 * and later), hardlink the linkname to the original filename. On
206 * earlier systems, user must rename file to match expected link for
207 * ntpd to find it. To allow building a ntp-keygen.exe which loads on
208 * Windows pre-XP, runtime link to CreateHardLinkA().
237 return -1;
246 mfprintf(stderr, "Create hard link %s to %s failed: %m\n",
249 return -1;
267 * followlink() - replace filename with its target if symlink.
269 * readlink() does not null-terminate the result.
288 if ((size_t)len > bufsiz - 1)
289 len = bufsiz - 1;
326 const char *ciphername = NULL; /* to encrypt priv. key */
348 fprintf(stderr, "Unable to initialize .rnd file\n");
360 * gethostname() won't null-terminate if hostname is exactly the
363 gethostname(hostbuf, sizeof(hostbuf) - 1);
364 hostbuf[COUNTOF(hostbuf) - 1] = '\0';
374 argc -= optct; // Just in case we care later.
458 /* -s @group is equivalent to -i group, host unch. */
467 * groupname variable is pointed to hostname for use in IFF, GQ,
489 exit (-1);
491 temp = RAND_load_file(pathbuf, -1);
496 exit (-1);
571 scheme = "RSA-MD5";
573 ciphername = "des-ede3-cbc";
577 exit(-1);
603 exit(-1);
655 * Write the nonencrypted GQ client parameters to the stdout
664 fprintf(stderr, "Writing GQ parameters %s to stdout\n",
684 * Write the encrypted GQ server keys to the stdout stream.
691 fprintf(stderr, "Writing GQ keys %s to stdout\n",
727 * Write the nonencrypted IFF client parameters to the stdout
736 fprintf(stderr, "Writing IFF parameters %s to stdout\n",
756 * Write the encrypted IFF server keys to the stdout stream.
763 fprintf(stderr, "Writing IFF keys %s to stdout\n",
782 * Create new encrypted MV trusted-authority keys file if
800 * Write the nonencrypted MV client parameters to the stdout
807 fprintf(stderr, "Writing MV parameters %s to stdout\n",
821 * Write the encrypted MV server keys to the stdout stream.
826 fprintf(stderr, "Writing MV keys %s to stdout\n",
848 exit (-1);
857 * Generate semi-random MD5 keys compatible with NTPv3 and NTPv4. Also,
868 int i, j;
877 for (j = 0; j < MD5SIZE; j++) {
885 if (-1 == rc) {
887 exit (-1);
895 md5key[j] = temp;
897 md5key[j] = '\0';
904 for (j = 0; j < MD5SIZE; j++) {
905 hexstr[2 * j] = hex[keystr[j] >> 4];
906 hexstr[2 * j + 1] = hex[keystr[j] & 0xf];
920 * readkey - load cryptographic parameters and keys
922 * This routine loads a PEM-encoded file of given name and password and
923 * extracts the filestamp from the file name. It returns a pointer to
969 * Read and decrypt PEM-encoded private keys. The first one
970 * found is returned. If others are expected, add them to the
973 for (i = 0; i <= MVMAX - 1;) {
998 exit (-1);
1029 * modulus turns out to be non-prime. Just for grins, we check
1119 * authority and the certificate cannot be used to convey public
1123 * securely transmitted to all servers of the group; client files can be
1130 * cryptography and described in Stimson p. 285. The p is a 512-bit
1131 * prime, g a generator of Zp* and q a 160-bit prime that divides p - 1
1134 * sends (p, q, g, b) to the servers and (p, q, g, v) to the clients.
1135 * Alice challenges Bob to confirm identity using the protocol described
1141 * p, q and generator g. The TA gives private key b to Bob and public
1142 * key v to Alice.
1144 * Alice rolls new random challenge r (o < r < q) and sends to Bob in
1145 * the IFF request message. Bob rolls new random k (0 < k < q), then
1146 * computes y = k + b r mod q and x = g^k mod p and sends (y, hash(x))
1147 * to Alice in the response message. Besides making the response
1148 * shorter, the hash makes it effectivey impossible for an intruder to
1152 * of algebra, this simplifies to g^k. If the hash of this result
1154 * response binds this knowledge to Bob's private key and the public key
1168 BIGNUM *b, *r, *k, *u, *v, *w; /* BN temp */
1190 * private key are distributed to the servers, while all except
1191 * the private key are distributed to the clients.
1193 b = BN_new(); r = BN_new(); k = BN_new();
1195 BN_rand(b, BN_num_bits(q), -1, 0); /* a */
1198 BN_mod_exp(v, g, v, p, ctx); /* g^(q - b) mod p */
1203 "Confirm g^(q - b) g^b = 1 mod p: %s\n", temp == 1 ?
1206 BN_free(b); BN_free(r); BN_free(k);
1216 * random nonce r mod q and sends it to Bob. She needs only
1219 BN_rand(r, BN_num_bits(q), -1, 0); /* r */
1223 * Bob rolls random nonce k mod q, computes y = k + b r mod q
1224 * and x = g^k mod p, then sends (y, x) to Alice. He needs
1227 BN_rand(k, BN_num_bits(q), -1, 0); /* k, 0 < k < q */
1228 BN_mod(k, k, q, ctx);
1230 BN_add(v, v, k);
1231 BN_mod(v, v, q, ctx); /* y = k + b r mod q */
1232 BN_mod_exp(u, g, k, p, ctx); /* x = g^k mod p */
1235 * Alice verifies x = g^y v^r to confirm that Bob has group key
1245 "Confirm g^k = g^(k + b r) g^(q - b) r: %s\n", temp ==
1247 BN_free(b); BN_free(r); BN_free(k);
1281 * The following routines implement the Guillou-Quisquater (GQ) *
1286 * The Guillou-Quisquater (GQ) identity scheme is intended for use when
1287 * the certificate can be used to convey public parameters. The scheme
1289 * a private key known only to servers. There are two kinds of files:
1292 * generations of server files must be securely transmitted to all
1300 * cryptography and described in Stimson p. 300 (with errors). The 512-
1303 * are known to all group members.
1307 * is the inverse obscured by the group key v = (u^-1)^b. These values
1309 * scheme. Alice challenges Bob to confirm identity using the protocol
1318 * key (u^-1)^b, although not necessarily the same ones. Bob and Alice
1319 * can regenerate the key pair from time to time without affecting
1323 * Alice rolls new random challenge r and sends to Bob in the GQ
1324 * request message. Bob rolls new random k, then computes y = k u^r mod
1325 * n and x = k^b mod n and sends (y, hash(x)) to Alice in the response
1327 * effectivey impossible for an intruder to solve for b by observing
1331 * of algebra, this simplifies to k^b. If the hash of this result
1333 * response binds this knowledge to Bob's private key and the public key
1337 * Generate Guillou-Quisquater (GQ) parameters file.
1347 BIGNUM *u, *v, *g, *k, *r, *y; /* BN temps */
1368 k = BN_new(); r = BN_new(); y = BN_new();
1373 * the RSA structure. The group key is transmitted to each group
1377 BN_rand(b, BN_num_bits(n), -1, 0); /* b */
1382 * u, then computes inverse v = u^-1.
1384 BN_rand(u, BN_num_bits(n), -1, 0); /* u */
1386 BN_mod_inverse(v, u, n, ctx); /* u^-1 mod n */
1387 BN_mod_mul(k, v, u, n, ctx);
1390 * Bob computes public key v = (u^-1)^b, which is saved in an
1396 BN_mod_mul(g, g, v, n, ctx); /* u^b (u^-1)^b */
1399 "Confirm u^b (u^-1)^b = 1 mod n: %s\n", temp ? "yes" :
1403 BN_free(g); BN_free(k); BN_free(r); BN_free(y);
1409 * Since we use these values again, we have to pass in dupes,
1416 * random nonce r mod n and sends it to Bob. She needs only n
1419 BN_rand(r, BN_num_bits(n), -1, 0); /* r */
1423 * Bob rolls random nonce k mod n, computes y = k u^r mod n and
1424 * g = k^b mod n, then sends (y, g) to Alice. He needs n, u, b
1427 BN_rand(k, BN_num_bits(n), -1, 0); /* k */
1428 BN_mod(k, k, n, ctx);
1430 BN_mod_mul(y, k, y, n, ctx); /* y = k u^r mod n */
1431 BN_mod_exp(g, k, b, n, ctx); /* g = k^b mod n */
1434 * Alice verifies g = v^r y^b mod n to confirm that Bob has
1436 * (u^-1)^b from the certificate, (y, g) from Bob and the
1444 fprintf(stderr, "Confirm g^k = v^r y^b mod n: %s\n", temp == 0 ?
1447 BN_free(g); BN_free(k); BN_free(r); BN_free(y);
1461 * q public key (u^-1)^b
1484 * The following routines implement the Mu-Varadharajan (MV) identity *
1489 * The Mu-Varadharajan (MV) cryptosystem was originally intended when
1490 * servers broadcast messages to clients, but clients never send
1491 * messages to servers. There is one encryption key for the server and a
1493 * pay-per-view satellite broadcasting system where the session key is
1495 * tamperproof set-top box.
1499 * different way. The values are used in an encryption scheme similar to
1501 * product terms (x - x[j]), as described in Mu, Y., and V.
1503 * 223-231. The paper has significant errors and serious omissions.
1505 * Let q be the product of n distinct primes s1[j] (j = 1...n), where
1506 * each s1[j] has m significant bits. Let p be a prime p = 2 * q + 1, so
1507 * that q and each s1[j] divide p - 1 and p has M = n * m + 1
1508 * significant bits. Let g be a generator of Zp; that is, gcd(g, p - 1)
1510 * project into Zp* as exponents of g. Sometimes we have to compute an
1511 * inverse b^-1 of random b in Zq, but for that purpose we require
1512 * gcd(b, q) = 1. We expect M to be in the 500-bit range and n
1514 * they are expensive to compute.
1517 * values x[j] mod q (j = 1...n), are generated as the zeros of a
1518 * polynomial of order n. The product terms (x - x[j]) are expanded to
1520 * used as exponents of the generator g mod p to generate the private
1522 * pairs (xbar[j], xhat[j]) (j = 1...n) of private client keys are used
1523 * to construct the decryption keys. The devil is in the details.
1528 * keys xbar[j] and xhat[j] for each client j. The partial decryption
1529 * files are used to compute the inverse of E. These values are suitably
1532 * The distinguishing characteristic of this scheme is the capability to
1534 * product s = prod(s1[j]) (j = 1...n) above. If the factor s1[j] is
1536 * recomputed, the jth client will no longer be able to compute E^-1 and
1537 * thus unable to decrypt the messageblock.
1544 * Alice rolls new random nonce r mod p and sends to Bob in the MV
1545 * request message. Bob rolls random nonce k mod q, encrypts y = r E^k
1546 * mod p and sends (y, gbar^k, ghat^k) to Alice.
1548 * Alice receives the response and computes the inverse (E^k)^-1 from
1549 * the partial decryption keys gbar^k, ghat^k, xbar and xhat. She then
1551 * response binds this knowledge to Bob's private key and the public key
1576 int i, j, n;
1583 * The object is to generate a multiplicative group Zp* modulo a
1585 * distinct primes s1[j] (j = 1...n) and q divides p - 1. We
1586 * first generate n m-bit primes, where the product n m is in
1587 * the order of 512 bits. One or more of these may have to be
1588 * replaced later. As a practical matter, it is tough to find
1603 for (j = 1; j <= n; j++) {
1604 s1[j] = BN_new();
1606 BN_generate_prime_ex(s1[j], modulus2 / n, 0,
1608 for (i = 1; i < j; i++) {
1609 if (BN_cmp(s1[i], s1[j]) == 0)
1612 if (i == j)
1624 * we have to reveal p to servers, but not clients. However,
1625 * factoring q to find the primes should be adequately hard, as
1627 * it as hard to find n small prime factors totalling n bits as
1628 * it is to find two large prime factors totalling n bits?
1634 for (j = 1; j <= n; j++)
1635 BN_mul(q, q, s1[j], ctx);
1643 j = temp % n + 1;
1654 BN_copy(s1[j], u);
1660 * gcd(g, p - 1) = 1 and g^q = 1. This is a generator of p, not
1666 BN_rand(g, BN_num_bits(p) - 1, 0, 0);
1680 * Setup is now complete. Roll random polynomial roots x[j]
1681 * (j = 1...n) for all j. While it may not be strictly
1688 for (j = 1; j <= n; j++) {
1689 x[j] = BN_new();
1692 BN_rand(x[j], BN_num_bits(q), 0, 0);
1693 BN_mod(x[j], x[j], q, ctx);
1694 BN_gcd(u, x[j], q, ctx);
1702 * expansion of root products (x - x[j]) mod q for all j. The
1709 for (j = 1; j <= n; j++) {
1711 for (i = 0; i < j; i++) {
1713 BN_mod_mul(v, a[i], x[j], q, ctx);
1730 * Verify prod(gs[i]^(a[i] x[j]^i)) = 1 for all i, j. Note the
1731 * a[i] x[j]^i exponent is computed mod q, but the gs[i] is
1736 for (j = 1; j <= n; j++) {
1740 BN_mod_exp(v, x[j], v, q, ctx);
1749 "Confirm prod(gs[i]^(x[j]^i)) = 1 for all i, j: %s\n", temp ?
1757 * since it is expensive to compute.
1762 for (j = 1; j <= n; j++) {
1765 BN_mod_exp(v, x[j], v, q, ctx);
1773 * gcd(b, q) = 1 to guarantee b^-1 exists, then compute b^-1
1786 * Make private client keys (xbar[j], xhat[j]) for all j. Note
1787 * that the keys for the jth client do not s1[j] or the product
1788 * s1[j]) (j = 1...n) which is q by construction.
1790 * Compute the factor w such that w s1[j] = s1[j] for all j. The
1791 * easy way to do this is to compute (q + s1[j]) / s1[j].
1794 for (j = 1; j <= n; j++) {
1795 xbar[j] = BN_new(); xhat[j] = BN_new();
1797 BN_add(w, q, s1[j]);
1798 BN_div(w, u, w, s1[j], ctx);
1799 BN_zero(xbar[j]);
1802 if (i == j)
1806 BN_add(xbar[j], xbar[j], u);
1808 BN_mod_mul(xbar[j], xbar[j], b1, q, ctx);
1809 BN_mod_exp(xhat[j], x[j], v, q, ctx);
1810 BN_mod_mul(xhat[j], xhat[j], w, q, ctx);
1814 * We revoke client j by dividing q by s1[j]. The quotient
1815 * becomes the enabling key s. Note we always have to revoke
1817 * identical. For the present there are no provisions to revoke
1825 * For each combination of clients to be revoked, make private
1827 * and ghat = g^(s b), all mod p. The servers use these keys to
1840 * step is to generate the system parameters p, q, g, b, A and
1841 * the enabling keys s1[j]. Associated with each s1[j] are
1842 * parameters xbar[j] and xhat[j]. All of these parameters are
1843 * retained in a data structure protecteted by the trusted-agent
1844 * password. The p, xbar[j] and xhat[j] paremeters are
1845 * distributed to the j clients. When the client keys are to be
1846 * activated, the enabled keys are multipied together to form
1848 * used to compute the server encryption key E and the partial
1852 * it to the server. The server rolls random k, which is used
1853 * only once, then computes the session key E^k and partial
1854 * decryption keys gbar^k and ghat^k. The server sends the
1855 * encrypted r along with gbar^k and ghat^k to the client. The
1859 * Write the MV trusted-agent parameters and keys as a DSA
1871 fprintf(stderr, "Generating MV trusted-authority keys\n");
1888 * q modulus q (used only when generating k)
1907 * Append the MV client parameters for each client j as DSA keys
1911 * priv_key xbar[j] mod q
1912 * pub_key xhat[j] mod q
1916 for (j = 1; j <= n; j++) {
1920 DSA_set0_key(sdsa, BN_dup(xhat[j]), BN_dup(xbar[j]));
1930 * The product (gbar^k)^xbar[j] (ghat^k)^xhat[j] and E
1935 BN_mod_exp(v, gbar, xhat[j], p, ctx);
1936 BN_mod_exp(u, ghat, xbar[j], p, ctx);
1940 fprintf(stderr, "Revoke key %d\n", j);
1953 for (j = 1; j <= n; j++) {
1954 BN_free(x[j]); BN_free(xbar[j]); BN_free(xhat[j]);
1955 BN_free(s1[j]);
1966 * self-signed certificate, the issuer name is the same as the subject
1968 * validity interval extends from the current time to the same time one
1969 * year hence. For NTP purposes, it is convenient to use the NTP seconds
1990 * Generate X509 self-signed certificate.
1992 * Set the certificate serial to the NTP seconds for grins. Set
1993 * the version to 3. Set the initial validity to the current
2008 (u_char *)name, -1, -1, 0);
2011 (u_char *)name, -1, -1, 0);
2025 * The basic_constraints extension CA:TRUE allows servers to
2032 if (!X509_add_ext(cert, ex, -1)) {
2045 if (!X509_add_ext(cert, ex, -1)) {
2059 if (!X509_add_ext(cert, ex, -1)) {
2070 * here. The semantics probably do not conform to the designer's
2080 if (!X509_add_ext(cert, ex, -1)) {
2115 * asn2ntp - convert ASN1_TIME time structure to NTP time
2119 ASN1_TIME *asn1time /* pointer to ASN1_TIME structure */
2122 char *v; /* pointer to ASN1_TIME string */
2129 * for UTC. Also note that years less than 50 map to years
2132 if (asn1time->length > 13)
2133 return (-1);
2134 v = (char *)asn1time->data;
2135 tm.tm_year = (v[0] - '0') * 10 + v[1] - '0';
2138 tm.tm_mon = (v[2] - '0') * 10 + v[3] - '0' - 1;
2139 tm.tm_mday = (v[4] - '0') * 10 + v[5] - '0';
2140 tm.tm_hour = (v[6] - '0') * 10 + v[7] - '0';
2141 tm.tm_min = (v[8] - '0') * 10 + v[9] - '0';
2142 tm.tm_sec = (v[10] - '0') * 10 + v[11] - '0';
2286 exit (-1);
2299 fprintf(stderr, "%s->%s\n", linkname, filename);