Support for generating Diffie-Hellman groups (/etc/moduli) from ssh-keygen.

Based on code from Phil Karn, William Allen Simpson and Niels Provos.
ok markus@, thanks jmc@

5 files changed, 822 insertions, 7 deletions

diff --git a/usr.bin/ssh/moduli.c b/usr.bin/ssh/moduli.c
new file mode 100644
index 00000000000..eb2c0fd18e8
--- /dev/null
+++ b/usr.bin/ssh/moduli.c
@@ -0,0 +1,617 @@
+/* $OpenBSD: moduli.c,v 1.1 2003/07/28 09:49:56 djm Exp $ */
+/*
+ * Copyright 1994 Phil Karn <karn@qualcomm.com>
+ * Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com>
+ * Copyright 2000 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Two-step process to generate safe primes for DHGEX
+ *
+ *  Sieve candidates for "safe" primes,
+ *  suitable for use as Diffie-Hellman moduli;
+ *  that is, where q = (p-1)/2 is also prime.
+ *
+ * First step: generate candidate primes (memory intensive)
+ * Second step: test primes' safety (processor intensive)
+ */
+
+#include "includes.h"
+#include "moduli.h"
+#include "xmalloc.h"
+#include "log.h"
+
+#include <openssl/bn.h>
+
+
+/*
+ * Debugging defines 
+ */
+
+/* define DEBUG_LARGE 1 */
+/* define DEBUG_SMALL 1 */
+/* define DEBUG_TEST  1 */
+
+/*
+ * File output defines
+ */
+
+/* need line long enough for largest moduli plus headers */
+#define QLINESIZE               (100+8192)
+
+/* Type: decimal.
+ * Specifies the internal structure of the prime modulus.
+ */
+#define QTYPE_UNKNOWN           (0)
+#define QTYPE_UNSTRUCTURED      (1)
+#define QTYPE_SAFE              (2)
+#define QTYPE_SCHNOOR           (3)
+#define QTYPE_SOPHIE_GERMAINE   (4)
+#define QTYPE_STRONG            (5)
+
+/* Tests: decimal (bit field).
+ * Specifies the methods used in checking for primality.
+ * Usually, more than one test is used.
+ */
+#define QTEST_UNTESTED          (0x00)
+#define QTEST_COMPOSITE         (0x01)
+#define QTEST_SIEVE             (0x02)
+#define QTEST_MILLER_RABIN      (0x04)
+#define QTEST_JACOBI            (0x08)
+#define QTEST_ELLIPTIC          (0x10)
+
+/* Size: decimal.
+ * Specifies the number of the most significant bit (0 to M).
+ ** WARNING: internally, usually 1 to N.
+ */
+#define QSIZE_MINIMUM           (511)
+
+/*
+ * Prime sieving defines
+ */
+
+/* Constant: assuming 8 bit bytes and 32 bit words */
+#define SHIFT_BIT       (3)
+#define SHIFT_BYTE      (2)
+#define SHIFT_WORD      (SHIFT_BIT+SHIFT_BYTE)
+#define SHIFT_MEGABYTE  (20)
+#define SHIFT_MEGAWORD  (SHIFT_MEGABYTE-SHIFT_BYTE)
+
+/*
+ * Constant: when used with 32-bit integers, the largest sieve prime
+ * has to be less than 2**32.
+ */
+#define SMALL_MAXIMUM   (0xffffffffUL)
+
+/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */
+#define TINY_NUMBER     (1UL<<16)
+
+/* Ensure enough bit space for testing 2*q. */
+#define TEST_MAXIMUM    (1UL<<16)
+#define TEST_MINIMUM    (QSIZE_MINIMUM + 1)
+/* real TEST_MINIMUM    (1UL << (SHIFT_WORD - TEST_POWER)) */
+#define TEST_POWER      (3)	/* 2**n, n < SHIFT_WORD */
+
+/* bit operations on 32-bit words */
+#define BIT_CLEAR(a,n)  ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31)))
+#define BIT_SET(a,n)    ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31)))
+#define BIT_TEST(a,n)   ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31)))
+
+/*
+ * Prime testing defines
+ */
+
+/*
+ * Sieving data (XXX - move to struct)
+ */
+
+/* sieve 2**16 */
+static u_int32_t *TinySieve, tinybits;
+
+/* sieve 2**30 in 2**16 parts */
+static u_int32_t *SmallSieve, smallbits, smallbase;
+
+/* sieve relative to the initial value */
+static u_int32_t *LargeSieve, largewords, largetries, largenumbers;
+static u_int32_t largebits, largememory;	/* megabytes */
+static BIGNUM *largebase;
+
+
+/*
+ * print moduli out in consistent form,
+ */
+static int
+qfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries,
+    u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus)
+{
+	struct tm *gtm;
+	time_t time_now;
+	int res;
+
+	time(&time_now);
+	gtm = gmtime(&time_now);
+	
+	res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ",
+	    gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday,
+	    gtm->tm_hour, gtm->tm_min, gtm->tm_sec,
+	    otype, otests, otries, osize, ogenerator);
+
+	if (res < 0)
+		return (-1);
+
+	if (BN_print_fp(ofile, omodulus) < 1)
+		return (-1);
+
+	res = fprintf(ofile, "\n");
+	fflush(ofile);
+
+	return (res > 0 ? 0 : -1);
+}
+
+
+/*
+ ** Sieve p's and q's with small factors
+ */
+static void
+sieve_large(u_int32_t s)
+{
+	u_int32_t r, u;
+
+	debug2("sieve_large %u", s);
+	largetries++;
+	/* r = largebase mod s */
+	r = BN_mod_word(largebase, s);
+	if (r == 0)
+		u = 0; /* s divides into largebase exactly */
+	else
+		u = s - r; /* largebase+u is first entry divisible by s */
+
+	if (u < largebits * 2) {
+		/*
+		 * The sieve omits p's and q's divisible by 2, so ensure that
+		 * largebase+u is odd. Then, step through the sieve in
+		 * increments of 2*s
+		 */
+		if (u & 0x1)
+			u += s; /* Make largebase+u odd, and u even */
+
+		/* Mark all multiples of 2*s */
+		for (u /= 2; u < largebits; u += s)
+			BIT_SET(LargeSieve, u);
+	}
+
+	/* r = p mod s */
+	r = (2 * r + 1) % s;
+	if (r == 0)
+		u = 0; /* s divides p exactly */
+	else
+		u = s - r; /* p+u is first entry divisible by s */
+
+	if (u < largebits * 4) {
+		/*
+		 * The sieve omits p's divisible by 4, so ensure that
+		 * largebase+u is not. Then, step through the sieve in
+		 * increments of 4*s
+		 */
+		while (u & 0x3) {
+			if (SMALL_MAXIMUM - u < s)
+				return;
+			u += s;
+		}
+
+		/* Mark all multiples of 4*s */
+		for (u /= 4; u < largebits; u += s)
+			BIT_SET(LargeSieve, u);
+	}
+}
+
+/*
+ * list candidates for Sophie-Germaine primes (where q = (p-1)/2)
+ * to standard output.
+ * The list is checked against small known primes (less than 2**30).
+ */
+int
+gen_candidates(FILE *out, int memory, int power, BIGNUM *start)
+{
+	BIGNUM *q;
+	u_int32_t j, r, s, t;
+	u_int32_t smallwords = TINY_NUMBER >> 6;
+	u_int32_t tinywords = TINY_NUMBER >> 6;
+	time_t time_start, time_stop;
+	int i, ret = 0;
+
+	largememory = memory;
+
+	/*
+         * Set power to the length in bits of the prime to be generated.
+         * This is changed to 1 less than the desired safe prime moduli p.
+         */
+	if (power > TEST_MAXIMUM) {
+		error("Too many bits: %u > %lu", power, TEST_MAXIMUM);
+		return (-1);
+	} else if (power < TEST_MINIMUM) {
+		error("Too few bits: %u < %u", power, TEST_MINIMUM);
+		return (-1);
+	}
+	power--; /* decrement before squaring */
+
+	/*
+         * The density of ordinary primes is on the order of 1/bits, so the
+         * density of safe primes should be about (1/bits)**2. Set test range
+         * to something well above bits**2 to be reasonably sure (but not
+         * guaranteed) of catching at least one safe prime.
+	 */
+	largewords = ((power * power) >> (SHIFT_WORD - TEST_POWER));
+
+	/*
+         * Need idea of how much memory is available. We don't have to use all
+         * of it.
+	 */
+	if (largememory > LARGE_MAXIMUM) {
+		logit("Limited memory: %u MB; limit %lu MB",
+		    largememory, LARGE_MAXIMUM);
+		largememory = LARGE_MAXIMUM;
+	}
+
+	if (largewords <= (largememory << SHIFT_MEGAWORD)) {
+		logit("Increased memory: %u MB; need %u bytes",
+		    largememory, (largewords << SHIFT_BYTE));
+		largewords = (largememory << SHIFT_MEGAWORD);
+	} else if (largememory > 0) {
+		logit("Decreased memory: %u MB; want %u bytes",
+		    largememory, (largewords << SHIFT_BYTE));
+		largewords = (largememory << SHIFT_MEGAWORD);
+	}
+
+	TinySieve = calloc(tinywords, sizeof(u_int32_t));
+	if (TinySieve == NULL) {
+		error("Insufficient memory for tiny sieve: need %u bytes",
+		    tinywords << SHIFT_BYTE);
+		exit(1);
+	}
+	tinybits = tinywords << SHIFT_WORD;
+
+	SmallSieve = calloc(smallwords, sizeof(u_int32_t));
+	if (SmallSieve == NULL) {
+		error("Insufficient memory for small sieve: need %u bytes",
+		    smallwords << SHIFT_BYTE);
+		xfree(TinySieve);
+		exit(1);
+	}
+	smallbits = smallwords << SHIFT_WORD;
+
+	/*
+	 * dynamically determine available memory
+	 */
+	while ((LargeSieve = calloc(largewords, sizeof(u_int32_t))) == NULL)
+		largewords -= (1L << (SHIFT_MEGAWORD - 2)); /* 1/4 MB chunks */
+
+	largebits = largewords << SHIFT_WORD;
+	largenumbers = largebits * 2;	/* even numbers excluded */
+
+	/* validation check: count the number of primes tried */
+	largetries = 0;
+	q = BN_new();
+
+	/*
+         * Generate random starting point for subprime search, or use
+         * specified parameter.
+	 */
+	largebase = BN_new();
+	if (start == NULL)
+		BN_rand(largebase, power, 1, 1);
+	else
+		BN_copy(largebase, start);
+
+	/* ensure odd */
+	BN_set_bit(largebase, 0);
+
+	time(&time_start);
+
+	logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start), 
+	    largenumbers, power);
+	debug2("start point: 0x%s", BN_bn2hex(largebase));
+
+	/*
+         * TinySieve
+         */
+	for (i = 0; i < tinybits; i++) {
+		if (BIT_TEST(TinySieve, i))
+			continue; /* 2*i+3 is composite */
+
+		/* The next tiny prime */
+		t = 2 * i + 3;
+
+		/* Mark all multiples of t */
+		for (j = i + t; j < tinybits; j += t)
+			BIT_SET(TinySieve, j);
+
+		sieve_large(t);
+	}
+
+	/*
+         * Start the small block search at the next possible prime. To avoid
+         * fencepost errors, the last pass is skipped.
+         */
+	for (smallbase = TINY_NUMBER + 3;
+	     smallbase < (SMALL_MAXIMUM - TINY_NUMBER);
+	     smallbase += TINY_NUMBER) {
+		for (i = 0; i < tinybits; i++) {
+			if (BIT_TEST(TinySieve, i))
+				continue; /* 2*i+3 is composite */
+
+			/* The next tiny prime */
+			t = 2 * i + 3;
+			r = smallbase % t;
+
+			if (r == 0) {
+				s = 0; /* t divides into smallbase exactly */
+			} else {
+				/* smallbase+s is first entry divisible by t */
+				s = t - r;
+			}
+
+			/*
+			 * The sieve omits even numbers, so ensure that
+			 * smallbase+s is odd. Then, step through the sieve
+			 * in increments of 2*t
+			 */
+			if (s & 1)
+				s += t; /* Make smallbase+s odd, and s even */
+
+			/* Mark all multiples of 2*t */
+			for (s /= 2; s < smallbits; s += t)
+				BIT_SET(SmallSieve, s);
+		}
+
+		/*
+                 * SmallSieve
+                 */
+		for (i = 0; i < smallbits; i++) {
+			if (BIT_TEST(SmallSieve, i))
+				continue; /* 2*i+smallbase is composite */
+
+			/* The next small prime */
+			sieve_large((2 * i) + smallbase);
+		}
+
+		memset(SmallSieve, 0, smallwords << SHIFT_BYTE);
+	}
+
+	time(&time_stop);
+
+	logit("%.24s Sieved with %u small primes in %ld seconds",
+	    ctime(&time_stop), largetries, (long) (time_stop - time_start));
+
+	for (j = r = 0; j < largebits; j++) {
+		if (BIT_TEST(LargeSieve, j))
+			continue; /* Definitely composite, skip */
+
+		debug2("test q = largebase+%u", 2 * j);
+		BN_set_word(q, 2 * j);
+		BN_add(q, q, largebase);
+		if (qfileout(out, QTYPE_SOPHIE_GERMAINE, QTEST_SIEVE,
+		    largetries, (power - 1) /* MSB */, (0), q) == -1) {
+			ret = -1;
+			break;
+		}
+
+		r++; /* count q */
+	}
+
+	time(&time_stop);
+
+	xfree(LargeSieve);
+	xfree(SmallSieve);
+	xfree(TinySieve);
+
+	logit("%.24s Found %u candidates", ctime(&time_stop), r);
+
+	return (ret);
+}
+
+/*
+ * perform a Miller-Rabin primality test
+ * on the list of candidates
+ * (checking both q and p)
+ * The result is a list of so-call "safe" primes
+ */
+int
+prime_test(FILE *in, FILE *out, u_int32_t trials, 
+    u_int32_t generator_wanted)
+{
+	BIGNUM *q, *p, *a;
+	BN_CTX *ctx;
+	char *cp, *lp;
+	u_int32_t count_in = 0, count_out = 0, count_possible = 0;
+	u_int32_t generator_known, in_tests, in_tries, in_type, in_size;
+	time_t time_start, time_stop;
+	int res;
+
+	time(&time_start);
+
+	p = BN_new();
+	q = BN_new();
+	ctx = BN_CTX_new();
+
+	debug2("%.24s Final %u Miller-Rabin trials (%x generator)",
+	    ctime(&time_start), trials, generator_wanted);
+
+	res = 0;
+	lp = xmalloc(QLINESIZE + 1);
+	while (fgets(lp, QLINESIZE, in) != NULL) {
+		int ll = strlen(lp);
+
+		count_in++;
+		if (ll < 14 || *lp == '!' || *lp == '#') {
+			debug2("%10u: comment or short line", count_in);
+			continue;
+		}
+
+		/* XXX - fragile parser */
+		/* time */
+		cp = &lp[14];	/* (skip) */
+
+		/* type */
+		in_type = strtoul(cp, &cp, 10);
+
+		/* tests */
+		in_tests = strtoul(cp, &cp, 10);
+
+		if (in_tests & QTEST_COMPOSITE) {
+			debug2("%10u: known composite", count_in);
+			continue;
+		}
+		/* tries */
+		in_tries = strtoul(cp, &cp, 10);
+
+		/* size (most significant bit) */
+		in_size = strtoul(cp, &cp, 10);
+
+		/* generator (hex) */
+		generator_known = strtoul(cp, &cp, 16);
+
+		/* Skip white space */
+		cp += strspn(cp, " ");
+
+		/* modulus (hex) */
+		switch (in_type) {
+		case QTYPE_SOPHIE_GERMAINE:
+			debug2("%10u: (%u) Sophie-Germaine", count_in, in_type);
+			a = q;
+			BN_hex2bn(&a, cp);
+			/* p = 2*q + 1 */
+			BN_lshift(p, q, 1);
+			BN_add_word(p, 1);
+			in_size += 1;
+			generator_known = 0;
+			break;
+		default:
+			debug2("%10u: (%u)", count_in, in_type);
+			a = p;
+			BN_hex2bn(&a, cp);
+			/* q = (p-1) / 2 */
+			BN_rshift(q, p, 1);
+			break;
+		}
+
+		/*
+		 * due to earlier inconsistencies in interpretation, check
+		 * the proposed bit size.
+		 */
+		if (BN_num_bits(p) != (in_size + 1)) {
+			debug2("%10u: bit size %u mismatch", count_in, in_size);
+			continue;
+		}
+		if (in_size < QSIZE_MINIMUM) {
+			debug2("%10u: bit size %u too short", count_in, in_size);
+			continue;
+		}
+
+		if (in_tests & QTEST_MILLER_RABIN)
+			in_tries += trials;
+		else
+			in_tries = trials;
+		/*
+		 * guess unknown generator
+		 */
+		if (generator_known == 0) {
+			if (BN_mod_word(p, 24) == 11)
+				generator_known = 2;
+			else if (BN_mod_word(p, 12) == 5)
+				generator_known = 3;
+			else {
+				u_int32_t r = BN_mod_word(p, 10);
+
+				if (r == 3 || r == 7) {
+					generator_known = 5;
+				}
+			}
+		}
+		/*
+		 * skip tests when desired generator doesn't match
+		 */
+		if (generator_wanted > 0 &&
+		    generator_wanted != generator_known) {
+			debug2("%10u: generator %d != %d",
+			    count_in, generator_known, generator_wanted);
+			continue;
+		}
+
+		count_possible++;
+
+		/*
+		 * The (1/4)^N performance bound on Miller-Rabin is 
+		 * extremely pessimistic, so don't spend a lot of time 
+		 * really verifying that q is prime until after we know 
+		 * that p is also prime. A single pass will weed out the 
+		 * vast majority of composite q's.
+		 */
+		if (BN_is_prime(q, 1, NULL, ctx, NULL) <= 0) {
+			debug2("%10u: q failed first possible prime test",
+			    count_in);
+			continue;
+		}
+	
+		/*
+		 * q is possibly prime, so go ahead and really make sure 
+		 * that p is prime. If it is, then we can go back and do 
+		 * the same for q. If p is composite, chances are that 
+		 * will show up on the first Rabin-Miller iteration so it
+		 * doesn't hurt to specify a high iteration count.
+		 */
+		if (!BN_is_prime(p, trials, NULL, ctx, NULL)) {
+			debug2("%10u: p is not prime", count_in);
+			continue;
+		}
+		debug("%10u: p is almost certainly prime", count_in);
+
+		/* recheck q more rigorously */
+		if (!BN_is_prime(q, trials - 1, NULL, ctx, NULL)) {
+			debug("%10u: q is not prime", count_in);
+			continue;
+		}
+		debug("%10u: q is almost certainly prime", count_in);
+
+		if (qfileout(out, QTYPE_SAFE, (in_tests | QTEST_MILLER_RABIN), 
+		    in_tries, in_size, generator_known, p)) {
+			res = -1;
+			break;
+		}
+
+		count_out++;
+	}
+
+	time(&time_stop);
+	xfree(lp);
+	BN_free(p);
+	BN_free(q);
+	BN_CTX_free(ctx);
+
+	logit("%.24s Found %u safe primes of %u candidates in %ld seconds",
+	    ctime(&time_stop), count_out, count_possible, 
+	    (long) (time_stop - time_start));
+
+	return (res);
+}
diff --git a/usr.bin/ssh/moduli.h b/usr.bin/ssh/moduli.h
new file mode 100644
index 00000000000..9cd1cd3f86c
--- /dev/null
+++ b/usr.bin/ssh/moduli.h
@@ -0,0 +1,23 @@
+/* $OpenBSD: moduli.h,v 1.1 2003/07/28 09:49:56 djm Exp $ */
+
+#include <sys/types.h>
+#include <openssl/bn.h>
+
+/*
+ * Using virtual memory can cause thrashing.  This should be the largest
+ * number that is supported without a large amount of disk activity --
+ * that would increase the run time from hours to days or weeks!
+ */
+#define LARGE_MINIMUM   (8UL)	/* megabytes */
+
+/*
+ * Do not increase this number beyond the unsigned integer bit size.
+ * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits).
+ */
+#define LARGE_MAXIMUM   (127UL)	/* megabytes */
+
+/* Minimum number of primality tests to perform */
+#define TRIAL_MINIMUM           (4)
+
+int gen_candidates(FILE *, int, int, BIGNUM *);
+int prime_test(FILE *, FILE *, u_int32_t, u_int32_t);
diff --git a/usr.bin/ssh/ssh-keygen.1 b/usr.bin/ssh/ssh-keygen.1
index fc6b5a5e0a2..dc4bcacd00e 100644
--- a/usr.bin/ssh/ssh-keygen.1
+++ b/usr.bin/ssh/ssh-keygen.1
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: ssh-keygen.1,v 1.59 2003/06/10 09:12:11 jmc Exp $
+.\"	$OpenBSD: ssh-keygen.1,v 1.60 2003/07/28 09:49:56 djm Exp $
 .\"
 .\"  -*- nroff -*-
 .\"
