On 13/03/2019 03:18, Matthew Hardeman wrote: > Overall I think it's a neat scheme. > > It does impose some trade-offs beyond the mechanism that I proposed: > > 1. It leaves the implementing CA with no space within the serial number > field to include a CA significant sequence number, timestamp, or other > value. That may not be a bad thing, but it's other than capabilities > that they have today.
To comply with today's BRs, SNOT requires that R MUST be 64-bits of (fresh and unfiltered!) output from a CSPRNG. However, if using SNOT in any environment where today's BRs don't apply, the purpose of R is simply to act as a disambiguator; so it could be any string of 64-bits chosen by the CA (because the TRUNCATE_TO_64BITS(D) part of the algorithm is, I believe, sufficient by itself to thwart chosen-prefix attacks). (For clarity: Whilst I can imagine a possible future in which the BRs are updated to relax the CSPRNG requirement when SNOT is used, I am *not proposing that here* because m.d.s.p is the wrong venue to discuss updating the BRs). > 2. It necessarily requires that the TBS certificate data be available > to the serial number generation routine. This would seem to lock in > some architectural changes as the system element producing the serial > number necessarily has to have all the TBSCertificate data), which may > not necessarily be the case today. Good point. I think this can be addressed by changing steps 7 and 8 to... 7. Perform a binary search for the first occurrence of H || A || R || D in the DER(TBSCertificate) that was produced in step 6, and replace that first occurrence with H || A || R || TRUNCATE_TO_64BITS(D). 8. Sign the (modified by step 7) DER(TBSCertificate). > On Tue, Mar 12, 2019 at 12:10 PM Rob Stradling via dev-security-policy > <[email protected] > <mailto:[email protected]>> wrote: > > 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 > [email protected] > <mailto:[email protected]> > https://lists.mozilla.org/listinfo/dev-security-policy > -- Rob Stradling Senior Research & Development Scientist Email: [email protected] Bradford, UK Office: +441274024707 Sectigo Limited This message and any files associated with it may contain legally privileged, confidential, or proprietary information. If you are not the intended recipient, you are not permitted to use, copy, or forward it, in whole or in part without the express consent of the sender. Please notify the sender by reply email, disregard the foregoing messages, and delete it immediately. _______________________________________________ dev-security-policy mailing list [email protected] https://lists.mozilla.org/listinfo/dev-security-policy
