Serial number length

[Jakob Bohm]

After looking at some real certificates both in the browser and on
crt.sh, I have some followup questions on certificate serial numbers:

1. Do all recently issued certificates have to contain at least 64 bits
of randomness in their serial numbers?

2. Is it acceptable for a CA to satisfy this requirement by generating
random 64 bit serial numbers and checking if there is a certificate
with that random serial before using it?

3. Or would the elimination in #2 reduce the entropy of such serial
numbers to slightly less than 64 bits (since there are less than 2**64
allowed values for all but the first such certificate)?

4. If the answers are yes, no, yes, why doesn't cablint flag
certificates with serial numbers of less than or equal to 64 bits as
non-compliant?


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[Peter Bowen]

On Thu, Dec 28, 2017 at 10:24 PM, Jakob Bohm via dev-security-policy
<dev-secur...@lists.mozilla.org> wrote:
> After looking at some real certificates both in the browser and on crt.sh, I
> have some followup questions on certificate serial numbers:
>

> 4. If the answers are yes, no, yes, why doesn't cablint flag
> certificates with serial numbers of less than or equal to 64 bits as
> non-compliant?

I can answer #4 -- your trusty cablint maintainer has fallen behind
and hasn't added lints for recent ballots.

[Nick Lamb]

On Fri, 29 Dec 2017 07:24:31 +0100

Jakob Bohm via dev-security-policy
<dev-secur...@lists.mozilla.org> wrote:

> 3. Or would the elimination in #2 reduce the entropy of such serial
> numbers to slightly less than 64 bits (since there are less than
> 2**64 allowed values for all but the first such certificate)?

The tremendous size of the numbers involved means that in practice this
makes no difference. A single collision only becomes likely (not
certain, merely likely) over the course of issuing billions of such
certificates.

If I'm right a decision to append a further byte (say 0x42) to the
serial number any time a collision would otherwise occur would have
the same _visible_ effect as just throwing away the colliding number and
choosing another, ie no effect because collisions don't actually
happen in practice.

[ In my day job I maintain a system which uses a 64-bit hash of URLs to
index them. We are conscious that by the pigeon hole principle this hash
could sometimes confuse two URLs and there's a safeguard to detect that.
Despite processing millions of URLs this way every day, for several
years, the safeguard has never triggered outside of unit tests. Perhaps
one day it will. ]

It wouldn't surprise me if some CAs actually don't check #2 at all.
Since collisions are so unlikely with truly random serial numbers it
might well never come up, even if you explicitly looked for it, so that
this "failure" might have no detectable consequence for a smaller CA
even over the course of decades of operation.

So far as we know ISRG / Let's Encrypt are issuing the largest volume
from a single subCA of any CA, but I believe they just use a lot more
than 64-bits, which is a rational choice here to avoid answering tricky
philosophical questions about integers. I would commend this approach
to other CAs wondering how best to comply.

Final thought: The linter should check for at least 64-bits, but it
can't check for true randomness (doing so may be literally impossible in
fact) so anything further should be left for human observers and/or CA
auditors.

Nick.

[Ryan Sleevi]

On Fri, Dec 29, 2017 at 1:24 AM, Jakob Bohm via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> After looking at some real certificates both in the browser and on crt.sh,
> I have some followup questions on certificate serial numbers:
>

> 1. Do all recently issued certificates have to contain at least 64 bits
> of randomness in their serial numbers?
>

https://cabforum.org/wp-content/uploads/CA-Browser-Forum-BR-1.5.4.pdf

Section 7.1

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.

> 2. Is it acceptable for a CA to satisfy this requirement by generating
> random 64 bit serial numbers and checking if there is a certificate
> with that random serial before using it?
>

https://tools.ietf.org/html/rfc5280#section-4.1.2.2

The serial number MUST be a positive integer assigned by the CA to
each certificate. It MUST be unique for each certificate issued by a
given CA (i.e., the issuer name and serial number identify a unique
certificate). CAs MUST force the serialNumber to be a non-negative
integer.

> 3. Or would the elimination in #2 reduce the entropy of such serial
> numbers to slightly less than 64 bits (since there are less than 2**64
> allowed values for all but the first such certificate)?
>

As the goal is to ensure robustness against collisions, particularly aided
by predictability in the construction of the serial number, yes.

