Pre-Incident Report - GoDaddy Serial Number Entropy

[Daymion Reynolds]

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.

[Matthew Hardeman]

Practical question:

How does the update to CABLint/Zlint work?

If a CA is choosing to issue certs with serial numbers with exactly 64 bits
of entropy, approximately 50% of the time there will be a certificate with
an 8 byte encoding of the serial number, as the high-order bit of the first
byte will be 0. Approximately the other 50% of the time, the high-order
bit of the 64 bits of data will be a 1 and the value will therefore be
encoded as 9 bytes, the value of the first byte being 0x00.

As linters work on one document [certificate] at a time, how can the linter
identify with certainty that the 8-byte encoded value represents less than
64 bits of entropy? Approximately half of the time, a strict 64-bit random
value would encode as a mere 8 bytes.

> _______________________________________________
> dev-security-policy mailing list
> dev-secur...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-security-policy
>

[Wayne Thayer]

I've created https://bugzilla.mozilla.org/show_bug.cgi?id=1533774 to track
this issue.

Apple has also submitted the following bug for this issue listing a large
number of impacted certificates:
https://bugzilla.mozilla.org/show_bug.cgi?id=1533655

- Wayne

[okaphone.e...@gmail.com]

On Friday, 8 March 2019 17:07:57 UTC+1, Wayne Thayer wrote:
> I've created https://bugzilla.mozilla.org/show_bug.cgi?id=1533774 to track
> this issue.
>
> Apple has also submitted the following bug for this issue listing a large
> number of impacted certificates:
> https://bugzilla.mozilla.org/show_bug.cgi?id=1533655
>
> - Wayne

Wow! Looks like there are going to be A LOT of certificates that MUST be revoked. Formally correct of course, but could it perhaps be a good idea to consider the possibility of handling this one somewhat different? ;-)

CU Hans

[Jeremy Rowley]

If they need some help with large scale replacement, I know some people who did that recently 😊. Joking of course, but really - with Godaddy, Google, and Apple reporting a large number of certs that have what seems to be a minor compliance issue in light of the certs all being SHA2, does Mozilla want to require a complete revocation and replacement? Seems like a lot of effort and disruption for little value to the Mozilla community.

-----Original Message-----
From: dev-security-policy <dev-security-...@lists.mozilla.org> On Behalf Of okaphone.elektronika--- via dev-security-policy
Sent: Friday, March 8, 2019 12:28 PM
To: mozilla-dev-s...@lists.mozilla.org
Subject: Re: Pre-Incident Report - GoDaddy Serial Number Entropy

On Friday, 8 March 2019 17:07:57 UTC+1, Wayne Thayer wrote:

> I've created https://bugzilla.mozilla.org/show_bug.cgi?id=1533774 to
> track this issue.
>
> Apple has also submitted the following bug for this issue listing a
> large number of impacted certificates:
> https://bugzilla.mozilla.org/show_bug.cgi?id=1533655
>
> - Wayne

Wow! Looks like there are going to be A LOT of certificates that MUST be revoked. Formally correct of course, but could it perhaps be a good idea to consider the possibility of handling this one somewhat different? ;-)

CU Hans

[Ryan Sleevi]

On Fri, Mar 8, 2019 at 4:35 PM Jeremy Rowley via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> does Mozilla want to require a complete revocation and replacement? Seems
> like a lot of effort and disruption for little value to the Mozilla
> community.

I'm surprised, given the length of the discussion in [1], to see such an
unhelpful framing of the issue, as it sounds remarkably like asking for an
"exception". I had hoped that the changes [2] to the policy [3] had
provided greater clarity about what the expectations are for CAs. It does
seem that CAs are following that process, which is something another CA
recently did in the case of underscores, so perhaps its best to not try and
re-open that discussion? :)

I think a particular piece of guidance and clarification, expected of such
incident reports, and captured in [3], is
"That you will perform an analysis to determine the factors that prevented
timely revocation of the certificates, and include a set of remediation
actions in the final incident report that aim to prevent future revocation
delays."

It does seem that this is an essential and valuable piece for the
community, regardless of the CA affected and regardless of the nature of
the incident. After all, it doesn't seem to dissimilar to the discussion
regarding Heartbleed, and the challenges the ecosystem faced then.

[1]
https://groups.google.com/d/msg/mozilla.dev.security.policy/0oy4uTEVnus/pnywuWbmBwAJ
[2]
https://groups.google.com/d/msg/mozilla.dev.security.policy/HdirGOy6TJI/oIHKXeSuCAAJ
[3] https://wiki.mozilla.org/CA/Responding_To_An_Incident#Revocation

[Wayne Thayer]

Ryan beat me to the punch. so I'll reinforce his message with my own:

The overall potential impact from revocations in the current scenario feels
quite similar to the potential for disruption from revoking certificates
containing underscores a few months ago. Mozilla's guidance for revocation
[1] was updated based on the "underscores" discussion, and it is generally
applicable here. (I will give it another review in light of the current
situation.)

In my opinion, Mozilla should not get in to the business of granting
one-off exceptions to the BR revocation requirements. In this case, doing
so would certainly not be fair to Google, and in the future would only
result in constant pleas for mercy that would be near impossible to refuse.
Revocation decisions should ultimately be made by CAs and followed up with
disclosure and preventative action. Mozilla should highlight situations
where delaying revocation will be viewed as an egregious failure by a CA to
respond to an imminent threat.

I believe that Google's response here sets a good, if imperfect, example of
the agility we desire for the entire web PKI. I hope that the current event
serves to illustrate the need for agility and encourages CAs to develop
more solutions that move us in that direction.

- Wayne

[1] https://wiki.mozilla.org/CA/Responding_To_An_Incident#Revocation

[Jeremy Rowley]

Apologies, I realize that Mozilla’s policy is that revocation is up to the CA and there is no such thing as an exception. A more careful way to state what I meant is that I’m surprised that there is not more discussion around the revocation of all of these certificates and the impact to the ecosystem compared to an assumption that they will all be revoked. There has been some discussion of course, but 1.8 million certificates is a lot of certificates to replace. I’d think to see more discussion here from GoDaddy about ether they are replacing the certificates or not and the pros and cons of doing so.

From: Wayne Thayer <wth...@mozilla.com>
Sent: Friday, March 8, 2019 3:46 PM
To: Ryan Sleevi <ry...@sleevi.com>
Cc: Jeremy Rowley <jeremy...@digicert.com>; mozilla-dev-s...@lists.mozilla.org
Subject: Re: Pre-Incident Report - GoDaddy Serial Number Entropy

Ryan beat me to the punch. so I'll reinforce his message with my own:



The overall potential impact from revocations in the current scenario feels quite similar to the potential for disruption from revoking certificates containing underscores a few months ago. Mozilla's guidance for revocation [1] was updated based on the "underscores" discussion, and it is generally applicable here. (I will give it another review in light of the current situation.)



In my opinion, Mozilla should not get in to the business of granting one-off exceptions to the BR revocation requirements. In this case, doing so would certainly not be fair to Google, and in the future would only result in constant pleas for mercy that would be near impossible to refuse. Revocation decisions should ultimately be made by CAs and followed up with disclosure and preventative action. Mozilla should highlight situations where delaying revocation will be viewed as an egregious failure by a CA to respond to an imminent threat.



I believe that Google's response here sets a good, if imperfect, example of the agility we desire for the entire web PKI. I hope that the current event serves to illustrate the need for agility and encourages CAs to develop more solutions that move us in that direction.



- Wayne



[1] https://wiki.mozilla.org/CA/Responding_To_An_Incident#Revocation

_______________________________________________
dev-security-policy mailing list
dev-secur...@lists.mozilla.org <mailto:dev-secur...@lists.mozilla.org>
https://lists.mozilla.org/listinfo/dev-security-policy

