[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*From*: Sandy Harris <sandyinchina AT gmail.com>*Subject*: [Cryptography] [RFC] random: add new pseudorandom number generator*Date*: Fri, 17 Sep 2021 11:18:35 +0800*List-archive*: <https://www.metzdowd.com/pipermail/cryptography>*Sender*: "cryptography" <cryptography-bounces+ben=bentasker.co.uk AT metzdowd.com>*To*: Linux Crypto Mailing List <linux-crypto AT vger.kernel.org>, Cryptography <cryptography AT metzdowd.com>, "Ted Ts'o" <tytso AT mit.edu>

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) ; } _______________________________________________ The cryptography mailing list cryptography AT metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

- Prev by Date:
**Re: [Cryptography] What ever happened to end-to-end email encryption?** - Next by Date:
**[Cryptography] Membership Drive - Association of Cyber Forensics** - Previous by thread:
**Re: [Cryptography] What ever happened to end-to-end email encryption?** - Next by thread:
**[Cryptography] Membership Drive - Association of Cyber Forensics** - Index(es):