@@ -87,6 +87,16 @@
 .Fl r Ar hostname
 .Op Fl f Ar input_keyfile
 .Op Fl g
+.Nm ssh-keygen
+.Fl G Ar output_file
+.Op Fl b Ar bits
+.Op Fl M Ar memory
+.Op Fl S Ar start_point
+.Nm ssh-keygen
+.Fl T Ar output_file
+.Fl f Ar input_file
+.Op Fl a Ar num_trials
+.Op Fl W Ar generator
 .Sh DESCRIPTION
 .Nm
 generates, manages and converts authentication keys for
@@ -98,6 +108,13 @@ The type of key to be generated is specified with the
 .Fl t
 option.
 .Pp
+.Nm
+is also used to generate groups for use in Diffie-Hellman group
+exchange (DH-GEX).
+See the
+.Sx MODULI GENERATION
+section for details.
+.Pp
 Normally each user wishing to use SSH
 with RSA or DSA authentication runs this once to create the authentication
 key in
@@ -150,6 +167,11 @@ should be placed to be activated.
 .Pp
 The options are as follows:
 .Bl -tag -width Ds
+.It Fl a Ar trials
+Specifies the number of primality tests to perform when screening DH-GEX
+candidates using the
+.Fl T
+command.
 .It Fl b Ar bits
 Specifies the number of bits in the key to create.
 Minimum is 512 bits.
