From patchwork Sat Nov 7 14:30:41 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sandy Harris X-Patchwork-Id: 7575641 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: X-Original-To: patchwork-linux-crypto@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id E81B2C05C6 for ; Sat, 7 Nov 2015 14:32:16 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id B14E620649 for ; Sat, 7 Nov 2015 14:32:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 6F7D9203F3 for ; Sat, 7 Nov 2015 14:32:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753630AbbKGObL (ORCPT ); Sat, 7 Nov 2015 09:31:11 -0500 Received: from mail-qg0-f52.google.com ([209.85.192.52]:32815 "EHLO mail-qg0-f52.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753455AbbKGOaw (ORCPT ); Sat, 7 Nov 2015 09:30:52 -0500 Received: by qgea14 with SMTP id a14so30599256qge.0; Sat, 07 Nov 2015 06:30:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=ccaOo7SQ9VrzPmEMzBv6rPpZxCIeIzKCmP7geP19I3g=; b=eLeB9cuEuCHoaI3WoxeImOZwZ4CH/BrWoz2UTbei1LpJDz8eVG7ttg0FfsE3niQDAu IEXn+1KQRNFj9d7ga2HFtd5TpFrnuEn6bMuSq2oP+ZHT9actTTuXV9C5mfC7rW32/WPQ WJped7ENC8PbFfzEU0uAf6BSWDn2zNgpQ5Mw2aX31Zfo6GbEg26lxjjkCHf/BOp4lUoE h9wl2xQRnGGMs20VQtt+tUIrQNM/jelR2Ge4mFlrf9PkbVGnwuEkBRM5O1x+cl0kYE8o mNEbIIyPPU23YSXeoBf0M254cszcBaJ3ks1Xr266/ecr8sG+WVxMQvn4aJ0wjkDYcEUF 5rJQ== X-Received: by 10.141.28.76 with SMTP id f73mr19784241qhe.17.1446906650771; Sat, 07 Nov 2015 06:30:50 -0800 (PST) Received: from Sandy-laptop.hitronhub.home (CPE00fc8d085973-CM00fc8d085970.cpe.net.cable.rogers.com. [99.224.153.28]) by smtp.gmail.com with ESMTPSA id d8sm1367697qgd.34.2015.11.07.06.30.49 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 07 Nov 2015 06:30:50 -0800 (PST) From: Sandy Harris To: "Theodore Ts\\'o" , Jason Cooper , "H. Peter Anvin" , John Denker Cc: linux-kernel@vger.kernel.org, linux-crypto@vger.kernel.org Subject: [PATCH 6/7] Produces generated/random_init.h for random driver Date: Sat, 7 Nov 2015 09:30:41 -0500 Message-Id: <1446906642-19372-6-git-send-email-sandyinchina@gmail.com> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1446906642-19372-1-git-send-email-sandyinchina@gmail.com> References: <1446906642-19372-1-git-send-email-sandyinchina@gmail.com> Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org X-Spam-Status: No, score=-6.8 required=5.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, T_DKIM_INVALID, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Signed-off-by: Sandy Harris --- 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 +#include +#include +#include +#include +#include + +/* + * 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) ; +}