secrand.c

keyring是一种用于保护PALM中关键信息的系统

/* -*- c-file-style: "java"; -*-
 *
 * $Header: /cvsroot/gnukeyring/keyring/secrand.c,v 1.12 2003/10/06 13:21:41 hoenicke Exp $
 *
 * GNU Keyring -- store passwords securely on a handheld
 * Copyright (C) 2001-2003 Jochen Hoenicke <[e-mail]>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/* Parts of this code are taken from the linux random device driver:
 * 
 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  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, and the entire permission notice in its entirety,
 *    including the disclaimer of warranties.
 * 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.
 * 3. The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior
 *    written permission.
 * 
 * ALTERNATIVELY, this product may be distributed under the terms of
 * the GNU Public License, in which case the provisions of the GPL are
 * required INSTEAD OF the above restrictions.  (This clause is
 * necessary due to a potential bad interaction between the GPL and
 * the restrictions contained in a BSD-style copyright.)
 * 
 * THIS SOFTWARE IS PROVIDED ``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.
 */

/*
 * (now, with legal B.S. out of the way.....) 
 * 
 * This routine gathers environmental noise from device drivers, etc.,
 * and returns good random numbers, suitable for cryptographic use.
 * Besides the obvious cryptographic uses, these numbers are also good
 * for seeding TCP sequence numbers, and other places where it is
 * desirable to have numbers which are not only random, but hard to
 * predict by an attacker.
 *
 * Theory of operation
 * ===================
 * 
 * Computers are very predictable devices.  Hence it is extremely hard
 * to produce truly random numbers on a computer --- as opposed to
 * pseudo-random numbers, which can easily generated by using a
 * algorithm.  Unfortunately, it is very easy for attackers to guess
 * the sequence of pseudo-random number generators, and for some
 * applications this is not acceptable.  So instead, we must try to
 * gather "environmental noise" from the computer's environment, which
 * must be hard for outside attackers to observe, and use that to
 * generate random numbers.  In a Unix environment, this is best done
 * from inside the kernel.
 * 
 * Sources of randomness from the environment include inter-keyboard
 * timings, inter-interrupt timings from some interrupts, and other
 * events which are both (a) non-deterministic and (b) hard for an
 * outside observer to measure.  Randomness from these sources are
 * added to an "entropy pool", which is mixed using a CRC-like function.
 * This is not cryptographically strong, but it is adequate assuming
 * the randomness is not chosen maliciously, and it is fast enough that
 * the overhead of doing it on every interrupt is very reasonable.
 * As random bytes are mixed into the entropy pool, the routines keep
 * an *estimate* of how many bits of randomness have been stored into
 * the random number generator's internal state.
 * 
 * When random bytes are desired, they are obtained by taking the SHA
 * hash of the contents of the "entropy pool".  The SHA hash avoids
 * exposing the internal state of the entropy pool.  It is believed to
 * be computationally infeasible to derive any useful information
 * about the input of SHA from its output.  Even if it is possible to
 * analyze SHA in some clever way, as long as the amount of data
 * returned from the generator is less than the inherent entropy in
 * the pool, the output data is totally unpredictable.  For this
 * reason, the routine decreases its internal estimate of how many
 * bits of "true randomness" are contained in the entropy pool as it
 * outputs random numbers.
 * 
 * If this estimate goes to zero, the routine can still generate
 * random numbers; however, an attacker may (at least in theory) be
 * able to infer the future output of the generator from prior
 * outputs.  This requires successful cryptanalysis of SHA, which is
 * not believed to be feasible, but there is a remote possibility.
 * Nonetheless, these numbers should be useful for the vast majority
 * of purposes.
 * 
 * Acknowledgements:
 * =================
 *
 * Ideas for constructing this random number generator were derived
 * from Pretty Good Privacy's random number generator, and from private
 * discussions with Phil Karn.  Colin Plumb provided a faster random
 * number generator, which speed up the mixing function of the entropy
 * pool, taken from PGPfone.  Dale Worley has also contributed many
 * useful ideas and suggestions to improve this driver.
 * 
 * Any flaws in the design are solely my responsibility, and should
 * not be attributed to the Phil, Colin, or any of authors of PGP.
 * 
 * The code for SHA transform was taken from Peter Gutmann's
 * implementation, which has been placed in the public domain.
 * The code for MD5 transform was taken from Colin Plumb's
 * implementation, which has been placed in the public domain.  The
 * MD5 cryptographic checksum was devised by Ronald Rivest, and is
 * documented in RFC 1321, "The MD5 Message Digest Algorithm".
 * 
 * Further background information on this topic may be obtained from
 * RFC 1750, "Randomness Recommendations for Security", by Donald
 * Eastlake, Steve Crocker, and Jeff Schiller.
 */

