What's the meaning of "non-sequential"? (AW: EJBCA defaulting to 63 bit serial numbers)

[Buschart, Rufus]

Dear mdsp!

I really like reading this discussion about 64 vs. 63 bits and how to read the BRGs as it shows a lot of passion by all of us in the PKI community. Never the less, in the discussion, I miss one interesting aspect. The BRGs not only speak about 64 bits as output from a CSPRNG but also about serial numbers being "non-sequential". But nowhere the BRGs define the exact meaning of "non-sequential". I always read this as serial numbers being totally random, but I know there is at least one CA out there that constructs its serial numbers like this:

serialNumber = timeInMS() + random(64) + 'constant_suffix'

Serial numbers constructed like this are strict monotonously rising but never the less contain 64 bits of random data. Do we consider those as "non-sequential"? We can't even go by the definition in the dictionary, because according to that (at least the one I consulted), every list of numbers is 'sequential', as one number comes after another.

With best regards,
Rufus Buschart

Siemens AG
Information Technology
Human Resources
PKI / Trustcenter
GS IT HR 7 4
Freyeslebenstr. 1
91058 Erlangen, Germany
Tel.: +49 1522 2894134
mailto:rufus.b...@siemens.com
www.twitter.com/siemens

www.siemens.com/ingenuityforlife

Siemens Aktiengesellschaft: Chairman of the Supervisory Board: Jim Hagemann Snabe; Managing Board: Joe Kaeser, Chairman, President and Chief Executive Officer; Roland Busch, Lisa Davis, Klaus Helmrich, Janina Kugel, Cedrik Neike, Michael Sen, Ralf P. Thomas; Registered offices: Berlin and Munich, Germany; Commercial registries: Berlin Charlottenburg, HRB 12300, Munich, HRB 6684; WEEE-Reg.-No. DE 23691322

> -----Ursprüngliche Nachricht-----
> Von: dev-security-policy <dev-security-...@lists.mozilla.org> Im Auftrag von Daymion Reynolds via dev-security-policy
> Gesendet: Montag, 11. März 2019 18:00
> An: mozilla-dev-s...@lists.mozilla.org
> Betreff: Re: EJBCA defaulting to 63 bit serial numbers
>
> On Monday, March 11, 2019 at 8:57:27 AM UTC-7, Ryan Sleevi wrote:
> > I don’t think there’s anything inherently wrong with an approach that
> > uses a fixed prefix, whether of one bit or more, provided that there
> > is at least
> > 64 bits of entropy included in the serial prior to encoding to DER.
> >
> > This means a scheme with guarantees a positive INTEGER will generate
> > *encoded* serials in the range of one bit to sixty five bits, of the
> > goal is to use the smallest possible amount of entropy.
> >
> > However, as you note, this issue only arises when one uses the
> > absolute minimum. A robust solution is to use 159 bits, the maximum
> > allowed. This helps ensure that, even when encoded, it will not exceed
> > 20 bytes, this avoiding any client interpretation issues regarding
> > whether the 20 bytes mentioned in 5280 are pre-encoding (the intent)
> > or post-encoding (as a few embedded libraries implemented).
> >
> > Note, however, even with 159 bits of entropy, it’s still possible to
> > have a compressed encoding of one byte, due to zero folding. Using a
> > one bit prefix in addition to the sign bit (thus, two fixed bits in
> > the serial) can help ensure that a leading run of zero bits are not folded when encoding.
>
> Glad you agree 64bit serial numbers can have no fixed bits, as a fixed bit in a 64 bit serial number would result in less than 64 bits of
> entropy. If you are going to fix a significant bit it must be beyond the 64th bit. If your 64 bit serial number does not contain 1's in the
> significant byte, as long as you still write 64 full bits of data to the cert with 0's left padded, then the desired entropy is achieved and is
> valid. CAs should keep this in mind while building their revocation lists.
> _______________________________________________
> dev-security-policy mailing list
> dev-secur...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-security-policy

[Ryan Sleevi]