[Wayne Thayer]

On Fri, Mar 8, 2019 at 4:03 PM Jeremy Rowley <jeremy...@digicert.com>
wrote:

> Apologies, I realize that Mozilla’s policy is that revocation is up to the
> CA and there is no such thing as an exception. A more careful way to state
> what I meant is that I’m surprised that there is not more discussion around
> the revocation of all of these certificates and the impact to the ecosystem
> compared to an assumption that they will all be revoked. There has been
> some discussion of course, but 1.8 million certificates is a lot of
> certificates to replace. I’d think to see more discussion here from GoDaddy
> about ether they are replacing the certificates or not and the pros and
> cons of doing so.
>
>
>

I agree - disclosure and discussion is an important element of situations
such as this.

[Daymion Reynolds]

Our goal is to reissue all the certificates within the next 30 days. We have started the revocation process. We have a significant number of customers that use manual methods for managing their certificates, so being agile for them is difficult. We want to keep our customers using https through the entire revocation period. Due to the large number of certificates and the benign nature of the issue, our plan is to revoke in a responsible way.

Once this is completed, I think we need to get together and have a serious discussion around how to handle potential incidents like this in the future. Having a discussion about if this is right or wrong in the middle of an incident doesn’t help anyone.

[Peter Gutmann]

Daymion Reynolds via dev-security-policy <dev-secur...@lists.mozilla.org> writes:

>Our goal is to reissue all the certificates within the next 30 days.

Before everyone goes into an orgy of mass revocation, see the message I just
posted "Why BR 7.1 allows any serial number except 0". As long as your serial
number isn't zero, there's no such thing as a non-compliant serial number, so
no need to revoke and replace great masses of certificates.

Peter.

[Matt Palmer]

On Fri, Mar 08, 2019 at 09:35:21PM +0000, Jeremy Rowley via
> dev-security-policy wrote: If they need some help with large scale
> replacement, I know some people who did that recently. Joking of

> course, but really - with Godaddy, Google, and Apple reporting a large
> number of certs that have what seems to be a minor compliance issue in

> light of the certs all being SHA2, does Mozilla want to require a complete

> revocation and replacement? Seems like a lot of effort and disruption for
> little value to the Mozilla community.

On the contrary, I think this incident provides a *lot* of value to the
Mozilla community -- and also to CAs and certificate users.

Horstman's Christmas Rule says, "anything important that you don't do very
often, you will do poorly". It's the reason why militaries drill regularly,
why firefighters practice rolling and bowling hoses, and why commercial
airline pilots spend time in simulators -- because those things need to be
done well. A closer-to-home equivalent might be something like the "simian
army" (sometimes known as the "chaos monkey") concept popularised by Netflix
-- you don't know if your disaster-recovery systems will work unless you
test them, so why not test them regularly?

Similarly, revoking (and potentially re-issuing) certificates en masse needs
to be done well, because there is the distinct chance that at some point,
a(nother) *very* serious security problem is going to be found that will
require that a large volume of certificates be revoked and reissued, for
real, with practically zero notice. I think at this point we have enough
data to say with some confidence that, when CAs have to do this
out-of-the-blue, the results are not what we might hope for. Whether it's
because CA systems and processes aren't where they should be, or because
certificate end-users are insufficiently willing and able, there are
definite problems that should be addressed.

I've previously suggested, somewhat tongue-in-cheek, that Mozilla should
provide for "spontaneous revocation" in its CA program requirements -- that
on a random basis, a CA should be handed a list of a certain percentage of
their certificates, chosen at random, and be told, "you must consider the
following certificates compromised, and handle it appropriately". I don't
expect such a rule to be adopted any time soon, because the general appetite
for wanton destruction does not match my own, but it is my platonic ideal of
ensuring, for real and certain, that CAs either are able to do what may very
well become necessary, or else they are shown, in clear and unambiguous
terms, that things are not up to scratch, and figure out what went wrong so
it can be fixed.

Essentially, situations like this insufficiently-random serial number issue,
or the previous underscore situation, are self-inflicted drills around
mass-revocation. They're drills, rather than the "real thing", because I
agree that there is very little short-term harm that will result if these
certificates are not revoked strictly within the mandated timeframes.

- Matt

[Ryan Sleevi]

(Posting in an official capacity)

I would strongly caution CAs against adopting any of these interpretations,
and suggest it would be best for CAs to wholly ignore the message
referenced.

[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

[ad...@adamcaudill.com]

Daymion,

You linked to a thread in m.d.s.p and cited it as confirming a specific interpretation of 7.1 - as that's a long thread (with some possible questionable information), could you possibly share what criteria you used to determine what certificates were impacted by this issue and which ones were not? Seeing a reduction from >1.8M to 12k is a substantial difference, and thus is bound to make participants curious.

I think that would be very helpful to ensure that everyone is on the same page about what is and isn't compliant with 7.1.

Thanks

On Tuesday, March 12, 2019 at 12:28:11 PM UTC-4, Daymion Reynolds wrote:
> 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.

> ...
> [1] https://groups.google.com/forum/#!topic/mozilla.dev.security.policy/7WuWS_20758

[Daymion Reynolds]

The crux of the difference is in the DER format interpretation. The fact prefix (0)s do count for entropy, provided none of the bits are fixed and you have a minimum of 8 bytes in the serial. We discuss this in the Mozilla post on 3/11/2019.

For the DER format the first two (0)s of the value is the positive sign of the integer. In our case if the un-signed integer value is 64bit and the most significant bit is set, two additional (0)s will be prepended to demonstrate a positive sign. In this case it will be 9bytes instead of 8bytes. Always a minimum of 8bytes (64bits) of entropy. You do still have to manage zero compression for integer values less than 72057594037927936, which will result in 7bytes instead of 8bytes.

Hope this helps.

[Ryan Sleevi]

On Tue, Mar 12, 2019 at 2:22 PM Daymion Reynolds via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> The crux of the difference is in the DER format interpretation. The fact
> prefix (0)s do count for entropy, provided none of the bits are fixed and
> you have a minimum of 8 bytes in the serial. We discuss this in the Mozilla
> post on 3/11/2019.
>
> For the DER format the first two (0)s of the value is the positive sign of
> the integer. In our case if the un-signed integer value is 64bit and the
> most significant bit is set, two additional (0)s will be prepended to
> demonstrate a positive sign. In this case it will be 9bytes instead of
> 8bytes. Always a minimum of 8bytes (64bits) of entropy. You do still have
> to manage zero compression for integer values less than 72057594037927936,
> which will result in 7bytes instead of 8bytes.
>

Just making sure I've got the right message - this is
https://groups.google.com/d/msg/mozilla.dev.security.policy/7WuWS_20758/9OKbI4xyCQAJ
correct?

If viewing through groups' interface, you can click the arrow for "More
Message Actions" to copy link.

To make sure I understand correctly, the statement is that GoDaddy
generated 64 bits of entropy prior to DER encoding. This resulted in some
serials that are exactly 8 octets (or even less, depending on leading zeros
and minimal encoding) and some serials that are 9 or more octets.

The reduction from >1.8M certificates to 12K certificates is a statement
that only those 12K certificates lacked a 64-bit entropy contribution? And
possibly 273K certificates which GoDaddy does not consider issued, but
otherwise made committments to issue (such as logging a pre-cert)?

To provide greater clarity about this incident, could you more fully
describe your serial number generation algorithm (potentially including
code or pseudo-code) that can help demonstrate how this system was
compliant?

[Daymion Reynolds]

It is an accurate statement to say that GoDaddy generates 64 full bits of entropy prior to the DER encoding. When these 64 bits are DER encoded, the result is either 8 or 9 octets written into the cert, depending on whether or not the most significant bit is a 0 (8 octets) or 1 (9 octets). In the case of 9 octets being written, the first octet is always “00” signifying the integer value is positive. It is worth noting: whether that extra “00” octet is present or not, there are always 64 randomly generated bits providing the needed entropy.

RS - The reduction from >1.8M certificates to 12K certificates is a statement that only those 12K certificates lacked a 64-bit entropy contribution?
DR – Yes, the 12k certs are only 7bytes or less and therefor do not meet the BRs.

RS - possibly 273K certificates which GoDaddy does not consider issued, but otherwise made commitments to issue (such as logging a pre-cert)?
DR - Yes, in most cases we logged a pre-cert prior to final issuance and turnover to the requested. We want to start revoking these certificates as they should be disposed of if not fully issued.


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.

[Ryan Sleevi]

On Tue, Mar 12, 2019 at 4:23 PM Daymion Reynolds via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> On Tuesday, March 12, 2019 at 11:32:38 AM UTC-7, Ryan Sleevi wrote:

> It is an accurate statement to say that GoDaddy generates 64 full bits of
> entropy prior to the DER encoding. When these 64 bits are DER encoded, the
> result is either 8 or 9 octets written into the cert, depending on whether
> or not the most significant bit is a 0 (8 octets) or 1 (9 octets). In the
> case of 9 octets being written, the first octet is always “00” signifying
> the integer value is positive. It is worth noting: whether that extra
> “00” octet is present or not, there are always 64 randomly generated bits
> providing the needed entropy.
>

> RS - The reduction from >1.8M certificates to 12K certificates is a

> statement that only those 12K certificates lacked a 64-bit entropy
> contribution?

> DR – Yes, the 12k certs are only 7bytes or less and therefor do not meet
> the BRs.
>
> RS - possibly 273K certificates which GoDaddy does not consider issued,
> but otherwise made commitments to issue (such as logging a pre-cert)?
> DR - Yes, in most cases we logged a pre-cert prior to final issuance and
> turnover to the requested. We want to start revoking these certificates as
> they should be disposed of if not fully issued.
>
>
> 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.
>

Thanks Daymion!

>From what you've described, it does sound that this is exactly what CAs
could/should have been doing, if they wanted the absolute minimum encoding
of a serial.

Note that even 7 bytes or less may still be valid - for example, if the
randomly generated integer was 4 [1], you might only have a one-byte serial
in encoded form ( '04'H ), and that would still be compliant. The general
burden of proof would be to demonstrate that these certificates were
generated with that given algorithm you described above.

[1] https://xkcd.com/221/

[Hector Martin 'marcan']

On 13/03/2019 05.38, Ryan Sleevi via dev-security-policy wrote:
> Note that even 7 bytes or less may still be valid - for example, if the
> randomly generated integer was 4 [1], you might only have a one-byte serial
> in encoded form ( '04'H ), and that would still be compliant. The general
> burden of proof would be to demonstrate that these certificates were
> generated with that given algorithm you described above.
>
> [1] https://xkcd.com/221/

Not only that, but, in fact, any attempt to guarantee certain properties
of the serial (such that it doesn't encode to 7 bytes or less) *reduces*
entropy.

In particular,

64bits_entropy = GetRandom64Bits() //This returns 64 random bits from a
CSPRNG with at least one bit in the highest byte set to 1

is, strictly speaking, not true. The best possible implementation for
GetRandom64Bits(), as described, only returns 63.994353 bits of entropy,
not 64.

Now whether 0.57% of a bit worth of entropy matters for practical
purposes, and for BR compliance purposes, is another matter entirely,
but the point is that *any* subsequent filtering and rejection of
serials with certain properties only *hurts* entropy, it doesn't help it.


--
Hector Martin "marcan" (mar...@marcan.st)
Public Key: https://mrcn.st/pub

[Ryan Sleevi]

On Tue, Mar 12, 2019 at 4:57 PM Hector Martin 'marcan' <mar...@marcan.st>
wrote:

Oh, wow, I missed that comment when reading the pseudo-code. I would agree
that filtering like appears to be an issue, similar for the reasons
discussed.

If it placed no restrictions on the highest byte, it would be evenly
distributed, with 0 and previously-issued serials being treated as
duplicates.

I think we should treat this similar to the discussion of other CAs that
ensured the highest bit was 0.

[Kurt Roeckx]

On Wed, Mar 13, 2019 at 05:56:55AM +0900, Hector Martin 'marcan' via dev-security-policy wrote:
> On 13/03/2019 05.38, Ryan Sleevi via dev-security-policy wrote:
> > Note that even 7 bytes or less may still be valid - for example, if the
> > randomly generated integer was 4 [1], you might only have a one-byte serial
> > in encoded form ( '04'H ), and that would still be compliant. The general
> > burden of proof would be to demonstrate that these certificates were
> > generated with that given algorithm you described above.
> >
> > [1] https://xkcd.com/221/
>
> Not only that, but, in fact, any attempt to guarantee certain properties
> of the serial (such that it doesn't encode to 7 bytes or less) *reduces*
> entropy.

The expected distribution when generating a random 64 bit integer
and properly encoding that as DER is that:
- about 1/2 integers require 9 bytes
- about 1/2 integers require 8 bytes
- about 1/512 integers require 7 bytes
- about 1/131072 integers require 6 bytes
- about 1/33554432 integers require 5 bytes
- [...]

That a serial is smaller than 8 bytes is not an indication that it
doesn't contain enough entropy.


Kurt

[Richard Moore]

On Tuesday, March 12, 2019 at 11:53:25 PM UTC, Kurt Roeckx wrote:
>
> The expected distribution when generating a random 64 bit integer
> and properly encoding that as DER is that:
> - about 1/2 integers require 9 bytes
> - about 1/2 integers require 8 bytes
> - about 1/512 integers require 7 bytes
> - about 1/131072 integers require 6 bytes
> - about 1/33554432 integers require 5 bytes
> - [...]
>
> That a serial is smaller than 8 bytes is not an indication that it
> doesn't contain enough entropy.

This is true, but the situation is surely worse - any CA who's serial numbers do not have a significant length variation is almost certainly not providing 64 bits of entropy with the exception of those who are add a prefix to ensure it is positive, and even those are not providing it unless they have lots of serial numbers with a big block of zeros.

If any other CA wants to check theirs before someone else does, then now is surely the time to speak up.

Kind Regards

Rich

[Daymion Reynolds]

On Thursday, March 7, 2019 at 7:01:41 PM UTC-7, Daymion Reynolds wrote:

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.

[Peter Gutmann]

Richard Moore via dev-security-policy <dev-secur...@lists.mozilla.org> writes:

>If any other CA wants to check theirs before someone else does, then now is
>surely the time to speak up.

I'd already asked previously whether any CA wanted to indicate publicly that
they were compliant with BR 7.1, which zero CAs responded to (I counted them
twice). This means either there are very few CAs bothering with dev-security-
policy, or they're all hunkering down and hoping it'll blow over, which given
that they're going to be forced to potentially carry out mass revocations
would be the game-theoretically sensible approach to take:

Option 1: Keep quiet case 1 (very likely): -> No-one notices, nothing happens.
Keep quite case 2 (less likely): -> Someone notices, revocation issues.
Option 2: Say something -> Revocation issues.

So keeping your head down would be the sensible/best policy.

Peter.

[Ryan Sleevi]

On Wed, Mar 13, 2019 at 6:09 PM Peter Gutmann via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Richard Moore via dev-security-policy <
> dev-secur...@lists.mozilla.org> writes:
>
> >If any other CA wants to check theirs before someone else does, then now
> is
> >surely the time to speak up.
>
> I'd already asked previously whether any CA wanted to indicate publicly
> that
> they were compliant with BR 7.1, which zero CAs responded to (I counted
> them
> twice). This means either there are very few CAs bothering with
> dev-security-
> policy, or they're all hunkering down and hoping it'll blow over, which
> given
> that they're going to be forced to potentially carry out mass revocations
> would be the game-theoretically sensible approach to take:

To be fair, this is not an either/or proposition. The third option is that
they could be ignoring you specifically, which may not be an unreasonable
position, game-theoretically speaking of course.

[Jeremy Rowley]

No one wants to paint a target on their back. If I announce we're 100%
compliant with everything, that's asking to be shot in the face. You're
welcome to look at ours. I think we fully comply with 7.1 (I've double
checked everything) and would love to find out if we're not. I like the
feedback and research so feel free to peel away at the DigiCert parfait.

-----Original Message-----
From: dev-security-policy <dev-security-...@lists.mozilla.org> On

Behalf Of Ryan Sleevi via dev-security-policy
Sent: Wednesday, March 13, 2019 8:03 PM
To: Peter Gutmann <pgu...@cs.auckland.ac.nz>
Cc: mozilla-dev-s...@lists.mozilla.org; Richard Moore
<richm...@gmail.com>
Subject: Re: Pre-Incident Report - GoDaddy Serial Number Entropy

_______________________________________________
dev-security-policy mailing list
dev-secur...@lists.mozilla.org

https://lists.mozilla.org/listinfo/dev-security-policy

[Rob Stradling]

On 13/03/2019 22:28, Richard Moore via dev-security-policy wrote:
> On Tuesday, March 12, 2019 at 11:53:25 PM UTC, Kurt Roeckx wrote:
>>

>> The expected distribution when generating a random 64 bit integer
>> and properly encoding that as DER is that:
>> - about 1/2 integers require 9 bytes
>> - about 1/2 integers require 8 bytes
>> - about 1/512 integers require 7 bytes
>> - about 1/131072 integers require 6 bytes
>> - about 1/33554432 integers require 5 bytes
>> - [...]
>>
>> That a serial is smaller than 8 bytes is not an indication that it
>> doesn't contain enough entropy.
>

> This is true, but the situation is surely worse - any CA who's serial numbers do not have a significant length variation is almost certainly not providing 64 bits of entropy with the exception of those who are add a prefix to ensure it is positive, and even those are not providing it unless they have lots of serial numbers with a big block of zeros.
>

> If any other CA wants to check theirs before someone else does, then now is surely the time to speak up.

Someone else is in the process of checking... ;-)

--
Rob Stradling
Senior Research & Development Scientist
Sectigo Limited

[Rob Stradling]

On 14/03/2019 01:09, Peter Gutmann via dev-security-policy wrote:
<snip>

> I'd already asked previously whether any CA wanted to indicate publicly that
> they were compliant with BR 7.1, which zero CAs responded to (I counted them
> twice).

Peter,

Mozilla Root Store Policy section 2.3 [1] requires CAs to conform to the
latest version of the Baseline Requirements. So ISTM that until or
unless a CA publicly states that they are non-compliant with BR 7.1, we
should act as if that CA has publicly stated that they are compliant
with BR 7.1.

FWIW though, you can find a public statement from Sectigo at [2].


[1]
https://www.mozilla.org/en-US/about/governance/policies/security-group/certs/policy/#23-baseline-requirements-conformance

[2]
https://sectigo.com/blog/all-sectigo-public-certificates-meet-64-bit-serial-number-requirements

[iden...@gmail.com]

IdenTrust confirms compliance: We do not run EJBCA, and our certificate serial number entropy is greater than what is required from BR 7.1.

Marco S.

[Jaime Hablutzel]

> 64bits_entropy = GetRandom64Bits() //This returns 64 random bits from a
> CSPRNG with at least one bit in the highest byte set to 1
>
> is, strictly speaking, not true. The best possible implementation for
> GetRandom64Bits(), as described, only returns 63.994353 bits of entropy,
> not 64.
>

Can you share how did you get the previous 63.994353?.

I'm trying the following and I'm getting a different value:

a = 2^64 = 18446744073709551616
b = 0x80000000000000 = 36028797018963968

(a - b) / a * 64 = 63.875

Maybe I'm misunderstanding something.

[Daymion Reynolds]

That post was for after 3/7. We were fine all along.

[Jaime Hablutzel]

> 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.

"uniqueness and non zero checks" have crippled the effective 64 bit output from the CSPRNG, so, as I can see it, all of your previously generated serial numbers (according to the algorithm you disclosed [1]) could be considered non-compliant to current BRs as explained below:

First, according to your algorithm, if the MSB in the fully random 8 octets is 1 you add a leading 00 byte, so until that time you have 64 full bits of entropy, i.e. 18446744073709551616 possible different values.

Then, you have to filter out some values. To begin with, you filter out the value 0, leaving you with 18446744073709551615 possible values.

Now, you filter the previosly generated serial numbers (known to potential attackers thanks to current CT deployment), let's say 1000000 at a given point in time, so now you are left with 18446744073708551615 possible values.

And if we do the math:

18446744073708551615 / 18446744073709551616 * 64 = 63.999999999996530549578599433858

Which is less than the required 64 bits.

So any filtering operation (e.g. previously generated serial numbers) actually reduce effective entropy and overall security as illustrated in the fictional and forced scenario in [2].

And finally, we can realize that serial number generation algorithms, among others requirements, have to be foresee the number of certificates intended to be generated all along the CA lifetime.

[1] https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/2UIea4fyBgAJ
[2] https://groups.google.com/d/msg/mozilla.dev.security.policy/7WuWS_20758/mgQaADsCCwAJ

[Kurt Roeckx]

On Thu, Mar 14, 2019 at 04:09:10PM -0700, Jaime Hablutzel via dev-security-policy wrote:
> > 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.
>

> "uniqueness and non zero checks" have crippled the effective 64 bit output from the CSPRNG, so, as I can see it, all of your previously generated serial numbers (according to the algorithm you disclosed [1]) could be considered non-compliant to current BRs as explained below:
>
> First, according to your algorithm, if the MSB in the fully random 8 octets is 1 you add a leading 00 byte, so until that time you have 64 full bits of entropy, i.e. 18446744073709551616 possible different values.
>
> Then, you have to filter out some values. To begin with, you filter out the value 0, leaving you with 18446744073709551615 possible values.
>
> Now, you filter the previosly generated serial numbers (known to potential attackers thanks to current CT deployment), let's say 1000000 at a given point in time, so now you are left with 18446744073708551615 possible values.
>
> And if we do the math:
>
> 18446744073708551615 / 18446744073709551616 * 64 = 63.999999999996530549578599433858
>
> Which is less than the required 64 bits.
>
> So any filtering operation (e.g. previously generated serial numbers) actually reduce effective entropy and overall security as illustrated in the fictional and forced scenario in [2].

The most obvious way to implement this is that in case the check
fails, you just generate an other serial. You can argue that that
new serial will contain 64 bit of entropy, but if you want to be
really correct, I think you're right and it doesn't.

Just as example, if you generate 64 bit random numbers, and throw
away all those that have the top bit set, which would be around
half of them, it's easy to see you've reduced it to 63 bit.

So you can argue that it's not possible to comply with the BRs by
just generating a 64 bit random number, you would need to generate
at least 65. But I would argue that such an implementation that
only generates 64 bits and does the checks is in the spirit of what
was intended.


Kurt

[Jaime Hablutzel]

Maths were wrong, sorry. I got your same calculation:

min = 0100000000000000 = 72057594037927936
max = 00FFFFFFFFFFFFFFFF = 18446744073709551615
log2(max - min + 1) = 63.99435343685886

[Jaime Hablutzel]

On Thursday, March 14, 2019 at 6:09:21 PM UTC-5, Jaime Hablutzel wrote:
> > 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.
>
> "uniqueness and non zero checks" have crippled the effective 64 bit output from the CSPRNG, so, as I can see it, all of your previously generated serial numbers (according to the algorithm you disclosed [1]) could be considered non-compliant to current BRs as explained below:
>
> First, according to your algorithm, if the MSB in the fully random 8 octets is 1 you add a leading 00 byte, so until that time you have 64 full bits of entropy, i.e. 18446744073709551616 possible different values.
>
> Then, you have to filter out some values. To begin with, you filter out the value 0, leaving you with 18446744073709551615 possible values.
>
> Now, you filter the previosly generated serial numbers (known to potential attackers thanks to current CT deployment), let's say 1000000 at a given point in time, so now you are left with 18446744073708551615 possible values.
>
> And if we do the math:
>
> 18446744073708551615 / 18446744073709551616 * 64 = 63.999999999996530549578599433858

Again, maths were wrong here, sorry. Correct calculation is:

log2(18446744073708551615) = 63.99999999999993

[Peter Gutmann]

Jaime Hablutzel via dev-security-policy <dev-secur...@lists.mozilla.org> writes:

>Again, maths were wrong here, sorry. Correct calculation is:
>
>log2(18446744073708551615) = 63.99999999999993

I love the way that people are calculating data on an arbitrarily-chosen value
pulled entirely out of thin air to 14 decimal places. It's like summing a
diverging series. Or calculating how many angels can fit on the head of a
pin. Or something.

Peter.

[Jaime Hablutzel]

> So you can argue that it's not possible to comply with the BRs by
> just generating a 64 bit random number, you would need to generate
> at least 65.

Yes, that's right, because the 64 bit entropy won't be left intact after any filtering, even the very basic zero value removal.

> But I would argue that such an implementation that
> only generates 64 bits and does the checks is in the spirit of what
> was intended.

I'm not sure if that could be the intent because it would allow the following to happen: Let's say that the biggest CA in the universe (serving other planets too) has issued the following number of certificates to the time, 18446744073709551614 (2^64 - 2), and now they need to generate a new certificate and there is only one possible serial number to choose from (the other value is the forbidden zero) and the purpose of ballot 164 (i.e. protect against https://fahrplan.events.ccc.de/congress/2008/Fahrplan/attachments/1251_md5-collisions-1.0.pdf) is defeated.

Anyway, the previous is a non-realistic example and I'm well aware that the mass violation under discussion won't affect security in the real world now, but given that in this very moment this is the formally implemented requirement, all violations should be treated according to the regular procedure, unless...

The Mozilla Root Store Policy gets updated with an exceptions handling procedure which could "forgive" retroactively (possible?) this massive violation, e.g. allowing a minimum entropy of 62 bits (or less) for certificates issued until a given date (in the near future) with the purpose to accomodate to the 62 bits [1] of entropy being guaranteed by a default EJBCA <7.0.1 or to the entropy provided by any other known PKI implementation.

So I would like to ask again if there is any possibility to implement some type of exceptions handling as asked in [2].

[1] log2(0x7FFFFFFFFFFFFFFF - 0x80000000000000 + 1) = 62.99435343685886 (or less if certificates has been previously generated)
[2] https://groups.google.com/forum/#!msg/mozilla.dev.security.policy/7WuWS_20758/erK0-f0GCwAJ

[Ryan Sleevi]

On Thu, Mar 14, 2019 at 11:16 PM Jaime Hablutzel via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> So I would like to ask again if there is any possibility to implement some
> type of exceptions handling as asked in [2].
>

This has been repeatedly and unambiguously answered: categorically, the
answer is no.

The analysis and discussion so far is not only demonstrative of what CAs
COULD have done, but what CAs SHOULD have done. If one imagines generating
2^64 certificates, they might pick serials of 2^128 bits of entropy.

It has been repeatedly addressed, for years, in this forum that exceptions
are not granted, and are fundamentally detrimental to the goals of a
transparent and equitable set of expectations for CAs. There's no need to
relitigate that, nor is it appropriate, considering that every matter of CA
non-compliance seems to invoke the same conversation. CAs are ultimately
responsible for their compliance and for their actions following
non-compliance. The revocation policy has been repeatedly clarified, both
individually and generally, as to the expectations.

It's a mistake to conflate non-compliance as a guaranteed removal, just as
it's a mistake to conflate (seeming) compliance with guaranteed inclusion.
Trust is not guaranteed - it's earned, by demonstration of awareness,
knowledge, and responsive handling of issues that demonstrate a holistic
understanding of the issues and risks and a reasonable and consistent
responsiveness.

[Jaime Hablutzel]

> >Again, maths were wrong here, sorry. Correct calculation is:
> >
> >log2(18446744073708551615) = 63.99999999999993
>
> I love the way that people are calculating data on an arbitrarily-chosen value
> pulled entirely out of thin air

Can you confirm if the motivation for the "64 bits of output from a CSPRNG" can be found in [1]?.

> to 14 decimal places. It's like summing a
> diverging series. Or calculating how many angels can fit on the head of a
> pin. Or something.
>
> Peter.

[1] https://www.mail-archive.com/search?l=pub...@cabforum.org&q=subject:%22Re%5C%3A+%5C%5Bcabfpub%5C%5D+Pre%5C-Ballot+164+%5C-+Certificate+Serial+Number+Entropy%22&o=newest

[Peter Bowen]

On Thu, Mar 14, 2019 at 4:33 AM Rob Stradling via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> On 14/03/2019 01:09, Peter Gutmann via dev-security-policy wrote:
> <snip>

> > I'd already asked previously whether any CA wanted to indicate publicly
> that
> > they were compliant with BR 7.1, which zero CAs responded to (I counted
> them
> > twice).
>

> Peter,
>
> Mozilla Root Store Policy section 2.3 [1] requires CAs to conform to the
> latest version of the Baseline Requirements. So ISTM that until or
> unless a CA publicly states that they are non-compliant with BR 7.1, we
> should act as if that CA has publicly stated that they are compliant
> with BR 7.1.
>
> FWIW though, you can find a public statement from Sectigo at [2].
>
>
> [1]
>
> https://www.mozilla.org/en-US/about/governance/policies/security-group/certs/policy/#23-baseline-requirements-conformance
>
> [2]
>
> https://sectigo.com/blog/all-sectigo-public-certificates-meet-64-bit-serial-number-requirements

As I posted in a related thread, we can see that both Boulder and R509
implement serial generation which conforms to BR 7.1. Both of these are
open source open source CA software packages that were written by
organizations that run CAs in the mozilla program. Unless the public code
has different generation semantics than the production code (which would be
very strange), one can surmise users of these packages are compliant.
Additionally many other CAs are known to have built their own software
and/or use software other than EJBCA, so making any generalization isn't
really valid.

Thanks,
Peter

[Jaime Hablutzel]

Hi Daymion, in [1] you said before:

> For the DER format the first two (0)s of the value is the positive sign of the integer. In our case if the un-signed integer value is 64bit and the most significant bit is set, two additional (0)s will be prepended to demonstrate a positive sign. In this case it will be 9bytes instead of 8bytes. Always a minimum of 8bytes (64bits) of entropy. You do still have to manage zero compression for integer values less than 72057594037927936, which will result in 7bytes instead of 8bytes.

Implying that you were preventing an encoding shorter than 8 bytes by filtering values lower than 01 00 00 00 00 00 00 00 (which, by the way, is unnecesarily high to avoid compression as 80 00 00 00 00 00 00 suffices).

But then you said:

> RS - The reduction from >1.8M certificates to 12K certificates is a statement that only those 12K certificates lacked a 64-bit entropy contribution?
> DR – Yes, the 12k certs are only 7bytes or less and therefor do not meet the BRs.

Confirming that you were not filtering out serial numbers shorter than 8 bytes, which contradicts the previous.

Can you please clarify?.

[1] https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/E7uzTWDDBwAJ

[Peter Gutmann]

Jaime Hablutzel via dev-security-policy <dev-secur...@lists.mozilla.org> writes:

>>>Again, maths were wrong here, sorry. Correct calculation is:
>>>
>>>log2(18446744073708551615) = 63.99999999999993
>>
>>I love the way that people are calculating data on an arbitrarily-chosen value
>>pulled entirely out of thin air
>

>Can you confirm if the motivation for the "64 bits of output from a CSPRNG"
>can be found in [1]?.

I actually thought it was from "Chosen-prefix collisions for MD5 and
applications" or its companion papers ("Short chosen-prefix collisions for MD5
and the creation of a rogue CA certificate", "Chosen-Prefix Collisions for MD5
and Colliding X.509 Certificates for Different Identities"), but it's not in
any of those. Even the CCC talk slides only say "We need defense in depth ->
random serial numbers" without giving a bit count. So none of the original
cryptographic analysis papers seem to give any value at all. It really does
seem to be a value pulled entirely out of thin air.

Peter.

[Jaime Hablutzel]

> > So I would like to ask again if there is any possibility to implement some
> > type of exceptions handling as asked in [2].
> >
>
> This has been repeatedly and unambiguously answered: categorically, the
> answer is no.

Could you please provide me a link to a previous discussion where the negative was stated, maybe by the module owner?. But note that I'm not asking for a bespoke or improvised exception for the current issue but for the possibility to introduce a procedure to handle any type of low breach/high disruption violations now and in the future?.

[Ryan Sleevi]

On Fri, Mar 15, 2019 at 12:36 AM Jaime Hablutzel via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Could you please provide me a link to a previous discussion where the
> negative was stated, maybe by the module owner?. But note that I'm not
> asking for a bespoke or improvised exception for the current issue but for
> the possibility to introduce a procedure to handle any type of low
> breach/high disruption violations now and in the future?.
>

"However, Mozilla does not grant exceptions to the BR revocation
requirements." [1]
"In my opinion, Mozilla should not get in to the business of granting
one-off exceptions ..." [2]

[1] https://wiki.mozilla.org/CA/Responding_To_An_Incident
[2]
https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/HNDX5LaZCAAJ
(That's this thread, one week ago)

[Andrew]

Perhaps the solution should be to amend the BRs to allow for more flexible handling of situations such as this.

I understand that'd be rather difficult to formalize, since we can't just trust the CAs to decide for themselves when mass revocation doesn't make sense (as they have a vested interest in not revoking), and security impact isn't something that's easy to objectively quantify. However, the current status quo where millions of certs need to be revoked due to a technicality that has practically no impact on actual security seems silly.

Remember that the security impact of revoking still-in-use certificates that do not actually pose a security risk is negative, as it leads to warning fatigue. Users who frequently encounter warnings about revoked certificates are more likely to bypass those warnings in the future. Not to mention the negative impact on the CA system as a whole, with increased operating costs for CAs and customers alike resulting from the additional work required to replace certificates.

[Wayne Thayer]

On Fri, Mar 15, 2019 at 8:54 AM Andrew via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Perhaps the solution should be to amend the BRs to allow for more flexible
> handling of situations such as this.
>
>

After a long debate, the BR revocation requirements were recently relaxed a
bit. It's not realistic or desirable to again change these requirements
simply as a reaction to the current situation, no matter how silly it seems.

I understand that'd be rather difficult to formalize, since we can't just
> trust the CAs to decide for themselves when mass revocation doesn't make
> sense (as they have a vested interest in not revoking), and security impact
> isn't something that's easy to objectively quantify. However, the current
> status quo where millions of certs need to be revoked due to a technicality
> that has practically no impact on actual security seems silly.
>
>

Anything short of entirely removing the BR revocation requirement would be
impossible to formalize. So we either have a situation in which the BRs
default to assuming that misissuance creates risk, or the BRs default to a
position in which they don't provide any normative guidance. The serial
number problem is a rather extreme example in which misissuance is not
introducing much risk to the web PKI, but we can't predict where future
forms of policy violations will fall in terms of risk.

Remember that the security impact of revoking still-in-use certificates
> that do not actually pose a security risk is negative, as it leads to
> warning fatigue. Users who frequently encounter warnings about revoked
> certificates are more likely to bypass those warnings in the future. Not to
> mention the negative impact on the CA system as a whole, with increased
> operating costs for CAs and customers alike resulting from the additional
> work required to replace certificates.
>
>

I understand that this is a hard problem, but ultimately we need to be able
to replace certificates quickly and easily so that revoking them doesn't
create an availability risk. Heartbleed and SHA-1 are just two events that
provide evidence that we need to be prepared for a serious, widespread
incident that requires mass certificate replacement.

On Friday, March 15, 2019 at 12:11:40 AM UTC-5, Ryan Sleevi wrote:

[ad...@adamcaudill.com]

Daymion,

(Apologies in advance if I've missed something that led to these results. These results rely on the crt.sh database, which I will admit to being less familiar with than I would like.)

While recently looking at some randomly selected recent certificates from this CA: https://crt.sh/?CAID=904, I noticed that it seemed that all had serial numbers with the high bit set. This being unlikely, I took advantage of the fact that crt.sh allows direct database access to get some more data - and it looks like for several days, the certificates logged did indeed have the high bit set in the serial number.

For certificates with a notBefore of 2019-03-07 22:52:51 to 2019-03-13 02:01:15, it appears that all certificates had a serial number with the high bit set; there are a little under 100,000 entries in the crt.sh database with notBefore between those dates, all appear to be encoded to 9 bytes and with the high bit set.

For certificates with notBefore of 2019-03-13 02:01:16 and later, it appears that the distribution returns to what would be expected based on the selection criteria described.

The odds of this happening by random chance being extremely remote - this seems to indicate that there may have been an issue (and a loss of entropy).

The data was pulled from the public crt.sh database, one day at a time, using the following query:

select
c.id,
x509_notBefore(c.CERTIFICATE),
x509_serialNumber(c.CERTIFICATE)
from certificate c
where
c.issuer_ca_id = 904
and x509_notBefore(c.CERTIFICATE) between '2019-03-08'::date and '2019-03-09'::date
limit 100000;

[Daymion Reynolds]

Please read through earlier posts discussing this.

[Daymion Reynolds]

I believe I hit reply to soon, as you are referencing something else. Will look into this.

[Ryan Sleevi]

On Fri, Mar 15, 2019 at 3:35 PM Daymion Reynolds via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> > On Wednesday, March 13, 2019 at 8:17:00 PM UTC-4, Daymion Reynolds wrote:
> >
> > > 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.
>

> Please read through earlier posts discussing this.
>

Daymion,

I was hoping you could respond more. I think based on the discussion on the
list to date, it's actually not clear that GoDaddy was compliant (as noted
in [1]), and Adam's response seems to support that.

A filtering algorithm that "returns 64 random bits from a CSPRNG with at
least one bit in the highest byte set to 1" is fairly ambiguous. If you're
returning 64 random bits AND a byte with at least one bit set to one,
that's different than returning 64 random bits and discarding values which
don't have a bit in the high byte set to one.

[1]
https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/ydp17Nz7BgAJ

[2]
https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/2UIea4fyBgAJ

[Daymion Reynolds]

I am investigating as it does not match my understanding.

[Daymion Reynolds]

The timeline does match expectation.
When the 64bit issue was escalated, GoDaddy decided to apply a fix on 3/7 to meet our BR interpretation of certificate must be “containing at least 64 bits of OUTPUT”. The fastest change was to set a minimum value. This is the source of the most significant bit you are referencing.
https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/F8AS4MNVCAAJ

On 3/12 we discussed what 64bits meant[1], had agreement from Ryan Sleevi[2] any most significant bit would be acceptable. We made the change later that same day to the described configuration. [1=https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/2UIea4fyBgAJ
[2]https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/HeCLu1rzBgAJ

Lastly, it was identified\discussed since we were STARTING with 64bits it was acceptable. Therefore, GoDaddy was in compliance prior to 3/7. After this discussion we changed back to the pre 3/7 configuration on 3/13.
https://groups.google.com/d/msg/mozilla.dev.security.policy/S2KNbJSJ-hs/vqt_XWX6CgAJ

[ad...@adamcaudill.com]

> Lastly, it was identified\discussed since we were STARTING with 64bits it was acceptable. Therefore, GoDaddy was in compliance prior to 3/7. After this discussion we changed back to the pre 3/7 configuration on 3/13.

Thanks for the additional explanation, greatly appreciated.

>From looking at the data, I think there's an open question as to whether GoDaddy was in compliance between those dates.

This is essentially the mirror image of the issue with EJBCA - it was coercing the high bit to zero, thus losing one bit; GoDaddy (between 3/7 and 3/13) was coercing the high bit to one. As these serial numbers were 8 bytes (64 bits), plus one null byte (0x00) to provide the sign when DER encoded, forcing the high bit to one drops the number of randomly selected bits from 64 to 63, below what is specified by BR 7.1.

Unfortunately, to me it looks like while trying to address a possible compliance issue, a compliance issue was introduced.

[Hector Martin 'marcan']

On 15/03/2019 07:13, Jaime Hablutzel via dev-security-policy wrote:
>> 64bits_entropy = GetRandom64Bits() //This returns 64 random bits from a

>> CSPRNG with at least one bit in the highest byte set to 1
>>

>> is, strictly speaking, not true. The best possible implementation for
>> GetRandom64Bits(), as described, only returns 63.994353 bits of entropy,
>> not 64.
>>
>
> Can you share how did you get the previous 63.994353?.
>
> I'm trying the following and I'm getting a different value:
>
> a = 2^64 = 18446744073709551616
> b = 0x80000000000000 = 36028797018963968
>
> (a - b) / a * 64 = 63.875
>
> Maybe I'm misunderstanding something.

Entropy in bits is measured as the log2 of the possible values. So:

>>> math.log2(2**64)
64.0

Of 64-bit numbers, 255/256 have at least one bit set in the highest byte
(only those starting with 00 don't), so:

>>> math.log2(2**64 * 255/256)
63.99435343685886

--
Hector Martin "marcan"
Public key: https://mrcn.st/pub

[Hector Martin 'marcan']

On 15/03/2019 13:26, Peter Gutmann via dev-security-policy wrote:
> I actually thought it was from "Chosen-prefix collisions for MD5 and
> applications" or its companion papers ("Short chosen-prefix collisions for MD5
> and the creation of a rogue CA certificate", "Chosen-Prefix Collisions for MD5
> and Colliding X.509 Certificates for Different Identities"), but it's not in
> any of those. Even the CCC talk slides only say "We need defense in depth ->
> random serial numbers" without giving a bit count. So none of the original
> cryptographic analysis papers seem to give any value at all. It really does

> seem to be a value pulled entirely out of thin air.

To be honest, I see this as a proxy for competence. Complying with the
spec strictly means you're doing the right thing. Complying with the
spec minus a tiny margin of error for practical reasons means you're
probably fine. Mucking things up due to misunderstood notions of entropy
and thus dropping entropy on the floor means you probably shouldn't be
writing CA software. The fact that the bar was pulled from thin air is
irrelevant; nobody here is suggesting that those using 63 bits of
entropy actually *introduced* a tangible security problem. They just
didn't follow the BR rules, which are there to be followed.

Thus:

a) If you use >64 bits of CSPRNG output raw, you're fine (assuming any
practical CA size).

b) If you use exactly 64 bits of CSPRNG output with duplicate and zero
checks, such that the odds of those checks ever *actually* rejecting a
serial number based on the number of issued certs are < (say) 1%, then
you're fine. For all *practical* intents and purposes you have 64 bits
of entropy.

Ideally you'd have used more bits to avoid risking a duplicate serial
discarding entropy, but at 64 bits, and doing the math for the birthday
problem, the threshold for 1% chance is at about 608 million
certificates [1]. If you've issued less than that number, you have a
less than 1% chance of having ever rejected a single serial number due
to the duplicate check (the zero check is negligible in comparison). It
can be argued that if the problematic code never ran, then it might as
well have never been there. Of course, *proving* that the code never ran
is unlikely to be possible. Ultimately, entropy was reduced by the
presence of that code, even if the outcome was identical to that had it
not been there.

That said, it's quite *reasonable* to write the code this way; no
strange misunderstandings are required. You had 64 bits of entropy and
you applied a required check that negligibly reduced that; it's
certainly better to lose a tiny fraction of a bit of entropy than to
risk a duplicate serial.

c) If you're dropping serials with e.g. the top 8 bits set to zero (as
per Daymion's algorithm), then you very clearly have 63.994353 bits of
entropy, for no good reason. This is problematic, because it clearly
demonstrates a *misunderstanding* of how entropy works and what the
whole point of using 64 bits of raw CSPRNG output is. This is a BR
violation in any strict reading, and readily provable by looking at
serial number distribution.

d) If you're coercing the top bit (EJBCA defaults), then that's clearly
63 bits of entropy, not 64, and of course a BR violation; it doesn't
take a cryptanalyst to realize this, and anyone who isn't trying to
"creatively interpret" the rules to weasel out of admitting
non-compliance can see that 63 < 64 and there's no way to have 64 bits
of entropy in a number where one bit never changes.

[1] See
https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem :

>>> math.sqrt(2*(2**64) * math.log(1/(1 - 0.01)))
608926881.2334852

[Rob Stradling]

On 14/03/2019 10:59, Rob Stradling via dev-security-policy wrote:
> On 13/03/2019 22:28, Richard Moore via dev-security-policy wrote:
<snip>
>> If any other CA wants to check theirs before someone else does, then now is surely the time to speak up.
>
> Someone else is in the process of checking... ;-)

