| Message ID | 20211201004858.19831-17-nstange@suse.de |
|---|---|
| State | Superseded |
| Headers | show |
| Series | crypto: dh - infrastructure for NVM in-band auth and FIPS conformance | expand |
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
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
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 --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;
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(-)