On Mon, Mar 11, 2019 at 1:18 PM Buschart, Rufus via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Dear mdsp!
>
> I really like reading this discussion about 64 vs. 63 bits and how to read
> the BRGs as it shows a lot of passion by all of us in the PKI community.
> Never the less, in the discussion, I miss one interesting aspect. The BRGs
> not only speak about 64 bits as output from a CSPRNG but also about serial
> numbers being "non-sequential". But nowhere the BRGs define the exact
> meaning of "non-sequential". I always read this as serial numbers being
> totally random, but I know there is at least one CA out there that
> constructs its serial numbers like this:
>
> serialNumber = timeInMS() + random(64) + 'constant_suffix'
>
> Serial numbers constructed like this are strict monotonously rising but
> never the less contain 64 bits of random data. Do we consider those as
> "non-sequential"? We can't even go by the definition in the dictionary,
> because according to that (at least the one I consulted), every list of
> numbers is 'sequential', as one number comes after another.
>

Oof,

With the requirement to be a positive integer greater than zero, you can
think of the serial number space as the one of /natural numbers/ (or,
because zero is excluded, /whole numbers/) whose DER encoding is less than
or equal to twenty bytes. The sequential requirement is 'meant' to apply to
serial numbers being constructed in order of that sequence of whole numbers
- that is, 1, 2, 3 is sequential in the set of whole numbers, although 1, 3
would be out of sequence with respect to the set of valid whole number
serials.

If I understand the question correctly, you're describing a situation in
which the serial number construct follows a strict ordering, and thus
itself forms a sequence of whole numbers which maintain sequential order of
the set of all valid whole numbers, but which does not include each whole
number, provided that no two certificates are issued in the same
millisecond. If two certificates are issued in the same millisecond, the
64-bits of entropy create a probability that the certificates will not
appear in sequential (monotonically increasing) order. Is that correct?

Put differently, the question is whether or not the algorithm, as
specified, needs to consider two certificates issued at different times
(and, presuming time is linear and increasing, so too will the serial
numbers), or whether it can/should consider certificates issued at the same
time (and thus be probabilistically out of sequential ordering)

Just making sure I've phrased and framed it correctly.

[Matthew Hardeman]

On Mon, Mar 11, 2019 at 12:18 PM Buschart, Rufus via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

>
> I really like reading this discussion about 64 vs. 63 bits and how to read
> the BRGs as it shows a lot of passion by all of us in the PKI community.
> Never the less, in the discussion, I miss one interesting aspect. The BRGs
> not only speak about 64 bits as output from a CSPRNG but also about serial
> numbers being "non-sequential". But nowhere the BRGs define the exact
> meaning of "non-sequential". I always read this as serial numbers being
> totally random, but I know there is at least one CA out there that
> constructs its serial numbers like this
>

I'm glad someone else asked, as no one has enjoyed the question in the form
that I presented it.

But I suggest that if "non-sequential" is taken to mean a guarantee that no
two serial numbers shall be numerically adjacent integer values, then I
submit that any serial numbers which only contain what was previously
considered to be 64-bits of entropy and no other data save, perhaps a
leading 0x00 byte if necessary to prevent high-order bit being 1, then the
effective entropy must be considered less because two adjacent values are
effectively blocked by any prior chosen value.

But, maybe "non-sequential" doesn't mean that. It's a pity a concept like
that isn't clearly objective.

[Buschart, Rufus]

> Von: Ryan Sleevi <ry...@sleevi.com>
> Betreff: Re: What's the meaning of "non-sequential"? (AW: EJBCA defaulting to 63 bit serial numbers)
>
> On Mon, Mar 11, 2019 at 1:18 PM Buschart, Rufus via dev-security-policy <dev-secur...@lists.mozilla.org
> <mailto:dev-secur...@lists.mozilla.org> > wrote:
>
> > [...] nowhere the BRGs define the exact meaning of "non-sequential".

> > I always read this as serial numbers being totally random, but I know there is at least one CA out there that constructs its serial

