: fix repetition test for hardware RNG to be FIPS compliant

PATCH In review Neil Horman 3 participants 5 messages Sep 12, 2009 – Sep 15, 2009

Subsystems (2)

Crypto API Random number driver

lore

Share & tools

lore

Neil Horman

author

2009-09-12 16:44 UTC #0 lore raw

PATCH 1/1 : fix repetition test for hardware RNG to be FIPS compliant

Hey all-
A while back I implemented a repetition check in the hardware RNG to
make it FIPS compliant. It was just pointed out to me that there was an item in the requirement that I missed. Namely, when operating in FIPS mode, the RNG should save the first n bit block that it produces for use in the repetition check, but not return it to the caller (opting instead to return the next n bit block which passes the repetiiton check instead. This patch corrects that.

Neil

Signed-off-by Neil Horman <[email protected]>

 random.c |   27 ++++++++++++++++++++-------
 1 file changed, 20 insertions(+), 7 deletions(-)

drivers/char/random.c +20 -7

index d8a9255..6700248 100644
@@ -399,6 +399,12 @@ module_param(debug, bool, 0644);
  * storing entropy in an entropy pool.
  *
  **********************************************************************/
+#define EXTRACT_SIZE 10
+#define REP_CHECK_BLOCK_COPIED 1
+struct repetition_check {
+	__u8 last_data[EXTRACT_SIZE];
+	__u8 flags;
+};
 
 struct entropy_store;
 struct entropy_store {

@@ -414,7 +420,7 @@ struct entropy_store {
 	unsigned add_ptr;
 	int entropy_count;
 	int input_rotate;
-	__u8 *last_data;
+	struct repetition_check *rep;
 };
 
 static __u32 input_pool_data[INPUT_POOL_WORDS];

@@ -714,7 +720,6 @@ void add_disk_randomness(struct gendisk *disk)
 }
 #endif
 
-#define EXTRACT_SIZE 10
 
 /*********************************************************************
  *

@@ -856,18 +861,24 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
 
+repeat_extract:
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
 	while (nbytes) {
 		extract_buf(r, tmp);
 
-		if (r->last_data) {
+		if (r->rep) {
 			spin_lock_irqsave(&r->lock, flags);
-			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
+			if ((r->rep->flags & REP_CHECK_BLOCK_COPIED) &&
+			    !memcmp(tmp, r->rep->last_data, EXTRACT_SIZE))
 				panic("Hardware RNG duplicated output!\n");
-			memcpy(r->last_data, tmp, EXTRACT_SIZE);
+			memcpy(r->rep->last_data, tmp, EXTRACT_SIZE);
 			spin_unlock_irqrestore(&r->lock, flags);
+			if (!(r->rep->flags & REP_CHECK_BLOCK_COPIED)) {
+				r->rep->flags |= REP_CHECK_BLOCK_COPIED;
+				goto repeat_extract;
+			}
 		}
 		i = min_t(int, nbytes, EXTRACT_SIZE);
 		memcpy(buf, tmp, i);

@@ -952,8 +963,10 @@ static void init_std_data(struct entropy_store *r)
 	mix_pool_bytes(r, &now, sizeof(now));
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
 	/* Enable continuous test in fips mode */
-	if (fips_enabled)
-		r->last_data = kmalloc(EXTRACT_SIZE, GFP_KERNEL);
+	if (fips_enabled) {
+		r->rep = kmalloc(sizeof(struct repetition_check), GFP_KERNEL);
+		r->rep->flags = 0;
+	}
 }
 
 static int rand_initialize(void)

Sebastian Andrzej Siewior

2009-09-13 12:17 UTC #1 lore raw

Quoted 5 lines · * Neil Horman | 2009-09-12 12:44:11 [-0400]:

drivers/char/random.c +0 -0
index d8a9255..6700248 100644

drivers/char/random.c module_param(debug, bool, 0644); · line 407

Quoted 9 lines

drivers/char/random.c +6 -0

@@ -399,6 +399,12 @@ module_param(debug, bool, 0644);
 * storing entropy in an entropy pool.
 *
 **********************************************************************/
+#define EXTRACT_SIZE 10
+#define REP_CHECK_BLOCK_COPIED 1
+struct repetition_check {
+	__u8 last_data[EXTRACT_SIZE];
+	__u8 flags;
+};

This struct should have 11 bytes and is only used in FIPS enabled mode.

