Forgot your password?
typodupeerror
Encryption Security IT

99.8% Security For Real-World Public Keys 108

Posted by Soulskill
from the what's-.2%-among-friends dept.
An anonymous reader writes "If you grab all the public keys you can find on the net, then you might expect to uncover a few duds — but would you believe that 2 out of every 1000 RSA keys is bad? This is one of the interesting findings in the paper 'Ron was wrong, Whit is right' by Lenstra, Hughes, Augier, Bos, Kleinjung and Wachter. Quoting from the paper's abstract: 'We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for "multiple-secrets" cryptosystems such as RSA is significantly riskier than for "single-secret" ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.'" For a layman's interpretation of the research, the NY Times has an article about the paper. Update: 02/15 01:34 GMT by S : Security researcher Dan Kaminsky has commented on the paper, saying that while the survey work itself is good, it doesn't necessarily support the paper's thesis. He writes, "On the most basic level, risk in cryptography is utterly dominated, not by cipher selection, but by key management. The study found 12,720 public keys. It also found approximately 2.94 million expired certificates. And while the study didn’t discuss the number of certificates that had no reason to be trusted in the first place (being self signed), it did find 5.4M PGP keys. It does not matter the strength of your public key if nobody knows to demand it."
This discussion has been archived. No new comments can be posted.

99.8% Security For Real-World Public Keys

Comments Filter:
  • by icebike (68054) * on Tuesday February 14, 2012 @07:17PM (#39039599)

    Quoting from the NYT article:

    They were able to produce evidence that a small percentage of those numbers were not truly random, making it possible to determine the underlying numbers, or secret keys, used to generate the public key.

    This is a far cry from "no security at all" if I understand it correctly. Any email encrypted with those keys would still be encrypted. And Joe Random Lurkerr would not be able to decrypt it even if he did intercept it.

    However Random Monitoring Agency might amass enough such emails to make a guess at the random number used key generation. You have to have a fairly good sized pool of keys to work from in order to figure out the keys of any single encryption.

    The paper goes on to state:

    Cryptosystems such as RSA that require, during key-setup, multiple secrets are more aaffected by the apparent difficulty to generate proper random values than systems such as Diffe-Hellman (cf. [8]), ElGamal, and (EC)DSA that require a single secret. For either type of system identical keys can be exploited only by parties that can be identified by searching for the owner of the duplicate. But for the former (RSA) partially identical choices allow any malcreant to commit fraud.

    For some values of "Any". You still need a significant number of such RSA keys in which to search for the use of duplicate random numbers.

    So DSA keys are safer it would seem.

    • by Spykk (823586) on Tuesday February 14, 2012 @07:28PM (#39039697)
      If what that quote says is true and you could derive the secret key from the public key then one could say that the key is worse than no security at all. Public keys are, by definition, public. They are generally available to the public at large on keyservers like http://pgp.mit.edu./ [pgp.mit.edu] You wouldn't need to intercept any messages because you could use the public key to encrypt any number of examples. The false sense of security presented by encrypting something with one of these flawed keys would make them very dangerous indeed.
      • by khasim (1285) <brandioch.conner@gmail.com> on Tuesday February 14, 2012 @07:47PM (#39039871)

        Suppose someone checks thousands of cars and finds that 998 out of every thousand cars checked had good, working brakes.

        But 2 out of every thousand cars checked had bad brakes.

        Is the braking system on cars broken?

        Or do we need to find out how and why those particular cars have problems? I vote for this one.

        • by karnal (22275) on Tuesday February 14, 2012 @08:08PM (#39040057)

          But at some point you want to fix the source, as it's cheaper and easier from a security (and a physical) perspective to fix it there.

          To take your example into account - say Toyota is building a line of Camry cars out of building X. 998 of 1000 have good brakes. They are interested in fixing the cars that are broken, but they're also going to launch an investigation as to why they're broken in the first place. In this case, could be a bad supplier shipping slightly out of spec parts; could be a worker on the line who is dissatisfied with his/her job. That's where fixing the system comes into play - if the system works as it should, then there's no cars to fix (in an ideal world - and that's what we try to get to with security as well.)

          • by martin-boundary (547041) on Tuesday February 14, 2012 @08:32PM (#39040287)
            But the situation looks different from an attacker's point of view. The attacker sees 2/1000 guaranteed easy targets, ie it's a fishing expedition which costs about 1000 tries for about 2 successes, so he can budget for the processing power etc.

            Moreover, the attacker doesn't care if the ultimate cause of the security failure is the manufacturer or the user or some freak lightning storm. All he cares is that statistically 2/1000 are guaranteed.

            • by Anonymous Coward

              Mod parent up. This is something which is important to be understood by IT personnel. I only understood it when some people started to systematically steal accounts with weak passwords on out site. It was not a problem for the vast majority of people with weak password, because there was a relatively small chance that they became affected. It was a problem for us, because any malicious people, maybe even without scripting, just trying manually, was able to guess the password of one from every 20 account. Be

          • But at some point you want to fix the source, as it's cheaper and easier from a security (and a physical) perspective to fix it there.

            They've identified that there MAY be a problem.

            But they haven't identified the source of the problem.

            Is it a certain make/model of Toyota?
            Is it a certain rotor from a manufacturer that is in different makes/models?
            Is it user error?

            Until they identify the source (sources?) of the problem then they cannot say that X is "broken". Because X seems to work in 998 out of 1,000 cases

            • by karnal (22275)

              This is why I specifically stated one model of car (Toyota Camry) as to not muddle the field with different part #s etc. And I only threw out suggestions as how to fix, seeing as I don't know what's broken in either case.

              What's the difference? Well, what's the difference in the 2 encryption cases from a security perspective? Don't know the answer to either I'm afraid.

        • by Magada (741361)

          Far less than 2/1000 Ford Pintos failed catastrophically.

          • by swb (14022)

            Since the risk of car accidents generally is pretty high, was the Pinto really a risk, or was it more media perception?

            • by Magada (741361)

              It was real risk, the design was flawed, the fuel tank was prone to catching fire upon the car being struck from the rear (just backing into a wall at more than walking speed was enough, really). But what inflamed the public was the unveiling of a rather cold-hearted financial risk calculation (a recall would cost X dollars, lawsuits from deaths and damage incurred will cost Y dollars over the model's lifetime, Y no recall).

              Interestingly enough, the company was forced to do a recall and the ultimate cost to

              • by Magada (741361)

                slashcode ate part of my post. I meant to write that X was larger than Y in the risk calculation so they decided to not do a recall.

      • by ceoyoyo (59147) on Tuesday February 14, 2012 @07:54PM (#39039935)

        Worse, the attacker could sign things that looked like they came from you.

        • > Worse, the attacker could sign things that looked like they came
          > from you.

          Hey, I wrote that!! :-O

    • Surely if the authors found these useless keys, a bad guy could too, using the same publicly available lists of keys. Or am I missing something? Once the bad guys know which keys are bad, anything "secured" with those keys would be vulnerable. Sounds like "no security at all" is about right. Of course people who don't want to go through the few hours it took the authors to search the public keys would still not be able to access your transmissions, but those aren't the people for which the security is p
    • Flaw in random number generator + euclid's algorithm = known factors for public keys = totally broken public key.

      Think about it. A flaw in random number generation may well result in several people independently picking the same factor for their public key. Just run euclid's GCD algorithm on all pairs of public keys, which is O(n^2 * m) where n is the number of keys and m is their average length. Poof, all the ones that managed to 'accidentally' share a factor with another one pop out with their factors sin

      • And, in case you're still confused, this means that anything that was encrypted with this public key may now be decrypted. It also means that any signature it's ever made is now suspect as anybody who knew about this problem could've made that signature.

        Of course, if someone is a protocol that implements forward secrecy and just using the RSA key to sign a diffie-helman exchange and then using the resulting key from that to encrypt their communications with a block cipher, they might be safe. Of course, th

        • Pseudo-random number generation is a problem that's been seen before. That numerous machines can be at a point where their seed is odd means that an additional factor, like a time-date hash, could re-randomize the key, thus reducing the attack set.

          I wonder if it's specific to one platform or another....

          • by TheRealMindChild (743925) on Tuesday February 14, 2012 @11:43PM (#39041415) Homepage Journal
            This isn't about psuedo-number generation, it is about using a seed that is easy to determine.... like 0.

            The claim that random number generation using the timer/tick count can be easily guessed is, at best, misleading. Your application has no idea what services are running, what priorities they are running at, etc, and to discover those would add even more entropy to the situation as it takes even more unknown amount of system time to determine their impact
      • by fatphil (181876)
        "... on all pairs ..."

        There are tens of trillions of pairs. You're the guy they predict will take 10 years to achieve what they did in an hour.

        You need to combine and conquer in order to actually get results before the certificates expire. (A back of a fag packet calculation implies that a naive GCD tree could crack them all in less than a day using GMP.)
    • by pla (258480)
      You still need a significant number of such RSA keys in which to search for the use of duplicate random numbers.

      And that limits an attacker how? Even ignoring the vast numbers of "abandoned" keys you can find with a clever Google search, you can always just make them yourself. A small army of Chinese prisoners can beat mere 500:1 odds in the time it takes most of us to drink our morning coffee.
      • by icebike (68054) * on Tuesday February 14, 2012 @07:54PM (#39039939)

        Well, left unsaid is just how many trials it takes to determine if the key in question is one of those 2 in 100 that is vulnerable.
        And the exact process is still not documented.

        • by Omnifarious (11933) * <eric-slash@omnif ... s.org minus city> on Tuesday February 14, 2012 @08:06PM (#39040039) Homepage Journal

          Steps:
          1. You scoop up all the public keys you can find. People generally publish them. They're public keys.
          2. You run GCD on each pair.
          3. You find they share a common factor and you win! Both keys are now completely and totally compromised. You know the secret key for both of them.
          4. Or... you find they share a common factor of 1. Oh, well, on to the next pair.

          • by Anonymous Coward

            2. You run GCD on each pair.

            For those who didn't know: the Binary GCD algorithm [wikipedia.org] only requires O((log_2 uv)^2) time in the worst case, which makes it super efficient to make this test.

            However, the number of 2048-bit primes is so astronomically large (think ~10^600), that you're more likely to randomly guess the prime factors of a given key than you are to find a collision between any two RSA-4096 keys ever generated -- past, present, or future.

            • by pla (258480)
              However, the number of 2048-bit primes is so astronomically large (think ~10^600), that you're more likely to randomly guess the prime factors of a given key than you are to find a collision between any two RSA-4096 keys ever generated -- past, present, or future.

              Very true, with one slight problem - We have no way to actually produce (non-trivial) guaranteed 2048-bit primes. Instead, in the real world we use likely primes via a combination of Fermat and Miller/Rabin testing.

              TFA points out that, becaus
              • by fatphil (181876)
                Bollocks. Google "APRCL" or "ECPP".

                And typically we have good enough PRNGs, we just don't use good enough seeds, as the seed is the only source of entropy.
            • by fatphil (181876)
              Bollocks. Now RTFA. Random number generation in some implementations is very flawed, and your entire conclusion is demonstrably false (and Lenstra has 12000 examples as proof).
            • by kasperd (592156)

              However, the number of 2048-bit primes is so astronomically large (think ~10^600), that you're more likely to randomly guess the prime factors of a given key than you are to find a collision between any two RSA-4096 keys ever generated -- past, present, or future.

              Actually that's not correct. Where you say more likely, you should instead have said slightly less likely. But that is assuming the key generation algorithm generated random primes. In reality the primes being generated are not truly random. And th

      • by fatphil (181876)
        The problem is that you have to make flawed keys. How do you know you're using the same flawed algorithm as (some subset of) the masses? If you aren't, then there's basically zero chance of a collision. (It's effectively trial division.)

        Do you take a bomb on to a plane in order to guarantee your safety? The chances of there being 2 bombs on a plane is minimal, right?

        Now were you to find one factor using your technique, which cannot be pure luck, it must because you're using the same flawed algorithm used by
    • by mveloso (325617)

      The article states that it's possible to determine the underlying numbers, not that they did it.

      That's just like the MD5 collision problem a few years back.

      The bad thing is that now that researchers have discovered this possibility there may have been someone that discovered it before and is actively exploiting it. Which is problematic, but I suspect that it's easier to compromise the back-end instead of attacking TLS directly.

    • by petermgreen (876956) <plugwash.p10link@net> on Tuesday February 14, 2012 @08:19PM (#39040163) Homepage

      So DSA keys are safer it would seem.

      DSA has it's own problems. Most notably merely USING your key to generate a signature with a broken random number generator can be enough to reveal it to an attacker. Thankfully PGP doesn't use openssl and while it's POSSIBLE to use the same keys for ssh and pgp the impression I got is that not many people do.

      http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-that-almost-was/ [root.org]

  • Any possibility for information to be handed over to them is always worth the low odds.

  • Slow down (Score:5, Interesting)

    by Effugas (2378) * on Tuesday February 14, 2012 @07:34PM (#39039743) Homepage
    I'm not seeing any data on what portion of those keys with bad moduli were actually attached to valid certificates.

    It's damn fine survey work, but the conclusions are just strange. More detail here:

    <a href="http://dankaminsky.com/ronwhit">Survey is good. Thesis is strange.</a>
    • by Z00L00K (682162)

      And how can we trust the certificate authorities these days?

      The current model is sensitive to security breaches at the CA:s and the general public has no control over which CA that is playing under the cover with which government.

  • by Anonymous Coward

    There's not published any mathematical proof of that RSA 4096-bit is broken, so that, it's suppossed to be secure for a short time, one week, or one month, or one year, or one century.

    JCPM: crackers aren't fool, they pick 100 best richest people for lottery of breaking 2 of their 100 credit cards (VISAs).

  • by kanoalani (2515446) on Tuesday February 14, 2012 @07:40PM (#39039803)
    I didn't find any discussion of what may have caused the lack of randomness. Presumably it was a particular implementation on a particular platform of RSA key generation and presumably they know what it is. I would be interested to know too.
    • Pretty sure this is the debian bug where the relevant packages for whatever reason decided to use a static number for the rng seed. There is an xkcd which pokes fun at this.

      • I've seen a *lot* of people take shortcuts like feeding in a well-known arbitrary piece of data as an entropy source in a script invoking SSL utilities. They will complain that '/dev/random is too slow (implicitly not realizing the urandom option)' or 'I wanted a script that would work exactly the same in all platforms and this happened to work'. Out of a plethora of better ways to do it they happen to pick the worst because they simply fail to understand the significance of the random source.

        • They will complain that '/dev/random is too slow (implicitly not realizing the urandom option)'

          Please help me understand this bit. It sounds as if you would prefer urandom over random. I'm not skilled in randomness on Linux, so I checked Wikipedia (emphasis mine):

          [...] A counterpart to /dev/random is /dev/urandom ("unlocked"/non-blocking random source) which reuses the internal pool to produce more pseudo-random bits. This means that the call will not block, but the output may contain less entropy than the corresponding read from /dev/random. While [/dev/urandom] is still intended as a pseudorandom number generator suitable for most cryptographic purposes, it is not recommended for the generation of long-term cryptographic keys. [...]

          That, to me, sounds as if one should not use urandom if random is as all feasible.

          So what's the deal here?

          • by Junta (36770) on Wednesday February 15, 2012 @09:50AM (#39044337)

            The problem with /dev/random is that it frequently is not feasible. The amount of usable entropy in /dev/random is rather low considering some needs. OpenSSL project itself defaults to urandom in fact. Frequently seeding /dev/urandom with /dev/random is a compromise.

            • by KlaymenDK (713149)

              +1 Informative -- Thank you.

            • Frequently seeding /dev/urandom with /dev/random is a compromise.

              That is interesting, how often is "frequently"? Can you increase randomness significantly by seeding from urandom, say, every 100 reads from random? Does this question even make sense? :)

              I tried to google for more details, but my search terms returned a lot of noise.

              • > That is interesting, how often is "frequently"?

                IIRC urandom reseeds itself whenever there is entropy available but free runs when entropy runs out instead of blocking as random does. Thus until the entropy pool runs dry the two are the same.

      • Is that the one along the lines of
        int rand() {
        return 3;// completely random seed, chosen by a roll of a dice
        }
      • by hawguy (1600213) on Tuesday February 14, 2012 @08:13PM (#39040105)

        Pretty sure this is the debian bug where the relevant packages for whatever reason decided to use a static number for the rng seed. There is an xkcd which pokes fun at this.

        Oh good, it's not too late to post the obligatory XKCD link:

        http://xkcd.com/221/ [xkcd.com]

      • Re: (Score:3, Informative)

        by Anonymous Coward

        First, if this were the Debian bug, I feel like they would have said so. I assume there is some other issue. I could be wrong though.

        My understanding of the Debian bug was that the OpenSSL key generation code had a bug where /dev/random (or /dev/urandom, whichever it actually used) was being read incorrectly but in a way that happened to work. The line that read the random seed appeared to be dead code despite happening to accidentally read in the random seed, so the Debian maintainer for the package delete

        • by Anonymous Coward

          Actually, we do say that it is NOT the Debian bug. In the paper.

      • by compro01 (777531)

        They didn't "decide" per se. What they did was read from uninitialized memory. Quick, simple, and cheap method to get a random value, and it works pretty much everywhere.

        Then some helpful person noticed they were reading from an uninitialized variable and not understanding why, went ahead and "fixed" it and no one noticed for a few years.

        • At the risk of taking a side-track - this is the perfect example of why I hate the concept of "self-documenting" code. A quick couple of words, indicating why the programmer was doing something weird, and this probably wouldn't have happened.

          • by AvitarX (172628)

            I don't really know enough to comment, but it's /.

            Couldn't a function name or some such be used to describe it?

            presumable that read is being done somehow, weather it's an initiated variable, or through a function or pointer or what not (not knowing enough to comment), I would think it's totally reasonable to explain what's going on with a name like uninitializedForSakeOfRandomSeed.

            • Or, as the guy above you said, just typing:

              // read from uninitialized memory to seed PRNG

              • by AvitarX (172628)

                My point was, the guy blamed self documenting code. I think it's a problem with poorly documented code, the method of which is irrelevant.

                That comment could be left out just as easily as the function/variable not concisely named.

        • What they did was read from uninitialized memory. Quick, simple, and cheap method to get a random value, and it works pretty much everywhere.

          Um, no. Uninitialized memory is not random.

        • Uninitialized memory is not random and whoever thinks that shouldn't be allowed near a compiler until they not only understand that they're wrong, but why they're wrong.

          In brief, when memory is released by a program, its contents aren't (usually) cleared. For anyone looking for random data, uninitialized memory is like a garbage bag full of old newspapers and post-its with passwords written on them. Not only is it just plain not random in that someone else might have a copy of the story you used for your "r

      • by fatphil (181876)
        If you RTFA, you'll see that they deliberately exclude the Debian fuckups from their sample set.
  • This is pretty bad (Score:4, Informative)

    by Omnifarious (11933) * <eric-slash@omnif ... s.org minus city> on Tuesday February 14, 2012 @08:17PM (#39040139) Homepage Journal

    It doesn't affect the security of RSA overall, but it strongly affects the security of certain keys, rendering them totally compromised.

    Think about it. A flaw in random number generation may well result in several people independently picking the same factor for their public key. Just run euclid's GCD algorithm on all pairs of public keys, which is O(n^2 * m) where n is the number of keys and m is their average length. Poof, all the ones that managed to 'accidentally' share a factor with another one pop out with their factors since a public key is just two big prime numbers multiplied together. Game over for those keys.

    Steps to exploit:

    1. You scoop up all the public keys you can find. People generally publish them. They're public keys.
    2. You run GCD on each pair.
    3. You find they share a common factor and you win! Both keys are now completely and totally compromised. You know the secret key for both of them.
    4. Or... you find they share a common factor of 1. Oh, well, on to the next pair.

    • by Omnifarious (11933) * <eric-slash@omnif ... s.org minus city> on Tuesday February 14, 2012 @08:20PM (#39040173) Homepage Journal

      As an addendum, this means that anything that was encrypted with this public key may now be decrypted. It also means that any signature it's ever made is now suspect as anybody who knew about this problem could've made that signature.

      Of course, if someone is a protocol that implements forward secrecy and just using the RSA key to sign a diffie-helman exchange and then using the resulting key from that to encrypt their communications with a block cipher, they might be safe. Of course, the same bug might result in predictable diffie-helman keys too.

      But any of those conversations may still have had a man-in-the middle.

    • by chihowa (366380)

      It doesn't affect the security of RSA overall, but it strongly affects the security of certain keys, rendering them totally compromised.

      ...Poof, all the ones that managed to 'accidentally' share a factor with another one pop out with their factors since a public key is just two big prime numbers multiplied together.

      Does this mean that every key generated has a chance of rendering a previously existing key totally compromised? If that's the case, RSA is actually broken. There are only so many prime numbers, so as more keys are created, more keys will potentially be compromised. Please, tell me I'm wrong (using a car analogy if possible).

      • Does this mean that every key generated has a chance of rendering a previously existing key totally compromised? If that's the case, RSA is actually broken. There are only so many prime numbers, so as more keys are created, more keys will potentially be compromised. Please, tell me I'm wrong (using a car analogy if possible).

        Just plan on using larger RSA keys (instead of 1024 bit), use the 3072 or 3200 or 4096 options when generating your RSA keys.

        From a cursory glance, the 0.2% number is only for RSA
        • This is all because the random numbers were bad random numbers. Not very random. The chances of properly generated 1024-bit RSA keys colliding is extremely tiny. Much, much smaller that 0.2%.

        • by russotto (537200)

          Just plan on using larger RSA keys (instead of 1024 bit), use the 3072 or 3200 or 4096 options when generating your RSA keys.

          From a cursory glance, the 0.2% number is only for RSA 1024. They indicate that RSA 2048 also suffers the same issue, but since the numeric space is much larger the odds go way down. Look for the "12720" number and you'll see the mentions of this being a 1024bit key issue.

          No.

          If your random number generator is bad, going from 1024 to 2048 doesn't get you better keys. It just gets you

      • by Omnifarious (11933) * <eric-slash@omnif ... s.org minus city> on Tuesday February 14, 2012 @11:05PM (#39041223) Homepage Journal

        Does this mean that every key generated has a chance of rendering a previously existing key totally compromised? If that's the case, RSA is actually broken. There are only so many prime numbers, so as more keys are created, more keys will potentially be compromised. Please, tell me I'm wrong (using a car analogy if possible).

        It does indeed mean this. But if the keys chosen are really and truly random, the chances of this ever happening are astronomically tiny.

        But there are an infinite number of prime numbers. There's even a mathematical proof of this fact. :-)

        More practically speaking, the actual distribution of primes is one prime every x/ln(x) numbers. This means that for numbers that are 1024 bits long, one in every 1024 of them is prime. This effectively means that the space of possible 1024-bit primes is 2^1023 (the top bit must always be one) / 2^10 = 2^1013. The chances that any two randomly generated 1013 bit numbers are exactly the same is extremely small. So small that you'd have to generate one such number for every proton or neutron in the solar system before you even got close to entering the realm of writing it down the percentage chance reasonably in non-exponent notation.

        So, no, this doesn't break RSA, even though what you say is true.

        • by WillerZ (814133)

          There is another consideration.

          When generating a 1024-bit random number which you hope is prime you take 1022 bits of random data and then put those bits in a 1-sandwich. For a 512-bit random probable prime you use 510 bits of random data. Having generated the probable prime you then test if it is very likely prime and if not you repeatedly add (or subtract, as long as your algorithm is consistent) two and retest until the test says you've found a winner. Because prime numbers are not perfectly evenly distr

    • Seriously, you are going to make the same post twice? http://it.slashdot.org/comments.pl?sid=2671717&cid=39040039 [slashdot.org]
      • by fatphil (181876)
        And his algorithm's completely unworkable too, as it's O(n^2) in the number of keys. Fortunately there exist O(n log n) approaches which would be a hundred of thousand times quicker (and which Lenstra probably used).
    • by fatphil (181876)
      This is the third time you've posted your totally useless (or "naive" as Lenstra calls it in his paper) algorithm. Your technique would take 10 years (I trust Lenstra's estimate, I've not verified it myself) on his data set.
      • I didn't read the paper, just guessed at the contents. And it doesn't surprise me that it's not optimal. I was posting it because it seemed there was a lot of disinformation that was being highly rated. I feel that what I posted was significantly less wrong, and gave people a better idea of the problem than the stuff I responded to.

        I believe though that I got the basic idea of what Lenstra is up to.

        I often find posts about cryptography to be extremely frustrating to read because of the complete lack of any

  • is too important to be left to chance."
    Robert R. Coveyou [quotationspage.com]
  • From what I know about RSA, the security comes from having 2 large secret prime numbers (call them P and Q).

    From reading this new paper, what these guys have been able to do is to take a pair of public keys and identify if one or both of the large secret prime numbers is the same between both keys. Am I reading things right, is this what they have found?

    And just how dangerous is it in the real world? I would assume that unless you can find (using this new discovery) a public key where one or both of P and Q

    • by YoungHack (36385) on Tuesday February 14, 2012 @10:31PM (#39041041)

      The process of finding that one of P or Q matches actually tells you that P or Q. That means instantly that both public keys can be factored. Hence both private keys can be determined. You don't need prior knowledge of either private key ahead of time, just the public keys.

      • by jonwil (467024)

        So are these keys a sign of weaknesses in specific implementations of RSA key generation or could they have arisen by pure chance due to 2 random number generators picking the exact same number (or is it a combination of both)?

        • by russotto (537200) on Tuesday February 14, 2012 @11:11PM (#39041259) Journal

          So are these keys a sign of weaknesses in specific implementations of RSA key generation or could they have arisen by pure chance due to 2 random number generators picking the exact same number (or is it a combination of both)?

          The primes for RSA-1024 should be 512 bits long. There are about 2^502 primes 512 bits long. By birthday paradox statistics, we should expect a collision in approximately every 2^251 choices, which is considerably less than 2 in 1000.

          So no, it's not chance.

          (all numbers extremely approximate)

    • And just how dangerous is it in the real world?

      Probably dangerous enough that if you were still using 1024 bit RSA keys, you should stop and move up to the larger key sizes above 3000 bit (and make sure that your PRNG isn't broken).

      But I'm pretty sure that 1024 bit RSA has been "not recommended" for at least a few years. The ssh-keygen in modern Linux systems uses a default of 2048 bits and I think GPG also uses 2048 bits as the default for a while now. The openssl documents on their website also reco
      • by fatphil (181876)
        The problem is entirely due to poor PRNGs (poorly seeded, more like). You get precisely no more scurity from using 3072-bit keys than using 1024-bit keys. If the prime generation process is deterministic and reproducable due to bad seeding, then generating identical 1536-bit primes is exactly as likely as generating 512-bit primes.

        Looking at their figures and charts, and assuming all other things were equal, I would expect about 300-350 2048-bit keys to have been found.
    • From reading this new paper, what these guys have been able to do is to take a pair of public keys and identify if one or both of the large secret prime numbers is the same between both keys. Am I reading things right, is this what they have found?

      Correct.

      I would assume that unless you can find (using this new discovery) a public key where one or both of P and Q match a key you already have the private half of, you cant decrypt.

      Not correct; if you have two RSA keys with a common prime factor, you can use the GCD to determine what that common prime is (normally, the GCD would be 1, because the two moduli would have no common factors), and then simply divide by that prime to determine both of the secret keys. The keys with common prime factors are effectively worthless, and worse still, someone happening to generate one of the same primes that you generated will leak your secret key to the entire world.

      Now, to be fai

      • by jonwil (467024)

        ok, so it not as bad as it sounds because you need to find a public key with P, Q or both matched to the key you want.

        e.g. its not like someone is going to be able to take the signing key for the XBOX 360 game disks and magically crack that open unless somehow by magic someone posted another public key out there that has the same public key or Microsoft REALLY screwed up their cryptography.

        • On the other hand, China might not care which American corporations they can read the emails of; they might just take whatever they can get. For a targeted attach, this is going to be hard to exploit -- it is like trying to guess one of the primes in an RSA number.

          Worse still, it may be the case that some particular software product or setup is causing these keys to be generated; this could make it easier to attack people using that software. Those weak keys might have been generated by a cloud service
  • the number of certificates that had no reason to be trusted in the first place (being self signed)

    I trust my self-signed certificate.

  • by rdebath (884132) on Wednesday February 15, 2012 @03:49AM (#39042315)

    "No reason to be trusted in the first place (being self signed)."

    At first this struck me as wrong. Mostly because all CA certificates are self signed.

    The I found a question, "why don't the CAs sign each other's certificates?"
    It's possible, they just never do it.
    Is it perhaps that they don't trust each other!
    If they don't trust each other why should we trust them ?

    • by TheLink (130905)

      Huh, they do. That's WHY you should trust CA certs less.
      See: http://groups.google.com/group/mozilla.dev.security.policy/browse_thread/thread/7ba51ca49de0f6cf [google.com]
      Summary: At least one CNNIC CA cert (think Chinese Gov) is signed by Entrust. So by default most browsers that trust Entrust will also automatically trust CNNIC.

      Which is not so good if one day the Chinese Gov decided to MITM you.

      • by rdebath (884132)

        From your link it wasn't a root certificate when it was signed, ie: by the "in the browser definition".

        Basically you've given me proof that they could sign each other's certificates. But that they don't because they're untrustworthy.

        Hmmm.

        • by TheLink (130905)

          1) The complaint in the link stated that a CNNIC cert was in the Mozilla browser store, AND it was signed by Entrust.

          2) I've given you proof that CAs _do_ sign each other's certificates. Whether they are included in the browser depends on the Browser bunch and nothing to do about whether the CAs trust each other or not. In this case the CNNIC cert was likely to have been included by Mozilla.

          So I don't see how you can say that I've given you proof "that they could sign each other's certificates. But that the

  • by KlaymenDK (713149) on Wednesday February 15, 2012 @06:34AM (#39042901) Journal

    It does not matter the strength of your public key if nobody knows to demand it.

    THIS! This is the core problem! Everybody knows email, and most people know that you shouldn't share your password with others, but nooobody knows about proper signatures and how to work with them.

    If each and every digital signature out there was useless, how much of our total bandwidth would be compromised?
    The painful answer is, at most the percentage that is signed in the first place, which is a drop in the proverbial ocean.

    Cory Doctorow has a statement about obscurity being a far bigger threat to authors than piracy, and I posit that an analog can be drawn for obscurity of security practices, the population at large, and privacy/security.

    It's hopeless to encrypt all your email unless your peers (including granny and junior) knows how to process such email, and knows to be suspicious of unsigned communications. If only some of the globally popular communications services would have the guts to enable, and indeed, enforce this. (Google and Facebook, I'm looking at you.) Yeah I know, they wouldn't be able to stay in *business* if they did that (which nicely highlights what, or rather who, the "product" really is).

  • I know about at least one public key that was intentionally created very weak, that is, one that is easily crackable.

    Why was it made? As a part of "hacking" competition.

    I wonder how many of the keys they found were bad were never used for anything serious, like the one I mentioned.

  • Apparently, they took the list of keys offline. So how do I know if my key is compromised?

We warn the reader in advance that the proof presented here depends on a clever but highly unmotivated trick. -- Howard Anton, "Elementary Linear Algebra"

Working...