1533774 - GoDaddy: Insufficient serial number entropy

Status: RESOLVED FIXED

(CA Program :: CA Certificate Compliance, task)

Description

[Wayne Thayer]

Daymion Reynolds posted the following to the mozilla.dev.security.policy list:

As of 9pm AZ on 3/6/2019 GoDaddy started researching the 64bit certificate Serial Number issue. We have identified a significant quantity of certificates (> 1.8million) not meeting the 64bit serial number requirement. We are still performing accounting so certificate quantity is expected to change before we finalize the report.

1.  How your CA first became aware of the problem (e.g. via a problem report submitted to your Problem Reporting Mechanism, a discussion in mozilla.dev.security.policy, a Bugzilla bug, or internal self-audit), and the time and date.
   

9pm 3/6/2019 AZ Time, due to reviewing a discussion in mozilla.dev.security.policy.

2.  A timeline of the actions your CA took in response. A timeline is a date-and-time-stamped sequence of all relevant events. This may include events before the incident was reported, such as when a particular requirement became applicable, or a document changed, or a bug was introduced, or an audit was done.
   

9pm 3/6/2019 AZ Time, identified a hot issue with serial numbers in Mozilla group.
10am 3/7/2019 AZ Time, identified the issue was pervasive, and identified root cause.
6:30pm 3/7/2019 AZ Time, fix deployed to production to correct the serial number issue.
We are still quantifying and classifying the certificate scope of impact.

3.  Whether your CA has stopped, or has not yet stopped, issuing certificates with the problem. A statement that you have will be considered a pledge to the community; a statement that you have not requires an explanation.
   

We have deployed a fix to the issue, and are no longer issuing certificates with the defect.

4.  A summary of the problematic certificates. For each problem: number of certs, and the date the first and last certs with that problem were issued.
   

Issue was introduced with a change in 2016. Impacted certificates still being aggregated. Will update with information and timeline on issue closure.

5.  The complete certificate data for the problematic certificates. The recommended way to provide this is to ensure each certificate is logged to CT and then list the fingerprints or crt.sh IDs, either in the report or as an attached spreadsheet, with one list per distinct problem.
   

Still being aggregated. Will update with certificate information on issue closure.

6.  Explanation about how and why the mistakes were made or bugs introduced, and how they avoided detection until now.
   

Ambiguity in language led to different interpretations of BR 7.1. It was believed a unsigned 64bit integer was sufficient to satisfy the new requirement. Additionally, industry tools like CABLint/ZLint were not catching this issue, which provided a false sense of compliance. We are submitting CABLint/Zlint updates as part of the fix.

7.  List of steps your CA is taking to resolve the situation and ensure such issuance will not be repeated in the future, accompanied with a timeline of when your CA expects to accomplish these things.
   

Defect has been resolved, we are also updating linting tools (CABLint/Zlint) and upstreaming to patch for other peoples usage.

Comment 1

[Ryan Sleevi]

Daymion,

Do you have an update on the list of impacted certificates? This is also missing a timeline about proposed next steps.

Comment 2

[Daymion Reynolds]

As of 9pm AZ on 3/6/2019 GoDaddy started researching the 64bit certificate Serial Number issue. Due to a m.d.s.p.[1] discussion validating an interpretation of BR 7.1 our revised count is approximately 12,152 live certificates not meeting the 64bit serial number requirement. Additionally, we have identified 273,784 “orphaned” certificates meeting the initial interpretation of BR 7.1. Orphaned certificates are certs, which were stopped mid-issuance due to a variety of reasons like requestor cancellation, system errors etc. These certs are most often pre-certificates, but some are leaf-certificates, which were logged to CT, but never received by the certificate requestor.

The initial report stated >1.8 million certificates were impacted. For our initial investigation we checked certs against the first bit being set, which seemed to be the industry interpretation at the time. This lead to more aggressive criteria than necessary. As we started revocations of orphan certificates we continued researching the criteria defined by BR7.1 After re-evaluating the criteria, per m.d.s.p.[1], we adjusted our certificate scope.

1.    How your CA first became aware of the problem (e.g. via a problem report submitted to your Problem Reporting Mechanism, a discussion in mozilla.dev.security.policy, a Bugzilla bug, or internal self-audit), and the time and date. 
   

9pm 3/6/2019 AZ Time, due to reviewing a discussion in mozilla.dev.security.policy.

