Inquiry Regarding Firefox's Handling of Multiple CA Certificates in Chain Building

[bruce lee]

Dear Browser Development Team,

I am writing to inquire about the specific logic and algorithms employed by your browser when constructing certificate chains, particularly in scenarios involving multiple intermediate certificates. I am looking for a thorough explanation of the decision-making process and, if possible, the location of the relevant code within your codebase.

My specific area of interest is in how the browser handles situations where it encounters multiple potential intermediary certificates that could link to a given end-entity certificate, specifically:

Scenario: Consider an end-entity certificate "C". This certificate can potentially be linked to two intermediate certificates, "A" and "B".
Key and Subject Identity: Intermediate certificates "A" and "B" share the same private key and have the same subject name.
Field Differences: However, other fields within "A" and "B" are different (e.g., different validity periods, subject alternative names, extensions, etc.).

In such a case, end-entity certificate "C" could be successfully linked to either "A" or "B", resulting in two potential certificate chain paths.

My questions are:

1.  Selection Criteria: What specific criteria or properties does the browser prioritize when selecting between such multiple intermediate certificates with the same subject name and public key? Is this selection based on the most recently issued certificate, or the one with the longer validity period, or some other factors? Please provide a complete list of these criteria, ordered by priority.
2.  Algorithm: Could you describe the detailed algorithm (or pseudo-code) used by the browser when making this selection? I am interested in understanding the complete process flow.
3.  Implementation Location: Could you please provide information on the location within the browser's codebase where this certificate chain selection logic is implemented? If possible, please include specific file paths or code modules.
4.  Rationale: What is the reasoning behind these design choices, and what are some potential edge cases or known issues that they are designed to mitigate?
5.  Specific Examples: If there are any practical examples or case studies of where the logic is relevant, could you share a few cases?

I understand the complexity of this area and appreciate any detailed information you can provide. I am particularly interested in the technical specifics behind these choices, as it directly relates to the security and reliability of web browsing.

Thank you for your time and consideration. I look forward to your response.

[Nick Alexander]

Hi Bruce,

I'm not the right person to answer really any of your queries, but I can at least point you to the relevant implementation (or, be the wrong answer in the adage about the fastest way to get an answer on the Web) -- building and verifying certificate chains is the work of mozpkix.  My belief, very loosely held, is that the browser will accept _any_ valid chain, so most of your questions about "which of two candidate certificates is favoured" are mostly irrelevant -- we're looking for any path in a graph, without any particular ordering, etc.  But hopefully you can either read the code and verify for yourself, or the experts will chime in.

Best,

Nick

[Dana Keeler]

On Sat, Jan 4, 2025 at 8:52 AM bruce lee <pikaq...@gmail.com> wrote:

Dear Browser Development Team,

I am writing to inquire about the specific logic and algorithms employed by your browser when constructing certificate chains, particularly in scenarios involving multiple intermediate certificates. I am looking for a thorough explanation of the decision-making process and, if possible, the location of the relevant code within your codebase.

My specific area of interest is in how the browser handles situations where it encounters multiple potential intermediary certificates that could link to a given end-entity certificate, specifically:

Scenario: Consider an end-entity certificate "C". This certificate can potentially be linked to two intermediate certificates, "A" and "B".
Key and Subject Identity: Intermediate certificates "A" and "B" share the same private key and have the same subject name.
Field Differences: However, other fields within "A" and "B" are different (e.g., different validity periods, subject alternative names, extensions, etc.).

In such a case, end-entity certificate "C" could be successfully linked to either "A" or "B", resulting in two potential certificate chain paths.

My questions are:

1.  Selection Criteria: What specific criteria or properties does the browser prioritize when selecting between such multiple intermediate certificates with the same subject name and public key? Is this selection based on the most recently issued certificate, or the one with the longer validity period, or some other factors? Please provide a complete list of these criteria, ordered by priority.

Candidate issuers are determined by subject name alone during path building. The public key/signature is verified when validating a particular path. Firefox tries candidate issuers in the following order. If there are multiple certificates in a particular category, they are tried in no particular order.

1. Built-in root certificates

2. Third-party root certificates

3. Intermediate certificates from the TLS handshake

4. Third-party intermediate certificates

5. Preloaded intermediate certificates (the set of disclosed intermediate certificates in the CCADB)

6. Root certificates found in the NSS cert DB

7. Intermediate certificates found in the NSS cert DB

 

2.  Algorithm: Could you describe the detailed algorithm (or pseudo-code) used by the browser when making this selection? I am interested in understanding the complete process flow.

