Subject: [pkix] RFC 5280 and the maximum permitted value for certificate serial number

From: Nikolai Koustov <[email-masked]>
Date: Thu, 3 Mar 2011 14:57:26 +0000

Hello everybody,

My question is in relation with the RFC 5280
(https://datatracker.ietf.org/doc/rfc5280/) and the maximum permitted
value for the certificate serial number and rules for CA when
generating a certificate serial number.

The Certificate Serial Number field is defined as follows (4.1.2.2.
Serial Number):
<quote>
  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.

  Given the uniqueness requirements above, serial numbers can be
  expected to contain long integers.  Certificate users MUST be able to
  handle serialNumber values up to 20 octets.  Conforming CAs MUST NOT
  use serialNumber values longer than 20 octets.
</quote>

Also,  Appendix B. ASN.1 Notes further clarifies on the matter:
<quote>
  CAs MUST force the serialNumber to be a non-negative integer, that
  is, the sign bit in the DER encoding of the INTEGER value MUST be
  zero.  This can be done by adding a leading (leftmost) `00'H octet if
  necessary.  This removes a potential ambiguity in mapping between a
  string of octets and an integer value.
</quote>

Given the nature of ASN.1 INTEGER (a signed big integer) as well as
the DER-encoding rules, does it mean the following:
1) the maximum value for X.509 certificate serial number is 2^159-1,
i.e 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF in Hexadecimal notation
2) the ASN.1 encoding for this value in Hexadecimal notation is 02 14
7F FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

Also, regarding the serial numbers below the maximum value, is it
valid to assume that the serial numbers like F7 and C1 etc. should NOT
be used and instead 00:F7 and 00:C1 should be used instead ?

Thanks and regards,
Nikolai Koustov.

---

From: Thomas Pornin <[email-masked]>
Date: Thu, 03 Mar 2011 12:56:22 -0500

> 7F FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

Yes.

> be used and instead 00:F7 and 00:C1 should be used instead ?

As an "integer" the distinction is meaningless. 247 is 247. As per ASN.1
DER encoding rules, 247 is to be encoded as: 02 02 00 F7. Encoding it as
02 01 F7 would be incorrect: this is the encoding of -9, not of 247.

The prohibitions in RFC 5280 make more sense if you imagine an
application which handles the "serial number" as a bunch of bytes, not
as an "integer value". They mean that the DER value should consist of no
more than 20 bytes, and such that the most significant bit of the first
byte is a zero. If your code handles the ASN.1 INTEGER as an integer,
then complying to those rules means that the serial number shall have a
value between 0 (inclusive) and 2^159 (exclusive).

Note: DER furthermore mandates that if the first byte of the value is
0x00, then the most significant bit of the second byte must be one. I.e.
the correct encoding of 120 is "02 01 78", not "02 02 00 78".

The undertone of all that is that you should emit strict DER, but be
prepared to receive opaque blobs in return. There could be some legacy
certificates where the serial number is encoded as a value longer than
20 bytes, or decodes as a negative value, or has a non-DER encoding with
too many leading zero-bits. You MUST NOT produce certificates with such
encodings of the serial number, but you SHOULD be able to accept such
certificates nonetheless.

	--Thomas Pornin

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 04 Mar 2011 14:28:54 +1300

Thomas Pornin <[email-masked]> writes:

>The prohibitions in RFC 5280 make more sense if you imagine an application
>which handles the "serial number" as a bunch of bytes, not as an "integer
>value". They mean that the DER value should consist of no more than 20 bytes,
>and such that the most significant bit of the first byte is a zero. If your
>code handles the ASN.1 INTEGER as an integer, then complying to those rules
>means that the serial number shall have a value between 0 (inclusive) and
>2^159 (exclusive).

A simpler way to look at it is that if you're using the ever-popular SHA-1
hash as a serial number then you take the hash, set the first bit to zero,
slap an 02 14 in front, and that's your serial number.

Peter.

---

From: Santosh Chokhani <[email-masked]>
Date: Thu, 3 Mar 2011 22:46:11 -0500

And how do you make the serial number unique?

Howsoever unlikely, SHA-1 hash may not be unique.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Peter Gutmann
Sent: Thursday, March 03, 2011 8:29 PM
To: [email-masked]; [email-masked]
Cc: [email-masked]
Subject: Re: [pkix] RFC 5280 and the maximum permitted value for certificate serial number

Peter.
_______________________________________________
pkix mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/pkix

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 04 Mar 2011 17:02:35 +1300

>Howsoever unlikely, SHA-1 hash may not be unique.

Given that the chances of a duplicate are 1 in 2^159, I'm not going to be
losing any sleep over it.

Peter.

---

From: Tomas Gustavsson <[email-masked]>
Date: Fri, 04 Mar 2011 10:03:58 +0100

And to have your suspenders on as well you can always implement checks
(unique index in a database anyone?) when storing a certificate that
it's not a duplicate and discard if it is.

/Tomas

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 04 Mar 2011 23:56:18 +1300

Tomas Gustavsson <[email-masked]> writes:

>(unique index in a database anyone?) when storing a certificate that it's not
>a duplicate and discard if it is.

The chances of getting a check like this wrong are going to be about two dozen
orders of magnitude higher than the chances of a collision, but if you must...

Peter.

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 04 Mar 2011 08:11:15 -0500

> slap an 02 14 in front, and that's your serial number.

Actually this procedure has a 1/256 chance of resulting in an encoding
which does not comply with strict DER rules: you could end up with 9 or
more leading zero-bits. This illustrates the kind of abuse which can be
encountered in practice: although X.509 mandates DER encoding, one had
better include some provision to cope with not-really-DER things in
existing certificates.

	--Thomas Pornin

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 05 Mar 2011 02:40:36 +1300

Thomas Pornin <[email-masked]> writes:

>Actually this procedure has a 1/256 chance of resulting in an encoding which
>does not comply with strict DER rules: you could end up with 9 or more
>leading zero-bits. 

Yeah, I forgot to consult my own code before posting that :-).  A quick fix is
to set the first two bits to 01.

Peter.

---

From: Tom Gindin <[email-masked]>
Date: Fri, 4 Mar 2011 09:42:59 -0500

Peter:

        It's nowhere near that extreme.  If N is the base 2 logarithm of 
the number of certificates issued by a given issuer name, the expected 
number of duplicate serial numbers is about 2**(159-2N).  If you issue 150 
certificates for every living person N will be 40 or so, giving 2**-79 
expected duplicates.  I wouldn't lose much sleep over that, and I doubt 
most CA's do either.
         All these discussions are equally applicable to RIPEMD-160, if 
people prefer that to SHA-1.

                Tom Gindin

From:
Peter Gutmann <[email-masked]>
To:
[email-masked], [email-masked], [email-masked], 
[email-masked]
Cc:
[email-masked]
Date:
03/03/2011 11:08 PM
Subject:
Re: [pkix] RFC 5280 and the maximum permitted value for certificate serial 
number
Sent by:
[email-masked]

Peter.