Follow Slashdot stories on Twitter

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

1024-bit RSA keys In Danger Of Compromise? 368

Posted by Hemos from the well-of-course-they-are dept.
antiher0 writes "According to an email from Lucky Green that came across bugtraq yesterday, 1024-bit encryption should no longer be considered pristine. Bernstein released a proposal that outlines the creation of a machine capable of breaking 1024-bit crypto on the order of minutes or even seconds for the measly cost of ~$1B USD. For a more thorough discussion, check out the original email." Update: 03/26 03:16 GMT by T : And don't forget to revisit Bruce Schneier's analysis of Bernstein's claims, which cast doubt on the practicality of breaking such large keys anytime soon.
This discussion has been archived. No new comments can be posted.

1024-bit RSA keys In Danger Of Compromise? More

1024-bit RSA keys In Danger Of Compromise?

Comments Filter:
  • for the measly cost of ~$1B USD.

    Is the company you work for hirring? God I wish I could call a billion dollars measly!!

    • Re:$1Billion (Score:2, Insightful)

      by Mittermeyer ( 195358 )
      When carrier battle groups, air wings, army divisions and the fate of nations are on the line, $1 billion for total SIGINT access is cheap indeed.

      Break out those one-time key pads and pigeons, boys, the government will own your electronic crytposouls before you know it.
      • Or move to 4096bit.

        Don't forget, every bit added, doubles the strength.

        4096 != 1024*4

        My HP 48GX says:
        2^1024=1.79769313486E308
        2^4096=9.99999999 999E499 (which it also says for 2^1661, which seems to be the overflow point).

        4096 is 2^3072 times stronger

        ; )

    • Re:$1Billion (Score:5, Informative)

      by joe90 ( 48497 ) on Monday March 25, 2002 @08:27PM (#3225713) Homepage
      It *is* a measly sum - as the email says - how many government agencies have this sort of funding? More than just a couple of US agencies that's for sure.

      Assuming the email is correct (and having read it, it does't seem to be that incredible) That $1B investment gets you the infrastructure, systems and processes to routinely break 1024 bit keys (and therefore the contents of the encrypted payload) in a fairly short order.

      Since many people believe that a 1024-bit key is essentially uncrackable today, tomorrow and next century, 1024-bit keys are still going to be popular.

      If an organisation can amortise the cost over 3-4 years (which is the likely life of short (1024 or smaller) keys). That gives you quite a return on investment.

      If that $1B allows you to break one key every 5 minutes, over a 4 year period, you can break ~420,000 keys - which works out to a cost of less than $2500 per key. If you can intelligently target who's keys you wish to compromise, the benefits could be significant.

      • Re:$1Billion (Score:3, Interesting)

        by Mr. Flibble ( 12943 )
        It *is* a measly sum - as the email says - how many government agencies have this sort of funding? More than just a couple of US agencies that's for sure.

        Exactly.

        For those of you who would like a breakdown of how a system like this would work, you may want to read Cracking DES by the Electronic Frontier Foundation [oreilly.com]. (Note, this book is out of print, but the EFF has made versions available online. [eff.org])

        It discusses building a computer from scratch that can crack DES quite fast. This same principle can be applied to any brute-force technique. And if the cost is $1Billion now, it will be considerably less in a few years.

      • Re:$1Billion (Score:2, Funny)

        by Gerdts ( 125105 )
        Sounds like a business plan. Let's go find some VCs!
      • The depressing thing is that probably a few goverments seriously would like to spend $1 billion to try to read something in an RSA encrypted format.

        Yet despite all that money and zillions of man-years being blown on reading stuff in such a format, no one has managed to go out, and no one is willing to spend the money to try to crack .DOC and produce software capable of reading it. A much, much easier problem but one that hasn't been done completely.

        There are so many *smarter* things to blow money on than cryptography that it blows the mind. Cryptography is a fun mind game, but frankly when this much money is being spent on it it's just ridiculous.

        You can bribe the people involved for less than $1 billion. Heck, buy up a private army and take over the building that has the information that you want.

  • I'm sure I've heard this somewhere before... (Score:3, Informative)

    by darkwiz ( 114416 ) on Monday March 25, 2002 @08:09PM (#3225587)
    Here? [slashdot.org]

  • previously reported (Score:2, Informative)

    by Roadmaster ( 96317 )
    The basis for this story was on slashdot [slashdot.org] almost a month ago. A repeat? something derived from the previous story's information? the key point here is Bernstein's paper on factoring huge numbers, about which some people have commented, and which appears to "work out" on a mathematical level.

    • Re:previously reported (Score:3, Interesting)

      by bourne ( 539955 )

      It seems to me that this story is hitting slashdot because, well, it hit slashdot.

      The original was passed around a few small mailing lists, where it got some comment but nothing big. Then it hit slashdot a month ago, and the number of places I saw it popping up increased. I also saw a story about DJB cranking at some reporter for misunderstanding the exact nature of the information, which tells me that someone thought it was suddenly big enough to have a reporter look into.

      And now, perhaps based on all this "publicity," Lucky Green or whoever is setting up discussion of it at some conference and revoking his old key. Note that he didn't do it a month ago, when the story was on all the crypto lists - presumably the more attention it got, the more real it became.

      Maybe I'm off base here, but I think this is one of those examples of the media gestalt manipulating and being manipulated by the media consumers - the story had to get big before it could be taken seriously, and it had to be taken seriously before it could get big... and the slashdot story a month ago was probably one of the bigger steps along the way.

      The slashdot effect... It isn't just for websites anymore!

    • he sais that the article referenced by slashdot has caused him to re-examine the CUMULATIVE effects of a number different recent development, not just the Bernstein paper

  • It's funny, laugh. (IHNRTA) (Score:3, Funny)

    by Anonymous Coward on Monday March 25, 2002 @08:12PM (#3225608)
    That's okay.

    I'm certain that qcrack will be poorly documented and require the addition of 5,000 users to whatever supercomputer it happens to operate properly on.

    Then DJB will speak incessantly about how it differs from other encryption cracking techniques with its "modular design" (which is actually the application of many patches in order to obtain features found in most SMTP daemons, err cracking programs). Yeah.

    (Disclaimer: I love qmail.)
    • (Disclaimer: I love qmail.)

      That's probably because you haven't tried postfix yet. I thought qmail was the bomb too until I discovered postfix and realized how bad the logging is in qmail.
  • You got a great machine to be built w/taxpayer dollars on the cheap and quick.

    It is way easier for you to move up a few orders of magnitude of encryption than for them to build a machine that can crack it.

    However, this will mean a bigger supercomputer for all kinds of numbering tasks - basic research and math, physics, and astronomy will eventually benefit.

  • Break my crypto for $1B? (Score:5, Funny)

    by brer_rabbit ( 195413 ) on Monday March 25, 2002 @08:15PM (#3225633) Journal
    Don't waste your money. I'll sell my company's secrets for a fraction of that.

    • Actually that's a very good point. At some point it does become more economical to buy off a person on the 'inside' of what ever organization you want to get secrets from... Hell I'd sell my personal secrets for a $1.50. Of course I don't have anything worth mentioning except my infatuation with girls with southern accents... oops well there's a freebie.
    • This would be an interesting Slashdot poll. "How much do you consider your most sensitive data to be worth?"

      $1
      $100
      $1000
      $10000
      $100000
      $100000000
      Mo re than Cowboy Neil has.

    • Not so fast.. (Score:5, Insightful)

      by Sloppy ( 14984 ) on Monday March 25, 2002 @09:54PM (#3226124) Homepage Journal
      The person who builds this machine may still underbid you. The machine doesn't just crack your secrets -- it's reusable. When you amortize the gigabuck over all the different people who need to be spied on, it may yet work out to be less than your minimum bribe.
  • Here's the link to their write up, commenting on Bruce Schneier's take No Big Deal [securityfocus.com].

    Anyway, we all know they've been reading our sekrit kees by telepathy for years now, right?

  • Would this be a solution? (Score:5, Insightful)

    by SClitheroe ( 132403 ) on Monday March 25, 2002 @08:19PM (#3225654) Homepage
    If you can come up with a brute force approach to common encryption schemes, could you not stay one step ahead of something like this by utilizing multiple layers of encryption, with differing methods of encryption at each level?

    Give that a brute force attack is orders of magnitude more computationally intensive than the original encryption, would this allow you to stay ahead of the curve?

    Also, although the papers seem to indicate that the proposed system could try multiple forms of attacks on the encrypted data, would modifying or customizing the encryption algorithm at each layer of encryption help? Computers are great at brute force attacks, but I highly doubt a system such as this proposed one can do much in the way of analysis or reverse engineering of the encryption algorithms used...at some point, you'd have to resort to good old (and slow) human deduction...
    • That's kindof the idea behind Triple-DES. Description here [tropsoft.com]. DES was deemed too easy to break, so Triple-DES was born and is still used in some applications today. Used properly, it turns the effective 56-bit key length of DES into 168 bits in Triple-DES.

      • It is however interesting to note that due to the way such Fiestel ciphers work, a double DES is easier to break than a single. Why? I don't remember, I'm not a math major, and don't feel like getting out my Crypto notes from last semester. :)

    • Re:Would obscurity be a solution? (Score:5, Informative)

      by Glorat ( 414139 ) on Monday March 25, 2002 @08:40PM (#3225778)
      Two issues going on here!

      Ah... the old security through obscurity notion. Someone else can carry the debate here but trying to get security by trying to hide what layers of algorithms you are using is defeating the point of security research. A "secure algorithm" is basically one such that it does not matter whether the hacker has access to the algorithm or not. Cracking a "secure algorithm" should be as hard as cracking by brute force. If your security relies on obscurity, then you are asking for trouble in general

      As for layering in general. Well it works for the most part (e.g 3DES) although there are caveats (2DES would not be safe). But the real point is that layering is slow. Doing 1024-bit RSA encryption is slow. And try generating a 2048-bit key instead of a 1024-bit key. It takes ages (possibly minutes on some computers). You may be increasing security but decreasing performance.

      Now going back to the first point about a "secure algorithm", you are better of say doubling your key size and exponentially increasing the keyspace on your existing algorithm then either inventing your own layering scheme that may or may not work AND will be slow nad memory wasteful by using many algorithms. The short answer is, you don't need layering, just make larger keys.

      • A "secure algorithm" is basically one such that it does not matter whether the hacker has access to the algorithm or not.
        The point of layering is not to keep the algorithm secret, it's to protect against cryptanalytical breakthroughs. Even if the cryptanalyst gets very lucky (or is very smart) and completely breaks one of the subciphers, the other subciphers still protect your data.
        • Another handy side-effect is that it may make the cracks themselves more difficult. It doesn't apply to breaking RSA (which is just factoring), but many of the best attacks for symmetric ciphers rely on having known plaintext - a file header, or whatever. Since the plaintext in this case would in fact be (hopefully) random ciphertext, the attacker's got a lot less to work with.

          There are disadvantages, of course - you don't know that the two algorithms together are secure, and when considered as a whole, the chances are that they're not more secure. You're relying to a certain extent on the attacker sticking to the rules and considering the supciphers as subciphers, instead of just trying to cryptanalyse the whole mess. The other difficulty is that the more layers you add, the more key material you need - at a certain point, you begin to have trouble getting enough truly random data.

      • Re:Would obscurity be a solution? (Score:5, Funny)

        by Shiny Metal S. ( 544229 ) on Tuesday March 26, 2002 @06:07AM (#3227337) Homepage
        As for layering in general. Well it works for the most part (e.g 3DES) although there are caveats (2DES would not be safe).
        That's correct. Once I wanted to make ROT13 stronger, so I decided to encrypt the message twice, but I discovered that 2ROT13 was actually less safe than ROT13. I finally used 3ROT13 and even 5ROT13 for the most sensitive data, however I'm not sure how much more secure is 5ROT13 than 3ROT13, but what the hell, the overhead is not very high.
    • Using multiple encryption on one message may not increase the difficulty and may even lower it. Encryption algorithms are mathmatical formula so this example will suffice even though it may be simplistic. Say you have two encryption algorithms F(x)=8x and G(x)=x*x*x. You may think that by combining the two would make it more difficult to find x but F(G(x))=(2x)*(2x)*(2x) or 2x cubed which is as difficult as G(x) by itself. But say instead of G(x) you used H(x)=x/8 which would simply decrypt x to it's original value. In short to be able to combine encryption algorithms you have to know what they do and even then there is no garuntee that you're not introducing new holes.

      If you modify the encryption algorithm then you're probably introducing new holes into it or at the very least you have to distribure those modifications to whomever you want to decrypt it. In essance a type of one time pad. Either you have to create a new encryption algorithm for each message or group of messages that you send or choose one and stick with it. If you constantly change algorithms or modify you have to have some secure way of getting those modifications to whomever wants to decrypt it, which can be difficult. You could simply create or modify an algorithm and not tell anyone what it is except for the recipient but to do that you'd have to know alot about cryptography and hopefully know the benefits of peer review. The people that encrpt DVDs know the benefits of peer review, now, after they released DVDs using CSS. If your modified algorithm is broken you'd probably never know because who would tell you? The guys that are trying to read your encrypted data or the ones that don't want to read your email and don't have access to your modified algorithm?

      The safest thing to do is either use a very long key or learn cryptography develop your own algorithm, get it peer reveiwed and then most likely use a very long key.
      • I doubt that using multiple encryption on one message would lower the strength. I'm not a cryptographer, but if that were the case, the very first thing any attacker would do is encrypt the message again with the same encryption scheme and a random key, which is a relatively cheap operation.
      • Use a long key - yes. Develop your own algorithm - no. Even the GSM telephone people and DVD encryption, which were theoretically developed by trained professionals, were total crockery. GSM had no excuse - the DVD folks could at least argue that the problem they were trying to solve is inherently hard and they were using double protection - a cheapo algorithm and expensive lawyers to run the DVDCSS lawsuits. But the GSM folks were working in well-established territory for which there are straightforward commercial-quality solutions available.
    • Layering is fine, if you know what you're doing and implement it carefully enough to prevent some layers from giving away information about other layers. For instance, you could probably come up with a layering of elliptic-curve public-key encryption and RSA public-key encryption that doesn't violate any of the don't-reuse-stuff rules and is still relatively practical. The nice thing about elliptic curve is that the keys are short - the bad thing is that the math is hairy enough that nobody's quite sure that somebody won't find a way around the difficult part. By contrast, RSA uses simpler and better-explored math (and longer keys), and there's less chance of a major breakthrough making a radical change in the necessary keylength, though Bernstein's machine may turn out to be significant given further exploration.

      The basic question is whether it's worth doing a two-or-three-algorithm solution as opposed to just making your keys longer. Depends a lot on your threat scenarios. Are you worried about the NSA cracking a key during your lifetime? Or are you running a bank and worried about bank robbers forging withdrawals? Or are you worrying about somebody forging your signature on an article on Slashdot? :-)

      It turns out that it's easier to make signature systems use multiple algorithms than encryption systems - all you do is create a tuple of Sigalgo1(message,key1),Sigalgo2(message,key2)... as your signature (and use a representation that doesn't let the Bad Guy change how many bits of the signature string are interpreted as belonging to each algorithm) and there's none of this nesting business required that encryption systems use.

      Computers, as proposed here *are* being used in conjunction with deep analysis - that's why the amount of computation required may have just dropped significantly. Reverse engineering doesn't really apply in this world, unless you're reverse engineering God's excellent job of making factoring difficult large numbers and interesting. :-) If you're doing some obscurity-based approach that requires reverse engineering, you've blown your chance at modern crypto work... Most of the public-key systems work by applying known hard algorithms in ways that let the work required to crack them be computationally infeasible, and it's understood that that's a shifting boundary - usually the crackers blow a dozen or so bits off the strength limits per year (some with faster computers, some with mathematical analysis), but the encryptors can add several hundred bits per year to the practical strength - doubling the number of key bits roughly quadruples the computation required, but you could do 512 bits conveniently enough on an 8086, so 2048 is no problem today, unless you've got packet size limitations which make that annoying, or unless you've got antique code that nobody wants to update for longer keys (particularly if the code is a silicon implementation of a bignum mulitplier), or unless you're running a web site that has to process a large number of connections per second, in which case this costs you actual money.

  • if you were a government agency with $1b to invest in some kind of anti-terrorist encryption breaking scheme, would you invest it in this or would you invest it in quantum computing research?

    would it be worth going for the brute force attack or would it be worth finding a different solution? not to mention how much money you could win and how much cancer you could cure with the idle time.
    • Neither. You'd want to put the billion into a combination of carrot and stick -- humanitarian aid, education, and investments into certain regions, tied to reforms and oversight where possible; plus substantial amounts into human intelligence and law enforcement, since some people aren't going to like you no matter how nice you play.

      When it comes to terrorism, encryption really isn't the main problem. Identifying, isolating and eliminating causes (be they philosophies -- such as a desire for complete theocratic control -- or individual people) is.

  • Pay attention. Security = risk management. (Score:5, Insightful)

    by mib ( 132909 ) <mib@post.com> on Monday March 25, 2002 @08:27PM (#3225708)

    Don't any of you bozos pay attention to prior articles? Security is about risk management. If you have something to protect that is worth $1bn for someone to steal and the only protection you have on it is 1024-bit crypto, you deserve to have it stolen.

    Your homework for today is to (re)read Secrets and Lies. There will be a quiz.

    • It doesn't cost the bad guys a billion dollars to steal your secret. It costs them a billion dollars to steal the secrets of everyone who uses the type of key the machine can crack. Your share might only be worth $10000 and it could conceivably still be worth their effort to buy/build the machine. Then you lose.

      Your argument only makes sense if they have to dedicate their billion dollars to just cracking one key.

    • but if 1024 bit crypto only takes a minute to crack then theoretically during the 3 year life of this 200million to billion dollar machine.
      $2e11 to 1e12 / 3 years / 365 days / 24 hrs /60 minutes

      This means that all of your assets between 124,000 (if machine costs 200 million) and 634,000(for 1 billion) and above are all worthwhile "investments" of this machine's time.

      Thank god I'm poor
    • Don't any of you bozos pay attention to prior articles? Security is about risk management.

      What do you see in the post that is inconsistent with this view? It claims that the cost of breaking 1024 bit keys is lower than previously believed. This means that risks must be reassessed.

      If you have something to protect that is worth $1bn for someone to steal and the only protection you have on it is 1024-bit crypto, you deserve to have it stolen.

      Guarding a $1B asset with a 1024 bit key would be foolish, with or without this finding. (For starters, the enemy doesn't necessarily have to build a cracker, they just have to rent time on one.) But who says we were talking about a $1B asset? Trivially, there exists some scenario in which 1024 bits was a good risk prior to this finding, but is no longer. So this finding is entirely relevant to a risk management approach.

    • Heh. You thought I was buying this to get your secrets. No, that's just the icing on the cake. This baby's for LAN parties. Nothing plays Quake quite like it.

      And there's the occasional corporate secrets to bust into once in a while. Ahhh.

      Did I mention Pac Man?

  • The US government has something like this (Score:4, Informative)

    by WolfWithoutAClause ( 162946 ) on Monday March 25, 2002 @08:29PM (#3225717) Homepage
    The US government recently relaxed export regulation for public key cryptography to make it the same as the domestic restrictions. The reasonable implication that we can take from this is that they have a way to crack that length of key, or they know they can do it, if they really have to.

    Either that, or the American government suddenly have benevolent feelings to the rest of mankind and a minority of their software community. Yeah right.
    • It's been generally suspected that NSA has had the ability to break 512-bit RSA encryption for a while. Breaking 384-bit RSA is old hat, and breaking 512-bit has been doable even before Nicko's group made it easy on their machines, but this IS exponentially hard work - before Bernstein's hypothetical machine was hypothesized, the limit to current practice was believed to be in the low 600s. This suggests that 768-bit keys aren't trustable for more than casual work, but 1024-bit keys are still way fine.

      The NSA has the advantage of occasionally being able to spend a billion dollars on chips or machine design, which says that building something like the EFF's DES $250K cracker was done at NSA long before the public got there (though "long before" has Moore's Law implications...). They also have some good mathematicians focusing on problems like this, not only because they like to crack other governments' codes but also because they need serious estimates of the strengths of the codes they use, but the general opinion in the crypto community is that they're no longer particularly far ahead of the open academic world, and in some ways they're behind because it's hard to get good peer review on secret algorithms, and it's hard to get and keep good mathematicians if you don't let them publish and don't pay them much money either. I don't believe they had the ability to crack 1024-bit RSA or Diffie-Hellman keys before Bernstein's paper came out - but they *do* have Bernstein's paper now :-)

  • Clearing up the deceptive intro (Score:5, Informative)

    by Glorat ( 414139 ) on Monday March 25, 2002 @08:32PM (#3225732)
    1024-bit encryption should no longer be considered pristine

    That intro is deceptive at best and is, well incorrect. Remember DES and other symmetric ciphers that currently use about 128-bit or so encryption are unaffected by this. Certainly, 1024-bit symmetric encryption (your typical secret password encryption) is going to be unbreakable for centuries based on current predictions. The intro should read asymmetric or public key encryption at 1024-bits

    Secondly, the advances being talked about are in factoring large numbers into their prime factors using the Number Field Sieve (NFS). This algorithm is the most advanced known factoring algorithm and if you believe the article improvements show that factoring 1024-bit length primes is doable for 1 billion dollars or so. (It was only a few years ago this kind of cost was attached to building a DES cracking machine... today I could probably crack DES on my uni computers given the software. 1024-bit factoring is only a matter of time before it is easy). However, not all public key schemes rely on the difficulty of prime factoring. Elliptic curves rely on a different hard problem

    Conclusion, the intro should read "1024-bit asymmetric encryption that relies on the difficulty of prime factoring (e.g RSA) should no longer be considered pristine"

  • Arbitrary costing = $1B (Score:5, Funny)

    by Nathdot ( 465087 ) on Monday March 25, 2002 @08:44PM (#3225796)
    I can picture the scenario now:

    <TELEPHONE CORRESPONDANCE>
    SHADY GOVERNMENT OPERATIVE: So how much will this 1024 decryption system cost?
    PIMPLY TEEN HACKER: $1B US dollars to be deposited into my secure off-shore bank account and safe passage to the Maldives.
    SHADY GOVERNMENT OPERATIVE: Excellent. The money is being transferred as we speak. Begin work.
    </TELEPHONE CORRESPONDANCE>

    <PIMPLY TEEN HACKER INTERNAL MONOLOGUE>
    Sweet! I've just charged the US government 1 billion dollars for a beowulf cluster of dreamcasts running home-brew linux.
    </PIMPLY TEEN HACKER INTERNAL MONOLOGUE>

    <SHADY GOVERNMENT OPERATIVE INTERNAL MONOLOGUE>
    Sweet! We will retrieve the 1 billion dollars once we crack the secure off-shore bank account's 1024 bit encryption system
    </SHADY GOVERNMENT OPERATIVE INTERNAL MONOLOGUE>

    :)
  • Bernstein released a proposal that outlines the creation of a machine capable of breaking 1024-bit crypto on the order of minutes or even seconds for the measly cost of ~$1B USD.

    Okay, I've been hiding my idea, but who cares. I'm releasing it now and officialy proposing the creation of a machine capable of breaking 2048-bit crypto on the order of hours or even minutes for the measly cost of ~10B USD.

    I'm currently soliciting offers from several major tech companies to fund this joint venture to be used only in the private sector.

    Please call now.

  • Read the Paper! (Score:5, Informative)

    by gweihir ( 88907 ) on Monday March 25, 2002 @08:58PM (#3225866)
    Actually Bernstein says that he does not expect his factoring device to have any significant speed advantage over other factoring techniques for "short" keys, "short" being significantly more than 1024 bits.

    The reason is that the speed up is asymptotic with a suspected slow convergence.

    But I agree that for security critical application 1024 bits is too short, even if only because there is not enough safety margin.

    Find the paper by D.J. Bernstein here. [cr.yp.to]

  • I have plenty of minutes, but I don't have 1.0e9 $. I want to build a machine for $10,000 that can crack 1024 in 100,000 minutes (about 70 days). Then I could be the first to grab the RSA prize and if I wasn't first at least I'd have a really fast box.

  • Maybe I'm not clear on this but... (Score:3, Insightful)

    by ZiZ ( 564727 ) on Monday March 25, 2002 @09:00PM (#3225881) Homepage
    Doesn't this fall under circumventing encryption, therefore making it illegal to think about under the DMCA? Or is it ok when it's expensive to break things, but not when it's cheap?

  • Hey, I've got a much worse problem to report: Most people don't use encryption!!! Right now, we're all browsing slashdot, our credentials sent in plaintext, our sessions open for anybody to see! Almost everybody sends unencrypted e-mail!

    Rather than freak out about the NSA being able to crack 1024-bit keys, maybe we should be doing more to actually get encryption used by people?

  • Only a billion dollars of the taxpayer's money to read other people's mail? The U.S. government will take 10.

  • Haha fools!!! (Score:4, Funny)

    by NoMoreNicksLeft ( 516230 ) <john.oylerNO@SPAMcomcast.net> on Monday March 25, 2002 @09:13PM (#3225930) Journal
    This is why I use 1025 bits. Suckers.

  • According to an email from Lucky Green

    That key of his seems awfully long. Sure enough, when I pasted it into a text file it was 46 kilobytes!!!

    There must be something else in there besides the 2048-bit key, but what? Is the first part the public key, and the rest the encrypted message?

  • Everyone here uses gpg or equiv for your email right?
    As a member of several mailing list most people do not even have gpg signatures, those that do never upload their public keys.
    Breaking 1024 bit encrytpion isnt that big of a deal for most people.

    I guess they like running naked through public parks.

  • One thing to consider is that rigorous threat assesment is based on CAPABILITY, not INTENT. Clearly it seems that there now many organizations that may have the capability seriously compromise a significant and growing part of the world economy.

  • We are facing some big challenges right now. Due to the crazy growth of computing power (despite the fact that new methods of calculation - factoring large number and stuff are constant being developed) Encryption standard are being obsolete faster than we can adapt to it.

    Think about how long the US government will take to adopt AES.... Same encryption are going to get weaker and weaker as times goes by, we have to adapt to the rate it fades out. But apparently, encryption standards takes time to develop and get accepted. We are very likely going to change standards every 5-10 years. Government agencies, are you coming along?

  • 2048 bit (Score:3, Informative)

    by MWright ( 88261 ) on Monday March 25, 2002 @10:21PM (#3226238)
    Correct me if I'm wrong, but:


    Each bit that you add roughly doubles the amount of time it takes to crack. 2048-bit encryption, although slow, is possible.


    What this means is that, assuming that a 1024-bit key can be factored in 1 second, it would take roughly
    570044753571256946895391042233962688235025678254 15 606695024759372695\
    54661513856010042759935388366 819543382606540822975 572640467047641318\
    57219835840434659197037569423 594829671728507799344 387665269701556798\
    84895284385512012411993557037 643680409952827613949 299430678049923879\
    77103579392323212688873973370
    years to crack 2048 bit encryption. I'm not all that worried.

    • Re:2048 bit (Score:3, Insightful)

      by prakashj79 ( 235807 )
      A brute force decryption attempt would take roughly twice as much time for every extra bit in the key. No naive decryption scheme will work even if the key size is as low as 128 bits.

      The problem has to be tackled at a more fundamental level - maybe by finding an inherent weakness in the algorithm, which can be used to decrypt the message without having to go through all possible key values.
      For example, if a few (plain text, encrypted text) pairs are known, we can search for a pattern, apply the pattern in reverse to an encrypted message, and get back the original plain text message.

    • Re:2048 bit (Score:2, Informative)

      by jessohyes ( 175502 )
      IIRC every 10 bits doubles the amount of work requred to break RSA. The reason for this is there are factoring algorithms which can do better than straight brute force.

      The best general-purpose factoring algorithm today is the Number Field Sieve (NFS) [BLP94] [BLZ94], which runs in time approximately O(e1.9(lnn)1/3(lnlnn)2/3). Previously, the most widely used general-purpose algorithm was the Multiple Polynomial Quadratic Sieve (MPQS) [Sil87], which has running time O(e(lnn)1/2(lnlnn)1/2).

  • Suppose some agency actually did build a machine that could crack 1024-bit RSA. How would they use it? The answer is, they would keep it very secret and use it only on very important stuff---nuclear threats, etc. They would certainly not risk revealing it's existence to crack small cases.
    • You havent thought this through have you. How will they know whether to decrypt a message or not. How would they know to check terrorist (or communist - choose your fake enemy) cells talking about plans?
      Nah they cant risk that, for the children and for national security they will read everyones, they probably allready are.

  • a slightly-less-Amerocentric thought... (Score:3, Insightful)

    by Simon Garlick ( 104721 ) on Monday March 25, 2002 @10:44PM (#3226312)
    How many tyrants and dictators around the world would think NOTHING of squeezing their own countries $1B harder in order to crack the communications of dissidents, opposing political parties, and oppressed ethnic minorities?

    ObDisclaimer: this isn't some pinko commie "FUCK YOU AMERIKKKA!" post... it's just an observation that I haven't yet seen made by another poster in the thread. I see a lot of people talking about the NSA, and breaking into banks, etc etc... but middle-class white male citizens of post-industrial western economies aren't the only people who have good reasons to use crypto, you know?
  • I'll just pay Guido to torture your ass for $10,000. There are other ways of extracting information . . . ironically brute force is an option in both umm professions. . .
    Sort of off topic, but honestly, the investment (for the machine) isn't worth it unless you plan on doing this a lot of times, and if somebody was going to do this on a case by case basis, it would be cheaper to hire one of Pol-pot's henchmen to do the job.

  • Ian Goldberg isn't worried (Score:4, Informative)

    by SiliconEntity ( 448450 ) on Monday March 25, 2002 @11:46PM (#3226546)
    One of the people to whom Lucky Green attributes the calculation that Bernstein's machine is practical is cryptographer Ian Goldberg. Ian is well known in the crypto community and has broken a number of publicly fielded cryptosystems.

    However, in a follow-up post [inet-one.com] to the cypherpunks mailing list, Ian said that he did not agree with the calculations.

    In fact he says that the physical properties of the factoring machine seem "implausible", and that there is no reason to believe that the result applies to "real" key lengths like 1024 bit keys.

  • It is generally regarded that the NSA and the military have technology that is about 20 years, yes 20, ahead of what is publicly known.

    The NSA has the budget to hire the best and brightest mathematicians money can buy. Whose to say that the NSA hasn't know about this for years? Sure, Bernstein could have simply "rediscovered" what the NSA has known for years.

    There have long been rumrors of a $2-3B machine that the NSA has for breaking encryption. Taking time into account, that translates to that $1B machine now.

    The NSA has likely been able to break these keys for years.
    • An interesting point about these theories is that they all assume that the NSA is a competent organisation. There seems to me to be a fair bit of evidence that they are in fact a bunch of self-politicised, bureaucratic, clueless idiots who spend their time and money talking to contractors whose only interest in life is to divest the government of as much money for as little work as possible, usually to a high level of success. 20 years behind sounds more realistic.

      Just a thought.

      TWW

  • 1024-bit RSA is in no danger. Not yet, anyway. (Score:5, Insightful)

    by swillden ( 191260 ) <shawn-ds@willden.org> on Tuesday March 26, 2002 @12:20AM (#3226662) Journal

    Even Bernstein's original paper is clear to point out that while his mathematical results are correct, and that his proposal does allow RSA keys of size n bits to be factored in the time we currently think it takes to crack keys of size n/~3.009, he proved this to be true *only in the asymptotic case*!!

    This means that for very, very large n Bernstein's results are known to hold. His paper is actually a grant proposal requesting funding so that he can spend the next few years finding out if it's possible to apply the same techniques to practical-sized keys. As I understand it, what Bernstein wants to study will still be purely theoretical. He wants to calculate what the savings factor is for smaller keys. The reduction factor for smaller keys may be as large as 3, or it may be smaller but still worthwhile, or it may be negligible.

    Even after Bernstein has done his calculations for smaller keys (which will take years) the results will still be purely theoretical, and there will likely remain a great number of practical challenges in building the rather unique kind of hardware Bernstein is proposing. It's possible that even if the theory holds for smaller keys, building a real machine may still be impractical.

    For more detailed discussion than you're likely to be able to digest, go read sci.crypt.

    From what I've read, I would say that if you have secrets you need to keep for more than 5 years, you might consider using a 2048-bit RSA key, or switching from RSA to ECC.

  • I wish that bum would get back to work and finish Qmail 2.0!!

  • Misleading article (Score:4, Informative)

    by Llanfairpwllgwyngyll ( 81289 ) on Tuesday March 26, 2002 @03:26AM (#3227027) Journal
    I'm afraid that this story is altogether misleading.

    When the paper first came to prominence, yes, it looked worrying.

    However... the speedup factor appears only to apply to LARGE numbers, not necessarily to smaller ones. Exactly how much advantage one gets for smaller ones is unclear.

    Note that this paper is a "research proposal", not a finished item of research. It's a very interesting read, nevertheless :-)

    However, if you're worried then you should be using 2048-bit original-style RSA PGP keys anyway (or 3072 or even 4096 bit new-style RSA keys). You might want to avoid the DH/DSS keys since the signature part cannot exceed 1024 bit....
  • This is an attack on the web of trust. The author is spreading FUD to fool people into revoking their keys. If everybody follows his advice, the web of trust is gone, and it will take quite some time to reconstruct it. In the end, revoking keys based on such unsubstantiated threats will water the meaning of key revocation as a whole.

Slashdot Top Deals

In order to get a loan you must first prove you don't need it.

Close