Re: [PATCH 7/7] random: add backtracking protection to the CRNG

[Theodore Ts'o]

On Sun, Jun 26, 2016 at 08:47:53PM +0200, Pavel Machek wrote:
> 
> You are basically trying to turn CRNG into one way hash function here,
> right? Do you have any explanation that it has the required
> properties?

Well, not really.  A CRNG has the property that if you generate a
series of outputs: O_N-1, O_N, O_N+1, etc., knowledge of O_N does not
give you any special knowledge with respect to O_N+1 or O_N-1.

The anti-backtracking protection means that when we generate O_N, we
use O_N+1 to mutate the state used for the CRNG; specifically, we are
XOR'ing O_N+1 into the state.  Now let's suppose that state gets
exposed.  Even if you know O_N, that's not going to let you know
O_N+1, so knowledge of the exposed state post XOR with O_N+1 isn't
going to help you get back the original state.

More generally, if we assume ChaCha20 is secure, that means that you
can't derive the key even if you have known plaintext.  The output of
the CRNG is basically the keystream --- what you have after you XOR
the ciphertext with the plaintext.  If ChaCha20 is secure, knowledge
of large portions of the keystream should not help you determine the
key, which means is why knowledge of O_N-1, O_N, won't help you derive
either (a) the state of CRNG, aka the ChaCha20 key, or (b) O_N+1.

Cheers,

- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 7/7] random: add backtracking protection to the CRNG

[Pavel Machek]

On Mon 2016-06-13 11:48:39, Theodore Ts'o wrote:
> Signed-off-by: Theodore Ts'o 
> ---
>  drivers/char/random.c | 54 
> ++-
>  1 file changed, 49 insertions(+), 5 deletions(-)
> 
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index d640865..963a6a9 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -436,7 +436,8 @@ static int crng_init = 0;
>  #define crng_ready() (likely(crng_init > 0))
>  static void _extract_crng(struct crng_state *crng,
> __u8 out[CHACHA20_BLOCK_SIZE]);
> -static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]);
> +static void _crng_backtrack_protect(struct crng_state *crng,
> + __u8 tmp[CHACHA20_BLOCK_SIZE], int used);
>  static void process_random_ready_list(void);

You can do u8 and u32 in the code, we know we are in kernel.

> +/*
> + * Use the leftover bytes from the CRNG block output (if there is
> + * enough) to mutate the CRNG key to provide backtracking protection.
> + */
> +static void _crng_backtrack_protect(struct crng_state *crng,
> + __u8 tmp[CHACHA20_BLOCK_SIZE], int used)
> +{
> + unsigned long   flags;
> + __u32   *s, *d;
> + int i;
> +
> + used = round_up(used, sizeof(__u32));
> + if (used + CHACHA20_KEY_SIZE > CHACHA20_BLOCK_SIZE) {
> + extract_crng(tmp);
> + used = 0;
> + }
> + spin_lock_irqsave(>lock, flags);
> + s = (__u32 *) [used];
> + d = >state[4];
> + for (i=0; i < 8; i++)
> + *d++ ^= *s++;
> + spin_unlock_irqrestore(>lock, flags);
> +}

You are basically trying to turn CRNG into one way hash function here,
right? Do you have any explanation that it has the required
properties?

Thanks,
Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) 
http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 7/7] random: add backtracking protection to the CRNG

[Theodore Ts'o]

Signed-off-by: Theodore Ts'o 
---
 drivers/char/random.c | 54 ++-
 1 file changed, 49 insertions(+), 5 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d640865..963a6a9 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -436,7 +436,8 @@ static int crng_init = 0;
 #define crng_ready() (likely(crng_init > 0))
 static void _extract_crng(struct crng_state *crng,
  __u8 out[CHACHA20_BLOCK_SIZE]);
-static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]);
+static void _crng_backtrack_protect(struct crng_state *crng,
+   __u8 tmp[CHACHA20_BLOCK_SIZE], int used);
 static void process_random_ready_list(void);
 
 /**
@@ -826,8 +827,11 @@ static void crng_reseed(struct crng_state *crng, struct 
entropy_store *r)
num = extract_entropy(r, , 32, 16, 0);
if (num == 0)
return;
-   } else
+   } else {
_extract_crng(_crng, buf.block);
+   _crng_backtrack_protect(_crng, buf.block,
+   CHACHA20_KEY_SIZE);
+   }
spin_lock_irqsave(_crng.lock, flags);
for (i = 0; i < 8; i++) {
unsigned long   rv;
@@ -889,9 +893,46 @@ static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE])
_extract_crng(crng, out);
 }
 
+/*
+ * Use the leftover bytes from the CRNG block output (if there is
+ * enough) to mutate the CRNG key to provide backtracking protection.
+ */
+static void _crng_backtrack_protect(struct crng_state *crng,
+   __u8 tmp[CHACHA20_BLOCK_SIZE], int used)
+{
+   unsigned long   flags;
+   __u32   *s, *d;
+   int i;
+
+   used = round_up(used, sizeof(__u32));
+   if (used + CHACHA20_KEY_SIZE > CHACHA20_BLOCK_SIZE) {
+   extract_crng(tmp);
+   used = 0;
+   }
+   spin_lock_irqsave(>lock, flags);
+   s = (__u32 *) [used];
+   d = >state[4];
+   for (i=0; i < 8; i++)
+   *d++ ^= *s++;
+   spin_unlock_irqrestore(>lock, flags);
+}
+
+static void crng_backtrack_protect(__u8 tmp[CHACHA20_BLOCK_SIZE], int used)
+{
+   struct crng_state *crng = NULL;
+
+#ifdef CONFIG_NUMA
+   if (crng_node_pool)
+   crng = crng_node_pool[numa_node_id()];
+   if (crng == NULL)
+#endif
+   crng = _crng;
+   _crng_backtrack_protect(crng, tmp, used);
+}
+
 static ssize_t extract_crng_user(void __user *buf, size_t nbytes)
 {
-   ssize_t ret = 0, i;
+   ssize_t ret = 0, i = CHACHA20_BLOCK_SIZE;
__u8 tmp[CHACHA20_BLOCK_SIZE];
int large_request = (nbytes > 256);
 
@@ -916,6 +957,7 @@ static ssize_t extract_crng_user(void __user *buf, size_t 
nbytes)
buf += i;
ret += i;
}
+   crng_backtrack_protect(tmp, i);
 
/* Wipe data just written to memory */
memzero_explicit(tmp, sizeof(tmp));
@@ -1473,8 +1515,10 @@ void get_random_bytes(void *buf, int nbytes)
if (nbytes > 0) {
extract_crng(tmp);
memcpy(buf, tmp, nbytes);
-   memzero_explicit(tmp, nbytes);
-   }
+   crng_backtrack_protect(tmp, nbytes);
+   } else
+   crng_backtrack_protect(tmp, CHACHA20_BLOCK_SIZE);
+   memzero_explicit(tmp, sizeof(tmp));
 }
 EXPORT_SYMBOL(get_random_bytes);
 
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html