Hi all. I've been working on an alternative proposal for a serial number generation scheme, for which I intend to write an I-D and propose to the LAMPS WG. However, since other folks' proposals are already flowing, I will share the gist of mine here. Comments welcome!
----- Serial Number Origin Transparency (SNOT ;-) ): Generation ----- 1. Let H (meaning "Header"; uint24) be: 0x00DE7E. The 0x00 is the byte that makes the ASN.1 INTEGER a positive value. 0xDE7E signifies "DE7Erministic". 2. Let A (meaning "Algorithm"; uint8) be a hash algorithm ID from the TLS HashAlgorithm registry (https://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-18). 3. Let R (meaning "Random"; uint64) be 64-bits of (fresh and unfiltered!) output from a CSPRNG. 4. Let M (meaning "Magic"; uint64) be the magic constant: 0x0102030405060708 5. Generate the TBSCertificate template with the serial number value set to: H || A || R || M 6. Let D (meaning "Digest") be the thumbprint of the DER-encoded TBSCertificate, calculated using the hash algorithm denoted by A. e.g., D = SHA-256(DER(TBSCertificate)) 7. Change the serial number value in the TBSCertificate template to: H || A || R || TRUNCATE_TO_64BITS(D). 8. Calculate DER(TBSCertificate), then sign it. ---------------------------------------------------------------------- Since this mechanism includes 64-bits of (fresh and unfiltered!) output from a CSPRNG, it is compatible with today's BRs. The randomness also ensures that this mechanism doesn't yield multiple certs with the same serial number (contrary to RFC5280 ยง4.1.2.2) if the CA signs the exact same TBSCertificate multiple times using a nondeterministic signature algorithm. In terms of preventing certificate forgery (see [1]), which is the thing that unpredictable serial numbers are designed to prevent, this mechanism gives CAs two chances to not screw up: 1) if the CA implements this mechanism wrongly but nonetheless does successfully include 64-bits of (fresh and unfiltered!) output from a CSPRNG, then the desired level of security is still achieved. 2) or, if the CA correctly implements the deterministic parts of this mechanism but mishandles the output from their CSPRNG, then the desired level of security is still achieved (although let me stress that this would of course not be compliant with today's BRs). Whilst this mechanism does add complexity for the CA (compared to only using a CSPRNG to generate serial numbers), I think that the additional operations on the TBSCertificate are less complicated than most CAs have already had to deal with to issue CT precertificates and embed SCTs in certificates. *** ADVANTAGES OF THIS MECHANISM *** When implemented correctly by the CA, this mechanism enables the community to programmatically verify(*) that a certificate is not a forgery, without having to... 1. trust the CA (to have handled their CSPRNG correctly), or 2. trust the CA's WebTrust/ETSI auditors (to have correctly verified that the CA has handled their CSPRNG correctly), or 3. trust the CSPRNG algorithm to actually be unpredictable (Dual_EC_DRBG, anyone?) This mechanism builds on PHB's earlier proposal [2]. [1] https://www.win.tue.nl/hashclash/rogue-ca/ [2] https://cabforum.org/pipermail/public/2016-July/008053.html (*) ----- Serial Number Origin Transparency (SNOT): Verification ----- 1. Check that the first 3 bytes of the certificate's serial number value (including the leading sign byte) are 0x00DE7E. 2. Check that the certificate's serial number value is exactly 20 bytes long (including the leading 0x00 sign byte). 3. Let A be the 4th byte of the serial number value (considering the leading 0x00 sign byte to be the 1st byte). Check that A denotes a supported hash algorithm. 4. Let D1 be a copy of the last 8 bytes of the certificate's serial number. 5. Let T be a copy of the DER-encoded TBSCertificate component of the certificate. 6. Change the last 8 bytes of T's serial number to the magic constant: 0x0102030405060708 (To avoid having to DER-decode and re-DER-encode T, this step should be performed using a binary search-and-replace directly on the first occurrence of D1 in T). 7. Let D2 be the thumbprint of T, calculated using the hash algorithm denoted by A. e.g., D2 = SHA-256(T) 8. Check that D1 exactly matches D2. ------------------------------------------------------------------ On 12/03/2019 14:14, Jakob Bohm via dev-security-policy wrote: > On 09/03/2019 03:43, Matthew Hardeman wrote: >> I know this isn't the place to bring a BR ballot, but I'm not presently a >> participant there. >> >> I present alternative language along with notes and rationale which, I put >> forth, would have resulted in a far better outcome for the ecosystem than >> the issues which have arisen from the present BR 7.1 subsequent to ballot >> 164. >> >> I humbly propose that this would have been a far better starting point, for >> reasons I discuss in notes below. >> >> Effective as of Month Day, Year, CAs shall generate a certificate serial >> numbers as herein specified: >> >> >> 1. The ASN.1 signed integer encoded form of the certificate serial >> number value must be represented as not less than 9 bytes and not more >> than >> 20 bytes. [Note 1] >> 2. The hexadecimal value of the first byte of the certificate serial >> number shall be 0x75. [Note 2] >> 3. The consecutive 64 bits immediately following the first byte of the >> encoded serial number shall be the first 64 bits of output of an AES-128 >> random session key generation operation, said operation having been >> seeded >> within random data to within its design requirements. [Note 3] >> 4. The remaining bytes of the encoded serial number (the 10th through >> 20th bytes of the encoded serial number), to the extent any are desired, >> may be populated with any values. [Note 4] >> >> Notes / Rationale: >> >> Note 1. The first bullet point sets out a structure which necessarily >> requires that the encoded form of the serial number for all cases be at >> least 9 bytes in length. As many CAs would have been able to immediately >> see that their values, while random, don't reach 9 bytes, each CA in that >> case would have had an easy hint that further work to assess compliance >> with this BR change would be necessary and would definitely result in >> changes. I believe that would have triggered the necessary investigations >> and remediations. To the extent that it did not do so, the CAs which >> ignored the change would be quickly identifiable as a certificate with an 8 >> byte serial number encoding would not have been valid after the effective >> date. >> >> Note 2. A fixed value was chosen for the first byte for a couple of >> reasons. First, by virtue of not having a value of 1 in the highest order >> bit, it means that ASN.1 integer encoding issues pertaining to sign are >> mooted. Secondarily, with each certificate issuance subsequent to the >> effective date of the proposal, a CA which has not updated their systems to >> accommodate this ballot but does use random number generation to populate >> the certificate serial has a probability of 127/128 of revealing that they >> have not implemented the changes specified in this ballot. >> >> Note 3. CAs and their software vendors are quite familiar with >> cryptographic primitives, cryptographic keys, key generation, etc. Rather >> than using ambiguous definitions of randomness or bits of entropy or output >> of a CSPRNG, the administration of a CA and their software vendors should >> be able to be relied upon to understand the demands of symmetric key >> generation in actual practice. By choosing to specify a symmetric block >> cipher type and key size in common use, the odds of an appropriate >> algorithm being selected from among the large body of appropriate >> implementations of such algorithms greatly reduces odds of low quality >> "random" data for the serial number. >> >> Note 4. Note 4 makes clear that plenty of space remains for the CA to >> populate other information, be it further random data or particular data of >> interest to the CA, such as sequence numbers, date/time, etc. >> >> Further notes / rationale: >> >> In supporting systems whose databases may support only a 64 bit serial >> number in database storage, etc, it is noteworthy that the serial number >> rules I specified here only refer to the encoded form which occurs in the >> certificate itself, not any internal representation in an issuance >> database. Because the first byte is hard coded to 0x75 in my proposal, >> this doesn't need to be reflected in a legacy system database, it can just >> be implemented as part of the certificate encoding process. >> >> Strategically, certificates which would conform to the proposal I've laid >> out here would obviously and facially be different from any previously >> deployed system which routinely utilized 8 byte encodings, meaning that >> every CA previously generating 8 byte serials would have an obvious signal >> that they needed to dig into their serial number generation methodologies. >> >> By tying the generation of high quality random data to fill the serial >> number to algorithms and procedures already well known to CAs and to their >> vendors, auditors, etc, my proposal enhances the odds that the required >> amount of random unpredictable bits actually be backed by a mechanism >> appropriate for the use of cryptography. >> >> If anyone thinks any of this has merit, by all means run with it. I >> disclaim any proprietary interest (copyright, etc) that I might otherwise >> have had by statute and declare that I'm releasing this to the public >> domain. >> > > This overspecifies too far. For example, there is no stated reason to > force the value 117 (0x75). > > Nor is there a stated reason why the "encrypted actual serial" should be > used in place of genuinely reandom entropy. The encryption would only > provide the entropy of its key (256 bits max) spread over all the serial > numbers of a CA, typically resulting in less than 1 bit of entropy per > serial number. > > Here is a better, simpler form: > > > 1. The ASN.1 DER signed integer encoded form of the certificate serial > number value must be represented as not less than n+1 bytes and not > more than 20 bytes. > Note: The first encoded byte shall have a value between 0x01 and > 0x7F to make the serial number a valid DER encoding of a number > 0. > > 2. The serial number shall included a contiguous sequence of at lest > n*8 random bits generated from a fresh invocation of a CSRNG with no > filtering of the resulting bits. These bits shall not be known by > any person or system before all other parts of the TbsCertificate > have been chosen and committed to the signing process. The location > of these n*8 random bits within the serial number shall be specified > in the associated CPS, such that both the CA's auditors and the > community can check that the scheme is being followed. > > 3. The value n shall be at least 8 for any certificates issued with > historic hash algorithms such as SHA-1 (such certificates are not > currently BR compliant anyway, but is relevant for no-longer-trusted > CAs intended to be trusted only be legacy systems.). > > 4. For current hash algorithms, n shall be at least 12 (96 bits of > entropy). A future BR may increase that value. > > 5. As a special exception, systems that require signing certificates > with the same serial-number more than once (such as CT and CA > validity adjustments) are not required to change the serial number > after initial selection). > > 6. As a special exception due to widespread technical failures, > certificates issued on or prior to 2019-03-31 UTC may instead use > serial numbers consisting only of 63 random bits chosen as per #2, > but checked to reject any value that would be encoded to 7 or fewer > bytes or be the same as a previously issued serial number. > > Note 1: The BR requirement that OCSP responders must reject never > issued serial numbers implies that any compliant CA must maintain > a full database of all certificates ever signed. > > Note 2: The following are some (not all possible) compliant schemes (If > any schemes on this list are patented, the patent should be noted > on that example): > > 2A: Generate sequential "internal" serial numbers between 0x01000000 > and 0x7fffffff and append 96 to 128 CSRNG bits. Database lookup > can use the "internal" part, then compare the random bits to the > value or the actually issued serial number (as stored separately > in the database or as part of the full certificate). > > 2B: Generate sequential "internal" serial numbers between 0 and > 0xffffffff. Generate 96 to 120 CSRNG bits. Combine the random > bits and an internal cryptographic key to produce a 32 bit value > xored onto the internal serial number. Final serial number is a > fixed byte between 0x01 and 0x7f (this might indicate which of > multiple signing machines were used), followed by the CSRNG bits > then the encrypted internal serial OR the internal serial followed > by the CSRNG bits. > > 2C: Generate 104 to 152 CSRNG bits. Choose a random prefix byte > between 0x01 and 0x7F, then check if the concatenation collides with > a previously issued serial number. If so, change the random prefix > byte until an unused serial number is found, if all 127 prefix bytes > result in collision choose a new set of CSRNG bits. Provide auditors > and root programs with a statistical proof that these retries will > not drop the total entropy below 96 bits. > > Note 3: An appropriate external auditing scheme is to collect all / most > of the issued serial numbers, extract the bit positions that are random > according the the CPS, then run statistical tests to check if they do > indeed form a plausible output from a CSRNG. > > Note 4: In addition to external statistical tests, the auditor of the > CA shall inspect the actual implementation to ensure it does what the > CA says it does. > > This too is released to the public domain, I hold no patents on these > techniques either. > > > Enjoy > > Jakob > -- Rob Stradling Senior Research & Development Scientist Sectigo Limited _______________________________________________ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
