I think this needs to be back-ported to 1.1.1 at least (a cherry-pick does not work).
Since we always generate p=q=2 mod 3, and also p=q=r=2 mod 3
n=p*q = 1 mod 3, but n=p*q*r = 2 mod 3
it is easy to scan for multi-prime rsa keys, just by dividing n.

Is that a security issue for multiprime rsa keys?

No, but it allows fingerprinting of public rsa certificates and possibly targeting weak ones.
This paper https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_svenda.pdf
shows that these properties can be used to track down which software generated which keys,
from just a few samples.

I think the current code will never find the safe prime 5.

I'm wondering if we should go for q ≡ 11 (mod 12) instead of q ≡ 3 (mod 4) for safe primes, and then just special case the values 5 and 7.

Yes, correct. Same for 11, and 23.
Because 5 cannot be the output of BN_rand BN_RAND_TOP_TWO,

So do we care that it can't generate some small primes?

not really.
One could consider generating random values with BN_RAND_TOP_ONE
if looking for safe primes.

Since the method uses random numbers, I expect the primes to be large.

But then we actually seem to have code for primes that fit in a word ...

yes, that's a strange thing.

And that the top 2 bits are set suggest that the use is for multiplying 2 such numbers, so that you end up with something of the correct bit length...

Yes, RSA depends on that a lot.
I don't know if it is documented that way,
but if you use add=NULL and look for safe primes,
the generated primes have the form 11xxx11 and exact the requested length
but on the other hand if you use add!=NULL you get safe primes
of the form 1xxxxx11 and possibly longer than the requested length.
Note: add/rem could be chosen in a way that enters a endless loop.

example for bad parametes would be
add=0x8000 rem=0x1 bits=3 for instance

I wonder if the FIPS stuff needs a range of sqrt(2)*2^(n-1)..2^n instead of our 1.5*2^(n-1)..2^n
for the RSA factors.

I could remove the single word special case, without sacrificing any functionality.
would you like that?

removed the single word code.

The last update uses the pre-computed modules from the probable_prime also
in probable_prime_dh, the speed-up is not too bad :-)
I have measured a few times cumulated probable_prime_dh vs. total time

safe prime bits             512           1024           2048       4096
original                    87%            75%            48%        20%
734bacf                     77%            59%            31%        11%
05d957b                     72%            50%            24%         8%

The single word code got added in commit 96a4c31, to prevent generating larger keys than what was requested.

Correct, it is still guaranteed that probable_prime is able to find a valid candidate
except for safe=true, bits=2/4/5.
While with the additional restriction that probable_prime_dh tries to satisfy it
is possible that it outputs a larger prime candidate than requested.
I don't think that needs to be fixed.

I wonder if the FIPS stuff needs a range of sqrt(2)*2^(n-1)..2^n instead of our 1.5*2^(n-1)..2^n
for the RSA factors.

See rsa_sp800_56b_check.c rsa_check_prime_factor_range()
The fips generation is currently just using 0.C00000000 Instead of 0.B504F33...

See rsa_sp800_56b_check.c rsa_check_prime_factor_range()

Oh, nice.
I wonder if the non-ascii character in the comments there /* set low = (√2)(2^(nbits/2 - 1) */
are okay, I remember in the past there were invisible non-ascii space characters
in the code base, which were causing problems in some O/S at least.

which were causing problems in some O/S at least.

Something that is inside a comment? wow.

... only a faux-pas, maybe just reading glibberish.

You've changed the safe DH generation from generating q, and sieving both p and q to generate p and only sieve p. My guess is that this will slow down the generation of the DH parameters, and I think we should continue to sieve both. probable_prime() should probably also sieve both in case of safe primes.

The whole idea behind this PR is the following:
if p mod x == 1 we know that x is a factor of p-1 and since p-1 is even q=(p-1)/2 is not a prime.
Therefore we want p mod x <= 1 for safe primes and p mod x == 0 for the general case.

+1 to CHANGES entry

Fixed conflicts, added CHANGES entry.

I am not convinced that this PR is well motivated. Neither the ability to fingerprint 3-prime RSA, nor the ability fingerprint OpenSSL as the generator of cracked (due to poor entropy) 2-prime RSA looks compelling to me. On the other hand, there may IIRC be worthwhile benefits to avoiding common small factors (other than 2) between (p-1) and (q-1) (there was some back even talk of avoiding small common factors of (p^2-1) and (q^2-1), don't recall the rationale).

Anyway, we should take care, and make changes only for sound number theoretic reasons, not publicity. When we're the most widely used toolkit, we're also the most widely misused toolkit, that's just life, but we should avoid knee-jerk fixes.

What is the actual best-practice around generation of 2-prime RSA moduli?

Is this PR consistent with SP186 B.3 for generating RSA key pairs? Perhaps it should be?

What benefits could those be, do you have any references?

Regarding multi-primes RSA modules, we enforce the following limits:
512..1023: n=2
1024..4095: n=2 or 3
4096..8191: n=2, 3 or 4
8192..16384: n=2, 3, 4 or 5

In the review of the multi-prime PR, I insisted in checking the first byte of the modulus to be
in the rang 0x9..0xF, as it would be always for 2-prime RSA. Thus avoid targeting 3-prime RSA
modules which happen to start with 0x8 in the most significant bits.
At that time, I was not aware of this undocumented feature of the probable_prime,
so as a result, currently all RSA modules between 1024 and 4095 are trivial to fingerprint.

Quoting from https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf, Page 22:

" Pollard’s p−1 method

This method finds larger factors than the rho method (in the same time) but only works for special primes. Here p−1 = 26·32·52·17·227·491·991·36559·308129·4161791has only small factors
(aka. p is smooth).

Math ahead: Avoiding such p helps against the p−1 method – but does not help against ECM (the elliptic curve method), which works if the number of points on a curve modulo p is smooth.

“Strong primes” are obsolete: fail to defend against ECM. "

Everybody assumes that this selection was designed as a defense against p-1 because p
might be more likely non-smooth this way, is that correct?

Is this PR consistent with SP186 B.3 for generating RSA key pairs? Perhaps it should be?

Ah, You mean FIPS186-4 B.3, I believe @slontis has been working on it here:
https://github.com/openssl/openssl/blob/master/crypto/bn/bn_rsa_fips186_4.c

It is not based on BN_generate_prime_ex2 and is therefore not affected by this PR.
But I don't see it preferring any kind of smoothness in p-1, or q-1, please someone correct
me if I am wrong.

talk of avoiding small common factors of (p^2-1) and (q^2-1), don't recall the rationale.

p^2-1 = (p-1)*(p+1)

Hmm, sounds like attacking p-1 and p+1 methods at once, right?

Even if avoiding fingerprinting of n-prime RSA may not be enough as a motivation,
I still don't see what could be worthwhile benefits to avoiding common small factors,
when the best factorization methods today are GNFS and ECM.
But except the small factors this PR also removes lots of code duplication and
offers certainly a worthwhile speed-up for generating safe primes as shown in
#9309 (comment).

Ping?

fixed the merge conflict in the CHANGES file.

Pushed. Thanks!