X509Chain.Build() fails to find path to root when there are cross-signed intermediate certificates (Linux only)

[shaan1337]

Description

in a configuration like this where all certificates and chains are valid/NOT expired:

root1 o   o root2  (root1 & root2 have different subjects & public keys)
      |   |
int1  o   o int2   (int1 & int2 have same subject/public key)
       \ /
        v
        o   leaf

chain building fails on linux with this X509Chain configuration:

          o root2
          |
int1  o   o int2
       \ /
        v
        o   leaf

but succeeds with this X509Chain configuration:

          o root2
          |
          o int2
         /
        /
        o   leaf

Reproduction Steps

Run the attached tests. They pass on windows but fail on linux.

An example with real let's encrypt certificates has been included, very similar to the following: (image source: https://scotthelme.co.uk/cross-signing-alternate-trust-paths-how-they-work/)

Note that time validity has been disabled for the let's encrypt tests as one of the intermediates signed by DST Root CA X3 has already expired (however, the problem still exists with certificates that haven't expired as shown by the other test)

Expected behavior

Chain building should succeed when there are multiple equivalent intermediate certificates (sharing the same public key) and a valid chain to the root. It appears that only one path is considered when there are multiple possible paths.

Actual behavior

Chain building fails with PartialChain. However, it succeeds when excluding one of the equivalent intermediate certificates.

Regression?

No response

Known Workarounds

When chain building fails with PartialChain, re-run chain building, excluding some of the intermediate certificates. However, this is not an efficient workaround. there may be many possibilities if there are many intermediates/multiple intermediate levels.

Configuration

.NET: 8.0.100 OS: Ubuntu 22.04 Architecture: x64

It is specific to linux. openssl version: OpenSSL 3.0.2 15 Mar 2022 (Library: OpenSSL 3.0.2 15 Mar 2022)

Other information

It seems to be a different issue to: https://github.com/dotnet/runtime/issues/31569 https://github.com/dotnet/runtime/issues/43884

[ghost]

Tagging subscribers to this area: @dotnet/area-system-security, @bartonjs, @vcsjones See info in area-owners.md if you want to be subscribed.

Issue Details

---

### Description ``` in a configuration like this where all certificates and chains are valid/NOT expired: root1 o o root2 (root1 & root2 have different subjects & public keys) | | int1 o o int2 (int1 & int2 have same subject/public key) \ / v o leaf chain building fails on linux with this configuration: o root2 | int1 o o int2 \ / v o leaf but succeeds with this configuration: o root2 | o int2 / / o leaf ``` ### Reproduction Steps Run the attached [tests](https://github.com/dotnet/runtime/files/14401837/x509.zip). They pass on windows but fail on linux. An example with real let's encrypt certificates has been included, very similar to the following:  (image source: https://scotthelme.co.uk/cross-signing-alternate-trust-paths-how-they-work/) Note that time validity has been disabled for the let's encrypt tests as one of the intermediates signed by `DST Root CA X3` has already expired (however, the problem still exists with certificates that haven't expired as shown by the other test) ### Expected behavior Chain building should succeed when there are multiple equivalent intermediate certificates (sharing the same public key) and a valid chain to the root. It appears that only one path is considered when there are multiple possible paths. ### Actual behavior Chain building fails with `PartialChain`. However, it succeeds when excluding one of the equivalent intermediate certificates. ### Regression? _No response_ ### Known Workarounds When chain building fails with `PartialChain`, re-run chain building, excluding some of the intermediate certificates. However, this is not an efficient workaround. there may be many possibilities if there are many intermediates/multiple intermediate levels. ### Configuration .NET: 8.0.100 OS: Ubuntu 22.04 Architecture: x64 It is specific to linux. openssl version: OpenSSL 3.0.2 15 Mar 2022 (Library: OpenSSL 3.0.2 15 Mar 2022) ### Other information It seems to be a different issue to: https://github.com/dotnet/runtime/issues/31569 https://github.com/dotnet/runtime/issues/43884

Author:	shaan1337
Assignees:	-
Labels:	`area-System.Security`, `untriaged`
Milestone:	-

[vcsjones]

The two intermediates in the Let's Encrypt case have the same subject, public key, and subject key identifier.

The failure is a known behavior with OpenSSL and is documented here https://github.com/openssl/openssl/issues/18708. Once it finds a certificate chain with a matching subject and issuer plus key identifiers, OpenSSL assumes "that" is the chain, even if using a different intermediate would result in a more successful chain build.

We can reproduce this from the command line. From the letsencrypt directory:

openssl verify -no-CAstore -no-CAfile -no-CApath -trusted dstrootcax3.pem -untrusted r3_isrg.pem -untrusted r3_dst.pem -no_check_time letsencrypt.org.pem

That will fail.

Switch the order of the -untrusted arguments, and a valid chain will be found.

[shaan1337]

@vcsjones hey, thanks for all the clarifications and the link!

to avoid any confusion for anyone reading: the issue also occurs when subject key identifiers/authority key identifiers are not present in the certificates (as per the custom test certificates)