The purpose of this survey is to flush out any further CAs that are (or
have been) noncompliant with BR 7.1 but have not yet disclosed an
incident.

Having scanned the crt.sh database, I have produced the following
spreadsheet. It covers all certificates known to crt.sh where the
notBefore date is between 30th September 2016(*) and 22nd February
2019(**), and where the issuing CA...
- is currently trusted by Mozilla to issue serverAuthentication
certificates, and
- has issued at least 1 certificate with a <64-bit serial number.

https://docs.google.com/spreadsheets/d/1K96XkOFYaCIYOdUKokwTZfPWALWmDed7znjCFn6lKoc/edit?usp=sharing

When a value in column E is 100%, this is pretty solid evidence of
noncompliance with BR 7.1.
When the values in column E and G are both approximately 50%, this
suggests (but does not prove) that the CA is handling the output from
their CSPRNG correctly.

For some issuing CAs, the sample sizes are too small to be able to draw
any conclusions.


(*) This date was chosen because BR 7.1 says:
"Effective September 30, 2016, CAs SHALL generate non-sequential
Certificate serial numbers greater than zero (0) containing at least 64
bits of output from a CSPRNG."

(**) This is when Wayne started the discussion about DarkMatter, which
is what prompted the discovery that many CAs were falling short of BR 7.1.

