Change generating and checking of primes so that the error rate of

not being prime depends on the intended use based on the size of
the input.  For larger primes this will result in more rounds of
Miller-Rabin.  The maximal error rate for primes with more than
1080 bits is lowered to 2^-128.
Patch from Kurt Roeckx <kurt@roeckx.be> and Annie Yousar
via OpenSSL commit feac7a1c Jul 25 18:55:16 2018 +0200,
still under a free license.
OK tb@.

2 files changed, 93 insertions, 26 deletions

diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index cd94e39345..cc1f467523 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn.h,v 1.38 2018/02/20 17:13:14 jsing Exp $ */
+/* $OpenBSD: bn.h,v 1.39 2019/08/25 19:23:59 schwarze Exp $ */
 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -308,24 +308,79 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b);
 #define BN_prime_checks 0 /* default: select number of iterations
                              based on the size of the number */
 
-/* number of Miller-Rabin iterations for an error rate  of less than 2^-80
- * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
- * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
- * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
- * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
-#define BN_prime_checks_for_size(b) ((b) >= 1300 ?  2 : \
-                                (b) >=  850 ?  3 : \
-                                (b) >=  650 ?  4 : \
-                                (b) >=  550 ?  5 : \
-                                (b) >=  450 ?  6 : \
-                                (b) >=  400 ?  7 : \
-                                (b) >=  350 ?  8 : \
-                                (b) >=  300 ?  9 : \
-                                (b) >=  250 ? 12 : \
-                                (b) >=  200 ? 15 : \
-                                (b) >=  150 ? 18 : \
-                                /* b >= 100 */ 27)
+/*
+ * BN_prime_checks_for_size() returns the number of Miller-Rabin
+ * iterations that will be done for checking that a random number
+ * is probably prime.  The error rate for accepting a composite
+ * number as prime depends on the size of the prime |b|.  The error
+ * rates used are for calculating an RSA key with 2 primes, and so
+ * the level is what you would expect for a key of double the size
+ * of the prime.
+ *
+ * This table is generated using the algorithm of FIPS PUB 186-4
+ * Digital Signature Standard (DSS), section F.1, page 117.
+ * (https://dx.doi.org/10.6028/NIST.FIPS.186-4)
+ *
+ * The following magma script was used to generate the output:
+ * securitybits:=125;
+ * k:=1024;
+ * for t:=1 to 65 do
+ *   for M:=3 to Floor(2*Sqrt(k-1)-1) do
+ *     S:=0;
+ *     // Sum over m
+ *     for m:=3 to M do
+ *       s:=0;
+ *       // Sum over j
+ *       for j:=2 to m do
+ *         s+:=(RealField(32)!2)^-(j+(k-1)/j);
+ *       end for;
+ *       S+:=2^(m-(m-1)*t)*s;
+ *     end for;
+ *     A:=2^(k-2-M*t);
+ *     B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S;
+ *     pkt:=2.00743*Log(2)*k*2^-k*(A+B);
+ *     seclevel:=Floor(-Log(2,pkt));
+ *     if seclevel ge securitybits then
+ *       printf "k: %5o, security: %o bits  (t: %o, M: %o)\n",k,seclevel,t,M;
+ *       break;
+ *     end if;
+ *   end for;
+ *   if seclevel ge securitybits then break; end if;
+ * end for;
+ *
+ * It can be run online at:
+ * http://magma.maths.usyd.edu.au/calc
+ *
+ * And will output:
+ * k:  1024, security: 129 bits  (t: 6, M: 23)
+ *
+ * k is the number of bits of the prime, securitybits is the level
+ * we want to reach.
+ *
+ * prime length | RSA key size | # MR tests | security level
+ * -------------+--------------|------------+---------------
+ *  (b) >= 6394 |     >= 12788 |          3 |        256 bit
+ *  (b) >= 3747 |     >=  7494 |          3 |        192 bit
+ *  (b) >= 1345 |     >=  2690 |          4 |        128 bit
+ *  (b) >= 1080 |     >=  2160 |          5 |        128 bit
+ *  (b) >=  852 |     >=  1704 |          5 |        112 bit
+ *  (b) >=  476 |     >=   952 |          5 |         80 bit
+ *  (b) >=  400 |     >=   800 |          6 |         80 bit
+ *  (b) >=  347 |     >=   694 |          7 |         80 bit
+ *  (b) >=  308 |     >=   616 |          8 |         80 bit
+ *  (b) >=   55 |     >=   110 |         27 |         64 bit
+ *  (b) >=    6 |     >=    12 |         34 |         64 bit
+ */
 
