DH private key size was one bit too large by bernd-edlinger · Pull Request #27870 · openssl/openssl

bernd-edlinger · 2025-06-21T11:12:20Z

In the case when no q parameter was given,
the function generate_key in dh_key.c did create
one bit too much, so the priv_key value was exeeding the DH group size q = (p-1)/2.
This affects also the ffdhe groups, where e.g. the length for ffdhe3072 is given as 275 by RFC 7919,
but the wording in the RFC makes it clear that we
did also use one bit too much, see section 5.2:
"for an ffdhe3072 handshake, each peer can choose
to do $2\times 2\times 275$ multiplications by choosing their
secret exponent from the range $[2^{274}, 2^{275}]$"
Therefore $2^{274}$ must be the highest bit in the
secret exponent, not $2^{275}$ as we did previously.

kroeckx · 2025-06-22T15:24:35Z

Note that the rfc also says:

that is, an m-bit integer where m is at least 275
Peers using ffdhe3072 [...] should choose a secret key of at least 275 bits.

I think the [2^274, 2^275] in the RFC is wrong, and you should probably open an errata.

kroeckx · 2025-06-22T15:26:11Z

Actually, the [2^274, 2^275] seems correct. 2^274 is 275 bit long.

crypto/dh/dh_key.c

bernd-edlinger · 2025-06-24T12:18:15Z

okay, @t8m I followed your suggestion, and changed the commit message to:

DH private key size was one bit too large

In the case when no q parameter was given,
the function generate_key in dh_key.c did create
one bit too much, so the priv_key value was exeeding
the DH group size q = (p-1)/2.
When the length is used in this case the limit is also
one bit too high, but for backward compatibility this
limit was left as is, instead we have to silently reduce
the value by one.

EDIT: fixed typo "exeeding" -> "exceeding"

In the case when no q parameter was given, the function generate_key in dh_key.c did create one bit too much, so the priv_key value was exceeding the DH group size q = (p-1)/2. When the length is used in this case the limit is also one bit too high, but for backward compatibility this limit was left as is, instead we have to silently reduce the value by one.

openssl-machine · 2025-07-25T00:09:32Z

This PR is in a state where it requires action by @openssl/committers but the last update was 30 days ago

vdukhovni · 2025-07-25T07:50:54Z

The patch looks wrong to me. It caps $l$ at $\lfloor\log_2 p\rfloor - 1$, i.e. at $2$ less than the bitsize of $p$, but I don't see why that's correct. Sure the group size is at most $(p-1)/2$, but that's just one bit less than $p$, why exactly are we dropping two bits?

vdukhovni · 2025-07-25T07:53:42Z

crypto/dh/dh_key.c

+                if (dh->length >= l)
                    goto err;
-                l = dh->length ? dh->length : BN_num_bits(dh->params.p) - 1;
+                l -= 2;


Please explain/justify the -2 here.

Suggested change

l -= 2;

l -= 1;

Is there a concern that $g^k$ for the n-bit private key $k$ is insecure because with $2^{n-1} \le q \lt 2^n - 1$ and $k \ge q$, there is an equivalent exponent $k' = k - q$ that could (with low probability) be small enough to be vulnerable to attacks?

Looking at SP800-56A, there are two methods (5.6.1.1.3 and 5.6.1.1.4) of private key generation, neither is limiting the private exponent to 1 bit less than $q$, both generate uniformly random exponents in the full range $[1, q-1]$. Is generating a random bit string in $[2^{l-1}, 2^l-1]$ with $l = \lfloor \log_2 q \rfloor$ (bit size of $q$ - 1) also a FIPS-validatable method?

yes, the concern is that the exponent is equal to q, or very close, so it can be insecure,
however the fips variant is different and what I dislike there is that they care about
explicitly avoiding the exponent 0 but allow very small exponents for no good reason.

Do we use one of the FIPS methods in the FIPS module? Or does the FIPS module use the code patched in this PR?
If the latter, is that allowed?

Assuming FIPS is not a problem, I'd like to see a comment above l -= 2 that explains that we're ensuring that $l$ is chosen to be the largest exponent with $2^l - 1 < q$, which requires $l$ to be one less than the bit length of $q$, i.e. two less than the bit length of $p$.

This is whole code section is inside an ifndef FIPS_MODULE section.
The FIPS compliant code using the algorithm in 5.6.1.1.4 is done here:

openssl/crypto/ffc/ffc_key_generate.c

Lines 12 to 23 in 49f8db5

/*

* SP800-56Ar3 5.6.1.1.4 Key pair generation by testing candidates.

* Generates a private key in the interval [1, min(2 ^ N - 1, q - 1)].

*

* ctx must be set up with a libctx (for fips mode).

* params contains the FFC domain parameters p, q and g (for DH or DSA).

* N is the maximum bit length of the generated private key,

* s is the security strength.

* priv_key is the returned private key,

*/

int ossl_ffc_generate_private_key(BN_CTX *ctx, const FFC_PARAMS *params,

int N, int s, BIGNUM *priv)

also the RFC 7919 groups are handled there, however while the RFC suggests to choose a
secret exponent in the range $[2^{N-1},2^{N}-1]$ the range is actually $[1,2^{N}-1]$

bernd-edlinger · 2025-07-26T06:45:44Z

Without this patch the random number can be larger than q
as this little experiment shows:

diff --git a/crypto/dh/dh_key.c b/crypto/dh/dh_key.c
index 7132b9b68e..618ec92762 100644
--- a/crypto/dh/dh_key.c
+++ b/crypto/dh/dh_key.c
@@ -335,6 +335,20 @@ static int generate_key(DH *dh)
                 if (!BN_priv_rand_ex(priv_key, l, BN_RAND_TOP_ONE,
                                      BN_RAND_BOTTOM_ANY, 0, ctx))
                     goto err;
+                { BIGNUM *q = BN_new();
+                  BN_rshift1(q, dh->params.p);
+                  if (BN_cmp(priv_key, q) >= 0) {
+                    fprintf(stderr, "p = ");
+                    BN_print_fp(stderr, dh->params.p);
+                    fprintf(stderr, "\nq = ");
+                    BN_print_fp(stderr, q);
+                    fprintf(stderr, "\nk = ");
+                    BN_print_fp(stderr, priv_key);
+                    fprintf(stderr, "\n");
+                    goto err;
+                  }
+                  BN_free(q);
+                }
                 /*
                  * We handle just one known case where g is a quadratic non-residue:
                  * for g = 2: p % 8 == 3

result after several tries:

$ make test
...
10-test_bn.t ............................. ok   
10-test_exp.t ............................ ok   
15-test_dh.t ............................. 
p = CF97E512AD6061A54ED3101CD7D6151096C9D8702FD1F7FEE116C165584D61FE1C01860F064FF29497A510D55A72B067104343CA7464BC3598E089452B646D2F
q = 67CBF28956B030D2A769880E6BEB0A884B64EC3817E8FBFF708B60B2AC26B0FF0E00C3078327F94A4BD2886AAD3958338821A1E53A325E1ACC7044A295B23697
k = 6EFED9931DE7D58A109F0A40348FB3ECE5085E22FA89399ED2B53D65EC828A4860DAE295A5DA79172B1A201EF424534C5040B914B26238407F1929F822E2685F
    # 4087D8DFC87F0000:error:02880003:Diffie-Hellman routines:generate_key:BN lib:crypto/dh/dh_key.c:392:
    # OPENSSL_TEST_RAND_SEED=1753512035
    not ok 1 - dh_test
# ------------------------------------------------------------------------------
../../util/wrap.pl ../../test/dhtest => 1
not ok 1 - running dhtest
15-test_dh.t ............................. 1/? ---------------------------------
#   Failed test 'running dhtest'
#   at .../openssl/util/perl/OpenSSL/Test/Simple.pm line 77.
15-test_dh.t ............................. Dubious, test returned 1 (wstat 256, 0x100)
Failed 1/1 subtests

bernd-edlinger · 2025-07-26T10:51:32Z

crypto/dh/dh_key.c

-                /* secret exponent length, must satisfy 2^(l-1) <= p */
-                if (dh->length != 0
-                    && dh->length >= BN_num_bits(dh->params.p))
+                /* secret exponent length, must satisfy 2^l < (p-1)/2 */


@vdukhovni the comment is already changed, to correctly describe the code below.

I find it a tad too terse, my request to make it slightly more explicit.

openssl-machine · 2025-08-13T08:00:30Z

This pull request is ready to merge

In the case when no q parameter was given, the function generate_key in dh_key.c did create one bit too much, so the priv_key value was exceeding the DH group size q = (p-1)/2. When the length is used in this case the limit is also one bit too high, but for backward compatibility this limit was left as is, instead we have to silently reduce the value by one. Reviewed-by: Viktor Dukhovni <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from #27870) (cherry picked from commit d6510d9)

In the case when no q parameter was given, the function generate_key in dh_key.c did create one bit too much, so the priv_key value was exceeding the DH group size q = (p-1)/2. When the length is used in this case the limit is also one bit too high, but for backward compatibility this limit was left as is, instead we have to silently reduce the value by one. Reviewed-by: Viktor Dukhovni <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from #27870)

In the case when no q parameter was given, the function generate_key in dh_key.c did create one bit too much, so the priv_key value was exceeding the DH group size q = (p-1)/2. When the length is used in this case the limit is also one bit too high, but for backward compatibility this limit was left as is, instead we have to silently reduce the value by one. Reviewed-by: Viktor Dukhovni <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from #27870) (cherry picked from commit d6510d9)

t8m · 2025-08-13T09:30:13Z

Merged to all the active branches. Thank you for your contribution.

In the case when no q parameter was given, the function generate_key in dh_key.c did create one bit too much, so the priv_key value was exceeding the DH group size q = (p-1)/2. When the length is used in this case the limit is also one bit too high, but for backward compatibility this limit was left as is, instead we have to silently reduce the value by one. Reviewed-by: Viktor Dukhovni <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from openssl#27870) (cherry picked from commit d6510d9)

bernd-edlinger added branch: master Applies to master branch branch: 3.0 Applies to openssl-3.0 branch branch: 3.2 Applies to openssl-3.2 (EOL) branch: 3.3 Applies to openssl-3.3 branch: 3.4 Applies to openssl-3.4 branch: 3.5 Applies to openssl-3.5 labels Jun 21, 2025

paulidale previously approved these changes Jun 23, 2025

View reviewed changes

slontis reviewed Jun 23, 2025

View reviewed changes

crypto/dh/dh_key.c Show resolved Hide resolved

bernd-edlinger dismissed paulidale’s stale review via 9106593 June 23, 2025 18:02

bernd-edlinger force-pushed the fix_dh_private_key_size branch from 58ce39e to 9106593 Compare June 23, 2025 18:02

kroeckx reviewed Jun 24, 2025

View reviewed changes

crypto/dh/dh_key.c Outdated Show resolved Hide resolved

t8m requested changes Jun 24, 2025

View reviewed changes

crypto/dh/dh_key.c Outdated Show resolved Hide resolved

crypto/dh/dh_key.c Outdated Show resolved Hide resolved

bernd-edlinger force-pushed the fix_dh_private_key_size branch from 9106593 to bf52c96 Compare June 24, 2025 12:16

bernd-edlinger force-pushed the fix_dh_private_key_size branch from bf52c96 to 2e96760 Compare June 24, 2025 12:27

t8m added approval: review pending This pull request needs review by a committer triaged: bug The issue/pr is/fixes a bug tests: exempted The PR is exempt from requirements for testing labels Jun 24, 2025

t8m approved these changes Jun 24, 2025

View reviewed changes

vdukhovni requested changes Jul 25, 2025

View reviewed changes

bernd-edlinger commented Jul 26, 2025

View reviewed changes

vdukhovni approved these changes Aug 8, 2025

View reviewed changes

bernd-edlinger added approval: done This pull request has the required number of approvals and removed approval: review pending This pull request needs review by a committer labels Aug 12, 2025

openssl-machine added approval: ready to merge The 24 hour grace period has passed, ready to merge and removed approval: done This pull request has the required number of approvals labels Aug 13, 2025

t8m closed this Aug 13, 2025

esyr mentioned this pull request Sep 15, 2025

[3.5] CHANGES.md, NEWS.md: update for 3.5.3 #28558

Closed

	/*
	* SP800-56Ar3 5.6.1.1.4 Key pair generation by testing candidates.
	* Generates a private key in the interval [1, min(2 ^ N - 1, q - 1)].
	*
	* ctx must be set up with a libctx (for fips mode).
	* params contains the FFC domain parameters p, q and g (for DH or DSA).
	* N is the maximum bit length of the generated private key,
	* s is the security strength.
	* priv_key is the returned private key,
	*/
	int ossl_ffc_generate_private_key(BN_CTX ctx, const FFC_PARAMS params,
	int N, int s, BIGNUM *priv)

Uh oh!

Comments

Conversation

bernd-edlinger commented Jun 21, 2025 • edited by vdukhovni Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kroeckx commented Jun 22, 2025

Uh oh!

kroeckx commented Jun 22, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bernd-edlinger commented Jun 24, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

openssl-machine commented Jul 25, 2025

Uh oh!

vdukhovni commented Jul 25, 2025

Uh oh!

vdukhovni Jul 25, 2025

Choose a reason for hiding this comment

Uh oh!

vdukhovni Jul 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bernd-edlinger Jul 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vdukhovni Jul 26, 2025

Choose a reason for hiding this comment

Uh oh!

bernd-edlinger Jul 26, 2025

Choose a reason for hiding this comment

Uh oh!

bernd-edlinger commented Jul 26, 2025

Uh oh!

bernd-edlinger Jul 26, 2025

Choose a reason for hiding this comment

Uh oh!

vdukhovni Jul 26, 2025

Choose a reason for hiding this comment

Uh oh!

openssl-machine commented Aug 13, 2025

Uh oh!

t8m commented Aug 13, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

bernd-edlinger commented Jun 21, 2025 •

edited by vdukhovni

Loading

bernd-edlinger commented Jun 24, 2025 •

edited

Loading

vdukhovni Jul 25, 2025 •

edited

Loading

bernd-edlinger Jul 26, 2025 •

edited

Loading