Slashdot Mirror
A Mighty Number Falls
space_in_your_face writes "An international team has broken a long-standing record in an impressive feat of calculation. On March 6, computer clusters from three institutions (the EPFL, the University of Bonn, and NTT in Japan) reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number — 2^1039 - 1 — that is 307 digits long." The lead researcher believes "the writing is on the wall" for 1024-bit encryption. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."
For an embarrassingly parallel, strictly integer application like this, I think the logical next step is to attack it with FPGAs. For such an application, it wouldn't surprise me if a large Alterera FPGA could give you at least the same computation power as a large cluster, for a fraction of the price (both for the hardware and the electricity to power the thing).
To make laws that man cannot, and will not obey, serves to bring all law into contempt.
--E.C. Stanton
...is that most Certificate Authorities who have trusted certs in the major browsers / e-mail programs will NOT sign a certificate for any keysize greater than 1024 bits.
This artificial limitation is going to become more and more glaringly obvious as time goes on.
But with this kind of computation time, you just have to send lots of junk traffic to make them waste all their computing resources. If you send out 500 messages a day, only 1 of which has actual usable information in it, then they are going to be wasting a lot of computing resources just to find out which messages actually have usable information. With computation times this high, it would be easy to flood them with data so that they wouldn't have enough time to decrypt everything.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
The Navajo language basically served as a one time pad in WWII
No, they served as code-talkers. A one-time pad is a system whereby every bit of the encryption key is independent of the others (never reused, unlike codewords) and entropy is maximal. Simply translating stuff from one word to another is simple substitution, a simple code.
The reason Navajo Code Talkers were succesful wasn't because the scheme was particularly advanced. In fact, it would have been computationally trivial to break. However the messages relayed were only ever "tactical" in nature; i.e. communications in the field, of use during a fight, but old news in about 10 minutes. Had Navajo code talking been used to relay top-secret messages, it would have been broken fairly quickly. The reason for its success was that is was extremely cheap to implement for the US, and the secrets protected weren't valuable enough to spend huge effort on breaking. Economics, rather than mathematics.
Navajo wasn't used in Europe, because Germany had sent anthropologists to the US to learn native languages, anticipating precisely this scheme.
SCO employee? Check out the bounty
Really it's not that bad of an idea. Create something that looks like image spam. Hide the encrypted information using stenography in the image, and send it out to millions of people, including the intended recipient. Everybody except the intended recipient deletes the message. It makes it harder to track down who you are communicating with, and harder to find out which messages actually contain useful information. It's similar to in olden days when they used to put a secret message in the classifieds of the newspaper. Only the people who know that it was supposed to be there could actually get the hidden message, but it was there for everyone to see.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
Not sure if this is a new idea, but this topic got me thinking. Decrypting something means is really just a mathematical transform. We say its "decrypted" if the end result "makes sense". But what if we didn't know what the final data should look like? How would we ever know it was decrypted?
Decryption itself only makes sense once we know what method was used, ie RSA, DES, Blowfish etc. However what if that algorithm itself was dynamic and formed part of the encryption? Sort of like a more generalised version of onion encryption, ie encrpyting the same content a number of times using different algorithms. So that the algorithms used and the sequence in which they are used form a sort of "meta-key"
From TFA:
Is the writing on the wall for 1024-bit encryption?"The answer to that question is an unqualified yes," says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking."Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."Reading Lestra's comments, I get the feeling that he has a fairly high degree of confidence that they will succeed in making the leap to a mathematical generalization within a modest time frame.
Can any security researchers tell me what GPG key length I should be using in the real world to give me a good trade-off between computational simplicity and future security please? I'm only using crypto for email and secure file storage.
-P
Be my friend.
This has already been done as early as 10 years ago.
I was working in Eastern Europe on a now unclassified project, working against a low budget illegal foreign intelligence agency. They were selling and distributing porn CD's and DVD's with thousands of pictures, one or more of which would contain an encrypted stenographic message. Their contact would purchase the DVD at one of hundreds of little markets, and decrypt the proper image(s).
It was really quite a good plan. Not only were there many possible valid messages to one or more agents, but there were also an unknown number of false messages, they even may have even been all false messages that could only be put together by inference. However, since they were encrypted with PGP, we never were able to break that particular system before I left the project.
The real genius of the plan was that it brought them in some much needed cash as well.
The television will not be revolutionized.
I don't think there are any good estimates of the computing power of the NSA. I suspect everything, up to and including their power bill, is classified; you'd just be getting somebody's conjecture.
I'm not even sure that it's really raw 'computing power' that you'd want to try and assess, anyway; I was thinking about something like a novel way of factoring general numbers very quickly, something that could be implemented in specialized hardware. That doesn't seem too outside the NSA's traditional forte -- they have some good mathematicians and probably have relationships with hardware companies that would let them source a lot of (odd) stuff without anyone noticing.
I do think it's interesting to note that of the algorithms listed as part of the NSA's "Suite B" Good-Housekeeping-seal-of-approval list, all the PK systems are based on elliptic curves, and not prime factorization, for the trapdoor function.
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."