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.
Good topic (Score:5, Informative)
Re:Good topic - hmmm i wonder. (Score:4, Interesting)
Re:Good topic - hmmm i wonder. (Score:5, Informative)
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)
Don't go telling anyone.
They're safe enough (Score:5, Insightful)
Re:They're safe enough (Score:5, Insightful)
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.
Re:They're safe enough (Score:2)
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.
Re:They're safe enough (Score:5, Insightful)
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.
Re:They're safe enough (Score:2)
"Sure, just read it the key right off the post-it note on your monitor..."
Re:They're safe enough (Score:5, Interesting)
Re:They're safe enough (Score:3, Interesting)
-a
Xbox (Score:1)
Re:Xbox (Score:3, Insightful)
Re:Xbox (Score:2)
Don't give Michael Robertson any ideas.
Re:Xbox destroys brain cells (Score:5, Insightful)
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
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
Re:Xbox (Score:5, Informative)
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)
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)
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.
Oh no! A year! (Score:5, Funny)
Re:Oh no! A year! (Score:5, Insightful)
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)
Well, those people who were too stupid not to create a revocation certificate, at least.
Re:Oh no! A year! (Score:2)
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>
Re:Oh no! A year! (Score:2)
$10M?! holy sh!t (Score:3, Insightful)
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.
Re:$10M?! holy sh!t (Score:2)
$10M is really not a lot of money for many Christain countries.
$10M is really not a lot of money for many Buhdist contries.
$10M is really not a lot of money for many Shintoist countries.
etc.....You're point?
But you were right on the Verisign thing.
Re:$10M?! holy sh!t (Score:2)
Re:$10M?! holy sh!t (Score:2)
Re:Oh no! A year! (Score:4, Funny)
Re:Oh no! A year! (Score:2)
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.
Don't be so alarmist (Score:2)
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*.
Re:Oh no! A year! (Score:2)
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.
Re:Oh no! A year! (Score:2)
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.
This should be obvious (Score:5, Insightful)
Re:This should be obvious (Score:4, Informative)
99% of encryption can be broken given enough time. You really only have to worry about the information in question being encrypted as long as it is considered sensitive.
For instance, I tell my friend "Mee my at the bar tomorrow at 9 pm". I only have to make sure that the message is secure until tomorrow at 9 pm. If it takes longer to break the message, the content of the message is no longer valid.
It's a waste of time to try to make the message more secure.
Re:This should be obvious (Score:3, Insightful)
But I agree with your point in general. :-)
Re:This should be obvious (Score:4, Funny)
From now on I shall encrypt my posts by mee mmoo un weedle dhodhe unbvoppe zzfp dee. ;)
Re:This should be obvious (Score:2)
One Question (Score:5, Insightful)
The secret formula for... (Score:1, Funny)
Re:One Question (Score:2)
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)
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)
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)
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)
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)
Daniel
The answer seems to be "soon, perhaps" (Score:5, Insightful)
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.
Re:The answer seems to be "soon, perhaps" (Score:2)
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.
Re:The answer seems to be "soon, perhaps" (Score:2)
Governments may well not encrypt large chunks of hyper-sensitive data with 1024-bit RSA. Given that "the rest of us" can fairly trivially encrypt using RSA with 4096-bit or larger keys, it'd be a surprise if this were the weak point in a typical government's communications. (If it's a very poor country with miserable IT resources, I bet there's a good chance it's amenable to all sorts of other forms of intelligence gathering, too.)
Re:The answer seems to be "soon, perhaps" (Score:2)
Governments probably do not encrypt sensitive data based on public key cryptography. There is a rumor that the NSA was aware of public key cryptography before RSA invented it, but that they didn't know what to do with it. Authentication is provided by the armed guard that checks your ID, not by an algorithm that depends on the assumption that factorization is hard.
Public key algorithms are used for signing documents. According to the German signature law, 1024 bit signatures that meet some additional requirements are considered equivalent to physical signatures. (minimum recommended len for keys valid up to 2005). Thus it is important if intelligence agencies can break 1024 bit RSA keys.
Re:The answer seems to be "soon, perhaps" (Score:2)
Actually there's more than a rumour that it was previously implemented [gchq.gov.uk] at GCHQ [gchq.gov.uk].
Public key algorithms are used for signing documents. According to the German signature law, 1024 bit signatures that meet some additional requirements are considered equivalent to physical signatures. (minimum recommended len for keys valid up to 2005). Thus it is important if intelligence agencies can break 1024 bit RSA keys.
You're right: that is interesting, and it's certainly something of which I wasn't aware. Though it suggests that 2005 is probably a sensible time frame to be retiring the 1024-bit keys. Probably unlikely that $10M will become $10 and 1 year will become 10 minutes that soon.
Re:The answer seems to be "soon, perhaps" (Score:2)
Seems to me that making it the equivalent to a physical signature is way open to perfect forgory in the future.
Re:The answer seems to be ... decimal . (Score:2)
Because I'm a C++ programmer, and I say 0x400 bit RSA.
oh dear....... (Score:2, Insightful)
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)
Re:Yes, but... (Score:3, Funny)
Is this really so shocking? (Score:2, Interesting)
1024 bits - dodgy against big threat models (Score:5, Informative)
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).
Re:1024 bits - dodgy against big threat models (Score:2)
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)
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.
Re:make a bigger key (Score:3, Insightful)
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.
Re:make a bigger key (Score:2)
Are 1024-bit RSA Keys Unsafe? (Score:5, Funny)
Slashdot and their damn dupes
The Race and Coca Cola (Score:4, Insightful)
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.
Re:The Race and Coca Cola (Score:2)
Define "Safe" (Score:4, Insightful)
Yes. With enough computing power, any key size is unsafe.
The real question is; are they safe enough?
Re:Define "Safe" (Score:2)
Succinctly put.
security is misleading (Score:5, Interesting)
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
They could build more than one machine! (Score:5, Insightful)
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.
Re:They could build more than one machine! (Score:2)
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
The six BILLION dollar computer room... (Score:2)
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...
Re:They could build more than one machine! (Score:2)
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.
How secure is PGP if you possess the private key? (Score:5, Interesting)
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.
Re:How secure is PGP if you possess the private ke (Score:2)
Re:How secure is PGP if you possess the private ke (Score:3, Informative)
"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
Re:How secure is PGP if you possess the private ke (Score:2)
"No, I'm sorry, Sir, we have to take your first answer.
"Boys! Come and take Mr. White to the car.
"Have you tried Cuban cuisine before, Mr White?" ~shark grin~
ps. You really shouldn't store your private key on your harddrive.
Re:How secure is PGP if you possess the private ke (Score:3)
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.
Re:How secure is PGP if you possess the private ke (Score:2)
Re:How secure is PGP if you possess the private ke (Score:2)
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.
Re:How secure is PGP if you possess the private ke (Score:2)
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.
Re:How secure is PGP if you possess the private ke (Score:2)
decoy keys (Score:2, Interesting)
DUPE (Score:2)
Very limited market (Score:2)
So, in cryptographic systems (Score:2, Funny)
Proof that RSA was never secure in the first place (Score:2)
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.
Re:Proof that RSA was never secure in the first pl (Score:2)
"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)
Not getting it... (Score:4, Informative)
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)
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
Quantum Computing and the Multiple Universes (Score:3, Informative)
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
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!
The attacker must know the method of encryption. (Score:2)
Quantum computing (Score:3, Informative)
As said here [rsasecurity.com] by RSA Labs
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
Of course 1024-bit keys are becoming unsafe.... (Score:4, Insightful)
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.
Beowulf Cluster ! (Score:3, Funny)
oversight in paper (Score:2, Informative)
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 :-)
You don't have to factor RSA (Score:3, Informative)
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.
Re:In the future... (Score:2)
Re:Brute force (Score:3)
You have the driest sense of humor I've ever seen. My hat is off to you.
Re:A question on intermediate key lengths (Score:2)
An "RSA operation,"
That tells me more than you did, although perhaps less than I would like to know. Why my original posting was rated up 3 interesting and then down 3 troll (?!) I fail to understand. Even less, why when we are talking the 1K-2K bit range, I am considered an idiot and quite stupid by an AC who only refers to the 10K bit 'range' who clearly could have given a sensible answer. Ah well:
Re:Wait 6 months... (Score:2)
Don't forget though, that many times they nab the terrorists and then keep them in prison while they sift his belongings and intercepted communications for evidence connecting him to x,y, and z criminal acts.
There are no "speedy trials" for these guys, they just barely finished up proceedings on guys suspected on the original bombing of the trade center, when they used explosives in rental trucks in the parking garages.