I have a PRNG that I want to use within the Linux random(4) driver. It looks remarkably strong to me, but analysis from others is needed. (The spinlocks here are a kluge for out-of-kernel testing.) /************************************************************************* * use xtea to create a pseudorandom 64-bit output * * xtea is fast & uses little storage * See https://en.wikipedia.org/wiki/XTEA and papers it links * * tea is the original block cipher, Tiny Encryption Algorithm * xtea is an improved version preventing some published attacks * both are in linux/crypto/tea.c *************************************************************************/ static spinlock_t xtea_lock; /* * The initialisations here may not be needed, but they are * more-or-less free and can do no harm. * constants taken from SHA-512 */ static u64 tea_mask = 0x7137449123ef65cd ; static u64 tea_counter = 0xb5c0fbcfec4d3b2f ; /* * 128-bit key * cipher itself uses 32-bit operations * but rekeying uses 64-bit */ static u64 tea_key64[2] = {0x0fc19dc68b8cd5b5, 0xe9b5dba58189dbbc} ; static u32 *tea_key = (u32 *) &tea_key64[0] ; /* * simplified version of code fron crypto/tea.c * xtea_encrypt(struct crypto_tfm *tfm, u8 *dst, const u8 *src) * * does not use struct * does no endianess conversions * no *src or *dst, encrypt a 64-bit block in place */ #define XTEA_ROUNDS 32 #define XTEA_DELTA 0x9e3779b9 static void xtea_block(u64 *x) { u32 i, y, z, sum, *p ; p = (u32 *) x ; y = p[0] ; z = p[1] ; for( i = 0, sum = 0 ; i < XTEA_ROUNDS ; i++ ) { y += ((z << 4 ^ z >> 5) + z) ^ (sum + tea_key[sum&3]); sum += XTEA_DELTA; z += ((y << 4 ^ y >> 5) + y) ^ (sum + tea_key[sum>>11 &3]); } p[0] = y ; p[1] = z ; } /* * For counter mode see RFC 4086 section 6.2.1 * Add a constant instead of just incrementing * to change more bits * * Even and Mansour proved proved a lower bound * for an XOR-permutation-XOR sequence. * S. Even, Y. Mansour, Asiacrypt 1991 * A Construction of a Cipher From a Single Pseudorandom Permutation * * For an n-bit cipher and D known or chosen plaintexts, * time T to break it is bounded by DT >= 2^n. * * This applies even if the enemy knows the permutation, * for a block cipher even if he or she knows the key. * All the proof requires is that the permutation be * nonlinear. * * Here the main calling function changes the key a bit * on every iteration and updates key, mask and counter * after TEA_REKEY iterations, so any possible D for * the same key, mask and counter sequence is small. * * With TEA_REKEY = 127 ~= 2^7, for each sequence of * 127 outputs between rekeyings the enemy needs * time T > 2^57 * * Assuming proper keying and that the enemy cannot * peek into the running kernel, this can be * considered effectively unbreakable, even if * xtea itself were found to be weak. */ #define COUNTER_DELTA 0x240ca1cc77ac9c65 static u64 xtea_counter() { u64 x ; x = tea_counter ^ tea_mask ; xtea_block(&x) ; x ^= tea_mask ; tea_counter += COUNTER_DELTA ; return x ; } /* * Interval for full rekey can be moderately long * because there is incremental key change as well */ #define TEA_REKEY 127 static int xtea_iterations = 0 ; static void get_xtea_long(u64 *out) { int a ; int flag = 0 ; spin_lock(&xtea_lock) ; if (xtea_iterations >= TEA_REKEY) xtea_iterations = 0 ; if (xtea_iterations == 0) flag = 1 ; spin_unlock(&xtea_lock) ; if (flag) xtea_rekey() ; spin_lock(&xtea_lock) ; a = xtea_iterations & 3 ; tea_key[a] += rol32(tea_key[(a+1)&3], 5) ; *out = xtea_counter() ; xtea_iterations++ ; spin_unlock(&xtea_lock) ; }