--
Rob Stradling
Senior Research & Development Scientist
Sectigo Limited

[Rob Stradling]

On 18/03/2019 15:30, Rob Stradling via dev-security-policy wrote:
<snip>

> On 14/03/2019 10:59, Rob Stradling via dev-security-policy wrote:
>> On 13/03/2019 22:28, Richard Moore via dev-security-policy wrote:
> <snip>
>>> If any other CA wants to check theirs before someone else does, then now is surely the time to speak up.
>>
>> Someone else is in the process of checking... ;-)
>
> The purpose of this survey is to flush out any further CAs that are (or
> have been) noncompliant with BR 7.1 but have not yet disclosed an
> incident.

Columns A and B are currently empty. They are intended to hold a
Bugzilla URL and the date on which the bug was filed.

Jonathan Rudenberg has offered to review the disclosures that have been
posted by CAs so far (thanks Jonathan!), so I've given him edit rights
to the spreadsheet.

[Rob Stradling]

On 18/03/2019 15:43, Rob Stradling via dev-security-policy wrote:
> On 18/03/2019 15:30, Rob Stradling via dev-security-policy wrote:
> <snip>
>> On 14/03/2019 10:59, Rob Stradling via dev-security-policy wrote:
>>> On 13/03/2019 22:28, Richard Moore via dev-security-policy wrote:
>> <snip>
>>>> If any other CA wants to check theirs before someone else does, then now is surely the time to speak up.
>>>
>>> Someone else is in the process of checking... ;-)
>>
>> The purpose of this survey is to flush out any further CAs that are (or
>> have been) noncompliant with BR 7.1 but have not yet disclosed an
>> incident.