@@ -217,10 +239,27 @@ Provides the new comment.
 .It Fl D Ar reader
 Download the RSA public key stored in the smartcard in
 .Ar reader .
+.It Fl G Ar output_file
+Generate candidate primes for DH-GEX.
+These primes must be screened for
+safety (using the
+.Fl T
+option) before use.
+.It Fl M Ar memory
+Specify the amount of memory to use (in megabytes) when generating
+candidate moduli for DH-GEX.
 .It Fl N Ar new_passphrase
 Provides the new passphrase.
 .It Fl P Ar passphrase
 Provides the (old) passphrase.
+.It Fl S Ar start
+Specify start point (in hex) when generating candidate moduli for DH-GEX.
+.It Fl T Ar output_file
+Test DH group exchange candidate primes (generated using the
+.Fl G
+option) for safety.
+.It Fl W Ar generator
+Specify desired generator when testing candidate moduli for DH-GEX.
 .It Fl U Ar reader
 Upload an existing RSA private key into the smartcard in
 .Ar reader .
@@ -228,6 +267,60 @@ Upload an existing RSA private key into the smartcard in
 Print DNS resource record with the specified
 .Ar hostname .
 .El
+.Sh MODULI GENERATION
+.Nm
+may be used to generate groups for the Diffie-Hellman Group Exchange
+(DH-GEX) protocol.
+Generating these groups is a two-step process: first, candidate
+primes are generated using a fast, but memory intensive process.
+These candidate primes are then tested for suitability (a CPU-intensive
+process).
+.Pp
+Generation of primes is performed using the
+.Fl G
+option.
+The desired length of the primes may be specified by the
+.Fl b
+option.
+For example:
+.Pp
+.Dl ssh-keygen -G moduli-2048.candidates -b 2048
+.Pp
+By default, the search for primes begins at a random point in the
+desired length range.
+This may be overridden using the
+.Fl S
+option, which specifies a different start point (in hex).
+.Pp
+Once a set of candidates have been generated, they must be tested for
+suitability.
+This may be performed using the
+.Fl T
+option.
+In this mode
+.Nm
+will read candidates from standard input (or a file specified using the
+.Fl f
+option).
+For example:
+.Pp
+.Dl ssh-keygen -T moduli-2048 -f moduli-2048.candidates
+.Pp
+By default, each candidate will be subjected to 100 primality tests.
+This may be overridden using the
+.Fl a
+option.
+The DH generator value will be chosen automatically for the
+prime under consideration.
+If a specific generator is desired, it may be requested using the
+.Fl W
+option.
+Valid generator values are 2, 3 and 5.
+.Pp
+Screened DH groups may be installed in
+.Pa /etc/moduli .
+It is important that this file contains moduli of a range of bit lengths and
+that both ends of a connection share common moduli.
 .Sh FILES
 .Bl -tag -width Ds
 .It Pa $HOME/.ssh/identity
