Posted by
CmdrTaco
on from the lotsa-bits-in-there dept.
ccshan writes "Adi Shamir, the "S" in "RSA", discovers a factorization method that renders 512-bit keys vulnerable to cryptoanalysis today. "
(its at the NYT:you know what that means)
Re:forget factoring - quantum cyphers is where its
by
Anonymous Coward
·
· Score: 2
QC is not at all like conventional crypto -- it takes advantage of two corrolated properties of a photon (or other particle), usually the x and y spins of a photon. Corrolated properties are subject to Heisenberg's principle, so unless you know the right way to set your polarizer, you get garbage, and the two sides know someone is listening in because they're getting garbage too. However, to make this work requires a communications channel which preserves spins of photons -- which conventional networks do not, and technically is very hard, so don't expect QC to be something you can use for some time.
Re:Prime-contest
by
Anonymous Coward
·
· Score: 3
You are thinking of Euclid's proof for the existence of infinitely many primes.
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.
You know, this explains why the government stopped bitching about RSA and dumped any legal action against the PGP folks all of the sudden a couple of years back. I suppose NSA figured this out and decided to keep it to themselves....
----
-- Every year during my review, I just pray the words "slashdot.org" aren't mentioned.
...I found out that the design of DES was optimized against a technique (differential cryptanalysis, I think) that wasn't "discovered" by the public academic community for another 20 years!
This was allegedly the reason why "they" didn't want to allow IBM to release how they 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.
-- "Ten years from now, they could do it in a few seconds." --
The Racketeer of the Hellfire Club, 1993, Phrack 42
Time to up the keys size...
by
strredwolf
·
· Score: 2
There goes 512 bit keys in PGP. I'd best revoke my key and rework it on the Linux box.
But this means we could see a way of speeding up Distributed.net's RC-64 contest!!!
--- Spammed? Click here for free slack on how to fight it!
--
--
# Canmephians for a better Linux Kernel
$Stalag99{"URL"}="http://stalag99.net";
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.
-- ERROR: Null.sig, core dumped.
Re:Security through openness
by
YogSothoth
·
· Score: 2
Ah, I see what you are getting at - rereading my original post I can see how it might be misinterpreted. My point was that this "hole" in RSA was only found because the algorithm is public (a good thing). An encryption algorithm that wasn't public might well contain an equivalent hole but since it wouldn't be subject to scrutiny it would continue to appear secure. As far as "noone would trust...", I'm not so certain - many companies use FlexLM to license their software and I've never seen any mention of the algorithm FlexLM uses. (admittedly I may be wrong here, I've not done exhaustive research to find out what sort of crypto FlexLM uses - it may well be published somewhere). My overall point was that with published algorithms one can have confidence in their quality because people are actively trying to break them whereas with proprietary algorithms you just have to trust the vendor.
-- there are two kinds of people in this world - those who divide people into two groups and those who don't
Security through openness
by
YogSothoth
·
· Score: 4
Interesting article - it shows again how important it is to only trust those algorithms that are open, published and subject to the scrutiny of the community. I am always amazed by the number of companies who really believe that keeping their encryption algorithms or security holes secret somehow makes them more secure. On a related note, I've often wondered if someday someone will find a fast, general algorithm for factoring. Such an algorithm might exist but be as yet undiscovered or it may be the case that brute force is about as good as can ever be done. Fascinating stuff, cryptoanalysis - I strongly recommend reading Applied Cryptography by Bruce Schneier to anyone who is interested in this sort of thing.
-- there are two kinds of people in this world - those who divide people into two groups and those who don't
Re:Security through openness
by
Jeffrey+Baker
·
· Score: 2
I'm not sure what you mean. The RSA algorithm is well-known and has been studied by cryptanalysts and cryptographers exhaustively. Nobody, not even suits at large corporations, would trust a cryptosystem with an unknown algorithm.
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:Security through openness
by
fishbowl
·
· Score: 2
"I am always amazed by the number of companies who really 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.
-- -fb
Everything not expressly forbidden is now mandatory.
It's called the Lucas-Lehmer test
by
Sesse
·
· Score: 2
The exact formula is given og GIMPS' pages, see my last comment.
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 */
FWIW, the (NIST) is currently evaluating several candidates for the new Advanced Encryption Standard (AES). This standard will presumably become the officially approved US Gov encryption methodology. One nice thing about this project is that most of the candidates have made their algorithms available for public scrutiny. Furthermore, it appears that there is concern about IP issues (e.g., patents).
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.:)
The AES is for a new symmetric encryption algorithm, to replace the tremendously outmoded DES. This has nothing to do with public key cryptography.
Re:Factoring technology
by
Andreas+Bombe
·
· Score: 4
No, there is no known plaintext. You don't encrypt the message, you encrypt a key for conventional cryptography and encrypt the message with that one. And the key you encrypt is (and should be, or you have a problem) a random number of which nothing is known about by an attacker.
quantum cryptanalysis = TEOTWAWKI
by
parallax
·
· Score: 3
Each bit added to a number makes it exponentially harder to factor using a classical computer. Factoring techniques will improve, but there is no reason to believe anyone will ever develop a polynomial time factoring algorithm for a classical (non-quantum) machine.
Factoring large numbers in polynomial time is one of only two known algorithms 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 lots of 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
-- parallax
Re:Factoring technology (check out RSA's website)
by
incubus
·
· Score: 2
They explain at rsa.com that (as another mentioned here already) the secret key for regular encyption is the only thing encrypted by public key, so you don't have to worry about how big your message is. The rsa FAQ is pretty interesting
If I'm not mistaken, RSA becomes free in September 2000 (patent expiry). Maybe this is RSA's way of "planned obselecance".:)
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.
Uh, do you realize how slow 4096-bit key generation is? Sure, computers are always getting faster...but you have to realize that the state of the art machine is not the 'baseline' platform. You also have to realize that these things need to work with cpu-poor devices, like smart cards. EC cryptosystems help this out to a degree, but they are no panacea either.
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
Shor's Algorithm (Re:Security through openness)
by
mrust
·
· Score: 2
Actually, if you stretch your definitions a little, somebody has found an efficient factoring algorithm. Peter Shor's algorithm will factor a number in polynomial time, trouble is it only works on a quantum computer.
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.
It's about the increase in computer power, not RSA
by
BIFFSTER
·
· Score: 3
Shamir has designed on paper a parallel machine that can crack 512 bit keys in a 'reasonable' amount of time.
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...
The problem is that Mersenne's formula does not reliably generate primes, i.e. a portion of the primes returned by (2^n)-1 [where n is itself prime] are _not_ primes. Hence all Mersenne primes generated via (2^n)-1 have to be tested to make sure they're bona fide, hence expensive computations required:)
Cheers Alastair
-- -- "I believe the human being and the fish can coexist peacefully." - George W. Bush, 29 September 2000
Slashdot Mirror
QC is not at all like conventional crypto -- it takes advantage of two corrolated properties of a photon (or other particle), usually the x and y spins of a photon. Corrolated properties are subject to Heisenberg's principle, so unless you know the right way to set your polarizer, you get garbage, and the two sides know someone is listening in because they're getting garbage too. However, to make this work requires a communications channel which preserves spins of photons -- which conventional networks do not, and technically is very hard, so don't expect QC to be something you can use for some time.
You are thinking of Euclid's proof for the existence of infinitely many primes.
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.
----
Every year during my review, I just pray the words "slashdot.org" aren't mentioned.
But this means we could see a way of speeding up Distributed.net's RC-64 contest!!!
---
Spammed? Click here for free slack on how to fight it!
--
# Canmephians for a better Linux Kernel
$Stalag99{"URL"}="http://stalag99.net";
Mind-bending stuff, really.
h enfeld.html
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
There is one major problem with this premise.
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.
ERROR: Null
Ah, I see what you are getting at - rereading my original post I can see how it might be misinterpreted. My point was that this "hole" in RSA was only found because the algorithm is public (a good thing). An encryption algorithm that wasn't public might well contain an equivalent hole but since it wouldn't be subject to scrutiny it would continue to appear secure. As far as "noone would trust ...", I'm not so certain - many companies use FlexLM to license their software and I've never seen any mention of the algorithm FlexLM uses. (admittedly I may be wrong here, I've not done exhaustive research to find out what sort of crypto FlexLM uses - it may well be published somewhere). My overall point was that with published algorithms one can have confidence in their quality because people are actively trying to break them whereas with proprietary algorithms you just have to trust the vendor.
there are two kinds of people in this world - those who divide people into two groups and those who don't
Interesting article - it shows again how important it is to only trust those algorithms that are open, published and subject to the scrutiny of the community. I am always amazed by the number of companies who really believe that keeping their encryption algorithms or security holes secret somehow makes them more secure. On a related note, I've often wondered if someday someone will find a fast, general algorithm for factoring. Such an algorithm might exist but be as yet undiscovered or it may be the case that brute force is about as good as can ever be done. Fascinating stuff, cryptoanalysis - I strongly recommend reading Applied Cryptography by Bruce Schneier to anyone who is interested in this sort of thing.
there are two kinds of people in this world - those who divide people into two groups and those who don't
The exact formula is given og GIMPS' pages, see my last comment.
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 */
(This comment is of course GPLed.)
FWIW, the (NIST) is currently evaluating several candidates for the new Advanced Encryption Standard (AES). This standard will presumably become the officially approved US Gov encryption methodology. One nice thing about this project is that most of the candidates have made their algorithms available for public scrutiny. Furthermore, it appears that there is concern about IP issues (e.g., patents).
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.:)
No, there is no known plaintext. You don't encrypt the message, you encrypt a key for conventional cryptography and encrypt the message with that one. And the key you encrypt is (and should be, or you have a problem) a random number of which nothing is known about by an attacker.
Each bit added to a number makes it exponentially harder to factor using a classical computer. Factoring techniques will improve, but there is no reason to believe anyone will ever develop a polynomial time factoring algorithm for a classical (non-quantum) machine.
Factoring large numbers in polynomial time is one of only two known algorithms 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 lots of 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
parallax
They explain at rsa.com that (as another mentioned here already) the secret key for regular encyption is the only thing encrypted by public key, so you don't have to worry about how big your message is.
The rsa FAQ is pretty interesting
If I'm not mistaken, RSA becomes free in September 2000 (patent expiry). Maybe this is RSA's way of "planned obselecance". :)
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.
æeee!
Uh, do you realize how slow 4096-bit key generation is? Sure, computers are always getting faster...but you have to realize that the state of the art machine is not the 'baseline' platform. You also have to realize that these things need to work with cpu-poor devices, like smart cards. EC cryptosystems help this out to a degree, but they are no panacea either.
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
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.
Shamir has designed on paper a parallel machine that can crack 512 bit keys in a 'reasonable' amount of time.
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.
The problem is that Mersenne's formula does not reliably generate primes, i.e. a portion of the primes returned by (2^n)-1 [where n is itself prime] are _not_ primes. Hence all Mersenne primes generated via (2^n)-1 have to be tested to make sure they're bona fide, hence expensive computations required :)
Cheers
Alastair
-- "I believe the human being and the fish can coexist peacefully." - George W. Bush, 29 September 2000