diff mbox series

[16/18] crypto: dh - calculate Q from P for the full public key verification

Message ID 20211201004858.19831-17-nstange@suse.de (mailing list archive)
State New
Headers show
Series crypto: dh - infrastructure for NVM in-band auth and FIPS conformance | expand

Commit Message

Nicolai Stange Dec. 1, 2021, 12:48 a.m. UTC
As the ->q in struct dh_ctx gets never set anywhere, the code
in dh_is_pubkey_valid() for doing the full public key validation in
accordance to SP800-56Arev3 is effectively dead.

However, for safe-prime groups, Q = (P - 1)/2 by definition and this
enables dh_is_pubkey_valid() to calculate Q on the fly for these groups.
Implement this.

With this change, the last code accessing struct dh_ctx's ->q is now gone.
Remove this member from struct dh_ctx.

Signed-off-by: Nicolai Stange <nstange@suse.de>
---
 crypto/dh.c | 40 +++++++++++++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 11 deletions(-)

Comments

Hannes Reinecke Dec. 1, 2021, 7:33 a.m. UTC | #1
On 12/1/21 1:48 AM, Nicolai Stange wrote:
> As the ->q in struct dh_ctx gets never set anywhere, the code
> in dh_is_pubkey_valid() for doing the full public key validation in
> accordance to SP800-56Arev3 is effectively dead.
> 
> However, for safe-prime groups, Q = (P - 1)/2 by definition and this
> enables dh_is_pubkey_valid() to calculate Q on the fly for these groups.
> Implement this.
> 
> With this change, the last code accessing struct dh_ctx's ->q is now gone.
> Remove this member from struct dh_ctx.
> 
> Signed-off-by: Nicolai Stange <nstange@suse.de>
> ---
>   crypto/dh.c | 40 +++++++++++++++++++++++++++++-----------
>   1 file changed, 29 insertions(+), 11 deletions(-)
> Reviewed-by: Hannes Reinecke <hare@suse.de>

Cheers,

Hannes
Stephan Mueller Dec. 5, 2021, 6:07 a.m. UTC | #2
Am Mittwoch, 1. Dezember 2021, 01:48:56 CET schrieb Nicolai Stange:

Hi Nicolai,

> As the ->q in struct dh_ctx gets never set anywhere, the code
> in dh_is_pubkey_valid() for doing the full public key validation in
> accordance to SP800-56Arev3 is effectively dead.
> 
> However, for safe-prime groups, Q = (P - 1)/2 by definition and this
> enables dh_is_pubkey_valid() to calculate Q on the fly for these groups.
> Implement this.
> 
> With this change, the last code accessing struct dh_ctx's ->q is now gone.
> Remove this member from struct dh_ctx.

Isn't it expensive to always calculate Q for a-priori known values? Why not 
add Q to the safe-prime definitions and do not do this operation here?

If you need Q for all of those safe-primes, you may get them from [1] and 
following lines.

[1] https://github.com/smuellerDD/acvpparser/blob/master/parser/
safeprimes.h#L346

Ciao
Stephan
Nicolai Stange Dec. 8, 2021, 6:41 a.m. UTC | #3
Stephan Müller <smueller@chronox.de> writes:

> Am Mittwoch, 1. Dezember 2021, 01:48:56 CET schrieb Nicolai Stange:
>
>> As the ->q in struct dh_ctx gets never set anywhere, the code
>> in dh_is_pubkey_valid() for doing the full public key validation in
>> accordance to SP800-56Arev3 is effectively dead.
>> 
>> However, for safe-prime groups, Q = (P - 1)/2 by definition and this
>> enables dh_is_pubkey_valid() to calculate Q on the fly for these groups.
>> Implement this.
>> 
>> With this change, the last code accessing struct dh_ctx's ->q is now gone.
>> Remove this member from struct dh_ctx.
>
> Isn't it expensive to always calculate Q for a-priori known values? Why not 
> add Q to the safe-prime definitions and do not do this operation here?