2.    A timeline of the actions your CA took in response. A timeline is a date-and-time-stamped sequence of all relevant events. This may include events before the incident was reported, such as when a particular requirement became applicable, or a document changed, or a bug was introduced, or an audit was done. 
   

9pm 3/6/2019 AZ Time, identified a hot issue with serial numbers in Mozilla group.
10am 3/7/2019 AZ Time, identified the issue was pervasive, and identified root cause.
6:30pm 3/7/2019 AZ Time, fix deployed to production to correct the serial number issue.
2pm 3/9/2019 AZ Time, we revoked 273,784 orphaned, pre-certs and leaf certificates which met the initial criteria. These certificates were low\no risk as they were never distributed.
11pm 3/11/2019 AZ Time, defined resolution as stated in m.d.s.p., further research revised the quantity of impacted certificates.
3/12 – 3/16 – We will be revoking the before mentioned 12,152 live certificates.
Once the revocation is complete we will update this timeline.

3.    Whether your CA has stopped, or has not yet stopped, issuing certificates with the problem. A statement that you have will be considered a pledge to the community; a statement that you have not requires an explanation. 
   

We have deployed a fix to the issue on 3/7/2019, and are no longer issuing certificates with the defect.

4.    A summary of the problematic certificates. For each problem: number of certs, and the date the first and last certs with that problem were issued. 
   

12,134 certificates were affected.
Revoking as a precaution, certificates issued on 9/29/2016
9/29/2016 2:41 66269447367104810
9/29/2016 7:44 35092532380173749
9/29/2016 9:46 43324527254073466
9/29/2016 14:16 53640950198707040
9/29/2016 14:31 36562688867169546

The first affected certificate was issued on 9/30/2016 1:29 https://crt.sh/?id=290271291
The last affected certificate was issued on 3/7/2019 15:32 https://crt.sh/?id=1262876175

5.    The complete certificate data for the problematic certificates. The recommended way to provide this is to ensure each certificate is logged to CT and then list the fingerprints or crt.sh IDs, either in the report or as an attached spreadsheet, with one list per distinct problem. 
   

Spreadsheet attached to defect. Older certificates may not yet be CT logged, as the majority of the certs are DV.

6.    Explanation about how and why the mistakes were made or bugs introduced, and how they avoided detection until now. 
   

Ambiguity in language led to different interpretations of BR 7.1 in 2016. It was believed an unsigned 64bit integer was sufficient to satisfy the new requirement. Additionally, industry tools like CABLint/ZLint were not catching this issue, which provided a false sense of compliance. We are submitting CABLint/Zlint updates as part of the fix.

7.    List of steps your CA is taking to resolve the situation and ensure such issuance will not be repeated in the future, accompanied with a timeline of when your CA expects to accomplish these things. 
   

Defect has been resolved, we are also updating linting tools (CABLint/Zlint) and upstreaming to patch for other peoples usage.
Additionally, we are looking to scope and roadmap upgrading our certificate serial number to a minimum of 128-bit, or the max possible.
[1] https://groups.google.com/forum/#!topic/mozilla.dev.security.policy/7WuWS_20758

Comment 3

[Daymion Reynolds]

Attachment: Final Serial Number List.csv

Set of certs

Comment 4

[Daymion Reynolds]

In accordance with our conversations to date, prior to 3/7 6:30pm AZ we utilized raw 64 bit output from CSPRING, with uniqueness and non zero checks. This new understanding of the rules calls for us to modify our original disclosure to 0 affected certificates.

For any new other serial number issues we will file a new incident.

Comment 5

[Ryan Sleevi]

Tracking these details is a bit tedious, so I'm trying to make sure. The related discussion on mozilla.dev.security.policy was titled Pre-Incident Report - GoDaddy Serial Number Entropy

• On 2019-03-12, and in Comment #0, Daymion stated that "We are looking to scope and roadmap upgrading our certificate serial number to a minimum of 128-bit, or the max possible."
• On 2019-03-12, Daymion described the algorithm as:

64bits_entropy = GetRandom64Bits() //This returns 64 random bits from a CSPRNG with at least one bit in the highest byte set to 1
CheckForDuplicate(64bits_entropy)//Verifies the serial is unique, otherwise repeat GetRandom64Bits()
Cert.SetSerialNumber(64bits_entropy) //The ANS.1 encoding will either write this number as 8 or 9 octets.  