Firefox uses mozilla::pkix to build and verify certificate chains. This is done in two parts: path building and chain validation. Path building is essentially depth-first search to find a path to a trust anchor (this is where e.g. basic constraints are checked). The depth is limited to 8 certificates, and loops are disallowed. Once a path to a trust anchor has been found, it is validated (this is where signature and revocation checking happens). If a path turns out to not be valid, path building continues with the next suitable candidate certificate.

 

3.  Implementation Location: Could you please provide information on the location within the browser's codebase where this certificate chain selection logic is implemented? If possible, please include specific file paths or code modules.

mozilla::pkix: https://searchfox.org/mozilla-central/source/security/nss/lib/mozpkix/

Firefox's TrustDomain implementation: https://searchfox.org/mozilla-central/source/security/certverifier/NSSCertDBTrustDomain.cpp

Firefox's CertVerifier: https://searchfox.org/mozilla-central/source/security/certverifier/CertVerifier.cpp

 

4.  Rationale: What is the reasoning behind these design choices, and what are some potential edge cases or known issues that they are designed to mitigate?

This is the original design document: https://briansmith.org/insanity-pkix

The short version is that among other issues, Firefox's previous implementation wouldn't fully traverse all available paths, which would lead to unexpected errors. In particular, it made implementing key pinning impossible.

 

5.  Specific Examples: If there are any practical examples or case studies of where the logic is relevant, could you share a few cases?

The prioritization in 1 is largely for performance reasons. If Firefox can find a short path to a trust anchor, that means fewer signatures to verify, which is faster. If it can find intermediates and eventually a trust anchor without accessing the NSS cert DB, that is also faster.

I understand the complexity of this area and appreciate any detailed information you can provide. I am particularly interested in the technical specifics behind these choices, as it directly relates to the security and reliability of web browsing.

Thank you for your time and consideration. I look forward to your response.

--
You received this message because you are subscribed to the Google Groups "dev-pl...@mozilla.org" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dev-platform...@mozilla.org.
To view this discussion visit https://groups.google.com/a/mozilla.org/d/msgid/dev-platform/8375bf7d-d061-4aef-b888-b1bbbd408fe6n%40mozilla.org.

[bruce lee]

I've seen your reply and I'll continue the discussion as I still have some questions that I haven't figured out, here are my follow-ups:

Question 6:
Based on your response to question 2 (Once a path to a trust anchor has been found, it is validated), I have the following inference:
Once a path to a trust anchor is found, Firefox will immediately proceed to validation. If this path passes validation, Firefox will stop looking for other possible paths. This means that even if there is a shorter path, as long as the found path has passed validation, it will be used. Therefore, Firefox does not guarantee finding the shortest certificate chain.
Is my understanding correct? I would like a 'Yes' or 'No' answer, along with the relevant knowledge.

Question 7:
In Chrome, one can obtain a log file through 'chrome://net-export/', which provides the following information:
1: The N paths that Chrome attempted to build, including the PEM encoding of the certificates in the path and their Subject field contents. (Assume the first N-1 paths were invalid, and the Nth path was valid).
2: The reasons why the first N-1 paths were invalid, e.g. "CA certificate key usage is incorrect".
Is there a way to achieve a similar effect as 'chrome://net-export/' in Firefox, where I can see the information of every certificate chain that Firefox attempted to build, as well as the reasons why the candidate chains were invalid?

Question 8:
Based on your response to question 1, I think you misunderstood my meaning. I am not concerned about the priority of the certificate source categories; I need to rephrase my question.
Suppose there is an end-entity certificate "C". This certificate can potentially be linked to two intermediate certificates, "A" and "B". Intermediate certificates "A" and "B" share the same private key and have the same subject name. Importantly, they also come from the same category of library, e.g. both "A" and "B" are from the intermediate CA certificate store on Windows.
In this case, how does Firefox make the selection?
In our experiments, we performed 500 tests, sending the end-entity certificate "C" to Firefox, and then adding "A" and "B" to the Windows intermediate CA certificate store, where "A" uses SHA256-RSA2048bits and "B" uses SHA384-RSA2048bits, and all other fields are the same between "A" and "B".
In each test, Firefox always selected the certificate "B" with the SHA384 algorithm.
So I inferred that Firefox prefers the more complex signing algorithm.
I know I only understand the tip of the iceberg, so my question remains: When faced with multiple certificates that share the same private key and subject name, and come from the same certificate source category, how does Firefox make the selection? For example, does it choose the certificate with the more complex signing algorithm? The one with the longer validity period? The one with the larger serial number value? If the two certificates only differ in the binary data of the public key, while all other fields are completely the same, just like facing identical twins with different names, how does Firefox make the choice?
I hope to receive a complete answer that can support me in reproducing the same selection logic as Firefox.