#include "includes.h"

/*
 * Configuration information
 */

#define USE_SHA
#define POOLWORDS 64    /* Power of 2 - note that this is 32-bit words */
#define POOLBITS (POOLWORDS*32)

/*
 * The pool is stirred with a primitive polynomial of degree POOLWORDS
 * over GF(2).  The taps for various sizes are defined below.  They are
 * chosen to be evenly spaced (minimum RMS distance from evenly spaced;
 * the numbers in the comments are a scaled squared error sum) except
 * for the last tap, which is 1 to get the twisting happening as fast
 * as possible.
 */
#if POOLWORDS == 2048	/* 115 x^2048+x^1638+x^1231+x^819+x^411+x^1+1 */
#define TAP1	1638
#define TAP2	1231
#define TAP3	819
#define TAP4	411
#define TAP5	1
#elif POOLWORDS == 1024	/* 290 x^1024+x^817+x^615+x^412+x^204+x^1+1 */
/* Alt: 115 x^1024+x^819+x^616+x^410+x^207+x^2+1 */
#define TAP1	817
#define TAP2	615
#define TAP3	412
#define TAP4	204
#define TAP5	1
#elif POOLWORDS == 512	/* 225 x^512+x^411+x^308+x^208+x^104+x+1 */
/* Alt: 95 x^512+x^409+x^307+x^206+x^102+x^2+1
 *      95 x^512+x^409+x^309+x^205+x^103+x^2+1 */
#define TAP1	411
#define TAP2	308
#define TAP3	208
#define TAP4	104
#define TAP5	1
#elif POOLWORDS == 256	/* 125 x^256+x^205+x^155+x^101+x^52+x+1 */
#define TAP1	205
#define TAP2	155
#define TAP3	101
#define TAP4	52
#define TAP5	1
#elif POOLWORDS == 128	/* 105 x^128+x^103+x^76+x^51+x^25+x+1 */
/* Alt: 70 x^128+x^103+x^78+x^51+x^27+x^2+1 */
#define TAP1	103
#define TAP2	76
#define TAP3	51
#define TAP4	25
#define TAP5	1
#elif POOLWORDS == 64	/* 15 x^64+x^52+x^39+x^26+x^14+x+1 */
#define TAP1	52
#define TAP2	39
#define TAP3	26
#define TAP4	14
#define TAP5	1
#elif POOLWORDS == 32	/* 15 x^32+x^26+x^20+x^14+x^7+x^1+1 */
#define TAP1	26
#define TAP2	20
#define TAP3	14
#define TAP4	7
#define TAP5	1
#elif POOLWORDS & (POOLWORDS-1)
#error POOLWORDS must be a power of 2
#else
#error No primitive polynomial available for chosen POOLWORDS
#endif


#ifdef USE_SHA

#define HASH_INIT initsha1
#define HASH_BUFFER_SIZE (kSHA1HashSize / 2)
#define HASH_L_DIGEST_SIZE (kSHA1HashSize / 4)
#define HASH_L_BLOCK_SIZE  (kSHA1BlockSize / 4)
#define HASH_TRANSFORM SHA1_Block

#else /* !USE_SHA - Use MD5 */