[RFC] random: add new pseudorandom number generator

* [RFC] random: add new pseudorandom number generator
@ 2021-09-17  3:18 Sandy Harris
  2021-10-03  0:08 ` [Cryptography] " Jon Callas
  2021-10-04  5:33 ` Tom Mitchell
  0 siblings, 2 replies; 7+ messages in thread
From: Sandy Harris @ 2021-09-17  3:18 UTC (permalink / raw)
  To: Linux Crypto Mailing List, Cryptography, Ted Ts'o

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) ;
}

^ permalink raw reply	[flat|nested] 7+ messages in thread