[1/2] ath9k: change entropy formula for easier understanding

Commit Message

Miaoqing Pan Aug. 9, 2016, 7:02 a.m. UTC

From: Miaoqing Pan <[e-mail]>

The quality of ADC entropy is 10 bits of min-entropy for
a 32-bit value, change '(((x) * 8 * 320) >> 10)' to
'(((x) * 8 * 10) >> 5)' for easier understanding.

Signed-off-by: Miaoqing Pan <[e-mail]>
---
 drivers/net/wireless/ath/ath9k/rng.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Comments

Stephan Mueller Aug. 10, 2016, 6:25 a.m. UTC | #1

Am Mittwoch, 10. August 2016, 06:04:32 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> FIPS RNG test is supposed to be run on the output of an RNG, and not on the
> RNG entropy source. It is not surprising that the RNG input fails the
> entropy tests from NIST. Check the following example.
> 
> Imagine you have a perfectly random sequence, a_1, a_2, .., a_n, where each
> a_i is a byte. And imagine, this sequence passes all randomness tests.
> 
> Now, let's say I create a new sequence a_1, 0, a_2, 0, a_3, 0, ..., 0, a_n,
> where each zero is a byte
> 
> If you give this sequence (as an entropy source) to a randomness test, it
> will fail most of the tests, if not all. This does not mean this sequence
> is not appropriate as an entropy source, it just means we need twice more
> bytes to gain the same amount of entropy.

Agreed. But that is a very simplistic view.
> 
> I can give this 2n byte sequence to an RNG as an entropy source and it
> provides the same amount of security as if I give the n byte stream.

Well, I am working with standards bodies like NIST and BSI on RNG 
assessments. They all require that the noise source (pre-whitening, of 
course) pass statistical tests like the AIS20 tests, SP800-22 and similar. If 
you fail, you better have a good argument.

And the only argument that is kind of allowed is that you oversample your 
noise source to seed a DRNG from (i.e. have an entropy to data ratio of 
significantly below 1). And the argument for the oversampling rate is always 
a very interesting discussion. You apply 10/32. In private, I am wondering 
about that ratio, but this should not be discussed here as I hope you have a 
valid argument for that.

As we are talking about the current rngd, we have to consider that it does 
*not* perform an oversampling (yet) as mentioned in the previous emails.

Do not get me wrong on my initial patch: your RNG may provide some entropy. 
But there are quite some folks who want to understand and audit a noise 
source before using it. Your current implementation simply does not allow 
switching the noise source off to feed the input_pool with data that 
increases the entropy estimator (at runtime).

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

miaoqing pan Aug. 10, 2016, 6:46 a.m. UTC | #2

Hi Stephan,

Would you please provide a recent NIST document which asks the entropy source to pass the NIST randomness tests ?

Thanks,
Miaoqing

-----Original Message-----
From: Stephan Mueller [mailto:[e-mail]] 
Sent: Wednesday, August 10, 2016 2:25 PM
To: Pan, Miaoqing <[e-mail]>
Cc: Herbert Xu <[e-mail]>; Matt Mackall <[e-mail]>; [e-mail]; Valo, Kalle <[e-mail]>; [e-mail]; ath9k-devel <[e-mail]>; [e-mail]; [e-mail]; Sepehrdad, Pouyan <[e-mail]>
Subject: Re: [PATCH 2/2] ath9k: disable RNG by default

Am Mittwoch, 10. August 2016, 06:04:32 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> FIPS RNG test is supposed to be run on the output of an RNG, and not 
> on the RNG entropy source. It is not surprising that the RNG input 
> fails the entropy tests from NIST. Check the following example.
> 
> Imagine you have a perfectly random sequence, a_1, a_2, .., a_n, where 
> each a_i is a byte. And imagine, this sequence passes all randomness tests.
> 
> Now, let's say I create a new sequence a_1, 0, a_2, 0, a_3, 0, ..., 0, 
> a_n, where each zero is a byte
> 
> If you give this sequence (as an entropy source) to a randomness test, 
> it will fail most of the tests, if not all. This does not mean this 
> sequence is not appropriate as an entropy source, it just means we 
> need twice more bytes to gain the same amount of entropy.

Agreed. But that is a very simplistic view.
> 
> I can give this 2n byte sequence to an RNG as an entropy source and it 
> provides the same amount of security as if I give the n byte stream.

Well, I am working with standards bodies like NIST and BSI on RNG assessments. They all require that the noise source (pre-whitening, of
course) pass statistical tests like the AIS20 tests, SP800-22 and similar. If you fail, you better have a good argument.

And the only argument that is kind of allowed is that you oversample your noise source to seed a DRNG from (i.e. have an entropy to data ratio of significantly below 1). And the argument for the oversampling rate is always a very interesting discussion. You apply 10/32. In private, I am wondering about that ratio, but this should not be discussed here as I hope you have a valid argument for that.

As we are talking about the current rngd, we have to consider that it does
*not* perform an oversampling (yet) as mentioned in the previous emails.

Do not get me wrong on my initial patch: your RNG may provide some entropy. 
But there are quite some folks who want to understand and audit a noise source before using it. Your current implementation simply does not allow switching the noise source off to feed the input_pool with data that increases the entropy estimator (at runtime).

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Stephan Mueller Aug. 10, 2016, 6:51 a.m. UTC | #3

Am Mittwoch, 10. August 2016, 06:46:31 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> Would you please provide a recent NIST document which asks the entropy
> source to pass the NIST randomness tests ?

See FIPS 140-2 IG 7.15 which explicitly references SP800-22.

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

miaoqing pan Aug. 10, 2016, 7:15 a.m. UTC | #4

Hi Stephan,

NIST SP 800-22-rev1a and NIST SP 800-90B are used together to evaluate the amount of min entropy the source provides, and not to decide if the source has passed the tests or failed. See

https://github.com/usnistgov/SP800-90B_EntropyAssessment

The goal is often to make sure the input entropy is more than the entropy we expect from the output.

Thanks,
Miaoqing

-----Original Message-----
From: Stephan Mueller [mailto:[e-mail]] 
Sent: Wednesday, August 10, 2016 2:52 PM
To: Pan, Miaoqing <[e-mail]>
Cc: Herbert Xu <[e-mail]>; Matt Mackall <[e-mail]>; [e-mail]; Valo, Kalle <[e-mail]>; [e-mail]; ath9k-devel <[e-mail]>; [e-mail]; [e-mail]; Sepehrdad, Pouyan <[e-mail]>
Subject: Re: [PATCH 2/2] ath9k: disable RNG by default

Am Mittwoch, 10. August 2016, 06:46:31 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> Would you please provide a recent NIST document which asks the entropy 
> source to pass the NIST randomness tests ?

See FIPS 140-2 IG 7.15 which explicitly references SP800-22.

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Stephan Mueller Aug. 10, 2016, 7:27 a.m. UTC | #5

Am Mittwoch, 10. August 2016, 07:15:49 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> NIST SP 800-22-rev1a and NIST SP 800-90B are used together to evaluate the
> amount of min entropy the source provides, and not to decide if the source
> has passed the tests or failed. See
> 
> https://github.com/usnistgov/SP800-90B_EntropyAssessment
> 
> The goal is often to make sure the input entropy is more than the entropy we
> expect from the output.

You are correct on the SP800-90B tests (hence I did not refer to them for the 
binary decision). Yet, SP800-22 with the associated tool delivers a binary 
decision.

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

miaoqing pan Aug. 10, 2016, 7:40 a.m. UTC | #6

Hi Stephan,

That is set as "optional but highly recommended" in the FIPS doc, plus the fact that we do not have a requirement to have a FIP-approved RNG in our case. Although FIPS might impose higher and stronger requirements on the source of entropy, but not passing those tests does not mean the source of entropy is of bad quality. As I mentioned earlier, we just need to evaluate the amount of entropy it provides correctly and use it accordingly. If we are dealing with a chip which has a HW RNG, we expect extremely high entropy close to full from our source, but this patch is for chips which do not have a dedicated HW RNG in place to improve the quality of random number generation on the platform.

Thanks,
Miaoqing

-----Original Message-----
From: Stephan Mueller [mailto:[e-mail]] 
Sent: Wednesday, August 10, 2016 3:27 PM
To: Pan, Miaoqing <[e-mail]>
Cc: Herbert Xu <[e-mail]>; Matt Mackall <[e-mail]>; [e-mail]; Valo, Kalle <[e-mail]>; [e-mail]; ath9k-devel <[e-mail]>; [e-mail]; [e-mail]; Sepehrdad, Pouyan <[e-mail]>
Subject: Re: [PATCH 2/2] ath9k: disable RNG by default

Am Mittwoch, 10. August 2016, 07:15:49 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> NIST SP 800-22-rev1a and NIST SP 800-90B are used together to evaluate 
> the amount of min entropy the source provides, and not to decide if 
> the source has passed the tests or failed. See
> 
> https://github.com/usnistgov/SP800-90B_EntropyAssessment
> 
> The goal is often to make sure the input entropy is more than the 
> entropy we expect from the output.

You are correct on the SP800-90B tests (hence I did not refer to them for the binary decision). Yet, SP800-22 with the associated tool delivers a binary decision.

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

miaoqing pan Aug. 10, 2016, 7:43 a.m. UTC | #7

Hi Stephan,

The problem with using the add_device_randomness is that we do not know when to call that API, and we have to make our solution either timer-based or interrupt based, which is not really the correct way of implementing this feature.

Thanks,
Miaoqing

-----Original Message-----
From: Pan, Miaoqing 
Sent: Wednesday, August 10, 2016 3:41 PM
To: Stephan Mueller <[e-mail]>
Cc: Herbert Xu <[e-mail]>; Matt Mackall <[e-mail]>; [e-mail]; Valo, Kalle <[e-mail]>; [e-mail]; ath9k-devel <[e-mail]>; [e-mail]; [e-mail]; Sepehrdad, Pouyan <[e-mail]>
Subject: RE: [PATCH 2/2] ath9k: disable RNG by default

Hi Stephan,

That is set as "optional but highly recommended" in the FIPS doc, plus the fact that we do not have a requirement to have a FIP-approved RNG in our case. Although FIPS might impose higher and stronger requirements on the source of entropy, but not passing those tests does not mean the source of entropy is of bad quality. As I mentioned earlier, we just need to evaluate the amount of entropy it provides correctly and use it accordingly. If we are dealing with a chip which has a HW RNG, we expect extremely high entropy close to full from our source, but this patch is for chips which do not have a dedicated HW RNG in place to improve the quality of random number generation on the platform.

Thanks,
Miaoqing

-----Original Message-----
From: Stephan Mueller [mailto:[e-mail]]
Sent: Wednesday, August 10, 2016 3:27 PM
To: Pan, Miaoqing <[e-mail]>
Cc: Herbert Xu <[e-mail]>; Matt Mackall <[e-mail]>; [e-mail]; Valo, Kalle <[e-mail]>; [e-mail]; ath9k-devel <[e-mail]>; [e-mail]; [e-mail]; Sepehrdad, Pouyan <[e-mail]>
Subject: Re: [PATCH 2/2] ath9k: disable RNG by default

Am Mittwoch, 10. August 2016, 07:15:49 CEST schrieb Pan, Miaoqing:

Hi Miaoqing,

> Hi Stephan,
> 
> NIST SP 800-22-rev1a and NIST SP 800-90B are used together to evaluate 
> the amount of min entropy the source provides, and not to decide if 
> the source has passed the tests or failed. See
> 
> https://github.com/usnistgov/SP800-90B_EntropyAssessment
> 
> The goal is often to make sure the input entropy is more than the 
> entropy we expect from the output.

You are correct on the SP800-90B tests (hence I did not refer to them for the binary decision). Yet, SP800-22 with the associated tool delivers a binary decision.

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Jason Cooper Aug. 10, 2016, 1:24 p.m. UTC | #8

Hi Miaoqing Pan, Stephen,

*gentle reminder: others are reading which may not be directly included
in the conversation.  Including the archives.  Please avoid top posting.
:)

