Slashdot Mirror
TWIRL: Are 1024-bit RSA Keys Unsafe?
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.
more here: link
SWORDFISH
Don't go telling anyone.
"Not knowing when the dawn will come, I open every door." - Emily Dickinson
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.
Wow. Looks like somebody's winning the $200k after all.
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!
-- 'The' Lord and Master Bitman On High, Master Of All
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.
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?
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.
Coca-Cola!
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.
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
And you'll be able to buy a machine that's 3 times as fast for half the price, saving both time, and the taxpayer lots of $$$. ;)
But seriously though...what's the point of spending $10M on this thing.
If the device is going to take a whole year to crack one key, then any self-respecting terrorist will just change keys more frequently.
And since we know that there's more than one terrorist, the Govt would have to buy multiple machines. How many? 100, 1000? at $10M a pop?
And that wouldn't even take into account running costs.
And ultimately, people who really didn't want their emails read will simply change to a longer keysize, (eg 2048 bits)
But at least I guess the hardware could be re-assigned to better uses, ie folded into TIA, where I'm sure it would make fast work of decrypting anything that the average Joe thinks is secure.
Can it factor large primes in mere seconds? I've designed a processor that can! I'm just looking for investors now...
they did develop a neural net a few years back that cracked 32 bit RSA in 3 days (more bits made it exponentially slower) so honestly how much better is 1024 bit given some of the hardware available today? A year on a 10 million dollar device is a month on a 100 million dollar device and are we to believe that our government or others (Russia) dont have better devices than that?
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*.
May we never see th
Spend enough money and just about anything can be solved.
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).
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.
Is this an obvious troll or what?
The guy's even used the same style in all his recent trolls - he should've learned by now that there's a limit to the amount of mathematical BS people can tolerate before becoming suspicious.
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
YES.
then don't comment it.
Noone here blames you for having no clue about modern mathematics
I wonder if this is complementary to the hardware-based approach discussed here?
me karma am bad
All it takes is around 5(2^64) years to crack a 128 bit key, you should be very afraid.
You do realize that this is CIA's and NSA's next purchase don't you? Of course this also means that the World outside the United States will choose Linux on a faster scale than ever beofre..because they tend to link Microsoft with these trends..:)
Don't Tread on OpenSource
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.
"There is no teacher but the enemy."-Mazer Rackham
In the extra reference Bruce Schneier says:
If 512-bit keys are insecure today, they were just as insecure last month. Anyone implementing RSA should have moved to 1024-bit keys years ago, and should be thinking about 2048-bit keys today...
IANAC(ryptographer), but I have done a little Number Theory at Cambridge (the real one, Turing, GCHQ, etc). The reason for these doublings is that the FFT (Fast Fourier Transform) requires a power of 2 (actually, the 2^N complex roots of 1).
On the other hand, a doubling in key length squares the size of the problem (at least until P=NP), so it seems odd to say that we need to move to 2048. After all, a single extra bit of key (theoretically) would compensate for Moore's Law. As the article points out, add 14 bits anyway.
Having said all that in explanation, my question is: How much difference does it make to use (e.g.) a 1280-bit key? Is it cheaper to implement this as a 2048 FFT, or could it be beneficial to do (perhaps) 9 256x256 and 1 1Kx1K multiplications and then add up? I am talking about the speed of 'legal' crypting as opposed to cracking here, obviously.
Yes. With enough computing power, any key size is unsafe.
The real question is; are they safe enough?
with quanum compputing.. I don't believe our normal encryption will work
A Good Troll is better than a Bad Human.
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
Even though $10M and a year sound a bit ridiculous, this is actually a huge discovery.
Ok, so Mr. AvgJoe won't be able to crack your encrypted post to a linux-devel mailing list... but in a short while, someone might improve upon this technology to make it more feasable for the average-sized company to use (few thousand dollars, less than a month).
This is just a building block!
You don't realize that for example 2^128 is greater than the number of atoms in the universe.
Imagine a 10 MB crypto key... Well, you can't imagine it, but something tells me it'll be hard to crack.
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.
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.
Adi shamir and Eran Tromer are well known In the israeli academy and in the world of computer science. Keep up the good work guys!
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.
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.
How is this related, if at all, to RSA slightly broken?
Yeah kids, we did this here and here.
I think we've got slightly more atoms than that. And if all else fails, energy can be turned into positrons and electrons, giving us more particles to work with quantum computing.
we will know Saddam's AOL password!! Ahahahahaaa
Someone once calculated the amount of heats created by switching a bit on or off and then calculated how much heat would be generated by a brute force approach to cracking a 1024 bit encryption key. This worked out to be about the same amount of energy as the sun puts out in one day. I'm not claiming that is entirely accurate but it makes me wonder.
I can factor any prime number in my head. Its the ones that aren't prime that get me.
Actually, quantum computers can break most of the commonly-used public-key algorithms (asymmetric), but it only helps out some on the commonly-used symmetric-key protocols (if they aren't breakable by anything except for brute force). So, 256-bit encryptions using Twofish/AES/Rijndael/3DES(although 3DES probably wants more bits) are still probably safe for the universal age even with quantum computers.
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
Heisenberg may have been here
(Let's just get it out of the way now...)
1) RSA-1024 prize: $100,000
2) Buy $10M device
3) ????
4) -(Profit!)
5) Oops.
The EFF, of course, has a hardware DES cracker. 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.
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.
Like tinyurl, but one letter less! http://qurl.co.uk/
Imaginge a beowolf cluster of these...
Dan Bernstein (author of qmail) wrote something like this a while ago.
http://cr.yp.to/papers/nfscircuit.pdf
Just in case some slashdot readers don't know...
0 2.htm
Adi Shamir is the "S" in RSA
Ronald Rivest, Adi Shamir, and Leonard Adleman
light reading here:
http://home.ecn.ab.ca/~jsavard/crypto/pk05
All of the hype I have seen goes on about the time required to guess a 1024 bit and the number of combinations you would have to got through.
However, I guess there IS a probability that you could hit jackpot on your first guess, or second, or tenth or 20,0000th.
So are there folks out there actively having a go at Verisign root keys just for the hell of it ? Just imagine the publicity if they got lucky and the resulting scramble to renew certs etc..
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.
You'd spend much less than $10 mil installing surveillance equipment to record my passwords (keystroke logger, camera, EM fields from my computer & monitor) or just bribe my bank/employer/friends to covertly give you the info you want. Bribe my postman to lend/give you my mail. Or steal someone's trash. etc.
--
There is no hatred more pure and true than that expressed by children.
thus, let m = c*2^b
now let c' = c / 10000, i.e. the new cost
m = c' * 10000 * 2^b
m = c' * 2^(ln(10000)/ln(2))*2^b
m = c' * 2^13.29 * 2^b
m = c' * 2^(b + 13.29)
Thus, the marginal attackable keysize that increasing your computational efficiency by 10000 has gained you is 13.29 bits. I think 1024 bit keys are a-OK. Welcome to the wonderful world of exponents.
Babak
I bet NSA have had this for years.
That's why I said strong passphrase - a regular sentence would be too
easily broken. I am talking about 70+ chars of apparent randomness -
note that the issue of remembering such a passphrase without writing
it down isn't the point of discussion here. I am interesting from the
perspective of security of stored information.
Say I was some nasty terrorist (which I'm not, better stress that
one!) using PGP to secure my plans and share them with my associates
over the Internet.
Using 4096 bit security may be fine for transmitting over the
Internet, but if the government come round and take your computer away
they have your private key. If they can then break all your messages
in five minutes because they have that key, that's a major weakness in
the security of the system as a whole.
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.
/. lamers we read the initial three words of whichever link we clicked first and immediately jump to one of serveral interpretations:
/. posters in category (4) would get jobs as microwave oven repair persons. Then everyone would become a lot more cautious about their dialectic coefficients.
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
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.
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.
It also hasn't been shown that El Gamal or RSA is as difficult as factoring. There may be other ways to break it. If it is as difficult as factoring then you need a quantum computer to break it.
From what I have heard from people that know much on it, and from what I've read - I thought the general point of RSA was *relative* ease and speed - but the general method was always going to be "unsafe" - it is just a matter of how long it is "safe" for.
The longer the key, the longer the data stays safe for - but as computers increase in speed and decrease in cost, it will become increasingly easier to break longer keys, and therefore reducing the time that something stays "safe".
there are things that you only don't want seen or known for a few minutes, there are things you don't want seen or known for hours... days - months - those are all judgement calls.
But eventually you have things that you always want safe... and it seems that the general concensus (sp?) for those things is not to use RSA.
a year to crack a 1024 key is still pretty damn good - it just depends what you are trying to keep people out of. as long as it is data that is only useful for a few months - then this news isn't horrific just yet.
There are some odd things afoot now, in the Villa Straylight.
The version currently circulating is indeed a draft. The final version, when available, will be placed at my homepage, and specifically here.
-- Eran Tromer
Do you ever have one of those moments where you realize how few people in the world would understand a sentence you just read? Then you stop and ask yourself if you just understood the sentence you just read? I mean, "1024-bit RSA Keys..." That's pretty easy to comprehend, right?
But if I were to look my dear 67-year-old father straight in the eyes and ask him, "Dad, are 1024-bit RSA keys unsafe?" first he'd stare at me blankly, then he'd start to drool, and finally he'd drool again. And he's a very smart man.
Sorry, waaaaaaaaaaaaaaaay offtopic, but I just had one of those "knowing more and more about less and less" moments. Go on about your business.
Love, Me.
"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.
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."
Are 1024-bit RSA Keys Unsafe?
1024-bit RSA keys can be completed in less than a year by a $10M device.
Ooh, I'm shaking in my boots now... C'mon folks get a grip. Who gives a rat's fart if a 1024-bit key can be compromised with a $10 million dollar device?
Run for the hills Velma! The govmn't will be able to read our bank statements, after they dedicate a $10 million dollar device to cracking our RSA key for a year!
Can you say paranoid?
What the fuck? Are you on crack? Shimura-Taniyama-Weil is true, yes, but WTF does that have to do with factoring and NP-completeness? Do you even know the statement of Shimura-Taniyama-Weil? Stupid Slashbots will probably still mod you up, idiot.
#!/bin/bash echo "What prime number do you need factorised?" read prime echo echo "The factors of $prime are 1 and $prime."
See? You don't even have to use a new processor!
Note to M1-ers: a curt but otherwise insightful message is not "Flamebait" or "Troll".
As pointed out in David Deutsche's The Fabric of Reality , no encryption based on large primes is ever indefinitely secure.
... and currently decoherence is the largest obstacle to overcome.
...
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, 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 about it. =P
-------
If you don't take responsibility
for what goes into your mind
Someone Else Will!
-=[You cannot consistently judge this statement to be true.]=-
It will be able to do teraflop right? Well then all we need is a cluster of these baby's and we'll be set.
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...
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.
Schneier, page 234:
... it's vulnerable to an elaborate dictionary attack?
"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
Why can't you just say 400h-bit RSA? Why is it so damn hard to do this? Isn't 400h beautiful and elegant, while 1024 is ugly and gross? Why must you do this? PLEASE PLEASE PLEASE try to use hexadecimal, especially when it's clearly aligned to it. Don't ignore me.
Why can't you just give your figures in hexadecimal? It makes more sense there. Hexadecimal is beautiful and elegant--decimal is UGLY. Does anybody else feel like me? Am I the only one? Stop using decimal.
PGP 6.5.8 uses for its passphrases by default an iterated salted SHA-1, which is roughly 2^160 chosen collision, 2^80 birthday collision, strong random salt and no known patterning through successive iterations.
I will assume that an attack requiring you to use a key that has been tampered with is impractical in this case.
I can't really give any accurate figures because it purely depends on how strong the passphrase is - how easy it is to guess - and that's not information you really want to give us.
At that size, it could be very secure indeed, up to the limit of a hash break (160 bits). It probably isn't even close to that good, because you can remember it. If you used, say, Diceware to generate your password, you're probably cool. It's a known wordlist, yes, but the randomness provided by the dice gives real, measurable entropy - if you can remember it, it's good.
We only really know the rough length here - if you picked a quote from anything, a word or phrase from any language, or a host of other things, it could be much less than you thought, possibly 2^40 or less. If you haven't been such a moron, then it could be 2^70 or even up to 2^90 depending on how ninja you've been.
This may not be as high as you were hoping for but if you have chosen a good passphrase, then you are safe unless you have a heavy, serious threat model trying to get your communications the dumb way (or if there was a keylogger on your machine).
It's not all that insecure - Hushmail uses this principle. But you have to choose a really good passphrase for that - it's critical, and it's something most people are bad at (hence the Diceware link).
At the end of the day, you have more security if your private keys stay private. If you are able to revoke that key and make another, do it, but don't use the same passphrase, or any part of it, ever again.
Why can't you just say 400h-bit RSA?
Because I'm a C++ programmer, and I say 0x400 bit RSA.
A legparnasom tele van angolnaval.
that it all depends on how lucky you are. You can crack any key of any length in mere seconds if you are lucky enough :)
why not change the 1024-bit key every day? Then it would probably take a $3.6 billion dollar device to crack it, so if it is ever cracked, we can probably convince some judge to sign a search warrant for Bill Gates' place.
Say I was some nasty terrorist (which I'm not, better stress that one!)...
"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.
Corporation, n. An ingenious device for obtaining individual profit without individual responsibility. - Ambrose Bierce
Remember, this story applies only when the attacker knows the method of encryption, and there is only one method of encryption.
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.
High-speed Road Trip (18.000KPH)
I keep them in a shoebox under my bed.
Oops! I mean, they're in the closet. Yeah, in an old coffee can. Forget what I said about the shoebox. I was just kidding.
Lump lingered last in line for brains, and the ones she got were sorta rotten and insane.
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 "
So, guys ?
READY, 3, 2, 1, GOOOO !
It could do it in a day. That is why it is called brute force.
Because I'm not a 16-fingered mutant.
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 :-)
Given that Quantum Computers can factor large numbers relatively easily and given the inability (as of now) to solve any NP-hard problem efficiently using a Quantum computer, it seems very likely that factoring may after all be easy. In fact, it is widely believed that the techniques for factoring are still in their infancy.
As the difficulty of many other problems (Quadratic Residuosity etc.) are directly related to the difficulty of factoring, abandoning factoring might not be particularly productive.
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 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.
A 70-character passphrase *is* better than a 32-character passphrase, because your passphrase is likely not random characters -- it's an English phrase, and English has low entropy.
Become a FSF associate member before the low #s are used
No you're not. You're saying 1024 bit, not 0x400 bit. Stop lying and start using hexadecimal.
...but don't you think the NSA has had the means to crack common cryptosystems for quite some time? They usually make an objection when they can't (ref. the NSA intervening and reducing the security in IBM's suggested DES standard back in the days).
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...)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks