openssl: OpenSSL 3.0.0-alpha6 6 Aug 2020 breaks perl Net::DNS::SEC ECDSA signature generation

Pleased to confirm that a build of a fresh master has resolved this issue.

Thanks everybody

I assume you tested with your reproducer (which I just discovered)?

Yes. Working on a fix now.

Seen from a different angle, RFC 5915 specifies the ASN.1 key format like this in chapter 3:

   ECPrivateKey ::= SEQUENCE {
     version        INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
     privateKey     OCTET STRING,
     parameters [0] ECParameters {{ NamedCurve }} OPTIONAL,
     publicKey  [1] BIT STRING OPTIONAL
   }

Do note the optional publickey. This is the structure that we’ll get from a PEM file with the header “-----BEGIN EC PRIVATE KEY-----”.

So it seems that the rather stringent import of EC keys specifically actually violates this standard.

My understanding of the situtation:

• It’s been documented since at least 2006 that for EVP_PKEY a private key requires the public key. Note that I talk about EVP_PKEY, and not some ECDSA or other API.
• When OpenSSL reads one of the various file formats it supports to read a private key and it does not contain the public key, it will calculate the public key.
• You have your own file format, parses it yourself, and use an EC_KEY API, and then convert it to an EVP_PKEY.
• Calculating the public key from the private key can be a 1 time cost. You do not need to calculate it each time you want to sign something. You can load the key 1 time, and then sign with that key multiple times.
• We did not enforce our documented behaviour, and as we all know, what the documentation says is irrelevant if you don’t enforce it because there will always be people who rely on undocumented behaviour.
• A new design was made with new functionality that now enforce previously documented behaviour at a point where we don’t know yet how the key is going to be used.

The questions I have are:

• How many people rely on that undocumented behaviour that contradicted the documented behaviour, and is that enough to do something about it?
• If we do something about it, which of the various solutions has the least potential to cause issues?

I believe I do have a good reason. DNS zone signing requires the private key only (a large random integer for ECDSA and EdDSA). The public key is generated once, published in DNS, and used by (many) remote DNSSEC resolvers to verify the signatures.

I did not meant to imply that your specific use-case is not relevant, but rather that we have to balance it with the expectations of other users.

Imposing a performance penalty of about 100%, simply to conform to your ideological insistence on key-pairs, does not represent good value for computational cycles.

Having a dedicated function that loads a private key intentionally omitting the computation of the missing public component would be a way to avoid the extra cost: you would be able to keep using the pattern that accidentally worked in 1.1.1 despite the documentation stating otherwise. What I am arguing is that the function to create a “private-only keypair” should be named appropriately, to discourage less savvy users from picking it without realizing that the returned object imposes extra limits and caveats compared to an object containing a full keypair.

Worse, the unnecessary computation exposes the private key to possible side-channel attacks every time the private key is used.

This is exactly one of the drawbacks of not saving the public component with the private key!

OpenSSL is a cryptographic library that supports many uses, not just this DNSSEC pattern: while in your use case it makes perfectly sense to disregard the absence of the public component (because the user is taking the responsibility of guaranteeing that only operations with no use for the public component will be executed on the loaded key object), this is not the safest approach for generic use.

Users can expect that loading a private key (that inherently reveals knowledge of the public key) results in an object that can run operations that require either the private component or the public component.

All you have to do to get an answer is to look at RFC 5915:

@levitte as I said the last time you quoted the ASN.1 from RFC 5915, if you keep reading a few more paragraphs, you will find:

   o  publicKey contains the elliptic curve public key associated with
      the private key in question.  The format of the public key is
      specified in Section 2.2 of [RFC5480].  Though the ASN.1 indicates
      publicKey is OPTIONAL, implementations that conform to this
      document SHOULD always include the publicKey field.  The publicKey
      field can be omitted when the public key has been distributed via
      another mechanism, which is beyond the scope of this document.
      Given the private key and the parameters, the public key can
      always be recomputed; this field exists as a convenience to the
      consumer.

which paints a different picture. The “other standard” that Shane was looking for is in fact the same document – you must set the public key, unless you have a specific reason to not set it.

I can’t shed much light on the development history, but yes, as @levitte mentioned the field is optional in the standard encoding, and openssl is not the only library that computes the potentially missing public component at load time.

The reason why openssl (and forks) and other libraries do it is not really mentioned explicitly, but my understanding is that it seemed wise given that the library cannot possibly know in advance if after creation the object is going to be used for an operation that requires the public component or not.

Given that it was always possible to compute the public component from the private, that it is perfectly admissible that a user might want to compute a public key result when it only has been given an encoding without the optional public component from a third party keygen, it seemed more robust to generate the public component on missing at load time (which is usually already a slow operation anyway, and users tend to do load once, reuse many for static keys). The alternatives would have been to do it “on demand”, if a pub key result is needed from a key object missing the pub component, or to throw an error.