@@ -284,11 +377,16 @@ The contents of this file should be added to
 on all machines
 where the user wishes to log in using public key authentication.
 There is no need to keep the contents of this file secret.
+.It Pa /etc/moduli
+Contains Diffie-Hellman groups used for DH-GEX.
+The file format is described in
+.Xr moduli 5 .
 .El
 .Sh SEE ALSO
 .Xr ssh 1 ,
 .Xr ssh-add 1 ,
 .Xr ssh-agent 1 ,
+.Xr moduli 5 ,
 .Xr sshd 8
 .Rs
 .%A J. Galbraith
diff --git a/usr.bin/ssh/ssh-keygen.c b/usr.bin/ssh/ssh-keygen.c
index 5f68e528482..206c761bf27 100644
--- a/usr.bin/ssh/ssh-keygen.c
+++ b/usr.bin/ssh/ssh-keygen.c
@@ -12,7 +12,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: ssh-keygen.c,v 1.106 2003/05/15 03:10:52 djm Exp $");
+RCSID("$OpenBSD: ssh-keygen.c,v 1.107 2003/07/28 09:49:56 djm Exp $");
 
 #include <openssl/evp.h>
 #include <openssl/pem.h>
@@ -27,6 +27,7 @@ RCSID("$OpenBSD: ssh-keygen.c,v 1.106 2003/05/15 03:10:52 djm Exp $");
 #include "pathnames.h"
 #include "log.h"
 #include "readpass.h"
