Fix issues in ia32 RDRAND asm leading to reduced entropy

This patch fixes two issues in the ia32 RDRAND assembly code that result in a
(possibly significant) loss of entropy.

The first, less significant, issue is that, by returning success as 0 from
OPENSSL_ia32_rdrand() and OPENSSL_ia32_rdseed(), a subtle bias was introduced.
Specifically, because the assembly routine copied the remaining number of
retries over the result when RDRAND/RDSEED returned 'successful but zero', a
bias towards values 1-8 (primarily 8) was introduced.

The second, more worrying issue was that, due to a mixup in registers, when a
buffer that was not size 0 or 1 mod 8 was passed to OPENSSL_ia32_rdrand_bytes
or OPENSSL_ia32_rdseed_bytes, the last (n mod 8) bytes were all the same value.
This issue impacts only the 64-bit variant of the assembly.

This change fixes both issues by first eliminating the only use of
OPENSSL_ia32_rdrand, replacing it with OPENSSL_ia32_rdrand_bytes, and fixes the
register mixup in OPENSSL_ia32_rdrand_bytes. It also adds a sanity test for
OPENSSL_ia32_rdrand_bytes and OPENSSL_ia32_rdseed_bytes to help catch problems
of this nature in the future.

Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/5342)

6 files changed, 166 insertions, 49 deletions

diff --git a/crypto/engine/eng_rdrand.c b/crypto/engine/eng_rdrand.c
index 7be64e3fd4..261e5debbf 100644
--- a/crypto/engine/eng_rdrand.c
+++ b/crypto/engine/eng_rdrand.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2011-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2011-2018 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -20,28 +20,15 @@
      defined(__x86_64) || defined(__x86_64__) || \
      defined(_M_AMD64) || defined (_M_X64)) && defined(OPENSSL_CPUID_OBJ)
 
