Initialising random(4)

Initialising random(4)

[Sandy Harris]

[-- Attachment #1: Type: text/plain, Size: 468 bytes --]

This program initialises the pools in random(4) with data from
/dev/urandom on the machine that does the compile. The output is
different every time it runs. This is not necessary in many cases, but
it is cheap, can do no harm, & may block some attacks.

Eventually I'll get around to submitting patches -- add this program
and do some minor fiddling with random.c and the makefile -- but quite
likely not soon, so here's the code in the meanwhile. Comment
solicited.

[-- Attachment #2: gen_random_init.c --]
[-- Type: text/x-csrc, Size: 7891 bytes --]

/*
 * Program to select random numbers for initialising things
 * in the random(4) driver.
 * 
 * This falls well short of the ideal 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, this is easier to do.
 *
 * 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 that is done early enough.
 * This program is then just another layer of a defense in depth.
 * 
 * The program akes one optional single-digit command-line option,
 * how many 512-bit contexts to initialise in addition to the
 * input pool
 *      no option or -0, just the pool
 *      -1, initialise a context for Salsa as well
 *          (useful with current driver)
 *      -2, Salsa context plus a 512-bit hash context
 *          (possibe in future driver)
 *
 * The program:
 *
 *      gets its data from /dev/urandom
 *      produces different output every time it runs
 *      limits the range of Hamming weights
 *      every byte has at least one bit 1, one 0
 *      output formatted as an array declaration
 *      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, ideally using a secure
 * deletion tool such as shred(1) srm(1) or wipe(1). I am
 * not sure which would be best.
 * 
 * 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.
 *
 * Inserting random data at compile time can do no harm and will
 * make some attacks considerably harder. It is not an ideal
 * solution, and not entirely 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, and
 * might even be too much for some attackers. However it clearly
 * will not stop a serious attacker who has access to another copy
 * of the distro or the device; it 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>
#include <string.h>
#include <linux/random.h>


typedef uint32_t u32 ;
/*
 * Configuration information
 */
#define INPUT_POOL_BITS 	4096
#define INPUT_POOL_WORDS	(INPUT_POOL_BITS >> 5)
/*
    for Salsa, SHA3 or another hash
*/
#define CONTEXT_BITS        512
#define CONTEXT_WORDS       (CONTEXT_BITS >> 5)
/*
    large enough for any expected usage
    may not all be used
*/
#define MAX_WORDS           (INPUT_POOL_WORDS + (2*CONTEXT_WORDS))

u32 data[MAX_WORDS] ;

int accept(u32) ;
int hamming(u32);
void usage(void) ;

int urandom ;

int main(int argc, char **argv)
{
	u32 i, x, *p, temp, last, n_contexts, total_words, total_bytes ;
    char *ptr ;
	if( (urandom = open("/dev/urandom", O_RDONLY)) == -1 )  {
		fprintf(stderr, "gen_random: no /dev/urandom, cannot continue\n") ;
		exit(1) ;
	}
	switch(argc)   {        
        case 1:
            /*
                just input pool
            */
            n_contexts = 0 ;
            break ;
        case 2:
            /*
                also some 512-bit contexts
                one for salsa
                maybe another for 512-bit hash
            */
            ptr = argv[1] ;
            ptr++ ;
            n_contexts = atoi( ptr ) ;
            // fprintf( stderr, "n_contexts %d\n", n_contexts ) ;
            break ;
        default:
            usage() ;
            break ;
    }
    if( (n_contexts > 2) || (n_contexts < 0))   {
        fprintf( stderr, "This version of gen_random_init supports only 0, 1 or 2 contexts\n" ) ;
        usage() ;
    }
    total_words = INPUT_POOL_WORDS + (n_contexts*CONTEXT_WORDS) ;
    total_bytes = total_words << 2 ;
	/*
	 * Initialise the pools with random data
	 */
	x = read( urandom, data, total_bytes ) ;
	if( x != total_bytes )	{
		fprintf(stderr,"gen_random_init: big read() failed, cannot continue\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, p = data ; i < total_words ; i++, p++ )	{
		while( !accept(*p) )      {
			x = read( urandom, (char *) &temp, 4) ;
            if( x != 4 )	{
                fprintf(stderr,"gen_random_init: small read() failed, cannot continue\n") ;
                exit(1) ;
            }
            *p ^= temp ;
        }
    }
    /*
        write a file suitable for inclusion
    */
    last = total_words - 1 ;
    printf( "static u32 pools[] = {\n") ;
    for( i = 0, p = data ; i < total_words ; i++, p++ )	{
        printf("0x%08x", *p) ;
        if( i == last )
             printf("\n} ;\n") ;
        else    {
            putchar(',') ;
            switch( i % 8 ) {
                case 7:
                    putchar('\n') ;
                    break ;
                default:
                    putchar(' ') ;
                    break ;
            }
        }
    }
}

void usage()
{
	fprintf(stderr, "usage: gen_random [-<digit>]\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 (number of bits that are 1)
 * near 16 gives using one of these numbers in arithmetic
 * (+, xor or various forms of multiplication) a better
 * chance of changing the output significantly. This is a
 * highly desirable effect.
 *
 * Compromise: apply some bias, but not a very strong one
 */

#define MIN  6
#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) ;
}