+#include "moduli.h"
 
 #ifdef SMARTCARD
 #include "scard.h"
@@ -777,6 +778,9 @@ usage(void)
 	fprintf(stderr, "  -U reader   Upload private key to smartcard.\n");
 #endif /* SMARTCARD */
 
+	fprintf(stderr, "  -G file     Generate candidates for DH-GEX moduli\n");
+	fprintf(stderr, "  -T file     Screen candidates for DH-GEX moduli\n");
+
 	exit(1);
 }
 
@@ -787,18 +791,22 @@ int
 main(int ac, char **av)
 {
 	char dotsshdir[MAXPATHLEN], comment[1024], *passphrase1, *passphrase2;
-	char *reader_id = NULL;
+	char out_file[PATH_MAX], *reader_id = NULL;
 	char *resource_record_hostname = NULL;
 	Key *private, *public;
 	struct passwd *pw;
 	struct stat st;
-	int opt, type, fd, download = 0;
+	int opt, type, fd, download = 0, memory = 0;
+	int generator_wanted = 0, trials = 100;
+	int do_gen_candidates = 0, do_screen_candidates = 0;
+	BIGNUM *start = NULL;
 	FILE *f;
 
 	extern int optind;
 	extern char *optarg;
 
 	SSLeay_add_all_algorithms();
+	log_init(av[0], SYSLOG_LEVEL_INFO, SYSLOG_FACILITY_USER, 1);
 
 	/* we need this for the home * directory.  */
 	pw = getpwuid(getuid());
@@ -811,7 +819,8 @@ main(int ac, char **av)
 		exit(1);
 	}
 