I actually considered this when writing the patch: it's basically a
time-memory tradeoff and I opted for time here. The reason is that I'd
expect the rather trivial Q calculation to be negligible when compared
to the subsequent mpi_powm() operation in dh_is_pubkey_valid(). OTOH, as
the size of Q is (almost) equal to that of P, the space needed for
storing all the the individual groups' precomputed Qs would be
significant. So I'd say let's wait and see whether the dynamic Q
calculation does actually show up in profiles before thinking about
optimizations like e.g. precomputations.

Thanks,

Nicolai

>
> If you need Q for all of those safe-primes, you may get them from [1] and 
> following lines.
>
> [1] https://github.com/smuellerDD/acvpparser/blob/master/parser/
> safeprimes.h#L346
>
> Ciao
> Stephan
>
>
diff mbox series

Patch

diff --git a/crypto/dh.c b/crypto/dh.c
index 38547c5301da..21de91a87ea5 100644
--- a/crypto/dh.c
+++ b/crypto/dh.c
@@ -15,7 +15,6 @@ 
 struct dh_ctx {
 	enum dh_group_id group_id;
 	MPI p;	/* Value is guaranteed to be set. */
-	MPI q;	/* Value is optional. */
 	MPI g;	/* Value is guaranteed to be set. */
 	MPI xa;	/* Value is guaranteed to be set. */
 };
@@ -23,7 +22,6 @@  struct dh_ctx {
 static void dh_clear_ctx(struct dh_ctx *ctx)
 {
 	mpi_free(ctx->p);
-	mpi_free(ctx->q);
 	mpi_free(ctx->g);
 	mpi_free(ctx->xa);
 	memset(ctx, 0, sizeof(*ctx));
@@ -114,11 +112,12 @@  static int dh_set_secret(struct crypto_kpp *tfm, const void *buf,
 /*
  * SP800-56A public key verification:
  *
- * * If Q is provided as part of the domain paramenters, a full validation
- *   according to SP800-56A section 5.6.2.3.1 is performed.
+ * * For safe-prime groups, Q can be computed trivially from P and a
+ *   full validation according to SP800-56A section 5.6.2.3.1 is
+ *   performed.
  *
- * * If Q is not provided, a partial validation according to SP800-56A section
- *   5.6.2.3.2 is performed.
+ * * For all other sets of group parameters, only a partial validation
+ *   according to SP800-56A section 5.6.2.3.2 is performed.
  */
 static int dh_is_pubkey_valid(struct dh_ctx *ctx, MPI y)
 {
@@ -129,21 +128,40 @@  static int dh_is_pubkey_valid(struct dh_ctx *ctx, MPI y)
 	 * Step 1: Verify that 2 <= y <= p - 2.
 	 *
 	 * The upper limit check is actually y < p instead of y < p - 1
-	 * as the mpi_sub_ui function is yet missing.
+	 * in order to save one mpi_sub_ui() invocation here. Note that
+	 * p - 1 is the non-trivial element of the subgroup of order 2 and
+	 * thus, the check on y^q below would fail if y == p - 1.
 	 */
 	if (mpi_cmp_ui(y, 1) < 1 || mpi_cmp(y, ctx->p) >= 0)
 		return -EINVAL;
 
-	/* Step 2: Verify that 1 = y^q mod p */
-	if (ctx->q) {
-		MPI val = mpi_alloc(0);
+	/*
+	 * Step 2: Verify that 1 = y^q mod p
+	 *
+	 * For the safe-prime groups q = (p - 1)/2.
+	 */
+	if (ctx->group_id != dh_group_id_unknown) {
+		MPI val, q;
 		int ret;
 
+		val = mpi_alloc(0);
 		if (!val)
 			return -ENOMEM;
 
-		ret = mpi_powm(val, y, ctx->q, ctx->p);
+		q = mpi_alloc(mpi_get_nlimbs(ctx->p));
+		if (!q) {
+			mpi_free(val);
+			return -ENOMEM;
+		}
+
+		/*
+		 * ->p is odd, so no need to explicitly subtract one
+		 * from it before shifting to the right.
+		 */
+		mpi_rshift(q, ctx->p, 1);
 
+		ret = mpi_powm(val, y, q, ctx->p);
+		mpi_free(q);
 		if (ret) {
 			mpi_free(val);
 			return ret;