Subject: Re: [Openpgp-dt] Follow-up on key validation checks

From: Justus Winter <[email-masked]>
Date: Tue, 05 Oct 2021 13:49:25 +0200

Hi Daniel :)

Daniel Huigens <d.huigens=[email-masked]> writes:

> As I promised in the meeting, here are some links to the key validation
> checks Lara Bruseghini implemented to thwart the attacks she described
> in the presentation at IETF 110, the slides of which are here:

Thanks!

> In OpenPGP.js:
>
> https://github.com/openpgpjs/openpgpjs/blob/fc42c38706e5b38f2dd3ef3072200eb56facaefd/src/crypto/crypto.js#L296-L341

To summarize: Arithmetic methods for RSA, DSA, and ElGamal.  Deriving the
public key from the secret one for ECDH, and EdDSA.  Trial signing and
verification for ECDSA.

> And in gopenpgp / go-crypto:
>
> https://github.com/ProtonMail/go-crypto/blob/52430bf6b52c07ea562b0263080aa6c4ebd78d28/openpgp/packet/private_key.go#L663-L780
>
> RSA key validation is missing there, as it's already implemented here:
>
> https://github.com/golang/go/blob/6d02ce85840fb7a1a9239d02e02710a008b1657a/src/crypto/rsa/rsa.go#L201-L237

To summarize: Arithmetic methods for RSA, DSA, and ElGamal.  Deriving the
public key from the secret one for ECDH, EdDSA, and ECDSA.

My questions:

  - Why is there a difference for ECDSA?
  - The arithmetic methods seem involved, why are trial operations not
    sufficient?

> In gopenpgp, we run these checks whenever we parse any private key
> material (after decryption or not) for simplicity.
>
> In OpenPGP.js we try to be more clever; for performance we only validate
> the key after decryption; and not when parsing an unencrypted private
> key, since then the private key material is not "trusted", and
> hopefully the application encrypted + authenticated the key in its
> entirety using some other method.
>
> Also, if there's a non-gnu-dummy primary key, then it's sufficient to
> validate only that one, as it signs all the public subkey material.
> Or, if there's a non-dummy signing subkey, it's sufficient to validate
> only that one, as it signs the primary public key which signs all other
> subkeys. So, we always just fetch the signing key, check if it's dummy,
> and if not validate only that one. If there are no non-dummy signing
> key packets, then we have to validate all key packets. See:
>
> https://github.com/openpgpjs/openpgpjs/blob/fc42c38706e5b38f2dd3ef3072200eb56facaefd/src/key/private_key.js#L113-L154

I'm curious about the performance impact of the validation.  You
certainly seem to worry about that enough for these optimizations.  But,
with the exception of the ElGamal method (which contains a loop), the
arithmetic operations don't look that expensive (then again, I'm not an
expert on the math).  Re-deriving the public key on the curves seems
cheap.  The trial signing is a bit more expensive, but could be avoided
as done in gopenpgp.

> Btw, we will also soon (finally) have a pre-release of the paper to
> share, which also describes these checks, but I imagine that for this
> group being able to look at some code may be more valuable.

Looking forward to this!

Ah, and a small thing I noticed:

https://github.com/ProtonMail/go-crypto/blob/52430bf6b52c07ea562b0263080aa6c4ebd78d28/openpgp/packet/private_key.go#L766

and

https://github.com/openpgpjs/openpgpjs/blob/fc42c38706e5b38f2dd3ef3072200eb56facaefd/src/crypto/public_key/elgamal.js#L120

both do 2 << 17 which seems like an odd way to say 1 << 18.  Is that
code correct?

Thanks,
Justus

---

From: Daniel Huigens <[email-masked]>
Date: Thu, 07 Oct 2021 14:55:08 +0000

Hi Justus :)

>   - Why is there a difference for ECDSA?

On the web platform specifically, in the case of ECDSA, doing a trial
signature and verification is done using native Web Crypto, and is thus
faster and more secure than re-deriving the public key in JS (which
would not be constant-time, for example). On most other platforms,
re-deriving the public key will be faster, so we recommend doing that.

>   - The arithmetic methods seem involved, why are trial operations not

We used to only do a trial signature and verification, but in certain
cases, it opens up the possibility of other attacks. We'll give some
details in the paper. But in general, re-deriving the public key is the
most straightforward and secure solution, wherever possible.

> cheap.  The trial signing is a bit more expensive, but could be avoided

ElGamal is indeed most expensive, DSA is also expensive given the need
for a strong primality check. Though to be perfectly honest, since
we're trying to phase out support for these anyway (e.g., OpenPGP.js v5
no longer accepts DSA and ElGamal keys by default), it's indeed perhaps
not as much of a concern.

In general, part of the reason I was worried about it for OpenPGP.js and
gopenpgp is because they don't have a concept of a keyring, and so the
key is potentially "imported" quite often. For an implementation with a
trusted keystore (which authenticates the public key), running a slow
check on import may be less prohibitive. Anyway, AEAD-encrypted private
keys should also solve any performance concerns.

> both do 2 << 17 which seems like an odd way to say 1 << 18.  Is that

Yeah, it's intended to calculate 2**18 - but maybe it would be clearer
to write that, instead.

Best,
Daniel