[Cryptography] [RFC] random: add new pseudorandom number generator
Sandy Harris
sandyinchina at gmail.com
Thu Sep 16 23:18:35 EDT 2021
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) ;
}
More information about the cryptography
mailing list