-size_t OPENSSL_ia32_rdrand(void);
+size_t OPENSSL_ia32_rdrand_bytes(unsigned char *buf, size_t len);
 
 static int get_random_bytes(unsigned char *buf, int num)
 {
-    size_t rnd;
-
-    while (num >= (int)sizeof(size_t)) {
-        if ((rnd = OPENSSL_ia32_rdrand()) == 0)
-            return 0;
-
-        *((size_t *)buf) = rnd;
-        buf += sizeof(size_t);
-        num -= sizeof(size_t);
-    }
-    if (num) {
-        if ((rnd = OPENSSL_ia32_rdrand()) == 0)
-            return 0;
-
-        memcpy(buf, &rnd, num);
+    if (num < 0) {
+        return 0;
     }
 
-    return 1;
+    return (size_t)num == OPENSSL_ia32_rdrand_bytes(buf, (size_t)num);
 }
 
 static int random_status(void)
diff --git a/crypto/x86_64cpuid.pl b/crypto/x86_64cpuid.pl
index 0a88c7a4ed..513d00560c 100644
--- a/crypto/x86_64cpuid.pl
+++ b/crypto/x86_64cpuid.pl
@@ -1,5 +1,5 @@
 #! /usr/bin/env perl
-# Copyright 2005-2016 The OpenSSL Project Authors. All Rights Reserved.
+# Copyright 2005-2018 The OpenSSL Project Authors. All Rights Reserved.
 #
 # Licensed under the OpenSSL license (the "License").  You may not use
 # this file except in compliance with the License.  You can obtain a copy
@@ -434,21 +434,6 @@ ___
 sub gen_random {
 my $rdop = shift;
 print<<___;
-.globl	OPENSSL_ia32_${rdop}
-.type	OPENSSL_ia32_${rdop},\@abi-omnipotent
-.align	16
-OPENSSL_ia32_${rdop}:
-	mov	\$8,%ecx
-.Loop_${rdop}:
-	${rdop}	%rax
-	jc	.Lbreak_${rdop}
-	loop	.Loop_${rdop}
-.Lbreak_${rdop}:
-	cmp	\$0,%rax
-	cmove	%rcx,%rax
-	ret
-.size	OPENSSL_ia32_${rdop},.-OPENSSL_ia32_${rdop}
-
 .globl	OPENSSL_ia32_${rdop}_bytes
 .type	OPENSSL_ia32_${rdop}_bytes,\@abi-omnipotent
 .align	16
@@ -482,11 +467,12 @@ OPENSSL_ia32_${rdop}_bytes:
 	mov	%r10b,($arg1)
 	lea	1($arg1),$arg1
 	inc	%rax
-	shr	\$8,%r8
+	shr	\$8,%r10
 	dec	$arg2
 	jnz	.Ltail_${rdop}_bytes
 
 .Ldone_${rdop}_bytes:
+	xor	%r10,%r10	# Clear sensitive data from register
 	ret
 .size	OPENSSL_ia32_${rdop}_bytes,.-OPENSSL_ia32_${rdop}_bytes
 ___
diff --git a/crypto/x86cpuid.pl b/crypto/x86cpuid.pl
index 08c129a2a0..d43dda4d93 100644
--- a/crypto/x86cpuid.pl
+++ b/crypto/x86cpuid.pl
@@ -1,5 +1,5 @@
 #! /usr/bin/env perl
-# Copyright 2004-2016 The OpenSSL Project Authors. All Rights Reserved.
+# Copyright 2004-2018 The OpenSSL Project Authors. All Rights Reserved.
 #
 # Licensed under the OpenSSL license (the "License").  You may not use
 # this file except in compliance with the License.  You can obtain a copy
@@ -453,18 +453,6 @@ my $max = "ebp";
 
 sub gen_random {
 my $rdop = shift;
-&function_begin_B("OPENSSL_ia32_${rdop}");
-	&mov	("ecx",8);
-&set_label("loop");
-	&${rdop}("eax");
-	&jc	(&label("break"));
-	&loop	(&label("loop"));
-&set_label("break");
-	&cmp	("eax",0);
-	&cmove	("eax","ecx");
-	&ret	();
-&function_end_B("OPENSSL_ia32_${rdop}");
-
 &function_begin_B("OPENSSL_ia32_${rdop}_bytes");
 	&push	("edi");
 	&push	("ebx");
@@ -502,6 +490,7 @@ my $rdop = shift;
 	&jnz	(&label("tail"));
 
 &set_label("done");
+	&xor	("edx","edx");		# Clear random value from registers
 	&pop	("ebx");
 	&pop	("edi");
 	&ret	();
diff --git a/test/build.info b/test/build.info
index 30424dc4cf..9fcaa7d8c8 100644
--- a/test/build.info
+++ b/test/build.info
@@ -405,7 +405,8 @@ INCLUDE_MAIN___test_libtestutil_OLB = /INCLUDE=MAIN
   # names with the DLL import libraries.
   IF[{- $disabled{shared} || $target{build_scheme}->[1] ne 'windows' -}]
     PROGRAMS_NO_INST=asn1_internal_test modes_internal_test x509_internal_test \
-                     tls13encryptiontest wpackettest ctype_internal_test
+                     tls13encryptiontest wpackettest ctype_internal_test \
+                     rdrand_sanitytest
     IF[{- !$disabled{poly1305} -}]
       PROGRAMS_NO_INST=poly1305_internal_test
     ENDIF
@@ -465,6 +466,10 @@ INCLUDE_MAIN___test_libtestutil_OLB = /INCLUDE=MAIN
     SOURCE[curve448_internal_test]=curve448_internal_test.c
     INCLUDE[curve448_internal_test]=.. ../include ../crypto/ec/curve448
     DEPEND[curve448_internal_test]=../libcrypto.a libtestutil.a
+
+    SOURCE[rdrand_sanitytest]=rdrand_sanitytest.c
+    INCLUDE[rdrand_sanitytest]=../include
+    DEPEND[rdrand_sanitytest]=../libcrypto.a libtestutil.a
   ENDIF
 
   IF[{- !$disabled{mdc2} -}]
diff --git a/test/rdrand_sanitytest.c b/test/rdrand_sanitytest.c
new file mode 100644
index 0000000000..21d5139f2b
--- /dev/null
+++ b/test/rdrand_sanitytest.c
@@ -0,0 +1,125 @@
+/*
+ * Copyright 2018-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * 
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "testutil.h"
+#include <openssl/opensslconf.h>
+
+#if (defined(__i386)   || defined(__i386__)   || defined(_M_IX86) || \
+     defined(__x86_64) || defined(__x86_64__) || \
+     defined(_M_AMD64) || defined (_M_X64)) && defined(OPENSSL_CPUID_OBJ)
+
+size_t OPENSSL_ia32_rdrand_bytes(unsigned char *buf, size_t len);
+size_t OPENSSL_ia32_rdseed_bytes(unsigned char *buf, size_t len);
+
+void OPENSSL_cpuid_setup();
+
+extern unsigned int OPENSSL_ia32cap_P[4];
+
+static int sanity_check_bytes(size_t (*rng)(unsigned char *, size_t), 
+    int rounds, int min_failures, int max_retries, int max_zero_words)
+{
+    int testresult = 0;
+    unsigned char prior[31] = {0}, buf[31] = {0}, check[7];
+    int failures = 0, zero_words = 0;
+
+    int i;
+    for (i = 0; i < rounds; i++) {
+        size_t generated = 0;
+
+        int retry;
+        for (retry = 0; retry < max_retries; retry++) {
+            generated = rng(buf, sizeof(buf));
+            if (generated == sizeof(buf))
+                break;
+            failures++;
+        }
+
+        /*-
+         * Verify that we don't have too many unexpected runs of zeroes,
+         * implying that we might be accidentally using the 32-bit RDRAND
+         * instead of the 64-bit one on 64-bit systems.
+         */
+        size_t j;
+        for (j = 0; j < sizeof(buf) - 1; j++) {
+            if (buf[j] == 0 && buf[j+1] == 0) {
+                zero_words++;
+            }
+        }
+
+        if (!TEST_int_eq(generated, sizeof(buf)))
+            goto end;
+        if (!TEST_false(!memcmp(prior, buf, sizeof(buf))))
+            goto end;
+
+        /* Verify that the last 7 bytes of buf aren't all the same value */
+        unsigned char *tail = &buf[sizeof(buf) - sizeof(check)];
+        memset(check, tail[0], 7);
+        if (!TEST_false(!memcmp(check, tail, sizeof(check))))
+            goto end;
+
+        /* Save the result and make sure it's different next time */
+        memcpy(prior, buf, sizeof(buf));
+    }
+
+    if (!TEST_int_le(zero_words, max_zero_words))
+        goto end;
+
+    if (!TEST_int_ge(failures, min_failures))
+        goto end;
+
+    testresult = 1;
+end:
+    return testresult;
+}
+
+static int sanity_check_rdrand_bytes()
+{
+    return sanity_check_bytes(OPENSSL_ia32_rdrand_bytes, 1000, 0, 10, 10);
+}
+
+static int sanity_check_rdseed_bytes()
+{
+    /*-
+     * RDSEED may take many retries to succeed; note that this is effectively
+     * multiplied by the 8x retry loop in asm, and failure probabilities are
+     * increased by the fact that we need either 4 or 8 samples depending on
+     * the platform.
+     */
+    return sanity_check_bytes(OPENSSL_ia32_rdseed_bytes, 1000, 1, 10000, 10);
+}
+
+int setup_tests() {
+    OPENSSL_cpuid_setup();
+
+    int have_rdseed = (OPENSSL_ia32cap_P[2] & (1 << 18)) != 0;
+    int have_rdrand = (OPENSSL_ia32cap_P[1] & (1 << (62 - 32))) != 0;
+
+    if (have_rdrand) {
+        ADD_TEST(sanity_check_rdrand_bytes);
+    }
+
+    if (have_rdseed) {
+        ADD_TEST(sanity_check_rdseed_bytes);
+    }
+
+    return 1;
+}
+
+
+#else
+
+int setup_tests()
+{
+    return 1;
+}
+
+#endif
diff --git a/test/recipes/06-test-rdrand.t b/test/recipes/06-test-rdrand.t
new file mode 100644
index 0000000000..07ee7c8478
--- /dev/null
+++ b/test/recipes/06-test-rdrand.t
@@ -0,0 +1,25 @@
+#! /usr/bin/perl
+
+# Copyright 2018-2018 The OpenSSL Project Authors. All Rights Reserved.
+# 
+# Licensed under the OpenSSL license (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+use strict;
+
+use OpenSSL::Test;              # get 'plan'
+use OpenSSL::Test::Simple;
+use OpenSSL::Test::Utils;
+
+setup("test_rdrand_sanity");
+
+plan skip_all => "This test is unsupported in a shared library build on Windows"
+    if $^O eq 'MSWin32' && !disabled("shared");
+
+# We also need static builds to be enabled even on linux
+plan skip_all => "This test is unsupported if static builds are not enabled"
+    if disabled("static");
+
+simple_test("test_rdrand_sanity", "rdrand_sanitytest");