OTC VOTE: EVP_PKEY private/public key components

[Nicola Tuveri]

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/