## RSA slightly broken 137

Posted
by
CmdrTaco

from the lotsa-bits-in-there dept.

from the lotsa-bits-in-there dept.

Posted
by
CmdrTaco

from the lotsa-bits-in-there dept.

from the lotsa-bits-in-there dept.

This discussion has been archived.
No new comments can be posted.

Any sufficiently advanced technology is indistinguishable from a rigged demo. - Andy Finkel, computer guy

## Re:Time to up the keys size... (Score:1)

## Re:This explains a lot (Score:1)

20years!And this is in mathematics(!), a field where dollars don't drive discoveries. What do they know about cloning, chip technology and other areas where good funding is the most significant obstacle to discoveries?

## Adi Shamir can play great poker! (Score:1)

You can imagine my suprise as i saw this article at the NY Times, this guy was EXTREMELY convincing and there was no way to tell from his face he hade already developed a way to crack his own system! WHAT A POKER FACE!!!

The lecture by itself was a fascinating experince, but now it has become

I wish i asked him if he thinks RSA would ever be

cracked...

try67 [mailto]

## Re:Shamir's machine and EFF's Deep Crack (Score:1)

And QC is hardly abuot to burst onto the scene... maybe in 20 years it will be ready for a non=trivial problem, but maybe not. Right now it can factor the number 4 with a little help. That's quite a ways from breaking a 1024bit prime. Also at best QC gives you a square root Order of speedup, which is impressive, but if yuo double your key length its sorted....

## unbreakable algorithms (Score:1)

And remember -- the algorithm isn't always (or, I believe, even usually) the weakest link in the chain.

## Re:Elliptic Curve Cryptography (ECC) Rulez! (Score:1)

Unfortunately, there's been LESS public research on ECC encryption than on factoring techniques. So you might just be switching to a system that has flaws that haven't been discovered yet.

## Re:HTTPS / SSL - What does this mean? (Score:1)

In the US, domestic versions of SSL clients and servers are limited by the U.S. Govt. to 168-bit symmetric keys and 1024-bit asymmetric keys. Export-grade software is limited to 40- (or in some cases 56-) bit symmetric keys, and 512-bit asymmetric keys.

## Re:This explains a lot (Score:1)

Remember that the NSA is the world's largest employer of mathematicians. It shouldn't be surprising that they have been able to make discoveries faster than anyone else.

## Re:forget factoring - quantum cyphers is where its (Score:2)

## Re:Prime-contest (Score:3)

Take all the known primes, multiply them together and add 1. Call this x. x is not divisible by any known prime, so either x itself is a new prime, or some unknown prime divides x.

Note that there is no way to ensure x itself is a prime. In particular, there is no known formula for generating another prime from any quantity of known primes.

## Going for pedant points. (Score:1)

10 INPUT "Prime number to be factored"; A

20 PRINT "The factors are:","1",A

The difficulty, as I understand it, has more to do with determining whether a given large number

isprime, or the product of two primes (and if so, which ones), or something like that.I don't really understand the math that makes the cool public key stuff work, but I do know that the special thing about prime numbers is that they don't

havefactors (beyond the trivial ones produced by my 2-line BASIC program above). Contrast 7 (prime) with 6 (non-prime), for example. Two times three makes six, but what, besides one times seven, makes seven?## Re:Not all public key systems... (Score:1)

## This explains a lot (Score:2)

----

## Time to up the keys size... (Score:2)

But this means we could see a way of speeding up Distributed.net's RC-64 contest!!!

---

Spammed? Click here [sputum.com] for free slack on how to fight it!

## QC = Quantum Computing (Score:2)

Check out openqubit.org; They're working on a simulator for these things...

There's a Scientific American on the subject at:

http://www.sciam.com/1998/0698issue/0698gers

## Re:Security through openness (Score:1)

BTW, RSADSI is probably the only cryptography company that had at a time proprietary cyptography systems trusted by the community (rc2 and rc4). Rivest effect, I guess.

OG.

## unless P=NP (Score:1)

I'm a bit rusty on this, but I seem to recall that if P=NP (which some belive true, but has never been proven) then ALL problems that cause public key encryption to work beomce vulnerable at the same time.