The latter can be seen by many users as a error, or missing functionality: all the information to compute the result is indeed available and there is no reason for the application/library not to perform the pubkey operation given a perfectly valid encoding of a key pair that omits the public component.

The “on demand” solution has several drawbacks, each with different priority depending on the hat you are wearing when thinking of them:

• from a API pov, a public key operation that is not keygen should never alter the key object in any of its components, so you either make the API non-const intentionally (and that opens another can of worms) or you can’t cache the pub component for later reuses
• generating the pub component from the private key and parameters is generally the most expensive operation of the whole cryptosystem (yes, it can be optimized somewhat for fixed generators and other assumptions, so there might be affine operations that are even slower, but bear with me) so you either trash the performance of applications by recomputing this and throwing it away if you can’t cache it inside the key object or you trash the performance of the first such operation
• if you can’t cache, repeating the operation that retrieves the public component from the private component, over and over, will give attackers a lot of ideal traces and it’s a huge security risk for both sw and hw implementations

So… I tend to think that, although admissible because the standards say so, in general encodings that omit the public component are a potential risk, don’t really have big benefits because storage and bandwidth is cheap (and this specific case is EC, so we are in the realm of very few bytes anyway, not huge FF keys), and that it is a good idea for libraries to ensure that their internal representation is always a key pair at load/init/keygen time and deal with keypairs or pub keys anywhere else than those critical sections.

On Thu, 8 Oct 2020 at 09:51, Billy Brumley notifications@github.com wrote:

After reading this thread, my vote does not count but I feel Option (2) is the way to go.

My team fuzzed so many libraries, so many different cryptosystems with various degrees of missing parameters. And various security implications of the results.

But in the wild we never found a private key that didn’t also include the public key. (Unless the key format does not support it – e.g. PVK DSA keys if I recall.)

So I feel like any “you’re wasting cycles” arguments really don’t have any teeth because such persisted keys, as far as our research told us, are rare at best.

This is far from being a “rare case”.

The ISC BIND keygen utility, widely used in DNSSEC circles, creates TWO files.

Kexample.com.+013+39400.private Private-key-format: v1.3 Algorithm: 13 (ECDSAP256SHA256) PrivateKey: cijBNlj+NRWvSg7+z+/4uIZHBJudq91LIGcZz9v7jUk= Created: 20201008102814 Publish: 20201008102814 Activate: 20201008102814

Kexample.com.+013+39400.key ; This is a zone-signing key, keyid 39400, for example.com. ; Created: 20201008102814 (Thu Oct 8 11:28:14 2020) ; Publish: 20201008102814 (Thu Oct 8 11:28:14 2020) ; Activate: 20201008102814 (Thu Oct 8 11:28:14 2020) example.com. IN DNSKEY 256 3 13 7S9GUAvpsI0bi7swn0OVQz92ZX1FajTT/dZhrDTIt/rgQbVCysLZLF5t htHQWn5I9OdtPIurWbjoHFmk8j9GSg==

Note

1. The private key contains neither the public key nor the EC parameters needed to create it.

2. The private key can be stored without knowledge of the EC curve with which it will be used.

3. Montgomery multiplication is computationally expensive. The “wasted cycles” massively outweigh the trivial cost of storing a 256-bit string.

4. Following the RFC5915 specification of an EC key would be the best solution in the long term. At the very least, everyone would know what the position is, and why it is what it is. The endless bickering and indecision could then stop.

—

You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/openssl/openssl/issues/12612#issuecomment-705427994, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABPJHP64BMOAKQQ2D5VBQQTSJV4RHANCNFSM4PYJRKFA .

But in the wild we never found a private key that didn’t also include the public key. (Unless the key format does not support it – e.g. PVK DSA keys if I recall.)

Ah, right, that code generates the public part as well:

https://github.com/openssl/openssl/blob/5884b05109d124f4c69df3be112c177ac4959684/crypto/pem/pvkfmt.c#L286-L294

After reading this thread, my vote does not count but I feel Option (2) is the way to go.

My team fuzzed so many libraries, so many different cryptosystems with various degrees of missing parameters. And various security implications of the results.

But in the wild we never found a private key that didn’t also include the public key. (Unless the key format does not support it – e.g. PVK DSA keys if I recall.)

So I feel like any “you’re wasting cycles” arguments really don’t have any teeth because such persisted keys, as far as our research told us, are rare at best.

Do note the optional publickey

FYI I’ve encoded almost all the ECC EVP KATs like this – e.g.

https://github.com/openssl/openssl/blob/master/test/recipes/30-test_evp_data/evppkey_ecc.txt

Otherwise, it’s not obvious how to do data driven tests on the key generation part of EVP. (“Does the public key compute from the private key? Yes because I parsed both from the same file” is not a very good test.)