drivers/char/random.c struct entropy_store { · line 424

Quoted 9 lines

drivers/char/random.c +1 -1

 struct entropy_store;
 struct entropy_store {

@@ -414,7 +420,7 @@ struct entropy_store {
 	unsigned add_ptr;
 	int entropy_count;
 	int input_rotate;
-	__u8 *last_data;
+	struct repetition_check *rep;
 };

so just a pointer to 11 bytes

Quoted 36 lines

drivers/char/random.c +9 -4

 static __u32 input_pool_data[INPUT_POOL_WORDS];

@@ -714,7 +720,6 @@ void ad
 
-#define EXTRACT_SIZE 10
 
 /*********************************************************************
 *

@@ -856,18 +861,24 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
 
+repeat_extract:
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
 	while (nbytes) {
 		extract_buf(r, tmp);
 
-		if (r->last_data) {
+		if (r->rep) {
 			spin_lock_irqsave(&r->lock, flags);
-			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
+			if ((r->rep->flags & REP_CHECK_BLOCK_COPIED) &&
+			    !memcmp(tmp, r->rep->last_data, EXTRACT_SIZE))
 				panic("Hardware RNG duplicated output!\n");
-			memcpy(r->last_data, tmp, EXTRACT_SIZE);
+			memcpy(r->rep->last_data, tmp, EXTRACT_SIZE);
 			spin_unlock_irqrestore(&r->lock, flags);
+			if (!(r->rep->flags & REP_CHECK_BLOCK_COPIED)) {
+				r->rep->flags |= REP_CHECK_BLOCK_COPIED;
+				goto repeat_extract;
+			}
 		}
 		i = min_t(int, nbytes, EXTRACT_SIZE);
 		memcpy(buf, tmp, i);

drivers/char/random.c static void init_std_data(struct entropy_store *r) · line 967

Quoted 7 lines

drivers/char/random.c +2 -2

@@ -952,8 +963,10 @@ static void init_std_data(struct entropy_store *r)
 	mix_pool_bytes(r, &now, sizeof(now));
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
 	/* Enable continuous test in fips mode */
-	if (fips_enabled)
-		r->last_data = kmalloc(EXTRACT_SIZE, GFP_KERNEL);
+	if (fips_enabled) {
+		r->rep = kmalloc(sizeof(struct repetition_check), GFP_KERNEL);

and we alloc this 11 bytes via kmalloc. The smallest allocation is afaik 32 bytes. The three pools (input_pool, blocking_pool, nonblocking_pool) are in data seg so it probably does not hurt if you add the extra 10 bytes there. The advantage:
- you don't have to deal with -ENOMEM. Otherwise it could be possible that you not doing anything special in fips_mode
- you go OOM if the user is using RNDCLEARPOOL ioctl(). Slowly but you do.

drivers/char/random.c static void init_std_data(struct entropy_store *r) · line 972

Quoted 5 lines

drivers/char/random.c +2 -0

+		r->rep->flags = 0;
+	}
 }
 
 static int rand_initialize(void)

Sebastian

Neil Horman

author

2009-09-14 02:04 UTC #2 lore raw

Quoted 72 lines · Sebastian Andrzej Siewior

Quoted 5 lines · * Neil Horman | 2009-09-12 12:44:11 [-0400]:

drivers/char/random.c +0 -0
index d8a9255..6700248 100644

drivers/char/random.c module_param(debug, bool, 0644); · line 407

Quoted 9 lines

drivers/char/random.c +6 -0

@@ -399,6 +399,12 @@ module_param(debug, bool, 0644);
 * storing entropy in an entropy pool.
 *
 **********************************************************************/
+#define EXTRACT_SIZE 10
+#define REP_CHECK_BLOCK_COPIED 1
+struct repetition_check {
+	__u8 last_data[EXTRACT_SIZE];
+	__u8 flags;
+};

This struct should have 11 bytes and is only used in FIPS enabled mode.

drivers/char/random.c struct entropy_store { · line 424

Quoted 9 lines

drivers/char/random.c +1 -1

 struct entropy_store;
 struct entropy_store {

@@ -414,7 +420,7 @@ struct entropy_store {
 	unsigned add_ptr;
 	int entropy_count;
 	int input_rotate;
-	__u8 *last_data;
+	struct repetition_check *rep;
 };

so just a pointer to 11 bytes

Quoted 36 lines

drivers/char/random.c +9 -4

 static __u32 input_pool_data[INPUT_POOL_WORDS];

@@ -714,7 +720,6 @@ void ad
 
-#define EXTRACT_SIZE 10
 
 /*********************************************************************
 *

@@ -856,18 +861,24 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
 
+repeat_extract:
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
 	while (nbytes) {
 		extract_buf(r, tmp);
 
-		if (r->last_data) {
+		if (r->rep) {
 			spin_lock_irqsave(&r->lock, flags);
-			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
+			if ((r->rep->flags & REP_CHECK_BLOCK_COPIED) &&
+			    !memcmp(tmp, r->rep->last_data, EXTRACT_SIZE))
 				panic("Hardware RNG duplicated output!\n");
-			memcpy(r->last_data, tmp, EXTRACT_SIZE);
+			memcpy(r->rep->last_data, tmp, EXTRACT_SIZE);
 			spin_unlock_irqrestore(&r->lock, flags);
+			if (!(r->rep->flags & REP_CHECK_BLOCK_COPIED)) {
+				r->rep->flags |= REP_CHECK_BLOCK_COPIED;
+				goto repeat_extract;
+			}
 		}
 		i = min_t(int, nbytes, EXTRACT_SIZE);
 		memcpy(buf, tmp, i);

drivers/char/random.c static void init_std_data(struct entropy_store *r) · line 967

Quoted 7 lines

drivers/char/random.c +2 -2

@@ -952,8 +963,10 @@ static void init_std_data(struct entropy_store *r)
 	mix_pool_bytes(r, &now, sizeof(now));
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
 	/* Enable continuous test in fips mode */
-	if (fips_enabled)
-		r->last_data = kmalloc(EXTRACT_SIZE, GFP_KERNEL);
+	if (fips_enabled) {
+		r->rep = kmalloc(sizeof(struct repetition_check), GFP_KERNEL);

Quoted 9 lines

and we alloc this 11 bytes via kmalloc. The smallest allocation is afaik 32 bytes. The three pools (input_pool, blocking_pool, nonblocking_pool) are in data seg so it probably does not hurt if you add the extra 10 bytes there. The advantage:
- you don't have to deal with -ENOMEM. Otherwise it could be possible that you not doing anything special in fips_mode
- you go OOM if the user is using RNDCLEARPOOL ioctl(). Slowly but you do.

Ok, fair enough. I'll rework it to all be inline and repost shortly. Neil

Neil Horman

author

2009-09-14 16:30 UTC #3 lore raw

Re: [PATCH]: fix repetition test for hardware RNG to be FIPS compliant (v2)

In reply to Sebastian Andrzej Siewior

Ok, version 2 of the patch, taking comments into account

To be fips compliant, RNGs need to preform a continuous test on their output. Specifically the requirement is that the first block of random data generated in an RNG be saved to see the comparison test, and never returned to the caller. This patch augments the continuous test in the hardware RNG to enforce this requirement, making the hardware RNG fips compliant (when operating in fips mode).

Neil

Signed-off-by Neil Horman <[email protected]>

 random.c |   28 ++++++++++++++++++++--------
 1 file changed, 20 insertions(+), 8 deletions(-)

drivers/char/random.c +20 -8

index d8a9255..36fb05e 100644
@@ -399,6 +399,14 @@ module_param(debug, bool, 0644);
  * storing entropy in an entropy pool.
  *
  **********************************************************************/
+#define EXTRACT_SIZE 10
+
+#define REP_CHECK_BLOCK_COPIED 1
+
+struct repetition_check {
+	__u8 last_data[EXTRACT_SIZE];
+	__u8 flags;
+};
 
 struct entropy_store;
 struct entropy_store {

@@ -414,7 +422,7 @@ struct entropy_store {
 	unsigned add_ptr;
 	int entropy_count;
 	int input_rotate;
-	__u8 *last_data;
+	struct repetition_check rep;
 };
 
 static __u32 input_pool_data[INPUT_POOL_WORDS];

@@ -714,7 +722,6 @@ void add_disk_randomness(struct gendisk *disk)
 }
 #endif
 
-#define EXTRACT_SIZE 10
 
 /*********************************************************************
  *

@@ -855,19 +862,27 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	ssize_t ret = 0, i;
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
+	size_t saved_nbytes = nbytes;
 
+repeat_extract:
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
 	while (nbytes) {
 		extract_buf(r, tmp);
 
-		if (r->last_data) {
+		if (fips_enabled) {
 			spin_lock_irqsave(&r->lock, flags);
-			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
+			if ((r->rep.flags & REP_CHECK_BLOCK_COPIED) &&
+			    !memcmp(tmp, r->rep.last_data, EXTRACT_SIZE))
 				panic("Hardware RNG duplicated output!\n");
-			memcpy(r->last_data, tmp, EXTRACT_SIZE);
+			memcpy(r->rep.last_data, tmp, EXTRACT_SIZE);
 			spin_unlock_irqrestore(&r->lock, flags);
+			if (!(r->rep.flags & REP_CHECK_BLOCK_COPIED)) {
+				r->rep.flags |= REP_CHECK_BLOCK_COPIED;
+				nbytes = saved_nbytes;
+				goto repeat_extract;
+			}
 		}
 		i = min_t(int, nbytes, EXTRACT_SIZE);
 		memcpy(buf, tmp, i);

@@ -951,9 +966,6 @@ static void init_std_data(struct entropy_store *r)
 	now = ktime_get_real();
 	mix_pool_bytes(r, &now, sizeof(now));
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
-	/* Enable continuous test in fips mode */
-	if (fips_enabled)
-		r->last_data = kmalloc(EXTRACT_SIZE, GFP_KERNEL);
 }
 
 static int rand_initialize(void)

Sebastian Andrzej Siewior

2009-09-15 18:54 UTC #4 lore raw

Re: [PATCH]: fix repetition test for hardware RNG to be FIPS compliant (v2)

Quoted 1 line · * Neil Horman | 2009-09-14 12:30:43 [-0400]:

Ok, version 2 of the patch, taking comments into account

looks good.

Sebastian