On Wed, Aug 10, 2016 at 07:43:45AM +0000, Pan, Miaoqing wrote:
> The problem with using the add_device_randomness is that we do not
> know when to call that API, and we have to make our solution either
> timer-based or interrupt based, which is not really the correct way of
> implementing this feature.

Exactly.  I think we're dancing around the problem by discussing the
quality of what the ath9k adc provides.

The fact is, barring userspace expectations of /dev/hwrng, hw_random is
the appropriate place for it.  It's not a devicetree blob, mac address,
or pci config space.  Which are things we feed in once for the heck of
it.  This is a *continuous* source or questionable quality.

I'm seriously considering putting this and timeriomem-rng into a
subdirectory under hw_random/, maybe environ/.  Anything in there gets
quality=0 for default, and *doesn't* contribute to /dev/hwrng.

Regardless which path we take, I think we should include 'adc' in the
name.  I've heard countless times about "Atheros cards come with an rng
on board". :-/

thx,

Jason.
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Miaoqing Pan Aug. 11, 2016, 2:54 a.m. UTC | #9

Hi Jason,

On 2016-08-10 21:24, Jason Cooper wrote:
> *gentle reminder: others are reading which may not be directly included
> in the conversation.  Including the archives.  Please avoid top 
> posting.
> :)

Thanks:)

> The fact is, barring userspace expectations of /dev/hwrng, hw_random is
> the appropriate place for it.  It's not a devicetree blob, mac address,
> or pci config space.  Which are things we feed in once for the heck of
> it.  This is a *continuous* source or questionable quality.
> 
> I'm seriously considering putting this and timeriomem-rng into a
> subdirectory under hw_random/, maybe environ/.  Anything in there gets
> quality=0 for default, and *doesn't* contribute to /dev/hwrng.
> 
> Regardless which path we take, I think we should include 'adc' in the
> name.  I've heard countless times about "Atheros cards come with an rng
> on board". :-/

If I understand correctly, you want to bind the ADC source to 
/dev/hwrng,
and then change rng-tools to set the entropy to zero in the ioctl call ?
There are two major problems with that approach,

1) We already tried once before to bind our solution to /dev/hwrng, and 
got
so much complaints. The conclusion was that maybe we know that the 
output of
/dev/hwrng does not have perfect entropy, but a normal user does not 
know and
will misuse it. You mentioned in 
https://www.kernel.org/doc/Documentation/hw_random.txt
we have

"This data is NOT CHECKED by any
	fitness tests, and could potentially be bogus (if the
	hardware is faulty or has been tampered with).  Data is only
	output if the hardware "has-data" flag is set, but nevertheless
	a security-conscious person would run fitness tests on the
	data before assuming it is truly random."

But this is not enough to convince upstream to switch to /dev/hwrng. I 
think the
concern of users misusing the solution is a very valid concern.

2) If we set the entropy to zero in rng-tools, we cannot tolerate the 
load.
Rng-tools is not a timer-based solution. Similar to our solution, it is 
based on
/proc/sys/kernel/random/write_wakeup_threshold. If we do not increase 
the entropy
counter, rng-tools keep writing into the pool, and both rng-tools and 
WiFi chip will
be overloaded.


Thanks,
Miaoqing
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Jason Cooper Aug. 11, 2016, 1:14 p.m. UTC | #10

On Thu, Aug 11, 2016 at 10:54:11AM +0800, [e-mail] wrote:
> On 2016-08-10 21:24, Jason Cooper wrote:
> >The fact is, barring userspace expectations of /dev/hwrng, hw_random is
> >the appropriate place for it.  It's not a devicetree blob, mac address,
> >or pci config space.  Which are things we feed in once for the heck of
> >it.  This is a *continuous* source or questionable quality.
> >
> >I'm seriously considering putting this and timeriomem-rng into a
> >subdirectory under hw_random/, maybe environ/.  Anything in there gets
> >quality=0 for default, and *doesn't* contribute to /dev/hwrng.
> >
> >Regardless which path we take, I think we should include 'adc' in the
> >name.  I've heard countless times about "Atheros cards come with an rng
> >on board". :-/
> 
> If I understand correctly, you want to bind the ADC source to
> /dev/hwrng, and then change rng-tools to set the entropy to zero in
> the ioctl call ?  There are two major problems with that approach,

Nope.  I want to leverage the hwrng framework to facilitate feeding the
*kernel* entropy pools like all the other hwrngs do currently.  The
difference for *environmental* sources is that when userspace read()s
from /dev/hwrng, they will *not* contribute.

If the environmental sources are the only sources, then no /dev/hwrng
should appear.

> 1) We already tried once before to bind our solution to /dev/hwrng,
> and got so much complaints. The conclusion was that maybe we know that
> the output of /dev/hwrng does not have perfect entropy, but a normal
> user does not know and will misuse it. You mentioned in
> https://www.kernel.org/doc/Documentation/hw_random.txt we have
> 
> "This data is NOT CHECKED by any
> 	fitness tests, and could potentially be bogus (if the
> 	hardware is faulty or has been tampered with).  Data is only
> 	output if the hardware "has-data" flag is set, but nevertheless
> 	a security-conscious person would run fitness tests on the
> 	data before assuming it is truly random."
> 
> But this is not enough to convince upstream to switch to /dev/hwrng.
> I think the concern of users misusing the solution is a very valid
> concern.

Agreed.

> 2) If we set the entropy to zero in rng-tools, we cannot tolerate the
> load.  Rng-tools is not a timer-based solution. Similar to our
> solution, it is based on
> /proc/sys/kernel/random/write_wakeup_threshold. If we do not increase
> the entropy counter, rng-tools keep writing into the pool, and both
> rng-tools and WiFi chip will be overloaded.

That's why I propose a change to the hwrng framework to permit noise
sources while not wiring them up to feed /dev/hwrng.  timeriomem-rng
should have the same problem ath9k-rng does.

Basically, if it wasn't designed to be an rng, it shouldn't be wired up
to /dev/hwrng.

thx,

Jason.
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Kalle Valo Sept. 27, 2016, 2:53 p.m. UTC | #11

miaoqing pan <[e-mail]> wrote:
> From: Miaoqing Pan <[e-mail]>
> 
> The quality of ADC entropy is 10 bits of min-entropy for
> a 32-bit value, change '(((x) * 8 * 320) >> 10)' to
> '(((x) * 8 * 10) >> 5)' for easier understanding.
> 
> Signed-off-by: Miaoqing Pan <[e-mail]>

I need some help here, it this patch ok to take or should I drop it? The
discussion is available from the patchwork link below if someone needs to
refresh the memory.

Kalle Valo Oct. 13, 2016, 2:23 p.m. UTC | #12

miaoqing pan <[e-mail]> wrote:
> From: Miaoqing Pan <[e-mail]>
> 
> The quality of ADC entropy is 10 bits of min-entropy for
> a 32-bit value, change '(((x) * 8 * 320) >> 10)' to
> '(((x) * 8 * 10) >> 5)' for easier understanding.
> 
> Signed-off-by: Miaoqing Pan <[e-mail]>

Patch applied to ath-next branch of ath.git, thanks.

e463139a7262 ath9k: change entropy formula for easier understanding

Patch

diff --git a/drivers/net/wireless/ath/ath9k/rng.c b/drivers/net/wireless/ath/ath9k/rng.c
index d38e50f..568b1c6 100644
--- a/drivers/net/wireless/ath/ath9k/rng.c
+++ b/drivers/net/wireless/ath/ath9k/rng.c
@@ -22,7 +22,7 @@ 
 #include "ar9003_phy.h"
 
 #define ATH9K_RNG_BUF_SIZE	320
-#define ATH9K_RNG_ENTROPY(x)	(((x) * 8 * 320) >> 10) /* quality: 320/1024 */
+#define ATH9K_RNG_ENTROPY(x)	(((x) * 8 * 10) >> 5) /* quality: 10/32 */
 
 static int ath9k_rng_data_read(struct ath_softc *sc, u32 *buf, u32 buf_size)
 {