secrand.c

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

#define HASH_INIT initmd5
#define HASH_BUFFER_SIZE (kMD5HashSize / 2)
#define HASH_L_DIGEST_SIZE (kMD5HashSize / 4)
#define HASH_L_BLOCK_SIZE  (kMD5BlockSize / 4)
#define HASH_TRANSFORM MD5_Block

#endif

/*
 * For the purposes of better mixing, we use the CRC-32 polynomial as
 * well to make a twisted Generalized Feedback Shift Register
 *
 * (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR generators.  ACM
 * Transactions on Modeling and Computer Simulation 2(3):179-194.
 * Also see M. Matsumoto & Y. Kurita, 1994.  Twisted GFSR generators
 * II.  ACM Transactions on Mdeling and Computer Simulation 4:254-266)
 *
 * Thanks to Colin Plumb for suggesting this.
 * We have not analyzed the resultant polynomial to prove it primitive;
 * in fact it almost certainly isn't.  Nonetheless, the irreducible factors
 * of a random large-degree polynomial over GF(2) are more than large enough
 * that periodicity is not a concern.
 *
 * The input hash is much less sensitive than the output hash.  All that
 * we want of it is that it be a good non-cryptographic hash; i.e. it
 * not produce collisions when fed "random" data of the sort we expect
 * to see.  As long as the pool state differs for different inputs, we
 * have preserved the input entropy and done a good job.  The fact that an
 * intelligent attacker can construct inputs that will produce controlled
 * alterations to the pool's state is not important because we don't
 * consider such inputs to contribute any randomness.
 * The only property we need with respect to them is
 * that the attacker can't increase his/her knowledge of the pool's state.
 * Since all additions are reversible (knowing the final state and the
 * input, you can reconstruct the initial state), if an attacker has
 * any uncertainty about the initial state, he/she can only shuffle that
 * uncertainty about, but never cause any collisions (which would
 * decrease the uncertainty).
 *
 * The chosen system lets the state of the pool be (essentially) the input
 * modulo the generator polymnomial.  Now, for random primitive polynomials,
 * this is a universal class of hash functions, meaning that the chance
 * of a collision is limited by the attacker's knowledge of the generator
 * polynomial, so if it is chosen at random, an attacker can never force
 * a collision.  Here, we use a fixed polynomial, but we *can* assume that
 * ###--> it is unknown to the processes generating the input entropy. <-###
 * Because of this important property, this is a good, collision-resistant
 * hash; hash collisions will occur no more often than chance.
 */

/* There is actually only one of these, globally. */
typedef struct {
	unsigned add_ptr;
	int input_rotate;
	UInt32 pool[POOLWORDS];
} Secrand_BucketType;

#define k_SecrandPrefId 'SR'
#define k_SecrandVersion 1

static Secrand_BucketType g_RandomState;

/*
 * This function adds a number of words into the entropy "pool".
 *
 * The pool is stirred with a primitive polynomial of the appropriate degree,
 * and then twisted.  We twist by three bits at a time because it's
 * cheap to do so and helps slightly in the expected case where the
 * entropy is concentrated in the low-order bits.
 */