In other words we already know there is a simple way to go from factoring a big prime number to breaking ECC. Note that here simple means N time or something equally simple in comptuer terms. It does not mean we know what the simple procedure is, only that we already know there is some way to go from factoring primes to breaking ECC.

Or as my Professer in that ECC course I took a couple years ago liked to say "Until that unlikey day when someone proves a therom on chaos theory, this is unbreakable."

## Urm... (Score:1)

The public key is used to protect a 128 bit symmetric key (one time pad) in PGP. The symmetric key encrypts the plaintext. This is because the RSA method takes too long to use directly on the plaintext. Thus, we already have 2048 bit keys protecting 128 bit plaintexts.

## Re:huh? (Score:1)

In this case. The symmetric key used is a 128 bit key chosen at random (and thus in this case, it is a one time pad). The algo used is 3des. One time pad just means the key is meant to be used only once. In practice, most OTP keys are for symmetric algos.

## Re:What does this mean for Diffie-Hellman/DSS? (Score:1)

Are they crackable in the same short period of time?Based on the similarity of the problem, probably. The prudant move is to assume yes, and use longer keys. In fact, use longer keys for any public key system (1024 should be safe for a while, but use 2048 for anything really important.

## Re:This explains a lot (Score:2)

This was allegedly the reason why "they" didn't want to allow IBM to release

howthey designed and verified Lucifer (DES' precursor) and DES itself. They incidentally got this clue, and the "big guys" were afraid that someone else might get another clue how to break/analyse other crypto-systems (and find their weak points) easier. This is really long known.## Theoretically... (Score:1)

In other words, you're probably safe for about a week after Shamir reveals the algorithms (which I don't think he's actually done yet). Then, well, I'd look into stronger security.

## Re:Factoring technology (Score:2)

As the length of the key increases, so does the amount of pad needed to encode short messages. For example, if your key was 8kb long and you encrypted a 2kb e-mail message, you would have 6kb of padding. This means, among other things, that you have 6kb of known plaintext, and also, the large amount of pad would affect the output of the cipher so that the result isn't as random or difficult to decipher as it theoretically should be with that key length.

This is why increasing key length can only happen for a limited time, and we need to keep looking for better algorithms.

## Re:Security through openness (Score:2)

## Security through openness (Score:4)

## Re:Factoring technology (Score:1)

Random numbers are far better then known plaintext. Random numbers are also really hard to get on current machines. What we have is psudo-random (see the man page for random), and on some-OSes we-did-some-stuff-that-may-be-pretty-random (see /dev/random). Psudo-random isn't so much better then known plaintext, in part because sometimes it ends up being known plaintext (like if a program uses the "normal" method of seting the random number seed to the current time, you will amost know the random text). In part because the streams some RNGs make can be recognised.

Still psudo-random would be better then known-not-random.

Also the original message had a small flaw, eight times the current 2K *bit* key size is 2K *bytes*, which isn't way huger then many things you may want to protect. Still if we have to keep expanding the key space every few years it will become a real problem.

## No surprise, just a little dissapointment (Score:1)

It was good to see DES last for so long with no real "cracks" that weren't massive brute force. Even today, triple DES looks like it will be pretty strong for a long time.

At least with the openness of the algorithms in question, we'll at least be educated as to how strong they really are, under current technology at least.

## Re:Factoring technology (Score:1)

## DETAILS!!! Where are the details!!!!???? (Score:1)

Currently, with packages like maple and mathematica, on a decent box you can factor primes that are reasonably big, but nowhere near in the range of what RSA uses. This special "machine" Shamir says he's thought up...I need the details!!!

## Re:HTTPS / SSL - What does this mean? (Score:1)

This is diffrent from the asymmetric encryption methods used for PGP, and their strenght is measured differently as well.

A good page to get very basic knowledge on this... Which is incidently where I got this from can be found at the following site.

http://www-users.informatik.rwth-aachen.de/~sen

## Re:Anyone ever seen sneakers? (Score:1)

## Re:Prime-contest (Score:1)

The prize is $50,000 for the first 1 million digit prime, $100,000 for the first 10 million and so on up to 1 billion digits. It all goes to you.

/* Steinar */

## RSA has not been broken (Score:1)

Repeat: RSA has not been broken. Shamir has only found a better way of factoring numbers (but he hasn't even made the machine he's been talking about).

/* Steinar */

## I think I forgot something... (Score:1)

3. Take the number modulo 2**n-1 (the prime itself)

Otherwise, you could never end up with zero, of course.

/* Steinar */

## It's called the Lucas-Lehmer test (Score:2)

I believe the formula is. Start with 4.

Do this n times (n = the exponent):

1. Square the number.

2. Subtract two.

If (after n iterations) you end up with zero, it's a prime.

/* Steinar */

## Re:Security through openness (Score:2)

The closed part of most closed cryptosystems is the implementation. Of course, nobody should trust a crypto implementation for which they do not have the source, lest the code be mailing your private keys back to the manufacturer/NSA/whomever.

-jwb

## Re:connection down (Score:1)

---

## Re:AES (Score:1)

## AES (Score:3)

This was taken from the AES site:

A process to develop a Federal Information Processing Standard (FIPS) for Advanced Encryption Standard (AES) specifying an Advanced Encryption Algorithm (AEA) has been initiated by NIST. NIST is currently soliciting candidate algorithms for inclusion in the AES. It is intended that the AES will specify an unclassified, publicly-disclosed encryption algorithm available royalty-free worldwide, that is capable of protecting sensitive government information well into the next century. It is also hoped that this standard will be as widely accepted as the Data Encryption Standard (DES) in the private and public sectors.I looked at one of the algorithms, but it just made my head hurt.:)

## Re:Factoring technology (Score:4)

## Re:SLIGHTLY! (Score:1)

What, me worry?

## Re:quantum cryptanalysis = TEOTWAWKI (Score:1)

We need a catchy, or at least pronounceable name,

if we want widespread adoption.

## If it doesn't work can the patent lift? (Score:1)

the "apparatus" being patented has to work?

That way they stopped people patenting perpetual motion machines and so on...

## Re:Security through openness (Score:2)

believe that keeping their encryption algorithms or security holes secret

somehow makes them more secure."

It buys them time...

If they publish their weak code or their security

holes, they are in trouble right away. Otherwise

they are in trouble, maybe, at some unspecified future time. "They" can live with that. One way

they get money, one way they do not.

Another thing to consider is the soft job market.

The people who wrote your code don't work there anymore, by and large. This is the downside of the ease of finding high-tech jobs, but I digress.

## HTTPS / SSL - What does this mean? (Score:1)

Anyway, What does this mean for my https server? I only allow 128bit or better clients, but does this mean potentially anyone sniffing the packets in between me and the clients would (given this nifty new hardware) be able to see everything that is being sent? (or at least with a far greater degrree of ease than before?) I'm afraid I'm not up on my crypto..

## quantum cryptanalysis = TEOTWAWKI (Score:3)

Factoring large numbers in polynomial time is one of only two

knownalgorithms for quantum computers. A modest quantum computer, if it could be built, would crack every prime-factorization cryptosystem currently in use (which is everything, essentially).Researchers here at the Media Lab have already built a two quantum-bit bulk spin-resonance quantum computer. There are significant technical challenges to building a quantum computer large enough for cryptanalysis, but there is currently no reason to believe that this is impossible. If it can be done, it will almost certainly be done in the next five to ten years; major governments and private companies all over the world are pouring

lotsof money into this effort.RSA is good, but we need to start developing cryptography algorithms which aren't factoring based (or reducible to prime factoring), and we need to start NOW. If there isn't a strong, widely-available non-factoring crypto implementation if/when the quantum computing breakthrough happens, all hell is going to break loose.

You're worried about the banks dropping a few transactions on Y2K? How about someone spoofing the Federal Reserve Banking Netowrk and bringing the global economy to its knees.

parallax

## They don't know for sure if it will work... (Score:1)

if it works. And the computer to use this new calculation hasn't been built yet, so no need to worry. But the article also stated that this machine would be cheap to build, so it would be exciting to see what it gets to## Prime-contest (Score:1)

## Re:Guys , IT DOES MATTER how long your message is (Score:1)

Having a large text gives them more to look at... but I don't think it makes decryption faster... maybe there's something with that differential cryptanalysis.

Besides.. you could switch symmetric keys every once in a while if neccessary.

## Re:Factoring technology (check out RSA's website) (Score:2)

The rsa FAQ is pretty interesting

## Nope! Re:Fixed size cyphers (Score:1)

Perhaps you are thinking of certain symetric cyphers like DES or IDEA. Both have fixed key lengths. However, many other algorithms don't suffer from such a limitation. A good example is Blowfish, which (IIRC) has a key length from 64 to 448 bits, variable.

Check out Applied Cryptography for examples of other variable-length cyphers.

Whether increasing keylength is a good idea or not, though... 128-bit keys are secure against any brute force search for a

verylong time ( even at 1 billion billion billion try/sec (ie 2^27)) it takes ~8e22 YEARS to break. Increasing a key further than this is silly. Symetric algorithms are invulnerable to advances in factoring and related math; they are vulnerable only to weaknesses in their underlying design.-Erik

## Re:Anyone ever seen sneakers? (Score:1)

## Re:HTTPS / SSL - What does this mean? (Score:1)

The symmetric key is used for encrypting the data itself. However, obviously both sides need to have the key for it to work. The first step in SSL is a key exchange mechanism. Typically a symmetric RC4 key is generated by the client, then sent to the server encrypted with the server's public RSA key. Other ciphers are available as well but the RSA / RC4 combination is the most common.

## Re:Not all public key systems... (Score:1)

My memory is a bit fuzzy, but I remember there were a large number of PK systems before RSA that were proposed and then cracked in rapid succession.

## Re:Not all public key systems... (Score:1)

## Re:Factoring technology (Score:1)

Is this overly easy or am I missing something?

## Factoring technology (Score:3)

Because it relies on the product of two large primes, RSA will always be vulnerable to advances in factoring technology. In about five years, even the 1024-bit keys may become easily breakable. Until a real method to factor numbers faster than currently becomes available, we are going to find that RSA is still the most powerful encryption algorithm available (security vs. speed). I would recommend that the minimum key length in bits be increased to at least 8 times the maximum for easily broken keys.

In this case, 512 is easy to break, so 4096 should be the standard. This should yield a number of years of security. And, as always, make sure you give your keys one-year expiry dates.

## Re:Prime-contest (Score:1)

## Re:Prime-contest (Score:1)

## Re:Anyone ever seen sneakers? (Score:1)

## Re:Shamir's machine and EFF's Deep Crack (Score:1)

## SLIGHTLY! (Score:1)

They knew when they published, they've watched half a hundred stumbling steps and laughed, and finally, after selling bogus security for 15 years, they laugh all the way to the bank and disprove themselves, so we can pay them more money to fix what they knew was broken.

## Re:Well, so much for... (Score:1)

your posession or shared amoung two or more people, then it's no longer

secret, authentic, or trustable. "

And we used to laugh at people who protected their images, would not allow photographs for fear of loss of the soul?

Were we? Are we? clever? Ever?

## Uh, I don't know about that... (Score:1)

CJK, frantically trying to finish up his crypto semester project (due tomorrow), which deals with discrete log public key crypto

## Uh, not so fast.. (Score:1)

(and I'm not sure that the statement about no patents is necessarily true)

But yes, ECC _is_ cool...but needs more research. Lots of people would be a little wary of implementing it, since EC cryptosystems haven't gotten as much scrutiny as of yet.

CJK

## Wow, lay off the crack... (Score:1)

CJK

## ??? What are you talking about? (Score:1)

Sure, this shows a weakness in RSA (but if you are using 512-bit keys right now, you are living dangerously as far as what's recommended)

Shamir's discovery doesn't imply any weaknesses in the entire class of public key cryptosystems based around discrete logs. (or other public key cryptosystems not based around prime factorization, such as some knapsack types and McEliece, based on algebraic coding)

The one time pad is impractical for all but a very narrow group of scenarios.

CJK

## Not all public key systems... (Score:1)

CJK

## ?? What you're saying makes no sense. (Score:1)

CJK

## Re:Not all public key systems... (Score:1)

You have ElGamal, based on discrete logs...(and the discrete log problem generalizes easily to allow for many many many variants on the same principle). DSA is based on discrete logs, too.

Most EC cryptosystems are based on an analog of the the discrete log problem on a finite field...generally a more intractable problem than the general discrete log problem (except for a few degenerate cases, in which it reduces to the problem of discrete log in a finite field).

McEliece, based on algebraeic coding theory...

I think there is one cryptosystem based on the knapsack problem which is yet unbroken (most knapsacks are shown to be weak)

CJK

## Re:quantum cryptanalysis = TEOTWAWKI (Score:1)

CJK

## Whoa (Score:1)

This is kind of dumb...it's easy to make up additional or new names as part of your marketing which are catchy/easy to remember.

CJK

## Practical Issues??? (Score:2)

Sensible key sizes are a much better solution. Using the max key size 'just because it's there' is just wasteful (and slow as hell).

CJK

## Okay, here's a question (Score:1)

cryptogeek> this? First, these advances only apply

cryptogeek> to public-key encryption, not

cryptogeek> secret-key encryption schemes like

cryptogeek> DES.

Isn't all encryption using a fixed-length

key solvable by a non-deterministic machine

in polynomial time? If a password was a maximum

of x characters with y characters in its alphabet,

wouldn't a non-deterministic machine just have

to spawn off y^x copies of itself and try each

combination in parallel? Or am I missing

something here?

## Re:Anyone ever seen sneakers? (Score:1)

## Not published yet (Score:1)

## Re:quantum cryptanalysis = TEOTWAWKI (Score:1)

Actually, last I heard the MIT Quantum Computer was a *long* way from Prime Time. I don't remember the details, but the techniques that work for a two qubit quantum computer will not work for anything much larger -- and the two qubit version was difficult enough.

There's no real rush yet. I think we have a number of years to go before Quantum Computing treatens cryptography.

## Quantum computing-- not the end of the world (Score:1)

So how is the situation _better_ than this? First, these advances only apply to public-key encryption, not secret-key encryption schemes like DES. Second, quantum mechanics also opens up new possibilites for key exchange that were not available before. In particular, quantum mechanics can be used to distribute random key material for a one-time pad over a public medium. There's a good overview of the process in the Oct. 1992 Scientific American, but the main idea is this: Quantum entities (photon, electrons, fundemental particles) change when observed. Therefore, someone can send out the random key material in the form of a stream of photons, and the reciever can tell if they were observed in transit.

This is a Good Thing, cryptographically speaking, because one-time pads are proven to be _unbreakable_. Furthermore, this type of key exchange has already been one, over distances as long as 30km (I believe).

So quantum computing would change things, certainly, but it's not the end of the world.

(For those interested, Schneier's _Applied Cryptography_ and the _Handbook of Applied Cryptography_ by Menzes, van Oorschot and Vanstone are good general references. As mentioned above, the quantum key distribution method can be found in Scientific American, Oct. 1992. Peter Shor's home page is here [att.com]. There's lots of information on quantum computing on the web, but a good place to start is here [qubit.org].)

## Re:Okay, here's a question (Score:1)

My reply would be that quantum computers are not non-deterministic. A non-deterministic machine is one that is allowed to make guesses, or choose between multiple possibilities. To say that a non-deterministic machine can solve something in polynomial time usually includes the unspoken assumption that the machine _always guesses correctly_. So, yes, secret key encryption is probably breakable by a non-deterministic machine in linear time-- the machine simply guesses each bit of the key correctly. However, I don't think anyone has actually built a non-deterministic machine.

A quantum computer, on the other hand, can be in multiple states simultaneously-- until you look at it. When you look at it, however, it collapses into one of its component states RANDOMLY. For example, suppose you have a quantum bit ("qubit"). This bit can be in either of the two classical states: |1>, or |0>. It can also be in any combination of the two, such as (a * |1> + b * |0>). (The coefficents a and b, by the way, can be complex numbers.) When you look at the bit, on the other hand, it will collapse into one of the two classical states randomly, with the probabilites given by the values of a and b.

So, as opposed to a non-deterministic machine, a quantum machine can look at all options simultaneously but will only show you one outcome. It may not be the outcome you want, and once you look at it _all the other outcomes are gone_. The trick of quantum computing is to cleverly massage the values of a and b until you can be sure that it will collapse into an outcome you want. (This is the essence of Shor's algorithm.)

If you want to know more, look at http://www.qubit.org.

## Re:forget factoring - quantum cyphers is where its (Score:1)

hasbeen done.Over pretty large distances too...

## Shor's Algorithm (Re:Security through openness) (Score:2)

It's been proven that P QP (that is, the set of all classical polynomial-time problems is a subset of all quantum polynomial-time problems) Also, there are certain things that can be done on quantum computers more efficiently than a classical computer could (not just speculation, there are problems like this)

I wish I knew more about this stuff.

## Spine tingling - I thought of sneakers as I read (Score:1)

To be honest, I always thought that the movie 'sneakers' would remain fiction, with any attack done the 'brute' force way, which really made these cyphers intractable.

I thought that the story was well written, and this just proves it.

## forget factoring - quantum cyphers is where its at (Score:1)

Theoretically this cypher is the cypher to end all cyphers. I say 'theoretically' because that's the way it is for all codes, until perserverance and science break them.

But the quantum mechanical cypher is pretty convincing. Any one have good links?

## Re:They don't know for sure if it will work... (Score:1)

The article says if it works. And the computer to use this new calculation hasn't been built yet,That he is aware of. The governments have a way of keeping things real secret when its in the intrest of 'national security'. Ah well maybe I'm being paranoid.

## It's about the increase in computer power, not RSA (Score:3)

All this heralds is that computing power has acheived another milestone, and that it's gotten easier/faster to factor numbers - and thus crack crypto.

Let it be pointed out, though, that the difficulty increase for each bit increase is exponential, not linear, so 768/1024/2048 bit RSA keys should be safe for quite some time...

maybe 10 years? HHOS.

## Re:unbreakable algorithms (Score:1)

Since what you are combining with is totally random there is no way to crack this system. One decryption is equally as likely as any other. I'm looking forward to Tuesday to see what the paper turns out to be.

## Crack smokers and Popular Science readers (Score:1)

Traveling salesmen , smallest network and factoring primes are all problems that can be converted into one another in a linear ( or is it quadratic ? ) amount of time . Hence ; you solve one , you solve em all . No one has proven NP complete problems to be hard to solve .

It is a conjecturethat any of these things is difficult ( Given , it is a conjecture that has held up for a darned long time under intense scrutiny ). RSA and anything dependent on factoring primes or other NP complete problems may be trivially easy to break . If they are , we just haven't figured out the method yet .If they aren't , it is entirely possible that we will never be able to prove that they aren't . One way or the other I wouldn't hold my breath for quantum computing to make these things suddenly open up.

See also ( before the NSA bans publication ) :

Bruce Schnier's book : Applied Cryptography

2nd edition

Your Squire [mailto]

## Re:What does this mean for Diffie-Hellman/DSS? (Score:1)

conjecturethat factoring primes is difficult ( given that it has been abitchso far , it still hasn't beenprovento be difficult ) . I don't even remember if factoring primes has been proven to be NP complete .P.S. I believe the NSA is the single largest employer of Mathematicians in the world . Does that scare anyone ? I'm not frightened about the potential abuses

## Guys , IT DOES MATTER how long your message is (Score:1)

## Re:Prime-contest (Score:2)

Cheers

Alastair

## Re:AES (Score:2)

symmetricencryption algorithm, to replace the tremendously outmoded DES. This has nothing to do with public key cryptography.## Re:It's about the increase in computer power, not (Score:1)

## Re:It's about the increase in computer power, not (Score:1)

## Re:Shamir's machine and EFF's Deep Crack (Score:1)

## Re:Quantum computing-- not the end of the world (Score:1)

fiber for transmitting photons, right?), there's

still a huge problem here.

If, for example(!), the US government (or rather,

No Such Agency), wants to make using crypto

impossible (and I mean QC here), they simply

install `photon-watchers' in all the main backbone

nodes.

So, you get a one-time pad... but you see it was

observed. You then either communicate in clear

(as the key isn't secure anyway) or you

encrypt with the key, full knowing that someone

can decrypt it...

Which would imply that quantum computing kills

crypto no matter what... I *hope* I'm wrong there!

## Re:factoring prime numbers (Score:1)