lkml.org 
[lkml]   [2022]   [Feb]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] random: use computational hash for entropy extraction
Hi Jason,

On Tue, Feb 01, 2022 at 05:13:42PM +0100, Jason A. Donenfeld wrote:
> This commit replaces the LFSR of mix_pool_bytes() with a straight-
> forward cryptographic hash function, BLAKE2s, which is already in use
> for pool extraction. Universal hashing with a secret seed was considered
> too, something along the lines of <https://eprint.iacr.org/2013/338>,
> but the requirement for a secret seed makes for a chicken & egg problem.
> Instead we go with a formally proven scheme using a computational hash
> function, described in section B.1.8 of <https://eprint.iacr.org/2019/198>.

What this patch does makes sense, but I'm having a hard time seeing how it maps
to the paper cited above. Your code seems to be treating BLAKE2s as an
arbitrary-length PRF, but "Construction 8" in section B.1 of the paper is
working with the raw compression function of a hash function. Can you clarify?

> -/*
> - * Originally, we used a primitive polynomial of degree .poolwords
> - * over GF(2). The taps for various sizes are defined below. They
> - * were chosen to be evenly spaced except for the last tap, which is 1
> - * to get the twisting happening as fast as possible.
> - *

The "Theory of operation" comment at the top of the file needs to be updated
too.

> +static void _extract_entropy(void *buf, size_t nbytes)
> {
> - struct blake2s_state state __aligned(__alignof__(unsigned long));
> - u8 hash[BLAKE2S_HASH_SIZE];
> - unsigned long *salt;
> unsigned long flags;
> -
> - blake2s_init(&state, sizeof(hash));
> -
> - /*
> - * If we have an architectural hardware random number
> - * generator, use it for BLAKE2's salt & personal fields.
> - */
> - for (salt = (unsigned long *)&state.h[4];
> - salt < (unsigned long *)&state.h[8]; ++salt) {
> - unsigned long v;
> - if (!arch_get_random_long(&v))
> - break;
> - *salt ^= v;
> + u8 seed[BLAKE2S_HASH_SIZE], next_key[BLAKE2S_HASH_SIZE];
> + struct {
> + unsigned long rdrand[32 / sizeof(long)];
> + size_t counter;
> + } block;
> + size_t i;
> +
> + for (i = 0; i < ARRAY_SIZE(block.rdrand); ++i) {
> + if (!arch_get_random_long(&block.rdrand[i]))
> + block.rdrand[i] = random_get_entropy();
> }
>
> - /* Generate a hash across the pool */
> spin_lock_irqsave(&input_pool.lock, flags);
> - blake2s_update(&state, (const u8 *)input_pool_data, POOL_BYTES);
> - blake2s_final(&state, hash); /* final zeros out state */
>
> - /*
> - * We mix the hash back into the pool to prevent 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. By
> - * mixing at least a hash worth of hash data back, we make
> - * brute-forcing the feedback as hard as brute-forcing the
> - * hash.
> - */
> - __mix_pool_bytes(hash, sizeof(hash));
> - spin_unlock_irqrestore(&input_pool.lock, flags);
> + /* seed = HASHPRF(last_key, entropy_input) */
> + blake2s_final(&input_pool.hash, seed);
>
> - /* Note that EXTRACT_SIZE is half of hash size here, because above
> - * we've dumped the full length back into mixer. By reducing the
> - * amount that we emit, we retain a level of forward secrecy.
> - */
> - memcpy(out, hash, EXTRACT_SIZE);
> - memzero_explicit(hash, sizeof(hash));
> -}
> + /* next_key = HASHPRF(key, RDRAND || 0) */

In the above comment, 'key' should be 'seed'.

> while (nbytes) {
> - extract_buf(tmp);
> - i = min_t(int, nbytes, EXTRACT_SIZE);
> - memcpy(buf, tmp, i);
> + i = min_t(size_t, nbytes, BLAKE2S_HASH_SIZE);
> + /* output = HASHPRF(key, RDRAND || ++counter) */

Likewise above.

- Eric

\
 
 \ /
  Last update: 2022-02-04 09:47    [W:0.248 / U:0.168 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site