7 ms·

A world of hurt after GoDaddy, Apple, and Google misissue 1M certificates

267 points by jonburs 8y ago

bitxbitxbitcoin 8y ago
“Almost no chance of exploitation.” How true is this?
- ikeboy 8y ago
  True. 2^63 and 2^64 are effectively the same cost to break. Instead of costing $2X to break, it now costs $X.
  - SethTro 8y ago
    when X > $1M (maybe even large) it really doesn't
    - geofft 8y ago
      They're "the same cost" because anyone with account to $1M or $1B to break a cert generally also has access to $2M or $2B. No reasonable threat model includes defending against attackers that have 50% of the necessary capital to conduct an attack but not more.
      - omeid2 8y ago
        I think this is a general fallacy held by a lot people. The notion that someone who has access to X amount of funds for a given task automatically has 2X and can also afford to spend 2X on the given task is not necessarily true, so such claims are generally baseless. What is most interesting is that these claims are generally about non-exact amounts, so the logic should follow that if you can afford X, then you can afford 2X, also means that you can afford 4X, and 8X, ad infinitum. In practice, a 2X difference in majority of real life cases concerning substantial amount of resources is by definition substantial and far from a trivial.
        geofft 8y ago
        I'm not sure but I think you're trying to say I'm wrong. In the general case it's wrong, of course, to say that being able to afford X implies being able to afford 2X: few people could afford 2x their rent or a house 2x the price of theirs, etc. Few people would fail to be meaningfully affected by getting 2x (or 1/2x) their salary. But I'm talking specifically about cryptographic threat models. No reasonable threat model says, conducting this attack takes $100,000, and since most people don't have $100,000 in savings it's safe, because defending against "most people" isn't meaningful. A reasonable threat model says either, conducting this attack takes $100,000 so we're going to add an additional layer of security because it's a realistic attack, or conducting this attack takes $100,000,000,000,000. In such a threat model, if the numbers change by a factor of two in either direction (either through a one-bit error like this, or through macroeconomic trends, or whatever), it doesn't change the analysis. And in particular the claims here are in fact about exact amounts: a factor of two, or one bit. Cryptographers tend to measure things very precisely in bits. There's usually no good reason for a particular choice (64 is not a magic number here, it's just a convenient number for computers), but the analysis is still done with that particular choice. You can measure the difficulty of attacking a problem with N bits of entropy, and then add a heavy margin on top, and be very clear about what that margin is. Once you've done that, N-1 becomes probably reasonable, and you can argue precisely about why it's reasonable; you can argue equally precisely that N-5 is questionable and N-10 is not reasonable, and that the arguments are not recursive.
        omeid2 8y ago
        > No reasonable threat model says, conducting this attack takes $100,000, and since most people don't have $100,000 in savings it's safe Sure, that is never the claim. > And in particular the claims here are in fact about exact amounts: a factor of two Sure, but that is still a factor of X, an unknown amount. The bottom line is that for many actors, even nation state, the cost difference of 20M and 40M might mean that they have to seek alternative options. Not every actor has access to infinite amount of USD or compute.
        geofft 8y ago
      - tptacek 8y ago
        Objection! There is one such threat model: content protection schemes (like BD+) are that finely-calibrated. The goal is to be secure enough for the new release window, but to accept failure after that point. You're totally right here, I'm just nerding out on threat models and security economics.
  - j16sdiz 8y ago
    This is an anti-collusion measure against birthday attack. The effect is exponential.
    - Ajedi32 8y ago
      2^x is exponential. GP is correct, it's still only one bit, so the cost is halved.
- geofft 8y ago
  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."
  - deleted 8y ago
    [deleted]
xyzzy123 8y ago
Given that there seems to be no security impact (and none expected in the next year or two)... 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?
- mmastrac 8y ago
  No idea and completely unsourced, but one of the site comments states this: > 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://bugzilla.mozilla.org/show_bug.cgi?id=1531800 https://groups.google.com/forum/#!msg/mozilla.dev.security.policy/nlN_QrDwgaw/cg_v-VY0AQAJ https://groups.google.com/forum/#!msg/mozilla.dev.security.p... Still not getting the whole picture.
  - geofft 8y ago
    The basic story as I understand it is that DarkMatter under contract to the United Arab Emirates wants to become a trusted CA, and they are widely expected to start running a governmental MITM once trusted, but the CA root programs don't have any provision for "You're a bunch of sketchy creeps, we don't trust you." (Oddly enough for a "trusted" root program, there is generally no actual evaluation of trust as conventionally defined. The "trust" part is "can you pass audits and generally be technically and organizationally competent to not let your private key be stolen / your infrastructure be abused by an attacker." Individual employees are part of the threat model, so there's usually a two-person rule for access to the private key; entire malicious organizations willing to lie in public and cover their tracks are not envisioned by the model.) So people are trying to block their application by nitpicking technical mistakes that, by the letter of the Baseline Requirements, disqualify you from being a CA. https://www.eff.org/deeplinks/2019/02/cyber-mercenary-groups-shouldnt-be-trusted-your-browser-or-anywhere-else https://www.eff.org/deeplinks/2019/02/cyber-mercenary-groups... covers some background on DarkMatter. One of the Baseline Requirements is you may not issue certs with fewer than 64 bits of entropy. Turns out DarkMatter was doing that, by issuing certs with 63 bits of entropy. Also turns out this was a thing lots of CAs did. Now that it's been pointed out publicly....