The report now also includes issuing CAs whose certificates have not
been disclosed to the CCADB, which of course is permitted for
technically-constrained intermediates. (Many thanks to the person who
pointed out this oversight to me).

> Columns A and B are currently empty. They are intended to hold a
> Bugzilla URL and the date on which the bug was filed.
>
> Jonathan Rudenberg has offered to review the disclosures that have been
> posted by CAs so far (thanks Jonathan!), so I've given him edit rights
> to the spreadsheet.

Jonathan has finished filling in Columns A & B for all of the
disclosures he's seen so far.

[Kurt Roeckx]

On Mon, Mar 18, 2019 at 03:30:37PM +0000, Rob Stradling via dev-security-policy wrote:
>
> When a value in column E is 100%, this is pretty solid evidence of
> noncompliance with BR 7.1.
> When the values in column E and G are both approximately 50%, this
> suggests (but does not prove) that the CA is handling the output from
> their CSPRNG correctly.

Sould F/G say >= 64, instead of > 64?


Kurt

[Rob Stradling]

Yes. Fixed. Thanks!

[Hector Martin 'marcan']

On 19/03/2019 02.17, Rob Stradling via dev-security-policy wrote:
> On 18/03/2019 17:05, Kurt Roeckx wrote:
>> On Mon, Mar 18, 2019 at 03:30:37PM +0000, Rob Stradling via dev-security-policy wrote:
>>>
>>> When a value in column E is 100%, this is pretty solid evidence of
>>> noncompliance with BR 7.1.
>>> When the values in column E and G are both approximately 50%, this
>>> suggests (but does not prove) that the CA is handling the output from
>>> their CSPRNG correctly.
>>
>> Sould F/G say >= 64, instead of > 64?
>
> Yes. Fixed. Thanks!

