Date:	Sat,  7 Nov 2015 09:30:41 -0500
From:	Sandy Harris <sandyinchina@...il.com>
To:	"Theodore Ts\\'o" <tytso@....edu>,
	Jason Cooper <jason@...edaemon.net>,
	"H. Peter Anvin" <hpa@...or.com>, John Denker <jsd@...n.com>
Cc:	linux-kernel@...r.kernel.org, linux-crypto@...r.kernel.org
Subject: [PATCH 6/7] Produces generated/random_init.h for random driver

Signed-off-by: Sandy Harris <sandyinchina@...il.com>
---
 scripts/gen_random.c | 260 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 260 insertions(+)
 create mode 100644 scripts/gen_random.c

diff --git a/scripts/gen_random.c b/scripts/gen_random.c
new file mode 100644
index 0000000..07b447f
--- /dev/null
+++ b/scripts/gen_random.c
@@ -0,0 +1,260 @@
+/*
+ * Program to select random numbers for initialising things
+ * in the random(4) driver.
+ *
+ * A different implementation of basically the same idea is
+ * one of several kernel security enhancements at
+ * https://grsecurity.net/
+ *
+ * This program:
+ *
+ *    limits the range of Hamming weights
+ *    every byte has at least one bit 1, one 0
+ *    different every time it runs
+ *
+ * data from /dev/urandom
+ * results suitable for inclusion by random.c
+ * writes to stdout, expecting makefile to redirect
+ *
+ * makefile should also delete the output file after it is
+ * used in compilation of random.c. This is more secure; it
+ * forces the file to be rebuilt and a new version used in
+ * every compile. It also prevents an enemy just reading an
+ * output file in the build directory and getting the data
+ * that is in use in the current kernel. This is not full
+ * protection since they might look in the kernel image,
+ * but it seems to be the best we can do.
+ *
+ * This falls well short of the ideal initialisation solution,
+ * which would give every installation (rather than every
+ * compiled kernel) a different seed. For that, see John
+ * Denker's suggestions at:
+ * http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image
+ *
+ * On the other hand, neither sort of seed is necessary if
+ *    either  you have a trustworthy hardware RNG
+ *    or      you have secure stored data
+ * In those cases, the device can easily be initialised well; the
+ * only difficulty is to ensure this is done early enough.
+ *
+ * Inserting random data at compile time can do no harm and may
+ * sometimes make attacks harder. It is not an ideal solution, and
+ * not always necessary, but cheap and probably the best we can do
+ * during the build (rather than install) process.
+ *
+ * This is certainly done early enough and the data is random
+ * enough, but it is not necessarily secret enough.
+ *
+ * In some cases -- for example, a firewall machine that compiles
+ * its own kernel -- this alone might be enough to ensure secure
+ * initialisation, since only an enemy who already has root could
+ * discover this data. Of course even in those cases it should not
+ * be used alone, only as one layer of a defense in depth.
+ *
+ * In other cases -- a kernel that is compiled once then used in
+ * a Linux distro or installed on many devices -- this is likely
+ * of very little value. It complicates an attack somewhat, but
+ * it clearly will not stop a serious attacker and may not even
+ * slow them down much.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <stdint.h>
+#include <ctype.h>
+
+/*
+ * Configuration information
+ * moved from random.c
+ */
+#define INPUT_POOL_SHIFT	12
+#define INPUT_POOL_WORDS	(1 << (INPUT_POOL_SHIFT-5))
+#define OUTPUT_POOL_SHIFT	10
+#define OUTPUT_POOL_WORDS	(1 << (OUTPUT_POOL_SHIFT-5))
+
+#define TOTAL_POOL_WORDS  (INPUT_POOL_WORDS + 2*OUTPUT_POOL_WORDS)
+
+typedef uint32_t u32 ;
+
+int accept(u32) ;
+int hamming(u32);
+void do_block( int, char * ) ;
+void usage(void) ;
+
+int urandom ;
+
+int main(int argc, char **argv)
+{
+	if( (urandom = open("/dev/urandom", O_RDONLY)) == -1 )  {
+		fprintf(stderr, "gen_random_init: no /dev/urandom, cannot continue\n") ;
+		exit(1) ;
+	}
+	printf("/* File generated by gen_random_init.c */\n\n") ;
+	/*
+	 * print our constants into output file
+	 * ensuring random.c has the same values
+	 */
+	printf("#define INPUT_POOL_WORDS %d\n", INPUT_POOL_WORDS) ; 
+	printf("#define OUTPUT_POOL_WORDS %d\n", OUTPUT_POOL_WORDS) ;
+	printf("#define INPUT_POOL_SHIFT %d\n\n", INPUT_POOL_SHIFT) ; 
+ 
+	/*
+	 * Initialise the pools with random data
+	 * This is done unconditionally
+	 */
+	do_block( TOTAL_POOL_WORDS, "pools" ) ;
+
+#ifdef CONFIG_RANDOM_GCM
+
+#define ARRAY_ROWS	 8			/* 4 pools get 2 constants each    */
+#define ARRAY_WORDS	(4 * ARRAY_ROWS)	/* 32-bit words, 128-bit constants */
+
+/*
+ * If we are using the GCM hash, set up an array of random
+ * constants for it.
+ *
+ * The choice of 32 words (eight 128-bit rows, 1024 bits) for
+ * this is partly arbitrary, partly reasoned. 256 bits would
+ * almost certainly be enough, but 1024 is convenient.
+ *
+ * The AES-GCM hash initialises its accumulator all-zero and uses
+ * a 128-bit multiplier, H. I chose instead to use two constants,
+ * one to initialise the accumulator and one in the role of H.
+ *
+ * This requires that a pair of 128-bit constants be used in each
+ * output operation. I have four pools and chose to give each pool
+ * its own pair instead of using one pair for all pools. I then
+ * chose to initialise all eight with random data.
+ *
+ * Any of those choices might be changed, but all seem reasonable.
+ *
+ * Add an extra 8 words for a counter used in the hashing
+ * 128-bit counter with some extra data for mixing
+ */
+	printf("#define ARRAY_WORDS %d\n\n", ARRAY_WORDS) ;
+
+	do_block( (ARRAY_WORDS + 8), "constants" ) ;
+	printf("static u32 *counter = constants + ARRAY_WORDS ;\n") ;
+
+#endif /* CONFIG_RANDOM_GCM */
+
+	exit(0) ;
+}
+
+/*
+ * each call outputs one array of nwords 32-bit words
+ * with the given array name
+ */
+
+#define PER_LINE 8
+
+void do_block( int nwords, char *name )
+{
+	int nbytes, i, x ;
+	u32 *p, *data ;
+
+	nbytes = 4 * nwords ;
+
+	if( (data = calloc( (size_t) nwords, 4)) == NULL )  {
+		fprintf(stderr, "gen_random_init: calloc() failed, cannot continue\n") ;
+		exit(1) ;
+	}
+
+	/* normal case: we have memory */
+	x = read( urandom, data, nbytes ) ;
+	if( x != nbytes )	{
+		fprintf(stderr,"gen_random_int: read() failed, cannot contiue\n") ;
+                exit(1) ;
+        }
+
+	/*
+	 * Replace any array entries that fail criteria
+	 *
+	 * In theory, the while loop here could run for some
+	 * ridiculously long time, or even go infinite
+	 * In practice, this is astronomically unlikely
+	 * given any sensible definition of accept() and
+	 * input that is anywhere near random
+	 */ 
+	for( i = 0, x = 1, p = data ; x && (i < nwords) ; i++, p++ )	{
+		while( !accept(*p) )
+			x = read( urandom, (char *) p, 4) ;
+        }
+
+        /* output an array of random data */
+        printf("static u32 %s[] = {\n", name ) ;
+	for( i = 0 ; i < nwords ; i ++ )	{
+		printf("0x%08x", data[i]) ;
+		if( i == (nwords-1) )
+			printf( " } ;\n" ) ;
+		else if( (i%PER_LINE) == (PER_LINE-1) )
+			printf( ",\n" ) ;
+		else	printf( ", " ) ;
+	}
+	printf("\n") ;
+	free( data ) ;
+}
+
+void usage()
+{
+	fprintf(stderr, "usage: gen_random_init\n") ;
+	exit(1) ;
+}
+
+/*
+ * These tests are not strictly necessary
+ *
+ * We could just use the /dev/urandom output & take what comes
+ * Arguably, that would be the best course;
+ * "If it ain't broke, don't fix it."
+ *
+ * Applying any bias here makes output somewhat less random,
+ * so easier for an enemy to guess.
+ *
+ * However, a Hamming weight near 16 gives a chance close
+ * to 50/50 that using one of these numbers in arithmetic
+ * (+, xor or various forms of multiplication) will change
+ * any given bit. This is a highly desirable effect.
+ *
+ * Compromise: apply some bias, but not a very strong one
+ */
+
+#define MIN  8
+#define MAX (32-MIN)
+
+int accept( u32 u )
+{
+        int h, i ;
+        char *p ;
+
+        /* reject low or high Hamming weights */
+        h = hamming(u) ;
+        if( ( h < MIN ) || ( h > MAX ) )
+                return(0) ;
+
+        /* at least one 1 and at least one 0 in each byte */
+        for( i = 0, p = (char *) &u ; i < 4 ; i++, p++ )        {
+                switch(*p)      {
+                        case '\0':
+                        case '\255':
+                                return(0) ;
+                        default:
+                                break ;
+                }
+        }
+        return(1) ;
+}
+
+/*
+ * Kernighan's method
+ * http://graphics.stanford.edu/~seander/bithacks.html
+ */
+int hamming( u32 x )
+{
+        int h ;
+        for (h = 0 ; x ; h++)
+          x &= (x-1) ; /* clear the least significant bit set */
+        return(h) ;
+}
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists