Skip to contentSkip to conversation

getrandom02: relax check for returned data

PATCH New Jan Stancek 3 participants 9 messages Feb 6, 2017 – Feb 8, 2017

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Current check function looks for frequency of returned bytes, which sometimes fail for small buffers, where one byte repeats.

For example, when getrandom() returns 10 bytes, and one byte repeats we fail on this check:

	if (max > 0 && table[i] > max)

This patch is replacing it with more relaxed condition:
if at least one byte is non-zero, we consider it a success.

---
 testcases/kernel/syscalls/getrandom/getrandom02.c | 46 ++++++-----------------
 1 file changed, 12 insertions(+), 34 deletions(-)
testcases/kernel/syscalls/getrandom/getrandom02.c +12 -34
index 0ac8bd28aed0..2b30c7f49f86 100644
@@ -38,14 +38,11 @@ static int modes[] = { 0, GRND_RANDOM, GRND_NONBLOCK,
 int TST_TOTAL = ARRAY_SIZE(modes);
 
 static unsigned char buf[256];
-static size_t size = 256;
-
-static void fill(void);
-static int check_content(int nb);
+int size = sizeof(buf);
 
 int main(int ac, char **av)
 {
-	int lc, i;
+	int lc, i, j, tmp;
 
 	tst_parse_opts(ac, av, NULL, NULL);
 
@@ -53,7 +50,7 @@ int main(int ac, char **av)
 		tst_count = 0;
 
 		for (i = 0; i < TST_TOTAL; i++) {
-			fill();
+			memset(buf, '\0', size);
 
 			do {
 				TEST(ltp_syscall(__NR_getrandom, buf, size,
@@ -61,38 +58,19 @@ int main(int ac, char **av)
 			} while ((modes[i] & GRND_NONBLOCK) && TEST_RETURN == -1
 				&& TEST_ERRNO == EAGAIN);
 
-			if (!check_content(TEST_RETURN))
+			if (TEST_RETURN == -1) {
 				tst_resm(TFAIL | TTERRNO, "getrandom failed");
-			else
+			} else {
 				tst_resm(TPASS, "getrandom returned %ld",
 						TEST_RETURN);
+				tmp = 0;
+				for (j = 0; j < TEST_RETURN; j++)
+					tmp |= buf[j];
+				if (tmp == 0)
+					tst_resm(TWARN, "all bytes from random"
+						" buffer are zero?");
+			}
 		}
 	}
 	tst_exit();
 }
-
-static void fill(void)
-{
-	memset(buf, '\0', sizeof(buf));
-}
-
-static int check_content(int nb)
-{
-	int table[256];
-	int i, index, max;
-
-	memset(table, 0, sizeof(table));
-
-	max = nb * 0.10;
-
-	for (i = 0; i < nb; i++) {
-		index = buf[i];
-		table[index]++;
-	}
-
-	for (i = 0; i < nb; i++) {
-		if (max > 0 && table[i] > max)
-			return 0;
-	}
-	return 1;
-}
Signature · 1 line
1.8.3.1
#1 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Hi!

testcases/kernel/syscalls/getrandom/getrandom02.c int main(int ac, char **av) · line 71

Quoted 9 lines
testcases/kernel/syscalls/getrandom/getrandom02.c +7 -0
+			} else {
 				tst_resm(TPASS, "getrandom returned %ld",
 						TEST_RETURN);
+				tmp = 0;
+				for (j = 0; j < TEST_RETURN; j++)
+					tmp |= buf[j];
+				if (tmp == 0)
+					tst_resm(TWARN, "all bytes from random"
+						" buffer are zero?");

This wouldn't for instance when the random output is filled with non-zero constant bytes...

What about just fixing the max value to something as:

max = 3 + nb * 0.2;

The constat part should handle cases with small buffer and a few repeating characters while for larger buffer it's neglectible.

Signature · 2 lines
Cyril Hrubis
[email protected]
#2 lore raw

PATCH 1/1 getrandom02: relax check for returned data

----- Original Message -----

Quoted 20 lines

From: "Cyril Hrubis" <[email protected]>
To: "Jan Stancek" <[email protected]>
Cc: [email protected]
Sent: Tuesday, 7 February, 2017 4:33:52 PM
Subject: Re: [LTP] [PATCH] getrandom02: relax check for returned data

Hi!

testcases/kernel/syscalls/getrandom/getrandom02.c int main(int ac, char **av) · line 71

Quoted 9 lines
testcases/kernel/syscalls/getrandom/getrandom02.c +7 -0
+			} else {
 				tst_resm(TPASS, "getrandom returned %ld",
 						TEST_RETURN);
+				tmp = 0;
+				for (j = 0; j < TEST_RETURN; j++)
+					tmp |= buf[j];
+				if (tmp == 0)
+					tst_resm(TWARN, "all bytes from random"
+						" buffer are zero?");

This wouldn't for instance when the random output is filled with non-zero constant bytes...

Quoted 6 lines

What about just fixing the max value to something as:

max = 3 + nb * 0.2;

The constat part should handle cases with small buffer and a few repeating characters while for larger buffer it's neglectible.

In that case we may as well skip the check for small buffers. What size would make reasonably large sample? 64?

Quoted 5 lines

--
Cyril Hrubis
[email protected]

#3 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Hi!

Quoted 11 lines
Quoted 9 lines

This wouldn't for instance when the random output is filled with non-zero constant bytes...

What about just fixing the max value to something as:

max = 3 + nb * 0.2;

The constat part should handle cases with small buffer and a few repeating characters while for larger buffer it's neglectible.

In that case we may as well skip the check for small buffers.

The probability of a failure, given that the distribution is random, would be:

256 * {N \choose max} / (256 ^ max)

Since you choose one of the possible 256 byte values, then you have N tries to hit the value, so you choose all possible combinations, each of them has probability 1/(256 ^ max).

I've tried to visualize the data with gnuplot and it looks like the minimal reasonable constant part of the equation is 4, with anything less we got probability of a failure in terms of percents. Bumping it to 4 the maximal probality for a failure is around 10^-5.

With max = 6 + N * 0.2 the maximal probability of a failure for a buffer of a size around 10 is about 10^-13. So I would say that something like this is pretty much safe. This also skips buffers smaller than 7 by default. Or we may get even safer with something as max = 10 * N * 0.1 which has maximal failure probability about 10^-19 and skips buffers up to size of a 11.

Try for youself:

gnuplot> comb(n,k) = gamma(n+1)/(gamma(k+1) * gamma(n - k + 1)) gnuplot> plot [6:30] 256 * comb(x, int(6 + x * 0.2)) / (256 ** int(6 + x * 0.2))

Note that we got series of spikes where each one is much smaller than the previous one (this is because the max is not continous and "hops" every time the x * 0.2 is integer number.

Signature · 2 lines
Cyril Hrubis
[email protected]
#4 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Quoted 11 lines · Cyril Hrubis

Hi!

Quoted 10 lines
Quoted 9 lines

This wouldn't for instance when the random output is filled with non-zero constant bytes...

What about just fixing the max value to something as:

max = 3 + nb * 0.2;

The constat part should handle cases with small buffer and a few repeating characters while for larger buffer it's neglectible.

Quoted 7 lines
Quoted 1 line

In that case we may as well skip the check for small buffers.

The probability of a failure, given that the distribution is random, would be:

256 * {N \choose max} / (256 ^ max)

<snip>

If you're interested in that level of randomness verification (although I would suggest splitting it from the getrandom syscall, so it could test ie. /dev/urandom output as well as both should be internally the same), take a look at rng-tools implementation of some of FIPS-140 at

http://gkernel.cvs.sourceforge.net/viewvc/gkernel/rng-tools/

(fips.c / rngtest.c)

This would AFAIK cover most catastrophic failures of HW RNGs, although on Linux, you're really testing just the CSPRNG,
http://lxr.free-electrons.com/source/drivers/char/random.c

Jiri

#5 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Hi!

Quoted 12 lines
Quoted 5 lines

The probability of a failure, given that the distribution is random, would be:

256 * {N \choose max} / (256 ^ max)

<snip>

If you're interested in that level of randomness verification (although I would suggest splitting it from the getrandom syscall, so it could test ie. /dev/urandom output as well as both should be internally the same), take a look at rng-tools implementation of some of FIPS-140 at

Quoted 7 lines

http://gkernel.cvs.sourceforge.net/viewvc/gkernel/rng-tools/

(fips.c / rngtest.c)

This would AFAIK cover most catastrophic failures of HW RNGs, although on Linux, you're really testing just the CSPRNG,
http://lxr.free-electrons.com/source/drivers/char/random.c

All I strive for for the getrandom test is to have some reasonable verification that the buffer was filled with something that looks at least a bit like random data, so that we rule out cases where the buffer was only partially filled or not filled in at all. The hard part is where to draw the line between the complexity of the check and probability of a failure...

Adding real entropy tests to LTP sounds like a good excercise though, maybe I will have a look into that later :-).

Signature · 2 lines
Cyril Hrubis
[email protected]
#6 lore raw

PATCH 1/1 getrandom02: relax check for returned data

In reply to Cyril Hrubis
Quoted 34 lines · Cyril Hrubis

Hi!

Quoted 11 lines
Quoted 9 lines

This wouldn't for instance when the random output is filled with non-zero constant bytes...

What about just fixing the max value to something as:

max = 3 + nb * 0.2;

The constat part should handle cases with small buffer and a few repeating characters while for larger buffer it's neglectible.

In that case we may as well skip the check for small buffers.

The probability of a failure, given that the distribution is random, would be:

256 * {N \choose max} / (256 ^ max)

Since you choose one of the possible 256 byte values, then you have N tries to hit the value, so you choose all possible combinations, each of them has probability 1/(256 ^ max).

I've tried to visualize the data with gnuplot and it looks like the minimal reasonable constant part of the equation is 4, with anything less we got probability of a failure in terms of percents. Bumping it to 4 the maximal probality for a failure is around 10^-5.

With max = 6 + N * 0.2 the maximal probability of a failure for a buffer of a size around 10 is about 10^-13. So I would say that something like this is pretty much safe. This also skips buffers smaller than 7 by default. Or we may get even safer with something as max = 10 * N * 0.1 which has maximal failure probability about 10^-19 and skips buffers up to size of a 11.

Quoted 4 lines

Try for youself:

gnuplot> comb(n,k) = gamma(n+1)/(gamma(k+1) * gamma(n - k + 1)) gnuplot> plot [6:30] 256 * comb(x, int(6 + x * 0.2)) / (256 ** int(6 + x * 0.2))

This does not look correct to me. Try it with old formula, it goes above 1:
gnuplot> comb(n,k) = gamma(n+1)/(gamma(k+1) * gamma(n - k + 1)) gnuplot> plot [6:30] 256 * comb(x, int(x * 0.1)) / (256 ** int(x * 0.1))

---

With old formula, for N<20 (and max=1), this is pretty much birthday problem [1] with smaller pool - we don't have 365 days, we have 256 bytes.

With birthday problem you get 50% chance of having 2 people with same birthday if number of people is 23. Since we have smaller pool, I'd expect we reach 50% chance sooner.

With N>=20, max increases and it gets a lot more complicated. Best advice I've found online was to use Poisson approximation [2].

Based on that (see attached python snippet) I'm getting that:
"x*0.1" is quite bad, specially for N=19
"6+x*0.2" is a lot better, with chance ~10^-16

I'll send v2, with "6+x*0.2".

Regards,
Jan

[1] https://en.wikipedia.org/wiki/Birthday_problem
[2] http://math.stackexchange.com/questions/25876/probability-of-3-people-in-a-room-of-30-having-the-same-birthday

-------------- next part --------------
A non-text attachment was scrubbed...
Name: birthday_problem.py
Type: text/x-python
Size: 650 bytes
Desc: not available
URL: <http://lists.linux.it/pipermail/ltp/attachments/20170208/b3ca6ad4/attachment.py>

#7 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Hi!

Quoted 6 lines
Quoted 2 lines

gnuplot> comb(n,k) = gamma(n+1)/(gamma(k+1) * gamma(n - k + 1)) gnuplot> plot [6:30] 256 * comb(x, int(6 + x * 0.2)) / (256 ** int(6 + x * 0.2))

This does not look correct to me. Try it with old formula, it goes above 1:
gnuplot> comb(n,k) = gamma(n+1)/(gamma(k+1) * gamma(n - k + 1)) gnuplot> plot [6:30] 256 * comb(x, int(x * 0.1)) / (256 ** int(x * 0.1))

You are right, this would be for if we fail the test test when table[i] >= max, which would fail with 100% probability for most of the smaller buffers, hence we get results that does not make much sense. We have to add 1 to the int(x * 0.1) in the formula.

Try plotting this:

plot [10:60] 256 * comb(x, int(x * 0.1) + 1) / (256 ** (int(x * 0.1) + 1))

which pretty much shows the same you are saying for N=19 the old formula has about 70% chance of failing. Well your script with poisson aproximation gets close to 50% but the order of magnitude seems to be the same for both formulae.

Quoted 9 lines

---

With old formula, for N<20 (and max=1), this is pretty much birthday problem [1] with smaller pool - we don't have 365 days, we have 256 bytes.

With birthday problem you get 50% chance of having 2 people with same birthday if number of people is 23. Since we have smaller pool, I'd expect we reach 50% chance sooner.

Quoted 6 lines

With N>=20, max increases and it gets a lot more complicated. Best advice I've found online was to use Poisson approximation [2].

Based on that (see attached python snippet) I'm getting that:
"x*0.1" is quite bad, specially for N=19
"6+x*0.2" is a lot better, with chance ~10^-16

I'm getting the same with the fixed formula in gnuplot:

plot [10:60] 256 * comb(x, int(6 + x * 0.2) + 1) / (256 ** (int(6 + x * 0.2) + 1))

This shows a peak for 15 which is about ~10^-16.

Quoted 1 line

I'll send v2, with "6+x*0.2".

Agreed.

Signature · 2 lines
Cyril Hrubis
[email protected]
#8 lore raw

PATCH 1/1 getrandom02: relax check for returned data

Hi!

Quoted 9 lines
Quoted 3 lines

Based on that (see attached python snippet) I'm getting that:
"x*0.1" is quite bad, specially for N=19
"6+x*0.2" is a lot better, with chance ~10^-16

I'm getting the same with the fixed formula in gnuplot:

plot [10:60] 256 * comb(x, int(6 + x * 0.2) + 1) / (256 ** (int(6 + x * 0.2) + 1))

This shows a peak for 15 which is about ~10^-16.

^
should have been 14 of course

I was typing faster than thinking again...

Signature · 2 lines
Cyril Hrubis
[email protected]