> > numbers like this:
> >
> > serialNumber = timeInMS() + random(64) + 'constant_suffix'
> >
> > Serial numbers constructed like this are strict monotonously rising but never the less contain 64 bits of random data. Do we
> > consider those as "non-sequential"? We can't even go by the definition in the dictionary, because according to that (at least the one I
> > consulted), every list of numbers is 'sequential', as one number comes after another.
>
> Oof,
>
> With the requirement to be a positive integer greater than zero, you can think of the serial number space as the one of /natural
> numbers/ (or, because zero is excluded, /whole numbers/) whose DER encoding is less than or equal to twenty bytes. The sequential
> requirement is 'meant' to apply to serial numbers being constructed in order of that sequence of whole numbers - that is, 1, 2, 3 is
> sequential in the set of whole numbers, although 1, 3 would be out of sequence with respect to the set of valid whole number serials.
>
> If I understand the question correctly, you're describing a situation in which the serial number construct follows a strict ordering, and
> thus itself forms a sequence of whole numbers which maintain sequential order of the set of all valid whole numbers, but which does
> not include each whole number, provided that no two certificates are issued in the same millisecond. If two certificates are issued in
> the same millisecond, the 64-bits of entropy create a probability that the certificates will not appear in sequential (monotonically
> increasing) order. Is that correct?

Yes, exactly

> Put differently, the question is whether or not the algorithm, as specified, needs to consider two certificates issued at different times
> (and, presuming time is linear and increasing, so too will the serial numbers), or whether it can/should consider certificates issued at
> the same time (and thus be probabilistically out of sequential ordering)
>
> Just making sure I've phrased and framed it correctly.

You got it totally right. Now basically we have two possible definitions of "sequential serial numbers":

1) A CA generates "sequential serial numbers" if every generated serial number meets the following criteria: serialNumber(n) = serialNumber(n-1)+1, with n being the n-th number of generated serial numbers
2) A CA generates "sequential serial numbers" if every generated serial number meets the following criteria: serialNumber(n) > serialNumber(n-m) (or serialNumber(n) < serialNumber(n-m) ), with n being the n-th number of generated serial numbers and m any whole number smaller n

Since choice 1 is a logical consequence of "containing 64 bits of random data", I was always under the impression, that choice 2 was meant by the BRGs. If choice 1 is meant, then I think the requirement of being 'non-sequential' is just some lyrical sugar in the BRGs. Maybe there is a third definition of "sequential" that I haven't thought of?

To put in a concrete example: There is a CA that generated the following serial numbers:

1843319960437720643048278653969636 on 2019-01-11 09:53:47 UTC
1843319960437694134774632325152679 on 2019-01-10 13:49:21 UTC
1843319960437689654817618007073336 on 2019-01-10 09:05:57 UTC
1843319960437665986305459379269472 on 2019-01-09 09:24:59 UTC
1843319960437653534927818400454844 on 2019-01-08 10:24:51 UTC
1843319960437625653787354520462187 on 2019-01-08 08:40:14 UTC
1843319960437610711593417697551974 on 2019-01-08 08:39:37 UTC

Are those serial numbers sequential? I think, yes, they are, but I admit, there are good arguments to say, no, they are not.

[Ryan Sleevi]

On Mon, Mar 11, 2019 at 5:35 PM Buschart, Rufus via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Since choice 1 is a logical consequence of "containing 64 bits of random
> data", I was always under the impression, that choice 2 was meant by the
> BRGs. If choice 1 is meant, then I think the requirement of being
> 'non-sequential' is just some lyrical sugar in the BRGs. Maybe there is a
> third definition of "sequential" that I haven't thought of?
>

I had definitely seen it as lyrical sugar, trying to *really* hammer the
point of concern (of predictable serials). This is an example where
providing guidance in-doc can lead to more confusion, rather than less.

For example, a "confused" reading of the BR requirement would say "at least
64-bits of entropy" by generating a random number once [1] and including it
in all subsequent serials, monotonically increasing +1 each time :)

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

[Peter Gutmann]

Matthew Hardeman via dev-security-policy <dev-secur...@lists.mozilla.org> writes:

>But, maybe "non-sequential" doesn't mean that. It's a pity a concept like
>that isn't clearly objective.

I assume what the text was meaning to say was "unpredictable", but it was
unfortunately phrased badly, presumably as a rushed response to "MD5
considered harmful today" which took advantage of the fact that RapidSSL used
a counter to create its serial numbers.

