OTC VOTE: EVP_PKEY private/public key components

Mon Nov 16 18:51:34 UTC 2020

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/