From:   Nicolai Stange <nstange@suse.de>
To:     Stephan =?utf-8?Q?M=C3=BCller?= <smueller@chronox.de>
Cc:     Herbert Xu <herbert@gondor.apana.org.au>,
        "David S. Miller" <davem@davemloft.net>,
        Nicolai Stange <nstange@suse.de>,
        Hannes Reinecke <hare@suse.de>, Torsten Duwe <duwe@suse.de>,
        Zaibo Xu <xuzaibo@huawei.com>,
        Giovanni Cabiddu <giovanni.cabiddu@intel.com>,
        David Howells <dhowells@redhat.com>,
        Jarkko Sakkinen <jarkko@kernel.org>,
        linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org,
        qat-linux@intel.com, keyrings@vger.kernel.org
Subject: Re: [PATCH 16/18] crypto: dh - calculate Q from P for the full public key verification
References: <20211201004858.19831-1-nstange@suse.de>
        <20211201004858.19831-17-nstange@suse.de>
        <4182894.UPlyArG6xL@positron.chronox.de>
Date:   Wed, 08 Dec 2021 07:41:22 +0100
In-Reply-To: <4182894.UPlyArG6xL@positron.chronox.de> ("Stephan
 \=\?utf-8\?Q\?M\=C3\=BCller\=22's\?\=
        message of "Sun, 05 Dec 2021 07:07:11 +0100")
Message-ID: <878rwvegz1.fsf@suse.de>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

Stephan M=C3=BCller <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.
>>=20
>> However, for safe-prime groups, Q =3D (P - 1)/2 by definition and this
>> enables dh_is_pubkey_valid() to calculate Q on the fly for these groups.
>> Implement this.
>>=20
>> With this change, the last code accessing struct dh_ctx's ->q is now gon=
e.
>> Remove this member from struct dh_ctx.
>
> Isn't it expensive to always calculate Q for a-priori known values? Why n=
ot=20
> 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=
=20
> following lines.
>
> [1] https://github.com/smuellerDD/acvpparser/blob/master/parser/
> safeprimes.h#L346
>
> Ciao
> Stephan
>
>

--=20
SUSE Software Solutions Germany GmbH, Maxfeldstr. 5, 90409 N=C3=BCrnberg, G=
ermany
(HRB 36809, AG N=C3=BCrnberg), GF: Ivo Totev