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/bn.h"
102 #include "openssl/evp.h"
103 #include "openssl/err.h"
104 #include "openssl/rand.h"
105 #include "openssl/pem.h"
106 #include "openssl/x509v3.h"
107 #include <openssl/objects.h>
109 #include <ssl_applink.c>
111 #define _UC(str) ((char *)(intptr_t)(str))
115 #define MD5KEYS 10 /* number of keys generated of each type */
116 #define MD5SIZE 20 /* maximum key size */
118 #define PLEN 512 /* default prime modulus size (bits) */
119 #define ILEN 256 /* default identity modulus size (bits) */
120 #define MVMAX 100 /* max MV parameters */
123 * Strings used in X509v3 extension fields
125 #define KEY_USAGE "digitalSignature,keyCertSign"
126 #define BASIC_CONSTRAINTS "critical,CA:TRUE"
127 #define EXT_KEY_PRIVATE "private"
128 #define EXT_KEY_TRUST "trustRoot"
134 FILE *fheader (const char *, const char *, const char *);
135 int gen_md5 (const char *);
136 void followlink (char *, size_t);
138 EVP_PKEY *gen_rsa (const char *);
139 EVP_PKEY *gen_dsa (const char *);
140 EVP_PKEY *gen_iffkey (const char *);
141 EVP_PKEY *gen_gqkey (const char *);
142 EVP_PKEY *gen_mvkey (const char *, EVP_PKEY **);
143 void gen_mvserv (char *, EVP_PKEY **);
144 int x509 (EVP_PKEY *, const EVP_MD *, char *, const char *,
146 void cb (int, int, void *);
147 EVP_PKEY *genkey (const char *, const char *);
148 EVP_PKEY *readkey (char *, char *, u_int *, EVP_PKEY **);
149 void writekey (char *, char *, u_int *, EVP_PKEY **);
150 u_long asn2ntp (ASN1_TIME *);
156 extern char *optarg; /* command line argument */
157 char const *progname;
158 u_int lifetime = DAYSPERYEAR; /* certificate lifetime (days) */
159 int nkeys; /* MV keys */
160 time_t epoch; /* Unix epoch (seconds) since 1970 */
161 u_int fstamp; /* NTP filestamp */
162 char hostbuf[MAXHOSTNAME + 1];
163 char *hostname = NULL; /* host, used in cert filenames */
164 char *groupname = NULL; /* group name */
165 char certnamebuf[2 * sizeof(hostbuf)];
166 char *certname = NULL; /* certificate subject/issuer name */
167 char *passwd1 = NULL; /* input private key password */
168 char *passwd2 = NULL; /* output private key password */
169 char filename[MAXFILENAME + 1]; /* file name */
171 u_int modulus = PLEN; /* prime modulus size (bits) */
172 u_int modulus2 = ILEN; /* identity modulus size (bits) */
173 long d0, d1, d2, d3; /* callback counters */
174 const EVP_CIPHER * cipher = NULL;
178 BOOL init_randfile();
181 * Don't try to follow symbolic links on Windows. Assume link == file.
190 return (int)strlen(file); /* assume no overflow possible */
194 * Don't try to create symbolic links on Windows, that is supported on
195 * Vista and later only. Instead, if CreateHardLink is available (XP
196 * and later), hardlink the linkname to the original filename. On
197 * earlier systems, user must rename file to match expected link for
198 * ntpd to find it. To allow building a ntp-keygen.exe which loads on
199 * Windows pre-XP, runtime link to CreateHardLinkA().
207 typedef BOOL (WINAPI *PCREATEHARDLINKA)(
208 __in LPCSTR lpFileName,
209 __in LPCSTR lpExistingFileName,
210 __reserved LPSECURITY_ATTRIBUTES lpSA
212 static PCREATEHARDLINKA pCreateHardLinkA;
221 hDll = LoadLibrary("kernel32");
222 pfn = GetProcAddress(hDll, "CreateHardLinkA");
223 pCreateHardLinkA = (PCREATEHARDLINKA)pfn;
226 if (NULL == pCreateHardLinkA) {
231 link_created = (*pCreateHardLinkA)(linkname, filename, NULL);
236 saved_errno = GetLastError(); /* yes we play loose */
237 mfprintf(stderr, "Create hard link %s to %s failed: %m\n",
245 WORD wVersionRequested;
247 wVersionRequested = MAKEWORD(2,0);
248 if (WSAStartup(wVersionRequested, &wsaData))
250 fprintf(stderr, "No useable winsock.dll\n");
254 #endif /* SYS_WINNT */
258 * followlink() - replace filename with its target if symlink.
260 * Some readlink() implementations do not null-terminate the result.
272 len = readlink(fname, fname, (int)bufsiz);
277 if (len > (int)bufsiz - 1)
278 len = (int)bufsiz - 1;
288 int argc, /* command line options */
292 struct timeval tv; /* initialization vector */
293 int md5key = 0; /* generate MD5 keys */
294 int optct; /* option count */
296 X509 *cert = NULL; /* X509 certificate */
297 X509_EXTENSION *ext; /* X509v3 extension */
298 EVP_PKEY *pkey_host = NULL; /* host key */
299 EVP_PKEY *pkey_sign = NULL; /* sign key */
300 EVP_PKEY *pkey_iffkey = NULL; /* IFF sever keys */
301 EVP_PKEY *pkey_gqkey = NULL; /* GQ server keys */
302 EVP_PKEY *pkey_mvkey = NULL; /* MV trusted agen keys */
303 EVP_PKEY *pkey_mvpar[MVMAX]; /* MV cleient keys */
304 int hostkey = 0; /* generate RSA keys */
305 int iffkey = 0; /* generate IFF keys */
306 int gqkey = 0; /* generate GQ keys */
307 int mvkey = 0; /* update MV keys */
308 int mvpar = 0; /* generate MV parameters */
309 char *sign = NULL; /* sign key */
310 EVP_PKEY *pkey = NULL; /* temp key */
311 const EVP_MD *ectx; /* EVP digest */
312 char pathbuf[MAXFILENAME + 1];
313 const char *scheme = NULL; /* digest/signature scheme */
314 const char *ciphername = NULL; /* to encrypt priv. key */
315 const char *exten = NULL; /* private extension */
316 char *grpkey = NULL; /* identity extension */
317 int nid; /* X509 digest/signature scheme */
318 FILE *fstr = NULL; /* file handle */
319 char groupbuf[MAXHOSTNAME + 1];
329 /* Initialize before OpenSSL checks */
331 if (!init_randfile())
332 fprintf(stderr, "Unable to initialize .rnd file\n");
340 ntp_crypto_srandom();
343 * Process options, initialize host name and timestamp.
344 * gethostname() won't null-terminate if hostname is exactly the
345 * length provided for the buffer.
347 gethostname(hostbuf, sizeof(hostbuf) - 1);
348 hostbuf[COUNTOF(hostbuf) - 1] = '\0';
353 GETTIMEOFDAY(&tv, NULL);
355 fstamp = (u_int)(epoch + JAN_1970);
357 optct = ntpOptionProcess(&ntp_keygenOptions, argc, argv);
358 argc -= optct; // Just in case we care later.
359 argv += optct; // Just in case we care later.
362 if (SSLeay() == SSLEAY_VERSION_NUMBER)
363 fprintf(stderr, "Using OpenSSL version %s\n",
364 SSLeay_version(SSLEAY_VERSION));
366 fprintf(stderr, "Built against OpenSSL %s, using version %s\n",
367 OPENSSL_VERSION_TEXT, SSLeay_version(SSLEAY_VERSION));
370 debug = OPT_VALUE_SET_DEBUG_LEVEL;
372 if (HAVE_OPT( MD5KEY ))
375 if (HAVE_OPT( PASSWORD ))
376 passwd1 = estrdup(OPT_ARG( PASSWORD ));
378 if (HAVE_OPT( EXPORT_PASSWD ))
379 passwd2 = estrdup(OPT_ARG( EXPORT_PASSWD ));
381 if (HAVE_OPT( HOST_KEY ))
384 if (HAVE_OPT( SIGN_KEY ))
385 sign = estrdup(OPT_ARG( SIGN_KEY ));
387 if (HAVE_OPT( GQ_PARAMS ))
390 if (HAVE_OPT( IFFKEY ))
393 if (HAVE_OPT( MV_PARAMS )) {
395 nkeys = OPT_VALUE_MV_PARAMS;
397 if (HAVE_OPT( MV_KEYS )) {
399 nkeys = OPT_VALUE_MV_KEYS;
402 if (HAVE_OPT( IMBITS ))
403 modulus2 = OPT_VALUE_IMBITS;
405 if (HAVE_OPT( MODULUS ))
406 modulus = OPT_VALUE_MODULUS;
408 if (HAVE_OPT( CERTIFICATE ))
409 scheme = OPT_ARG( CERTIFICATE );
411 if (HAVE_OPT( CIPHER ))
412 ciphername = OPT_ARG( CIPHER );
414 if (HAVE_OPT( SUBJECT_NAME ))
415 hostname = estrdup(OPT_ARG( SUBJECT_NAME ));
417 if (HAVE_OPT( IDENT ))
418 groupname = estrdup(OPT_ARG( IDENT ));
420 if (HAVE_OPT( LIFETIME ))
421 lifetime = OPT_VALUE_LIFETIME;
423 if (HAVE_OPT( PVT_CERT ))
424 exten = EXT_KEY_PRIVATE;
426 if (HAVE_OPT( TRUSTED_CERT ))
427 exten = EXT_KEY_TRUST;
430 * Remove the group name from the hostname variable used
431 * in host and sign certificate file names.
433 if (hostname != hostbuf)
434 ptr = strchr(hostname, '@');
439 groupname = estrdup(ptr + 1);
440 /* -s @group is equivalent to -i group, host unch. */
446 * Derive host certificate issuer/subject names from host name
447 * and optional group. If no groupname is provided, the issuer
448 * and subject is the hostname with no '@group', and the
449 * groupname variable is pointed to hostname for use in IFF, GQ,
450 * and MV parameters file names.
452 if (groupname == hostbuf) {
455 snprintf(certnamebuf, sizeof(certnamebuf), "%s@%s",
456 hostname, groupname);
457 certname = certnamebuf;
461 * Seed random number generator and grow weeds.
463 ERR_load_crypto_strings();
464 OpenSSL_add_all_algorithms();
465 if (!RAND_status()) {
466 if (RAND_file_name(pathbuf, sizeof(pathbuf)) == NULL) {
467 fprintf(stderr, "RAND_file_name %s\n",
468 ERR_error_string(ERR_get_error(), NULL));
471 temp = RAND_load_file(pathbuf, -1);
474 "RAND_load_file %s not found or empty\n",
479 "Random seed file %s %u bytes\n", pathbuf, temp);
480 RAND_add(&epoch, sizeof(epoch), 4.0);
485 * Create new unencrypted MD5 keys file if requested. If this
486 * option is selected, ignore all other options.
495 * Load previous certificate if available.
497 snprintf(filename, sizeof(filename), "ntpkey_cert_%s", hostname);
498 if ((fstr = fopen(filename, "r")) != NULL) {
499 cert = PEM_read_X509(fstr, NULL, NULL, NULL);
505 * Extract subject name.
507 X509_NAME_oneline(X509_get_subject_name(cert), groupbuf,
511 * Extract digest/signature scheme.
513 if (scheme == NULL) {
514 nid = OBJ_obj2nid(cert->cert_info->
515 signature->algorithm);
516 scheme = OBJ_nid2sn(nid);
520 * If a key_usage extension field is present, determine
521 * whether this is a trusted or private certificate.
524 ptr = strstr(groupbuf, "CN=");
525 cnt = X509_get_ext_count(cert);
526 for (i = 0; i < cnt; i++) {
527 ext = X509_get_ext(cert, i);
528 if (OBJ_obj2nid(ext->object) ==
530 bp = BIO_new(BIO_s_mem());
531 X509V3_EXT_print(bp, ext, 0, 0);
532 BIO_gets(bp, pathbuf,
537 exten = EXT_KEY_TRUST;
538 else if (strcmp(pathbuf,
540 exten = EXT_KEY_PRIVATE;
541 certname = estrdup(ptr + 3);
548 if (ciphername == NULL)
549 ciphername = "des-ede3-cbc";
550 cipher = EVP_get_cipherbyname(ciphername);
551 if (cipher == NULL) {
552 fprintf(stderr, "Unknown cipher %s\n", ciphername);
555 fprintf(stderr, "Using host %s group %s\n", hostname,
559 * Create a new encrypted RSA host key file if requested;
560 * otherwise, look for an existing host key file. If not found,
561 * create a new encrypted RSA host key file. If that fails, go
565 pkey_host = genkey("RSA", "host");
566 if (pkey_host == NULL) {
567 snprintf(filename, sizeof(filename), "ntpkey_host_%s", hostname);
568 pkey_host = readkey(filename, passwd1, &fstamp, NULL);
569 if (pkey_host != NULL) {
570 followlink(filename, sizeof(filename));
571 fprintf(stderr, "Using host key %s\n",
574 pkey_host = genkey("RSA", "host");
577 if (pkey_host == NULL) {
578 fprintf(stderr, "Generating host key fails\n");
583 * Create new encrypted RSA or DSA sign keys file if requested;
584 * otherwise, look for an existing sign key file. If not found,
585 * use the host key instead.
588 pkey_sign = genkey(sign, "sign");
589 if (pkey_sign == NULL) {
590 snprintf(filename, sizeof(filename), "ntpkey_sign_%s",
592 pkey_sign = readkey(filename, passwd1, &fstamp, NULL);
593 if (pkey_sign != NULL) {
594 followlink(filename, sizeof(filename));
595 fprintf(stderr, "Using sign key %s\n",
598 pkey_sign = pkey_host;
599 fprintf(stderr, "Using host key as sign key\n");
604 * Create new encrypted GQ server keys file if requested;
605 * otherwise, look for an exisiting file. If found, fetch the
606 * public key for the certificate.
609 pkey_gqkey = gen_gqkey("gqkey");
610 if (pkey_gqkey == NULL) {
611 snprintf(filename, sizeof(filename), "ntpkey_gqkey_%s",
613 pkey_gqkey = readkey(filename, passwd1, &fstamp, NULL);
614 if (pkey_gqkey != NULL) {
615 followlink(filename, sizeof(filename));
616 fprintf(stderr, "Using GQ parameters %s\n",
620 if (pkey_gqkey != NULL)
621 grpkey = BN_bn2hex(pkey_gqkey->pkey.rsa->q);
624 * Write the nonencrypted GQ client parameters to the stdout
625 * stream. The parameter file is the server key file with the
626 * private key obscured.
628 if (pkey_gqkey != NULL && HAVE_OPT(ID_KEY)) {
631 snprintf(filename, sizeof(filename),
632 "ntpkey_gqpar_%s.%u", groupname, fstamp);
633 fprintf(stderr, "Writing GQ parameters %s to stdout\n",
635 fprintf(stdout, "# %s\n# %s\n", filename,
637 rsa = pkey_gqkey->pkey.rsa;
638 BN_copy(rsa->p, BN_value_one());
639 BN_copy(rsa->q, BN_value_one());
640 pkey = EVP_PKEY_new();
641 EVP_PKEY_assign_RSA(pkey, rsa);
642 PEM_write_PKCS8PrivateKey(stdout, pkey, NULL, NULL, 0,
646 RSA_print_fp(stderr, rsa, 0);
650 * Write the encrypted GQ server keys to the stdout stream.
652 if (pkey_gqkey != NULL && passwd2 != NULL) {
655 snprintf(filename, sizeof(filename),
656 "ntpkey_gqkey_%s.%u", groupname, fstamp);
657 fprintf(stderr, "Writing GQ keys %s to stdout\n",
659 fprintf(stdout, "# %s\n# %s\n", filename,
661 rsa = pkey_gqkey->pkey.rsa;
662 pkey = EVP_PKEY_new();
663 EVP_PKEY_assign_RSA(pkey, rsa);
664 PEM_write_PKCS8PrivateKey(stdout, pkey, cipher, NULL, 0,
668 RSA_print_fp(stderr, rsa, 0);
672 * Create new encrypted IFF server keys file if requested;
673 * otherwise, look for existing file.
676 pkey_iffkey = gen_iffkey("iffkey");
677 if (pkey_iffkey == NULL) {
678 snprintf(filename, sizeof(filename), "ntpkey_iffkey_%s",
680 pkey_iffkey = readkey(filename, passwd1, &fstamp, NULL);
681 if (pkey_iffkey != NULL) {
682 followlink(filename, sizeof(filename));
683 fprintf(stderr, "Using IFF keys %s\n",
689 * Write the nonencrypted IFF client parameters to the stdout
690 * stream. The parameter file is the server key file with the
691 * private key obscured.
693 if (pkey_iffkey != NULL && HAVE_OPT(ID_KEY)) {
696 snprintf(filename, sizeof(filename),
697 "ntpkey_iffpar_%s.%u", groupname, fstamp);
698 fprintf(stderr, "Writing IFF parameters %s to stdout\n",
700 fprintf(stdout, "# %s\n# %s\n", filename,
702 dsa = pkey_iffkey->pkey.dsa;
703 BN_copy(dsa->priv_key, BN_value_one());
704 pkey = EVP_PKEY_new();
705 EVP_PKEY_assign_DSA(pkey, dsa);
706 PEM_write_PKCS8PrivateKey(stdout, pkey, NULL, NULL, 0,
710 DSA_print_fp(stderr, dsa, 0);
714 * Write the encrypted IFF server keys to the stdout stream.
716 if (pkey_iffkey != NULL && passwd2 != NULL) {
719 snprintf(filename, sizeof(filename),
720 "ntpkey_iffkey_%s.%u", groupname, fstamp);
721 fprintf(stderr, "Writing IFF keys %s to stdout\n",
723 fprintf(stdout, "# %s\n# %s\n", filename,
725 dsa = pkey_iffkey->pkey.dsa;
726 pkey = EVP_PKEY_new();
727 EVP_PKEY_assign_DSA(pkey, dsa);
728 PEM_write_PKCS8PrivateKey(stdout, pkey, cipher, NULL, 0,
732 DSA_print_fp(stderr, dsa, 0);
736 * Create new encrypted MV trusted-authority keys file if
737 * requested; otherwise, look for existing keys file.
740 pkey_mvkey = gen_mvkey("mv", pkey_mvpar);
741 if (pkey_mvkey == NULL) {
742 snprintf(filename, sizeof(filename), "ntpkey_mvta_%s",
744 pkey_mvkey = readkey(filename, passwd1, &fstamp,
746 if (pkey_mvkey != NULL) {
747 followlink(filename, sizeof(filename));
748 fprintf(stderr, "Using MV keys %s\n",
754 * Write the nonencrypted MV client parameters to the stdout
755 * stream. For the moment, we always use the client parameters
756 * associated with client key 1.
758 if (pkey_mvkey != NULL && HAVE_OPT(ID_KEY)) {
759 snprintf(filename, sizeof(filename),
760 "ntpkey_mvpar_%s.%u", groupname, fstamp);
761 fprintf(stderr, "Writing MV parameters %s to stdout\n",
763 fprintf(stdout, "# %s\n# %s\n", filename,
765 pkey = pkey_mvpar[2];
766 PEM_write_PKCS8PrivateKey(stdout, pkey, NULL, NULL, 0,
770 DSA_print_fp(stderr, pkey->pkey.dsa, 0);
774 * Write the encrypted MV server keys to the stdout stream.
776 if (pkey_mvkey != NULL && passwd2 != NULL) {
777 snprintf(filename, sizeof(filename),
778 "ntpkey_mvkey_%s.%u", groupname, fstamp);
779 fprintf(stderr, "Writing MV keys %s to stdout\n",
781 fprintf(stdout, "# %s\n# %s\n", filename,
783 pkey = pkey_mvpar[1];
784 PEM_write_PKCS8PrivateKey(stdout, pkey, cipher, NULL, 0,
788 DSA_print_fp(stderr, pkey->pkey.dsa, 0);
792 * Decode the digest/signature scheme and create the
793 * certificate. Do this every time we run the program.
795 ectx = EVP_get_digestbyname(scheme);
798 "Invalid digest/signature combination %s\n",
802 x509(pkey_sign, ectx, grpkey, exten, certname);
809 * Generate semi-random MD5 keys compatible with NTPv3 and NTPv4. Also,
810 * if OpenSSL is around, generate random SHA1 keys compatible with
811 * symmetric key cryptography.
815 const char *id /* file name id */
818 u_char md5key[MD5SIZE + 1]; /* MD5 key */
822 u_char keystr[MD5SIZE];
823 u_char hexstr[2 * MD5SIZE + 1];
824 u_char hex[] = "0123456789abcdef";
827 str = fheader("MD5key", id, groupname);
828 for (i = 1; i <= MD5KEYS; i++) {
829 for (j = 0; j < MD5SIZE; j++) {
835 rc = ntp_crypto_random_buf(
836 &temp, sizeof(temp));
838 fprintf(stderr, "ntp_crypto_random_buf() failed.\n");
844 if (temp > 0x20 && temp < 0x7f)
850 fprintf(str, "%2d MD5 %s # MD5 key\n", i,
854 for (i = 1; i <= MD5KEYS; i++) {
855 RAND_bytes(keystr, 20);
856 for (j = 0; j < MD5SIZE; j++) {
857 hexstr[2 * j] = hex[keystr[j] >> 4];
858 hexstr[2 * j + 1] = hex[keystr[j] & 0xf];
860 hexstr[2 * MD5SIZE] = '\0';
861 fprintf(str, "%2d SHA1 %s # SHA1 key\n", i + MD5KEYS,
872 * readkey - load cryptographic parameters and keys
874 * This routine loads a PEM-encoded file of given name and password and
875 * extracts the filestamp from the file name. It returns a pointer to
876 * the first key if valid, NULL if not.
878 EVP_PKEY * /* public/private key pair */
880 char *cp, /* file name */
881 char *passwd, /* password */
882 u_int *estamp, /* file stamp */
883 EVP_PKEY **evpars /* parameter list pointer */
886 FILE *str; /* file handle */
887 EVP_PKEY *pkey = NULL; /* public/private key */
888 u_int gstamp; /* filestamp */
889 char linkname[MAXFILENAME]; /* filestamp buffer) */
897 str = fopen(cp, "r");
902 * Read the filestamp, which is contained in the first line.
904 if ((ptr = fgets(linkname, MAXFILENAME, str)) == NULL) {
905 fprintf(stderr, "Empty key file %s\n", cp);
909 if ((ptr = strrchr(ptr, '.')) == NULL) {
910 fprintf(stderr, "No filestamp found in %s\n", cp);
914 if (sscanf(++ptr, "%u", &gstamp) != 1) {
915 fprintf(stderr, "Invalid filestamp found in %s\n", cp);
921 * Read and decrypt PEM-encoded private keys. The first one
922 * found is returned. If others are expected, add them to the
925 for (i = 0; i <= MVMAX - 1;) {
926 parkey = PEM_read_PrivateKey(str, NULL, NULL, passwd);
927 if (evpars != NULL) {
928 evpars[i++] = parkey;
937 if (parkey->type == EVP_PKEY_DSA)
938 DSA_print_fp(stderr, parkey->pkey.dsa,
940 else if (parkey->type == EVP_PKEY_RSA)
941 RSA_print_fp(stderr, parkey->pkey.rsa,
947 fprintf(stderr, "Corrupt file %s or wrong key %s\n%s\n",
948 cp, passwd, ERR_error_string(ERR_get_error(),
958 * Generate RSA public/private key pair
960 EVP_PKEY * /* public/private key pair */
962 const char *id /* file name id */
965 EVP_PKEY *pkey; /* private key */
966 RSA *rsa; /* RSA parameters and key pair */
969 fprintf(stderr, "Generating RSA keys (%d bits)...\n", modulus);
970 rsa = RSA_generate_key(modulus, 65537, cb, _UC("RSA"));
971 fprintf(stderr, "\n");
973 fprintf(stderr, "RSA generate keys fails\n%s\n",
974 ERR_error_string(ERR_get_error(), NULL));
979 * For signature encryption it is not necessary that the RSA
980 * parameters be strictly groomed and once in a while the
981 * modulus turns out to be non-prime. Just for grins, we check
984 if (!RSA_check_key(rsa)) {
985 fprintf(stderr, "Invalid RSA key\n%s\n",
986 ERR_error_string(ERR_get_error(), NULL));
992 * Write the RSA parameters and keys as a RSA private key
995 if (strcmp(id, "sign") == 0)
996 str = fheader("RSAsign", id, hostname);
998 str = fheader("RSAhost", id, hostname);
999 pkey = EVP_PKEY_new();
1000 EVP_PKEY_assign_RSA(pkey, rsa);
1001 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1005 RSA_print_fp(stderr, rsa, 0);
1011 * Generate DSA public/private key pair
1013 EVP_PKEY * /* public/private key pair */
1015 const char *id /* file name id */
1018 EVP_PKEY *pkey; /* private key */
1019 DSA *dsa; /* DSA parameters */
1020 u_char seed[20]; /* seed for parameters */
1024 * Generate DSA parameters.
1027 "Generating DSA parameters (%d bits)...\n", modulus);
1028 RAND_bytes(seed, sizeof(seed));
1029 dsa = DSA_generate_parameters(modulus, seed, sizeof(seed), NULL,
1030 NULL, cb, _UC("DSA"));
1031 fprintf(stderr, "\n");
1033 fprintf(stderr, "DSA generate parameters fails\n%s\n",
1034 ERR_error_string(ERR_get_error(), NULL));
1039 * Generate DSA keys.
1041 fprintf(stderr, "Generating DSA keys (%d bits)...\n", modulus);
1042 if (!DSA_generate_key(dsa)) {
1043 fprintf(stderr, "DSA generate keys fails\n%s\n",
1044 ERR_error_string(ERR_get_error(), NULL));
1050 * Write the DSA parameters and keys as a DSA private key
1053 str = fheader("DSAsign", id, hostname);
1054 pkey = EVP_PKEY_new();
1055 EVP_PKEY_assign_DSA(pkey, dsa);
1056 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1060 DSA_print_fp(stderr, dsa, 0);
1066 ***********************************************************************
1068 * The following routines implement the Schnorr (IFF) identity scheme *
1070 ***********************************************************************
1072 * The Schnorr (IFF) identity scheme is intended for use when
1073 * certificates are generated by some other trusted certificate
1074 * authority and the certificate cannot be used to convey public
1075 * parameters. There are two kinds of files: encrypted server files that
1076 * contain private and public values and nonencrypted client files that
1077 * contain only public values. New generations of server files must be
1078 * securely transmitted to all servers of the group; client files can be
1079 * distributed by any means. The scheme is self contained and
1080 * independent of new generations of host keys, sign keys and
1083 * The IFF values hide in a DSA cuckoo structure which uses the same
1084 * parameters. The values are used by an identity scheme based on DSA
1085 * cryptography and described in Stimson p. 285. The p is a 512-bit
1086 * prime, g a generator of Zp* and q a 160-bit prime that divides p - 1
1087 * and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA rolls a
1088 * private random group key b (0 < b < q) and public key v = g^b, then
1089 * sends (p, q, g, b) to the servers and (p, q, g, v) to the clients.
1090 * Alice challenges Bob to confirm identity using the protocol described
1095 * The scheme goes like this. Both Alice and Bob have the public primes
1096 * p, q and generator g. The TA gives private key b to Bob and public
1099 * Alice rolls new random challenge r (o < r < q) and sends to Bob in
1100 * the IFF request message. Bob rolls new random k (0 < k < q), then
1101 * computes y = k + b r mod q and x = g^k mod p and sends (y, hash(x))
1102 * to Alice in the response message. Besides making the response
1103 * shorter, the hash makes it effectivey impossible for an intruder to
1104 * solve for b by observing a number of these messages.
1106 * Alice receives the response and computes g^y v^r mod p. After a bit
1107 * of algebra, this simplifies to g^k. If the hash of this result
1108 * matches hash(x), Alice knows that Bob has the group key b. The signed
1109 * response binds this knowledge to Bob's private key and the public key
1110 * previously received in his certificate.
1113 * Generate Schnorr (IFF) keys.
1115 EVP_PKEY * /* DSA cuckoo nest */
1117 const char *id /* file name id */
1120 EVP_PKEY *pkey; /* private key */
1121 DSA *dsa; /* DSA parameters */
1122 u_char seed[20]; /* seed for parameters */
1123 BN_CTX *ctx; /* BN working space */
1124 BIGNUM *b, *r, *k, *u, *v, *w; /* BN temp */
1129 * Generate DSA parameters for use as IFF parameters.
1131 fprintf(stderr, "Generating IFF keys (%d bits)...\n",
1133 RAND_bytes(seed, sizeof(seed));
1134 dsa = DSA_generate_parameters(modulus2, seed, sizeof(seed), NULL,
1135 NULL, cb, _UC("IFF"));
1136 fprintf(stderr, "\n");
1138 fprintf(stderr, "DSA generate parameters fails\n%s\n",
1139 ERR_error_string(ERR_get_error(), NULL));
1144 * Generate the private and public keys. The DSA parameters and
1145 * private key are distributed to the servers, while all except
1146 * the private key are distributed to the clients.
1148 b = BN_new(); r = BN_new(); k = BN_new();
1149 u = BN_new(); v = BN_new(); w = BN_new(); ctx = BN_CTX_new();
1150 BN_rand(b, BN_num_bits(dsa->q), -1, 0); /* a */
1151 BN_mod(b, b, dsa->q, ctx);
1152 BN_sub(v, dsa->q, b);
1153 BN_mod_exp(v, dsa->g, v, dsa->p, ctx); /* g^(q - b) mod p */
1154 BN_mod_exp(u, dsa->g, b, dsa->p, ctx); /* g^b mod p */
1155 BN_mod_mul(u, u, v, dsa->p, ctx);
1156 temp = BN_is_one(u);
1158 "Confirm g^(q - b) g^b = 1 mod p: %s\n", temp == 1 ?
1161 BN_free(b); BN_free(r); BN_free(k);
1162 BN_free(u); BN_free(v); BN_free(w); BN_CTX_free(ctx);
1165 dsa->priv_key = BN_dup(b); /* private key */
1166 dsa->pub_key = BN_dup(v); /* public key */
1169 * Here is a trial round of the protocol. First, Alice rolls
1170 * random nonce r mod q and sends it to Bob. She needs only
1171 * q from parameters.
1173 BN_rand(r, BN_num_bits(dsa->q), -1, 0); /* r */
1174 BN_mod(r, r, dsa->q, ctx);
1177 * Bob rolls random nonce k mod q, computes y = k + b r mod q
1178 * and x = g^k mod p, then sends (y, x) to Alice. He needs
1179 * p, q and b from parameters and r from Alice.
1181 BN_rand(k, BN_num_bits(dsa->q), -1, 0); /* k, 0 < k < q */
1182 BN_mod(k, k, dsa->q, ctx);
1183 BN_mod_mul(v, dsa->priv_key, r, dsa->q, ctx); /* b r mod q */
1185 BN_mod(v, v, dsa->q, ctx); /* y = k + b r mod q */
1186 BN_mod_exp(u, dsa->g, k, dsa->p, ctx); /* x = g^k mod p */
1189 * Alice verifies x = g^y v^r to confirm that Bob has group key
1190 * b. She needs p, q, g from parameters, (y, x) from Bob and the
1191 * original r. We omit the detail here thatt only the hash of y
1194 BN_mod_exp(v, dsa->g, v, dsa->p, ctx); /* g^y mod p */
1195 BN_mod_exp(w, dsa->pub_key, r, dsa->p, ctx); /* v^r */
1196 BN_mod_mul(v, w, v, dsa->p, ctx); /* product mod p */
1197 temp = BN_cmp(u, v);
1199 "Confirm g^k = g^(k + b r) g^(q - b) r: %s\n", temp ==
1201 BN_free(b); BN_free(r); BN_free(k);
1202 BN_free(u); BN_free(v); BN_free(w); BN_CTX_free(ctx);
1209 * Write the IFF keys as an encrypted DSA private key encoded in
1220 str = fheader("IFFkey", id, groupname);
1221 pkey = EVP_PKEY_new();
1222 EVP_PKEY_assign_DSA(pkey, dsa);
1223 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1227 DSA_print_fp(stderr, dsa, 0);
1233 ***********************************************************************
1235 * The following routines implement the Guillou-Quisquater (GQ) *
1238 ***********************************************************************
1240 * The Guillou-Quisquater (GQ) identity scheme is intended for use when
1241 * the certificate can be used to convey public parameters. The scheme
1242 * uses a X509v3 certificate extension field do convey the public key of
1243 * a private key known only to servers. There are two kinds of files:
1244 * encrypted server files that contain private and public values and
1245 * nonencrypted client files that contain only public values. New
1246 * generations of server files must be securely transmitted to all
1247 * servers of the group; client files can be distributed by any means.
1248 * The scheme is self contained and independent of new generations of
1249 * host keys and sign keys. The scheme is self contained and independent
1250 * of new generations of host keys and sign keys.
1252 * The GQ parameters hide in a RSA cuckoo structure which uses the same
1253 * parameters. The values are used by an identity scheme based on RSA
1254 * cryptography and described in Stimson p. 300 (with errors). The 512-
1255 * bit public modulus is n = p q, where p and q are secret large primes.
1256 * The TA rolls private random group key b as RSA exponent. These values
1257 * are known to all group members.
1259 * When rolling new certificates, a server recomputes the private and
1260 * public keys. The private key u is a random roll, while the public key
1261 * is the inverse obscured by the group key v = (u^-1)^b. These values
1262 * replace the private and public keys normally generated by the RSA
1263 * scheme. Alice challenges Bob to confirm identity using the protocol
1268 * The scheme goes like this. Both Alice and Bob have the same modulus n
1269 * and some random b as the group key. These values are computed and
1270 * distributed in advance via secret means, although only the group key
1271 * b is truly secret. Each has a private random private key u and public
1272 * key (u^-1)^b, although not necessarily the same ones. Bob and Alice
1273 * can regenerate the key pair from time to time without affecting
1274 * operations. The public key is conveyed on the certificate in an
1275 * extension field; the private key is never revealed.
1277 * Alice rolls new random challenge r and sends to Bob in the GQ
1278 * request message. Bob rolls new random k, then computes y = k u^r mod
1279 * n and x = k^b mod n and sends (y, hash(x)) to Alice in the response
1280 * message. Besides making the response shorter, the hash makes it
1281 * effectivey impossible for an intruder to solve for b by observing
1282 * a number of these messages.
1284 * Alice receives the response and computes y^b v^r mod n. After a bit
1285 * of algebra, this simplifies to k^b. If the hash of this result
1286 * matches hash(x), Alice knows that Bob has the group key b. The signed
1287 * response binds this knowledge to Bob's private key and the public key
1288 * previously received in his certificate.
1291 * Generate Guillou-Quisquater (GQ) parameters file.
1293 EVP_PKEY * /* RSA cuckoo nest */
1295 const char *id /* file name id */
1298 EVP_PKEY *pkey; /* private key */
1299 RSA *rsa; /* RSA parameters */
1300 BN_CTX *ctx; /* BN working space */
1301 BIGNUM *u, *v, *g, *k, *r, *y; /* BN temps */
1306 * Generate RSA parameters for use as GQ parameters.
1309 "Generating GQ parameters (%d bits)...\n",
1311 rsa = RSA_generate_key(modulus2, 65537, cb, _UC("GQ"));
1312 fprintf(stderr, "\n");
1314 fprintf(stderr, "RSA generate keys fails\n%s\n",
1315 ERR_error_string(ERR_get_error(), NULL));
1318 u = BN_new(); v = BN_new(); g = BN_new();
1319 k = BN_new(); r = BN_new(); y = BN_new();
1322 * Generate the group key b, which is saved in the e member of
1323 * the RSA structure. The group key is transmitted to each group
1324 * member encrypted by the member private key.
1327 BN_rand(rsa->e, BN_num_bits(rsa->n), -1, 0); /* b */
1328 BN_mod(rsa->e, rsa->e, rsa->n, ctx);
1331 * When generating his certificate, Bob rolls random private key
1332 * u, then computes inverse v = u^-1.
1334 BN_rand(u, BN_num_bits(rsa->n), -1, 0); /* u */
1335 BN_mod(u, u, rsa->n, ctx);
1336 BN_mod_inverse(v, u, rsa->n, ctx); /* u^-1 mod n */
1337 BN_mod_mul(k, v, u, rsa->n, ctx);
1340 * Bob computes public key v = (u^-1)^b, which is saved in an
1341 * extension field on his certificate. We check that u^b v =
1344 BN_mod_exp(v, v, rsa->e, rsa->n, ctx);
1345 BN_mod_exp(g, u, rsa->e, rsa->n, ctx); /* u^b */
1346 BN_mod_mul(g, g, v, rsa->n, ctx); /* u^b (u^-1)^b */
1347 temp = BN_is_one(g);
1349 "Confirm u^b (u^-1)^b = 1 mod n: %s\n", temp ? "yes" :
1352 BN_free(u); BN_free(v);
1353 BN_free(g); BN_free(k); BN_free(r); BN_free(y);
1358 BN_copy(rsa->p, u); /* private key */
1359 BN_copy(rsa->q, v); /* public key */
1362 * Here is a trial run of the protocol. First, Alice rolls
1363 * random nonce r mod n and sends it to Bob. She needs only n
1366 BN_rand(r, BN_num_bits(rsa->n), -1, 0); /* r */
1367 BN_mod(r, r, rsa->n, ctx);
1370 * Bob rolls random nonce k mod n, computes y = k u^r mod n and
1371 * g = k^b mod n, then sends (y, g) to Alice. He needs n, u, b
1372 * from parameters and r from Alice.
1374 BN_rand(k, BN_num_bits(rsa->n), -1, 0); /* k */
1375 BN_mod(k, k, rsa->n, ctx);
1376 BN_mod_exp(y, rsa->p, r, rsa->n, ctx); /* u^r mod n */
1377 BN_mod_mul(y, k, y, rsa->n, ctx); /* y = k u^r mod n */
1378 BN_mod_exp(g, k, rsa->e, rsa->n, ctx); /* g = k^b mod n */
1381 * Alice verifies g = v^r y^b mod n to confirm that Bob has
1382 * private key u. She needs n, g from parameters, public key v =
1383 * (u^-1)^b from the certificate, (y, g) from Bob and the
1384 * original r. We omit the detaul here that only the hash of g
1387 BN_mod_exp(v, rsa->q, r, rsa->n, ctx); /* v^r mod n */
1388 BN_mod_exp(y, y, rsa->e, rsa->n, ctx); /* y^b mod n */
1389 BN_mod_mul(y, v, y, rsa->n, ctx); /* v^r y^b mod n */
1390 temp = BN_cmp(y, g);
1391 fprintf(stderr, "Confirm g^k = v^r y^b mod n: %s\n", temp == 0 ?
1393 BN_CTX_free(ctx); BN_free(u); BN_free(v);
1394 BN_free(g); BN_free(k); BN_free(r); BN_free(y);
1401 * Write the GQ parameter file as an encrypted RSA private key
1408 * q public key (u^-1)^b
1413 BN_copy(rsa->d, BN_value_one());
1414 BN_copy(rsa->dmp1, BN_value_one());
1415 BN_copy(rsa->dmq1, BN_value_one());
1416 BN_copy(rsa->iqmp, BN_value_one());
1417 str = fheader("GQkey", id, groupname);
1418 pkey = EVP_PKEY_new();
1419 EVP_PKEY_assign_RSA(pkey, rsa);
1420 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1424 RSA_print_fp(stderr, rsa, 0);
1430 ***********************************************************************
1432 * The following routines implement the Mu-Varadharajan (MV) identity *
1435 ***********************************************************************
1437 * The Mu-Varadharajan (MV) cryptosystem was originally intended when
1438 * servers broadcast messages to clients, but clients never send
1439 * messages to servers. There is one encryption key for the server and a
1440 * separate decryption key for each client. It operated something like a
1441 * pay-per-view satellite broadcasting system where the session key is
1442 * encrypted by the broadcaster and the decryption keys are held in a
1443 * tamperproof set-top box.
1445 * The MV parameters and private encryption key hide in a DSA cuckoo
1446 * structure which uses the same parameters, but generated in a
1447 * different way. The values are used in an encryption scheme similar to
1448 * El Gamal cryptography and a polynomial formed from the expansion of
1449 * product terms (x - x[j]), as described in Mu, Y., and V.
1450 * Varadharajan: Robust and Secure Broadcasting, Proc. Indocrypt 2001,
1451 * 223-231. The paper has significant errors and serious omissions.
1453 * Let q be the product of n distinct primes s1[j] (j = 1...n), where
1454 * each s1[j] has m significant bits. Let p be a prime p = 2 * q + 1, so
1455 * that q and each s1[j] divide p - 1 and p has M = n * m + 1
1456 * significant bits. Let g be a generator of Zp; that is, gcd(g, p - 1)
1457 * = 1 and g^q = 1 mod p. We do modular arithmetic over Zq and then
1458 * project into Zp* as exponents of g. Sometimes we have to compute an
1459 * inverse b^-1 of random b in Zq, but for that purpose we require
1460 * gcd(b, q) = 1. We expect M to be in the 500-bit range and n
1461 * relatively small, like 30. These are the parameters of the scheme and
1462 * they are expensive to compute.
1464 * We set up an instance of the scheme as follows. A set of random
1465 * values x[j] mod q (j = 1...n), are generated as the zeros of a
1466 * polynomial of order n. The product terms (x - x[j]) are expanded to
1467 * form coefficients a[i] mod q (i = 0...n) in powers of x. These are
1468 * used as exponents of the generator g mod p to generate the private
1469 * encryption key A. The pair (gbar, ghat) of public server keys and the
1470 * pairs (xbar[j], xhat[j]) (j = 1...n) of private client keys are used
1471 * to construct the decryption keys. The devil is in the details.
1473 * This routine generates a private server encryption file including the
1474 * private encryption key E and partial decryption keys gbar and ghat.
1475 * It then generates public client decryption files including the public
1476 * keys xbar[j] and xhat[j] for each client j. The partial decryption
1477 * files are used to compute the inverse of E. These values are suitably
1478 * blinded so secrets are not revealed.
1480 * The distinguishing characteristic of this scheme is the capability to
1481 * revoke keys. Included in the calculation of E, gbar and ghat is the
1482 * product s = prod(s1[j]) (j = 1...n) above. If the factor s1[j] is
1483 * subsequently removed from the product and E, gbar and ghat
1484 * recomputed, the jth client will no longer be able to compute E^-1 and
1485 * thus unable to decrypt the messageblock.
1489 * The scheme goes like this. Bob has the server values (p, E, q,
1490 * gbar, ghat) and Alice has the client values (p, xbar, xhat).
1492 * Alice rolls new random nonce r mod p and sends to Bob in the MV
1493 * request message. Bob rolls random nonce k mod q, encrypts y = r E^k
1494 * mod p and sends (y, gbar^k, ghat^k) to Alice.
1496 * Alice receives the response and computes the inverse (E^k)^-1 from
1497 * the partial decryption keys gbar^k, ghat^k, xbar and xhat. She then
1498 * decrypts y and verifies it matches the original r. The signed
1499 * response binds this knowledge to Bob's private key and the public key
1500 * previously received in his certificate.
1502 EVP_PKEY * /* DSA cuckoo nest */
1504 const char *id, /* file name id */
1505 EVP_PKEY **evpars /* parameter list pointer */
1508 EVP_PKEY *pkey, *pkey1; /* private keys */
1509 DSA *dsa, *dsa2, *sdsa; /* DSA parameters */
1510 BN_CTX *ctx; /* BN working space */
1511 BIGNUM *a[MVMAX]; /* polynomial coefficient vector */
1512 BIGNUM *g[MVMAX]; /* public key vector */
1513 BIGNUM *s1[MVMAX]; /* private enabling keys */
1514 BIGNUM *x[MVMAX]; /* polynomial zeros vector */
1515 BIGNUM *xbar[MVMAX], *xhat[MVMAX]; /* private keys vector */
1516 BIGNUM *b; /* group key */
1517 BIGNUM *b1; /* inverse group key */
1518 BIGNUM *s; /* enabling key */
1519 BIGNUM *biga; /* master encryption key */
1520 BIGNUM *bige; /* session encryption key */
1521 BIGNUM *gbar, *ghat; /* public key */
1522 BIGNUM *u, *v, *w; /* BN scratch */
1528 * Generate MV parameters.
1530 * The object is to generate a multiplicative group Zp* modulo a
1531 * prime p and a subset Zq mod q, where q is the product of n
1532 * distinct primes s1[j] (j = 1...n) and q divides p - 1. We
1533 * first generate n m-bit primes, where the product n m is in
1534 * the order of 512 bits. One or more of these may have to be
1535 * replaced later. As a practical matter, it is tough to find
1536 * more than 31 distinct primes for 512 bits or 61 primes for
1537 * 1024 bits. The latter can take several hundred iterations
1538 * and several minutes on a Sun Blade 1000.
1542 "Generating MV parameters for %d keys (%d bits)...\n", n,
1544 ctx = BN_CTX_new(); u = BN_new(); v = BN_new(); w = BN_new();
1545 b = BN_new(); b1 = BN_new();
1547 dsa->p = BN_new(); dsa->q = BN_new(); dsa->g = BN_new();
1548 dsa->priv_key = BN_new(); dsa->pub_key = BN_new();
1550 for (j = 1; j <= n; j++) {
1553 BN_generate_prime(s1[j], modulus2 / n, 0, NULL,
1555 for (i = 1; i < j; i++) {
1556 if (BN_cmp(s1[i], s1[j]) == 0)
1564 fprintf(stderr, "Birthday keys regenerated %d\n", temp);
1567 * Compute the modulus q as the product of the primes. Compute
1568 * the modulus p as 2 * q + 1 and test p for primality. If p
1569 * is composite, replace one of the primes with a new distinct
1570 * one and try again. Note that q will hardly be a secret since
1571 * we have to reveal p to servers, but not clients. However,
1572 * factoring q to find the primes should be adequately hard, as
1573 * this is the same problem considered hard in RSA. Question: is
1574 * it as hard to find n small prime factors totalling n bits as
1575 * it is to find two large prime factors totalling n bits?
1576 * Remember, the bad guy doesn't know n.
1581 for (j = 1; j <= n; j++)
1582 BN_mul(dsa->q, dsa->q, s1[j], ctx);
1583 BN_copy(dsa->p, dsa->q);
1584 BN_add(dsa->p, dsa->p, dsa->p);
1585 BN_add_word(dsa->p, 1);
1586 if (BN_is_prime(dsa->p, BN_prime_checks, NULL, ctx,
1593 BN_generate_prime(u, modulus2 / n, 0, 0, NULL,
1595 for (i = 1; i <= n; i++) {
1596 if (BN_cmp(u, s1[i]) == 0)
1604 fprintf(stderr, "Defective keys regenerated %d\n", temp);
1607 * Compute the generator g using a random roll such that
1608 * gcd(g, p - 1) = 1 and g^q = 1. This is a generator of p, not
1609 * q. This may take several iterations.
1614 BN_rand(dsa->g, BN_num_bits(dsa->p) - 1, 0, 0);
1615 BN_mod(dsa->g, dsa->g, dsa->p, ctx);
1616 BN_gcd(u, dsa->g, v, ctx);
1620 BN_mod_exp(u, dsa->g, dsa->q, dsa->p, ctx);
1626 * Setup is now complete. Roll random polynomial roots x[j]
1627 * (j = 1...n) for all j. While it may not be strictly
1628 * necessary, Make sure each root has no factors in common with
1632 "Generating polynomial coefficients for %d roots (%d bits)\n",
1633 n, BN_num_bits(dsa->q));
1634 for (j = 1; j <= n; j++) {
1638 BN_rand(x[j], BN_num_bits(dsa->q), 0, 0);
1639 BN_mod(x[j], x[j], dsa->q, ctx);
1640 BN_gcd(u, x[j], dsa->q, ctx);
1647 * Generate polynomial coefficients a[i] (i = 0...n) from the
1648 * expansion of root products (x - x[j]) mod q for all j. The
1649 * method is a present from Charlie Boncelet.
1651 for (i = 0; i <= n; i++) {
1655 for (j = 1; j <= n; j++) {
1657 for (i = 0; i < j; i++) {
1659 BN_mod_mul(v, a[i], x[j], dsa->q, ctx);
1663 BN_mod(a[i], u, dsa->q, ctx);
1668 * Generate g[i] = g^a[i] mod p for all i and the generator g.
1670 for (i = 0; i <= n; i++) {
1672 BN_mod_exp(g[i], dsa->g, a[i], dsa->p, ctx);
1676 * Verify prod(g[i]^(a[i] x[j]^i)) = 1 for all i, j. Note the
1677 * a[i] x[j]^i exponent is computed mod q, but the g[i] is
1678 * computed mod p. also note the expression given in the paper
1682 for (j = 1; j <= n; j++) {
1684 for (i = 0; i <= n; i++) {
1686 BN_mod_exp(v, x[j], v, dsa->q, ctx);
1687 BN_mod_mul(v, v, a[i], dsa->q, ctx);
1688 BN_mod_exp(v, dsa->g, v, dsa->p, ctx);
1689 BN_mod_mul(u, u, v, dsa->p, ctx);
1695 "Confirm prod(g[i]^(x[j]^i)) = 1 for all i, j: %s\n", temp ?
1702 * Make private encryption key A. Keep it around for awhile,
1703 * since it is expensive to compute.
1708 for (j = 1; j <= n; j++) {
1709 for (i = 0; i < n; i++) {
1711 BN_mod_exp(v, x[j], v, dsa->q, ctx);
1712 BN_mod_exp(v, g[i], v, dsa->p, ctx);
1713 BN_mod_mul(biga, biga, v, dsa->p, ctx);
1718 * Roll private random group key b mod q (0 < b < q), where
1719 * gcd(b, q) = 1 to guarantee b^-1 exists, then compute b^-1
1720 * mod q. If b is changed, the client keys must be recomputed.
1723 BN_rand(b, BN_num_bits(dsa->q), 0, 0);
1724 BN_mod(b, b, dsa->q, ctx);
1725 BN_gcd(u, b, dsa->q, ctx);
1729 BN_mod_inverse(b1, b, dsa->q, ctx);
1732 * Make private client keys (xbar[j], xhat[j]) for all j. Note
1733 * that the keys for the jth client do not s1[j] or the product
1734 * s1[j]) (j = 1...n) which is q by construction.
1736 * Compute the factor w such that w s1[j] = s1[j] for all j. The
1737 * easy way to do this is to compute (q + s1[j]) / s1[j].
1738 * Exercise for the student: prove the remainder is always zero.
1740 for (j = 1; j <= n; j++) {
1741 xbar[j] = BN_new(); xhat[j] = BN_new();
1743 BN_add(w, dsa->q, s1[j]);
1744 BN_div(w, u, w, s1[j], ctx);
1747 for (i = 1; i <= n; i++) {
1751 BN_mod_exp(u, x[i], v, dsa->q, ctx);
1752 BN_add(xbar[j], xbar[j], u);
1754 BN_mod_mul(xbar[j], xbar[j], b1, dsa->q, ctx);
1755 BN_mod_exp(xhat[j], x[j], v, dsa->q, ctx);
1756 BN_mod_mul(xhat[j], xhat[j], w, dsa->q, ctx);
1760 * We revoke client j by dividing q by s1[j]. The quotient
1761 * becomes the enabling key s. Note we always have to revoke
1762 * one key; otherwise, the plaintext and cryptotext would be
1763 * identical. For the present there are no provisions to revoke
1764 * additional keys, so we sail on with only token revocations.
1768 BN_div(s, u, s, s1[n], ctx);
1771 * For each combination of clients to be revoked, make private
1772 * encryption key E = A^s and partial decryption keys gbar = g^s
1773 * and ghat = g^(s b), all mod p. The servers use these keys to
1774 * compute the session encryption key and partial decryption
1775 * keys. These values must be regenerated if the enabling key is
1778 bige = BN_new(); gbar = BN_new(); ghat = BN_new();
1779 BN_mod_exp(bige, biga, s, dsa->p, ctx);
1780 BN_mod_exp(gbar, dsa->g, s, dsa->p, ctx);
1781 BN_mod_mul(v, s, b, dsa->q, ctx);
1782 BN_mod_exp(ghat, dsa->g, v, dsa->p, ctx);
1785 * Notes: We produce the key media in three steps. The first
1786 * step is to generate the system parameters p, q, g, b, A and
1787 * the enabling keys s1[j]. Associated with each s1[j] are
1788 * parameters xbar[j] and xhat[j]. All of these parameters are
1789 * retained in a data structure protecteted by the trusted-agent
1790 * password. The p, xbar[j] and xhat[j] paremeters are
1791 * distributed to the j clients. When the client keys are to be
1792 * activated, the enabled keys are multipied together to form
1793 * the master enabling key s. This and the other parameters are
1794 * used to compute the server encryption key E and the partial
1795 * decryption keys gbar and ghat.
1797 * In the identity exchange the client rolls random r and sends
1798 * it to the server. The server rolls random k, which is used
1799 * only once, then computes the session key E^k and partial
1800 * decryption keys gbar^k and ghat^k. The server sends the
1801 * encrypted r along with gbar^k and ghat^k to the client. The
1802 * client completes the decryption and verifies it matches r.
1805 * Write the MV trusted-agent parameters and keys as a DSA
1806 * private key encoded in PEM.
1813 * (remaining values are not used)
1816 str = fheader("MVta", "mvta", groupname);
1817 fprintf(stderr, "Generating MV trusted-authority keys\n");
1818 BN_copy(dsa->priv_key, biga);
1819 BN_copy(dsa->pub_key, b);
1820 pkey = EVP_PKEY_new();
1821 EVP_PKEY_assign_DSA(pkey, dsa);
1822 PEM_write_PKCS8PrivateKey(str, pkey, cipher, NULL, 0, NULL,
1826 DSA_print_fp(stderr, dsa, 0);
1829 * Append the MV server parameters and keys as a DSA key encoded
1833 * q modulus q (used only when generating k)
1837 * (remaining values are not used)
1839 fprintf(stderr, "Generating MV server keys\n");
1841 dsa2->p = BN_dup(dsa->p);
1842 dsa2->q = BN_dup(dsa->q);
1843 dsa2->g = BN_dup(bige);
1844 dsa2->priv_key = BN_dup(gbar);
1845 dsa2->pub_key = BN_dup(ghat);
1846 pkey1 = EVP_PKEY_new();
1847 EVP_PKEY_assign_DSA(pkey1, dsa2);
1848 PEM_write_PKCS8PrivateKey(str, pkey1, cipher, NULL, 0, NULL,
1850 evpars[i++] = pkey1;
1852 DSA_print_fp(stderr, dsa2, 0);
1855 * Append the MV client parameters for each client j as DSA keys
1859 * priv_key xbar[j] mod q
1860 * pub_key xhat[j] mod q
1861 * (remaining values are not used)
1863 fprintf(stderr, "Generating %d MV client keys\n", n);
1864 for (j = 1; j <= n; j++) {
1866 sdsa->p = BN_dup(dsa->p);
1867 sdsa->q = BN_dup(BN_value_one());
1868 sdsa->g = BN_dup(BN_value_one());
1869 sdsa->priv_key = BN_dup(xbar[j]);
1870 sdsa->pub_key = BN_dup(xhat[j]);
1871 pkey1 = EVP_PKEY_new();
1872 EVP_PKEY_set1_DSA(pkey1, sdsa);
1873 PEM_write_PKCS8PrivateKey(str, pkey1, cipher, NULL, 0,
1875 evpars[i++] = pkey1;
1877 DSA_print_fp(stderr, sdsa, 0);
1880 * The product gbar^k)^xbar[j] (ghat^k)^xhat[j] and E
1881 * are inverses of each other. We check that the product
1882 * is one for each client except the ones that have been
1885 BN_mod_exp(v, dsa2->priv_key, sdsa->pub_key, dsa->p,
1887 BN_mod_exp(u, dsa2->pub_key, sdsa->priv_key, dsa->p,
1889 BN_mod_mul(u, u, v, dsa->p, ctx);
1890 BN_mod_mul(u, u, bige, dsa->p, ctx);
1891 if (!BN_is_one(u)) {
1892 fprintf(stderr, "Revoke key %d\n", j);
1900 * Free the countries.
1902 for (i = 0; i <= n; i++) {
1903 BN_free(a[i]); BN_free(g[i]);
1905 for (j = 1; j <= n; j++) {
1906 BN_free(x[j]); BN_free(xbar[j]); BN_free(xhat[j]);
1914 * Generate X509v3 certificate.
1916 * The certificate consists of the version number, serial number,
1917 * validity interval, issuer name, subject name and public key. For a
1918 * self-signed certificate, the issuer name is the same as the subject
1919 * name and these items are signed using the subject private key. The
1920 * validity interval extends from the current time to the same time one
1921 * year hence. For NTP purposes, it is convenient to use the NTP seconds
1922 * of the current time as the serial number.
1926 EVP_PKEY *pkey, /* signing key */
1927 const EVP_MD *md, /* signature/digest scheme */
1928 char *gqpub, /* identity extension (hex string) */
1929 const char *exten, /* private cert extension */
1930 char *name /* subject/issuer name */
1933 X509 *cert; /* X509 certificate */
1934 X509_NAME *subj; /* distinguished (common) name */
1935 X509_EXTENSION *ex; /* X509v3 extension */
1936 FILE *str; /* file handle */
1937 ASN1_INTEGER *serial; /* serial number */
1938 const char *id; /* digest/signature scheme name */
1939 char pathbuf[MAXFILENAME + 1];
1942 * Generate X509 self-signed certificate.
1944 * Set the certificate serial to the NTP seconds for grins. Set
1945 * the version to 3. Set the initial validity to the current
1946 * time and the finalvalidity one year hence.
1948 id = OBJ_nid2sn(md->pkey_type);
1949 fprintf(stderr, "Generating new certificate %s %s\n", name, id);
1951 X509_set_version(cert, 2L);
1952 serial = ASN1_INTEGER_new();
1953 ASN1_INTEGER_set(serial, (long)epoch + JAN_1970);
1954 X509_set_serialNumber(cert, serial);
1955 ASN1_INTEGER_free(serial);
1956 X509_time_adj(X509_get_notBefore(cert), 0L, &epoch);
1957 X509_time_adj(X509_get_notAfter(cert), lifetime * SECSPERDAY, &epoch);
1958 subj = X509_get_subject_name(cert);
1959 X509_NAME_add_entry_by_txt(subj, "commonName", MBSTRING_ASC,
1960 (u_char *)name, -1, -1, 0);
1961 subj = X509_get_issuer_name(cert);
1962 X509_NAME_add_entry_by_txt(subj, "commonName", MBSTRING_ASC,
1963 (u_char *)name, -1, -1, 0);
1964 if (!X509_set_pubkey(cert, pkey)) {
1965 fprintf(stderr, "Assign certificate signing key fails\n%s\n",
1966 ERR_error_string(ERR_get_error(), NULL));
1972 * Add X509v3 extensions if present. These represent the minimum
1973 * set defined in RFC3280 less the certificate_policy extension,
1974 * which is seriously obfuscated in OpenSSL.
1977 * The basic_constraints extension CA:TRUE allows servers to
1978 * sign client certficitates.
1980 fprintf(stderr, "%s: %s\n", LN_basic_constraints,
1982 ex = X509V3_EXT_conf_nid(NULL, NULL, NID_basic_constraints,
1983 _UC(BASIC_CONSTRAINTS));
1984 if (!X509_add_ext(cert, ex, -1)) {
1985 fprintf(stderr, "Add extension field fails\n%s\n",
1986 ERR_error_string(ERR_get_error(), NULL));
1989 X509_EXTENSION_free(ex);
1992 * The key_usage extension designates the purposes the key can
1995 fprintf(stderr, "%s: %s\n", LN_key_usage, KEY_USAGE);
1996 ex = X509V3_EXT_conf_nid(NULL, NULL, NID_key_usage, _UC(KEY_USAGE));
1997 if (!X509_add_ext(cert, ex, -1)) {
1998 fprintf(stderr, "Add extension field fails\n%s\n",
1999 ERR_error_string(ERR_get_error(), NULL));
2002 X509_EXTENSION_free(ex);
2004 * The subject_key_identifier is used for the GQ public key.
2005 * This should not be controversial.
2007 if (gqpub != NULL) {
2008 fprintf(stderr, "%s\n", LN_subject_key_identifier);
2009 ex = X509V3_EXT_conf_nid(NULL, NULL,
2010 NID_subject_key_identifier, gqpub);
2011 if (!X509_add_ext(cert, ex, -1)) {
2013 "Add extension field fails\n%s\n",
2014 ERR_error_string(ERR_get_error(), NULL));
2017 X509_EXTENSION_free(ex);
2021 * The extended key usage extension is used for special purpose
2022 * here. The semantics probably do not conform to the designer's
2023 * intent and will likely change in future.
2025 * "trustRoot" designates a root authority
2026 * "private" designates a private certificate
2028 if (exten != NULL) {
2029 fprintf(stderr, "%s: %s\n", LN_ext_key_usage, exten);
2030 ex = X509V3_EXT_conf_nid(NULL, NULL,
2031 NID_ext_key_usage, _UC(exten));
2032 if (!X509_add_ext(cert, ex, -1)) {
2034 "Add extension field fails\n%s\n",
2035 ERR_error_string(ERR_get_error(), NULL));
2038 X509_EXTENSION_free(ex);
2044 X509_sign(cert, pkey, md);
2045 if (X509_verify(cert, pkey) <= 0) {
2046 fprintf(stderr, "Verify %s certificate fails\n%s\n", id,
2047 ERR_error_string(ERR_get_error(), NULL));
2053 * Write the certificate encoded in PEM.
2055 snprintf(pathbuf, sizeof(pathbuf), "%scert", id);
2056 str = fheader(pathbuf, "cert", hostname);
2057 PEM_write_X509(str, cert);
2060 X509_print_fp(stderr, cert);
2065 #if 0 /* asn2ntp is used only with commercial certificates */
2067 * asn2ntp - convert ASN1_TIME time structure to NTP time
2071 ASN1_TIME *asn1time /* pointer to ASN1_TIME structure */
2074 char *v; /* pointer to ASN1_TIME string */
2075 struct tm tm; /* time decode structure time */
2078 * Extract time string YYMMDDHHMMSSZ from ASN.1 time structure.
2079 * Note that the YY, MM, DD fields start with one, the HH, MM,
2080 * SS fiels start with zero and the Z character should be 'Z'
2081 * for UTC. Also note that years less than 50 map to years
2082 * greater than 100. Dontcha love ASN.1?
2084 if (asn1time->length > 13)
2086 v = (char *)asn1time->data;
2087 tm.tm_year = (v[0] - '0') * 10 + v[1] - '0';
2088 if (tm.tm_year < 50)
2090 tm.tm_mon = (v[2] - '0') * 10 + v[3] - '0' - 1;
2091 tm.tm_mday = (v[4] - '0') * 10 + v[5] - '0';
2092 tm.tm_hour = (v[6] - '0') * 10 + v[7] - '0';
2093 tm.tm_min = (v[8] - '0') * 10 + v[9] - '0';
2094 tm.tm_sec = (v[10] - '0') * 10 + v[11] - '0';
2098 return (mktime(&tm) + JAN_1970);
2109 void *chr /* arg 3 */
2115 fprintf(stderr, "%s %d %d %lu\r", (char *)chr, n1, n2,
2120 fprintf(stderr, "%s\t\t%d %d %lu\r", (char *)chr, n1,
2125 fprintf(stderr, "%s\t\t\t\t%d %d %lu\r", (char *)chr,
2130 fprintf(stderr, "%s\t\t\t\t\t\t%d %d %lu\r",
2131 (char *)chr, n1, n2, d3);
2140 EVP_PKEY * /* public/private key pair */
2142 const char *type, /* key type (RSA or DSA) */
2143 const char *id /* file name id */
2148 if (strcmp(type, "RSA") == 0)
2149 return (gen_rsa(id));
2151 else if (strcmp(type, "DSA") == 0)
2152 return (gen_dsa(id));
2154 fprintf(stderr, "Invalid %s key type %s\n", id, type);
2157 #endif /* AUTOKEY */
2161 * Generate file header and link
2165 const char *file, /* file name id */
2166 const char *ulink, /* linkname */
2167 const char *owner /* owner name */
2170 FILE *str; /* file handle */
2171 char linkname[MAXFILENAME]; /* link name */
2177 snprintf(filename, sizeof(filename), "ntpkey_%s_%s.%u", file,
2180 orig_umask = umask( S_IWGRP | S_IRWXO );
2181 str = fopen(filename, "w");
2182 (void) umask(orig_umask);
2184 str = fopen(filename, "w");
2190 if (strcmp(ulink, "md5") == 0) {
2191 strcpy(linkname,"ntp.keys");
2193 snprintf(linkname, sizeof(linkname), "ntpkey_%s_%s", ulink,
2196 (void)remove(linkname); /* The symlink() line below matters */
2197 temp = symlink(filename, linkname);
2200 fprintf(stderr, "Generating new %s file and link\n", ulink);
2201 fprintf(stderr, "%s->%s\n", linkname, filename);
2202 fprintf(str, "# %s\n# %s\n", filename, ctime(&epoch));