Slashdot Mirror
Factoring Breakthrough?
An anonymous reader sent in: "In this post to the Cryptography Mailing List, someone who knows more about math than I do claimed "effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were." Apparently Dan Bernstein of qmail fame figured out how to factor integers faster on the same cost hardware. Should we be revoking our keys and creating larger ones? Is this "the biggest
news in crypto in the last decade," as the original poster claims, or only ginger-scale big?"
Try viewing the postscript file using the online viewer here instead.
/cj
don't tell me you haven't converted your judgments of magnitude to the ginger scale. everybody's doing it.
Cryptography is going to be a perpetual game of "measure, counter-measure" as computing power increases and people develop more clever ways of doing things.
Does anybody have good sources about this? Ones based on historical encryption and decryption that lead into modern times would be ideal.
Either give it away or get top dollar, but never sell yourself cheap.
The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.
So when you ask "Are our keys secure" the logical follow-up question is, "From who?"
From me? Yes. I probably couldn't factor a 1000 digit number.
From your boss? Yes. You could use rot-13 and your boss would probably be baffeled.
From your boss' lawyers? From the police? Here is where we get into the gray area; where the article becomes relevant
From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.
God is real unless declared integer
I use a 4096-bit GPG key. It may take a day to encrypt a message, but at least the encryption can't be broken (yet).
--
Beauty is in the eye of the beholder... Oh, no. It's just an eyelash.
http://cr.yp.to/papers.html
Raised by monkeys.
The Rijndael/AES cryptosystem does not depend on the difficulty of factoring. This is a big deal mostly for RSA.
Circut for integer factorization?
Reminds me of a certain movie...
--J(K) DOS is like Unix in exactly the same way that a pinto is like an aircraft carrier.
I haven't hit a top limit on the GPG key yet. I had an obnoxiously long 4096 bit one I was testing with for a while and PGP was able to encrypt messages to it but was unable to import the private key. Oh well, time to move to an obnoxiously obnoxious 8096 bit one.
Suddenly the 128 bit netscape encryption isn't looking so good (Not that it was before...)
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
Shouldn't we all hang on until crypto experts validate this? Is it theoretical? How much does the attack cost? etc. etc.
I wouldn't start sending those revocation certificates just yet.
e4 e5
I read somewhere that the RSA public key algorithm was invented at GCHQ, and kept secret, years before RSA invented it.
Best Slashdot Co
There is no impact. AES is a symmetric system that is not based on factoring. This apparent discovery only affects algorithms that are based on the difficulty factoring large numbers.
All editorial writers ever do is come down from the hill after the battle is over and shoot the wounded.
"Holy shit. The math works. Bernstein has found ways using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies an redundancies because we kept thinking in terms of linear implementations. This is probably the bigest news in crypto in the last decade."
Yeah, this is big news. It also sheds new light on the relaxation of the export constraints. The NSA has dedicated hardware performing this same procesing, and probably for the last 5-10 years...
"Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fa ct very likely."
Time to make new keys...
Using 128 bits is fine for symmetric key algorithms like IDEAS and Blowfish. It's not ok for public/private key algorithms like RSA. You're comparing Apples to Oranges.
Protecting against the http://cr.yp.to/papers.html#nfscircuit speedup means switching from n-bit keys to f(n)-bit keys. I'd like to emphasize that, at this point, very little is known about the function f. It's clear that f(n) is approximately (3.009...)n for _very large_ sizes n, but I don't know whether f(n) is larger than n for _useful_ sizes n.
Bernstein's paper is excerpted from a grant proposal where he is requesting funds to answer the question of whether the design is applicable to useful key sizes. At this point it is far too early to assume that 1024 to 2048 bit keys can be attacked by his proposed machine more efficiently than with known methods.
None at all when considered by itself. AES (ala Rijndael) does not depend upon prime numbers. Hence, it is not subject to factoring. It is a symmetric cipher with key lengths up to 256 bits.
Where it could be susceptible, however, is during a key negotiation session (say via Diffie-Hellman Key Exchange) or a naive approach of simply encoding the session key using the recepients RSA key.
Where I would be truly frightened is in the realm of digital signatures where somebody could forge a digital signature simply by knowing the sender's public key and factoring it. With digital signatures almost as legally binding as handwritten signatures, identity theft may increase using these methods.
The resulting impact may be less acceptance of digital signatures and more reliance on antiquated methods.
RD
Isn't this just a creative variation on the one-time pad technique?
And all of these, really, are just techniques that split up the message, and then assume the decrypters can only get one part. So essentially you could do this with any encryption algorithm, just send part by the internet, and part by carrier pigeon, attack stoat, etc.
Ooh, a sarcasm detector. Oh, that's a real useful invention.
This is about a threefold increase in factoring speed.. not an order of magnitude.
The NSA can afford huge hardware.. REALLY huge hardware, for breaking crypto... was there ever any doubt?
Only a threefold increase in speed? That would make hardly any difference, you'd get a threefold speed increase just by waiting a few years for Moore's law to deliver.
My understanding is that keys of three times the length can be cracked in about the same time - which is an _exponential_ increase in speed.
-- Ed Avis ed@membled.com
The poster seems to think speeding the calculation by 3x means reducing the strength of 300bits to that of 100bits. I know this is plain wrong but I'm not sure of the correct value.
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
Is he going to pay someone $5000 if they can prove him wrong? (qmail joke)
You could view this post script file online here, or you could use the Windows, OS/2 or Linux viewers available here.
Every rule has an exception, and this is the only rule with no exceptions! Huh? -- Spatch
This isn't really a big deal, nor is it surprising.
Basically, what DJB has done is translated the GNFS from its normal implementation on serial computers (where there is a great deal of available memory, but only one operation is performed at once) into a parallel implementation, where the number of processors more closely matches the available memory.
The "decreased cost" is misleading here, since it is calculated on the assumption that sieving would have been done by a single processor with access to a huge memory... this quite simply was never the case.
There is nothing here to suggest that factoring can be performed using any fewer FLOPS; all that is demonstrated is that by using several processors, each with a smaller memory, you can do better than with a single processor and a giant memory. Which we already knew.
To summarize: DON'T PANIC!
Tarsnap: Online backups for the truly paranoid
I've seen a lot of comments about how this means that all SSL and PGP encryption is transparent, etc.
Please, get a grip.
Most "transient" connections still use 512 bit keys. If this effectively reduces the key size by 3, that's still 170 bits. That's far larger than the RSA key that took years to crack a few years back.
Technology improves, algorithms improve, and the TLAs can certainly afford to build cracking engines, but it will probably still take a substantial amount of time to crack a key. (Substantial = days.) Well worth the effort if you're looking at suspected terrorists or double agents inside of the FBI, but hardly worth it for anyone reading this comment.
What we *do* need to worry about is the effect on long-term keys. E.g., root CA keys often have 20-year lifetimes, something that now seems foolish with 1k bit keys.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
So the trick is to find a shortcut or a flaw in the algorithm that allows you to get the data without searching all the keys.
In the case of RSA, the shortcut is factoring the product of two primes. It's way way easier to factor a 128-bit product than it is to search through a 128-bit keyspace. So RSA bumped the size of the product up and up and up until it was as impossibly hard to factor it as it was to search a 128-bit keyspace.
Other algorithms have other shortcuts, too. Remember when a weakness was found in the session key choosing algorithm for Netscape? The keyspace was reduced from 128 bits to 24 bits or something like that, and then a search could be made on it.
Anything you can do to avoid trying all the keys is the name of the game. Unless you're some kind of quantum computer freak. ;-)
Well, of course, if the picture is unique, this is the one-time-pad encryption. In order to decrypt, you have to use the same picture (i.e. the same key).
One-time-pad is so-far the most secure, but it is not very practical in daily use. And make sure you don't use the same key more than once, otherwise, it falls into the same weakness as other encryption.
AES is secure, as is DES, as is almost any other symmetric cryptographic protocol. AES, for instance, is based on Galois Fields (and associated chicanery), whereas DES is based on drop-dead simple permutations that are so elegant and inexpensive that I find it difficult to resist *not* implementing them on an 8-bit PIC (although someone else has of course beaten me to the punch!). Neither one is reducible to anything like factoring.
;). However, don't make the switch to DH just yet -- IIRC, the ciphertext is effectively doubled in length (over RSA). So you can either make a bigger RSA, or you can make a bigger message every time you encrypt -- either way, you email just got longer :)
Many public-key algorithms, and many public-key-based authentication protocols, however, *are* reducible to factoring, even if they don't appear to involve such darkness the first time you read them.AFAIK, for public key algs the deep magic is either factoring or the knapsack problem; however, almost all of the latter kind have been proven insecure. One notable exception of the latter variety is the Diffie-Hellman (sp?) algorithm, which is incidentally also the first public-key alg ever invented, and the underlying muscle behind the NSA's DSA signature scheme (although ElGamal did some strengthening work and got to rename the bugger
- undoware.ca
No no, God is in the square root of the second time dimension. The proof is here.
It hurts when I pee.
.deen uoy noitpyrcne eht all is sihT
so when can i get a distributed.net client that makes use of this?
Suppose I have a 1024-bit key. The new algorithm makes it essentially take the same time to break as a 341-bit key using the old algorithm.
Since each bit makes it take twice as long, this means that the new algorithm is 2^683 times faster at cracking the code. This is a bit different than 3 times...
But then again, quantum cryptography may be even closer than working quantum computers, which means secure private key cryptography, meaning you can factor all you want, you aren't gonna find anything unless you get that private key.
See also my Australian mirror at: http://www.glasswings.com.au/cr.yp.to/papers.html# nfscircuit
Share and enjoy,
*** Xanni ***
http://www.glasswings.com/
I suppose the TLA agengies don't really need strong crypto to invade on my privacy. They just need a court order.
It's interesting. The TLA agencies which most likely can crack large encryption (NSA, CIA) have no authority to get a court order - they have no authority within the US. Also, it seems unlikely they'd reveal that they have this advanced technology for a mere murder trial or the like - more important to keep it hidden from their foreign enemies.
will that really stop them from making me give up the goods if faced with jail when they come asking for my data?
The US can't force you to give up your encryption keys - it would be a violation of your 5th amendment rights to keep silent, or at least your 1st amendment rights. Unless it was evidence to be used to convict someone else, then they could subpoena it.
Well, to answer my own question, on Freshmeat there appear to be one or two.
Have fun!
299,792,458 m/s...not just a good idea, its the law!
Galileo: "The Earth revolves around the Sun!"
Score: -1 100% Flamebait
Even if the NSA has *really* big hardware, even 1024 bits is a serious challenge. About 5 years ago, it was estimated that with current hardware, 1024 bits could not be cracked before heat-death of the Sun occurs. Even with today's hardware and (perhaps) improved factoring algorithms, it's still a pretty big challenge. The NSA is only going to devote serious computing power to very, very few things (e.g. terrorism).
Unless they've already got quantum computers. IBM's best effort so far is cracking a 4 bit(!) number using quantum, but expect huge budgets to be devoted to quantum factorising now.
HH
"(NSA, CIA) have no authority to get a court order
They no longer need it if you are suspected of any "terrorist activities". whatever that means.
"The US can't force you to give up your encryption keys "
See above and see Patriot Act and Homeland Security Act. They can force you if its for the good of the state, oops, I mean if its for the "security" of the state.
Operator, give me the number for 911!
The real reason a symmetric algorithm is used for the bulk of an SSL session is that it is much less computationally intensive than an asymmetric algorithm with a similar degree of security.
Note that these algorithms are independently pluggable, so a more secure or larger key size asymmetric algorithm could be used alongside the same old 128 bit RC4.
The big problem here is for systems using browser managed certificates for authentication would have to be upgraded and new certs issued. This is not the most common usage of SSL, but where it is in place the systems tend to be large and expensive.
Or more correctly, the new algorithm operates in the cube-root of the time of the original. (I'm pretty sure factoring is still an exponential search problem. Would someone who knows this algo better than I comment?)
At any rate, it's not quite as impressive as if an exponential search had been made polynomial. Rather, the exponent in the exponential search's runtime has been divided by 3. (Still a very big deal.)
In terms of big-Oh, it went from O(x^N) to O(x^(N/3)).
--JoeProgram Intellivision!
... create random noise to be used in a 'one time key' / 'one pad key'. Totally unbreakable. Especially if the message is short.
I remember the post you are referencing. There are cameras that photograph a number of lava lamps. Thru a couple of data munging operations, out pops a length of completely random data.
This was posted on some crypto/compression list awhile back about compressing totally random data. The guy was able to do so by underspecification of the problem. It was slashdotted, I believe.
Anyways, the same thing can be applied to picking up atmospheric noise/wind. Anything that cant be predicted or known at any other location should work for random data, thus you could use to encrypt. It is a "One Time Key" - no way to recreate the data without the data.
That square root thing is only for the most naive type of search using Grover's algorithm. It doesn't apply to many other kinds of searches. For example integer factorisation is much faster that sqrt time using Shor's algorithm. It may be there's also a sub-sqrt time algorithm for AES if someone actually looks for it - and AFAIK nobody has.
-- SIGFPE
For the past 50 years, that's been the case.
> I suppose this very well could be the case, but it sure lends itself to great conspiracy theories.
For the past 50 years, that's also been the case ;-)
Most of us older /.ers grew up believing that the mods to the S-boxes in DES were probably backdoors. Turns out they were to secure the algorithm against differential cryptanalysis, which didn't get discovered outside of NSA until recently.
NSA is still reputed to be the largest employer of mathematicians on the planet. They're reputed to have more supercomputing power than any organization on the planet. Both allegations are reasonably well-substantiated.
> I suppose the TLA agencies don't really need strong crypto to invade on my privacy. They just need a court order.
Correct. NSA's got two missions - secure American computing and communications, and 0wn every one else's ;-)
Not only is it easier to get a court order to make you give up your keys (or to eavesdrop/keylog you while you enter them), it's a hell of a lot safer.
The funniest part of Cryptonomicon is where the Brits are busy sending bombers to "see" German shipping but not bomb it. (If they just bombed the Germans, the Germans would realize that their crypto had been broken.) One of the protagonist's jobs, as an information theorist, was to figure out just how often they could get away with "just bombing them" and how often they had to make it look like they "got lucky" with a chance overflight or other observation.
The hardest part of crypto isn't breaking your opponent's codes, nor is it securing your own secrets. It's securing the big secret, namely not acting in a way that proves you've broken your opponent's codes.
Knowing your enemy's "A" team plans to attack tomorrow at dawn is good, but if you take out the "A" team 5 minutes before dawn, you run the risk of losing your ability to monitor the "B" team.
The TLAs will just install a wiretapper on your keyboard anyways.
I was always partial to the maryann scale, myself.
I feel fantastic, and I'm still alive.
No, it isn't. RTFA.
For very large keys, where the definition of "very large" is not yet known, this is a 3x decrease in the (for lack of a better term) 'effective key length'.
In other words, it might be possible to crack a 1536 bit key in the amount of time it currently takes to crack a 512 bit key.
Since the 1536 bit key is 1024 bits longer, that means that it *should* take 2^1024 (1.79e308) times as long to crack.
So, for that specific example, assuming that this works it's actually cracking the key 179 million trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion times faster.
Sounds like a few orders of magnitude to me.
ZFS: because love is never having to say fsck
No, someone has been spreading around an erroneous interpretation of the paper. From the abstract:
"This reduction of total cost from L^(2.852...+o(1)) to L^(1.976...+o(1) means that a ((3.009...+o(1))d)-digit factorization with the new machine has the same cost as a d-digit factorization with previous machines."
In plain terms: A factorization of a number that has 3 times as many digits will have the same cost as a the number did before.
Hope this clarifies why this is a breakthrough (that may be important).
...it's not clear this has any impact on crypto security today. There are lots of O(1)'s and nobody can be sure just how big they are for the real keys that are used today. Still, it can't do any harm to keep on your toes and make your keylength as long as your hardware will allow.
-- SIGFPE
That's true, but don't most AES/DES implementations depend on public-key encryption for key exchange? IIRC, the disadvantage of symmetric key schemes is that both parties need to have the same private key. While these can be easily exchanged using public-key encryption, that part might have suddenly become the weak link in the process...
Reminder: find a new sig
A friend of mine worked for Cray Computer Corporation until the untimely death of Seymour Cray. The last machine they were working on was a monster, that might make more sense in terms of today's developments.
In the early nineties, CCC was working on the Cray 3, a new gallium arsenide computer. It was to have a cycle time of about 1ns (shockingly fast back then.) It was cooled by a high-pressure very high-speed mist of Flourinert suspended in helium. It was built as a series of wedges much like the Cray 1 and 2, although somewhat smaller. They built working prototype wedges, and were debugging them, while looking over their collective shoulders at the ground being gained on them by arrays of microprocessors.
One thing led to another, and it was clear that the Cray 3 would never be a commercial success. They were then given a contract to build what was called the Cray 4. The Cray 4 was a one-off machine using PIM (processor in memory) chips. These were 1-bit computers, but there were 262,144 of them in the box. The idea was that the gallium arsenide chips, wiring, and cooling system that made up the Cray 3 were just the networking system for these PIM chips, which would do the actual work.
Anyway, Cray died, and then CCC quickly died, and I don't believe that the machine was ever finished.
thad
I love Mondays. On a Monday, anything is possible.
Well i couldn't get to the original site, but i see that NEC's citeseer has it.
True, perhaps I worded my reply too strongly.
But I am not content with possibilities and maybes. He has shown an effective way to greatly increase the capability of simple hardware to attack large integer factorization. This alone is enough to make me nervous. Do you really want to bet your security on possibilities?
I already use a 4096bit ElGamal key. I would suggest others do the same.
And regarding the rather tame developments in the crypto field (this is becoming old, well explored territory, not much new happens these days) I still think this is signifigant.
In terms of big-Oh, it went from O(x^N) to O(x^(N/3)).
Exactly. That means we have to make N three times as large as we thought we had to. This is not a catastrophe, except in high-security applications. But these should use something like "make absolute sure its enough bits and then quadruple the number" anyway...
Most ACs are not even worth the keystrokes to insult them. Be generically insulted and ignored otherwise.
What about the S-box modifications to RSA that the NSA did that strengthened it from differential cryptoanalysis. That was 20 years before the public sector re-invented differential cryptoanalysis.
There are 4 boxes to use in the defense of liberty: soap, ballot, jury, ammo. Use in that order. Starting now.
Wrong... in 1999, a group in Australia factored the RSA-140 challenge (140 decimal digits). This effort took roughly 3 months of calendar time using roughtly 300 computers (300MHz PC's and slower megahertz wise suns/sgi) for the seiving portion (parallizable) and then 1 cray (don't know specs) for the final step (which took less that 1 month). The RSA-155 challenge (512 bits) is estimated to only be 7.2 times harder CPU wise (versus the 1024 bit one, which is estimated at 40 million times harder). If I understand how this enhancement works, the algorithm is still not polynomial, but it should cut down the growth from 140 digits to 155 digits.
Any impact on DSA, as used by ssh and GnuPG ?
morcego
Diffie-Helman is not based on the knapsack problem (which is roughly: given a bunch of sack of various sizes (say, all of size 100) and a bunch of objects, what's the most efficient way of packing the objects into the (least number of) sacks?); DH is based on the discrete logarithm.
Note: people are interested in the knapsack problem because it is NP-complete to solve in general; the problem is that many (many!) specific cases are very easy to crack, and it's hard to tell a priori if you are generating such an example (a similar thing occurs in factor, in that there are some numbers that are much easier to factor than they may appear).
The discrete logarithm is as follow: recall that computing the logarithm (base b=10, say) of a number n is determining a number a such that 10^a=n. If you're working over the real numbers, this is easy to solve, and any calculator can do it quickly. On the other hand, suppose you are working in the integers modulo a prime p (imagine you're on a clock with p hours); then it's still possible to raise an integer b to a power a, getting a number n, and this is very quick. Say, given p=7 and b=5, and a=4, we get that 5^4 = 25*25 = 4*4 = 2 (modulo 7), so the discrete log base 5 mod 7 of 2 is 4. This is what Diffie-Helman relies on. Note that there are variants that work in different groups than this (a group is a mathematical object where you can add and subtract, roughly), particularly with elliptic curves, and these last are much touted as being possibly more secure than RSA or DH.
If the only way to factor a number was trial division then you would be correct. However the modern algorythms for factoring are much better than that, perhaps you are confusing symetric cryptography such as DES or AES with RSA.
I am unable to find a table online but in 83 a cray factored a 71 digit number in 0.1 Mips-year (1 million instructions per second for 1 year) Since the numbers are talking about are much smaller (50 digits vs 71 digits) and cpu's are much faster (> 1 billion ips) it would not be unresonable that a 50 digit prime could be factored in a few hours on a machine with suffecient memory.
This is about a threefold increase in factoring speed.. not an order of magnitude.
... to find out.
No. This is wrong. Read the paper.
For large keys, this method reduces the difficulty of factoring keys by a factor of ~3.009, i.e. the diffuclty of factoring a 90,000 byte key is now comparable to factoring a 30,0000 byte key using traditional methods.
It is unknown if this applies to smaller keys currently in widespread use, i.e. if your 2048 key will now have a factorization cost equivelent to that of a 683 byte key using traditional methods. That is what they guy wants funding for
So yes, this makes cracking keys orders of magnitude easier and faster.
The Future of Human Evolution: Autonomy
Heh. Not so long ago, there was a thread around here about Swordfish. Some smart alec came along and claimed that it was not realistic at all, just the usual Hollywood-overdone glamour, because it featured the best (still alive) hacker in the world cracking a 128-bit encryption system in about one minute...
The scary thing about the whole cryptography field is that the maths behind most cryptographic algorithms is really very simple (in "professional mathematician" terms, at least). You can obviously never know when a new technique is going to be uncovered within mathematical research that will undo years of "secure" communications in a heartbeat.
Hey, there are guys alive who can do incredible arithmetic feats in their head. Many of them can't explain how they do it, they just see things differently to the rest of us. What happens if someone comes along who can "just see" a large number as the product of a couple of prime factors...?
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
Seems you are right about the NSA employing more mathematicians than anyone else in the world. They believe this too. From a page on their web site:
NSA employs the country's premier codemakers and codebreakers. It is said to be the largest employer of mathematicians in the United States and perhaps the world. Its mathematicians contribute directly to the two missions of the Agency: designing cipher systems that will protect the integrity of U.S. information systems and searching for weaknesses in adversaries' systems and codes.
The needed approaches are radically different depending on whether you're trying to keep secrets from highly-skilled groups with plenty of resources (e.g. government agencies investigating you in particular), skilled groups with some resources (corporate espionage, small countries), snoopy ISPs (e.g. Comcast), skilled interested parties (IS groups), the casually curious (repair techs), and the unskilled (your grandmother). At the top end, you have to do all sorts of things that make using computers much more of a pain in the ass to keep them from adding keyboard sniffers, monitoring emissions, etc. At the low end, you have to learn how to hide files (using a .prefix or "hidden" flag, who cares) to keep your grandmother from being shocked by all that hot monkey lovin' in your porn archive. In between there are tradeoffs - how important is the information (do you need to keep it at all?), how important is it that it not be seen by others, how much inconvenience are you willing to go to to ensure that nobody else sees it?
Keep in mind that encryption isn't security. Encryption isn't even close to security. Encryption is a tool.
fencepost
just a little off
The methods described in the paper can be used to improve the cost of cracking EC discrete logs as well. The author, in a recent Usenet posting, points out that the paper's methods are likely to reduce the cost/effort of EC key cracking as well ... perhaps even more than RSA key
factoring.
The paper, combined with other other EC strength concerns suggests that EC is not the technology to turn to at the moment.
In other words, if this paper has you concerned about the security of RSA keys by factoring, then you should be even more concerned about the safety of Elliptic Curves as well.
But as others, including the author, have stated (in large friendly letters): DONT PANIC! It is not known if the ideas expressed in the paper are applicable to key sizes that are in common use.
chongo (was here)
Factoring 170-bit numbers is childs play. Anyone can do it.
::Alsee whips out pencil and paper and starts scribbling furiously::
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Umm, yes. Actually, there was a great big huge flaw in this - the lamps had harmonics at 60Hx (well, duh), and apparently the random genereation was based on the change in the picture at a particular point and another a time after it... Oh well, never mind, back to the this-mainframe-has-a-cosmic-ray-detector ideas...
James F.
According to dictionary.com Link Thus the entire security of RSA depends on the difficulty of factoring; an easy method for factoring large prime numbers would break RSA. So it looks like we've been going about it all wrong. We should be concentrating on factoring large prime numbers. :)
--"Karma is justice without the satisfaction"
The paper suggests a way to improve some of the steps required (such as some of the linear algebra work) to factor using the Number Field Sieve (NFS) for large keys.
The paper does NOT give a method to improve the speed of cracking EC keys.
Special purpose hardware could reduce the cost of cracking an RSA key. However: The same could be said of cracking an EC key. Using different special purpose hardware and different performance tuning, one should be able speed up cracking of EC keys as well.
So ... If the existence of ideas to improve
the speed of cracking sufficiently large RSA
keys scares you and you worry about that
might come next,
then you should be even more worried about EC.
Why? Not because of the exact idea outlined in the paper. The paper does not apply to EC. Because EC is subject to special purpose hardware improvements: perhaps even more than RSA.
chongo (was here)
He's observed that current factoring algorithms use asymptotically more memory than CPU. For a sufficiently big problem, all of the cost of the machine goes into buying memory, which spends most of its life waiting for the CPU to get around to it.
It's the same idea that motivated the Connection Machine.
He's observing that if you use the right (low-memory) algorithms, you can trade off memory for CPU and get something for which the total cost, memory+CPU, grows more slowly with problem size.
But it's not clear that's we've reached the CPU bottleneck yet. RAM is really cheap these days, so it's quite possibly premature to worry about the growth rate of that term.
Remember, the paper is part of a grant application. "I have this neat idea, and I'd like to study how practical it is."
More concretely, if all his ideas pan out, he can factor a 3*n+k-bit number for the same cost*time that GNFS can factor an n+k-bit number. What's k? Nobody knows! That's what he wants to study. If it's 1024, there are no immediate security issues. If it's 128, we need to deal with it.
(The claim in the abstract, (3.009...+o(1))*n, is more accurate, but the casual reader might not notice that o(1) can be significant and negative for currently interesting problem sizes.)
So while it deserves careful attention, let me add, in large, friendly letters: Don't Panic .
Indeed - the RIPA (Regulation of Investigatory Powers Act) of 2000 has sections under which one can be imprisoned on failing to 'hand over' keys to the authorities on request; the burden of proof of lack of ability to hand over said keys lies with the defendent; to quote:
53
(1) A person to whom a section 49 notice has been given is guilty of an offence if he knowingly fails, in accordance with the notice, to make the disclosure required by virtue of the giving of the notice.
(2) In proceedings against any person for an offence under this section, if it is shown that that person was in possession of a key to any protected information at any time before the time of the giving of the section 49 notice, that person shall be taken for the purposes of those proceedings to have continued to be in possession of that key at all subsequent times, unless it is shown that the key was not in his possession after the giving of the notice and before the time by which he was required to disclose it.[emphasis mine]
The act also makes it an offence to give notice that one has been given notice to divulge a key.
However, it should be noted that although this act came in to force in 2000, the code of conduct has yet to be released by the HO (presumably because they're having difficulty working out when to release it so as to best avoid a fuss in the media; maybe they should consider hiring Jo Moore), so no-one will have been prosecuted under this act yet (assumedly).
Oh, BTW, IANAL and all that #include stddsclmr etc...
James F.
128 bit keys almost always refers to a /symmetric/ algorithm - this is things like AES, Twofish, IDEA, etc. And for good symmetric ciphers, 128 bits of key is fairly secure - to brute force, you have to try out all 2^128 possible keys, which is a very hard problem (assuming, of course, that there aren't other problems with the cipher).
/assymetric/ ciphers - public key cryptosystems, and in particular RSA. RSA keys are made up of two large primes multiplied together (IIRC - it's been a while since I read this part of Applied Cryptography): finding the two primes breaks the key, and so its security is based on the difficulty of factoring really large numbers into prime constituents.
This article is referring to
The research referred to here is a way to speed up the factoring of large numbers, apparently by a factor of about 3 - it doesn't break the algorithm, it just speeds up a brute force attack. If it took 3000 years to break a 2048 bit RSA key before, now it'd take 1000 years. Barring more such discoveries . . .
Don't panic is a very good response to this - it's a serioius discovery, and it changes the risk factors involved with using RSA crypto, but it doesn't throw everything out the window.
Finally, I'd really suggest reading at least the interesting bits of Applied Cryptography, by Bruce Schneier. It explains a lot of this stuff, and gives you a good framework within which to put this kind of thing.
himi
My very own DeCSS mirror.
I don't think it'll be an issue.
All it does is speed up a brute force attack.
/did/ break RSA completely - ie, by indicating that factoring is in fact a P problem rather than NP complete - then it would have made infinitely more of a splash than it did. That kind of breakthrough is Nobel Prize type stuff.
If it
himi
My very own DeCSS mirror.
It doesn't speed up the factoring by a factor of three, it increases the keylength it can break by a factor of three . . . In other words, this version of the NFS algorithm runs in the cube root time of previous versions.
/doesn't/ break RSA, it merely speeds up the attack.
This is more significant than a simple three times speedup, but it still doesn't change the fact that it
himi
My very own DeCSS mirror.
I'm happy to rumormonger with you all for a little while...
I hear things from various people that I shouldn't hear, not often, but occasionally. These are people who are rather credible - not totally, but rather. I feel pretty confident in this particular "rumor," because I've heard basically the same set of facts from three different people with three different kinds of intelligence community experience.
What I hear is that your assertion is true. The NSA has had the ability to break RSA cyphertext "for some time." Even extremely large key sizes are said to be vulnerable, and they can do it "reasonably quickly."
This, of course, flies in the face of all accepted non-defense conventional wisdom in the field - at least until today - but, as I said, three sources. So I believe it.
This may be the result of harrowing secret advances in factoring techniques, or it may simply be brute force. This is an agency that has historically measured its computing power in acreage.
So, "reasonably quickly." The other part of this "rumor" is that reasonable is not reasonable enough to do RSA decryption on a large scale, and hence, while they can break open a particular piece of data, they haven't necessarily integrated RSA see-thru into their global signals intelligence regimine. That, for the uneducated/head-in-the-sand types, is Echelon - and yes, the NSA does listen to, and data-mine, almost all of the world's information traffic.
Final piece of this particular story: the NSA is apparently fastiduous about not sharing this technology, even with other federal agencies. Kevin Mitnick's infamous laptop, rife with PGP-encrypted documents, was impenetrable to the FBI, and despite numerous, desperate appeals for help, the NSA refused to assist them in decrypting the data. That suggests the NSA is abiding by their charter, which basically forbids them from becoming involved in domestic law enforcement (i.e. they're not supposed to spy on Americans) - a necessity if you consider consitutional guarantees about "search and siezure" applicable (by no means a universally held view, unfortunately).
We're on the road to Tycho.
Wasn't somebody doing something similar at the recent RSA conference...Blasting through multiple rounds of DES and factoring RSA keys on smart cards with some magic boxes?
You're using her as bait, Master!
I recompiled PGP back in 1994, after looking through the source code and finding a variable called (I kid you not) "MAX_KEY_LENGTH=1024".
I changed it to 8080 or some such strange number, and it ran just fine.
On a 386-33 it was *slow* to generate the keys, and of course no one was compatable, but it was trivially easy to do.
I wonder why the keysize limits on GPG still demand only 2048 or smaller. Why bother?
Bob-
The Ludwig von Mises Institute. The reasoning individuals economics
I'm a person who has quite an interest in crypto and often a good understanding of the base concepts behind crypto systems, but I don't understand much of the math that goes into proofs like this. Thus, I'd like to put some questions out to those who are more experienced than I am.
First, does this work? Have people independently verified that DJB is correct? (I went looking for some peer review via Google and didn't turn up anything that looked conclusive.)
Secondly, what's vulnerable? As I understand it, what DJB has discovered is a more efficient method of factoring numbers (on custom hardware) such that keys three times longer can be factored in roughly the same time. RSA is based on the product of two relatively prime numbers, so it's vulnerable. Aren't most public key systems based on this principle, though? How vulnerable is, for example, DSA to this new factoring technique?
--Phil (This article went up yesterday; hope someone's still around to read my post...)
355/113 -- Not the famous irrational number PI, but an incredible simulation!
No, what was being done at the RSA conference was completely different, wonderfully practical, and available today. It's a way of cracking RSA and DES implementations in smart cards using Differential Power Analysis and Differential Fault Analysis.
There was a company at the conference that was cracking these codes by very carefully watching the power levels on the input traces to the chip. By careful analysis, you can see exactly what is happening, what numbers are being sent to the various S-Boxes in DES for instance. From this, you can determine the DES keys. They said that single DES took a couple of minutes, triple-DES only three times as long. They claimed to be able to crack RSA as well.
Differential Fault Analysis involves giving the wrong voltages to the chip, and seeing how, and when, it fails. Again, this provides clues to what numbers are being processed within the chip.
Neither of these flaws point to problems with the algorithm, but to problems with its implementation. In fact, creating inexpensive physical hardware to do secure cryptography may be impossible.
What was remarkable at the RSA conference is that most of the other booths at the trade show were selling these same smart cards, in abject denial of their flaws.
thad
I love Mondays. On a Monday, anything is possible.
262,144 didn't make a lot of sense to me, so I figured it as a power of 2 -- 2^18th. Odd. It also counts for 512^2, or 4 banks of 2^16th. Only somewhat more logical... but it still doesn't make much sense to me.
The choice of number seems... unusual. Is there some special signifigance or particular reason for that number? Any ideas on how this particular approach would be applied? (Am I missing something, or was it just that point where the economy of scale was most favorable?)
"...America's great minds of today, teaching America's great minds of tomorrow. Poor bastards." -- A Beautiful Min
But it'd be a discovery at the same kind of level that /would/ win one in a field where a Nobel was offered. Which is what I meant - "Nobel Prize type stuff" doesn't mean it'd win a Nobel Prize, just that it's roughly equivalent.
himi
My very own DeCSS mirror.
My boss said he heard that rot-13 might be crackable! So I told him to switch to triple-rot13.
now we need to go OSS in diesel cars
Depends. Are you already using an 8k bit key?
now we need to go OSS in diesel cars