-	while ((opt = getopt(ac, av, "degiqpclBRxXyb:f:t:U:D:P:N:C:r:")) != -1) {
+	while ((opt = getopt(ac, av,
+	    "degiqpclBRxXyb:f:t:U:D:P:N:C:r:g:T:G:M:S:a:W:")) != -1) {
 		switch (opt) {
 		case 'b':
 			bits = atoi(optarg);
@@ -882,6 +891,39 @@ main(int ac, char **av)
 		case 'r':
 			resource_record_hostname = optarg;
 			break;
+		case 'W':
+			generator_wanted = atoi(optarg);
+			if (generator_wanted < 1)
+				fatal("Desired generator has bad value.");
+			break;
+		case 'a':
+			trials = atoi(optarg);
+			if (trials < TRIAL_MINIMUM) {
+				fatal("Minimum primality trials is %d", 
+				    TRIAL_MINIMUM);
+			}
+			break;
+		case 'M':
+			memory = atoi(optarg);
+			if (memory != 0 && 
+			   (memory < LARGE_MINIMUM || memory > LARGE_MAXIMUM)) {
+				fatal("Invalid memory amount (min %ld, max %ld)",
+				    LARGE_MINIMUM, LARGE_MAXIMUM);
+			}
+			break;
+		case 'G':
+			do_gen_candidates = 1;
+			strlcpy(out_file, optarg, sizeof(out_file));
+			break;
+		case 'T':
+			do_screen_candidates = 1;
+			strlcpy(out_file, optarg, sizeof(out_file));
+			break;
+		case 'S':
+			/* XXX - also compare length against bits */
+			if (BN_hex2bn(&start, optarg) == 0)
+				fatal("Invalid start point.");
+			break;
 		case '?':
 		default:
 			usage();
@@ -925,6 +967,41 @@ main(int ac, char **av)
 #endif /* SMARTCARD */
 	}
 
+	if (do_gen_candidates) {
+		FILE *out = fopen(out_file, "w");
+		
+		if (out == NULL) {
+			error("Couldn't open modulus candidate file \"%s\": %s",
+			    out_file, strerror(errno));
+			return (1);
+		}
+		if (gen_candidates(out, memory, bits, start) != 0)
+			fatal("modulus candidate generation failed\n");
+
+		return (0);
+	}
+
+	if (do_screen_candidates) {
+		FILE *in;
+		FILE *out = fopen(out_file, "w");
+
+		if (have_identity && strcmp(identity_file, "-") != 0) {
+			if ((in = fopen(identity_file, "r")) == NULL) {
+				fatal("Couldn't open modulus candidate "
+				    "file \"%s\": %s", identity_file, 
+				    strerror(errno));
+			}
+		} else
+			in = stdin;
+
+		if (out == NULL) {
+			fatal("Couldn't open moduli file \"%s\": %s",
+			    out_file, strerror(errno));
+		}
+		if (prime_test(in, out, trials, generator_wanted) != 0)
+			fatal("modulus screening failed\n");
+	}
+
 	arc4random_stir();
 
 	if (key_type_name == NULL) {
diff --git a/usr.bin/ssh/ssh-keygen/Makefile b/usr.bin/ssh/ssh-keygen/Makefile
index d175813bc0c..491583a44ab 100644
--- a/usr.bin/ssh/ssh-keygen/Makefile
+++ b/usr.bin/ssh/ssh-keygen/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.21 2001/06/27 19:29:16 markus Exp $
+#	$OpenBSD: Makefile,v 1.22 2003/07/28 09:49:56 djm Exp $
 
 .PATH:		${.CURDIR}/..
 
@@ -10,7 +10,7 @@ BINMODE?=555
 BINDIR=	/usr/bin
 MAN=	ssh-keygen.1
 
-SRCS=	ssh-keygen.c
+SRCS=	ssh-keygen.c moduli.c
 
 .include <bsd.prog.mk>