> 4. If the answers are yes, no, yes, why doesn't cablint flag
> certificates with serial numbers of less than or equal to 64 bits as
> non-compliant?
>

Peter answered that already.

[Jakob Bohm]

However, the "random-with length-extension on collision" algorithm has
some other (non-BR) shortcomings:

- It is sailing very close to the edge of compliance for little or no
good reason.

- If the collision case is ever triggered, chances are high that other
parts of the CA system have not been tested with different length
serial numbers from the same issuing CA, thus causing larger failures,
such as OCSP responders returning incorrect results for the colliding
certificates.

Another algorithm that would produce occasional <= 64 bit serial numbers
while remaining compliant is:

- Generate 64 random bits.
- Append a 15 bit counter resulting in a 15 to 79 bit serial number (up
to 10 bytes).
- Rotate issuing CAs before the counter wraps.

Here a small fraction (1 in 65536 certificates thus about one per two
issuing CAs if all 32768 counter values are used) will randomly be 64
bits or shorter due to the first 16 random bits being zero.

So

- 63-bit serial numbers are highly suspicious (the algorithm you
provided would produce them for half the certificates, other algorithms
much less frequently, if at all).

- 64-bit serial numbers would be cause for concern, but would require
more thorough analysis, perhaps even a code audit.

- >= 65-bit serial numbers are a lot less likely to be violating the
entropy requirement BR.

So perhaps:

- Generate an informational warning for 64-bit serial numbers.

- Generate a stronger warning for 33 to 63-bit serial numbers.

- In a separate tool check if an issuing CA produces shorter-than-64-bit
serial numbers more frequently than a random distribution (with some
margin).

- One simple test could be to dump the serial numbers from an issuing CA
(without DER formatting, leading zeroes etc.) as bare unsigned numbers
with no fomatting, pipe this into gzip -9 or zlib and check if the
resulting output is less than 8 bytes per certificate.

- A more sophisticated whole-CA test could first sort the serials
numerically, then do pairwise subtracts of all but the first before
converting to bare (signed) binary numbers and compressing. This would
reduce false entropy from pure counter bits.

[Ryan Sleevi]

Or just generate longer serials with random.

Which is much simpler.

On Fri, Dec 29, 2017 at 11:57 AM, Jakob Bohm via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> On 29/12/2017 13:55, Nick Lamb wrote:
>

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

[David E. Ross]

I know this would require changing not only software but also the format
of certificates. However, why not use UUID version 1? UUIDs
(Universally Unique IDentifiers) require no central registry. UUIDs are
specified in RFC 4122.

>From <https://www.uuidgenerator.net/>:
> A Version 1 UUID is a universally unique identifier that is generated
> using a timestamp and the MAC address of the computer on which it was
> generated.MAC addresses are supposed to be unique for each device. Continuously
varying time means that time-stamps are unique to the device, not
rolling over until around the year 3400.

Yes, it is possible that the manufacturer of a device -- especially now
with so many IoT devices being developed -- might reuse a MAC address.
This problem can be overcome if certification authorities are required
to obtain confirmation from their hardware suppliers that the MAC
addresses in their devices are indeed unique.

--
David E. Ross
<http://www.rossde.com/>

President Trump: Please stop using Twitter. We need
to hear your voice and see you talking. We need to know
when your message is really your own and not your attorney's.

[Paul Kehrer]

On December 29, 2017 at 12:27:35 PM, David E. Ross via dev-security-policy (

dev-secur...@lists.mozilla.org) wrote:

On 12/28/2017 10:33 PM, Peter Bowen wrote:

I know this would require changing not only software but also the format
of certificates. However, why not use UUID version 1? UUIDs
(Universally Unique IDentifiers) require no central registry. UUIDs are
specified in RFC 4122.

Modern X509 uses serial number as both a source of randomness and a unique
identifier. Unfortunately, trying to solve for uniqueness doesn't absolve
you from needing quality randomness. The reason for the "at least 64-bits
of random" requirement is to add entropy to the tbsCertificate structure to
make hash collision attacks more difficult. UUIDv1 is (almost) entirely
predictable and thus not suitable for this. And if you have a good random
source you might as well just generate a long random serial which has a
vanishingly small probability of collision.