SethTro 8y ago
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.
- deleted 8y ago
  [deleted]
- schoen 8y ago
  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.
  - tialaramex 8y ago
    Well not _all_ the bits. We do want the serial numbers to be non-identical because you need a way to talk about specific certificates for validity checking. Once upon a time bug reports would have focused on certificate serial numbers, these days they're more likely to be crt.sh links but arguably we should discourage that because crt.sh could go away some day.
    - schoen 8y ago
      Yep, that's what I mean by "for other reasons". (Without distinctive serial numbers or crt.sh, we would probably have to attach PEM copies of the certificate in every discussion about it.)
geofft 8y ago
> 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.
- talaketu 8y ago
  "50% easier than theoretically impossible" means it's now 50% possible, doesn't it?
  - Dylan16807 8y ago
    No more than "half of infinity" is half finite.
    - TylerE 8y ago
      Infinity and "practically infinity" aren't the same thing though. Half of "practically infinity" may end up being practical.
      - krferriter 8y ago
        Yes the previous value was not infinity. It was impractical to solve in a human lifetime, but if they keep trimming off a few bits it very quickly becomes practical. If actually "infinity" then dividing it by any finite number would still result in infinity, which is not the case here.
        geofft 8y ago
        Right, which is why the specific claim here is that 63 is not a problem, not that smaller numbers in general are not a problem. A better way to put this: instead of saying "it reduces the search space by 9 quintillion," say "it reduces 50% of the search space." Sure, that's a lot, but not nearly as much as trimming 8 bits and saying "it reduces 99.6% of the search space."
spydum 8y ago
Sooooo all the big players depend on one CA PKI package: EJBCA - is that not a major concern ?
- danite 8y ago
  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.
  - spydum 8y ago
    Suppose so but doesn’t it become one well to poison? It just surprises me a bit (mainly because I was NOT familiar with EJBCA and have moderate awareness of PKI)
    - omeid2 8y ago
      I suspect a lot of people expect OpenSSL or LibreSSL to be used in this kind of setups.