Perhaps it would make sense to separate out <64, ==64, >64?

100% "64-bit" serial numbers would indicate an algorithm using 63 bits
of entropy and the top bit coerced to 1.


--
Hector Martin "marcan" (mar...@marcan.st)
Public Key: https://mrcn.st/pub

[Rob Stradling]

Even better than that (and many thanks to Andrew Ayer for suggesting
this idea)...

To enable folks to do more thorough statistical analysis, I've produced
another, richer summary table (named serial_number_entropy_20190325) on
the crt.sh DB where each row contains...
- the CA ID.
- a count of the total number of unique serial numbers.
- 160 counts, representing the number of times a given serial number bit
is 1. (Serial numbers of <20 octets were left-padded with 0x00 bytes).

This report covers all serial numbers in certs known to crt.sh where:
- there is an unrevoked serverAuthentication trust path to a Mozilla
built-in root.
- the notBefore date is between 2018-04-01 and 2019-02-22.

Duplicate serial numbers (i.e., precertificate/certificate pairs) are
deduplicated.

[Doug Beattie]

Rob,

I'm sure you provided this info somewhere, but I can't figure our where the
new summary table (named serial_number_entropy_20190325) is located. Is it
somewhere on your Google Doc, or somewhere else?

https://docs.google.com/spreadsheets/d/1K96XkOFYaCIYOdUKokwTZfPWALWmDed7znjC
Fn6lKoc/edit#gid=1093195185