[Dana Keeler]

On Tue, Jan 7, 2025 at 8:19 AM bruce lee <pikaq...@gmail.com> wrote:

I've seen your reply and I'll continue the discussion as I still have some questions that I haven't figured out, here are my follow-ups:

Question 6:
Based on your response to question 2 (Once a path to a trust anchor has been found, it is validated), I have the following inference:
Once a path to a trust anchor is found, Firefox will immediately proceed to validation. If this path passes validation, Firefox will stop looking for other possible paths. This means that even if there is a shorter path, as long as the found path has passed validation, it will be used. Therefore, Firefox does not guarantee finding the shortest certificate chain.
Is my understanding correct? I would like a 'Yes' or 'No' answer, along with the relevant knowledge.

Yes. Firefox does not exhaustively search all possible paths, so there may be a shorter path than the one found.

 

Question 7:
In Chrome, one can obtain a log file through 'chrome://net-export/', which provides the following information:
1: The N paths that Chrome attempted to build, including the PEM encoding of the certificates in the path and their Subject field contents. (Assume the first N-1 paths were invalid, and the Nth path was valid).
2: The reasons why the first N-1 paths were invalid, e.g. "CA certificate key usage is incorrect".
Is there a way to achieve a similar effect as 'chrome://net-export/' in Firefox, where I can see the information of every certificate chain that Firefox attempted to build, as well as the reasons why the candidate chains were invalid?

No. Firefox does not have a feature like this.

 

Question 8:
Based on your response to question 1, I think you misunderstood my meaning. I am not concerned about the priority of the certificate source categories; I need to rephrase my question.
Suppose there is an end-entity certificate "C". This certificate can potentially be linked to two intermediate certificates, "A" and "B". Intermediate certificates "A" and "B" share the same private key and have the same subject name. Importantly, they also come from the same category of library, e.g. both "A" and "B" are from the intermediate CA certificate store on Windows.
In this case, how does Firefox make the selection?
In our experiments, we performed 500 tests, sending the end-entity certificate "C" to Firefox, and then adding "A" and "B" to the Windows intermediate CA certificate store, where "A" uses SHA256-RSA2048bits and "B" uses SHA384-RSA2048bits, and all other fields are the same between "A" and "B".
In each test, Firefox always selected the certificate "B" with the SHA384 algorithm.
So I inferred that Firefox prefers the more complex signing algorithm.
I know I only understand the tip of the iceberg, so my question remains: When faced with multiple certificates that share the same private key and subject name, and come from the same certificate source category, how does Firefox make the selection? For example, does it choose the certificate with the more complex signing algorithm? The one with the longer validity period? The one with the larger serial number value? If the two certificates only differ in the binary data of the public key, while all other fields are completely the same, just like facing identical twins with different names, how does Firefox make the choice?
I hope to receive a complete answer that can support me in reproducing the same selection logic as Firefox.

 

Firefox does not make any kind of ordering decision here. The ordering in this case would come from the order in which the operating system presented the certificates to Firefox.

[bruce lee]

Thanks for the second reply, I still have questions to follow:

Question 9:
Based on your answer to question 8, if "A" and "B" are from the server rather than from the Windows system, for instance, if the server sends a certificate chain file (.crt) containing the PEM encodings of [C, A, B], in this scenario, I still want to ask about the content mentioned in question 8. How would Firefox make its selection?

Question 10:
Chrome uses the CA Issuer URL in the AIA field of the certificate to download CA certificates for building the certificate chain. Does Firefox have this capability?

Question 11:
Firefox has a path length limit of 8, but I'd like to know if there is a path construction iteration limit in Firefox?
My investigation shows that Chrome has a parameter set to kPathBuilderIterationLimit = 20, so its maximum allowed certificate chain depth is also 20. This leads to the following construction process in Chrome:

First attempt to build: [ABCDEFG], this chain is invalid.
Second attempt to build: [AHIJKLMNOPQ], this chain is also invalid.
At this point, 17 certificates have appeared: [ABCDEFGHIJKLMNOPQ].
When attempting the third build, if the 20th certificate is tried and a trust anchor is still not found, the kPathBuilderIterationLimit is exhausted, stopping the search, and the build fails.
Does Firefox have such a limitation?

[Dana Keeler]

On Tue, Jan 7, 2025 at 8:52 AM bruce lee <pikaq...@gmail.com> wrote:

Thanks for the second reply, I still have questions to follow:

Question 9:
Based on your answer to question 8, if "A" and "B" are from the server rather than from the Windows system, for instance, if the server sends a certificate chain file (.crt) containing the PEM encodings of [C, A, B], in this scenario, I still want to ask about the content mentioned in question 8. How would Firefox make its selection?

