[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openbsd-tech
Subject:    undefined behaviour in add_entropy_words()
From:       Martin Natano <natano () natano ! net>
Date:       2016-01-31 14:17:50
Message-ID: 20160131141750.GA17159 () watschnbaum ! site
[Download RAW message or body]

Hi,

The add_entropy_words() function performs a right shift by
(32 - entropy_input_rotate) bits, with entropy_input_rotate being an
integer between [0..31]. This can lead to a shift of 32 on a 32 bit
value, which is undefined behaviour in C. The standard says this: "If
the value of the right operand is negative or is greater than or equal
to the width of the promoted left operand, the behaviour is undefined."
In our case the value is 32 and the width of the promoted left operand
is 32 too, thus the behaviour is undefined.

As a matter of fact the expression doesn't yield the (probably) expected
result of 0 on i386 and amd64 machines. The reason being, that the shift
exponent is truncated to 5 bits on x86.

natano@obsd:~$ uname -a
OpenBSD obsd.my.domain 5.9 GENERIC.MP#1862 amd64
natano@obsd:~$ cat test.c
#include <stdio.h>

int
main(void)
{
        unsigned int x = 0xffffffff;
        printf("x >> 32: 0x%x\n", x >> 32);
        return 0;
}
natano@obsd:~$ cc test.c
test.c: In function 'main':
test.c:7: warning: right shift count >= width of type
natano@obsd:~$ ./a.out
x >> 32: 0xffffffff
natano@obsd:~$

On the other hand ppc truncates the shift exponent to 6 bits. (I didn't
try it, but
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
says so).

In the specific instance below, the differing behaviour between x86 and
pcc doesn't matter, because of the equality (x | x) == (x | 0) == x.

However, I think it might be still worth fixing this, because we can't
rely on future versions of gcc and other compilers retaining this
behaviour. The behaviour is undefined, so the compiler can do whatever
it wants (insert obligatory reference to nasal demons here).


Index: dev/rnd.c
===================================================================
RCS file: /cvs/src/sys/dev/rnd.c,v
retrieving revision 1.178
diff -u -p -u -r1.178 rnd.c
--- dev/rnd.c	8 Jan 2016 07:54:02 -0000	1.178
+++ dev/rnd.c	31 Jan 2016 10:11:17 -0000
@@ -420,8 +420,9 @@ add_entropy_words(const u_int32_t *buf, 
 	};
 
 	for (; n--; buf++) {
-		u_int32_t w = (*buf << entropy_input_rotate) |
-		    (*buf >> (32 - entropy_input_rotate));
+		u_int32_t w = *buf << entropy_input_rotate;
+		if (entropy_input_rotate > 0)
+			w |= *buf >> (32 - entropy_input_rotate);
 		u_int i = entropy_add_ptr =
 		    (entropy_add_ptr - 1) & POOLMASK;
 		/*

cheers,
natano

[prev in list] [next in list] [prev in thread] [next in thread]