Or just generate longer serials with random. Which is much simpler.
On Fri, Dec 29, 2017 at 11:57 AM, Jakob Bohm via dev-security-policy < dev-security-policy@lists.mozilla.org> wrote: > On 29/12/2017 13:55, Nick Lamb wrote: > >> On Fri, 29 Dec 2017 07:24:31 +0100 >> Jakob Bohm via dev-security-policy >> <dev-security-policy@lists.mozilla.org> wrote: >> >> 3. Or would the elimination in #2 reduce the entropy of such serial >>> numbers to slightly less than 64 bits (since there are less than >>> 2**64 allowed values for all but the first such certificate)? >>> >> >> The tremendous size of the numbers involved means that in practice this >> makes no difference. A single collision only becomes likely (not >> certain, merely likely) over the course of issuing billions of such >> certificates. >> >> If I'm right a decision to append a further byte (say 0x42) to the >> serial number any time a collision would otherwise occur would have >> the same _visible_ effect as just throwing away the colliding number and >> choosing another, ie no effect because collisions don't actually >> happen in practice. >> >> [ In my day job I maintain a system which uses a 64-bit hash of URLs to >> index them. We are conscious that by the pigeon hole principle this hash >> could sometimes confuse two URLs and there's a safeguard to detect that. >> Despite processing millions of URLs this way every day, for several >> years, the safeguard has never triggered outside of unit tests. Perhaps >> one day it will. ] >> >> It wouldn't surprise me if some CAs actually don't check #2 at all. >> Since collisions are so unlikely with truly random serial numbers it >> might well never come up, even if you explicitly looked for it, so that >> this "failure" might have no detectable consequence for a smaller CA >> even over the course of decades of operation. >> >> So far as we know ISRG / Let's Encrypt are issuing the largest volume >> from a single subCA of any CA, but I believe they just use a lot more >> than 64-bits, which is a rational choice here to avoid answering tricky >> philosophical questions about integers. I would commend this approach >> to other CAs wondering how best to comply. >> >> Final thought: The linter should check for at least 64-bits, but it >> can't check for true randomness (doing so may be literally impossible in >> fact) so anything further should be left for human observers and/or CA >> auditors. >> >> Nick. >> >> > However, the "random-with length-extension on collision" algorithm has > some other (non-BR) shortcomings: > > - It is sailing very close to the edge of compliance for little or no > good reason. > > - If the collision case is ever triggered, chances are high that other > parts of the CA system have not been tested with different length > serial numbers from the same issuing CA, thus causing larger failures, > such as OCSP responders returning incorrect results for the colliding > certificates. > > Another algorithm that would produce occasional <= 64 bit serial numbers > while remaining compliant is: > > - Generate 64 random bits. > - Append a 15 bit counter resulting in a 15 to 79 bit serial number (up > to 10 bytes). > - Rotate issuing CAs before the counter wraps. > > Here a small fraction (1 in 65536 certificates thus about one per two > issuing CAs if all 32768 counter values are used) will randomly be 64 > bits or shorter due to the first 16 random bits being zero. > > So > > - 63-bit serial numbers are highly suspicious (the algorithm you > provided would produce them for half the certificates, other algorithms > much less frequently, if at all). > > - 64-bit serial numbers would be cause for concern, but would require > more thorough analysis, perhaps even a code audit. > > - >= 65-bit serial numbers are a lot less likely to be violating the > entropy requirement BR. > > So perhaps: > > - Generate an informational warning for 64-bit serial numbers. > > - Generate a stronger warning for 33 to 63-bit serial numbers. > > - In a separate tool check if an issuing CA produces shorter-than-64-bit > serial numbers more frequently than a random distribution (with some > margin). > > - One simple test could be to dump the serial numbers from an issuing CA > (without DER formatting, leading zeroes etc.) as bare unsigned numbers > with no fomatting, pipe this into gzip -9 or zlib and check if the > resulting output is less than 8 bytes per certificate. > > - A more sophisticated whole-CA test could first sort the serials > numerically, then do pairwise subtracts of all but the first before > converting to bare (signed) binary numbers and compressing. This would > reduce false entropy from pure counter bits. > > > > > > Enjoy > > Jakob > -- > Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com > Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10 > This public discussion message is non-binding and may contain errors. > WiseMo - Remote Service Management for PCs, Phones and Embedded > _______________________________________________ > dev-security-policy mailing list > dev-security-policy@lists.mozilla.org > https://lists.mozilla.org/listinfo/dev-security-policy > _______________________________________________ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
