Slashdot Log In
512-bit RSA Key Cracked.
Posted by
justin++
on Sat Aug 28, 1999 09:10 PM
from the go-alec dept.
from the go-alec dept.
Alec Muffett writes "
On Thursday, a small team of people (including myself) announced the
world's first factorisation of a 512-bit RSA encryption key (aka:
RSA-155) - considerably bigger than the RSA-129 challenge of several
years ago, and this time performed by a small
cabal of numbercrunchers, just to see if it could be done in secret.
There are
press releases and
announcements available, as well as considerable discussion in sci.crypt.
" Read on for what Alec has to say on the matter.
This is a significant advance because such 512-bit length keys are
routinely used in (possibly ill-advised?) transaction protocols for some important
financial institutions (read: some serious $$$$$$$ may be at risk in
the near future) - and moreover, as a factoring contributor, I can state that I
personally have now been offered the use of additional hardware which
could take the 6 or 7 months spent sieving for results, and reduce the
time by a factor of some 40% to 60%.
This discussion has been archived.
No new comments can be posted.
512-bit RSA Key Cracked.
|
Log In/Create an Account
| Top
| 173 comments
(Spill at 50!) | Index Only
| Search Discussion
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
(1)
|
2
(1)
|
2
It's not about privacy. (Score:3)
What this trouble is about, however, is security. Not national security, but information security. On most UNIX systems, passwords are stored as 56-bit DES, and there's always a way that one can somehow get the password file, from which point it's almost always painfully simple to get a root shell. From there they can access any information on the servers, and if it's encrypted - and 512-bit RSA is pretty standard for such sensitive information - it's not too hard to crack that anymore, either.
I still feel comfortable in sending my credit card information to online retailers who use 64-bit RSA and the like. There's just too much information out there for someone to effectively snatch my info, and it's certainly more secure than using a phone or mail or whatever to send that information to them. What I'm concerned about is the information when it's on the other server.
As has been stated before, 1024-bit RSA and 128-bit blowfish are still plenty secure, and likely will be for a long time. I'm not concerned about my ssh connections being cracked. And, honestly, I'm not too concerned if someone else gets my bank information, since banks have insurance for my money (up to $10,000 anyway) and although it'd be a hassle for me, it's the one stealing the money who would eventually suffer, not me.
But my privacy isn't really something I clutch with my big guns blazing. It's a false premise anyway. I mean, hell, I even give Too Much Information on my slashdot user info, and anyone on the various MUCKs I'm on would have an easy time to find out anything they want about me. That coupled with many websearches and the like would easily find plenty of dirt on me, things I've done or said in the past I'm ashamed of but which I've pretty much put behind me, since it was before I decided to grow up instead of being a trite little punk hacker wannabe.
Though if you do find out enough, there's no reason to use it against me; after all, I do deserve my privacy.
---
"'Is not a quine' is not a quine" is a quine.
Re:Oh no! (Score:3)
But the BIG difference here is that 512-bit keys have been thought safe against all but (perhaps) Major World Governments, until now. What happens when some terrorists finally cotton to this, and realize that with some intelligent cracking, they could very well jeopardize the stability of, oh, say, the US dollar as a currency. An awful lot of bank transactions are secured with 512-bit keys, and (no reference here-- if anyone has real numbers, please contribute!) I believe something like 95% of US currency exists only as bits in computers.
So now, the situation is not that "someone will steal your credit card number," but that someone could potentially steal (or render worthless and nonexistent) >= 50% of all US dollars. That scares me. It ought to scare you too.
And obNote to those not residing in the US, or handling US currency on a daily basis:
It's even easier to decrypt messages from the web. (Score:3)
Reading the sci.crypt FAQ's it gives you tips on cracking encrypted text.
One of those is by using information you know that's contained in the encrypted text, which is very simple to get.
On the web, it's simple. Take amazon.com for example, everybody sends the same static information, but different dynamic information.
Static being 'CC#:', 'Full Name:', 'Address:', 'Phone Number:', etc. and dynamic being what follows these.
So right there you have _that much_ information, and when you think about it you can get most of those things I listed above.
If the person is targetted, it's even simpler. I know I write my address the same on-line as i do on snail mail. My full name can be on my return address. Phone number is no sweat. Credit card number is one of the few things the cracker needs.
Not to mention how unsecure lots of web sales sites are. BEFORE YOU SEND YOUR CREDIT CARD NUMBER TO A WEB SITE READ THE WEB PAGES' SOURCE CODE TO SEE HOW IT'S HANDLED.. This is very good practice.
I've seen countless times sites with https saving order forms in text files that are chmod'd wrong. Even some that are E-Mail'd. One of the most secure ways is to be put into a database, they might even be encrypted to boot.
From the Bible (Score:3)
In Schneier's "Advanced Cryptography" he makes estimates on the amount of computer power needed to factor various size numbers. The estimatetd that using the General Number Field Sieve, it would take 30,000 mips-years to do the factoring of a 512 bit number (it took 6,000 mips-years). He also postulated that the NSA might have a much more efficient algorithm (that works at the same speed as the more specialized Special Number Field Sieve) that would do the job in under 200 hours. The number here, 6,000 mips years is in between these numbers, and completely expected. Anyone risking hundreds of millions of dollars on security the can be broken for less than that (i.e. 512 bit keys) deserves to lose their money.
What is safe? For comparison, the General Sieve would take
2*10^8 mips-years to factor a 768 bit number
and
3*10^11 mips-years to factor a 1024 bit number
IF a way to run this as fast as a special sieve is discovered these numbers become
100,000 mips-years
and
3*10^7 mips-years respectively.
Dedicated hardware sieves _could possibly_ do these today.
This result doesn't change the basic conclusion that 1024 bits is, for individuals, safe for the near future. For governments and banks etc. public keys of at least 2048 bits should be used.
It all depeds on how valuable your information is, how important performance is, and how long you want your data to be safe for.
Schneier also makes the useful remark that all predictions of the future are bunkum and shouldn't be trusted.
Why this is not a problem (Score:3)
1) Who has every considered 512 bit RSA secure? It's been on the export list precisely because it is not considered secure. This article states 25 years ago it was considered virtually unbreakable. 25 years ago computers were barely around! The first personal computer was the MITS Altair 8800, released at the end of 1974 (25 years ago). Anything other than XOR would have seemed virtually impossible to crack with that!
In 1974, IBM's fastest mainframe ran at ~1-2MIPS.
2) You can't "steal" credit card numbers, like you can steal cash. If you had every number under the sun, there is no way you could spend it without getting caught. Many sysadmins have access to millions of credit card numbers. If that really translated to a billion dollars they would be living in the Bahamas. Credit cards numbers != currency.
3) The cost of breaking a single SSL message would not be worth the cost gained by getting a credit card number. Each connection has a different key and there is no way to know if there is actually anything useful in the message until you break it. Just because someone makes a SSL connection doesn't mean there is anything valuable in the data. If you pick a SSL message at random and spend 3 months cracking it, chances are you'll come up with an banner ad image.
4) The internet isn't as insecure as people make it out to be, even without encryption. The government can't monitor most of the internet traffic, how is someone else supposed to collect all of the data to crack? Sure you can break into random machines here and there and do some small time sniffing, but nothing wide spread. It's not like you can take a laptop out to a fiber line somewhere and splice it in... you'd have to setup a big data center. If you could tap into a backbone, you'd *have* to use filters to reduce your data set size, but with encryption this is impossible. Even 64 bit RSA would be secure for this reason.
5) Cracking 512 bit RSA with plaintext available is not the same as breaking a SSL message. It's much much hard to break SSL (see below for a description of the SSL connection algorithm).
6) All banks that I know of offering online banking, either a) require 1024 bit RSA, or b) don't allow the transfer of money to an outside account (unless you count bill-payment systems).
---SSL connection description---
For the initial connection, when a client wishes to establish a secure connection, it sends a CLIENT-HELLO message, including a challenge, along with information on the cryptographic systems it is willing or able to support. The server responds with a SERVER-HELLO message, which is connection id, its key certificate, and information about the cryptosystems it supports. The client is responsible for choosing a cryptosystem it shares with the server.
The client then verifies the server's public key, and responds with a CLIENT-MASTER-KEY message, which is a randomly generated master key, encrypted or partially encrypted with the servers public key. The client then sends a CLIENT-FINISHED message. This includes the connection-id, encrypted with the client-write-key. (All these keys are explained separately, in the next section.) The server then sends a SERVER-VERIFY, verifying its identity by responding with the challenge, encrypted with the server write key. The server got its server-write-key sent to it by the client, encrypted with the server's public key. The server thus must have the appropriate private key to decrypt the CLIENT-MASTER-KEY message, thus obtaining the master-key, from which it can produce the server-write-key
How much was power and how much was parallelized? (Score:3)
More Info...Comments (Score:4)
"Sieving was done on about 160 175-400 MHz SGI and Sun workstations, on 8 300 MHz SGI Origin 2000 processors, on about 120 300-450 MHz Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes. The total amount of CPU-time spent on sieving was 35.7 CPU years estimated to be equivalent to approximately 8000 mips years. Calendar time for sieving was 3 1/2 months."
"(L: using lattice sieving code from Arjen K. Lenstra C: using line sieving code from CWI)
20.1 % (3057 CPU days) Alec Muffett (L at Sun Microsystems Professional Services, Camberley, UK)
17.5 % (2092 CPU days) Paul Leyland (L,C at Microsoft, Cambridge, UK)
14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L at CWI, Amsterdam)
13.6 % (2222) Bruce Dodson (L,C at Lehigh University, Bethlehem, PA, USA)
13.0 % (1801) Francois Morain and Gerard Guillerm (L,C at Ecole Polytechnique, Palaiseau, France)
6.4 % (576) Joel Marchand (L,C at Ecole Polytechnique/CNRS, Palaiseau, France)
5.0 % (737) Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA and Univ. of Sydney, Australia)
4.5 % (252) Paul Zimmermann (C at Inria Lorraine and Loria, Nancy, France)
4.0 % (366) Jeff Gilchrist (L at Entrust Technologies Ltd., Ottawa, Canada)
0.65 % (62) Karen Aardal (L at Utrecht University, The Netherlands)
0.56 % (47) Chris and Craig Putnam (L at ?)
Calendar time for the sieving was 3.7 months.
The relations were collected at CWI and required 3.7 Gbytes of disk space."
Quoted material from the link provided at the begining.
Time for Civil Disobediance? Think Carefully... (Score:4)
Seymour Cray's final product involved the fastest switching technology ever activated in a super computer, which was then coupled into a massively parallel computing system. The Cray-3/Super Scalable System [ccic.gov] had a revolutionary GaAs control processor with potentially tens of millions of computing memory elements. This system (an adaptation of the original GaAs Cray-3) was financed by the NSA. Seymour Cray accepted this funding in a last-ditch effort to save his company and when I visited the Colorado Springs office, I was actually given the impression by one of their executives that they had a working model and would consider commercial sale of the device. Cray Computer Corporation went bankrupt shortly thereafter in the first business failure of Cray's phenomenal career. About a year later, Cray was killed in a jeeping accident. Having cut my teeth on his machines at the CDC/Urbana PLATO project [thinkofit.com], I knew Cray was unhappy with the direction his technology had been taken by "the spook shops" from before the day he left CDC to found Cray Research on his farm in in Wisconsin [umn.edu].
Recent revelations of RSA's vulnerability come as no surprise. The NSA, despite the fact that it is run by unaccountable bureaucrats embedded in a dough ball of Federal funding, is probably far beyond a cabal of private hackers in their capabilities.
Lest hackers and civil libertarians get the idea that now is the time for civil disobedience in protest of regulations against unlimited key sizes, you should probably be aware that Federal officials are so embolden by their lack of accountability that some of them have slipped up and are explicitly threatening suspects with prisoner gang rape. Given the prevalence of HIV infection in the prison systems, and the efficiency with which the virus is transmitted during gang rape, such threats amount to murderous sexual sadism as punishment for civil disobedience. In one of the most outrageous examples, Assistant U.S. attorney Gordon Zubrod from Harrisburg, PA made the following statement in a broadcast statement to 3 suspects who fled to Canada (this statement was captured for the public record during a Canadian Broadcasting Corporation interview):
"You're going to be the boyfriend of a very bad man if you wait out your extradition."
If you think the use of murderous sexual sadism against protesters who engage in civil disobedience is unrealistic, or somehow so low risk as to be inconsequential, you should read Torture In The American Gulag [deja.com] before taking any personal risks.
Oh no! (Score:3)
Anyhow:
I'm just shaking in my boots. It's so frightening to me that a cracker with a cluster of 30 computers to spare for a period of 7 months can get all of my secret credit card information. It's much more frightening than that scary person at the gas station who processes my credit card everytime I fill up with gas.
Face it, there is no such thing as privacy, even with encryption. It's all just an *illusion* of privacy. I wouldn't be surprised if the NSA already knew how to crack 1024-bit RSA keys. Encryption, like any form of computer security, is not the process of making you invincible, it's just making it more difficult for someone to crack your information/system/network/whatever.