commit cb583e783500d92bbda9a850e43cd94df0b2d5e1
author David Benjamin <davidben@google.com> Fri Aug 11 18:37:18 2023 -0400
committer Boringssl LUCI CQ <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com> Tue Aug 15 22:15:47 2023 +0000
tree 6c96a38422d74d6bee12d599c0b76fea45d74708
parent 5edba0bcc9cf554d7a2539b31713b5cd66bff5fc

Default to q = (p-1)/2 for DH keygen

As with large p, q, or g in the preceding CL, an application that uses
Diffie-Hellman incorrectly could be given a large private key length.
Computing the public key and shared secret will then be very slow.

This matters for a (p, g)-only group, where q is unknown. One way or
another, we should bound or clamp dh->priv_length. The two relevant
specifications I could find are SP 800-56A Rev3 and PKCS#3. SP 800-56A
wants a value for q, so we'd need to fabricate one. I believe X9.42's
Diffie-Hellman formulation similarly expects an explicit q. PKCS#3 is
(p, g)-only and seems to match what OpenSSL does. In PKCS#3:

- DH groups have an optional l, such that 2^(l-1) <= p

- For keygen, if l was provided, pick 2^(l-1) <= x < 2^l. Otherwise,
  pick 0 < x < p-1

Our current q-less keygen behavior matches this, with
l = num_bits(p) - 1. Interestingly, the first constraint allows
l = num_bits(p), but doing so allows x >= p - 1! This is a bit odd and
will wrap around the multiplicative group.

OpenSSL 3.0 (but not 1.1.1) bounds l in their q-less path, and cites
PKCS#3's 2^(l-1) <= p in a comment. But their actual check doesn't match
and excludes num_bits(p). The two problems cancel each other out.

PKCS#3 is quite old and does not even discuss subgroups or safe primes,
only this uninspiring text:

> Some additional conditions on the choice of prime, base, and
> private-value length may well be taken into account in order to deter
> discrete logarithm computation. These security conditions fall outside
> the scope of this standard.

I'm thus not inclined to give the document much weight in 2023. SP
800-56A Rev3 is not ideal either. First, we must fabricate a value for
q. (p-1)/2 is most natural, though it assumes g indeed generates a
prime-order subgroup and not the whole multiplicative group.

The second annoyance with SP 800-56A Rev3 is its insistance on uniformly
selecting between [1, 2^N-1] instead of [0, 2^N-1] or [1, 2^N]. For all
plausible values of N, this difference will not matter, yet NIST
specifies rejection sampling, defeating the point of a power-of-two
bound.

None of these really matters. p should be large enough to make the
differences between all these schemes negligible. Since we want to
follow NIST for the (p, q, g) path, using the same scheme for the (p, g)
path seems the most reasonable. Thus this CL recasts that path from
PKCS#3 to SP 800-56A, except dh->priv_length is clamped before invoking
the algorithm, to avoid worrying about whether someone expects
DH_set_length(BN_num_bits(p)) to work.

Change-Id: I270f235a6f04c69f8abf59edeaf39d837e2c79f8
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/62228
Reviewed-by: Bob Beck <bbe@google.com>
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: David Benjamin <davidben@google.com>