Firefox will try the intermediates in the order received in the handshake.

 

Question 10:
Chrome uses the CA Issuer URL in the AIA field of the certificate to download CA certificates for building the certificate chain. Does Firefox have this capability?

No - Firefox does not do AIA chasing (it introduces additional latency in the handshake and is a privacy concern). Instead, Firefox proactively downloads all publicly-disclosed intermediate certificates that are part of Mozilla's Root CA Program.

 

Question 11:
Firefox has a path length limit of 8, but I'd like to know if there is a path construction iteration limit in Firefox?
My investigation shows that Chrome has a parameter set to kPathBuilderIterationLimit = 20, so its maximum allowed certificate chain depth is also 20. This leads to the following construction process in Chrome:

First attempt to build: [ABCDEFG], this chain is invalid.
Second attempt to build: [AHIJKLMNOPQ], this chain is also invalid.
At this point, 17 certificates have appeared: [ABCDEFGHIJKLMNOPQ].
When attempting the third build, if the 20th certificate is tried and a trust anchor is still not found, the kPathBuilderIterationLimit is exhausted, stopping the search, and the build fails.
Does Firefox have such a limitation?

Firefox's equivalent, buildForwardCallBudget, is 200000: https://searchfox.org/mozilla-central/rev/e24277e20c492b4a785b4488af02cca062ec7c2c/security/nss/lib/mozpkix/lib/pkixbuild.cpp#393

[bruce lee]

Thanks for the third reply, I still have questions to follow:

Question 12:
Based on your answer to question 8, I would like to delve deeper into that topic. Your answer stated: "Firefox does not make any kind of ordering decision here. The ordering in this case would come from the order in which the operating system presented the certificates to Firefox." 

I want to know how one could obtain the order in which Windows provides certificates to Firefox. Is it by sending a request to Windows API, and then Windows returns the order? I'm interested in finding out how to get the same certificate order as Firefox from Windows so I can understand which certificate Firefox tries first, and then which one it tries next.

Question 13:
Regarding Chrome, `kPathBuilderIterationLimit = 20`, each `kPathBuilderIterationLimit` represents a attempted certificate used to build the path, thus, Chrome's maximum path depth is also equal to `kPathBuilderIterationLimit = 20`.
Concerning Firefox, `buildForwardCallBudget = 200000`. I want to know under what circumstances `buildForwardCallBudget` increments by one, and what each increment of `buildForwardCallBudget` represents.

[Dana Keeler]

On Mon, Jan 13, 2025 at 5:08 AM bruce lee <pikaq...@gmail.com> wrote:

Thanks for the third reply, I still have questions to follow:

Question 12:
Based on your answer to question 8, I would like to delve deeper into that topic. Your answer stated: "Firefox does not make any kind of ordering decision here. The ordering in this case would come from the order in which the operating system presented the certificates to Firefox." 

I want to know how one could obtain the order in which Windows provides certificates to Firefox. Is it by sending a request to Windows API, and then Windows returns the order? I'm interested in finding out how to get the same certificate order as Firefox from Windows so I can understand which certificate Firefox tries first, and then which one it tries next.

The implementation is here: https://searchfox.org/mozilla-central/rev/d788991012a1a8ec862787f9799db4954a33045f/security/manager/ssl/EnterpriseRoots.cpp#209

The easiest way to see what order Firefox gets them in is to enable the browser console (set `devtools.chrome.enabled` to `true` in `about:config`, open up the browser console (`ctrl` + `shift` + `j` on Windows), and run this code:

let nss = Cc["@mozilla.org/psm;1"].getService(Ci.nsINSSComponent);

nss.getEnterpriseRootsPEM();

nss.getEnterpriseIntermediatesPEM();

That will list the roots and intermediates Firefox gleaned from the operating system.

 

Question 13:
Regarding Chrome, `kPathBuilderIterationLimit = 20`, each `kPathBuilderIterationLimit` represents a attempted certificate used to build the path, thus, Chrome's maximum path depth is also equal to `kPathBuilderIterationLimit = 20`.
Concerning Firefox, `buildForwardCallBudget = 200000`. I want to know under what circumstances `buildForwardCallBudget` increments by one, and what each increment of `buildForwardCallBudget` represents.

Strictly speaking, buildForwardCallBudget only decreases. See https://searchfox.org/mozilla-central/rev/d788991012a1a8ec862787f9799db4954a33045f/security/nss/lib/mozpkix/lib/pkixbuild.cpp#194-200

Basically, every time mozilla::pkix attempts to find the next certificate in a certificate chain, it will decrement that counter. When it reaches 0, mozilla::pkix stops trying to build a path and returns a failure.