bbrumley@emerald:/tmp$ cat priv.pem
-----BEGIN PRIVATE KEY-----
MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCDZE0NZiGAFJX6JQxumKTFRT+XFCQqJ
gHCUxmU2fRcn9Q==
-----END PRIVATE KEY-----
bbrumley@emerald:/tmp$ openssl asn1parse -in priv.pem 
    0:d=0  hl=2 l=  65 cons: SEQUENCE          
    2:d=1  hl=2 l=   1 prim: INTEGER           :00
    5:d=1  hl=2 l=  19 cons: SEQUENCE          
    7:d=2  hl=2 l=   7 prim: OBJECT            :id-ecPublicKey
   16:d=2  hl=2 l=   8 prim: OBJECT            :prime256v1
   26:d=1  hl=2 l=  39 prim: OCTET STRING      [HEX DUMP]:30250201010420D9134359886005257E89431BA62931514FE5C5090A89807094C665367D1727F5
bbrumley@emerald:/tmp$ openssl asn1parse -in priv.pem -strparse 26
    0:d=0  hl=2 l=  37 cons: SEQUENCE          
    2:d=1  hl=2 l=   1 prim: INTEGER           :01
    5:d=1  hl=2 l=  32 prim: OCTET STRING      [HEX DUMP]:D9134359886005257E89431BA62931514FE5C5090A89807094C665367D1727F5
bbrumley@emerald:/tmp$ 

This is a long thread and I’m not entirely sure what the root cause or solution is, but I’m just bringing it up now that, for EC keys, OpenSSL has always been tolerant to “private key with no public key” PEMs. The behavior we’ve seen in the past, is OpenSSL will compute and cache the public key when the PEM is parsed, whether the public half is needed or not. (Naturally – there’s no way for the lib to know what the application intends to do with the key after parsing.)

Also I understand that what a standard says about a PEM and how OpenSSL handles keys internally can be different – which is fine, and does not in itself imply compliance/noncompliance.

In the context of ECC, when we brought this issue up with you in … Aug 2019? Everyone seemed fine with that behavior – e.g. compute public key immediately if it’s missing when parsing the PEM.

OpenSSL is not alone in this strategy. We raised the same issue with BoringSSL, LibreSSL, and MbedTLS. All basically said “yea that’s by design” with various reasoning, e.g. if you defer the computation until the public part might be needed, you can end up with a lot of duplicate computation across threads. (I don’t know enough about the application layer to confirm or refute that.)

My team went through various other cryptosystems / formats as part of our Certified SCA paper. EdDSA was conceptually similar, but standards wise even worse because apparently they started with an ASN1 structure for private keys that did not support a public key field at all, that got evidently deployed, then the RFC finalized with a different structure, leading to nice RFC 8410 wording like

   NOTE: There exist some private key import functions that have not
   picked up the new ASN.1 structure OneAsymmetricKey that is defined in
   [RFC7748].  This means that they will not accept a private key
   structure that contains the public key field.  This means a balancing
   act needs to be done between being able to do a consistency check on
   the key pair and widest ability to import the key.

I personally see no issues having just the private key material (+ parameters) when signing. For that operation, that’s actually all that’s needed. It’s also possible that this was considered in previous OpenSSL versions, and I simply glossed over that part. That means the list of possible combinations needs being expanded:

• Parameters
• [Parameters +] Public Key
• [Parameters +] Private Key
• [Parameters +] Public Key + Private Key

Any way, if this was working in 1.1.1, I would consider what’s detected here as a breaking change. That makes 1 the clear solution. In this particular situation, it looks to me like this condition is simply too much:

https://github.com/openssl/openssl/blob/28833f1465a2dd197f8df80a69095d1913e6e85e/providers/implementations/keymgmt/ec_kmgmt.c#L306-L308

@t8m said:

Can you actually have any other key type without the public key? I do not see it being possible for RSA or DSA keys.

Are you talking about code or concept? Conceptually, I can’t see anything saying you can’t just use d, and e, so conceptually speaking, it’s absolutely possible. In code, I can at least say that the provider-native importer is much more relaxed, it will simply take what it’s told (within tolerances) and not be terribly picky about combinations:

https://github.com/openssl/openssl/blob/28833f1465a2dd197f8df80a69095d1913e6e85e/providers/implementations/keymgmt/rsa_kmgmt.c#L151-L174

So, I was under the impression that in general for EVP keys the assumption is that a valid EVP_PKEY object always has the public key part, and optionally the private key part.

Nope. It may contain only domain (and other) parameters.

So, common combinations of components are:

• Parameters
• Parameters + public key
• Parameters + public key + private key

(it’s a common assumption that the private key contains the public key parts, so “public key + private key” is the same as “private key” in practice)