>From <https://www.uuidgenerator.net/>:
> A Version 1 UUID is a universally unique identifier that is generated
> using a timestamp and the MAC address of the computer on which it was
> generated.MAC addresses are supposed to be unique for each device.
Continuously
varying time means that time-stamps are unique to the device, not
rolling over until around the year 3400.

Yes, it is possible that the manufacturer of a device -- especially now
with so many IoT devices being developed -- might reuse a MAC address.
This problem can be overcome if certification authorities are required
to obtain confirmation from their hardware suppliers that the MAC
addresses in their devices are indeed unique.



--
David E. Ross
<http://www.rossde.com/>

President Trump: Please stop using Twitter. We need
to hear your voice and see you talking. We need to know
when your message is really your own and not your attorney's.

[Jakob Bohm]

I was exploring what legitimate reasons/excuses there could be for a CA
to have serial numbers that happen to be 64 bits long, not good ways to
generate serial numbers.

The overall context is to propose automated tests to be run against CT
data or other certificates to detect CAs that fail to include the
required 64 bits of entropy in the serial numbers (as per the BRs).

If you have access to a CA implementation, you may want to check if it
issues short (<= 64 bits) serial numbers and if it actually complies
with the >=64 bit entropy BR requirement, just as a precaution.

[Tim Hollebeek]

> -----Original Message-----
> From: dev-security-policy [mailto:dev-security-policy-
> bounces+tim.hollebeek=digice...@lists.mozilla.org] On Behalf Of Paul
> Kehrer via dev-security-policy
> Sent: Friday, December 29, 2017 12:46 PM
> To: mozilla-dev-s...@lists.mozilla.org
> Subject: Re: Serial number length
>
> On December 29, 2017 at 12:27:35 PM, David E. Ross via dev-security-policy
(
> dev-secur...@lists.mozilla.org) wrote:
>
> On 12/28/2017 10:33 PM, Peter Bowen wrote:

> I know this would require changing not only software but also the format
of
> certificates. However, why not use UUID version 1? UUIDs (Universally
Unique
> IDentifiers) require no central registry. UUIDs are specified in RFC 4122.
>
> Modern X509 uses serial number as both a source of randomness and a unique
> identifier. Unfortunately, trying to solve for uniqueness doesn't absolve
you
> from needing quality randomness. The reason for the "at least 64-bits of
> random" requirement is to add entropy to the tbsCertificate structure to
make
> hash collision attacks more difficult. UUIDv1 is (almost) entirely
predictable
> and thus not suitable for this. And if you have a good random source you
might
> as well just generate a long random serial which has a vanishingly small
> probability of collision.

The baseline requirements don't just require 64 bits of good randomness.
They
specifically require the use of a CSPRNG ("A random number generator
intended
for use in cryptographic system", the grammar error is in the BRs and the
original
ballot 164).

So things like UUIDs and MACs are clearly not compliant on their own, and
count
for zero bits, regardless of how unpredictable they may or may not be.

In fact, I noticed last month that there's no requirement that random
numbers
used for domain control validation come from a CSPRNG. I intend to fix that
this month ... maybe I'll fix the grammar error while I'm at it.

-Tim

[Gervase Markham]

Hi,

On 29/12/17 06:24, Jakob Bohm wrote:
> 1. Do all recently issued certificates have to contain at least 64 bits
>   of randomness in their serial numbers?

Yes. (References given by others.)

> 2. Is it acceptable for a CA to satisfy this requirement by generating
>   random 64 bit serial numbers and checking if there is a certificate
>   with that random serial before using it?

IMO Yes. The requirement is specifically to include 64 bits of output
from a CSPRNG. Bits don't stop being from a CSPRNG just because they've
compared unequally with a list of other sets of bits.

> 3. Or would the elimination in #2 reduce the entropy of such serial
>   numbers to slightly less than 64 bits (since there are less than 2**64
>   allowed values for all but the first such certificate)?

Technically, it would, but I don't think that's a problem as the
requirement is written, and I don't think it's a problem in practice
because the entropy reduction is so slight and the error margin is
intentionally large.

2^64 is 18,446,744,073,709,552,000. Even if you issue a billion
certificates, the entropy reduction is 0.0000001%. (May be off by an
order of mag. or two, but roughly that.)

Gerv