Join Log in
Score:11
Farzad Sadeghi avatar Crypto

RSA Private Exponent Generation according to FIPS 186-4 in openssl v1

us flag
Farzad Sadeghi

I guess this is more of a math problem in a cryptography context so I apologize beforehand if it is not the right place to ask. Basically I have to check whether a certain implementation of RSA key-pair generation adheres to FIPS 186-4. More specifically, Appendix B-3-1. FIPS 186-4 necessitates that $d$ (the private exponent) be created like so:

$d = (e^{-1})\bmod(\text{LCM}(p-1, \space q-1))$

The library in question(openssl v1.0.1) calculates $d$ like so:

$d = (e^{-1})\bmod((p-1)(q-1))$

I can't prove or disprove whether these two create the same set of answers for $d$.
The condition for generation of $p$ and $q$ is that $(p-1)$ and $(q-1)$ are both relatively prime to $e$ (the public exponent) so both formulas have answers.
Also since $p$ and $q$ are both prime, $(p-1)$ and $(q-1)$ will both be even numbers and from $a \times b=\text{GDC}(a, \space b) \times \text{LCM}(a, \space b)$ we know that $\text{GCD}(p-1, \space q-1) \geq 2$ so $\text{LCM}(p-1, \space q-1) \neq (p-1)(q-1)$.

My question is are they the same or different?

I would also appreciate if you could point me in the right direction math-wise so that I could potentially solve this myself.

P.S.: I understand for openssl v1, there is a FIPS module and also that openssl v3.0 will try to apply for a FIPS 140-2 certificate. I am unfortunately stuck with the version I mentioned and I cannot change that(it's not up to me).

592
2 + 3
rsa
Maarten Bodewes avatar
in flag
Maarten Bodewes
I think you got quite a long way of explaining it to yourself and fgrieu's answer is basically confirmation + some additional info on FIPS. Note that the actual ~50% is very hard to narrow down as it depends on $(p-1)(q-1)$ and possibly even the distribution of primes. However, if you just need the calculation to be FIPS compliant it would mean that you could try and use rejection sampling on the RSA key pair generation (generate, check if the additional FIPS requirements are met, and restart if they do not). Private keys in OpenSSL (with internal software engine) are generated with CRT params
2
Reply
dave_thompson_085 avatar
cn flag
dave_thompson_085
Nit: OpenSSL 'v1' is not a single thing; current OpenSSL FIPS-module 2.0.x should work with OpenSSL 1.0.1 and 1.0.2 but not 1.0.0 1.1.0 1.1.1. OpenSSL 3.0.x is designed to be validatable, but not under FIPS 140-2 because that is no longer available; it must go for 140-3 instead. More significant, the current SecurityPolicy (2.0.16) lists RSA compliance as 186-2 not -4, and _keygen_ only as X9.31 per -2 (but _sign_ and _verify_ as both X9.31 per -2 and PKCS1v2 per -3/4), and references CAVP certs that list "RSA KeyGen FIPS186-2" with a strikethrough indicating 'no longer approved'.
0
Reply
Farzad Sadeghi avatar
us flag
Farzad Sadeghi
In retrespect, yes. maybe the v1 in the question title might a bit misleading. you're right. As for the FIPS validation, openssl 3 will go for FIPS 140-2 validation as that is available until September 2021. they will not be going for FIPS 140-3. I've taken a look at the code thought. they are going for FIPS 186-4 compliancy nonetheless.
0
Reply
Score:10
fgrieu avatar Crypto
ng flag
fgrieu

FIPS 186-4's $d_1=e^{-1}\bmod m_1$ with $m_1=\operatorname{lcm}(p-1,q-1)$, and OpenSSL's $d_2=e^{-1}\bmod m_2$ with $m_2=(p-1)(q-1)$, are different with probability $>1/2$ for random choice of $p$ and $q$ and either fixed $e$ adding further constraints on $p$ and $q$ (as common), or $e$ chosen somewhat randomly after $p$ and $q$.

Justification: it holds $m_2=g\,m_1$ for integer $g=\gcd(p-1,q-1)$. That $g$ is an integer at least $2$ (and noticeably often a larger even integer). It follows $d_2\bmod m_1=d_1$. It's well-verified that $d_2$ is roughly uniformly distributed on the interval $[0,m_2)$ within the constraint of being coprime with $m_2$. Thus the modular reduction from $d_2$ to $d_1$ causes a change with probability next to $1-1/g$, which always is at least $1/2$. It's easy to make an example where that occurs. The bound $1/2$ for the probablity that $d_1\ne d_2$ could be improved (increased, a little over $2/3$ actually) by considering the distribution of $g$.

Such frequent discrepancy is not as bad as it sounds, because

  • What's really needed for $d$ to work (when and if used as RSA private exponent, or to compute or check $d_p$ and $d_q$ ) is that $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$ (assuming $p$ and $q$ are distinct primes). Both $d_1$ and $d_2$ match this, and conform to PKCS#1 which additionally requires $0<d<n$ (that follows from $d_1<m_1<m_2<n$ and $d_2<m_2<n$).
  • In practice $d$ is seldom used, because private key operation is faster with the Chineese Remainder Theorem, which typically only uses $(n,e,p,q,d_p,d_q,q_\text{inv})$ or a subset of that, in which case the only possible issues with $d_1$ or $d_2$ is when it first checked, and that's bound to be detected by key import and a single use.
  • Any FIPS 186-4 RSA key is accepted by any version of OpenSSL. I would not bet the house in the other direction, but then it's rare to import a key from OpenSSL into a FIPS 140 device. That might even be prohibited in FIPS mode, and a FIPS device (at least in non-FIPS mode) would be allowed to accept any mathematically valid $d$ including $d_2$, or ignore the given $d$.
0 + 2
poncho avatar
my flag
poncho
Also note that, in practice, the actual value of $d$ is usually ignored. Instead, we usually use the CRT parameters ($p, q, dp, dq, qinv$), and those turn out to be all the same no matter if you use the $\phi(n)$ or the $\operatorname{lcm}(p-1,q-1)$ definition of $d$...
3
Reply
dave_thompson_085 avatar
cn flag
dave_thompson_085
FWIW, FIPS186-4 (and -3) 5.1 explicitly says CRT representation is 'allowed'; it doesn't explicitly mention using it, but references PKCS1v2.1 and of course PKCS1 back to v1.5 at least has preferred CRT for both storage and operations.
1
Reply
Score:2
avatar Crypto
cn flag
j.p.

To my understanding, the requirement in FIPS 186-4 to use for the calculation of the private key $d$ the least common multiple of $p-1$ and $q-1$ instead of the their product has the purpose to prevent attacks against small $d$ like Wiener's attack. The common believe among experts is that one is secure against any improvement of Wiener's attack, if the length of $d$ is at least half of the length of the modulus $m$.

As all (known) variants of attacks against small private key $d$ work depending on the size of the smallest possible $d$ (the one calculated using the least common multiple), NIST insists on using the least common multiple, so that one can check that the smallest possible $d$ is big enough.

As NIST requires that $p$ and $q$ have about the same size, you can verify the length requirement for $d$ also instead by simply checking that $d_p$, $d_p+p-1$, $d_q$ and $d_q+q-1$ are pairwise different. If side-channel attacks are an issue for you, this test can be protected much easier than the calculation of the greatest common divisor of $p-1$ and $q-1$, which became in the last years the target of several published attacks. Which $d$ you use in your calculations shouldn't matter much, as adding a multiple of $(p-1)(q-1)$ to the exponent is commonly used countermeasure against side-channel attacks.

0 + 4
fgrieu avatar
ng flag
fgrieu
Indeed, the test for a minimum $d$ made in FIPS 186-4 would make even less sense if $d$ was not specified to be the minimum positive $d$, as it is. But this test makes little sense anyway, since (A) this test fails with negligible probability when the overall generation methods mandated is used (maximum $e$ + random primes), and (B) there are plenty of methods to rig an RSA key generator in a way that's not detectable from the output. Among other hard to justify tests in FIPS 186-4 are the minimum $\lvert p-q\rvert$; but at least this later one is a redundant way to catch a stuck generator.
0
Reply
cn flag
j.p.
Small $d$ might be an innocent way of "rigging" the keygen for better performance (in case one is afraid of the bellcore attack). Using a sieve for both primes to save some time (obtaining small, insecure $|p-q|$) seems to be less likely indeed.
0
Reply
fgrieu avatar
ng flag
fgrieu
FIPS 186-4 requires $n$ of at least 1024-bit, with $p$ and $q$ half that, and $e$ of at most 256-bit. With this, it's hard to craft $p$ and $q$ with $d$ less than half $n$ (the required limit); and I think impossible with $p$ and $q$ anywhere close to random and independent, even if $e$ is chosen afterwards. That would make the minimum $d$ relevant only for crafted $p$ or/and $q$; but crafted primes are dangerous in many different ways, including a few that could pass as (or even be) accidental mishaps. Hence the minimum $d$ requirement has dubious rationale.
0
Reply
cn flag
j.p.
I think everyone would agree that for really random $p$ and $q$ requiring $e$ not too long should be enough for avoiding bad things to happen. The only way I know to get short $d$ (for short $e$) is to impose a big common divisor for $p-1$ and $q-1$ (that rarely happens by random choice), so I guess that some of the NIST requirements are as "dubious" as the former usage of "safe primes" was....
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.