- gpm 8y ago
  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).
  - geofft 8y ago
    Counterpoint (which I'm not fully convinced of myself, to be fair): CAs are supposed to be interchangeable and easy to revoke. While the CA ecosystem as a whole must be robust, no individual CA can be too big to fail. If a serious bug is found in software used by one or a few CAs (imagine something like the Debian OpenSSL bug from 11 years ago), revoking them and requiring customers to move to other CAs is feasible. If a serious bug is found in software used by all CAs, you can't revoke all the certs on the web and leave HTTPS useless globally while CAs set up new software. On a tangent: one practice I'd genuinely like to see for security reasons (and which I'm surprised the CAs haven't proposed themselves, since it would make them twice as much money) is that major sites should always hold valid certs from two CAs, so that if a CA gets revoked it's just updating a file or even flipping a feature flag and certainly not signing up with a new CA. It would make sense to have two certs generated by different software, then. (It might also make sense, re abuse of power concerns, to present both certs and have browsers verify that a site has two valid certs from two organizationally-unrelated CAs. That way you can be significantly more confident that the certs aren't fraudulent.)
profmonocle 8y ago
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.
- deleted 8y ago
  [deleted]
- _wmd 8y ago
  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
  - heinrich5991 8y ago
    I believe this is only an issue if you can produce collisions for the underlying hash function. SHA256 is still considered safe against that.
  - geofft 8y ago
    The signature is over all the data in the certificate. So a hash collision in the signature algorithm makes this attack possible. (And if you can predict/control serial numbers, it makes the attack much easier because then you can generate a colliding pair of one valid cert and one invalid one and get the first one signed, instead of having to find a preimage of a valid certificate.) But without a hash collision, it should be theoretically safe to have no entropy at all. Most commonly-digitally-signed objects (Git commits, software packages, etc.) have no added entropy in the object itself / the input to the hash function.
helper 8y ago
This is the CAB Forum rationale for serial number entropy[1]: > As demonstrated in https://events.ccc.de/congress/2008/Fahrplan/attachments/1251_md5-collisions-1.0.pdf 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/ https://cabforum.org/2016/03/31/ballot-164/
ggm 8y ago
CT principles would surely demand they do some public facing declaration? 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 8y ago
  I don't understand what you're asking. 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.
bandrami 8y ago
Again and again, the problem with PKI is not the tech, but the agents. We need an authorityless solution.
- j16sdiz 8y ago
  It works fine until some bug arise and nobody have the authority to fix it....
wahern 8y ago
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.
- paulddraper 8y ago
  Yes, now certificates are about half as hard to hack as they were supposed to be.
  - baking 8y ago
    Does that mean that twice as many will be cracked?/s
    - deleted 8y ago
      [deleted]
  - cheeze 8y ago
    Well, it depends on what you mean by "hack." The attack that we're talking about here isn't breaking a signature, but relies instead on being able to manipulate certificate data to generate a certificate with a known hash. That hash must collide with another certificate hash, which would then let you generate a rogue certificate. A team demonstrated that this attack was possible by being able to issue a rogue cert by being able to predict the not_before and not_after on the certificate that would be issued, predicting the serial of the issued cert, and finding an input for the rest of the cert fields which caused a collision. https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/ So, yes 128 bit serials would be better, but we should be safe even at 63 bits of entropy.
omeid2 8y ago
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.
- p1mrx 8y ago
  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.
  - deleted 8y ago
    [deleted]
  - omeid2 8y ago
    imagine is hardly assuming. But it doesn't have to be exactly 1 year, any attack that takes longer but less than 2x average certificate lifetime with 64bit serial numbers (useless) becomes practical on 63bit serial numbers (useful, for a strange meaning of useful).
    - fwip 8y ago
      Such an attack doesn't exist. Any such attack would also become feasible with twice the budget.
      - omeid2 8y ago
        > Such an attack doesn't exist. As far as we know. > Any such attack would also become feasible with twice the budget. Assuming that the attack yields to parallel computing and scales linearly with more cpu/cores, because linear programming is bound to current compute capabilities and then theoretical limits like Bremermann's limit and Margolus–Levitin theorem.
a-wu 8y ago
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.) [1] https://groups.google.com/forum/#!topic/mozilla.dev.security.policy/nnLVNfqgz7g https://groups.google.com/forum/#!topic/mozilla.dev.security... [2] https://groups.google.com/d/msg/mozilla.dev.security.policy/nnLVNfqgz7g/VAdQotoiBQAJ https://groups.google.com/d/msg/mozilla.dev.security.policy/... [3] https://groups.google.com/d/msg/mozilla.dev.security.policy/nnLVNfqgz7g/OVKywVZIBgAJ https://groups.google.com/d/msg/mozilla.dev.security.policy/...
jrochkind1 8y ago
from that write-up, I'd call that a bug in EJBCA more than a "misconfiguration". If it was working as designed, then it's design was buggy. :)
modeless 8y ago
Is this a consequence of Java's failure to expose unsigned integer types?
systemBuilder 8y ago
This is the most hype-driven bit of misinformation I'm surprised fox news did not publish it first?
tbodt 8y ago
The true cost of Java not supporting unsigned integers
- bdhess 8y ago
  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.
