Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
On Sun, Sep 22, 2013 at 09:11:58PM -0700, H. Peter Anvin wrote: > > This doesn't mix in across the entire width of the hash (my original > motivation for putting this at the end was to do it after the hash is > folded in half -- which is still believe is cryptographically dubious, > but please don't take my word for it, as I'm not a professional > cryptographer.) As such, this change should *probably* have > EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply "20") both in the for > loop and in the declaration of the union. Agreed, I'll make the change to "20" instead of EXTRACT_SIZE. As far as whether or not folding the hash is cryptographically dubious, we're not using the hash as part of a digital signature, which is normally where cryptographers get antsy about truncating a cryptographic hash value (since it effectively halves the length of the hash, which thanks to the birthday paradox, makes it much easier to find collisions). However, in this case, we are reducing the amount of information which is available to an attacker to infer the state of the pool. The "Linux Random Pool Revisited" paper had the following to say about it in section 4.3: "In addition, the folding operation helps in avoiding recognizable patterns: the output of the hash function is not directly recognizable from the output data. For an optimal hash function, this step would not be necessary and could be replaced by a simple truncation." If they had thought it was cryptographically dubious, they could have said so --- but they didn't. It's true that if we know for sure that SHA-1 is a perfect one-way hash function (which is believed to be true, although there is no proof of this, and the recent work by Xiaoyun Wang, Yiquin Lisa Yin, and Hungbo Yu does not lead to any evidence for or against SHA-1's status as a one-way function), the folding operation wouldn't be necessary. But the folding operation shouldn't hurt (except for reducing the speed of generating random numbers, and it's currently not a bottleneck), and in the case where it might not be a perfect one-way function, it could help. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
On 09/22/2013 01:38 PM, Theodore Ts'o wrote:
> Previously if CPU chip had a built-in random number generator (i.e.,
> RDRAND on newer x86 chips), we mixed it in at the very end of
> extract_buf() using an XOR operation.
>
> We now mix it in right after the calculate a hash across the entire
> pool. This has the advantage that any contribution of entropy from
> the CPU's HWRNG will get mixed back into the pool. In addition, it
> means that if the HWRNG has any defects (either accidentally or
> maliciously introduced), this will be mitigated via the non-linear
> transform of the SHA-1 hash function before we hand out generated
> output.
>
> Signed-off-by: "Theodore Ts'o"
This doesn't mix in across the entire width of the hash (my original
motivation for putting this at the end was to do it after the hash is
folded in half -- which is still believe is cryptographically dubious,
but please don't take my word for it, as I'm not a professional
cryptographer.) As such, this change should *probably* have
EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply "20") both in the for
loop and in the declaration of the union.
-hpa
> drivers/char/random.c | 22 +++---
> 1 file changed, 11 insertions(+), 11 deletions(-)
>
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index ba23d5c..6d5e8e6 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -993,6 +993,17 @@ static void extract_buf(struct entropy_store *r, __u8
> *out)
> sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
>
> /*
> + * If we have a architectural hardware random number
> + * generator, mix that in, too.
> + */
> + for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
> + unsigned long v;
> + if (!arch_get_random_long())
> + break;
> + hash.l[i] ^= v;
> + }
> +
> + /*
>* 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
> @@ -1021,17 +1032,6 @@ static void extract_buf(struct entropy_store *r, __u8
> *out)
> hash.w[1] ^= hash.w[4];
> hash.w[2] ^= rol32(hash.w[2], 16);
>
> - /*
> - * If we have a architectural hardware random number
> - * generator, mix that in, too.
> - */
> - for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
> - unsigned long v;
> - if (!arch_get_random_long())
> - break;
> - hash.l[i] ^= v;
> - }
> -
> memcpy(out, , EXTRACT_SIZE);
> memset(, 0, sizeof(hash));
> }
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
Previously if CPU chip had a built-in random number generator (i.e.,
RDRAND on newer x86 chips), we mixed it in at the very end of
extract_buf() using an XOR operation.
We now mix it in right after the calculate a hash across the entire
pool. This has the advantage that any contribution of entropy from
the CPU's HWRNG will get mixed back into the pool. In addition, it
means that if the HWRNG has any defects (either accidentally or
maliciously introduced), this will be mitigated via the non-linear
transform of the SHA-1 hash function before we hand out generated
output.
Signed-off-by: "Theodore Ts'o"
---
drivers/char/random.c | 22 +++---
1 file changed, 11 insertions(+), 11 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index ba23d5c..6d5e8e6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -993,6 +993,17 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
/*
+* If we have a architectural hardware random number
+* generator, mix that in, too.
+*/
+ for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
+ unsigned long v;
+ if (!arch_get_random_long())
+ break;
+ hash.l[i] ^= v;
+ }
+
+ /*
* 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
@@ -1021,17 +1032,6 @@ static void extract_buf(struct entropy_store *r, __u8
*out)
hash.w[1] ^= hash.w[4];
hash.w[2] ^= rol32(hash.w[2], 16);
- /*
-* If we have a architectural hardware random number
-* generator, mix that in, too.
-*/
- for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
- unsigned long v;
- if (!arch_get_random_long())
- break;
- hash.l[i] ^= v;
- }
-
memcpy(out, , EXTRACT_SIZE);
memset(, 0, sizeof(hash));
}
--
1.7.12.rc0.22.gcdd159b
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
Previously if CPU chip had a built-in random number generator (i.e.,
RDRAND on newer x86 chips), we mixed it in at the very end of
extract_buf() using an XOR operation.
We now mix it in right after the calculate a hash across the entire
pool. This has the advantage that any contribution of entropy from
the CPU's HWRNG will get mixed back into the pool. In addition, it
means that if the HWRNG has any defects (either accidentally or
maliciously introduced), this will be mitigated via the non-linear
transform of the SHA-1 hash function before we hand out generated
output.
Signed-off-by: Theodore Ts'o ty...@mit.edu
---
drivers/char/random.c | 22 +++---
1 file changed, 11 insertions(+), 11 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index ba23d5c..6d5e8e6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -993,6 +993,17 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
sha_transform(hash.w, (__u8 *)(r-pool + i), workspace);
/*
+* If we have a architectural hardware random number
+* generator, mix that in, too.
+*/
+ for (i = 0; i LONGS(EXTRACT_SIZE); i++) {
+ unsigned long v;
+ if (!arch_get_random_long(v))
+ break;
+ hash.l[i] ^= v;
+ }
+
+ /*
* 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
@@ -1021,17 +1032,6 @@ static void extract_buf(struct entropy_store *r, __u8
*out)
hash.w[1] ^= hash.w[4];
hash.w[2] ^= rol32(hash.w[2], 16);
- /*
-* If we have a architectural hardware random number
-* generator, mix that in, too.
-*/
- for (i = 0; i LONGS(EXTRACT_SIZE); i++) {
- unsigned long v;
- if (!arch_get_random_long(v))
- break;
- hash.l[i] ^= v;
- }
-
memcpy(out, hash, EXTRACT_SIZE);
memset(hash, 0, sizeof(hash));
}
--
1.7.12.rc0.22.gcdd159b
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
On 09/22/2013 01:38 PM, Theodore Ts'o wrote:
Previously if CPU chip had a built-in random number generator (i.e.,
RDRAND on newer x86 chips), we mixed it in at the very end of
extract_buf() using an XOR operation.
We now mix it in right after the calculate a hash across the entire
pool. This has the advantage that any contribution of entropy from
the CPU's HWRNG will get mixed back into the pool. In addition, it
means that if the HWRNG has any defects (either accidentally or
maliciously introduced), this will be mitigated via the non-linear
transform of the SHA-1 hash function before we hand out generated
output.
Signed-off-by: Theodore Ts'o ty...@mit.edu
This doesn't mix in across the entire width of the hash (my original
motivation for putting this at the end was to do it after the hash is
folded in half -- which is still believe is cryptographically dubious,
but please don't take my word for it, as I'm not a professional
cryptographer.) As such, this change should *probably* have
EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply 20) both in the for
loop and in the declaration of the union.
-hpa
drivers/char/random.c | 22 +++---
1 file changed, 11 insertions(+), 11 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index ba23d5c..6d5e8e6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -993,6 +993,17 @@ static void extract_buf(struct entropy_store *r, __u8
*out)
sha_transform(hash.w, (__u8 *)(r-pool + i), workspace);
/*
+ * If we have a architectural hardware random number
+ * generator, mix that in, too.
+ */
+ for (i = 0; i LONGS(EXTRACT_SIZE); i++) {
+ unsigned long v;
+ if (!arch_get_random_long(v))
+ break;
+ hash.l[i] ^= v;
+ }
+
+ /*
* 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
@@ -1021,17 +1032,6 @@ static void extract_buf(struct entropy_store *r, __u8
*out)
hash.w[1] ^= hash.w[4];
hash.w[2] ^= rol32(hash.w[2], 16);
- /*
- * If we have a architectural hardware random number
- * generator, mix that in, too.
- */
- for (i = 0; i LONGS(EXTRACT_SIZE); i++) {
- unsigned long v;
- if (!arch_get_random_long(v))
- break;
- hash.l[i] ^= v;
- }
-
memcpy(out, hash, EXTRACT_SIZE);
memset(hash, 0, sizeof(hash));
}
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
On Sun, Sep 22, 2013 at 09:11:58PM -0700, H. Peter Anvin wrote: This doesn't mix in across the entire width of the hash (my original motivation for putting this at the end was to do it after the hash is folded in half -- which is still believe is cryptographically dubious, but please don't take my word for it, as I'm not a professional cryptographer.) As such, this change should *probably* have EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply 20) both in the for loop and in the declaration of the union. Agreed, I'll make the change to 20 instead of EXTRACT_SIZE. As far as whether or not folding the hash is cryptographically dubious, we're not using the hash as part of a digital signature, which is normally where cryptographers get antsy about truncating a cryptographic hash value (since it effectively halves the length of the hash, which thanks to the birthday paradox, makes it much easier to find collisions). However, in this case, we are reducing the amount of information which is available to an attacker to infer the state of the pool. The Linux Random Pool Revisited paper had the following to say about it in section 4.3: In addition, the folding operation helps in avoiding recognizable patterns: the output of the hash function is not directly recognizable from the output data. For an optimal hash function, this step would not be necessary and could be replaced by a simple truncation. If they had thought it was cryptographically dubious, they could have said so --- but they didn't. It's true that if we know for sure that SHA-1 is a perfect one-way hash function (which is believed to be true, although there is no proof of this, and the recent work by Xiaoyun Wang, Yiquin Lisa Yin, and Hungbo Yu does not lead to any evidence for or against SHA-1's status as a one-way function), the folding operation wouldn't be necessary. But the folding operation shouldn't hurt (except for reducing the speed of generating random numbers, and it's currently not a bottleneck), and in the case where it might not be a perfect one-way function, it could help. - Ted -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
