Slashdot Mirror
1978 Cryptosystem Resists Quantum Attack
KentuckyFC writes "In 1978, the CalTech mathematician Robert McEliece developed a cryptosystem based on the (then) new idea of using asymmetric mathematical functions to create different keys for encrypting and decrypting information. The security of these systems relies on mathematical steps that are easy to make in one direction but hard to do in the other. Today, popular encryption systems such as the RSA algorithm use exactly this idea. But in 1994, the mathematician Peter Shor dreamt up a quantum algorithm that could factorise much faster than any classical counterpart and so can break these codes. As soon as the first decent-sized quantum computer is switched on, these codes will become breakable. Since then, cryptographers have been hunting for encryption systems that will be safe in the post quantum world. Now a group of mathematicians have shown that the McEliece encryption system is safe against attack by Shor's algorithm and all other known quantum algorithms. That's because it does not depend on factorisation but gets its security from another asymmetric conundrum known as the hidden subgroup problem which they show is immune to all known quantum attacks."
Don't start feeling too secure about the so-called McEliece encryption system - a candidate for the security of Internet traffic in the age of the quantum computer (2008 article)
When the foot seeks the place of the head, the line is crossed. Know your place. Keep your place. Be a shoe.
> If it can be engineered, it can be reverse-engineered.
How does that apply to this article, in any way?
Often wrong but never in doubt.
I am Jack9.
Everyone knows me.
It is worth noting that solving hidden subgroup problem is a subfield of quantum computing that has been active for a while. Although we can't figure out how to solve it in general, we can solve specific instances of it; for example, I think that factorizing is one such instance.
Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.
I see
Would ElGamal also be immune since it's based on Discrete Logarithms?
I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of our enemies. Would it be possible to develop one of these in secrecy?
If it can be engineered, it can be reverse-engineered.
That only works for "security through obscurity" type of problems. A good encryption should not be "solvable" - it must be brute forced. The question is how expensive the brute force method is in processing power and time.
It doesn't apply to this article. The way that one typically breaks a cryptosystem is not by reverse engineering (which is not even meaningful here, given that the algorithm is already completely open), but by finding a clever new way to solve the mathematics underlying the system using less information than the designers of the system had thought was needed.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.
This is not a brute-force attack. The article refers to a method of deriving the private key from the public key (which is available for anyone to download).
Send a bunch of encrypted e-mails containing questionable content and see if anyone comes knocking at your door. And be sure to not send any questionable content unencrypted, or to give any other reasons for them to show up.
You can lead a horse to water, but you can't make it dissolve.
Symmetric algorithms are at least in their second generation (DES/Lucifer now AES) of production use, with decades of study and close analysis by a lot of good minds.
Asymmetric algorithms are still essentially the first generation. Take RSA. It has been out for so long that its patent has expired more than 15 years ago. Even elliptic curve cryptography has been out at least 20 years, because the NeXT had it in NeXTStep 3.0 (and ended up getting pulled out of the OS due to ITAR).
Even cryptographic hashes have been through a number of iterations. We had MD4, then MD5, then SHA-1, then SHA-256, now are looking for something to replace SHA, similar to how Rijndael replaced 3DES and DES.
Maybe it is time to have a contest to have a standard asymmetric algorithm to replace RSA, DSS, and ElGamal? Something fundamentally designed to resist quantum computer attack as well as other threats.
Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.
From TFA:
However, it's worth pointing out that while the new work guanratees safety against all known quantum attacks, it does nothing of the sort for future quantum attacks. It's perfectly possible that somebody will develop a quantum algorithm that will tear it apart as easily as Shor's can with the RSA algorithm. "Our results do not rule out other quantum (or classical) attacks," says Dinh and co.
"I don't care about the Constitution!" --Bill O'Reilly, November 17, 2009
Seriously, Slashdot gets it wrong EVERY TIME. Next time, would it kill the editor to go to http://www.caltech.edu/ and, you know, read any of the words on the page?
Actually, with really hard-core crypto systems there are three traditional ways to break them: 1) rubber hose; 2) dumpster diving; or 3) box of chocolates/bouquet of roses.
I think you are too optimistic. I do not mean that "THEY" have one (I do not know/not answer). The issue is that the statement should read:
After all, why limit it to only "ours" enemies after spending so much on it?
Why can't
Of course, that presumes a purely random one-time pad.
Mod parent up... It is surprising how true that is.
Actually, with really hard-core crypto systems there are three traditional ways to break them: 1) rubber hose; 2) dumpster diving; or 3) box of chocolates/bouquet of roses.
What no wad of Cash xor hookers & blow?
And a secure system for transmitting this pad from the sender to the receiver.
A sociological observation is that Shor was an undergrad at Caltech when McEliece was a professor there formulating the cryptosystem that would resist the quantum algorithm that Shor would develop years later. I wonder if knew each other.
1) I think (hope) you mean WPA2, not WEP2...
2) The proof for the perfect security of OTPs only applies if the pad is random. Not pseudo-random. You seem to be describing what amounts to a very primitive psuedo-random number generator, using pages of books as seeds. If you are not using random information, it is incorrect to call it a one time pad.
"linux is just DOS with a UNIX like syntax" -- Galactic Dominator (944134)
Wow you're ignorant. Or a very subtle form of funny.
Randomly generated one-time pads are definitely unbreakable. But the problems are generating the key and getting the key to the target as the key is as big as the text. So if you're using this to encrypt a connection, you need to split a 1Gig key, physically hand it to the target, and then you have 1Gig of communication before you need to hand him another stack of pads. It's good for sending code-words and like, emergency e-mails or something, but not constant communication channels.
Wait... you're using a pad for the key to a WEP2 encryption? And you're using books to generate the pads... that's... wow dude. Just wow.
It doesn't apply to this article. The way that one typically breaks a cryptosystem is not by reverse engineering (which is not even meaningful here, given that the algorithm is already completely open), but by finding a clever new way to solve the mathematics underlying the system using less information than the designers of the system had thought was needed.
So, you're saying 640k should be enough?
- Dan.
~ People that think they are better than anyone else for any reason are the cause of all the strife in the world.
The only encryption method I've heard about that has not been found to be breakable is the one time pad. This method has the problem of exchanging the pads beforehand.
All of the major encryption machines used during WWII appear to have been broken. The new encryption methods are currently much harder to break, but the spooks are likely to discover some innovative method to break such algorithms.
Current methods using large prime numbers sounds like they are soon (next few decades) to be broken. If we got into a war where breaking these methods became important, I'm sure that quantum computers would soon become available, if they aren't already. Even if quantum algorithms aren't available, someone might come up with a way to calculate prime factors using a bacteria colony through DNA molecules. A method may cost a million dollars per factor found, but sometimes that is small change for the information gained.
I'm sure that there are groups looking for the next level of encryption. Something that isn't compatible with quantum methods, or requires it to reverse the encrypted data. Making it take longer and be more expensive to break is the goal of encryption.
Who would win this election: Andrew Weiner vs Andrew Weiner's weiner.
W8, why both of them wouldn't work?
One that hath name thou can not otter
That falls under the generalization of (3).
(1) Threat/intimidation/violence
(2) Exploit a careless mistake
(3) Bribery/persuasion
I suppose (1) and (3) even could blur together into "influence" (negative and positive).
...the future crusty old bastards are already drinking the Kool-Aid.
In the morning.
I think he's saying that this article does not qualify for reverse-engineering ;)
I don't think XOR is the appropriate logic operator. cash is not mutually exclusive from hookers and dope as a bribe.
In the simplest of terms
I thought the whole point of the quantum computer was was it did the equivalent of brute forcing every single possible answer simultaneously
instead of checking a password say from
a ..z ..az ..bz
b
c
aa
ab
ac
ba
bb
bc
so a one letter password (normal computer) can be checked in 26 steps, and a 2 letter password in 676 steps..
each once then proceeding,
and on a quantum computer, I thought it threw the equivalent of the OED (all possible answers, all possible combinations) at the same time.
but only responding with the correct answer
will someone please tell me where my basis is way off?
every day http://en.wikipedia.org/wiki/Special:Random
I don't think XOR is the appropriate logic operator. cash is not mutually exclusive from hookers and dope as a bribe.
True but when you mix the two something odd happens and all of the money gets overwritten with blow somewhere in the FIFO buffer...
WTF... OK... I can deal with slashdot being overrun by morns who know little but act big, but now we have to put up with text-ese ?
His UID is lower than yours so shouldn't it be "I can deal with that slashdot was overrun by morns who knew little when I signed up. (eol)"
Quantum computers only provide a quadratic speedup for search problems like brute-forcing cryptography. Current secret key algorithms are safe.
Maybe he did, maybe he didn't.
Infuriate left and right
I love you too... but it's a secret remember?
I can engineer a dead flower by leaving a live flower on a table without water for a week. Can you reverse engineer a living flower from that dead flower?
Cash is actually the superposition of hookers and blow.
I purpose we petition for a grant to study this theorem in extreme detail as it just might lead to a grand unifying theory with black jack.
This exchange is illustrated here:
http://imgs.xkcd.com/comics/security.png
and hookers. Okay, forget the Black Jack!
-- Posted from my parent's basement
This is a newer ID. I have been on slashdot since '99
There is an old paper, written by DJB, which gives a quick introduction to some (this and) other quantum computer resistant encryption methods: Introduction to post-quantum cryptography
yes, take the seeds in it and plant them.
Easy,
Here is a link to the paper on the arxiv:
http://arxiv.org/abs/1008.2390
Reading through the abstract, I see that a significant feature of this cryptosystem is that it cannot be solved by "strong Fourier sampling", which makes the situation more interesting because it is only a slight exaggeration to say that quantum Fourier transforms are the only trick we know of that lets us get exponential speed-ups in quantum algorithms.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.
I call shenanigans. No hot girl sends pictures to someone who posts on Slashdot.
This is a newer ID. I have been on slashdot since '99
... yeah ...
It's worth noting that social engineering is quite often the cheapest method. I was at a conference back in 1999, where a Navy guy pointed out that in 'red team' testing, they'd found that the typical Systems Administrator would roll over for an average of $7000. No, I don't know how the details of how they conducted the test.
One could argue (or hope) that _most_ SysAdmins these days are more cognizant of the risks, so probably not as casual as they used to be.
It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
This doesn't rule out other methods of speeding up using quantum tricks. Also, keep in mind that this may all be for naught since no work of this form can rule out the existence of a fast classical algorithm for handling the problem. Thus, implicitly, all these sorts of results are interesting primarily if one assumes that these sorts of problems don't lie in P. The good news is that the hidden subgroup problem is very likely not in P.
There was an app named iGnore, which was rumoured to hide Apple stories from the Slashdot website.
Unfortunately, anyone who used it only saw a blank screen and assumed it was broken.
Regardless of whether or not his method is "good enough" (it probably is), it's not a OTP unless it uses actually random pads. By definition. If it's using a PRNG instead of a RNG, it is called a stream cipher.
'One time pad' is a term of art. In technical discussions about cryptography is should only be used where technically correct.
"linux is just DOS with a UNIX like syntax" -- Galactic Dominator (944134)
How do you brute force (or solve) a one-time pad, where the pad was created from random atmospheric noise or any other truly random source?
[...]
The only downside (and it's really not much of a downside) of OTP technique is that you need the pads before you need the message. However, I actually can't think of a situation where that would seriously inconvenience modern users of the technique.
Oh, and how do you unbreakably update OTPs in the field? Easy: You encrypt them with the last/reserved OTP the other end has. Cyclic encryption of truly random numbers? Incomprehensible. It's just another 100% opaque data stream. Done deal.
I've fallen off your lawn, and I can't get up.
There still being a flower means there will be no seeds (yet) though.
I thought it had been proven that quantum computation was a pipe dream (you can't physically compute 2^N operations with less than 2^N atoms). Is the hypothesis still considered plausible ?
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.
It's worth noting that social engineering is quite often the cheapest method. I was at a conference back in 1999, where a Navy guy pointed out that in 'red team' testing, they'd found that the typical Systems Administrator would roll over for an average of $7000. No, I don't know how the details of how they conducted the test.
One could argue (or hope) that _most_ SysAdmins these days are more cognizant of the risks, so probably not as casual as they used to be.
Not disputing your point, but regarding the seemingly low number: the job market may have had an effect, too; 1999 was a very good time to be in IT. Quitting one job and picking up a couple months' salary in cash probably looked a lot better than it would for most people now.
A fair point, but I would say that the number is at least one, maybe two orders of magnitude too low. $7000 is pocket change, probably less than the red team paid to fly there (wherever 'there' was). It says that a sysadmin would sell out what must be viewed as a multimillion dollar asset (not to mention their self-respect) for pennies on the dollar. To me it means that the sysadmins had no respect for their jobs, their profession, their responsibilities. If you're going to be a sleazebag crook, at least do it for what it's worth. If you steal a Mercedes you don't sell it for $100.
It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
Although I'm working with cryptography, I must admit there are a lot of technical ways to circumvent it, the cryptography will only help to rise the cost of those technical ways. And to be really secure, you must have special computers in special rooms in addition to using cryptography.
ResoMail - the alternative secure e-mail system
How does that apply to this article, in any way?
I don't think you'd be surprised by how many upmods you could get by replying with old saying to just about any topic.
You can even pick one at random, post it in the next news item without even readin it and you'll have big chances of at least a +1 (insightful) among all the offtopics.
Back in the day (1980) where I worked we were trying to get some computer graphics terminals 'TEMPEST' certified. For those not familiar, this was a standard for minimal leakage of EMI, such that folks outside the building could pick up the noise and figure out what you were typing on your keyboard, or what direction and speed the plotter pen was moving, or even (I suppose) the memory addresses put on the bus - and certainly the large EMI coming off the high voltage guns for the display tubes, which could tell you what was on the screen.
The interesting thing was that the standard was classified. We would send our equipment for testing, and they would send it back and say only 'nope, not yet' - no clue to how it failed. We would then have to try to figure out what to do to improve it.
It was totally understandable - knowing the standard would provide information on how to defeat it. But it was a very puzzling way to work.
Interestingly, I see that according to the Wikipedia article TEMPEST is still valid terminology, and the standards are still mostly classified.
It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
Still a young'n. Heh, n00b!
sig: sauer
I guess you think "2ndcoming" is nothing like "W8"
I hold it, that a little rebellion, now and then, is a good thing. -- Thomas Jefferson
Now that makes sense.
Often wrong but never in doubt.
I am Jack9.
Everyone knows me.
A fair point, but I would say that the number is at least one, maybe two orders of magnitude too low. $7000 is pocket change, probably less than the red team paid to fly there (wherever 'there' was). It says that a sysadmin would sell out what must be viewed as a multimillion dollar asset (not to mention their self-respect) for pennies on the dollar. To me it means that the sysadmins had no respect for their jobs, their profession, their responsibilities. If you're going to be a sleazebag crook, at least do it for what it's worth. If you steal a Mercedes you don't sell it for $100.
Or that those sys-admins feel like Peter Gibbons in office-space so they see it as an opportunity to cash in.
Just saying...and there are a lot of thieves that would sell the Mercedes for $100 if it means easy out of the situation.
Truth is like the sun. You can shut it out for a time, but it ain't goin' away. - Elvis Presley (source: imdb.com)