nneonneo 8y ago
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...
- Cthulhu_ 8y ago
  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. [1] https://en.wikipedia.org/wiki/DigiNotar https://en.wikipedia.org/wiki/DigiNotar
  - matmg 8y ago
    I don't think you can compare misissuing certificates, including *.google.com, to leaving one bit out of 64 marked as 0.
IloveHN84 8y ago
Personally I hate EJBCA. 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)
Golfkid2Gadfly 8y ago
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.
- Ajedi32 8y ago
  > 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.
air7 8y ago
This article really annoys me. 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"
- fredley 8y ago
  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.
- Xylakant 8y ago
  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.
  - fixermark 8y ago
    As you know, those 50%s grow quickly. But the relevant question is "How few bits before cracking the cert takes less time than the rate of reissuance?" And the answer is "Fewer than 63."
    - shawnz 8y ago
      I think you're missing their point. The time it takes to crack a key is given as an average. In reality, half of all 64 bit keys are crackable in the same amount of time or less than what it would take to crack a 63-bit key on average. So if they are saying that it's feasable to crack any 63-bit key in that timeframe, then it must also be true that it's feasable to crack around 50% of 64-bit keys in the same timeframe. Clearly that's still unacceptable.
mikestew 8y ago
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. [0] https://www.snopes.com/fact-check/brown-out/ https://www.snopes.com/fact-check/brown-out/

267 points by jonburs 8y ago

bitxbitxbitcoin 8y ago

“Almost no chance of exploitation.” How true is this?

