OTC VOTE: EVP_PKEY private/public key components

Mon Nov 16 19:09:25 UTC 2020

I will only answer what I see as new points in your last email, to
avoid repeating ourselves.

Validity of a serialized key:
- ASN.1 validity says little about the validity of the key, as ASN.1
cannot enforce limits on the private scalar range
- validity as a serialized EC key requires that in addition to be
valid ASN.1, other criteria are satisfied:
  - (this is assuming a named curve, with explicit parameters things
get more involved, as we need to validate those before looking at
private and public components)
  - private scalar is in the prescribed range for the curve
  - if optional public component is present, the public key encoding
matches the SECG standard in one of the supported compression formats
  - if optional public component is present, the public key point
belongs to the curve
  - if optional public component is present, the public key point
belongs to the prime subgroup of the curve (this collapses into the
previous point only if the cofactor for this curve is 1)
  - if optional public component is present, the public key point matches `k*G`

I confirm what you saw in your experiments, the validity checks (if
invoked!) catch these corner cases (I did similar experiments when
preparing the EC part of #13359).

The fact that you had to alter `ec_key_simple_check_key()` to skip the
public component validation, which is necessary also in 1.1.1 and
earlier, is the reason why I raised this side discussion on key
validation, as disproving the "lack of enforcement" argument: but I
posted this on the public openssl-project list only after verifying we
did not have gaping security holes.

Nicola

On Mon, Nov 16, 2020 at 8:51 PM Richard Levitte <levitte at openssl.org> wrote:
>
> This is what I read:
>
> - the key in p256_invalid.pem is invalid in other ways than merely the
>   lack of the public key in the file.
>   (the public key is *not* lacking in run-time in this example, since
>   d2i_ECPrivateKey() autogenerates it, which happens before it's
>   checked or used)
>
> - you confirmed that the public key isn't really relevant for this
>   problem, apart from triggering a check error that's really emanating
>   from some other invalid data.
>
> This does not, however, demonstrate what happens when the EVP_PKEY
> holds an EC_KEY that lacks a public key, because in run-time, it in
> fact does *not* lack a public key.  So while that's an interesting
> discussion, it doesn't really demonstrate your concerns about this
> vote.
>
> BTW, regarding checking, I did a bit of an experiment; I removed the
> autogeneration of the public key from d2i_ECPrivateKey(), and relaxed
> ec_key_simple_check_key() so it only checks eckey->pub_key if it's
> actually present...  and of course removeed a few eckey->pub_key NULL
> checks along the way.  EVP_PKEY_check still fails, but now with the
> detailed error "wrong order", which sounds perfectly reasonable
> considering your description, so it looks to me like the invalidity
> of the key can be caught either way.
>
> From a contents point of view, p256_invalid.pem is actually perfectly
> valid, or you would have gotten ASN1 errors when trying to load it.
>
> Cheers,
> Richard
>
> P.S.  I'd like to pause the debate at this point...  it looks like
> we're getting back into locked positions, and I'm not keen on
> continuing under those conditions.
>
> On Mon, 16 Nov 2020 19:06:51 +0100,
> Nicola Tuveri wrote:
> >
> > The issue with that key is that the secret scalar `k` is equal to `n`
> > (where `n` is the order of the generator point `G`), while for EC keys
> > the validity range is `1 <= k < n`.
> >
> > If the scalar `k` is equal to `n`, it means that the associated pubkey
> > is `k*G` = `n*G` = `0*G mod n` = `P_infinity`.
> > The pubkey generation in the `d2i_` routines is correctly being
> > triggered because the PEM file I generated only includes the secret
> > scalar: if we did not catch the point at infinity validating the
> > public component we would reach the private component validity checks
> > and we would trigger the private scalar range check.
> >
> > The infinite loop happens not because of the public component (that as
> > we know is not touched during signature generation) but because the
> > secret scalar is effectively congruent to `0 mod n` in the computation
> > to generate the `s` value of the signature.
> >
> > I would not classify this as a bug, but as a programmer error: the
> > user is using an invalid key (this has nothing to do with the "keypair
> > assumption", literally `k` is a value out of range according to the
> > relevant spec).
> > Input key material should be validated: if not at each run (for
> > performance reason), once after it has been serialized to disk and
> > protected with proper measures to ensure the validated key material is
> > not tampered with (or leaked).
> >
> >
> > If we consider this a bug, or a potential DoS attack vector, we would
> > likely fix it by running validation of the `EVP_PKEY` object on load
> > (and with some caching mechanism to validate keys created manually via
> > `EC_KEY` objects): this would once again reveal that the use pattern
> > in #12612 was invalid to begin with, as the validity checks were
> > enforcing the "keypair assumption" in 1.1.1 and previous versions.
> >
> >
> > Nicola
> >
> > On Mon, Nov 16, 2020 at 7:44 PM Richard Levitte <levitte at openssl.org> wrote:
> > >
> > > Er, Nicola, I'm unsure how that endless loop has anything to do with
> > > the presence or the absence of a public key, as it happens in
> > > ossl_ecdsa_sign_sig(), which doesn't even look at the public key, at
> > > all.
> > >
> > > Your check does say that the key you have there is invalid, but that
> > > would rather be because from that private key and group, it seems that
> > > d2i_ECPrivateKey() generates a public key with Z == 0, which is indeed
> > > infinity as I understand it.  You can see that for yourself with a
> > > breakpoint at d2i_ECPrivateKey(), step down to about line 1042
> > > (current OpenSSL_1_1_1-stable, btw), and simply look:
> > >
> > >     (gdb) p *ret->pub_key
> > >     $16 = {meth = 0x7ffff7f0dc00 <ret>, curve_name = 415, X = 0x5555556450f0,
> > >       Y = 0x555555645090, Z = 0x5555556450b0, Z_is_one = 0}
> > >     (gdb) p *ret->pub_key->Z
> > >     $17 = {d = 0x555555641170, top = 0, dmax = 4, neg = 0, flags = 1}
> > >     (gdb) p *ret->pub_key->X
> > >     $18 = {d = 0x555555641ec0, top = 4, dmax = 4, neg = 0, flags = 1}
> > >     (gdb) p *ret->pub_key->Y
> > >     $19 = {d = 0x555555641e40, top = 4, dmax = 4, neg = 0, flags = 1}
> > >
> > > (ret->pub_key->Z->top == 0, that's a bignum zero)
> > >
> > > That still has no impact on the infinite loop as far as I can see, but
> > > that may be an indication that something else is wrong with that
> > > private key.
> > >
> > > It's also possible that if there are conditions that may cause an
> > > infinite loop, that is a bug in itself that needs a fix.
> > >
> > > I believe this loop is due for a raised issue, unless there already is
> > > one.
> > > (if there isn't, I wonder why)
> > >
> > > Cheers,
> > > Richard
> > >
> > > On Thu, 12 Nov 2020 11:33:13 +0100,
> > > Nicola Tuveri wrote:
> > > >
> > > > > Nonsense.  Each iteration involves a new PRN, which by definition you cannot predict.
> > > >
> > > > ~~~sh
> > > > ; which openssl; openssl version
> > > > /usr/bin/openssl
> > > > OpenSSL 1.1.1f  31 Mar 2020
> > > > ; cat > /tmp/p256_invalid.pem
> > > > -----BEGIN PRIVATE KEY-----
> > > > MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCD/////AAAAAP//////
> > > > ////vOb6racXnoTzucrC/GMlUQ==
> > > > -----END PRIVATE KEY-----
> > > > ; openssl pkey -check -text -noout -in /tmp/p256_invalid.pem
> > > > Key is invalid
> > > > Detailed error: point at infinity
> > > > Private-Key: (256 bit)
> > > > priv:
> > > >     ff:ff:ff:ff:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:
> > > >     ff:bc:e6:fa:ad:a7:17:9e:84:f3:b9:ca:c2:fc:63:
> > > >     25:51
> > > > pub:
> > > >     00
> > > > ASN1 OID: prime256v1
> > > > NIST CURVE: P-256
> > > > ; dd if=/dev/zero of=/tmp/foo.hash bs=1 count=32
> > > > ; openssl pkeyutl -sign -inkey /tmp/p256_invalid.pem -in /tmp/foo.hash
> > > > -out /tmp/sig.der
> > > > # here is the infinite loop
> > > > ~~~
> > >
> > > --
> > > Richard Levitte         levitte at openssl.org
> > > OpenSSL Project         http://www.openssl.org/~levitte/
> >
> --
> Richard Levitte         levitte at openssl.org
> OpenSSL Project         http://www.openssl.org/~levitte/