• It was pointed out that same day that the described algorithm results in 63.994353 bits of entropy
• Clarifications were requested on 2019-03-15 regarding the described algorithm
• A statistical analysis of the (known) certificates was performed, resulting in the following spreadsheet. In this, GoDaddy's two primary issuing CAs were https://crt.sh/?caid=904 and https://crt.sh/?caid=797 , with a respective distribution of 49.99450631% / 50.00549369% and 49.98069428% / 50.01930572%

The area I'm concerned about is that clarifications to the psuedo-code were not provided, and thus the described algorithm is not compliant - but close enough to look compliant for such analysis.

I'm hoping that GoDaddy will provide the necessary clarifications as to how it generated serial numbers during the period of time in question. As described, requiring 1 bit in the high byte results in 255 values, rather than 256 (since an all zero value is excluded), along with 2^56 other possible values. lg((2^8 - 1) * 2^56) is 63.9943534369 bits of entropy.

Comment 6

[Ryan Sleevi]

Emailed POCs on 2019-07-15 regarding this issue, highlighting https://wiki.mozilla.org/CA/Responding_To_An_Incident#Keeping_Us_Informed

Comment 7

[Joanna]

Apologies for the delayed response. GoDaddy acknowledges the inquiry. We will work to have a response to the community by EOD, July 19th.

Comment 8

[Joanna]

During the time period in question, we received 64 random bits of output from a CSPRNG, checked that it had at least one bit in the top byte set (based on industry guidance at the time of the event), checked it for duplicates, and used it as the serial number. In accordance with BR 7.1 to, “generate non-sequential Certificate serial numbers greater than zero (0) containing at least 64 bits of output from a CSPRNG.”

Comment 9

[Ryan Sleevi]

Joanna: Thanks. However, as noted in Comment #5, and previously noted in the mozilla.dev.security.policy discussion, that algorithm isn't actually 64-bits. That was flagged for Daymion, and while I understand he's no longer with GoDaddy, I think that still remains an existing concern.

Put differently, imagine if a CA said "We generate 64-bits of entropy, discard the top 32 bits if any of the bits are 1, check for duplicates, and use that as the serial number". You can understand how that wouldn't suffice.

I understand that GoDaddy was under the mistaken impression it was compliant, but I'm curious whether GoDaddy took any steps to resolve this going forward. For example, did you increase your serial number length in light of these incidents? If so, when? If not, why not?

Comment 10

[Joanna]

Yes, GoDaddy has indeed taken steps forward. On March 13, we discontinued checking the top-most byte for having a bit set, based on the evolving industry guidance at that time, leaving us in compliance with BR 7.1 to, “generate non-sequential Certificate serial numbers greater than zero (0) containing at least 64 bits of output from a CSPRNG.” We continue to evaluate the BR's as written, and will make updates accordingly.

Comment 11

[Ryan Sleevi]

Is anything being done for the existing non-compliant certificates generated with less than 64 bits of entropy?

Comment 12

[Joanna]

GoDaddy’s position is that BR 7.1, to “generate non-sequential Certificate serial numbers greater than zero (0) containing at least 64 bits of output from a CSPRNG,” has been followed, therefore revocations are not needed. If the BR’s are updated with further clarification, we will certainly make changes to remain in compliance.

Comment 13

[Wayne Thayer]

In determining how to close this out, it's important both to prevent CAs from using creative interpretations of the requirements when it suits them, but also not to punish a CA when the requirements are ambiguous. I concur with Ryan's comment #9 that GoDaddy's algorithm was not compliant with the BRs, however I note that in the m.d.s.p. discussion, an analysis was presented that apparently did not detect non-compliance. (I acknowledge that it was a statistical analysis that could be wrong)

Based on the conflicting evidence at hand, I propose that this bug be closed with no further action (e.g. "Failure to revoke" bug) as "Fixed" (not "Invalid").

Ryan: N-I for your feedback on this.

Comment 14

[Ryan Sleevi]

Wayne: I agree.

That is, I'm quite disappointed with the explanation/justifications given during the discussion, and the lack of clarity surrounding the algorithm, but I agree that we're unlikely to make further progress here. I think the substantive comment would be to make sure that creative interpretations, as you rightly called, aren't applied in the future, regardless of the requirement.

While there are substantive things GoDaddy could do to help that, such as making sure to carefully examine their CP/CPS with a multi-party review and look for other elements of concern or ambiguity and share those, I don't think we need to keep this bug to track that.