ikeboy 8y ago
True. 2^63 and 2^64 are effectively the same cost to break. Instead of costing $2X to break, it now costs $X.
- SethTro 8y ago
  when X > $1M (maybe even large) it really doesn't
  - geofft 8y ago
    They're "the same cost" because anyone with account to $1M or $1B to break a cert generally also has access to $2M or $2B. No reasonable threat model includes defending against attackers that have 50% of the necessary capital to conduct an attack but not more.
    - omeid2 8y ago
      I think this is a general fallacy held by a lot people. The notion that someone who has access to X amount of funds for a given task automatically has 2X and can also afford to spend 2X on the given task is not necessarily true, so such claims are generally baseless. What is most interesting is that these claims are generally about non-exact amounts, so the logic should follow that if you can afford X, then you can afford 2X, also means that you can afford 4X, and 8X, ad infinitum. In practice, a 2X difference in majority of real life cases concerning substantial amount of resources is by definition substantial and far from a trivial.
      - geofft 8y ago
        I'm not sure but I think you're trying to say I'm wrong. In the general case it's wrong, of course, to say that being able to afford X implies being able to afford 2X: few people could afford 2x their rent or a house 2x the price of theirs, etc. Few people would fail to be meaningfully affected by getting 2x (or 1/2x) their salary. But I'm talking specifically about cryptographic threat models. No reasonable threat model says, conducting this attack takes $100,000, and since most people don't have $100,000 in savings it's safe, because defending against "most people" isn't meaningful. A reasonable threat model says either, conducting this attack takes $100,000 so we're going to add an additional layer of security because it's a realistic attack, or conducting this attack takes $100,000,000,000,000. In such a threat model, if the numbers change by a factor of two in either direction (either through a one-bit error like this, or through macroeconomic trends, or whatever), it doesn't change the analysis. And in particular the claims here are in fact about exact amounts: a factor of two, or one bit. Cryptographers tend to measure things very precisely in bits. There's usually no good reason for a particular choice (64 is not a magic number here, it's just a convenient number for computers), but the analysis is still done with that particular choice. You can measure the difficulty of attacking a problem with N bits of entropy, and then add a heavy margin on top, and be very clear about what that margin is. Once you've done that, N-1 becomes probably reasonable, and you can argue precisely about why it's reasonable; you can argue equally precisely that N-5 is questionable and N-10 is not reasonable, and that the arguments are not recursive.
        omeid2 8y ago
        > No reasonable threat model says, conducting this attack takes $100,000, and since most people don't have $100,000 in savings it's safe Sure, that is never the claim. > And in particular the claims here are in fact about exact amounts: a factor of two Sure, but that is still a factor of X, an unknown amount. The bottom line is that for many actors, even nation state, the cost difference of 20M and 40M might mean that they have to seek alternative options. Not every actor has access to infinite amount of USD or compute.
        geofft 8y ago
    - tptacek 8y ago
      Objection! There is one such threat model: content protection schemes (like BD+) are that finely-calibrated. The goal is to be secure enough for the new release window, but to accept failure after that point. You're totally right here, I'm just nerding out on threat models and security economics.
- j16sdiz 8y ago
  This is an anti-collusion measure against birthday attack. The effect is exponential.
  - Ajedi32 8y ago
    2^x is exponential. GP is correct, it's still only one bit, so the cost is halved.
geofft 8y ago
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."
- deleted 8y ago
  [deleted]

xyzzy123 8y ago

Given that there seems to be no security impact (and none expected in the next year or two)... 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?

mmastrac 8y ago
No idea and completely unsourced, but one of the site comments states this: > 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://bugzilla.mozilla.org/show_bug.cgi?id=1531800 https://groups.google.com/forum/#!msg/mozilla.dev.security.policy/nlN_QrDwgaw/cg_v-VY0AQAJ https://groups.google.com/forum/#!msg/mozilla.dev.security.p... Still not getting the whole picture.
- geofft 8y ago
  The basic story as I understand it is that DarkMatter under contract to the United Arab Emirates wants to become a trusted CA, and they are widely expected to start running a governmental MITM once trusted, but the CA root programs don't have any provision for "You're a bunch of sketchy creeps, we don't trust you." (Oddly enough for a "trusted" root program, there is generally no actual evaluation of trust as conventionally defined. The "trust" part is "can you pass audits and generally be technically and organizationally competent to not let your private key be stolen / your infrastructure be abused by an attacker." Individual employees are part of the threat model, so there's usually a two-person rule for access to the private key; entire malicious organizations willing to lie in public and cover their tracks are not envisioned by the model.) So people are trying to block their application by nitpicking technical mistakes that, by the letter of the Baseline Requirements, disqualify you from being a CA. https://www.eff.org/deeplinks/2019/02/cyber-mercenary-groups-shouldnt-be-trusted-your-browser-or-anywhere-else https://www.eff.org/deeplinks/2019/02/cyber-mercenary-groups... covers some background on DarkMatter. One of the Baseline Requirements is you may not issue certs with fewer than 64 bits of entropy. Turns out DarkMatter was doing that, by issuing certs with 63 bits of entropy. Also turns out this was a thing lots of CAs did. Now that it's been pointed out publicly....

SethTro 8y ago

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.

deleted 8y ago
[deleted]
schoen 8y ago
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.
- tialaramex 8y ago
  Well not _all_ the bits. We do want the serial numbers to be non-identical because you need a way to talk about specific certificates for validity checking. Once upon a time bug reports would have focused on certificate serial numbers, these days they're more likely to be crt.sh links but arguably we should discourage that because crt.sh could go away some day.
  - schoen 8y ago
    Yep, that's what I mean by "for other reasons". (Without distinctive serial numbers or crt.sh, we would probably have to attach PEM copies of the certificate in every discussion about it.)