+#define BN_prime_checks_for_size(b) ((b) >= 3747 ?  3 : \
+                                (b) >=  1345 ?  4 : \
+                                (b) >=  476 ?  5 : \
+                                (b) >=  400 ?  6 : \
+                                (b) >=  347 ?  7 : \
+                                (b) >=  308 ?  8 : \
+                                (b) >=  55  ? 27 : \
+                                /* b >= 6 */ 34)
+ 
 #define BN_num_bytes(a) ((BN_num_bits(a)+7)/8)
 
 /* Note that BN_abs_is_word didn't work reliably for w == 0 until 0.9.8 */
diff --git a/src/lib/libcrypto/man/BN_generate_prime.3 b/src/lib/libcrypto/man/BN_generate_prime.3
index 2369b6f24f..7db27fd627 100644
--- a/src/lib/libcrypto/man/BN_generate_prime.3
+++ b/src/lib/libcrypto/man/BN_generate_prime.3
@@ -1,6 +1,5 @@
-.\" $OpenBSD: BN_generate_prime.3,v 1.17 2019/06/10 14:58:48 schwarze Exp $
-.\" full merge up to: OpenSSL b3696a55 Sep 2 09:35:50 2017 -0400
-.\" selective merge up to: OpenSSL df75c2bf Dec 9 01:02:36 2018 +0100
+.\" $OpenBSD: BN_generate_prime.3,v 1.18 2019/08/25 19:24:00 schwarze Exp $
+.\" full merge up to: OpenSSL f987a4dd Jun 27 10:12:08 2019 +0200
 .\"
 .\" This file was written by Ulf Moeller <ulf@openssl.org>
 .\" Bodo Moeller <bodo@openssl.org>, and Matt Caswell <matt@openssl.org>.
@@ -51,7 +50,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: June 10 2019 $
+.Dd $Mdocdate: August 25 2019 $
 .Dt BN_GENERATE_PRIME 3
 .Os
 .Sh NAME
@@ -156,6 +155,8 @@ Deprecated:
 .Fn BN_generate_prime_ex
 generates a pseudo-random prime number of at least bit length
 .Fa bits .
+The returned number is probably prime, but there is a very small
+probability of returning a non-prime number.
 If
 .Fa ret
 is not
@@ -212,8 +213,6 @@ If
 is true, it will be a safe prime (i.e. a prime p so that (p-1)/2
 is also prime).
 .Pp
-The prime number generation has a negligible error probability.
-.Pp
 .Fn BN_is_prime_ex
 and
 .Fn BN_is_prime_fasttest_ex
@@ -251,8 +250,21 @@ If
 .Fa nchecks
 ==
 .Dv BN_prime_checks ,
-a number of iterations is used that yields a false positive rate of at
-most 2^-80 for random input.
+a number of iterations is used that yields a false positive rate
+of at most 2\(ha-64 for random input.
+The error rate depends on the size of the prime
+and goes down for bigger primes.
+The rate is 2\(ha-80 starting at 308 bits, 2\(ha-112 at 852 bits,
+2\(ha-128 at 1080 bits, 2\(ha-192 at 3747 bits
+and 2\(ha-256 at 6394 bits.
+.Pp
+When the source of the prime is not random or not trusted, the
+number of checks needs to be much higher to reach the same level
+of assurance: It should equal half of the targeted security level
+in bits (rounded up to the next integer if necessary).
+For instance, to reach the 128 bit security level,
+.Fa nchecks
+should be set to 64.
 .Pp
 If
 .Fa cb