2 * Program to generate cryptographic keys for ntp clients and servers
4 * This program generates password encrypted data files for use with the
5 * Autokey security protocol and Network Time Protocol Version 4. Files
6 * are prefixed with a header giving the name and date of creation
7 * followed by a type-specific descriptive label and PEM-encoded data
8 * structure compatible with programs of the OpenSSL library.
10 * All file names are like "ntpkey_<type>_<hostname>.<filestamp>", where
11 * <type> is the file type, <hostname> the generating host name and
12 * <filestamp> the generation time in NTP seconds. The NTP programs
13 * expect generic names such as "ntpkey_<type>_whimsy.udel.edu" with the
14 * association maintained by soft links. Following is a list of file
15 * types; the first line is the file name and the second link name.
17 * ntpkey_MD5key_<hostname>.<filestamp>
18 * MD5 (128-bit) keys used to compute message digests in symmetric
21 * ntpkey_RSAhost_<hostname>.<filestamp>
22 * ntpkey_host_<hostname>
23 * RSA private/public host key pair used for public key signatures
25 * ntpkey_RSAsign_<hostname>.<filestamp>
26 * ntpkey_sign_<hostname>
27 * RSA private/public sign key pair used for public key signatures
29 * ntpkey_DSAsign_<hostname>.<filestamp>
30 * ntpkey_sign_<hostname>
31 * DSA Private/public sign key pair used for public key signatures
33 * Available digest/signature schemes
35 * RSA: RSA-MD2, RSA-MD5, RSA-SHA, RSA-SHA1, RSA-MDC2, EVP-RIPEMD160
36 * DSA: DSA-SHA, DSA-SHA1
38 * ntpkey_XXXcert_<hostname>.<filestamp>
39 * ntpkey_cert_<hostname>
40 * X509v3 certificate using RSA or DSA public keys and signatures.
41 * XXX is a code identifying the message digest and signature
42 * encryption algorithm
44 * Identity schemes. The key type par is used for the challenge; the key
45 * type key is used for the response.
47 * ntpkey_IFFkey_<groupname>.<filestamp>
48 * ntpkey_iffkey_<groupname>
49 * Schnorr (IFF) identity parameters and keys
51 * ntpkey_GQkey_<groupname>.<filestamp>,
52 * ntpkey_gqkey_<groupname>
53 * Guillou-Quisquater (GQ) identity parameters and keys
55 * ntpkey_MVkeyX_<groupname>.<filestamp>,
56 * ntpkey_mvkey_<groupname>
57 * Mu-Varadharajan (MV) identity parameters and keys
59 * Note: Once in a while because of some statistical fluke this program
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
62 * program does complete with exit code 0, the data are correct as
65 * These cryptographic routines are characterized by the prime modulus
66 * size in bits. The default value of 512 bits is a compromise between
67 * cryptographic strength and computing time and is ordinarily
68 * considered adequate for this application. The routines have been
69 * tested with sizes of 256, 512, 1024 and 2048 bits. Not all message
70 * digest and signature encryption schemes work with sizes less than 512
71 * bits. The computing time for sizes greater than 2048 bits is
72 * prohibitive on all but the fastest processors. An UltraSPARC Blade
73 * 1000 took something over nine minutes to generate and verify the
74 * values with size 2048. An old SPARC IPC would take a week.
76 * The OpenSSL library used by this program expects a random seed file.
77 * As described in the OpenSSL documentation, the file name defaults to
78 * first the RANDFILE environment variable in the user's home directory
79 * and then .rnd in the user's home directory.
90 #include <sys/types.h>
93 #include "ntp_random.h"
94 #include "ntp_stdlib.h"
95 #include "ntp_assert.h"
96 #include "ntp_libopts.h"
97 #include "ntp_unixtime.h"
98 #include "ntp-keygen-opts.h"
101 #include "openssl/asn1.h"
102 #include "openssl/bn.h"
103 #include "openssl/crypto.h"
104 #include "openssl/evp.h"
105 #include "openssl/err.h"
106 #include "openssl/rand.h"
107 #include "openssl/opensslv.h"
108 #include "openssl/pem.h"
109 #include "openssl/x509.h"
110 #include "openssl/x509v3.h"
111 #include <openssl/objects.h>
112 #include "libssl_compat.h"
114 #include <ssl_applink.c>
116 #define _UC(str) ((char *)(intptr_t)(str))
120 #define MD5KEYS 10 /* number of keys generated of each type */
121 #define MD5SIZE 20 /* maximum key size */
123 #define PLEN 512 /* default prime modulus size (bits) */
124 #define ILEN 256 /* default identity modulus size (bits) */
125 #define MVMAX 100 /* max MV parameters */
128 * Strings used in X509v3 extension fields
130 #define KEY_USAGE "digitalSignature,keyCertSign"
131 #define BASIC_CONSTRAINTS "critical,CA:TRUE"
132 #define EXT_KEY_PRIVATE "private"
133 #define EXT_KEY_TRUST "trustRoot"
139 FILE *fheader (const char *, const char *, const char *);
140 int gen_md5 (const char *);
141 void followlink (char *, size_t);
143 EVP_PKEY *gen_rsa (const char *);
144 EVP_PKEY *gen_dsa (const char *);
145 EVP_PKEY *gen_iffkey (const char *);
146 EVP_PKEY *gen_gqkey (const char *);
147 EVP_PKEY *gen_mvkey (const char *, EVP_PKEY **);
148 void gen_mvserv (char *, EVP_PKEY **);
149 int x509 (EVP_PKEY *, const EVP_MD *, char *, const char *,
151 void cb (int, int, void *);
152 EVP_PKEY *genkey (const char *, const char *);
153 EVP_PKEY *readkey (char *, char *, u_int *, EVP_PKEY **);
154 void writekey (char *, char *, u_int *, EVP_PKEY **);
155 u_long asn2ntp (ASN1_TIME *);
157 static DSA* genDsaParams(int, char*);
158 static RSA* genRsaKeyPair(int, char*);
165 extern char *optarg; /* command line argument */
166 char const *progname;
167 u_int lifetime = DAYSPERYEAR; /* certificate lifetime (days) */
168 int nkeys; /* MV keys */
169 time_t epoch; /* Unix epoch (seconds) since 1970 */
170 u_int fstamp; /* NTP filestamp */
171 char hostbuf[MAXHOSTNAME + 1];
172 char *hostname = NULL; /* host, used in cert filenames */
173 char *groupname = NULL; /* group name */
174 char certnamebuf[2 * sizeof(hostbuf)];
175 char *certname = NULL; /* certificate subject/issuer name */
176 char *passwd1 = NULL; /* input private key password */
177 char *passwd2 = NULL; /* output private key password */
178 char filename[MAXFILENAME + 1]; /* file name */
180 u_int modulus = PLEN; /* prime modulus size (bits) */
181 u_int modulus2 = ILEN; /* identity modulus size (bits) */
182 long d0, d1, d2, d3; /* callback counters */
183 const EVP_CIPHER * cipher = NULL;
187 BOOL init_randfile();
190 * Don't try to follow symbolic links on Windows. Assume link == file.
199 return (int)strlen(file); /* assume no overflow possible */
203 * Don't try to create symbolic links on Windows, that is supported on
204 * Vista and later only. Instead, if CreateHardLink is available (XP
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().
216 typedef BOOL (WINAPI *PCREATEHARDLINKA)(
217 __in LPCSTR lpFileName,
218 __in LPCSTR lpExistingFileName,
219 __reserved LPSECURITY_ATTRIBUTES lpSA
221 static PCREATEHARDLINKA pCreateHardLinkA;
230 hDll = LoadLibrary("kernel32");
231 pfn = GetProcAddress(hDll, "CreateHardLinkA");
232 pCreateHardLinkA = (PCREATEHARDLINKA)pfn;
235 if (NULL == pCreateHardLinkA) {
240 link_created = (*pCreateHardLinkA)(linkname, filename, NULL);
245 saved_errno = GetLastError(); /* yes we play loose */
246 mfprintf(stderr, "Create hard link %s to %s failed: %m\n",
254 WORD wVersionRequested;
256 wVersionRequested = MAKEWORD(2,0);
257 if (WSAStartup(wVersionRequested, &wsaData))
259 fprintf(stderr, "No useable winsock.dll\n");
263 #endif /* SYS_WINNT */
267 * followlink() - replace filename with its target if symlink.
269 * Some readlink() implementations do not null-terminate the result.
281 len = readlink(fname, fname, (int)bufsiz);
286 if (len > (int)bufsiz - 1)
287 len = (int)bufsiz - 1;
297 int argc, /* command line options */
301 struct timeval tv; /* initialization vector */
302 int md5key = 0; /* generate MD5 keys */
303 int optct; /* option count */
305 X509 *cert = NULL; /* X509 certificate */
306 EVP_PKEY *pkey_host = NULL; /* host key */
307 EVP_PKEY *pkey_sign = NULL; /* sign key */
308 EVP_PKEY *pkey_iffkey = NULL; /* IFF sever keys */
309 EVP_PKEY *pkey_gqkey = NULL; /* GQ server keys */
310 EVP_PKEY *pkey_mvkey = NULL; /* MV trusted agen keys */
311 EVP_PKEY *pkey_mvpar[MVMAX]; /* MV cleient keys */
312 int hostkey = 0; /* generate RSA keys */
313 int iffkey = 0; /* generate IFF keys */
314 int gqkey = 0; /* generate GQ keys */
315 int mvkey = 0; /* update MV keys */
316 int mvpar = 0; /* generate MV parameters */
317 char *sign = NULL; /* sign key */
318 EVP_PKEY *pkey = NULL; /* temp key */
319 const EVP_MD *ectx; /* EVP digest */
320 char pathbuf[MAXFILENAME + 1];
321 const char *scheme = NULL; /* digest/signature scheme */
322 const char *ciphername = NULL; /* to encrypt priv. key */
323 const char *exten = NULL; /* private extension */
324 char *grpkey = NULL; /* identity extension */
325 int nid; /* X509 digest/signature scheme */
326 FILE *fstr = NULL; /* file handle */
327 char groupbuf[MAXHOSTNAME + 1];
334 const char *sslvtext;
341 /* Initialize before OpenSSL checks */
343 if (!init_randfile())
344 fprintf(stderr, "Unable to initialize .rnd file\n");
352 ntp_crypto_srandom();
355 * Process options, initialize host name and timestamp.
356 * gethostname() won't null-terminate if hostname is exactly the
357 * length provided for the buffer.
359 gethostname(hostbuf, sizeof(hostbuf) - 1);
360 hostbuf[COUNTOF(hostbuf) - 1] = '\0';
365 GETTIMEOFDAY(&tv, NULL);
367 fstamp = (u_int)(epoch + JAN_1970);
369 optct = ntpOptionProcess(&ntp_keygenOptions, argc, argv);
370 argc -= optct; // Just in case we care later.
371 argv += optct; // Just in case we care later.
374 sslvtext = OpenSSL_version(OPENSSL_VERSION);
375 sslvmatch = OpenSSL_version_num() == OPENSSL_VERSION_NUMBER;
377 fprintf(stderr, "Using OpenSSL version %s\n",
380 fprintf(stderr, "Built against OpenSSL %s, using version %s\n",
381 OPENSSL_VERSION_TEXT, sslvtext);
384 debug = OPT_VALUE_SET_DEBUG_LEVEL;
386 if (HAVE_OPT( MD5KEY ))
389 if (HAVE_OPT( PASSWORD ))
390 passwd1 = estrdup(OPT_ARG( PASSWORD ));
392 if (HAVE_OPT( EXPORT_PASSWD ))
393 passwd2 = estrdup(OPT_ARG( EXPORT_PASSWD ));
395 if (HAVE_OPT( HOST_KEY ))
398 if (HAVE_OPT( SIGN_KEY ))
399 sign = estrdup(OPT_ARG( SIGN_KEY ));
401 if (HAVE_OPT( GQ_PARAMS ))
404 if (HAVE_OPT( IFFKEY ))
407 if (HAVE_OPT( MV_PARAMS )) {
409 nkeys = OPT_VALUE_MV_PARAMS;
411 if (HAVE_OPT( MV_KEYS )) {
413 nkeys = OPT_VALUE_MV_KEYS;
416 if (HAVE_OPT( IMBITS ))
417 modulus2 = OPT_VALUE_IMBITS;
419 if (HAVE_OPT( MODULUS ))
420 modulus = OPT_VALUE_MODULUS;
422 if (HAVE_OPT( CERTIFICATE ))
423 scheme = OPT_ARG( CERTIFICATE );
425 if (HAVE_OPT( CIPHER ))
426 ciphername = OPT_ARG( CIPHER );
428 if (HAVE_OPT( SUBJECT_NAME ))
429 hostname = estrdup(OPT_ARG( SUBJECT_NAME ));
431 if (HAVE_OPT( IDENT ))
432 groupname = estrdup(OPT_ARG( IDENT ));
434 if (HAVE_OPT( LIFETIME ))
435 lifetime = OPT_VALUE_LIFETIME;
437 if (HAVE_OPT( PVT_CERT ))
438 exten = EXT_KEY_PRIVATE;
440 if (HAVE_OPT( TRUSTED_CERT ))
441 exten = EXT_KEY_TRUST;
444 * Remove the group name from the hostname variable used
445 * in host and sign certificate file names.
447 if (hostname != hostbuf)
448 ptr = strchr(hostname, '@');
453 groupname = estrdup(ptr + 1);
454 /* -s @group is equivalent to -i group, host unch. */
460 * Derive host certificate issuer/subject names from host name
461 * and optional group. If no groupname is provided, the issuer
462 * and subject is the hostname with no '@group', and the
463 * groupname variable is pointed to hostname for use in IFF, GQ,
464 * and MV parameters file names.
466 if (groupname == hostbuf) {
469 snprintf(certnamebuf, sizeof(certnamebuf), "%s@%s",
470 hostname, groupname);
471 certname = certnamebuf;
475 * Seed random number generator and grow weeds.
477 #if OPENSSL_VERSION_NUMBER < 0x10100000L
478 ERR_load_crypto_strings();
479 OpenSSL_add_all_algorithms();
480 #endif /* OPENSSL_VERSION_NUMBER */
481 if (!RAND_status()) {
482 if (RAND_file_name(pathbuf, sizeof(pathbuf)) == NULL) {
483 fprintf(stderr, "RAND_file_name %s\n",
484 ERR_error_string(ERR_get_error(), NULL));
487 temp = RAND_load_file(pathbuf, -1);
490 "RAND_load_file %s not found or empty\n",
495 "Random seed file %s %u bytes\n", pathbuf, temp);
496 RAND_add(&epoch, sizeof(epoch), 4.0);
501 * Create new unencrypted MD5 keys file if requested. If this
502 * option is selected, ignore all other options.
511 * Load previous certificate if available.
513 snprintf(filename, sizeof(filename), "ntpkey_cert_%s", hostname);
514 if ((fstr = fopen(filename, "r")) != NULL) {
515 cert = PEM_read_X509(fstr, NULL, NULL, NULL);
521 * Extract subject name.
523 X509_NAME_oneline(X509_get_subject_name(cert), groupbuf,
527 * Extract digest/signature scheme.
529 if (scheme == NULL) {
530 nid = X509_get_signature_nid(cert);
531 scheme = OBJ_nid2sn(nid);
535 * If a key_usage extension field is present, determine
536 * whether this is a trusted or private certificate.
539 ptr = strstr(groupbuf, "CN=");
540 cnt = X509_get_ext_count(cert);
541 for (i = 0; i < cnt; i++) {
545 ext = X509_get_ext(cert, i);
546 obj = X509_EXTENSION_get_object(ext);
548 if (OBJ_obj2nid(obj) ==
550 bp = BIO_new(BIO_s_mem());
551 X509V3_EXT_print(bp, ext, 0, 0);
552 BIO_gets(bp, pathbuf,
557 exten = EXT_KEY_TRUST;
558 else if (strcmp(pathbuf,
560 exten = EXT_KEY_PRIVATE;
561 certname = estrdup(ptr + 3);
568 if (ciphername == NULL)
569 ciphername = "des-ede3-cbc";
570 cipher = EVP_get_cipherbyname(ciphername);
571 if (cipher == NULL) {
572 fprintf(stderr, "Unknown cipher %s\n", ciphername);
575 fprintf(stderr, "Using host %s group %s\n", hostname,
579 * Create a new encrypted RSA host key file if requested;
580 * otherwise, look for an existing host key file. If not found,
581 * create a new encrypted RSA host key file. If that fails, go
585 pkey_host = genkey("RSA", "host");
586 if (pkey_host == NULL) {
587 snprintf(filename, sizeof(filename), "ntpkey_host_%s", hostname);
588 pkey_host = readkey(filename, passwd1, &fstamp, NULL);
589 if (pkey_host != NULL) {
590 followlink(filename, sizeof(filename));
591 fprintf(stderr, "Using host key %s\n",
594 pkey_host = genkey("RSA", "host");
597 if (pkey_host == NULL) {
598 fprintf(stderr, "Generating host key fails\n");
603 * Create new encrypted RSA or DSA sign keys file if requested;
604 * otherwise, look for an existing sign key file. If not found,
605 * use the host key instead.
608 pkey_sign = genkey(sign, "sign");
609 if (pkey_sign == NULL) {
610 snprintf(filename, sizeof(filename), "ntpkey_sign_%s",
612 pkey_sign = readkey(filename, passwd1, &fstamp, NULL);
613 if (pkey_sign != NULL) {
614 followlink(filename, sizeof(filename));
615 fprintf(stderr, "Using sign key %s\n",
618 pkey_sign = pkey_host;
619 fprintf(stderr, "Using host key as sign key\n");
624 * Create new encrypted GQ server keys file if requested;
625 * otherwise, look for an exisiting file. If found, fetch the
626 * public key for the certificate.
629 pkey_gqkey = gen_gqkey("gqkey");
630 if (pkey_gqkey == NULL) {
631 snprintf(filename, sizeof(filename), "ntpkey_gqkey_%s",
633 pkey_gqkey = readkey(filename, passwd1, &fstamp, NULL);
634 if (pkey_gqkey != NULL) {
635 followlink(filename, sizeof(filename));
636 fprintf(stderr, "Using GQ parameters %s\n",
640 if (pkey_gqkey != NULL) {
644 rsa = EVP_PKEY_get0_RSA(pkey_gqkey);
645 RSA_get0_factors(rsa, NULL, &q);
646 grpkey = BN_bn2hex(q);
650 * Write the nonencrypted GQ client parameters to the stdout
651 * stream. The parameter file is the server key file with the
652 * private key obscured.
654 if (pkey_gqkey != NULL && HAVE_OPT(ID_KEY)) {
657 snprintf(filename, sizeof(filename),
658 "ntpkey_gqpar_%s.%u", groupname, fstamp);
659 fprintf(stderr, "Writing GQ parameters %s to stdout\n",
661 fprintf(stdout, "# %s\n# %s\n", filename,
663 /* XXX: This modifies the private key and should probably use a
664 * copy of it instead. */
665 rsa = EVP_PKEY_get0_RSA(pkey_gqkey);
666 RSA_set0_factors(rsa, BN_dup(BN_value_one()), BN_dup(BN_value_one()));
667 pkey = EVP_PKEY_new();
668 EVP_PKEY_assign_RSA(pkey, rsa);
669 PEM_write_PKCS8PrivateKey(stdout, pkey, NULL, NULL, 0,
673 RSA_print_fp(stderr, rsa, 0);
677 * Write the encrypted GQ server keys to the stdout stream.
679 if (pkey_gqkey != NULL && passwd2 != NULL) {
682 snprintf(filename, sizeof(filename),
683 "ntpkey_gqkey_%s.%u", groupname, fstamp);
684 fprintf(stderr, "Writing GQ keys %s to stdout\n",
686 fprintf(stdout, "# %s\n# %s\n", filename,
688 rsa = EVP_PKEY_get0_RSA(pkey_gqkey);
689 pkey = EVP_PKEY_new();
690 EVP_PKEY_assign_RSA(pkey, rsa);
691 PEM_write_PKCS8PrivateKey(stdout, pkey, cipher, NULL, 0,
695 RSA_print_fp(stderr, rsa, 0);
699 * Create new encrypted IFF server keys file if requested;
700 * otherwise, look for existing file.
703 pkey_iffkey = gen_iffkey("iffkey");
704 if (pkey_iffkey == NULL) {
705 snprintf(filename, sizeof(filename), "ntpkey_iffkey_%s",
707 pkey_iffkey = readkey(filename, passwd1, &fstamp, NULL);
708 if (pkey_iffkey != NULL) {
709 followlink(filename, sizeof(filename));
710 fprintf(stderr, "Using IFF keys %s\n",
716 * Write the nonencrypted IFF client parameters to the stdout
717 * stream. The parameter file is the server key file with the
718 * private key obscured.
720 if (pkey_iffkey != NULL && HAVE_OPT(ID_KEY)) {
723 snprintf(filename, sizeof(filename),
724 "ntpkey_iffpar_%s.%u", groupname, fstamp);
725 fprintf(stderr, "Writing IFF parameters %s to stdout\n",
727 fprintf(stdout, "# %s\n# %s\n", filename,
729 /* XXX: This modifies the private key and should probably use a
730 * copy of it instead. */
731 dsa = EVP_PKEY_get0_DSA(pkey_iffkey);
732 DSA_set0_key(dsa, NULL, BN_dup(BN_value_one()));
733 pkey = EVP_PKEY_new();
734 EVP_PKEY_assign_DSA(pkey, dsa);
735 PEM_write_PKCS8PrivateKey(stdout, pkey, NULL, NULL, 0,
739 DSA_print_fp(stderr, dsa, 0);
743 * Write the encrypted IFF server keys to the stdout stream.
745 if (pkey_iffkey != NULL && passwd2 != NULL) {
748 snprintf(filename, sizeof(filename),
749 "ntpkey_iffkey_%s.%u", groupname, fstamp);
750 fprintf(stderr, "Writing IFF keys %s to stdout\n",
752 fprintf(stdout, "# %s\n# %s\n", filename,
754 dsa = EVP_PKEY_get0_DSA(pkey_iffkey);
755 pkey = EVP_PKEY_new();
756 EVP_PKEY_assign_DSA(pkey, dsa);
757 PEM_write_PKCS8PrivateKey(stdout, pkey, cipher, NULL, 0,
761 DSA_print_fp(stderr, dsa, 0);
765 * Create new encrypted MV trusted-authority keys file if
766 * requested; otherwise, look for existing keys file.
769 pkey_mvkey = gen_mvkey("mv", pkey_mvpar);
770 if (pkey_mvkey == NULL) {
771 snprintf(filename, sizeof(filename), "ntpkey_mvta_%s",
773 pkey_mvkey = readkey(filename, passwd1, &fstamp,
775 if (pkey_mvkey != NULL) {
776 followlink(filename, sizeof(filename));
777 fprintf(stderr, "Using MV keys %s\n",
783 * Write the nonencrypted MV client parameters to the stdout
784 * stream. For the moment, we always use the client parameters
785 * associated with client key 1.
787 if (pkey_mvkey != NULL && HAVE_OPT(ID_KEY)) {
788 snprintf(filename, sizeof(filename),
789 "ntpkey_mvpar_%s.%u", groupname, fstamp);
790 fprintf(stderr, "Writing MV parameters %s to stdout\n",
792 fprintf(stdout, "# %s\n# %s\n", filename,
794 pkey = pkey_mvpar[2];
795 PEM_write_PKCS8PrivateKey(stdout, pkey, NULL, NULL, 0,
799 DSA_print_fp(stderr, EVP_PKEY_get0_DSA(pkey), 0);
803 * Write the encrypted MV server keys to the stdout stream.
805 if (pkey_mvkey != NULL && passwd2 != NULL) {
806 snprintf(filename, sizeof(filename),
807 "ntpkey_mvkey_%s.%u", groupname, fstamp);
808 fprintf(stderr, "Writing MV keys %s to stdout\n",
810 fprintf(stdout, "# %s\n# %s\n", filename,
812 pkey = pkey_mvpar[1];
813 PEM_write_PKCS8PrivateKey(stdout, pkey, cipher, NULL, 0,
817 DSA_print_fp(stderr, EVP_PKEY_get0_DSA(pkey), 0);
821 * Decode the digest/signature scheme and create the
822 * certificate. Do this every time we run the program.
824 ectx = EVP_get_digestbyname(scheme);
827 "Invalid digest/signature combination %s\n",
831 x509(pkey_sign, ectx, grpkey, exten, certname);
838 * Generate semi-random MD5 keys compatible with NTPv3 and NTPv4. Also,
839 * if OpenSSL is around, generate random SHA1 keys compatible with
840 * symmetric key cryptography.
844 const char *id /* file name id */
847 u_char md5key[MD5SIZE + 1]; /* MD5 key */
851 u_char keystr[MD5SIZE];
852 u_char hexstr[2 * MD5SIZE + 1];
853 u_char hex[] = "0123456789abcdef";
856 str = fheader("MD5key", id, groupname);
857 for (i = 1; i <= MD5KEYS; i++) {
858 for (j = 0; j < MD5SIZE; j++) {
864 rc = ntp_crypto_random_buf(
865 &temp, sizeof(temp));
867 fprintf(stderr, "ntp_crypto_random_buf() failed.\n");
873 if (temp > 0x20 && temp < 0x7f)
879 fprintf(str, "%2d MD5 %s # MD5 key\n", i,
883 for (i = 1; i <= MD5KEYS; i++) {
884 RAND_bytes(keystr, 20);
885 for (j = 0; j < MD5SIZE; j++) {
886 hexstr[2 * j] = hex[keystr[j] >> 4];
887 hexstr[2 * j + 1] = hex[keystr[j] & 0xf];
889 hexstr[2 * MD5SIZE] = '\0';
890 fprintf(str, "%2d SHA1 %s # SHA1 key\n", i + MD5KEYS,
901 * readkey - load cryptographic parameters and keys
903 * This routine loads a PEM-encoded file of given name and password and
904 * extracts the filestamp from the file name. It returns a pointer to
905 * the first key if valid, NULL if not.
907 EVP_PKEY * /* public/private key pair */
909 char *cp, /* file name */
910 char *passwd, /* password */
911 u_int *estamp, /* file stamp */
912 EVP_PKEY **evpars /* parameter list pointer */
915 FILE *str; /* file handle */
916 EVP_PKEY *pkey = NULL; /* public/private key */
917 u_int gstamp; /* filestamp */
918 char linkname[MAXFILENAME]; /* filestamp buffer) */
926 str = fopen(cp, "r");
931 * Read the filestamp, which is contained in the first line.
933 if ((ptr = fgets(linkname, MAXFILENAME, str)) == NULL) {
934 fprintf(stderr, "Empty key file %s\n", cp);
938 if ((ptr = strrchr(ptr, '.')) == NULL) {
939 fprintf(stderr, "No filestamp found in %s\n", cp);
943 if (sscanf(++ptr, "%u", &gstamp) != 1) {
944 fprintf(stderr, "Invalid filestamp found in %s\n", cp);
950 * Read and decrypt PEM-encoded private keys. The first one
951 * found is returned. If others are expected, add them to the
954 for (i = 0; i <= MVMAX - 1;) {
955 parkey = PEM_read_PrivateKey(str, NULL, NULL, passwd);
956 if (evpars != NULL) {
957 evpars[i++] = parkey;
966 if (EVP_PKEY_base_id(parkey) == EVP_PKEY_DSA)
967 DSA_print_fp(stderr, EVP_PKEY_get0_DSA(parkey),
969 else if (EVP_PKEY_base_id(parkey) == EVP_PKEY_RSA)
970 RSA_print_fp(stderr, EVP_PKEY_get0_RSA(parkey),
976 fprintf(stderr, "Corrupt file %s or wrong key %s\n%s\n",
977 cp, passwd, ERR_error_string(ERR_get_error(),
987 * Generate RSA public/private key pair
989 EVP_PKEY * /* public/private key pair */
991 const char *id /* file name id */
994 EVP_PKEY *pkey; /* private key */
995 RSA *rsa; /* RSA parameters and key pair */
998 fprintf(stderr, "Generating RSA keys (%d bits)...\n", modulus);
999 rsa = genRsaKeyPair(modulus, _UC("RSA"));
1000 fprintf(stderr, "\n");
1002 fprintf(stderr, "RSA generate keys fails\n%s\n",
1003 ERR_error_string(ERR_get_error(), NULL));
1008 * For signature encryption it is not necessary that the RSA
1009 * parameters be strictly groomed and once in a while the
1010 * modulus turns out to be non-prime. Just for grins, we check
1013 if (!RSA_check_key(rsa)) {
1014 fprintf(stderr, "Invalid RSA key\n%s\n",
1015 ERR_error_string(ERR_get_error(), NULL));
1021 * Write the RSA parameters and keys as a RSA private key
1024 if (strcmp(id, "sign") == 0)
1025 str = fheader("RSAsign", id, hostname);
1027 str = fheader("RSAhost", id, hostname);
1028 pkey = EVP_PKEY_new();
1029 EVP_PKEY_assign_RSA(pkey, rsa);
1030 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1034 RSA_print_fp(stderr, rsa, 0);
1040 * Generate DSA public/private key pair
1042 EVP_PKEY * /* public/private key pair */
1044 const char *id /* file name id */
1047 EVP_PKEY *pkey; /* private key */
1048 DSA *dsa; /* DSA parameters */
1052 * Generate DSA parameters.
1055 "Generating DSA parameters (%d bits)...\n", modulus);
1056 dsa = genDsaParams(modulus, _UC("DSA"));
1057 fprintf(stderr, "\n");
1059 fprintf(stderr, "DSA generate parameters fails\n%s\n",
1060 ERR_error_string(ERR_get_error(), NULL));
1065 * Generate DSA keys.
1067 fprintf(stderr, "Generating DSA keys (%d bits)...\n", modulus);
1068 if (!DSA_generate_key(dsa)) {
1069 fprintf(stderr, "DSA generate keys fails\n%s\n",
1070 ERR_error_string(ERR_get_error(), NULL));
1076 * Write the DSA parameters and keys as a DSA private key
1079 str = fheader("DSAsign", id, hostname);
1080 pkey = EVP_PKEY_new();
1081 EVP_PKEY_assign_DSA(pkey, dsa);
1082 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1086 DSA_print_fp(stderr, dsa, 0);
1092 ***********************************************************************
1094 * The following routines implement the Schnorr (IFF) identity scheme *
1096 ***********************************************************************
1098 * The Schnorr (IFF) identity scheme is intended for use when
1099 * certificates are generated by some other trusted certificate
1100 * authority and the certificate cannot be used to convey public
1101 * parameters. There are two kinds of files: encrypted server files that
1102 * contain private and public values and nonencrypted client files that
1103 * contain only public values. New generations of server files must be
1104 * securely transmitted to all servers of the group; client files can be
1105 * distributed by any means. The scheme is self contained and
1106 * independent of new generations of host keys, sign keys and
1109 * The IFF values hide in a DSA cuckoo structure which uses the same
1110 * parameters. The values are used by an identity scheme based on DSA
1111 * cryptography and described in Stimson p. 285. The p is a 512-bit
1112 * prime, g a generator of Zp* and q a 160-bit prime that divides p - 1
1113 * and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA rolls a
1114 * private random group key b (0 < b < q) and public key v = g^b, then
1115 * sends (p, q, g, b) to the servers and (p, q, g, v) to the clients.
1116 * Alice challenges Bob to confirm identity using the protocol described
1121 * The scheme goes like this. Both Alice and Bob have the public primes
1122 * p, q and generator g. The TA gives private key b to Bob and public
1125 * Alice rolls new random challenge r (o < r < q) and sends to Bob in
1126 * the IFF request message. Bob rolls new random k (0 < k < q), then
1127 * computes y = k + b r mod q and x = g^k mod p and sends (y, hash(x))
1128 * to Alice in the response message. Besides making the response
1129 * shorter, the hash makes it effectivey impossible for an intruder to
1130 * solve for b by observing a number of these messages.
1132 * Alice receives the response and computes g^y v^r mod p. After a bit
1133 * of algebra, this simplifies to g^k. If the hash of this result
1134 * matches hash(x), Alice knows that Bob has the group key b. The signed
1135 * response binds this knowledge to Bob's private key and the public key
1136 * previously received in his certificate.
1139 * Generate Schnorr (IFF) keys.
1141 EVP_PKEY * /* DSA cuckoo nest */
1143 const char *id /* file name id */
1146 EVP_PKEY *pkey; /* private key */
1147 DSA *dsa; /* DSA parameters */
1148 BN_CTX *ctx; /* BN working space */
1149 BIGNUM *b, *r, *k, *u, *v, *w; /* BN temp */
1152 const BIGNUM *p, *q, *g;
1153 BIGNUM *pub_key, *priv_key;
1156 * Generate DSA parameters for use as IFF parameters.
1158 fprintf(stderr, "Generating IFF keys (%d bits)...\n",
1160 dsa = genDsaParams(modulus2, _UC("IFF"));
1161 fprintf(stderr, "\n");
1163 fprintf(stderr, "DSA generate parameters fails\n%s\n",
1164 ERR_error_string(ERR_get_error(), NULL));
1167 DSA_get0_pqg(dsa, &p, &q, &g);
1170 * Generate the private and public keys. The DSA parameters and
1171 * private key are distributed to the servers, while all except
1172 * the private key are distributed to the clients.
1174 b = BN_new(); r = BN_new(); k = BN_new();
1175 u = BN_new(); v = BN_new(); w = BN_new(); ctx = BN_CTX_new();
1176 BN_rand(b, BN_num_bits(q), -1, 0); /* a */
1177 BN_mod(b, b, q, ctx);
1179 BN_mod_exp(v, g, v, p, ctx); /* g^(q - b) mod p */
1180 BN_mod_exp(u, g, b, p, ctx); /* g^b mod p */
1181 BN_mod_mul(u, u, v, p, ctx);
1182 temp = BN_is_one(u);
1184 "Confirm g^(q - b) g^b = 1 mod p: %s\n", temp == 1 ?
1187 BN_free(b); BN_free(r); BN_free(k);
1188 BN_free(u); BN_free(v); BN_free(w); BN_CTX_free(ctx);
1191 pub_key = BN_dup(v);
1192 priv_key = BN_dup(b);
1193 DSA_set0_key(dsa, pub_key, priv_key);
1196 * Here is a trial round of the protocol. First, Alice rolls
1197 * random nonce r mod q and sends it to Bob. She needs only
1198 * q from parameters.
1200 BN_rand(r, BN_num_bits(q), -1, 0); /* r */
1201 BN_mod(r, r, q, ctx);
1204 * Bob rolls random nonce k mod q, computes y = k + b r mod q
1205 * and x = g^k mod p, then sends (y, x) to Alice. He needs
1206 * p, q and b from parameters and r from Alice.
1208 BN_rand(k, BN_num_bits(q), -1, 0); /* k, 0 < k < q */
1209 BN_mod(k, k, q, ctx);
1210 BN_mod_mul(v, priv_key, r, q, ctx); /* b r mod q */
1212 BN_mod(v, v, q, ctx); /* y = k + b r mod q */
1213 BN_mod_exp(u, g, k, p, ctx); /* x = g^k mod p */
1216 * Alice verifies x = g^y v^r to confirm that Bob has group key
1217 * b. She needs p, q, g from parameters, (y, x) from Bob and the
1218 * original r. We omit the detail here thatt only the hash of y
1221 BN_mod_exp(v, g, v, p, ctx); /* g^y mod p */
1222 BN_mod_exp(w, pub_key, r, p, ctx); /* v^r */
1223 BN_mod_mul(v, w, v, p, ctx); /* product mod p */
1224 temp = BN_cmp(u, v);
1226 "Confirm g^k = g^(k + b r) g^(q - b) r: %s\n", temp ==
1228 BN_free(b); BN_free(r); BN_free(k);
1229 BN_free(u); BN_free(v); BN_free(w); BN_CTX_free(ctx);
1236 * Write the IFF keys as an encrypted DSA private key encoded in
1247 str = fheader("IFFkey", id, groupname);
1248 pkey = EVP_PKEY_new();
1249 EVP_PKEY_assign_DSA(pkey, dsa);
1250 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1254 DSA_print_fp(stderr, dsa, 0);
1260 ***********************************************************************
1262 * The following routines implement the Guillou-Quisquater (GQ) *
1265 ***********************************************************************
1267 * The Guillou-Quisquater (GQ) identity scheme is intended for use when
1268 * the certificate can be used to convey public parameters. The scheme
1269 * uses a X509v3 certificate extension field do convey the public key of
1270 * a private key known only to servers. There are two kinds of files:
1271 * encrypted server files that contain private and public values and
1272 * nonencrypted client files that contain only public values. New
1273 * generations of server files must be securely transmitted to all
1274 * servers of the group; client files can be distributed by any means.
1275 * The scheme is self contained and independent of new generations of
1276 * host keys and sign keys. The scheme is self contained and independent
1277 * of new generations of host keys and sign keys.
1279 * The GQ parameters hide in a RSA cuckoo structure which uses the same
1280 * parameters. The values are used by an identity scheme based on RSA
1281 * cryptography and described in Stimson p. 300 (with errors). The 512-
1282 * bit public modulus is n = p q, where p and q are secret large primes.
1283 * The TA rolls private random group key b as RSA exponent. These values
1284 * are known to all group members.
1286 * When rolling new certificates, a server recomputes the private and
1287 * public keys. The private key u is a random roll, while the public key
1288 * is the inverse obscured by the group key v = (u^-1)^b. These values
1289 * replace the private and public keys normally generated by the RSA
1290 * scheme. Alice challenges Bob to confirm identity using the protocol
1295 * The scheme goes like this. Both Alice and Bob have the same modulus n
1296 * and some random b as the group key. These values are computed and
1297 * distributed in advance via secret means, although only the group key
1298 * b is truly secret. Each has a private random private key u and public
1299 * key (u^-1)^b, although not necessarily the same ones. Bob and Alice
1300 * can regenerate the key pair from time to time without affecting
1301 * operations. The public key is conveyed on the certificate in an
1302 * extension field; the private key is never revealed.
1304 * Alice rolls new random challenge r and sends to Bob in the GQ
1305 * request message. Bob rolls new random k, then computes y = k u^r mod
1306 * n and x = k^b mod n and sends (y, hash(x)) to Alice in the response
1307 * message. Besides making the response shorter, the hash makes it
1308 * effectivey impossible for an intruder to solve for b by observing
1309 * a number of these messages.
1311 * Alice receives the response and computes y^b v^r mod n. After a bit
1312 * of algebra, this simplifies to k^b. If the hash of this result
1313 * matches hash(x), Alice knows that Bob has the group key b. The signed
1314 * response binds this knowledge to Bob's private key and the public key
1315 * previously received in his certificate.
1318 * Generate Guillou-Quisquater (GQ) parameters file.
1320 EVP_PKEY * /* RSA cuckoo nest */
1322 const char *id /* file name id */
1325 EVP_PKEY *pkey; /* private key */
1326 RSA *rsa; /* RSA parameters */
1327 BN_CTX *ctx; /* BN working space */
1328 BIGNUM *u, *v, *g, *k, *r, *y; /* BN temps */
1335 * Generate RSA parameters for use as GQ parameters.
1338 "Generating GQ parameters (%d bits)...\n",
1340 rsa = genRsaKeyPair(modulus2, _UC("GQ"));
1341 fprintf(stderr, "\n");
1343 fprintf(stderr, "RSA generate keys fails\n%s\n",
1344 ERR_error_string(ERR_get_error(), NULL));
1347 RSA_get0_key(rsa, &n, NULL, NULL);
1348 u = BN_new(); v = BN_new(); g = BN_new();
1349 k = BN_new(); r = BN_new(); y = BN_new();
1353 * Generate the group key b, which is saved in the e member of
1354 * the RSA structure. The group key is transmitted to each group
1355 * member encrypted by the member private key.
1358 BN_rand(b, BN_num_bits(n), -1, 0); /* b */
1359 BN_mod(b, b, n, ctx);
1362 * When generating his certificate, Bob rolls random private key
1363 * u, then computes inverse v = u^-1.
1365 BN_rand(u, BN_num_bits(n), -1, 0); /* u */
1366 BN_mod(u, u, n, ctx);
1367 BN_mod_inverse(v, u, n, ctx); /* u^-1 mod n */
1368 BN_mod_mul(k, v, u, n, ctx);
1371 * Bob computes public key v = (u^-1)^b, which is saved in an
1372 * extension field on his certificate. We check that u^b v =
1375 BN_mod_exp(v, v, b, n, ctx);
1376 BN_mod_exp(g, u, b, n, ctx); /* u^b */
1377 BN_mod_mul(g, g, v, n, ctx); /* u^b (u^-1)^b */
1378 temp = BN_is_one(g);
1380 "Confirm u^b (u^-1)^b = 1 mod n: %s\n", temp ? "yes" :
1383 BN_free(u); BN_free(v);
1384 BN_free(g); BN_free(k); BN_free(r); BN_free(y);
1389 /* setting 'u' and 'v' into a RSA object takes over ownership.
1390 * Since we use these values again, we have to pass in dupes,
1391 * or we'll corrupt the program!
1393 RSA_set0_factors(rsa, BN_dup(u), BN_dup(v));
1396 * Here is a trial run of the protocol. First, Alice rolls
1397 * random nonce r mod n and sends it to Bob. She needs only n
1400 BN_rand(r, BN_num_bits(n), -1, 0); /* r */
1401 BN_mod(r, r, n, ctx);
1404 * Bob rolls random nonce k mod n, computes y = k u^r mod n and
1405 * g = k^b mod n, then sends (y, g) to Alice. He needs n, u, b
1406 * from parameters and r from Alice.
1408 BN_rand(k, BN_num_bits(n), -1, 0); /* k */
1409 BN_mod(k, k, n, ctx);
1410 BN_mod_exp(y, u, r, n, ctx); /* u^r mod n */
1411 BN_mod_mul(y, k, y, n, ctx); /* y = k u^r mod n */
1412 BN_mod_exp(g, k, b, n, ctx); /* g = k^b mod n */
1415 * Alice verifies g = v^r y^b mod n to confirm that Bob has
1416 * private key u. She needs n, g from parameters, public key v =
1417 * (u^-1)^b from the certificate, (y, g) from Bob and the
1418 * original r. We omit the detaul here that only the hash of g
1421 BN_mod_exp(v, v, r, n, ctx); /* v^r mod n */
1422 BN_mod_exp(y, y, b, n, ctx); /* y^b mod n */
1423 BN_mod_mul(y, v, y, n, ctx); /* v^r y^b mod n */
1424 temp = BN_cmp(y, g);
1425 fprintf(stderr, "Confirm g^k = v^r y^b mod n: %s\n", temp == 0 ?
1427 BN_CTX_free(ctx); BN_free(u); BN_free(v);
1428 BN_free(g); BN_free(k); BN_free(r); BN_free(y);
1435 * Write the GQ parameter file as an encrypted RSA private key
1442 * q public key (u^-1)^b
1447 RSA_set0_key(rsa, NULL, b, BN_dup(BN_value_one()));
1448 RSA_set0_crt_params(rsa, BN_dup(BN_value_one()), BN_dup(BN_value_one()),
1449 BN_dup(BN_value_one()));
1450 str = fheader("GQkey", id, groupname);
1451 pkey = EVP_PKEY_new();
1452 EVP_PKEY_assign_RSA(pkey, rsa);
1453 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1457 RSA_print_fp(stderr, rsa, 0);
1463 ***********************************************************************
1465 * The following routines implement the Mu-Varadharajan (MV) identity *
1468 ***********************************************************************
1470 * The Mu-Varadharajan (MV) cryptosystem was originally intended when
1471 * servers broadcast messages to clients, but clients never send
1472 * messages to servers. There is one encryption key for the server and a
1473 * separate decryption key for each client. It operated something like a
1474 * pay-per-view satellite broadcasting system where the session key is
1475 * encrypted by the broadcaster and the decryption keys are held in a
1476 * tamperproof set-top box.
1478 * The MV parameters and private encryption key hide in a DSA cuckoo
1479 * structure which uses the same parameters, but generated in a
1480 * different way. The values are used in an encryption scheme similar to
1481 * El Gamal cryptography and a polynomial formed from the expansion of
1482 * product terms (x - x[j]), as described in Mu, Y., and V.
1483 * Varadharajan: Robust and Secure Broadcasting, Proc. Indocrypt 2001,
1484 * 223-231. The paper has significant errors and serious omissions.
1486 * Let q be the product of n distinct primes s1[j] (j = 1...n), where
1487 * each s1[j] has m significant bits. Let p be a prime p = 2 * q + 1, so
1488 * that q and each s1[j] divide p - 1 and p has M = n * m + 1
1489 * significant bits. Let g be a generator of Zp; that is, gcd(g, p - 1)
1490 * = 1 and g^q = 1 mod p. We do modular arithmetic over Zq and then
1491 * project into Zp* as exponents of g. Sometimes we have to compute an
1492 * inverse b^-1 of random b in Zq, but for that purpose we require
1493 * gcd(b, q) = 1. We expect M to be in the 500-bit range and n
1494 * relatively small, like 30. These are the parameters of the scheme and
1495 * they are expensive to compute.
1497 * We set up an instance of the scheme as follows. A set of random
1498 * values x[j] mod q (j = 1...n), are generated as the zeros of a
1499 * polynomial of order n. The product terms (x - x[j]) are expanded to
1500 * form coefficients a[i] mod q (i = 0...n) in powers of x. These are
1501 * used as exponents of the generator g mod p to generate the private
1502 * encryption key A. The pair (gbar, ghat) of public server keys and the
1503 * pairs (xbar[j], xhat[j]) (j = 1...n) of private client keys are used
1504 * to construct the decryption keys. The devil is in the details.
1506 * This routine generates a private server encryption file including the
1507 * private encryption key E and partial decryption keys gbar and ghat.
1508 * It then generates public client decryption files including the public
1509 * keys xbar[j] and xhat[j] for each client j. The partial decryption
1510 * files are used to compute the inverse of E. These values are suitably
1511 * blinded so secrets are not revealed.
1513 * The distinguishing characteristic of this scheme is the capability to
1514 * revoke keys. Included in the calculation of E, gbar and ghat is the
1515 * product s = prod(s1[j]) (j = 1...n) above. If the factor s1[j] is
1516 * subsequently removed from the product and E, gbar and ghat
1517 * recomputed, the jth client will no longer be able to compute E^-1 and
1518 * thus unable to decrypt the messageblock.
1522 * The scheme goes like this. Bob has the server values (p, E, q,
1523 * gbar, ghat) and Alice has the client values (p, xbar, xhat).
1525 * Alice rolls new random nonce r mod p and sends to Bob in the MV
1526 * request message. Bob rolls random nonce k mod q, encrypts y = r E^k
1527 * mod p and sends (y, gbar^k, ghat^k) to Alice.
1529 * Alice receives the response and computes the inverse (E^k)^-1 from
1530 * the partial decryption keys gbar^k, ghat^k, xbar and xhat. She then
1531 * decrypts y and verifies it matches the original r. The signed
1532 * response binds this knowledge to Bob's private key and the public key
1533 * previously received in his certificate.
1535 EVP_PKEY * /* DSA cuckoo nest */
1537 const char *id, /* file name id */
1538 EVP_PKEY **evpars /* parameter list pointer */
1541 EVP_PKEY *pkey, *pkey1; /* private keys */
1542 DSA *dsa, *dsa2, *sdsa; /* DSA parameters */
1543 BN_CTX *ctx; /* BN working space */
1544 BIGNUM *a[MVMAX]; /* polynomial coefficient vector */
1545 BIGNUM *gs[MVMAX]; /* public key vector */
1546 BIGNUM *s1[MVMAX]; /* private enabling keys */
1547 BIGNUM *x[MVMAX]; /* polynomial zeros vector */
1548 BIGNUM *xbar[MVMAX], *xhat[MVMAX]; /* private keys vector */
1549 BIGNUM *b; /* group key */
1550 BIGNUM *b1; /* inverse group key */
1551 BIGNUM *s; /* enabling key */
1552 BIGNUM *biga; /* master encryption key */
1553 BIGNUM *bige; /* session encryption key */
1554 BIGNUM *gbar, *ghat; /* public key */
1555 BIGNUM *u, *v, *w; /* BN scratch */
1556 BIGNUM *p, *q, *g, *priv_key, *pub_key;
1562 * Generate MV parameters.
1564 * The object is to generate a multiplicative group Zp* modulo a
1565 * prime p and a subset Zq mod q, where q is the product of n
1566 * distinct primes s1[j] (j = 1...n) and q divides p - 1. We
1567 * first generate n m-bit primes, where the product n m is in
1568 * the order of 512 bits. One or more of these may have to be
1569 * replaced later. As a practical matter, it is tough to find
1570 * more than 31 distinct primes for 512 bits or 61 primes for
1571 * 1024 bits. The latter can take several hundred iterations
1572 * and several minutes on a Sun Blade 1000.
1576 "Generating MV parameters for %d keys (%d bits)...\n", n,
1578 ctx = BN_CTX_new(); u = BN_new(); v = BN_new(); w = BN_new();
1579 b = BN_new(); b1 = BN_new();
1581 p = BN_new(); q = BN_new(); g = BN_new();
1582 priv_key = BN_new(); pub_key = BN_new();
1584 for (j = 1; j <= n; j++) {
1587 BN_generate_prime_ex(s1[j], modulus2 / n, 0,
1589 for (i = 1; i < j; i++) {
1590 if (BN_cmp(s1[i], s1[j]) == 0)
1598 fprintf(stderr, "Birthday keys regenerated %d\n", temp);
1601 * Compute the modulus q as the product of the primes. Compute
1602 * the modulus p as 2 * q + 1 and test p for primality. If p
1603 * is composite, replace one of the primes with a new distinct
1604 * one and try again. Note that q will hardly be a secret since
1605 * we have to reveal p to servers, but not clients. However,
1606 * factoring q to find the primes should be adequately hard, as
1607 * this is the same problem considered hard in RSA. Question: is
1608 * it as hard to find n small prime factors totalling n bits as
1609 * it is to find two large prime factors totalling n bits?
1610 * Remember, the bad guy doesn't know n.
1615 for (j = 1; j <= n; j++)
1616 BN_mul(q, q, s1[j], ctx);
1620 if (BN_is_prime_ex(p, BN_prime_checks, ctx, NULL))
1626 BN_generate_prime_ex(u, modulus2 / n, 0,
1628 for (i = 1; i <= n; i++) {
1629 if (BN_cmp(u, s1[i]) == 0)
1637 fprintf(stderr, "Defective keys regenerated %d\n", temp);
1640 * Compute the generator g using a random roll such that
1641 * gcd(g, p - 1) = 1 and g^q = 1. This is a generator of p, not
1642 * q. This may take several iterations.
1647 BN_rand(g, BN_num_bits(p) - 1, 0, 0);
1648 BN_mod(g, g, p, ctx);
1649 BN_gcd(u, g, v, ctx);
1653 BN_mod_exp(u, g, q, p, ctx);
1658 DSA_set0_pqg(dsa, p, q, g);
1661 * Setup is now complete. Roll random polynomial roots x[j]
1662 * (j = 1...n) for all j. While it may not be strictly
1663 * necessary, Make sure each root has no factors in common with
1667 "Generating polynomial coefficients for %d roots (%d bits)\n",
1669 for (j = 1; j <= n; j++) {
1673 BN_rand(x[j], BN_num_bits(q), 0, 0);
1674 BN_mod(x[j], x[j], q, ctx);
1675 BN_gcd(u, x[j], q, ctx);
1682 * Generate polynomial coefficients a[i] (i = 0...n) from the
1683 * expansion of root products (x - x[j]) mod q for all j. The
1684 * method is a present from Charlie Boncelet.
1686 for (i = 0; i <= n; i++) {
1690 for (j = 1; j <= n; j++) {
1692 for (i = 0; i < j; i++) {
1694 BN_mod_mul(v, a[i], x[j], q, ctx);
1698 BN_mod(a[i], u, q, ctx);
1703 * Generate gs[i] = g^a[i] mod p for all i and the generator g.
1705 for (i = 0; i <= n; i++) {
1707 BN_mod_exp(gs[i], g, a[i], p, ctx);
1711 * Verify prod(gs[i]^(a[i] x[j]^i)) = 1 for all i, j. Note the
1712 * a[i] x[j]^i exponent is computed mod q, but the gs[i] is
1713 * computed mod p. also note the expression given in the paper
1717 for (j = 1; j <= n; j++) {
1719 for (i = 0; i <= n; i++) {
1721 BN_mod_exp(v, x[j], v, q, ctx);
1722 BN_mod_mul(v, v, a[i], q, ctx);
1723 BN_mod_exp(v, g, v, p, ctx);
1724 BN_mod_mul(u, u, v, p, ctx);
1730 "Confirm prod(gs[i]^(x[j]^i)) = 1 for all i, j: %s\n", temp ?
1737 * Make private encryption key A. Keep it around for awhile,
1738 * since it is expensive to compute.
1743 for (j = 1; j <= n; j++) {
1744 for (i = 0; i < n; i++) {
1746 BN_mod_exp(v, x[j], v, q, ctx);
1747 BN_mod_exp(v, gs[i], v, p, ctx);
1748 BN_mod_mul(biga, biga, v, p, ctx);
1753 * Roll private random group key b mod q (0 < b < q), where
1754 * gcd(b, q) = 1 to guarantee b^-1 exists, then compute b^-1
1755 * mod q. If b is changed, the client keys must be recomputed.
1758 BN_rand(b, BN_num_bits(q), 0, 0);
1759 BN_mod(b, b, q, ctx);
1760 BN_gcd(u, b, q, ctx);
1764 BN_mod_inverse(b1, b, q, ctx);
1767 * Make private client keys (xbar[j], xhat[j]) for all j. Note
1768 * that the keys for the jth client do not s1[j] or the product
1769 * s1[j]) (j = 1...n) which is q by construction.
1771 * Compute the factor w such that w s1[j] = s1[j] for all j. The
1772 * easy way to do this is to compute (q + s1[j]) / s1[j].
1773 * Exercise for the student: prove the remainder is always zero.
1775 for (j = 1; j <= n; j++) {
1776 xbar[j] = BN_new(); xhat[j] = BN_new();
1778 BN_add(w, q, s1[j]);
1779 BN_div(w, u, w, s1[j], ctx);
1782 for (i = 1; i <= n; i++) {
1786 BN_mod_exp(u, x[i], v, q, ctx);
1787 BN_add(xbar[j], xbar[j], u);
1789 BN_mod_mul(xbar[j], xbar[j], b1, q, ctx);
1790 BN_mod_exp(xhat[j], x[j], v, q, ctx);
1791 BN_mod_mul(xhat[j], xhat[j], w, q, ctx);
1795 * We revoke client j by dividing q by s1[j]. The quotient
1796 * becomes the enabling key s. Note we always have to revoke
1797 * one key; otherwise, the plaintext and cryptotext would be
1798 * identical. For the present there are no provisions to revoke
1799 * additional keys, so we sail on with only token revocations.
1803 BN_div(s, u, s, s1[n], ctx);
1806 * For each combination of clients to be revoked, make private
1807 * encryption key E = A^s and partial decryption keys gbar = g^s
1808 * and ghat = g^(s b), all mod p. The servers use these keys to
1809 * compute the session encryption key and partial decryption
1810 * keys. These values must be regenerated if the enabling key is
1813 bige = BN_new(); gbar = BN_new(); ghat = BN_new();
1814 BN_mod_exp(bige, biga, s, p, ctx);
1815 BN_mod_exp(gbar, g, s, p, ctx);
1816 BN_mod_mul(v, s, b, q, ctx);
1817 BN_mod_exp(ghat, g, v, p, ctx);
1820 * Notes: We produce the key media in three steps. The first
1821 * step is to generate the system parameters p, q, g, b, A and
1822 * the enabling keys s1[j]. Associated with each s1[j] are
1823 * parameters xbar[j] and xhat[j]. All of these parameters are
1824 * retained in a data structure protecteted by the trusted-agent
1825 * password. The p, xbar[j] and xhat[j] paremeters are
1826 * distributed to the j clients. When the client keys are to be
1827 * activated, the enabled keys are multipied together to form
1828 * the master enabling key s. This and the other parameters are
1829 * used to compute the server encryption key E and the partial
1830 * decryption keys gbar and ghat.
1832 * In the identity exchange the client rolls random r and sends
1833 * it to the server. The server rolls random k, which is used
1834 * only once, then computes the session key E^k and partial
1835 * decryption keys gbar^k and ghat^k. The server sends the
1836 * encrypted r along with gbar^k and ghat^k to the client. The
1837 * client completes the decryption and verifies it matches r.
1840 * Write the MV trusted-agent parameters and keys as a DSA
1841 * private key encoded in PEM.
1848 * (remaining values are not used)
1851 str = fheader("MVta", "mvta", groupname);
1852 fprintf(stderr, "Generating MV trusted-authority keys\n");
1853 BN_copy(priv_key, biga);
1854 BN_copy(pub_key, b);
1855 DSA_set0_key(dsa, pub_key, priv_key);
1856 pkey = EVP_PKEY_new();
1857 EVP_PKEY_assign_DSA(pkey, dsa);
1858 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1862 DSA_print_fp(stderr, dsa, 0);
1865 * Append the MV server parameters and keys as a DSA key encoded
1869 * q modulus q (used only when generating k)
1873 * (remaining values are not used)
1875 fprintf(stderr, "Generating MV server keys\n");
1877 DSA_set0_pqg(dsa2, BN_dup(p), BN_dup(q), BN_dup(bige));
1878 DSA_set0_key(dsa2, BN_dup(ghat), BN_dup(gbar));
1879 pkey1 = EVP_PKEY_new();
1880 EVP_PKEY_assign_DSA(pkey1, dsa2);
1881 PEM_write_PKCS8PrivateKey(str, pkey1, cipher, NULL, 0, NULL,
1883 evpars[i++] = pkey1;
1885 DSA_print_fp(stderr, dsa2, 0);
1888 * Append the MV client parameters for each client j as DSA keys
1892 * priv_key xbar[j] mod q
1893 * pub_key xhat[j] mod q
1894 * (remaining values are not used)
1896 fprintf(stderr, "Generating %d MV client keys\n", n);
1897 for (j = 1; j <= n; j++) {
1899 DSA_set0_pqg(sdsa, BN_dup(p), BN_dup(BN_value_one()),
1900 BN_dup(BN_value_one()));
1901 DSA_set0_key(sdsa, BN_dup(xhat[j]), BN_dup(xbar[j]));
1902 pkey1 = EVP_PKEY_new();
1903 EVP_PKEY_set1_DSA(pkey1, sdsa);
1904 PEM_write_PKCS8PrivateKey(str, pkey1, cipher, NULL, 0,
1906 evpars[i++] = pkey1;
1908 DSA_print_fp(stderr, sdsa, 0);
1911 * The product (gbar^k)^xbar[j] (ghat^k)^xhat[j] and E
1912 * are inverses of each other. We check that the product
1913 * is one for each client except the ones that have been
1916 BN_mod_exp(v, gbar, xhat[j], p, ctx);
1917 BN_mod_exp(u, ghat, xbar[j], p, ctx);
1918 BN_mod_mul(u, u, v, p, ctx);
1919 BN_mod_mul(u, u, bige, p, ctx);
1920 if (!BN_is_one(u)) {
1921 fprintf(stderr, "Revoke key %d\n", j);
1929 * Free the countries.
1931 for (i = 0; i <= n; i++) {
1932 BN_free(a[i]); BN_free(gs[i]);
1934 for (j = 1; j <= n; j++) {
1935 BN_free(x[j]); BN_free(xbar[j]); BN_free(xhat[j]);
1943 * Generate X509v3 certificate.
1945 * The certificate consists of the version number, serial number,
1946 * validity interval, issuer name, subject name and public key. For a
1947 * self-signed certificate, the issuer name is the same as the subject
1948 * name and these items are signed using the subject private key. The
1949 * validity interval extends from the current time to the same time one
1950 * year hence. For NTP purposes, it is convenient to use the NTP seconds
1951 * of the current time as the serial number.
1955 EVP_PKEY *pkey, /* signing key */
1956 const EVP_MD *md, /* signature/digest scheme */
1957 char *gqpub, /* identity extension (hex string) */
1958 const char *exten, /* private cert extension */
1959 char *name /* subject/issuer name */
1962 X509 *cert; /* X509 certificate */
1963 X509_NAME *subj; /* distinguished (common) name */
1964 X509_EXTENSION *ex; /* X509v3 extension */
1965 FILE *str; /* file handle */
1966 ASN1_INTEGER *serial; /* serial number */
1967 const char *id; /* digest/signature scheme name */
1968 char pathbuf[MAXFILENAME + 1];
1971 * Generate X509 self-signed certificate.
1973 * Set the certificate serial to the NTP seconds for grins. Set
1974 * the version to 3. Set the initial validity to the current
1975 * time and the finalvalidity one year hence.
1977 id = OBJ_nid2sn(EVP_MD_pkey_type(md));
1978 fprintf(stderr, "Generating new certificate %s %s\n", name, id);
1980 X509_set_version(cert, 2L);
1981 serial = ASN1_INTEGER_new();
1982 ASN1_INTEGER_set(serial, (long)epoch + JAN_1970);
1983 X509_set_serialNumber(cert, serial);
1984 ASN1_INTEGER_free(serial);
1985 X509_time_adj(X509_getm_notBefore(cert), 0L, &epoch);
1986 X509_time_adj(X509_getm_notAfter(cert), lifetime * SECSPERDAY, &epoch);
1987 subj = X509_get_subject_name(cert);
1988 X509_NAME_add_entry_by_txt(subj, "commonName", MBSTRING_ASC,
1989 (u_char *)name, -1, -1, 0);
1990 subj = X509_get_issuer_name(cert);
1991 X509_NAME_add_entry_by_txt(subj, "commonName", MBSTRING_ASC,
1992 (u_char *)name, -1, -1, 0);
1993 if (!X509_set_pubkey(cert, pkey)) {
1994 fprintf(stderr, "Assign certificate signing key fails\n%s\n",
1995 ERR_error_string(ERR_get_error(), NULL));
2001 * Add X509v3 extensions if present. These represent the minimum
2002 * set defined in RFC3280 less the certificate_policy extension,
2003 * which is seriously obfuscated in OpenSSL.
2006 * The basic_constraints extension CA:TRUE allows servers to
2007 * sign client certficitates.
2009 fprintf(stderr, "%s: %s\n", LN_basic_constraints,
2011 ex = X509V3_EXT_conf_nid(NULL, NULL, NID_basic_constraints,
2012 _UC(BASIC_CONSTRAINTS));
2013 if (!X509_add_ext(cert, ex, -1)) {
2014 fprintf(stderr, "Add extension field fails\n%s\n",
2015 ERR_error_string(ERR_get_error(), NULL));
2018 X509_EXTENSION_free(ex);
2021 * The key_usage extension designates the purposes the key can
2024 fprintf(stderr, "%s: %s\n", LN_key_usage, KEY_USAGE);
2025 ex = X509V3_EXT_conf_nid(NULL, NULL, NID_key_usage, _UC(KEY_USAGE));
2026 if (!X509_add_ext(cert, ex, -1)) {
2027 fprintf(stderr, "Add extension field fails\n%s\n",
2028 ERR_error_string(ERR_get_error(), NULL));
2031 X509_EXTENSION_free(ex);
2033 * The subject_key_identifier is used for the GQ public key.
2034 * This should not be controversial.
2036 if (gqpub != NULL) {
2037 fprintf(stderr, "%s\n", LN_subject_key_identifier);
2038 ex = X509V3_EXT_conf_nid(NULL, NULL,
2039 NID_subject_key_identifier, gqpub);
2040 if (!X509_add_ext(cert, ex, -1)) {
2042 "Add extension field fails\n%s\n",
2043 ERR_error_string(ERR_get_error(), NULL));
2046 X509_EXTENSION_free(ex);
2050 * The extended key usage extension is used for special purpose
2051 * here. The semantics probably do not conform to the designer's
2052 * intent and will likely change in future.
2054 * "trustRoot" designates a root authority
2055 * "private" designates a private certificate
2057 if (exten != NULL) {
2058 fprintf(stderr, "%s: %s\n", LN_ext_key_usage, exten);
2059 ex = X509V3_EXT_conf_nid(NULL, NULL,
2060 NID_ext_key_usage, _UC(exten));
2061 if (!X509_add_ext(cert, ex, -1)) {
2063 "Add extension field fails\n%s\n",
2064 ERR_error_string(ERR_get_error(), NULL));
2067 X509_EXTENSION_free(ex);
2073 X509_sign(cert, pkey, md);
2074 if (X509_verify(cert, pkey) <= 0) {
2075 fprintf(stderr, "Verify %s certificate fails\n%s\n", id,
2076 ERR_error_string(ERR_get_error(), NULL));
2082 * Write the certificate encoded in PEM.
2084 snprintf(pathbuf, sizeof(pathbuf), "%scert", id);
2085 str = fheader(pathbuf, "cert", hostname);
2086 PEM_write_X509(str, cert);
2089 X509_print_fp(stderr, cert);
2094 #if 0 /* asn2ntp is used only with commercial certificates */
2096 * asn2ntp - convert ASN1_TIME time structure to NTP time
2100 ASN1_TIME *asn1time /* pointer to ASN1_TIME structure */
2103 char *v; /* pointer to ASN1_TIME string */
2104 struct tm tm; /* time decode structure time */
2107 * Extract time string YYMMDDHHMMSSZ from ASN.1 time structure.
2108 * Note that the YY, MM, DD fields start with one, the HH, MM,
2109 * SS fiels start with zero and the Z character should be 'Z'
2110 * for UTC. Also note that years less than 50 map to years
2111 * greater than 100. Dontcha love ASN.1?
2113 if (asn1time->length > 13)
2115 v = (char *)asn1time->data;
2116 tm.tm_year = (v[0] - '0') * 10 + v[1] - '0';
2117 if (tm.tm_year < 50)
2119 tm.tm_mon = (v[2] - '0') * 10 + v[3] - '0' - 1;
2120 tm.tm_mday = (v[4] - '0') * 10 + v[5] - '0';
2121 tm.tm_hour = (v[6] - '0') * 10 + v[7] - '0';
2122 tm.tm_min = (v[8] - '0') * 10 + v[9] - '0';
2123 tm.tm_sec = (v[10] - '0') * 10 + v[11] - '0';
2127 return (mktime(&tm) + JAN_1970);
2138 void *chr /* arg 3 */
2144 fprintf(stderr, "%s %d %d %lu\r", (char *)chr, n1, n2,
2149 fprintf(stderr, "%s\t\t%d %d %lu\r", (char *)chr, n1,
2154 fprintf(stderr, "%s\t\t\t\t%d %d %lu\r", (char *)chr,
2159 fprintf(stderr, "%s\t\t\t\t\t\t%d %d %lu\r",
2160 (char *)chr, n1, n2, d3);
2169 EVP_PKEY * /* public/private key pair */
2171 const char *type, /* key type (RSA or DSA) */
2172 const char *id /* file name id */
2177 if (strcmp(type, "RSA") == 0)
2178 return (gen_rsa(id));
2180 else if (strcmp(type, "DSA") == 0)
2181 return (gen_dsa(id));
2183 fprintf(stderr, "Invalid %s key type %s\n", id, type);
2193 RSA * rsa = RSA_new();
2194 BN_GENCB * gcb = BN_GENCB_new();
2195 BIGNUM * bne = BN_new();
2198 BN_GENCB_set_old(gcb, cb, what);
2200 BN_set_word(bne, 65537);
2201 if (!(rsa && gcb && bne && RSA_generate_key_ex(
2202 rsa, bits, bne, gcb)))
2219 DSA * dsa = DSA_new();
2220 BN_GENCB * gcb = BN_GENCB_new();
2224 BN_GENCB_set_old(gcb, cb, what);
2225 RAND_bytes(seed, sizeof(seed));
2226 if (!(dsa && gcb && DSA_generate_parameters_ex(
2227 dsa, bits, seed, sizeof(seed), NULL, NULL, gcb)))
2236 #endif /* AUTOKEY */
2240 * Generate file header and link
2244 const char *file, /* file name id */
2245 const char *ulink, /* linkname */
2246 const char *owner /* owner name */
2249 FILE *str; /* file handle */
2250 char linkname[MAXFILENAME]; /* link name */
2256 snprintf(filename, sizeof(filename), "ntpkey_%s_%s.%u", file,
2259 orig_umask = umask( S_IWGRP | S_IRWXO );
2260 str = fopen(filename, "w");
2261 (void) umask(orig_umask);
2263 str = fopen(filename, "w");
2269 if (strcmp(ulink, "md5") == 0) {
2270 strcpy(linkname,"ntp.keys");
2272 snprintf(linkname, sizeof(linkname), "ntpkey_%s_%s", ulink,
2275 (void)remove(linkname); /* The symlink() line below matters */
2276 temp = symlink(filename, linkname);
2279 fprintf(stderr, "Generating new %s file and link\n", ulink);
2280 fprintf(stderr, "%s->%s\n", linkname, filename);
2281 fprintf(str, "# %s\n# %s\n", filename, ctime(&epoch));