geofft 8y ago

> 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.

talaketu 8y ago
"50% easier than theoretically impossible" means it's now 50% possible, doesn't it?
- Dylan16807 8y ago
  No more than "half of infinity" is half finite.
  - TylerE 8y ago
    Infinity and "practically infinity" aren't the same thing though. Half of "practically infinity" may end up being practical.
    - krferriter 8y ago
      Yes the previous value was not infinity. It was impractical to solve in a human lifetime, but if they keep trimming off a few bits it very quickly becomes practical. If actually "infinity" then dividing it by any finite number would still result in infinity, which is not the case here.
      - geofft 8y ago
        Right, which is why the specific claim here is that 63 is not a problem, not that smaller numbers in general are not a problem. A better way to put this: instead of saying "it reduces the search space by 9 quintillion," say "it reduces 50% of the search space." Sure, that's a lot, but not nearly as much as trimming 8 bits and saying "it reduces 99.6% of the search space."

spydum 8y ago

Sooooo all the big players depend on one CA PKI package: EJBCA - is that not a major concern ?

danite 8y ago
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.
- spydum 8y ago
  Suppose so but doesn’t it become one well to poison? It just surprises me a bit (mainly because I was NOT familiar with EJBCA and have moderate awareness of PKI)
  - omeid2 8y ago
    I suspect a lot of people expect OpenSSL or LibreSSL to be used in this kind of setups.
gpm 8y ago
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).
- geofft 8y ago
  Counterpoint (which I'm not fully convinced of myself, to be fair): CAs are supposed to be interchangeable and easy to revoke. While the CA ecosystem as a whole must be robust, no individual CA can be too big to fail. If a serious bug is found in software used by one or a few CAs (imagine something like the Debian OpenSSL bug from 11 years ago), revoking them and requiring customers to move to other CAs is feasible. If a serious bug is found in software used by all CAs, you can't revoke all the certs on the web and leave HTTPS useless globally while CAs set up new software. On a tangent: one practice I'd genuinely like to see for security reasons (and which I'm surprised the CAs haven't proposed themselves, since it would make them twice as much money) is that major sites should always hold valid certs from two CAs, so that if a CA gets revoked it's just updating a file or even flipping a feature flag and certainly not signing up with a new CA. It would make sense to have two certs generated by different software, then. (It might also make sense, re abuse of power concerns, to present both certs and have browsers verify that a site has two valid certs from two organizationally-unrelated CAs. That way you can be significantly more confident that the certs aren't fraudulent.)

profmonocle 8y ago

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.

deleted 8y ago
[deleted]
_wmd 8y ago
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
- heinrich5991 8y ago
  I believe this is only an issue if you can produce collisions for the underlying hash function. SHA256 is still considered safe against that.
- geofft 8y ago
  The signature is over all the data in the certificate. So a hash collision in the signature algorithm makes this attack possible. (And if you can predict/control serial numbers, it makes the attack much easier because then you can generate a colliding pair of one valid cert and one invalid one and get the first one signed, instead of having to find a preimage of a valid certificate.) But without a hash collision, it should be theoretically safe to have no entropy at all. Most commonly-digitally-signed objects (Git commits, software packages, etc.) have no added entropy in the object itself / the input to the hash function.

helper 8y ago

This is the CAB Forum rationale for serial number entropy[1]: > As demonstrated in https://events.ccc.de/congress/2008/Fahrplan/attachments/1251_md5-collisions-1.0.pdf 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/ https://cabforum.org/2016/03/31/ballot-164/

ggm 8y ago

CT principles would surely demand they do some public facing declaration? 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 8y ago
I don't understand what you're asking. 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.

bandrami 8y ago

Again and again, the problem with PKI is not the tech, but the agents. We need an authorityless solution.

j16sdiz 8y ago
It works fine until some bug arise and nobody have the authority to fix it....

wahern 8y ago

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.

paulddraper 8y ago
Yes, now certificates are about half as hard to hack as they were supposed to be.
- baking 8y ago
  Does that mean that twice as many will be cracked?/s
  - deleted 8y ago
    [deleted]
- cheeze 8y ago
  Well, it depends on what you mean by "hack." The attack that we're talking about here isn't breaking a signature, but relies instead on being able to manipulate certificate data to generate a certificate with a known hash. That hash must collide with another certificate hash, which would then let you generate a rogue certificate. A team demonstrated that this attack was possible by being able to issue a rogue cert by being able to predict the not_before and not_after on the certificate that would be issued, predicting the serial of the issued cert, and finding an input for the rest of the cert fields which caused a collision. https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/ So, yes 128 bit serials would be better, but we should be safe even at 63 bits of entropy.

omeid2 8y ago

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.

p1mrx 8y ago
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.
- deleted 8y ago
  [deleted]
- omeid2 8y ago
  imagine is hardly assuming. But it doesn't have to be exactly 1 year, any attack that takes longer but less than 2x average certificate lifetime with 64bit serial numbers (useless) becomes practical on 63bit serial numbers (useful, for a strange meaning of useful).
  - fwip 8y ago
    Such an attack doesn't exist. Any such attack would also become feasible with twice the budget.
    - omeid2 8y ago
      > Such an attack doesn't exist. As far as we know. > Any such attack would also become feasible with twice the budget. Assuming that the attack yields to parallel computing and scales linearly with more cpu/cores, because linear programming is bound to current compute capabilities and then theoretical limits like Bremermann's limit and Margolus–Levitin theorem.

a-wu 8y ago

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.) [1] https://groups.google.com/forum/#!topic/mozilla.dev.security.policy/nnLVNfqgz7g https://groups.google.com/forum/#!topic/mozilla.dev.security... [2] https://groups.google.com/d/msg/mozilla.dev.security.policy/nnLVNfqgz7g/VAdQotoiBQAJ https://groups.google.com/d/msg/mozilla.dev.security.policy/... [3] https://groups.google.com/d/msg/mozilla.dev.security.policy/nnLVNfqgz7g/OVKywVZIBgAJ https://groups.google.com/d/msg/mozilla.dev.security.policy/...

jrochkind1 8y ago

from that write-up, I'd call that a bug in EJBCA more than a "misconfiguration". If it was working as designed, then it's design was buggy. :)