Given that we've now got several more interpretations of what 7.1 is
requiring, and it's only Monday (at least for you lot), I think this really,
really needs an update to clarify what's actually required. The 7.1 text is
clearly inadequate to convey precisely what should be going into the serial
number field, given the number of interpretations and the amount of debate
about what is and isn't allowed. The "modest proposal" sounds like a good
fit for the updated text.

Peter.

[Hector Martin 'marcan']

Sony tried this (minus the increment) when generating random nonces for
ECDSA signing, apparently generating the nonce once during key
generation, and reusing it for all subsequent signing operations [1].
That worked wonders for them *cough* :)

I think when it comes to specifications with cryptographic relevance (as
unpredictable serials are), less is more; the more inflexible and
unambiguous the spec is, the less likely it will be "creatively
interpreted" in a manner that bypasses the whole point. To someone with
crypto experience and an understanding of the intent, the current
language clearly means "take 64 bits from a CSPRNG once, put whatever
you want around them (or nothing), DER encode, and stuff it into the
serial field". But clearly some implementers interpreted this
differently, and here we are.

That said, I do think the current exercise is, shall we say, bringing
out some interesting opinions on what an appropriate response to the
problem is. Statements such as:

> There are no, and has never been any, 63 bit serial numbers created by EJBCA.

... lead me to significantly reduce my trust in those making them, and
their ability to correctly interpret security-critical standards in the
future. Not everyone gets things right the first time, but owning up to
problems, understanding the technical issue at hand, and accepting
responsibility is a basic tenet of earning community trust.

[1] https://mrcn.st/t/1780_27c3_console_hacking_2010.pdf pp. 122-129

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

[Mike Kushner]

> I think when it comes to specifications with cryptographic relevance (as
> unpredictable serials are), less is more; the more inflexible and
> unambiguous the spec is, the less likely it will be "creatively
> interpreted" in a manner that bypasses the whole point. To someone with
> crypto experience and an understanding of the intent, the current
> language clearly means "take 64 bits from a CSPRNG once, put whatever
> you want around them (or nothing), DER encode, and stuff it into the
> serial field". But clearly some implementers interpreted this
> differently, and here we are.
>
> That said, I do think the current exercise is, shall we say, bringing
> out some interesting opinions on what an appropriate response to the
> problem is. Statements such as:
>
> > There are no, and has never been any, 63 bit serial numbers created by EJBCA.
>
> ... lead me to significantly reduce my trust in those making them, and
> their ability to correctly interpret security-critical standards in the
> future. Not everyone gets things right the first time, but owning up to
> problems, understanding the technical issue at hand, and accepting
> responsibility is a basic tenet of earning community trust.

I'm sorry you feel that way, but here's the thing. EJBCA produces whatever length serial numbers you request from it, restricted to an even octet and within the span of 4 to 20. EJBCA set to produce 8 octet serial numbers will produce exactly 64 bit serial numbers, including the MSB. Are you suggesting that a logical behavior for a 8 octet serial number would be to produce a 9 octet serial number and pad the first 7 bits?
EJBCA will produce exactly the serial number you've specified, and give you as much entropy as your serial length allows.

EJBCA is a general CA implementation with multiple use cases, so it's not built to specifically conform to cabf requirements. As Ryan Sleevi pointed out - It is up to the end customer to understand their own requirements, and to understand that a 64 bit signed integer can in no way or fashion contain 64 bits of entropy.

