Entropy of certificate serial number

[Lijun Liao]

In the last days, the issue related to the 63 bit serial number by using
the default configuration of EJBCA poped up in many forums.

Could someone please explain why the BR requires the minimal entropy to be
64 bit?

Best regards
Lijun

[Alex Gaynor]

Hi Lijun,

Entropy is required in serial numbers to protect against weak hash
functions -- historically exploitation of MD5's weakness was possible
because CAs used sequential serial numbers, thus allowing an attacker to
pre-compute hash prefixes, because they could predict future data that
would be signed's prefix. The exact value of 64 comes out of a Microsoft
Root Program requirement that was later incorporated into the BRs, as I
recall.

Cheers,
Alex

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

[Lijun Liao]

With random serial numbers an adversary does not even need to guess the
serial number.

Consider the following attack, the adversary finds a certificate with weak
hash algorithm. He adds his host to the SAN field, then he tries to find
out a positive serial number up to 20 octets which results in the same hash
of the tbsCertificate. Since the serial number octets are random, one
cannot find out whether this is a modified certificate or not. Indeed in
this case, higher entropy simplifies this attack.

Best regards
Lijun

[Tim Shirley]

If it were possible to do what you're suggesting, there's no reason you'd need to use the serial number for it. You could just as easily add that randomness in an additional SAN, or a certificate extension that the browser didn't care about. In fact, since the BRs require SHA-256 as a minimum hash algorithm, and you only have 159 bits to work with in the serial number field, there's only a 1 in 2^97 (158 billion billion billion) chance that would give you enough randomness to where there even exists a value you could set that would work (ignoring the challenge of finding that value.) I've not heard of any attacks where someone could start with an already-issued certificate and work backwards to find a collision, however.

The MD5 attack (https://fahrplan.events.ccc.de/congress/2008/Fahrplan/attachments/1251_md5-collisions-1.0.pdf) was predicated on the attacker knowing exactly what was going to be in the certificate outside of the bits they control, far enough in advance of it being issued to be able to do the collision calculations to determine what other inputs they could feed in to make the collision possible. That exact prediction of the contents of the certificate had to include the actual values of the "not before" and "not after" to the second as well as the serial number value. Any unpredictability in those fields makes that attack harder, and 64 bits of unpredictability makes it effectively impossible. That was the motivation behind the requirement as I understand it.

>> https://scanmail.trustwave.com/?c=4062&d=8fen3GYDv5KnmIy2Xr-0e5uaoDeNGtjgffCW9PJ80w&s=5&u=https%3a%2f%2flists%2emozilla%2eorg%2flistinfo%2fdev-security-policy

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

https://scanmail.trustwave.com/?c=4062&d=8fen3GYDv5KnmIy2Xr-0e5uaoDeNGtjgffCW9PJ80w&s=5&u=https%3a%2f%2flists%2emozilla%2eorg%2flistinfo%2fdev-security-policy

[Lijun Liao]

Hi Tim,

Thanks for your reply.

First to your questions:

1. The purpose of serial number is to identify the certificate, not to make
it secure. It will be used in the CRL, OCSP, etc. as identifier.

2. Unfortually yes, you can change the SAN and some non-critical extensions
to get the same hash value over tbsCertificate if the hash algo is not
cryptographically secure.

3. Yes only SHA256 can be used in the new certificate, but what about those
existing with SHA1? They still remain valid for given period of time. This
may also happen for SHA256.

4. Remember that SHA256 is only 128 bit secure, not 256. So 159 bit is
large enough.

5. Related to how the MD5 attacks you might be right. But theoretically,
and also in practice, if you have enough bits to play and the hash
algorithm is not cryptographically secure, you can find a collision with
less complexity than the claimed one.

So IMO the only reason to increase the entropy of serial number is not to
increase the security, but to reduce the possibility to issue certificate
with identical serial numbers, since not all CAs have mechanism to prevent
from this.

Best regards
Lijun

[Hector Martin 'marcan']

On 06/04/2019 03.01, Lijun Liao via dev-security-policy wrote:
> 5. Related to how the MD5 attacks you might be right. But theoretically,
> and also in practice, if you have enough bits to play and the hash
> algorithm is not cryptographically secure, you can find a collision with
> less complexity than the claimed one.

No, not in practice. There are different levels of "not
cryptographically secure". What you are talking about is preimage
resistance - the ability to construct an input to the hash algorithm
that produces a given, fixed, arbitrary output. There are no such
practical attacks on MD5 or SHA-1.

What the serial number entropy requirement seeks to mitigate are
collision attacks, in particular chosen-prefix collision attacks. This
is the attack that was used to break MD5. This means that you can
construct two messages with the same hash, by modifying both, given a
chosen (known, not modifiable) prefix for each message. Due to the
Merkle-Damgård construction of MD5 and SHA-1, these collisions are also
inherently arbitrary-suffix (after you get two partial messages to
collide, you can append the same arbitrary data to both and they will
still collide).

The serial number entropy requirement effectively mitigates collision
attacks, because the serial number is one of the first pieces of
information in the certificate, well before any attacker-controlled
data. In order to implement a chosen-prefix collision attack, you need
to predict the serial number. If the serial number has at least 64 bits
of entropy, then you would have to try to obtain around 2^63 colliding
certificates on average to match a precomputed collision. Note that the
birthday paradox does not apply here, because any given certificate can
only be obtained for any given collision attempt; it doesn't matter if
you compute 2^32 collisions and then try to get 2^32 certificates,
because *each one* of those certificates has to be obtained for a
*single* collision attempt embedded into it.

Note that the practical SHA-1 attack that was demonstrated was even
weaker than this, as it wasn't a chosen-prefix attack (each message has
a different prefix), but rather an identical-prefix attack (each message
has the *same* prefix, and the messages only differ in the
collision-generating blocks). This is less powerful, but still
sufficient for practical attacks, e.g. I bet you could combine it with
the x.509 structure to yield useful conditional parsing, much like the
demonstrated SHA-1 collision combined it with the JPEG structure to
yield conditional parsing. The serial number entropy requirement also
mitigates this weaker attack, of course.

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

[lijun...@gmail.com]

Thanks for the detailed declaration. I did not consider that the serialNumber is in the very first block of hash input.