modeless 8y ago

Is this a consequence of Java's failure to expose unsigned integer types?

systemBuilder 8y ago

This is the most hype-driven bit of misinformation I'm surprised fox news did not publish it first?

tbodt 8y ago

The true cost of Java not supporting unsigned integers

bdhess 8y ago
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.

nneonneo 8y ago

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...

Cthulhu_ 8y ago
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. [1] https://en.wikipedia.org/wiki/DigiNotar https://en.wikipedia.org/wiki/DigiNotar
- matmg 8y ago
  I don't think you can compare misissuing certificates, including *.google.com, to leaving one bit out of 64 marked as 0.

IloveHN84 8y ago

Personally I hate EJBCA. 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)

Golfkid2Gadfly 8y ago

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.

Ajedi32 8y ago
> 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.

air7 8y ago

This article really annoys me. 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"

fredley 8y ago
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.
Xylakant 8y ago
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.
- fixermark 8y ago
  As you know, those 50%s grow quickly. But the relevant question is "How few bits before cracking the cert takes less time than the rate of reissuance?" And the answer is "Fewer than 63."
  - shawnz 8y ago
    I think you're missing their point. The time it takes to crack a key is given as an average. In reality, half of all 64 bit keys are crackable in the same amount of time or less than what it would take to crack a 63-bit key on average. So if they are saying that it's feasable to crack any 63-bit key in that timeframe, then it must also be true that it's feasable to crack around 50% of 64-bit keys in the same timeframe. Clearly that's still unacceptable.

mikestew 8y ago

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. [0] https://www.snopes.com/fact-check/brown-out/ https://www.snopes.com/fact-check/brown-out/