#define MASK(x) ((x) & (POOLWORDS-1))	/* Convenient abreviation */
static void Secrand_AddEntropyWords(UInt32 *p, Int16 count)
{
    static UInt32 const twist_table[8] = {
	0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
    unsigned i, j;
    
    i = g_RandomState.add_ptr;
    j = g_RandomState.input_rotate;
    while (count-- > 0) {
	UInt32 x = *p++;
	x = (x << j) | (x >> (32 - j));

	i = MASK(i - 1);
	
	/*
	 * Normally, we add 14 bits of rotation to the pool.
	 * At the beginning of the pool, add an extra 7 bits
	 * rotation, so that successive passes spread the
	 * input bits across the pool evenly.
	 */
	j += 14;
	if (i)
	    j += 7;
	j &= 31;
	
	/*
	 * XOR in the various taps.  Even though logically, we compute
	 * x and then compute y, we read in y then x order because most
	 * caches work slightly better with increasing read addresses.
	 * If a tap is even then we can use the fact that i is even to
	 * avoid a masking operation.  Every polynomial has at least one
	 * even tap, so j is always used.
	 */
	x ^= g_RandomState.pool[MASK(i+TAP1)];
	x ^= g_RandomState.pool[MASK(i+TAP2)];
	x ^= g_RandomState.pool[MASK(i+TAP3)];
	x ^= g_RandomState.pool[MASK(i+TAP4)];
	x ^= g_RandomState.pool[MASK(i+TAP5)];
	x ^= g_RandomState.pool[i];
	g_RandomState.pool[i]  = (x >> 3) ^ twist_table[x & 7];
    }
    g_RandomState.add_ptr = i;
    g_RandomState.input_rotate = j;
}

static void Secrand_AddTickRandomness(void)
{
    UInt32 ticks = TimGetTicks();
    Secrand_AddEntropyWords(&ticks, 1);
}

void Secrand_Init(void)
{
    Int16  version;
    Int16  size = sizeof(g_RandomState);
    
    version = PrefGetAppPreferences(kKeyringCreatorID, k_SecrandPrefId,
				    &g_RandomState, &size, false);

    if (version != k_SecrandVersion || size != sizeof(g_RandomState)) {
	/* We have to initialize g_RandomState ourself.  We don't
	 * initialize the pool, since clearing it would only diminish
	 * entropy.
	 */
	g_RandomState.add_ptr = 0;
	g_RandomState.input_rotate = 0;
    }
    Secrand_AddTickRandomness();
}

/*
 * We store the entropy pool in the application preferences.
 */
void Secrand_Close(void)
{
    PrefSetAppPreferences(kKeyringCreatorID, 
			  k_SecrandPrefId, k_SecrandVersion,
			  &g_RandomState, sizeof(g_RandomState), false);
}


/*
 * This function adds entropy to the entropy "pool" from an event.
 */
void Secrand_AddEventRandomness(EventType *ev)
{
    UInt32 *rand = (UInt32 *) ev;
    Secrand_AddEntropyWords(rand, sizeof(EventType) / sizeof(UInt32));
}

/*
 * This function extracts randomness from the "entropy pool", and
 * returns it in a buffer.
 */
static void Secrand_ExtractEntropy(UInt8 buf[HASH_BUFFER_SIZE])
{
    UInt32 digest[HASH_L_DIGEST_SIZE];
    UInt32 *pool;
    UInt16 i, x;

    /*
     * As we hash the pool, we mix intermediate values of
     * the hash back into the pool.  This eliminates
     * backtracking attacks (where the attacker knows
     * the state of the pool plus the current outputs, and
     * attempts to find previous outputs), unless the hash
     * function can be inverted.
     */
    Secrand_AddTickRandomness();

    pool = g_RandomState.pool;
    x = 0;
    MemMove(digest, HASH_INIT, sizeof(digest));
    while (pool < g_RandomState.pool + POOLWORDS) {
	HASH_TRANSFORM(digest, pool, digest);
	Secrand_AddEntropyWords(&digest[x % HASH_L_DIGEST_SIZE], 1);
	pool += HASH_L_BLOCK_SIZE;
	x += 2;
    }

    /*
     * In case the hash function has some recognizable
     * output pattern, we fold it in half.
     */
    for (i = 0; i < HASH_L_DIGEST_SIZE / 2; i++)
	digest[i] ^= digest[i + HASH_L_DIGEST_SIZE / 2];
    MemMove(buf, digest, HASH_BUFFER_SIZE);
}

/*
 * This function is exported.  It returns 8 bits of
 * strong random bits, suitable for password generation etc.
 */
UInt8 Secrand_GetByte(void)
{
    static UInt8 bitbucket[HASH_BUFFER_SIZE];
    static Int16 used = HASH_BUFFER_SIZE;

    if (used == HASH_BUFFER_SIZE) {
	/* We used up the whole pool, so refresh it.
	 */
	Secrand_ExtractEntropy(bitbucket);
	used = 0;
    }
    return bitbucket[used++];
}