Please create an account to participate in the Slashdot moderation system

 



Forgot your password?
typodupeerror
Encryption Security

TWIRL: Are 1024-bit RSA Keys Unsafe? 207

This came across the Interesting-People list today: a preliminary draft of a paper, co-authored by Adi Shamir, that proposes new hardware for factoring large numbers. It is claimed that a machine could be built which would be "3-4 orders of magnitude more cost effective than the best previously published designs," and that "the NFS sieving step for 1024-bit RSA keys can be completed in less than a year by a $10M device." For background, here's a primer on key length in symmetric and asymmetric crypto.
This discussion has been archived. No new comments can be posted.

TWIRL: Are 1024-bit RSA Keys Unsafe?

Comments Filter:
  • Good topic (Score:5, Informative)

    by shaklee ( 631847 ) on Saturday January 25, 2003 @12:51PM (#5157411)
    more here: link [networkcomputing.com]
    • by loknor ( 583729 ) on Saturday January 25, 2003 @01:17PM (#5157534) Journal
      I wonder if this is complementary to the hardware-based approach discussed here [slashdot.org]?
      • by akruppa ( 300316 ) on Saturday January 25, 2003 @02:52PM (#5157954) Homepage
        The TWIRL paper refers to Bernstein's "Circuits for integer factoizaion" which was later partially debunked by "Analysis of Bernstein's factoring circuit" by Lenstra, Shamir, Tomlinson and Tromer, however they agreed that mesh-routing for doing the linear algebra step (solving a huge matrix) was an extremely attractive and feasible idea.

        TWIRL appears to be an improvement of the previous TWINKLE hardware, also by Shamir, which proposed using optoelectronics in the sieving step. I don't know if that was ever built.

        TWIRL is both faster and cheaper than TWINKLE, for instance as it uses a common silicon process as opposed to GaAs, and the actual sieving process is more efficient as well. I have only skimmed over the paper so I don't know about details.

        The previous papers were more or less theoretical, but this TWIRL device appears to be perfectly feasible to build today.

        Alex
  • password (Score:2, Funny)

    by Flamesplash ( 469287 )
    SWORDFISH

    Don't go telling anyone.
  • by Anonymous Coward on Saturday January 25, 2003 @12:54PM (#5157422)
    For most things for the near future. It's still plenty to prevent Joe Cracker from intercepting my SSL connection and decrypting it. Sure, a few large groups will have the ability to do it in a "reasonable" time, but, that's probably right anyway. If I have something that's worth $10 million and a year to crack, well, I should probably be encrypting it with a 2048 bit key.
    • by Kaa42 ( 137049 ) on Saturday January 25, 2003 @02:35PM (#5157875) Homepage

      This does have further implications than simply breaking encyption though, concider that much of PKI relies on the same problem (the difficulty of factoring large numbers).

      I did a quick check and atleast Amazon, Ebay and Yahoo all use 1024 bit RSA certificates, by turning my machine to crack those I could impersonate any of those. I also checked the root certificate of Verisign installed in my browser and found it was also a 1024 bit RSA certificate (well 1000 bits actually). Meaning I could be printing valid certificates for anyone, looking like they came from the real deal.

      There is a lot hanging on the difficulty of factoring large numbers.

      • I did a quick check and atleast Amazon, Ebay and Yahoo all use 1024 bit RSA certificates, by turning my machine to crack those I could impersonate any of those.

        Currently, it costs less than 10^6 dollars to install a new root
        certificate in the popular browsers. So it's much cheaper to attack
        the HTTPS PKI this way, in particular since you can impersonate all
        sites at once.
    • by sql*kitten ( 1359 ) on Saturday January 25, 2003 @03:00PM (#5157981)
      If I have something that's worth $10 million and a year to crack, well, I should probably be encrypting it with a 2048 bit key.

      If a piece of information is worth >$10M, then whoever wants it is wasting their time trying to crack it. There are plenty of much cheaper ways. The nice clean technological solution is to bug the owner's keyboard and screen and wait for them to decrypt it themselves, then steal it afterwards. The nasty way is to hire some Mafia or ex-CIA to kidnap the owner's daughter and ransom the information. A fast cracking machine is of mere academic interest, and will remain so until you can do the longest key in common use in a matter of hours.
    • There's a reason why cryptographers talk about 10 and 20 year security. If you have information that is worth $1 million and will still be worth $1 million 10 years ago, it may be in danger. Lets say the adversary waits 5 years and builds one of these machines for only $2 million. Now he can crack one key per year for at least 5 years and more than recover his investment.

      -a
  • Wow. Looks like somebody's winning the $200k after all.
    • Re:Xbox (Score:3, Insightful)

      by damiam ( 409504 )
      Nope - the Xbox key is 2048 bits, would take 2^1024 times longer to crack than a 1024 bir key. Besides, who would build a $10M machine to win a $200K proze?
      • HEY!

        Don't give Michael Robertson any ideas.
      • by epine ( 68316 ) on Saturday January 25, 2003 @03:54PM (#5158286)
        If this guy's math is correct, that moving from 1024 bit keys to 2048 bit keys increases the computational cost of breaking the key by a factor of 2^1024, then this guy must also believe--in some dark corner of his brain--that the first 1024 bits of key also requires 2^1024 operations to crack. I think this fellow needs to sit in a corner and count his way up to 2^1024 before he posts again.

        Unlike the symmetric ciphers, the public key cipher does not have a pure exponential structure. If it did, we'd be using 128 bit keys and that would be more than adequate.

        Let's just pull a sample key strength function out of some dark place. Let S represent the effective public key bit strength.

        S = 1/4 * log2(N) * sqrt(N)

        N=256 S=32
        N=512 S=50
        N=1024 S=80
        N=2048 S=124

        The new discovery modifies this relationship, but since we are all /. lamers we read the initial three words of whichever link we clicked first and immediately jump to one of serveral interpretations:

        1) S = 1/4 * log2(N) * sqrt(N) - 10
        // constant factor improved

        2) S = log2(pi) + e/4 * log2(N) * cuberoot(N)
        // root improved

        3) S = 1/4 * sqrt(N)
        // log2(N) term eliminated

        To confuse matters, it happens that (1) and (3) amount to pretty much the same thing: a rough factor of 1000 in the computational cost of cracking a key.

        orig (1) (2) (3) (4)
        N=256 32 22 36 24 -698
        N=512 50 40 51 41 -442
        N=1024 80 70 70 70 70
        N=2048 124 114 97 113 1094
        N=4096 192 182 132 180 3142
        N=8192 294 284 180 281 7238

        I didn't mention column (4). That would be the hypothesis of the post I'm responding to, where S is linear in N with an origin in the vicinity of 2^70 (a high speed computer running for one year) for N=1024.

        In a perfect world all the /. posters in category (4) would get jobs as microwave oven repair persons. Then everyone would become a lot more cautious about their dialectic coefficients.
    • Re:Xbox (Score:5, Informative)

      by Zeinfeld ( 263942 ) on Saturday January 25, 2003 @01:22PM (#5157565) Homepage
      the NFS sieving step for 1024-bit RSA keys can be completed in less than a year by a $10M device

      The NFS sieve step is only half the problem, you still have to invert a huge matrix and that requires a closely coupled machine.

      Adi has been describing machines of this type for years, he proposed twinkle a while back. The big problem is that only one half of the problem has a trivial parallelism.

      OK there is a tradeoff between the sieve stage and the matrix stage. But it is not that helpfull. Basically to halve your work at the matrix stage you have to increase your sieving at least four-fold. This does not get you too far since the sieve stage is still pretty stiff.

      Wow. Looks like somebody's winning the $200k after all

      Not likely since the XBox key is 2048 bits, as are most of the major keys in use. The competent CAs plan about 10 years in advance. There are 2048 bit roots embedded in the browsers that can be used as soon as there is a need.

      • Re:Xbox (Score:5, Interesting)

        by akruppa ( 300316 ) on Saturday January 25, 2003 @02:20PM (#5157810) Homepage
        The NFS sieve step is only half the problem, you still have to invert a huge matrix and that requires a closely coupled machine.

        The TWIRL paper describes all that. They propose using a mesh-routing algorithm for doing the matrix job, as described in the paper "Analysis of Bernstein's factorization circuit" by Lenstra, Shamir, Tomlinson and Tromer, which they estimate can be built to solve a matrix for a 1024 bit GNFS factorization for only $5000. This is a somewhat optimistic estimate, basically they have to get a 30cm custom designed silicon waver produced which will cost a bunch more than $5000 for a one-off job, but the design is still perfectly feasible.

        In the new paper they describe how the previous TWINKLE sieving hardware can be improved to be both faster and cheaper, reducing the estimated cost to do the sieving for a 1024 bit GNFS factorizaion in a year to only $10M. This is amazing.

        Alex
        • Re:Xbox (Score:3, Insightful)

          by Zeinfeld ( 263942 )
          The TWIRL paper describes all that. They propose using a mesh-routing algorithm for doing the matrix job, as described in the paper "Analysis of Bernstein's factorization circuit" by Lenstra, Shamir, Tomlinson and Tromer, which they estimate can be built to solve a matrix for a 1024 bit GNFS factorization for only $5000.

          Yeah, just got to that bit, I am suprised that that paper had not received more comment since that is the step that has been limitting.

          I still think that Adi significantly underestimates the costs. The thing that made deep crack practical was that it completed the run in a pretty short length of time (days). So the system did not require a lot of extra engineering to cope with unreliable processors etc.

          I don't think we are going to see this built for at least five years or so. Of course others might build it and not let on. And even then Deep crack was built to prove a political point, not just for the cryptographic fun of it.

          Even so, there is no particular reason to insist on continuing to use 1024 bit keys at this stage. The 2048 bit roots have been distributed for some time. Most computer systems are now sufficiently fast that the longer keys can be used without unacceptable delays.

  • by Lord Bitman ( 95493 ) on Saturday January 25, 2003 @12:57PM (#5157441) Homepage
    A $10,000,000 machine dedicated to breaking into a single encrypted communication for a full year will be able to break it! This makes encryption completely worthless!
    • Re:Oh no! A year! (Score:5, Insightful)

      by DarkMan ( 32280 ) on Saturday January 25, 2003 @01:05PM (#5157483) Journal
      Unless you use a key only once, (possible, but definitly an odd way to do it), then for their $10M and a year, they get _all_ of your encrypted communications, and the ability to pretend to be you, online.

      They say disceting a joke is like disecting a frog: No one really enjoys it, and at the end you have a dead frog.

      Sorry for killing your frog.
      • Re:Oh no! A year! (Score:4, Interesting)

        by waytoomuchcoffee ( 263275 ) on Saturday January 25, 2003 @01:18PM (#5157539)
        they get... the ability to pretend to be you, online.

        Well, those people who were too stupid not to create a revocation certificate, at least.
        • Well, those people who were too stupid not to create a revocation certificate, at least.

          That's right. As soon as the folks who've been quietly intercepting you communications phone you up and say "Hi, we cracked your RSA key last year, and have been reading your encrypted traffic ever since! Have a nice day!", you should release your revocation certificate.

          Kind of like how in WWII Germany realized Enigma had been cracked, and promptly replaced all their Enigma machines with newer models, allowing them to continue to disrupt the Allies' atlantic supply lines and win the war.

          </sarcasm>

      • $10M?! holy sh!t (Score:3, Insightful)

        by buzban ( 227721 )

        good point, but still, $10 million dollars to pretend to be me? thinking economies-of-scale here, on that $10M machine, and assuming (perhaps wrongly) similarities between me and other users...
        I estimate the owner of that machine will need to be able to pretend to be about 10,000 people like me to make that investment worthwhile.
        One has to wonder at whom a $10M encryption-breaking machine would be targeted...almost assuredly not to any old user, probably to someone with something worth having (stealing, duplicating, masquerading, etc.) And it's *these* folks, I think, that should be concerned most about their choice of technology and cypher.
        doesn't hurt to recheck your own priorities, but speaking for myself i can assure you that my identity is worth much less than the cost of this machine. ;0
      • by yomegaman ( 516565 ) on Saturday January 25, 2003 @02:46PM (#5157927)
        I'll sell anyone who wants them all of my passwords and keys for only $5 million. Just think, 50% off and no waiting!
      • Unless you use a key only once, (possible, but definitly an odd way to do it)

        Not at all - have a search for ephemeral keys. Not applicable to RSA (usually too slow), but can be used with Elgamal very easily/quickly.

    • A $10,000,000 machine dedicated to breaking into a single encrypted communication for a full year will be able to break it! This makes encryption completely worthless!

      That should read "...for a full year *might* be able to break it", assuming he's right. Hasn't actually been done yet.

      In Soviet Russia, encryption breaks *people*.
    • A $10,000,000 machine dedicated to breaking into a single encrypted communication for a full year will be able to break it! This makes encryption completely worthless!

      Uhh, dude, it's not so long ago that $10M bought you about as much CPU power as you get in a $10 pocket calculator today. Fortunately, for each additional bit, it gets twice as had to crack. Eventually 8192-bit will be the standard for a while, then we'll take it from there.
      • Eventually 8192-bit will be the standard for a while, then we'll take it from there.

        Unlikely. Assume Moore's law accellerates significantly, and computing power quadruples every year. Furthermore, assume a couple of major technological breakthroughs increase it by two or three orders of magnitude in the next 10 years. Even with these advances, it would still take your $10M machine longer than the lifetime of the universe to crack 2048 bits using brute force with today's algorithms. So while the extremely paranoid might go to say, 2560 bits, the chances of the world in general going past 2048 bits is pretty slim. Either some new technique, be it quantum computing, or a non-exponential time factoring algorithm will make key length irrelevant, or 2048 bits will be enough effectively for ever.

  • by Dr. Photo ( 640363 ) on Saturday January 25, 2003 @12:58PM (#5157444) Journal
    If you have sensitive information, you want to encrypt it based on what you think will be difficult to crack years from now, not just today. Otherwise, interested third parties can simply store away an intercepted transmission until it becomes technologically feasible to crack it.
  • One Question (Score:5, Insightful)

    by El Pollo Loco ( 562236 ) on Saturday January 25, 2003 @12:59PM (#5157450)
    Who has data that needs to be so secure that their competitors spending 10 million dollars and a year of their time to do it is a problem? My only thoughts were of governemnt/military/big corps, but couldn't all of them use longer keys?
    • by Anonymous Coward
      Coca-Cola!
    • Well, lets see:
      NSA, CIA, FBI + other similar intelligence agencies in the other 95% of the world. And then there's other valuable government databases, bank systems. And maybe various mafia organisations, definitly columbian drug cartels (who're said to have one of the most advanced computer networks.) And then there's Saddam Hussein, North Korea, the US government. And all those I've forgotten.

      (One might also say that the RIAA, MPAA and BSA believe they have those kind of enemies.)
    • Re:One Question (Score:3, Insightful)

      by sql*kitten ( 1359 )
      Who has data that needs to be so secure that their competitors spending 10 million dollars and a year of their time to do it is a problem? My only thoughts were of governemnt/military/big corps, but couldn't all of them use longer keys?

      If the NSA really want what you've got, remember they've got the root password to the Constitution. Fancy spending the rest of your life in Guantanamo Bay? No? Then hand over your passphrase like a good Citizen. 2003 encryption is no match for centuries-old intimidation. I can't see that changing anytime soon.
  • So? (Score:1, Insightful)

    by Anonymous Coward
    It is claimed that a machine could be built which would be "3-4 orders of magnitude more cost effective than the best previously published designs."

    Even if you read "3-4" to mean 5 orders of magnitude, that means that the factoring cost is reduced by a factor of 100,000.

    In other words, a 1024-bit key will only be as safe, after this cost-reduction, as a 1007-bit key is today for the same amount of money.

    I'm not worried.
    • Re:So? (Score:5, Informative)

      by jamie ( 78724 ) <jamie@slashdot.org> on Saturday January 25, 2003 @01:09PM (#5157500) Journal
      "Even if you read "3-4" to mean 5 orders of magnitude, that means that the factoring cost is reduced by a factor of 100,000. In other words, a 1024-bit key will only be as safe, after this cost-reduction, as a 1007-bit key is today for the same amount of money."

      You didn't read the primer [sans.org] we linked to :)

      An increase in 3 bits in symmetric keys corresponds to an increase of about 160 bits at this size of asymmetric key. As I understand it (and this is probably an oversimplification), this is because while you can pick any symmetric key you want, your choice of asymmetric key is limited to prime numbers.

      So a change of 4 orders of magnitude in cost-effectiveness would be about the same as shaving 13 bits off a symmetric key. But if the table credited to Lenstra and Verheul is correct, that would correspond to reducing a 1028-bit asymmetric key's effectiveness to 488 bits.

      I think.

      • Re:So? (Score:5, Informative)

        by acidblood ( 247709 ) <decio@@@decpp...net> on Sunday January 26, 2003 @07:45AM (#5161216) Homepage
        An increase in 3 bits in symmetric keys corresponds to an increase of about 160 bits at this size of asymmetric key. As I understand it (and this is probably an oversimplification), this is because while you can pick any symmetric key you want, your choice of asymmetric key is limited to prime numbers.

        Prime numbers can only account for so much -- their distribution is asymptotic to n/(ln n) by the PNT. So at this size only 1 out of ln 2^1024 = 710 numbers is prime on average. That would account for ~9.5 bits shaved on RSA around this range for each symmetric key bit shaved.

        Actually most of this can be credited to much faster algorithms for number-theoretic problems (like the subexponential NFS for factoring, being discussed on this article) whereas usually the best known method for cracking a symmetric-key algorithm is brute force, which is of course exponential.
    • Re:So? (Score:3, Interesting)

      by KDan ( 90353 )
      Unless of course he's talking about reducing the cost, rather than reducing the difficulty. And from the wording, it sounds more like the cost is being reduced by 3-4 orders of magnitude. So from $10mil to $10k-$1k is a pretty good step. Would mean that for the same price they could crack 1000-10000 more keys per unit time.

      Daniel
  • by 1984 ( 56406 ) on Saturday January 25, 2003 @01:03PM (#5157471)

    As always, the tinfoil hat crowd will point out that a machine with such capabilities may already have been constructed and be in use. The NSA, perhaps. And they might be right.

    Let's say the NSA has one. Let's say it's actually really good and 100x faster than the system proposed by Shamir and Tromer. That means it can plough through 100 1024-bit RSA keys per year. There are about 280 million people in the US (give or take). Let's say 0.3% of them encrypt using 1024-bit RSA (or below). That gives us about a million people. Let's say each one of those only has a single piece of important data. That's a million pieces of data, and you can crack a hundred of them. Be afraid?

    It might be useful if you can (big if) decide exactly what data to go after, and it happens to be RSA = 1024 bit (or anything else equally amenable to being factored using NFS). But if it's 2048-bit RSA, this thing won't have a shot -- it's not fancy knew math that "breaks" RSA, it's a faster implementation of an existing technique. And it's probably not the cue for Joe Public to get paranoid.


    • Well, the standard tinfoil hat answer (and not a bad one) is that we don't really know what the NSA's capabilities are. In the past they have been large leaps ahead of the public in cryptography and cryptoanalysis. If you're really worried about the NSA wanting to see your data, you have to assume that they may have new mathematical methods available to them that we are unaware of, which is a whole different ballgame than just fast brute force hardware. There's a remote possibility that the NSA already solved the factoring problem in O(3N) time or something like that. Or that they maybe didnt figure out factoring in general, but have found a flaw in the specifics of how it's used in RSA with the modulus and all. Or that they've already got quantum computing up and running well enough to insta-factor with it. These are all remote possibilities, especially considering that in the newer more open era the gap has probably closed a bit between the NSA and the public - but if someone were actually worried about NSA snooping, they have to consider such things. They are (and have been for a long time) the world's largest single employer of mathematicians after all.

      Of course in a practical sense, there's no point worrying about the technical stuff. If the NSA wants your data, you better have some better way of hiding it that cryptography. They're gonna come after you and your family with a rubber hose for it. The best bet is probably knowing some secret they don't want the public to know, and setting up a dead man switch to release that information. Then you might have a playing field on which to negotiate the privacy of your data with them.
  • oh dear....... (Score:2, Insightful)

    by Anonymous Coward
    I'm so scared, they only need $10M of hardware running for a year to be able to steal the $3,000 I have stashed at the back....

    Seriously, everybody knows that any key length can be broken given enough time/hardware power. Then the keys will get larger, the hardware will get faster, rinse, repeat....

    If someone can make a device as fast as they claim, then those people that have information/assets/whatever worth more than a $10M machine, should begin using larger keys. As simple as that. No big deal really
  • Yes, but... (Score:4, Funny)

    by Elbereth ( 58257 ) on Saturday January 25, 2003 @01:05PM (#5157484) Journal
    Can it factor large primes in mere seconds? I've designed a processor that can! I'm just looking for investors now...
  • Spend enough money and just about anything can be solved.
  • by Anonymous Coward on Saturday January 25, 2003 @01:11PM (#5157503)
    1024 bit RSA composites have been considered the low end of the secure sizes, for a while now.

    As always, as hardware and techniques get better, this needs to be revised - it seems likely that a large threat model (intelligence agency or very large corporation with money to waste on pointless cryptanalysis), today, could factor a 1024-bit key within a year. However, the resources necessary to smash a 1024 bit key are so great, in comparison with the cost of key theft/keylogger attacks, you'd have to be nuts to actually factor them. If someone wants your key that badly, they'll bug your keyboard, catch the passphrase and steal it, and that attack works against any keysize.

    Planning ahead, though, 1024-bit RSA keys are unsuitable for use in new applications, and moving to 1536 or, if you can, 2048 or greater is strongly suggested.

    Elgamal et al are roughly as complex as RSA (slightly more resistant to attacks, it seems). You shouldn't be using new Elgamal keys of 1024 bits or less either.

    This does present one clear problem: the NSA's Digital Signature Algorithm (DSA - used commonly by PGP 5.x and up and GnuPG, as well as many other diverse cryptosystems) currently only specifies a 1024-bit modulus (for use with the SHA-1 160-bit hash). Larger modulus sizes would need larger standard hashes, and although these have now been developed (SHA-256, SHA-384, and SHA-512, collectively and informally known as SHA-2), the NSA have not yet blessed an extended DSA specification, making them useless to DSA for the time being (as extended sizes apparently violate the standard, and what generators to use with larger sizes?).

    So it may, with a large threat model, millions of dollars and a year, be possible to find someone's PGP signing key and forge signatures. Whether or not this will be worth it is another matter (attacking the threat model like this would not stick very well, as if they ever see a forged signature of theirs, they'll revoke their key and shout loudly about it).

    It is noteworthy, in the PGP field, that the 'new-style' RSA v4 keys, which can be used by GnuPG, PGP 6.5.8ckt08 and PGP 7.x and 8.x, allow the use of larger signature keys. No-one is going to break a 4096/4096 RSA new-style PGP key using SHA-512 as the hash anytime soon, unless someone is hiding a magic quantum computer.

    If you need keys for secure communications, and speed may be somewhat critical (SSH or SSL come to mind), go 2048 bit or 1536 bit if you're in urgent need of space. If you're using them for anything else, especially long-term keys, think about 3072 or 4096 bits (you never know what the future holds, but you can be damn sure computers will keep getting faster).
    • If you need keys for secure communications, and speed may be somewhat critical (SSH or SSL come to mind), go 2048 bit or 1536....

      Almost irrelevant. ssh and ssl only use rsa to send a symmetric key which is used to encrypt the rest of the data. In the case of ssh, that key is changed periodically; it may be the case with ssl too. Using a smaller keysize will only speed up connection initiation - useful, surely, but not critical.

  • make a bigger key (Score:5, Insightful)

    by jdkane ( 588293 ) on Saturday January 25, 2003 @01:12PM (#5157509)
    NFS sieving step for 1024-bit RSA keys can be completed in less than a year by a $10M device

    So at this moment in time they *may* have the ability to crack a few hundred keys in one person's lifetime. (Remember, the machine is theoretical). That's a lot of money and time to crack relatively few keys, using a machine that doesn't exist. Maybe it would be worthwhile to use against AlQueda. As for the rest of us here on /., we probably don't have much to worry about. If you are worried then make a 2048-bit key for yourself. Case closed ... until a few years down the road. Then do the same again.

    Wouldn't it be nice if instead of focusing on the problem ("1024 is unsafe!"/"the government might find the password to my hotmail account!") we focused on the solution ("make a bigger key!"/"don't inherently trust technology to be the final solution").

    We can quip about 1024 being unsecure just like a few years ago we quiped about 512 being unsecure. That's why the key lengths keep going up. Any encryption is a preventative measure, not an absolute.

    So Are 1024-bit RSA Keys Unsafe.
    Right now, the answer would be No, they are not unsafe, relatively.

    • by sql*kitten ( 1359 )
      Maybe it would be worthwhile to use against AlQueda.

      No, because al-Queda rely on oral communication between people who's grandparents, parents and children are friends. That's why no-one knows what they're up to, and why it's so difficult to infiltrate them. The US govt can throw almost unlimited resources at this, but there is no technological solution this time.
      • While I do agree with you (and most things you post), I think cloning breakthroughs could lead to some nice impersonation that could help. Granted, the timeframe on this wouldnt be any time soon enough to be relevant, but technology is technology.
  • by Anonymous Coward on Saturday January 25, 2003 @01:14PM (#5157517)
    Of course they are. I just read an article the other day on how to file them down and make a master key out of them.

    Slashdot and their damn dupes ;)
  • by QEDog ( 610238 ) on Saturday January 25, 2003 @01:26PM (#5157586)
    A lot of people here are missing the point of the paper. Cryptography is a continuous race. You assume how many years you want your info to be safe. You invest based on that. If someone proves that your assumption was wrong, your information is in danger automatically, and you lost the race. Some information can still be sensitive years after it was written, so this is a big concern.

    Imagine an evil (good?) corporation that decided to crack the encryption for a message sent with the Coca Cola recipe, and that it was only a 1024.

  • Define "Safe" (Score:4, Insightful)

    by peterpi ( 585134 ) on Saturday January 25, 2003 @01:32PM (#5157612)
    "TWIRL: Are 1024-bit RSA Keys Unsafe?"

    Yes. With enough computing power, any key size is unsafe.

    The real question is; are they safe enough?

  • by jdkane ( 588293 ) on Saturday January 25, 2003 @01:35PM (#5157624)
    If anybody thinks anything is totally secured in this world, then they are deluded.

    By the time "they" get your credit card number by breaking the bytes of an SSL connection that you used to pay online with one year ago, one of these will probably have happened:

    - Robbers broke into your house when you weren't home and stole your home entertainment system (you say you have insurance on your household items; well, your bank also insures your credit card against fraud).
    - or, your car may have been stolen (oh no! while I was worrying about 1024-bit keys being unsecure my car was stolen!)
    - or, Somebody kidnapped you and held a gun to your head until you gave them your PIN #. (A gun is much cheaper than a 10M computer).
    - or, you lost your credit card and somebody bought something on it, or somebody got your number from a carbon copy slip in the garbage can
    - or, you went bankrupt so "they" can have as much access to that account as "they" want
    - etc. etc.

    I honestly don't think that the common person has much to worry about if 1024 encryption is hard to crack right now. If so, then just use a lengthier key, like 2048. Problem salve

  • by SiliconEntity ( 448450 ) on Saturday January 25, 2003 @01:44PM (#5157665)
    A lot of you are missing the point. $10 million isn't that much. They could build 100 such machines for a billion dollars, not an unreasonable sum for the NSA, especially if it is spread out over a few years.

    Furthermore, technology continues to improve. Moore's law will speed up the chips, and this design is probably not the last word. There could be significant improvements ahead.
    • A lot of you are missing the point. $10 million isn't that much. They could build 100 such machines for a billion dollars, not an unreasonable sum for the NSA, especially if it is spread out over a few years.

      They may not even have to. They'd use their own fab [212.100.234.54] which will probably give them a better deal than that.

      Alex
    • Clifford Stoll in "cuckoos egg" writes about a computer room full of rows of Crays "as far as the eye can see" at the NSA.

      I've heard other people describe this room using a football field as unit of reference (something like 1/2 a football field size).

      Lastly, publicly traded companies are legally allowed to hide their sales to top secret organizations. Remember this the next time you wonder why would SGI ever purchase and continue production of Cray's when they are only selling, supposedlty 5 a year...

    • A lot of you are missing the point. $10 million isn't that much. They could build 100 such machines for a billion dollars, not an unreasonable sum for the NSA, especially if it is spread out over a few years.
      We aren't missing the point, you are. Encryption isn't perfect. It's good enough to discourage casual snoopers, and even some serious ones. But anyone who really wants to get at that decrypted information will be able to, no matter what keysize you use. If NSA thinks my email is important to national security, why wouldn't they just send over some guy to beat the shit out of me until I told them my passwords? I doubt that sort of thing costs them $10 million. Hell, even if they decide not to do that, for the low, low price of $1 million, I will voluntarily disclose all my personal information to whoever wants it.

      It's pretty much analagous to all the various anti-theft things you can put on your car, ranging from a keyed ignition to a fuel pump cutoff. Anyone who really wants to steal your car is going to do it. The only purpose to all this anti-theft garbage is to make your car less convenient to steal than the cars next to it in the parking lot.

      The time to start worrying about this sort of thing is when those computers cost $5000 and everybody can buy one and use it for evil.

  • by SteWhite ( 212909 ) on Saturday January 25, 2003 @02:06PM (#5157759)
    A lot of talk about breaking encryption comes from the perspective of
    the private key still being private. How secure is something like PGP
    if the attacker has the private key but not the password?

    Assuming maximum PGP 6.5.8 security of 4096 bit keys, with a good
    strong passphrase (70+ chars, including non-alphanumeric), how long
    would it take to break? Any reasonably accurate figures would be
    appreciated.
    • Not very long, since your passphrase is probably just a text sentence type string, and language has extremely low entropy. It's vulnerable to an elaborate dictionary attack.
      • Schneier, page 234:

        "The rate of normal English takes various values between 1.0 bits per letter and 1.5 bits per letter... [Shannon] indicated a rate of 2.3 bits/letter for 8-bit chunks, but the rate drops to between 1.3 and 1.5 for 16-letter chunks. Thomas Cover used a gambling estimating technique and found an entropy of 1.3 bits/character."

        I like to use 1.5 for my ballpark figures, since it makes the math easier; but assuming the most conservative value of 1.3, that still means a 70-character passphrase in plain English has 91 bits of entropy.

        That's a freaking lot, incidentally.

        How long did it take the RC5-64 challenge to succeed? Multiply that by 128 million. That's how long it would take them, on average, to break a 91-bit passphrase.

        Would you care to revise your statement about not very long, since your passphrase is probably just a text sentence type string, and language has extremely low entropy ... it's vulnerable to an elaborate dictionary attack?
    • Well how do you think the pass phrase factors in to that equation? Seriously. Do the math for El Gamal or RSA, I don't see a "passphrase" component.

      They use a symmetric cipher to encrypt your private key on disk. Depending on which cipher is used, likey IDEA, AES or 3DES. You're looking at a 112, 128, 168, 192, or 256bit symmetric block cipher and the effort it takes to break that. RFC 2440 states that a hash is applied to your pass phrase to expand it or reduce it to the proper key space (your 70character phrase doesn't buy you any more than a 32character phrase,) MD5 or SHA is probably used and then a cipher which isn't specified. However MD5 and IDEA are chosen for backwards compatibility, implicitely.

      So how long does it take to decrypt an IDEA encrypted message? 64bit blocks, 128bit key space. A lot less time than it does to factor a 4096bit Blum integer.

    • PGP 6.5.8 uses CAST5-128 to encrypt the private key, and uses SHA-160 to redact the passphrase into a cryptographic key; the last 32 bits are discarded.

      According to Shannon, Schneier, etc., English has about 1.5 bits of entropy per glyph. You'd be looking at much higher entropy per glyph if your passphrase was random, had alphanumerics, etc.--still, for simplicity's sake, let's take the 1.5 bits per glyph as canonical.

      70 * 1.5 = 105 bits of entropy

      I would be thirty-one flavors of not worried.
    • 70+ characters is a bit insane. A huge bit insane.

      26 lowercase letters
      26 uppercase letters
      10 digits
      32 other characters
      94 total.

      My longest passwords are under 20 characters long, but even if I told you that a given password were exactly 12 characters long, you would have 94^12 = 4.75x10^23 possible passwords. Checking a trillion passwords per second, you'd burn through the problem in a mere 15,000 years.

      There's no need for a 70+ character password. Security is only as strong as the weakest link, and if the password is stronger than the encryption, you're golden.
    • If you're only using your passphrase for one key, then an attacker who has your private key doesn't need your passphrase. If you're using your passphrase for more than one key, then it makes a lot more difference how they got your private key... A more likely threat is that somebody got your private keyring file, which is encrypted, and they're running pgpcrack to see if you've got a wimpy passphrase so they can get your private keys. If your passphrase is in /usr/dict/words it won't take them long to crack it; if you've picked a really high-entropy passphrase that people who know lots of information about you aren't likely to guess then you're fine (unless they've got continuing access to your machine and can watch you type in your passphrase, in which case you're toast anyway...)
  • decoy keys (Score:2, Interesting)

    by theguru ( 70699 )
    Why not just send and store a lot of decoy payloads encrypted with decoy keys of the same strength as the legit key? It takes a year and $10M to decrypt a 1024 key? Fine. For every valid key I use, I'll pass around 5-10 random messages with throwaway keys.
  • Yeah kids, we did this here [slashdot.org] and here [slashdot.org].
  • The EFF, of course, has a hardware DES cracker. [eff.org] It cost about $250,000. They'd though they'd get some occasional business from companies who'd lost DES keys and needed them cracked, but that didn't seem to happen.
  • size matters.
  • I heard about TWINKLE in a class actually. Sounds kind of bizarre. I wonder if the NSA has a giant facility with a $10B version of this thing that factors all of our primes.

    Anyways, RSA NEVER was secure. It was based on a problem which was *practically* hard. In practice, it seemed pretty hard, but there never was any mathematical proof that it was hard (i.e it is NOT NP-complete). Factoring large composites into their prime factors is hard at the moment, but it is very likely there will be a time when you can punch a function on your simple scientific calculator and easily factor billion digit composites. TWINKLE is just proof that there *ARE* fast ways to factor composites into their primes.

    What is the solution? We should have never used it to begin with. Perhaps the NSA pushed it behind the scenes because they knew a way to factor large primes would eventually come. Maybe they already have a better method than TWINKLE. Regardless, NSA isn't secure. We should have used a system based on an actual NP-complete problem, such as the decoding problem. The McEliese cryptosystem seems to be secure and it is based on a NP-complete problem, so the only way to break it is to steal the other person's key or brute force it.
    • "TWINKLE is just proof that there *ARE* fast ways to factor composites into their primes."

      TWINKLE is no such proof. TWINKLE was estimated to be able to crack 512-bit, maybe 768-bit keys but even Adi said it wouldn't scale to 1,204-bit keys....I can break 5 bit RSA keys in my head, that doesn't make RSA insecure, it just means that parameters need careful selection.

      "The McEliese cryptosystem seems to be secure and it is based on a NP-complete problem"

      I assume you mean McEliece? Your confusing NP-completeness with strength - look at the number of PK ciphers built upon NP-Complete problems (e.g. the knapsack ciphers etc) and you'll soon see that NP-Complete doesn't secure automatically imply secure

      People need to, still, chose their algorithms and parameters carefully. Use DH or Elgamal with 2,048-bit keys for strategic data.

  • NSA (Score:2, Funny)

    by jakobk ( 553240 )
    I bet NSA have had this for years.
  • Not getting it... (Score:4, Informative)

    by Anonymous Coward on Saturday January 25, 2003 @04:07PM (#5158357)
    The point of this paper is NOT that 1024-bit keys are "unsafe" for some definition of "unsafe".

    This is a brilliant refinement on a brilliant idea. A few years back, Shamir published "TWINKLE", a factoring technology that used optoelectronics to great effect-- rather than using a (slow) software loop to test the smoothness of certain numbers, TWINKLE used LEDs of varying brightness to represent factors of a given number-- the brighter the combined output of the LCDs, the smoother the number.

    This is a VERY intelligent refinement on the idea; the original TWINKLE had to use GaAs wafers and (partially due to the optical part of the design) was going to be VERY difficult to manufacture. This new device uses only electronic components, but it essentially parallelizes the original TWINKLE idea.

    The implications are enormous. First of all, 512-bit keys are officially dead-- $10000 and 10 minutes may be a bit optimistic, but it's surely no more than half an hour with this device. And, yes, there ARE people and organizations still using 512-bit keys (stupid people and organizations, yes, but they exist).

    Second of all, this approach scales incredibly well. A 1024-bit number is $10 million and one year. But because of its reliance on cheap silicon parts, you can bet that the price and speed will get better in accordance with Moore's law.

    As well, because the time/cost relationship is essentially linear, it becomes easier to model threats (read Schneier's "Attack Landscapes" paper, this will give you an idea of what I'm saying).

    Plus, the paper is just plain cool. Shamir is a bright guy (he's not just the 'S' in RSA, you know-- he co-invented differential cryptanalysis with Eli Biham, and he has done some amazing work with hash functions and block cipher cryptanalysis, not to mention TWINKLE and TWIRL), and when he publishes a paper, people pay attention.
  • URL for updates (Score:5, Informative)

    by Insount ( 11174 ) <slashdot2eran@nOspaM.tromer.org> on Saturday January 25, 2003 @04:19PM (#5158417) Homepage
    I'm a co-author of the paper.

    The version currently circulating is indeed a draft. The final version, when available, will be placed at my homepage [weizmann.ac.il], and specifically here [weizmann.ac.il].

    -- Eran Tromer

  • by diggitzz ( 615742 ) <diggitzNO@SPAMgmail.com> on Saturday January 25, 2003 @04:55PM (#5158580) Homepage
    As pointed out in David Deutsche's The Fabric of Reality [qubit.org], no encryption based on large primes is ever indefinitely secure.

    While the factorization of large prime numbers is currently an intractable task, quantum computing is very likely to make it as tractable as multiplication.

    For instance, Shor's Algorithm [att.com], first discovered in 1994, has already been implemented to factor the number 15 -- to 3 and 5 with 80% accuracy. (If anyone knows what it got the other 20% of the time, I'm interested!)

    Now certainly 15 isn't comparable to a 1024-bit RSA key, but it's only a start for quantum computers. Using entanglement and interference, one can have very large primes factored in a matter of minutes! All we have left to do is actually build a device that does it ... and currently decoherence is the largest obstacle to overcome.

    So, if you really want information to be secure, and remain secure indefinitely, a better method of encryption which does not rely on the factorization of large primes needs to be implemented.

    Peter Shor even wrote a poem [att.com] about it. =P

    -------
    If you don't take responsibility
    for what goes into your mind ...
    Someone Else Will!
  • Remember, this story applies only when the attacker knows the method of encryption, and there is only one method of encryption.
  • Quantum computing (Score:3, Informative)

    by nkrgovic ( 311833 ) on Saturday January 25, 2003 @07:41PM (#5159352)
    All this being said, we are ignoring the fact tah it's only valid for traditional computing. With quantum machines the situation differs completely.

    As said here [rsasecurity.com] by RSA Labs : " It has been proven that a quantum computer will be able to factor and compute discrete logarithms in polynomial time." . What this means is that on a quantum machine all rsa encrypted data can be decripted in a short time...

    Now, as far as we know, no one has made a successfull, large enough, quantum machine, but...

    On the other hand, eliptical curves are still inpenetrable even with quantum computer. I can't wait for the new version of OpenSSL, with the eliptical algorithams built in (as covered on /. ) . I know I'll be moving all my encription to eliptical, just in case... :)) And, while at it, I'll go with a very long key... 256bit's, or even 1024...

  • by sakeneko ( 447402 ) on Saturday January 25, 2003 @07:50PM (#5159386) Homepage Journal

    Nobody who knows anything about crypto or public keys ever claimed that any key length is safe from cracking forever. Years ago someone cracked a PGP key with a length of, as I recall, 384 bits -- PGP is crackable.

    What people have claimed is, and always has been, that public key cryptography can keep your secrets secret for a certain period of time before computing power improves sufficiently to crack them.

    Now Adi Shamir (the "S" in RSA, by the way) is estimating that a computer capable of cracking a 1024-bit PGP key in less than a year could be built. Not *has been* built -- *could be*, and that's a key of half or less the length of the default keys produced by most of today's PGP implementations.

    I think we have some chicken littles around here. ;>

    What a PGP user must do is pick a key of sufficient complexity that it won't be easily crackable for longer than the user needs to keep their credit card numbers, or other private information, private. PGP is still quite capable of doing that, and (I suspect) will be for quite a few more years.

  • by red-beard's ( 639520 ) on Saturday January 25, 2003 @09:18PM (#5159691)
    Imagine a beowulf cluster of these . Hmmmm you could crack God's answering machine remote . Think of the messages "Hello God this is Satan you think i could be someone else besides Bill Gates for awhile . I hate being so damn nerdy. Oh an i was thinking we could give the DOJ the plague or maybe just the antitrust section . Gotta get back to my new version of windows for life support machines ....muhahahaha "
  • oversight in paper (Score:2, Informative)

    by bunnie ( 536976 )
    One thing that is not mentioned in the paper, as far as I can see, is that the NRE cost of making a 0.13u ASIC is almost a half million dollars these days, I think. This doesn't count the other two or three million dollars for cadence licenses, backend tools, verification, server farms, and engineers necessary to produce a chip of such complexity. It also does not account for the cost of test and package, which can be quite high for such a high performance chip.

    There are a few other technical errors in the paper, at first glance. The large stations seem to call for 2000 banks of tiny DRAMs. Unfortunately, DRAM on an ASIC is not available at such a fine granularity. He would have to use SRAMs to implement this memory, and lose quite a bit on area. One could argue for a custom DRAM implementation, but DRAMs are black magic in the process industry and you really don't want to get into that business if you can avoid it, especially at half a million bucks per spin of the chip!

    otoh, the architecture looks pretty systolic and repeated, so yield can be made near-perfect if some kind of fault-detecting bank-switching scheme is designed into the chip.

    These ancillary costs start to grow in comparison to the 10 million dollar figure to crack RSA-1024, and it is enormous in comparison to the numbers quoted for cracking RSA-512 and RSA-768. In particular, the observation about how the cost of the machine would be smaller than the prize money awarded for breaking RSA-768 should include the non-recurring costs, since presumably the only reason for someone to build such a cracking machine would either be to break a challenge such as this (public awareness), or to perform real espionage (you're funded elsewhere). In the case of real espionage, you probably wouldn't publicize the power of your machine by claiming the RSA-768 prize, anyways, so the cost of the machine relative to the prize amount is not as relevant :-)

  • by thogard ( 43403 ) on Sunday January 26, 2003 @08:42AM (#5161329) Homepage
    RSA is a pain to decypher because the assumed 1:1 for public and private keys. That isn't true. Its 1:N where N is a very larage number and may be N:M.

    this code [abnormal.com] shows a simple 10 bit RSA in perl (its too slow to do much more) and it will generage one public key and several private keys. Doing it for 1024 bit is left as an exercise for the reader.

    RSA's 1:1 is based on a short cut of a nasty operation via the Euclidian algorithm and it turns out the math works quite well if you do things the hard way but it takes a long time even on a modern computer.

Unix: Some say the learning curve is steep, but you only have to climb it once. -- Karl Lehenbauer

Working...