Unless you're going under the presumption that the MSB doesn't count as a part of the serial number (and I've never seen an RFC or requirement pointing to that being the case, EJBCA does not produce 63 bit serial numbers.

Cheers,
Mike

[Ryan Sleevi]

On Tue, Mar 12, 2019 at 12:07 PM Mike Kushner via dev-security-policy <
dev-secur...@lists.mozilla.org> wrote:

> Unless you're going under the presumption that the MSB doesn't count as a
> part of the serial number (and I've never seen an RFC or requirement
> pointing to that being the case, EJBCA does not produce 63 bit serial
> numbers.
>

As this has come up in discussion in the past [1], particularly as called
out by Peter Bowen [2], there's been some ambiguity as to whether limits on
the maximum size of serial numbers apply to the encoded form or the
unencoded form. This came up as well during the Ballot 164 discussion [3].

I highlight this, because I think your response is absolutely consistent
with the past discussion - namely, that treating the sign-bit as part of
the serial number is consistent. By treating the sign-bit as part of the
length, even though it is conceptually an encoding issue of DER/BER, as
opposed to fundamental to the ASN.1 version, this naturally leads to a
conclusion that there are 159 bits available for the CA to control, since
the most significant bit, the sign bit, MUST be 0.

The confusion, however, that I think is being highlighted here, is whether
the setting is perceived as a configuration of the 'output' serial number
(in which case, you're guaranteeing 8 octets) or the 'CA-controlled' serial
number (in which case, only 63 bits are being contributed by the CA). The
interpretation that EJBCA is applying - in which the configuration
specifies the hard upper bound of the encoded serial - is a very reasonable
configuration, given the implications to the 20 octet maximum captured in
RFC 5280, thus avoiding the issues in [1], although introducing the issues
in [3].

[1]
https://groups.google.com/d/msg/mozilla.dev.security.policy/b33_4CyJbWI/74sItqcvBgAJ

[2]
https://groups.google.com/d/msg/mozilla.dev.security.policy/b33_4CyJbWI/96ENFxrGBgAJ
[3] https://cabforum.org/pipermail/public/2016-April/007245.html

[Hector Martin 'marcan']

On 12/03/2019 21.10, Mike Kushner via dev-security-policy wrote:
>>> There are no, and has never been any, 63 bit serial numbers created by EJBCA.
>>
>> ... lead me to significantly reduce my trust in those making them, and
>> their ability to correctly interpret security-critical standards in the
>> future. Not everyone gets things right the first time, but owning up to
>> problems, understanding the technical issue at hand, and accepting
>> responsibility is a basic tenet of earning community trust.
>

> I'm sorry you feel that way, but here's the thing. EJBCA produces whatever length serial numbers you request from it, restricted to an even octet and within the span of 4 to 20. EJBCA set to produce 8 octet serial numbers will produce exactly 64 bit serial numbers, including the MSB. Are you suggesting that a logical behavior for a 8 octet serial number would be to produce a 9 octet serial number and pad the first 7 bits?
> EJBCA will produce exactly the serial number you've specified, and give you as much entropy as your serial length allows.

It's clear that multiple CAs made a configuration mistake here, and in
general when multiple users make the same mistake when configuring
software, that points to a usability problem in the software. Your
statement is just shoving the entirety of the issue on CAs, while
picking the interpretation most favorable to EJBCA. While the ultimate
responsibility certainly lies with the CAs, it is not helpful for EJBCA
to be so dismissive of the subject.

We can make several accurate statements about EJBCA configured to an
8-octet serial number size (the default):

- It generates serial numbers with 63 bits of entropy (or negligibly
less, if we consider the duplicate-removal code)
- It generates serial numbers from 1 to 2**63 - 1
- It generates serial numbers with 63 bits of effective output from a
CSPRNG (the MSB having been coerced to zero, and thus effectively
eliminated; that this is done by "trying until you get lucky" is an
irrelevant implementation detail and has no bearing on the result)
- It generates 8-byte serial numbers in encoded DER form (which is 64
bits worth of DER).

In other words, only after DER encoding does the serial number become 64
bits in length. The statement "There are no, and has never been any, 63
bit serial numbers created by EJBCA." presumes that bit length is being
measured at one specific point consistent with what EJBCA is actually
doing, which may not be what users expect.

I would in fact expect that if software is taking N bits of output from
a CSPRNG (with the goal of providing N bits of entropy), that it would
then encode it as a positive integer in DER, which indeed requires
adding an extra zero octet to contain the sign bit when the MSB of the
original value is 1. In fact, I would dare say that the output size is
less likely to be relevant to users than the amount of entropy contained
within, and that if a fixed output size is desired, a solution much less
likely to result in people shooting themselves in the foot is to prepend
a fixed constant byte 0x01<=0x7f to the serial before encoding.

The EJBCA configuration file defaults state, verbatim:
> # The length in octets of certificate serial numbers generated. 8 octets is a 64 bit serial number.
> # It is really recommended to use at least 64 bits, so please leave as default unless you are really sure,
> # and have a really good reason to change it.
> # Possible values: between 4 and 20
> # Default: 8
> #ca.serialnumberoctetsize=8

Considering:

1) The BRs require 64 bits of output from a CSPRNG (which can only be
reasonably interpreted by anyone familiar with the subject as as 64 bits
of entropy; anything else is just 'creative interpretation')
2) The configuration file *explicitly* discourages changes.
3) All references are to "64 bits", with no mention that this refers to
the *encoded* serial number and, thus, one of those bits is always zero