_______________________________________________
dev-security-policy mailing list
dev-secur...@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-security-policy

[Wayne Thayer]

Doug: You'll need to connect directly to the certwatch database using a
tool like psql:
psql -h crt.sh -p 5432 -U guest certwatch

Here's Rob's announcement of direct database access:
https://crt.sh/forum?place=msg%2Fcrtsh%2FsUmV0mBz8bQ%2FK-6Vymd_AAAJ

On Tue, Mar 26, 2019 at 11:34 AM Doug Beattie via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Rob,
>
> I'm sure you provided this info somewhere, but I can't figure our where the
> new summary table (named serial_number_entropy_20190325) is located. Is it
> somewhere on your Google Doc, or somewhere else?
>
>
> https://docs.google.com/spreadsheets/d/1K96XkOFYaCIYOdUKokwTZfPWALWmDed7znjC
> Fn6lKoc/edit#gid=1093195185

> <https://docs.google.com/spreadsheets/d/1K96XkOFYaCIYOdUKokwTZfPWALWmDed7znjCFn6lKoc/edit#gid=1093195185>

[Andrew Ayer]

On Mon, 25 Mar 2019 22:16:27 +0000

Rob Stradling via dev-security-policy
<dev-secur...@lists.mozilla.org> wrote:

> Even better than that (and many thanks to Andrew Ayer for suggesting
> this idea)...
>
> To enable folks to do more thorough statistical analysis, I've
> produced another, richer summary table (named
> serial_number_entropy_20190325) on the crt.sh DB where each row
> contains...
> - the CA ID.
> - a count of the total number of unique serial numbers.
> - 160 counts, representing the number of times a given serial number
> bit is 1. (Serial numbers of <20 octets were left-padded with 0x00
> bytes).
>
> This report covers all serial numbers in certs known to crt.sh where:
> - there is an unrevoked serverAuthentication trust path to a Mozilla
> built-in root.
> - the notBefore date is between 2018-04-01 and 2019-02-22.
>
> Duplicate serial numbers (i.e., precertificate/certificate pairs) are
> deduplicated.

Thanks for creating this report Rob!

I used the following query to estimate the serial number entropy of
every CA which has issued more than 1,000 certificates:

SELECT issuer_ca_id,(SELECT COUNT(*) FROM (SELECT unnest(bit_position_sums)/(cert_count::float) AS ratio) subq WHERE ratio >= 0.45 AND ratio <= 0.55) AS entropy_estimate FROM serial_number_entropy_20190325 WHERE cert_count > 1000 ORDER BY issuer_ca_id;

(This query considers a bit "random" if it's 1 between 45% and 55% of
the time.)

Fortunately, this did not find any CA not already listed in Rob's
spreadsheet.

Regards,
Andrew