Just to be clear - "mississued" in this case doesn't mean they were issued to someone who doesn't control the domain. The issue is they were issued using a 63-bit serial number instead of the minimum 64 bits. (The software these CAs were all using was generating 64 random bits, but setting the first bit to zero to produce a positive integer.)
The reason CAs are required to use 64-bit serial numbers is to make the content of a certificate hard to guess, which provides better protection against hash collisions. IIRC this policy was introduced when certs were still signed using MD5 hashes. (That or shortly after it was retired.) Since all publicly-trusted certs use SHA256 today, the actual security impact of this incident is practically nil.
Is there a reason why certificates are being issued using the bare minimum required number of bits, instead of something higher like 128 or 256? Why even risk being at the very edge?
This seems highly unlikely to be authoritative -- AIUI serial number unpredictability is critical to SSL certificate security, as without it, it becomes possible to induce a CA into producing a signature that matches a certificate for another domain. Unless something else changed about the format when the hash algorithm was changed, AFAIK this property is independent to the hash algorithm in use
If memory serves it isn't a theoretical attack either, I read about it used against (Startcom maybe?) not so many years ago
It's "Rage Culture" or maybe just front-page seeking by the author. The problem with that is that it makes people desensitized because if everyone is screaming all the time, one should just shut their ears. We have real issues to discuss and this isn't one of them by a long shot.
Reducing the search space from 64bits to 63bits is of no consequence because if an attack on 63bits was feasible, it would mean the same attack would work 50% of the time on 64bit (or take twice as long for 100%). That wouldn't be acceptable at all.
Sure, 64>63, but at the very least it's not "A world of hurt"
The "world of hurt" comes from the fact that the CAs are revoking every single one of these non-compliant certs, as they're required to by the BRs.
Even though the actual security impact is nil, the current policies in place don't allow any flexibility in how non-compliant certs are treated. Therefore, millions of customers now need to replace their certificates due to a mere technicality.
It isn't a problem in itself. It doesn't make the certificate any less secure in practice, even if we still used md5 as a hash.
The problem however as pointed out down-page [0] [1]
> If you can't obey this silly requirement to use extra bits how can we trust you to do all the other things that we need done correctly? Or internally, if you can't make sure you obey this silly rule, how are you making sure you obey these important rules?
> The reason for the urgent fixes is to promote uniformly applied rules. There are certain predefined rules that CAs need to follow, regardless of whether the individual rules help security or not. The rules say the certs that are badly formed need to be reissued in 5 days.
> If these rules are not followed and no penalties are applied, then later on when other CAs make more serious mistakes they'll point to this and say "Apple and Google got to disobey the rules, so we should as well, otherwise it's favoritism to Apple and Google."
The world of hurt is not that the certificates are insecure - the world of hurt is that by the letter of the rules, which people seem intent on sticking to, millions of certs need to be revoked and replaced for (as you point out) no good reason.
And people are sticking to the letter of the rules entirely independent of the article's author. The author is not advocating for anything to be done, just reporting that this process is already in motion.
Of course we have real issues to discuss. But the fact that all these certs are going to get revoked and require replacing is a real issue that impacts people, even if there's no technical reason for it.
They even include the phrase "Practically speaking, there’s almost no chance of the certificates being maliciously exploited.", but continue to talk about the mistake as catastrophic. Very irresponsible.
There appears to be some subtext involving a UAE state-backed CA called Dark Matter which is the real reason this is being treated so severely: https://news.ycombinator.com/item?id=19376528
Reducing the search space from 63bits to 62bits is of no consequence because if an attack on 62bits was feasible, it would mean the same attack would work 50% of the time on 63bit (or take twice as long for 100%). That wouldn't be acceptable at all.
> Adam Caudill, the security researcher who blogged about the mass misissuance last weekend, pointed out that it’s easy to think that a difference of 1 single bit would be largely inconsequential when considering numbers this big. In fact, he said, the difference between 2^63 and 2^64 is more than 9 quintillion.
Okay, but, that's because 2^63 itself is more than 9 quintillion. Where the search space was previously 18 quintillion, it's now 9 quintillion. Both of those are "big". The attack is 50% easier than "theoretically impossible before certificate expiration," which should still mean that it's impossible.
Or, if the safety margin here is really only one bit, we should probably increase the minimum. If 63 is unsafe today, 64 will be unsafe tomorrow.
If you discovered your AES key generator only created 127 bit keys, would you correct the mistake moving forward? Or go back and immediately burn everything with the old key? The difference between 2^127 and 2^128 is much, much more than 9 quintillion.
It seems unlikely that there was process that determined that 2^63 was an insufficient number of outputs, but 2^64 was just right. The choice was somewhat arbitrary in the first place.
What an incredible non-story burying an actual real and terrifying story.
The crux of this entire issue is a company known as Dark Matter, which is essentially a UAE state sponsored company, potentially getting a root CA trusted by Mozilla.
It's highly suspected that Dark Matter is working on behalf of the UAE to get a root trusted certificate in order to spy on encrypted traffic at their will. Everyone involved in this decision is at least suspect of this if not actively seeking a way to thwart Dark Matter.
Mozilla threw the book at them by giving them this technical hurdle about their 63-bit generated serial numbers - which turned out to be something that a lot of other (far more reputable) vendors also happened to have this issue.
Should it get fixed? Ya, absolutely.
Is it nearly as big of a deal as giving a company like Dark Matter, who works on behalf of the UAE, the ability to decrypt HTTPS communication? Not even close - this is far more scarier, and much more of a security threat to you and me. It's pretty disappointing that this is the story that arstechnica runs with instead of the far more critical one.
The measure of what makes a trustworthy CA are things like organizational competency and technical procedures. These are things that state level actors easily succeed in. There is no real measure in place for motives and morals for state level actors. That should be the terrifying part of this story - anyone arguing about the entropy of 63 or 64 bit is simply missing the forest for the trees in this argument.
> It's highly suspected that Dark Matter is working on behalf of the UAE to get a root trusted certificate in order to spy on encrypted traffic at their will.
This is false. DarkMatter already operates an intermediate CA, so _if_ this were something they were actually planning to do they wouldn't need a trusted root CA to do it. So far, there's been no evidence presented that DarkMatter has abused their intermediate cert in the past, or that they plan to abuse any root cert they might be granted in the future.
Presumably 64 bits were originally chosen because it still permitted simple or naive ASN.1 decoders to return the parsed value as a native 64-bit type. But ASN.1 INTEGERs are always signed, so theses serials would now have to be 65 bits. But any ASN.1 decoder interface that permitted directly storing a 65-bit value into a 64-bit type--even an unsigned type--is dangerous if not broken. I'm guessing that most X.509 management software (much like my own) simply maintains the parsed serial as a bignum object.
Serials were originally intended for... well, for multiple purposes. But if they only function today as a random nonce, and if they're already 65 bits, then they may as well be 128 bits or larger.
A randomly generated 64-bit nonce has a 50% chance of repeating after 2^32 iterations. That can be acceptable, especially if you can rely on other certificate data (e.g. issued and expire timestamps) changing. But such expectations have a poor track record which you don't want to rely on unless your back is against the wall (e.g. as in AES GCM). Because certificates are already so large, absent some dubious backwards compatibility arguments I'm surprised they just didn't require 128-bit serials.
Seems like a lot of hand wringing over nothing, security is done with huge factors of safety (moving to 256 bit keys when no one had ever broken a 128 or even 96 bit key). It's hard to imagine that 1,2, or even a quarter of the bits couldn't be zero-ed.
> it’s easy to think that a difference of 1 single bit would be largely inconsequential when considering numbers this big. In fact, he said, the difference between 263 and 264 is more than 9 quintillion.
In fact, without a practical attack against SHA256, all of the serial number bits could be zeroed. This is undesirable for other reasons, but the serial number isn't part of the cryptographic security of the certificate except as far as it can be used to prevent the person requesting the certificate from anticipating or controlling what the entire signed data will be.
The reason for the urgent fixes is to promote uniformly applied rules. There are certain predefined rules that CAs need to follow, regardless of whether the individual rules help security or not. The rules say the certs that are badly formed need to be reissued in 5 days.
If these rules are not followed and no penalties are applied, then later on when other CAs make more serious mistakes they'll point to this and say "Apple and Google got to disobey the rules, so we should as well, otherwise it's favoritism to Apple and Google."
This is the CAB Forum rationale for serial number entropy[1]:
> As demonstrated in https://events.ccc.de/congress/2008/Fahrplan/attachments/125..., hash collisions can allow an attacker to forge a signature on the certificate of their choosing. The birthday paradox means that, in the absence of random bits, the security level of a hash function is half what it should be. Adding random bits to issued certificates mitigates collision attacks and means that an attacker must be capable of a much harder preimage attack. For a long time the Baseline Requirements have encouraged adding random bits to the serial number of a certificate, and it is now common practice. This ballot makes that best practice required, which will make the Web PKI much more robust against all future weaknesses in hash functions. Additionally, it replaces “entropy” with “CSPRNG” to make the requirement clearer and easier to audit, and clarifies that the serial number must be positive.
Theoretical possibilities and minimal security impacts aside, I'm not seeing comments along the lines of the brown M&M clause [0]. Yeah, brown M&M's weren't going to ruin the day of David Lee Roth, but that wasn't the point: when dealing with heavy and high-amperage equipment of a stage show, what else did you forget or ignore?
64 bits, 63 bits, what's the difference? The difference is that we now have to go through everything you might have forgotten that will make a difference. In other words, we apparently can't trust you to follow instructions, and certificates are all about trust.
Ok, I’m all for strong security and better SSL infrastructure, but the response to this issue was just totally overboard. The issue - one fixed bit in a 64-bit randomized serial field - does not compromise the security of these certs in any meaningful way, especially not before their natural expiry dates anyway.
The disruption caused by reissuing everything surely exceeded the disruption of this theoretical issue. I guess, on the plus side, we get to find out whether the PKI infrastructure is ready for a mass revocation/replacement event...
It's not about whether it compromised security; it's that they didn't adhere to standards. If you're a certificate authority, you need to conform to standards. If you're not, you SHOULD get evicted as an authority, like DigiNotar [1] was for example.
Recently they stopped releasing new updates for the community edition (blocker at 6.10, while the 7.0.1 is out) because they are a really greedy company.
Building by yourself is half a nightmare and the installation process as well, relying on ant tasks for it and that fail 5 out of 10 times.
Considering the UI, most of the settings can be really misused and even their evangelist can get fooled by it (especially with their Enterprise Hardware Instance, whose synchronization across the nodes is also faulty)
That seems like the correct state of things. More packages means more possibility of bugs. We want to trust as little code as possible.
Now if only the same policy would be applied to CAs (possibly a few to mitigate abuse of power concerns, but far less than are in my trust store today).
EJBCA is popular but it's hardly a monoculture, especially among the larger CAs that can afford to do their own thing. Let's Encrypt doesn't use it, and I'm pretty sure a significant number of the other bigger CAs don't.
Typically with crypto you want to stick with one major industry standard implementation that is strenuously verified. It's probably more concerning if everyone's using their own.
For background, earlier this month, DarkMatter applied for Mozilla root CA inclusion. There was an email thread [1], with concerns about DarkMatter, and one of the emails[2] was concerned that DarkMatter was generating serial numbers in this exact same fashion using EJBCA. There was a pretty long-winded discussion in the thread about whether flipping the MSB constituted a loss of 1-bit of entropy and an EJBCA dev chimed in[3] saying basically that they are pushing a fix to solve this. This seems to have kicked off this issue. (there's a lot more to it, with DarkMatter's CTO saying that the method did not constitute a loss of a bit, etc, but this thread seems to be where the issue was discovered at least.)
High-entropy certificate serial numbers are a defense against hash collision attacks. The margin of security is reduced to the point that a brute force attack is twice as easy. If it was going to take you 10,000 years to brute-force it, now it takes you 5,000, both of which round to "impossible." If it was going to take you four weeks on EC2, now it takes two weeks, both of which round to "entirely too easy."
In an X.509 certificate, the serial number is encoded as the ASN.1 integer type, which is arbitrary length. So that can't map to a native integer type on any platform.
I'd chalk this up to the author of the relevant module not really grokking the two's complement behavior in java.math.BigInteger.
The interesting aspect that a lot of people are overlooking is that, for a theoretical attack within certain timeframes, this difference can be make-it or break it!
Imagine a collision attack that takes about a 1 year with 64bit serial numbers, so with 63bit serial number it should take about half, at 6 months.
The average certificate is issued for about 1 year, so being able to mount a collision attack that took 1 year in 6 months can make the difference from generally-not-useful to very practical and dangerous.
Why do you assume that an attack would take 1 year, and not (e.g.) a billion years? A factor of two is only interesting if the number you're dividing was interesting in the first place.
profmonocle|7 years ago
The reason CAs are required to use 64-bit serial numbers is to make the content of a certificate hard to guess, which provides better protection against hash collisions. IIRC this policy was introduced when certs were still signed using MD5 hashes. (That or shortly after it was retired.) Since all publicly-trusted certs use SHA256 today, the actual security impact of this incident is practically nil.
ehsankia|7 years ago
unknown|7 years ago
[deleted]
_wmd|7 years ago
If memory serves it isn't a theoretical attack either, I read about it used against (Startcom maybe?) not so many years ago
air7|7 years ago
It's "Rage Culture" or maybe just front-page seeking by the author. The problem with that is that it makes people desensitized because if everyone is screaming all the time, one should just shut their ears. We have real issues to discuss and this isn't one of them by a long shot.
Reducing the search space from 64bits to 63bits is of no consequence because if an attack on 63bits was feasible, it would mean the same attack would work 50% of the time on 64bit (or take twice as long for 100%). That wouldn't be acceptable at all.
Sure, 64>63, but at the very least it's not "A world of hurt"
Ajedi32|7 years ago
Even though the actual security impact is nil, the current policies in place don't allow any flexibility in how non-compliant certs are treated. Therefore, millions of customers now need to replace their certificates due to a mere technicality.
isostatic|7 years ago
The problem however as pointed out down-page [0] [1]
> If you can't obey this silly requirement to use extra bits how can we trust you to do all the other things that we need done correctly? Or internally, if you can't make sure you obey this silly rule, how are you making sure you obey these important rules?
> The reason for the urgent fixes is to promote uniformly applied rules. There are certain predefined rules that CAs need to follow, regardless of whether the individual rules help security or not. The rules say the certs that are badly formed need to be reissued in 5 days. > If these rules are not followed and no penalties are applied, then later on when other CAs make more serious mistakes they'll point to this and say "Apple and Google got to disobey the rules, so we should as well, otherwise it's favoritism to Apple and Google."
[0] https://news.ycombinator.com/item?id=19377292 [1] https://news.ycombinator.com/item?id=19375758
geofft|7 years ago
And people are sticking to the letter of the rules entirely independent of the article's author. The author is not advocating for anything to be done, just reporting that this process is already in motion.
Of course we have real issues to discuss. But the fact that all these certs are going to get revoked and require replacing is a real issue that impacts people, even if there's no technical reason for it.
fredley|7 years ago
shawnz|7 years ago
Xylakant|7 years ago
geofft|7 years ago
Okay, but, that's because 2^63 itself is more than 9 quintillion. Where the search space was previously 18 quintillion, it's now 9 quintillion. Both of those are "big". The attack is 50% easier than "theoretically impossible before certificate expiration," which should still mean that it's impossible.
tedunangst|7 years ago
If you discovered your AES key generator only created 127 bit keys, would you correct the mistake moving forward? Or go back and immediately burn everything with the old key? The difference between 2^127 and 2^128 is much, much more than 9 quintillion.
underwater|7 years ago
beardbandit|7 years ago
Either you crack it or you don't.
talaketu|7 years ago
Golfkid2Gadfly|7 years ago
The crux of this entire issue is a company known as Dark Matter, which is essentially a UAE state sponsored company, potentially getting a root CA trusted by Mozilla.
It's highly suspected that Dark Matter is working on behalf of the UAE to get a root trusted certificate in order to spy on encrypted traffic at their will. Everyone involved in this decision is at least suspect of this if not actively seeking a way to thwart Dark Matter.
Mozilla threw the book at them by giving them this technical hurdle about their 63-bit generated serial numbers - which turned out to be something that a lot of other (far more reputable) vendors also happened to have this issue.
Should it get fixed? Ya, absolutely.
Is it nearly as big of a deal as giving a company like Dark Matter, who works on behalf of the UAE, the ability to decrypt HTTPS communication? Not even close - this is far more scarier, and much more of a security threat to you and me. It's pretty disappointing that this is the story that arstechnica runs with instead of the far more critical one.
The measure of what makes a trustworthy CA are things like organizational competency and technical procedures. These are things that state level actors easily succeed in. There is no real measure in place for motives and morals for state level actors. That should be the terrifying part of this story - anyone arguing about the entropy of 63 or 64 bit is simply missing the forest for the trees in this argument.
Ajedi32|7 years ago
This is false. DarkMatter already operates an intermediate CA, so _if_ this were something they were actually planning to do they wouldn't need a trusted root CA to do it. So far, there's been no evidence presented that DarkMatter has abused their intermediate cert in the past, or that they plan to abuse any root cert they might be granted in the future.
wahern|7 years ago
Serials were originally intended for... well, for multiple purposes. But if they only function today as a random nonce, and if they're already 65 bits, then they may as well be 128 bits or larger.
A randomly generated 64-bit nonce has a 50% chance of repeating after 2^32 iterations. That can be acceptable, especially if you can rely on other certificate data (e.g. issued and expire timestamps) changing. But such expectations have a poor track record which you don't want to rely on unless your back is against the wall (e.g. as in AES GCM). Because certificates are already so large, absent some dubious backwards compatibility arguments I'm surprised they just didn't require 128-bit serials.
paulddraper|7 years ago
SethTro|7 years ago
> it’s easy to think that a difference of 1 single bit would be largely inconsequential when considering numbers this big. In fact, he said, the difference between 263 and 264 is more than 9 quintillion.
schoen|7 years ago
unknown|7 years ago
[deleted]
xyzzy123|7 years ago
Curious why everyone doesn’t agree to use 64 bits in future and just let the mis-issued certs live out their natural life?
Seems to create a lot of busywork for lots of people for no discernible benefit?
Buge|7 years ago
If these rules are not followed and no penalties are applied, then later on when other CAs make more serious mistakes they'll point to this and say "Apple and Google got to disobey the rules, so we should as well, otherwise it's favoritism to Apple and Google."
mmastrac|7 years ago
> 4) This only came up because of DarkMatter, a very shady operator who most people are very happy to have an excuse to screw with technicalities.
Edit maybe these are sources?
https://bugzilla.mozilla.org/show_bug.cgi?id=1531800
https://groups.google.com/forum/#!msg/mozilla.dev.security.p...
Still not getting the whole picture.
helper|7 years ago
> As demonstrated in https://events.ccc.de/congress/2008/Fahrplan/attachments/125..., hash collisions can allow an attacker to forge a signature on the certificate of their choosing. The birthday paradox means that, in the absence of random bits, the security level of a hash function is half what it should be. Adding random bits to issued certificates mitigates collision attacks and means that an attacker must be capable of a much harder preimage attack. For a long time the Baseline Requirements have encouraged adding random bits to the serial number of a certificate, and it is now common practice. This ballot makes that best practice required, which will make the Web PKI much more robust against all future weaknesses in hash functions. Additionally, it replaces “entropy” with “CSPRNG” to make the requirement clearer and easier to audit, and clarifies that the serial number must be positive.
[1]: https://cabforum.org/2016/03/31/ballot-164/
mikestew|7 years ago
64 bits, 63 bits, what's the difference? The difference is that we now have to go through everything you might have forgotten that will make a difference. In other words, we apparently can't trust you to follow instructions, and certificates are all about trust.
[0] https://www.snopes.com/fact-check/brown-out/
nneonneo|7 years ago
The disruption caused by reissuing everything surely exceeded the disruption of this theoretical issue. I guess, on the plus side, we get to find out whether the PKI infrastructure is ready for a mass revocation/replacement event...
Cthulhu_|7 years ago
[1] https://en.wikipedia.org/wiki/DigiNotar
IloveHN84|7 years ago
Recently they stopped releasing new updates for the community edition (blocker at 6.10, while the 7.0.1 is out) because they are a really greedy company.
Building by yourself is half a nightmare and the installation process as well, relying on ant tasks for it and that fail 5 out of 10 times.
Considering the UI, most of the settings can be really misused and even their evangelist can get fooled by it (especially with their Enterprise Hardware Instance, whose synchronization across the nodes is also faulty)
spydum|7 years ago
gpm|7 years ago
Now if only the same policy would be applied to CAs (possibly a few to mitigate abuse of power concerns, but far less than are in my trust store today).
jaas|7 years ago
danite|7 years ago
a-wu|7 years ago
[1] https://groups.google.com/forum/#!topic/mozilla.dev.security...
[2] https://groups.google.com/d/msg/mozilla.dev.security.policy/...
[3] https://groups.google.com/d/msg/mozilla.dev.security.policy/...
ggm|7 years ago
The 'pull the certificates from the browsers' thing demands people from these companies maybe recuse themselves from conversations?
(this is public trust process stuff, not technology per se)
Ajedi32|7 years ago
Many of the affected CAs have already come out and "confessed" that they've issued non-compliant certs and stated that they're revoking them.
No certificates are being "pulled from browsers" as a result of this incident as far as I know.
modeless|7 years ago
jrochkind1|7 years ago
bitxbitxbitcoin|7 years ago
How true is this?
geofft|7 years ago
ikeboy|7 years ago
2^63 and 2^64 are effectively the same cost to break. Instead of costing $2X to break, it now costs $X.
tbodt|7 years ago
bdhess|7 years ago
I'd chalk this up to the author of the relevant module not really grokking the two's complement behavior in java.math.BigInteger.
systemBuilder|7 years ago
[deleted]
bandrami|7 years ago
j16sdiz|7 years ago
omeid2|7 years ago
Imagine a collision attack that takes about a 1 year with 64bit serial numbers, so with 63bit serial number it should take about half, at 6 months.
The average certificate is issued for about 1 year, so being able to mount a collision attack that took 1 year in 6 months can make the difference from generally-not-useful to very practical and dangerous.
underwater|7 years ago
p1mrx|7 years ago