Then it's not surprising that multiple CAs made the same mistake; heck,
I probably would've done the same too, without reviewing the code.

> EJBCA is a general CA implementation with multiple use cases, so it's not built to specifically conform to cabf requirements. As Ryan Sleevi pointed out - It is up to the end customer to understand their own requirements, and to understand that a 64 bit signed integer can in no way or fashion contain 64 bits of entropy.
>

> Unless you're going under the presumption that the MSB doesn't count as a part of the serial number (and I've never seen an RFC or requirement pointing to that being the case, EJBCA does not produce 63 bit serial numbers.

The MSB is part of the serial number *encoding*. It is part of the
serial number field as encoded in a DER certificate. It is not part of
the *number* itself, the integer. For example, the MSB has no meaning
when certificate serial numbers are e.g. expressed in integer decimal
notation. A 64-bit positive integer expressed in decimal is a number
from 0 to 18446744073709551615, a range of which only half is covered by
the serial numbers generated by EJBCA in this configuration.

I am not claiming that EJBCA made a catastrophic mistake here. This is
merely a consequence of the fact that serial numbers, as an abstract
numerical entity, and serial numbers, as an encoded DER field, are not
the same thing and do not have the same length. It was unclear which
interpretation was used where.

What I'm saying is that merely sticking to the most convenient
interpretation for you and deflecting all responsibility for how we
ended up here is not productive, and does not scream trustworthiness.
The various actors in the WebPKI need to strive for a secure
environment, not act adversarially. This includes both acting in good
faith (e.g. not attempting to pursue "creative interpretations"), but
also, equally, recognizing when actions and decisions may have
unexpectedly and unintentionally contributed to a problem, and making
changes to eliminate that possibility in the future.

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

[Ryan Sleevi]

On Tue, Mar 12, 2019 at 2:49 PM Hector Martin 'marcan' via
dev-security-policy <dev-secur...@lists.mozilla.org> wrote:

> What I'm saying is that merely sticking to the most convenient
> interpretation for you and deflecting all responsibility for how we
> ended up here is not productive, and does not scream trustworthiness.
> The various actors in the WebPKI need to strive for a secure
> environment, not act adversarially. This includes both acting in good
> faith (e.g. not attempting to pursue "creative interpretations"), but
> also, equally, recognizing when actions and decisions may have
> unexpectedly and unintentionally contributed to a problem, and making
> changes to eliminate that possibility in the future.
>

Hey Hector,

I tried to capture in [1] that the interpretation being offered here is
consistent with past discussions. While I understand you may disagree with
the documentation, I also tried to capture in [1] how it avoids a different
problem which has been discussed in this Forum.

As it relates to the remarks about assigning blame or pushing to their
customers, I think a more charitable read of those remarks is, again,
consistent with long-standing expectations of the policy and past
discussions in the Forum, the CA is ultimately responsible for compliance.
We have CAs using vendors that are far less responsive or engaged in this
Forum, and which software produces things far less compliant, and I want to
make sure we don't discourage participation by not assuming good faith or
good intent. I totally understand that your personal opinions will
naturally (and should naturally!) impact the choice of CA software you run,
so I don't want you to think I'm shilling for a particular vendor, but I
also want to make sure we're assigning responsibility appropriately.

I definitely think it behoves all participants - CAs, software vendors,
random users - to strive to avoid "creative interpretations", for the
reasons you mention. I think the extent of such creative explorations
should be in the pursuit of providing stronger guidance - whether as a
matter of policy or to be enshrined in the requirements - rather than
excuse or dismiss problems. However, I don't think the current discussion
is about dismissing the problems - but about ensuring meaningful technical
accuracy so that there's a clear understanding of the issue.

[1]
https://groups.google.com/d/msg/mozilla.dev.security.policy/13lXh5gomB8/Ie7AnHC9BwAJ