Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Cryptogram: AES Broken?

chrisd posted more than 11 years ago | from the small-s-boxes-lead-to-weirdness dept.

Encryption 277

bcrowell writes "The latest CryptoGram reports that AES (Rijndael) and Serpent may have been broken. The good news is that when cryptographers say 'broken' they don't necessarily mean broken in a way that is practical to exploit right now. Still, maybe we need to assume that any given type of crypto is only temporary. All of cryptography depends on a small number of problems that are believed to be hard. And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy."

cancel ×

277 comments

Jennifer! (-1, Troll)

Anonymous Coward | more than 11 years ago | (#4264912)

Thank you! You are the best!

SUCK MY PUSSY (-1, Troll)

Anonymous Coward | more than 11 years ago | (#4264919)

Re:SUCK MY PUSSY (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#4265057)

Jennifer, is that you? Should I start calling you Jennifur-burger instead?

I always thought you were a whore.

Quantum computing for white hats (3, Insightful)

kingpin2k (523489) | more than 11 years ago | (#4264922)

Wouldn't the same quantum computing that allows people to break today's crypto enable white hats to use increasingly complex algorithms and S-boxes to protect data? I mean, it's not as if crypto crackers are going to have these bad ass machines while the good guys sit around on 486's, right? Am I missing something?

Re:Quantum computing for white hats (-1, Troll)

tomstdenis (446163) | more than 11 years ago | (#4264933)

Am I missing something?

Yeah an education.

Re:Quantum computing for white hats (0)

Anonymous Coward | more than 11 years ago | (#4265000)

Shut up, Tom. He had a perfectly valid question.

Re:Quantum computing for white hats (0)

Anonymous Coward | more than 11 years ago | (#4264942)

Depends who you think the good guys are.

Re:Quantum computing for white hats (2)

tanveer1979 (530624) | more than 11 years ago | (#4264946)

Not really missing.. but the point is that bad guys upgrade first step ahead of good guys. first we have the virus and then we have the anti-virus.. not the ohther way round.. The problem is that quantum computing will make the coverable space huge.. So "good guys" will not really know what they missed and finding something goodies missed will be randomly possible... now all the random theory shit i cant put here, but the biggest challenge in quantum crypto is mapping the coverage, a lot of loopholes can be left of everything is uncertain.... and our knowledge of quantum mechs is still infantile.

Re:Quantum computing for white hats (1)

BESTouff (531293) | more than 11 years ago | (#4264965)

The problem is that old encrypted data doesn't "evolve" with the computing/crypto capacity.

Imagine some black hat just archived all encrypted data he could get (bank transactions, private conversations, you name it) then decrypts them in 10 years when he can buy his brand new quantum computer. All this old data may prove very valuable for him.

Perhaps very sensitive data shouldn't even transit on the net because you can't tell if it'll be decryptable in the future.

Re:Quantum computing for white hats (1)

ch-chuck (9622) | more than 11 years ago | (#4264974)

Can't you just see the global super-villian of the future - instead of having a planet destroying laser/particle beam of immense proportions, s/he'll have built the ultimate quantum computer, with a cadre of white frocked genius hacks slithering around coding decryption algorithms, holding clipboards and turning dials on outdated 9-track tape units. "See, with this ultimate weapon, Bond, I'll be able to penetrate the defenses of even your highly vaunted NSA/CIA defense complex, muhahahahah!".

Yes, you're missing something. (2)

Kjella (173770) | more than 11 years ago | (#4264982)

The underlying idea of both symmetric abd asymmetric cryptography is that there exists operations that are very asymmetric. For example, multiplying two numbers together is extremely much faster than factoring them, and there are several other.

Quantum computing changes this balance. So your white hats won't be able to multiply a billion times faster even if the black hats can factor a billion times faster.

Kjella

Re:Quantum computing for white hats (3, Informative)

smallfries (601545) | more than 11 years ago | (#4264985)

No.

Slightly different quantum computation will do though, quantum crypto allows transmission of entirely secure messages, that is an unbreakable system. It isn't guarenteed by the hardness of a couple of mathematical challenges but by the actaul laws of physics themselves. Not only can a quantum crypto stream not be broken, but it can detect when somebody attempts to listen in. This has been demonstarted using both air and fibre as a transmission system (can't be arsed to google for a link but there should be plenty out there, it was textbook for our quantum computation course).

On the other hand, a quantum computer would break all the old cryptosystems quite easily (not sure about eliptic curves), however they are years away from being feasible and there are a lot of hard problems to solve first.

Re:Quantum computing for white hats (0)

Anonymous Coward | more than 11 years ago | (#4265042)

um could you explain me how 2 particles separated can be linked together

i mean i thought that you could not separate two particles far away for that they keep their link

Re:Quantum computing for white hats (0)

Anonymous Coward | more than 11 years ago | (#4265109)

It relies on an assumption that noone will be able to play man in the middle on both the quantum and standard connection between the communicating parties ... if someone manages to put himself in between the two parties on both lines all bets are off (you will have to rely on standard cryptography if you want absolute certainty of this not happening).

Re:Quantum computing for white hats (1)

jpvlsmv (583001) | more than 11 years ago | (#4265235)

Not only can a quantum crypto stream not be broken, but it can detect when somebody attempts to listen in.
Not really. A quantum-encoded message (what you refer to as a "quantum crypto stream") can not be observed by a third party without destroying the message.

An analogous real-world situation would be where you write a message across the "tear here" strip on an envelope. An interceptor can open the message, but destroys it in the process.

--Joe

I'm no mathematician, (1, Interesting)

3.5 stripes (578410) | more than 11 years ago | (#4264927)

Not even close, but isn't breaking encryption just a matter of throwing enough processor cycles at it until it finds a match?

Re:I'm no mathematician, (2)

sydneyfong (410107) | more than 11 years ago | (#4264958)

Sure you can try that (good luck!), but when it takes all the computers in the world to run for a few hundred/thousand years to get the result, or when the number of cycles is more than the number of atoms in the universe, it's basically impossible to find the match.

Re:I'm no mathematician, (1)

26199 (577806) | more than 11 years ago | (#4264989)

All the computers in the world for a hundred years would be a bit marginal, though... after all, things are always getting faster...

In fifty years, that could well be feasible... (who knows?)

What you really want is to need all the computers in the world working for several universe lifetimes, then you're *definitely* safe ;-)

Re:I'm no mathematician, (1)

Marlin099 (133736) | more than 11 years ago | (#4264976)

Yes, except that 'enough processor cycles' means hundreds or thousands of years of processor time for the major encryption standards as of right now. What they're talking about is a mathmatical 'shortcut' to find that key, a way to do the same thing in a much shorter amount of time, or cycles.

Re:I'm no mathematician, (2)

blancolioni (147353) | more than 11 years ago | (#4265005)

Not even close, but isn't breaking encryption just a matter of throwing enough processor cycles at it until it finds a match?

This is correct. But if you can show that a massively parallel computer the size of the Earth would take billions of years to crack your code, then you can feel reasonably secure. Factorisation of large primes is a task that (probably) falls into this category -- it hasn't yet been shown to be easier.

If, on the other hand, you're talking about trying every message against the encrypted text, then that doesn't work either, because (a) it takes even longer than cracking the code, and (b) any message is potentially the plain text.

Factorisation of large primes is easy (5, Funny)

Anonymous Coward | more than 11 years ago | (#4265145)

Contrary to what appears to be a prevailing belief on slashdot that it's difficult to factor large primes, with current advances in parallel computation and quantum computing this is actually quite an easy task. I present to you the following 1024 bit prime:

111961017586322450238441928964701918986406535146 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703

Now we have to factor it. We step up to the main terminal of our quantum computer beowulf cluster and type in the question, "Of which numbers is this the product?". Qubits flip, waveforms collapse, a cat in a box somewhere dies (of radiation poisoning, strangely, or charmingly), and out pops the statement:

111961017586322450238441928964701918986406535146 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703 * 1 = 11196101758632245023844192896470191898640653514665 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703

Re:I'm no mathematician, (1)

Rich0 (548339) | more than 11 years ago | (#4265223)

Factorisation of large primes is a task that (probably) falls into this category -- it hasn't yet been shown to be easier.

Probably not... Last time I checked the factors for a large prime are itself and 1.

Re:I'm no mathematician, (-1, Troll)

Anonymous Coward | more than 11 years ago | (#4265036)

I second that. You're no mathematician.

Re:I'm no mathematician, (0)

Anonymous Coward | more than 11 years ago | (#4265039)

Technically, yes. But you need an *awful* lot of cycles.

Let's say you've got a chip that can crack a 64 bit cypher in a day. Someone's given you a 128 bit cypher, and told you to work out a method of cracking that in a day. How many chips do you need?

The way the maths works is that for each extra bit, you need to double the number of processors. So for 65 bits, you need 2 processors; for 66 bits you need 4 processors, and so on. For 128 bits, you need 2^64 processors. That's 18 billion billion chips. That would cost a lot.

Re:I'm no mathematician, (1)

3.5 stripes (578410) | more than 11 years ago | (#4265079)

Thanks for all your replies, now know it's more about possible shortcuts/weaknesses than just brute force.

Definition of "Broken" (2, Informative)

therealmoose (558253) | more than 11 years ago | (#4265081)

Broken to a cryptographer means anything easier than brute-force. So in theory, this methed requires throwing less processor cycles at it than just totally random throwing, but it's still "just throwing processor cycles at it" in a sense. Broken to an engineer means something that is reasonable to do that cracks the code. That this is not (yet).

Re:Definition of "Broken" (1)

virve (63803) | more than 11 years ago | (#4265098)

Broken to a cryptographer means anything easier than brute-force. So in theory, this methed requires throwing less processor cycles at it than just totally random throwing, but it's still "just throwing processor cycles at it" in a sense.

Broken to an engineer means something that is reasonable to do that cracks the code. That this is not (yet).


Which definition does Microsoft use when describing said company's products?

quantum computers (2, Funny)

ch-chuck (9622) | more than 11 years ago | (#4264928)

And all bets are definitely off when quantum computers arrive on the scene.

couldn't these be described as "weapons of mass decryption"? [visions of 'sneakers' all over again]

Re:quantum computers (0)

Anonymous Coward | more than 11 years ago | (#4264963)

"Told my boss I'm sick of Software that Sucks and the lusers that use it - I'm using BSD and if you don't like it fire me"

If you worked for me I'd not only fire you, but make sure you never worked a day in your life again. The business world has no use for pretentious scum like you.

Quantum cryptography (1)

ljubom (147499) | more than 11 years ago | (#4264929)

I'm sure that quantum cryptography will be in everyday use long before quantum computers (it is much simpler concept, and there is number of experimental instalations), and quantum encrypted data are not breakable by any computers.

Re:Quantum cryptography (1, Informative)

gazbo (517111) | more than 11 years ago | (#4264960)

True, but I'd like to see you go to a new website and send your CC details to it via quantum encryption.

In those terms, quantum encryption sets us back to way before we had public key encryption. Except now it's not just key distribution that's the problem, but the actual comms link. I know I don't have the appropriate wire leaving my house to Amazon...

Re:Quantum cryptography (1)

smallfries (601545) | more than 11 years ago | (#4265041)

Some of the guys who do quantum research next door explained that they've demo'd routing qubits and normal bits across a fibre network. So the message header is normal bits describing where to route, and the payload is actual qubits that contain the encypted payload with all the usual guarentees, apparently it works although its a bit of a headf**k.

Re:Quantum cryptography (0)

gazbo (517111) | more than 11 years ago | (#4265067)

Seriously cool. I'd not heard of that technology.

Either way, it still seems to me that the age old key distribution problem is back. Unless there's any other tech you'd like to inform me about...

Quantum (2, Interesting)

caluml (551744) | more than 11 years ago | (#4264932)

Seriously, once quantum computers arrive, and we all have to ditch our factored encryption, what are we left with?
Is it really back to XORing our messages with random data known to both ends?
That sucks.

And the cry went up - make quantum computers illegal. Only terrorists want quantum computers... ;)

Re:Quantum (0)

Anonymous Coward | more than 11 years ago | (#4265206)

Actually you'll find that one of the most secure encryption algorithms are "One Time Pads". Read the bible of cryptography Applied Cryptography [amazon.com] by Bruce Schneier.

Re:Quantum (1)

The Original Yama (454111) | more than 11 years ago | (#4265251)

Maybe by then we'll have fractal encryption algorithms that not even the Borg can break ("it's extremely unlikely" -- Data, Star Trek: First Contact).

Or here's an idea: quantum encryption! I'll admit, I made that one up. But if Klingons are possible (I have one stored in my freezer right now) then anything is.

Why do people assume that while processors evolve to the quantum stage everything else stays essentially the same? By then we'll probably all have four butts from eating too much GM asparagus (the evil vegetable) and through genetic engineering.

Golden Age of Privacy (2)

marko123 (131635) | more than 11 years ago | (#4264934)

It will continue to exist so long as the average hacker has a computer within 2 or 3 orders of magnitude of power of the government. Easy.

quantum != exponential growth qjkx (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#4264935)

Don't you get to the point where all the atoms in the universe can't calculate the code before, say, the IPO? Just toss more bits at it.

Quantum computing =/= no privacy (3, Interesting)

deego (587575) | more than 11 years ago | (#4264937)

>And all bets are definitely >off when quantum >computers arrive on the scene. >Maybe someday we'll >look back fondly on the golden >age of privacy."

That, is untrue. Yes, when quantum computers arrive, they will decode encryptions done today in polynomial time.

But arrival of quantum computers does not mean an end to privacy. "Quantum Cryptography" invokes the fundamental laws of QM to guarantee that there's absolutely no way to decode a message thus encoded (without alerting the sender of a "wiretap"). It stands to reason that by the time Quantum Computers arrive bigtime on the scene, Quantum Cryptography will arrive as well.

The theories of the two ideas are well worked out, but the tech remains in its infancy.

Re:Quantum computing =/= no privacy (5, Informative)

stevelinton (4044) | more than 11 years ago | (#4265016)

Quantum Computing and Quantum Cryptography are unrelated technologoies. Quantum crypto is indeed "unbreakable", but requires a single physical channel connecting source and destination. It will not carry over routers and absolutely cannot be used for normal internet email for instance.

Quantum computing would break a range of encryption techniques, especially most public-key techniques, but nothing known today rules out new and more robust digital encryption technologies being developed that Quantum Computers could not break, and I imagine plenty of people are working on them.

Addendum (4, Informative)

seizer (16950) | more than 11 years ago | (#4265186)

It's probably worth noting that IBM has already demonstrated a quantum computer running a factoring algorithm:

(See here) [ibm.com]

Re:Quantum computing =/= no privacy (3, Insightful)

afidel (530433) | more than 11 years ago | (#4265190)

In fact elyptic curves appear to be immune to quantum techniques that have so far been postulated. This does not mean that a fast method will not be found to break EC's simply that there is not yet any knowledge of a technique that significantly weakens EC's.

Re:Quantum computing =/= no privacy (1)

AxelTorvalds (544851) | more than 11 years ago | (#4265176)

Mix and mash ciphers are immune to quantum cryptograpy. AES, DES, just about all symmetric block ciphers will not be any easier to break with it.

Quantum cryptography myths (0)

Anonymous Coward | more than 11 years ago | (#4265178)

It IS vulnerable to man in the middle attacks, if you manage to cut both the quantum connection and the "public" connection between the two parties and put yourself in between you have 2 completely functional communication channels "protected" by quantum cryptography to both parties.

The only way for them to distinguish you from the party they actually want to converse with is good old classical cryptography.

The end of privacy (5, Insightful)

bjelkeman (107902) | more than 11 years ago | (#4264939)

on the golden age of privacy

That is quite a funny statement. 99% of all email is being sent in clear text, often passing through gateways which have permanent wiretaps installed. Phone tapping is at an all time high in the west and there are cameras on nearly every street corner around where I live.

Privacy.... I had a lot more privacy 20 years ago, that is for certain.

Re:The end of privacy (2, Insightful)

Winterblink (575267) | more than 11 years ago | (#4265163)

Hah, too true. :) The "golden age of privacy" would be known more as the "golden age of privacy that nobody bothered to take advantage of when they could".

security thru obscurity (1)

buttahead (266220) | more than 11 years ago | (#4264941)

There will be privacy as long as you have something to hide, and the patience to hide it. Any kind of obscurity based privacy can be broken as well, but when quantum computers come, this may be more protection than an encryption algorithm.

Nostalgia... (1)

maya (90492) | more than 11 years ago | (#4264945)

Maybe someday we'll look back fondly on the golden age of privacy.

No. Sorry. No looking back. There was no golden age. Privacy has been replaced by security. We are shutting down your blog....

quantum crypto (2)

TechnoVooDooDaddy (470187) | more than 11 years ago | (#4264948)

When quantum computers come out, we'll develop problems that are believed to be hard on quantum computers...

we can not assume that either side of the crypto equation will remain dormant, using only today's technologies. The next Bruce Schneier [amazon.com] will happen along (or maybe the man himself) and we'll be dealing with the golden age of quantum cryptography.

Re:quantum crypto (0)

Anonymous Coward | more than 11 years ago | (#4264970)

Travelling salesman cryptography would be hard to solve with the current 'generation' of quantum computers.

I'm not sure how you'd make travelling salesman keys though!

gross oversimplification (3, Funny)

jukal (523582) | more than 11 years ago | (#4264951)

Basically, the attack works by trying to express the entire algorithm as multivariate quadratic polynomials, and then using an innovative technique to treat the terms of those polynomials as individual variables. This gives you a system of linear equations in a quadratically large number of variables, which you have to solve. There are a bunch of minimization techniques, and several other clever tricks you can use to make the solution easier. (This is a gross oversimplification of the paper; read it for more detail.)

Uhm. emm. EZ? :)

While we're on the subject of cryptography... (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#4264952)

OpenBSD creator Theo de Raadt has confirmed: his toy OS is dying. It's pallbearers are UltraSPARC, SPARC, Sun 2, and Sun 3. OpenBSD we hardly knew ye. [netcraft.com]

I broke it yesterday (-1)

neal n bob (531011) | more than 11 years ago | (#4264964)

with my handy overclocked TI calculator. It really wasn't too hard, and I'm not even good with numbers and stuff.

Nice article... (2, Funny)

26199 (577806) | more than 11 years ago | (#4264966)

...I love the first line:

AES may have been broken. Serpent, too. Or maybe not. In either case, there's no need to panic. Yet. But there might be soon. Maybe.

Lovely summary, guys :-)

Well... If AES isn't sufficient... (1, Offtopic)

Jugalator (259273) | more than 11 years ago | (#4264973)

... jr pbhyq whfg nf jryy fvzcyl hfr EBG Guvegrra gura? :)

Re:Well... If AES isn't sufficient... (1)

Tikiman (468059) | more than 11 years ago | (#4265087)

For the curious, a decoder [mchsi.com]

Maybe? (1)

mischief (6270) | more than 11 years ago | (#4264979)

maybe we need to assume that any given type of crypto is only temporary

Maybe? Since when has any crypto been considered even remotely permanently unbreakable?

Re:Maybe? (3, Informative)

Noryungi (70322) | more than 11 years ago | (#4265058)

Since when has any crypto been considered even remotely permanently unbreakable?

Since the one-time pad [std.com] , that's when. This has been mathematically proven, as well, as early as 1910 or 1920, if I remember well.

OTOH, it is true that a one-time pad is symmetric (sp?) crypto. modern crypto, such as AES, DES, Serpent and others mentioned in Cryptogram are assymetric, and, as such, more susceptible to cracking methods.

Re:Maybe? (2, Informative)

jonatha (204526) | more than 11 years ago | (#4265137)

modern crypto, such as AES, DES, Serpent and others mentioned in Cryptogram are assymetric

AES and DES are symmetric. Serpent probably is too, inasmuch as it was an AES finalist.

Re:Maybe? (3, Informative)

Dwonis (52652) | more than 11 years ago | (#4265151)

DES is symmetric, and I'm pretty sure AES (Rijindael) and Serpent are, as well.

Re:Maybe? (1)

troc (3606) | more than 11 years ago | (#4265103)

One time pads?

ok, not *permanently* unbreakable but a one time pad (assuming the 'pad is sent safely :) has certain advantages over normal asymmetric codes....

Sure they have drawbacks in distribution of pads etc which adds costs to the system but with nothing except some encoded text (and no plaintext to guess/assume, no other messages with the same pad) that really will appear random, to work on, the bad guys will have their work cut out. ;)

Troc

Re:Maybe? (2)

autocracy (192714) | more than 11 years ago | (#4265153)

It's all over the comments for his article, but I have to throw it in - the only widely agreed upon method of encryption that is "unbreakable" is the one-time pad. Do a search if you don't understand it. The concept is really fairly easy and widely documented.

Beyond that, all crypto is considered breakable - the question is the amount of computational effort required. A "perfect" cypher will require each possible key to be checked and each with have an equal chance of being correct (and of being wrong). A "broken" cypher allows a considerable shortcut in the process of discovering what it has been used to encrypt. This shortcut may cut the time required in half, it might make it happen only 5% faster. The question to be asked is: is the person who wrote the paper stating an insecurity correct? How much of a risk is it?

According to CryptoGram, this attack is expected to take a large nominal amount of known plaintext, and hence might not be that risky after all. I personally like Blowfish better anyway :)

random keys (-1, Redundant)

Anonymous Coward | more than 11 years ago | (#4264983)

"All of cryptography depends on a small number of problems..." This isn't true. No message that is encoded with a key which is both random and at least as long as the message can be cracked; provided the key is used once.

Re:random keys (0)

gazbo (517111) | more than 11 years ago | (#4265053)

Maybe it's talking about asymmetric crypto - then the statement is true. It's not really any news that symmetric crypto can be unbreakable.

Quantum computers and privacy (1)

Skal Tura (595728) | more than 11 years ago | (#4264994)

Well, we won't be looking fondly back in golden era of privacy, privacy will still remain, although there won't be a reason to crypt your data for a while after quantum puters has been released, developers need time to create even more stronger crypting methods... although, how much sooner goverments get these quantum computers? i bet years!
and well then goverment agencies can simply brute force your crypted document, so we will have many years without privacy, that sucks...

Quantum Computing and Privacy (4, Insightful)

hillct (230132) | more than 11 years ago | (#4264998)

Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware. International politics would be forever changed. The basis for personal freedom (now based on privacy) would have to shift to something as alien as mutual trust and maybe even respect.

The focus of international intelligence gathering would shift radically back to human intelligence (which is already happening for other reasons) and the new basis for security would become that of access cintrol through discontinuity - if you network is not connected to your neighbor's, then he can't get access to it regardless of his technical sophistocation.

The days of the NSA Sneaker-Net would return (picture NSA computer geeks running from one terminal to another with DLTs in order to keep the systems in communication, such that data could only flow in one direction.

Disclaimer: IANAF - I Am Not A Futurist

--CTH

Re:Quantum Computing and Privacy (5, Insightful)

sql*kitten (1359) | more than 11 years ago | (#4265046)

Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware

How would this technology work against one-time pads? Besides, historically technologies have always tended to balance. Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats. If today's sophisticated encryption can in the future be defeated with cheap devices, then the crypto that this future society considers sophisticated would be well beyond ours. Consider the relative computational power of Bletchly Park and the sophistication of Engima of the early 40s and the power and sophistication of a 21st Century desktop PC.

International politics would be forever changed.

Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes - which is how it worked for centuries. Complexity in international affairs is nothing new.

Re:Quantum Computing and Privacy (2)

Beautyon (214567) | more than 11 years ago | (#4265316)

Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes

Where of course, Numbers Stations [ibmpcug.co.uk] come in.

For all the advances in asymetric cryptography, Numbers Stations / OTP has remained the system of choice for many organizations. This says something about asymetric cryptography; either that it isnt trusted, that its impractical for espionage, or something else...

Re:Quantum Computing and Privacy (0)

gazbo (517111) | more than 11 years ago | (#4265084)

picture NSA computer geeks running from one terminal to another with DLTs... ...such that data could only flow in one direction.

Strange though it may sound, that does still happen. OK, not necessarily NSA, but I know for certain that some defence installations in the UK do that - it's known as an 'air gap'. They are paranoid to the extent that they do not trust cryptography at all for really sensitive materials.

Do not fear the Quantum Age (2)

psicE (126646) | more than 11 years ago | (#4264999)

http://www.newsfactor.com/perl/story/13468.html

Quantum computing is a *good* thing.

Quantum Cryptography (1)

alekd (580693) | more than 11 years ago | (#4265015)

Before the arrival of useful quantum computers we will probably see the advent of quantum cryptography. Quantum cryptography should by the laws of nature as we believe them to be today be uncrackable. Quantum cryptography would also make wiretapping without being detected impossible.

Long Live Triple-DES! n/t (0)

Anonymous Coward | more than 11 years ago | (#4265029)

n/t

Codes in general (0, Redundant)

saintThomas (608920) | more than 11 years ago | (#4265033)

Well, there is always the one-time-pad, which is theoretically unbreakable......... but then there's the security of the one-time-pad......... snail-mail for security, anyone?

Strictly Speaking (2, Insightful)

Beautyon (214567) | more than 11 years ago | (#4265037)

All of cryptography depends on a small number of problems that are believed to be hard.

This is not true; The "One Time Pad" does not rely on a difficult problem like factoring for its basis.

And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy.

OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.

Now legislation ending the golden age of privacy is another matter entirely.

Re:Strictly Speaking (2)

sql*kitten (1359) | more than 11 years ago | (#4265157)

OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.

Only if your pad is truly random. There's a scene in Cryptonomicon in which they realize the vicar's wife is looking at the letters as she draws them out of the tombola used to randomize; being a native English speaker she is subconsciously biased to prefer certain letters over others, and this is enough to open a chink in the armor.

Re:Strictly Speaking (2)

Beautyon (214567) | more than 11 years ago | (#4265240)

When I use the term "OPT", it is implicit that I mean "when OTPt is deployed correctly".

It would be a little crazy to say "OTP, when it is deployed improperly, cannot be broken", now wouldnt it?

Re:Strictly Speaking (2)

gclef (96311) | more than 11 years ago | (#4265318)

While this is true, there's a reason that no one uses one-time-pads : they're a pain in the ass. In terms of practical usefulness, really only governments are willing to go to the trouble.

The big problem is that once you've encrypted something with an OTP, the security (and secrecy) of the OTP is *everything*. If anyone gets the OTP, your encryption is done for.

So, managing the OTPs becomes the biggest challenge in using them. First, you have to have an OTP about the same size as the file you're encrypting, to ensure that no statistical games can be played to re-build the key, and you have to have a seperate OTP for every message you encrypt. Also, getting an OTP to someone else you want to encrypt a message to is not an easy matter. You have to be sure that no one else can see the transaction that shares the OTP, since that would immediately destroy the security of the system.

Compare this to any symmetric-key system: Yeah, you've also got a key that's central to the cipher. But, the key does not need to be approximately the same size as the file encrypted (as is the case with OTPs), which, for big files, is a huge deal.

Basically, there's a reason we like symmetric-key algorithms, and it's mostly to do with usability. If an encryption system is such a pain in the ass that no one uses it, then its impact in the real world will be zero.

Well... yeah! (2)

rocjoe71 (545053) | more than 11 years ago | (#4265050)

...maybe we need to assume that any given type of crypto is only temporary.

Well that's a serious problem if you ever, ever thought cryptography had any sort of permanence!

For one thing, an encrypted message is of no use to the receiver if they can't DE-crypt it, *poof* crypto is not permanent.

I'd recommend reading "The Code Book" by Simon Singh as the first two-thirds of the book are a history lesson that demonstates to me how cryptography endagers the lives/way of life of those who rely on it to protect themselves (in particular, Mary Queen of Scots and Enigma).

Old data is the problem (5, Insightful)

BESTouff (531293) | more than 11 years ago | (#4265061)

The problem is that old encrypted data doesn't "evolve" with the computing/crypto capacity.

Imagine some black hat just archived all encrypted data he could get (bank transactions, private conversations, you name it) then decrypts them in 10 years when he can buy his brand new quantum computer. All this old data may prove very valuable for him.

Perhaps very sensitive data shouldn't even transit on the net because you can't tell if it'll be decryptable in the future.

The Code Book (1)

kmac06 (608921) | more than 11 years ago | (#4265069)

I'm sure a lot of /. readers have read Singh's (sp?) book about cryptography, and quantum cryptography is coming along faster than quantum computing. The first quantum crypto message was sent about 6-7 years ago across about 2 feet, and I think someone had it up to 5 km in the air a couple years ago. Shouldn't be too long (before quantum computing) that there'll be wires running everywhere for this type of data transfer (or just send it via airwaves)

So use one-time pads (2, Insightful)

wiredog (43288) | more than 11 years ago | (#4265070)

They're easy to generate. All you need is a good source of randomness. A small analog input card connected to a thermocouple wire with a bad (therefore noisy) connection makes a wonderful source of randomness. Use the low four bits of a 12 bit card. Two reads gives one random byte. String random bytes together to generate however many you need.

Once you have the list of numbers, get the list of words and phrases to encode. Put one random number next to each word or phrase (watch for duplicate codes here!)

Put the pad on a cd, send it to whoever you want to communicate with. Doing this last part is the only large potential insecurity, plus it's inefficient. But the one time pad is theoretically unbreakable.

Re:So use one-time pads (1)

kmac06 (608921) | more than 11 years ago | (#4265083)

One-time pads are not theoretically unbreakable, they are completely unbreakable (as long as you use numbers 1-26 not 1-10)

Re:So use one-time pads (1)

GigsVT (208848) | more than 11 years ago | (#4265139)

One-time pads are not theoretically unbreakable, they are completely unbreakable (as long as you use numbers 1-26 not 1-10)

Confusing a one time pad with a monoalphabetic replacement cypher?

Re:So use one-time pads (2)

autocracy (192714) | more than 11 years ago | (#4265166)

Not 1-26, and not 1-10... 1 or 0. Bit level XOR is the "proper" way to do it.

Re:So use one-time pads (0)

Anonymous Coward | more than 11 years ago | (#4265165)

So every time I order something over the net and use my credit card, I've gotta burn a CD with a one time pad on it and send it to the company I'm ordering from? Woo hoo, e-commerce here we come.

Re:So use one-time pads (2)

Luyseyal (3154) | more than 11 years ago | (#4265191)

Postal Workers of the world rejoice! :)
-l

Re:So use one-time pads (0)

TerryAtWork (598364) | more than 11 years ago | (#4265169)

The way to generate random bits is to sample a good physical source, see above, check the bits in pairs and abandon identical pairs, use the first bit of different pairs, gather a power of 2 of these bits, say 512, and XOR them all together. That gives you one INCREDIBLY random bit, where the probability of a 1 is .5 + some small epsilon ( less than .5) that is taken to the power of 512 minus one. Whatever, it'll do, I think. Repeat as necessary.

Re:So use one-time pads (2, Informative)

lars_stefan_axelsson (236283) | more than 11 years ago | (#4265175)

But the one time pad is theoretically unbreakable.

Here it's fitting to note the words of Steve Bellowin:

"As a practical person, I've observed that one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong."

In operation, there are many 'gotchas' to watch out for, never reuse a pad for example.

Google for 'Venona' and 'one time pad' for a good example of even the experts (KGB et al) getting one time pads wrong.

That's the wrong way to use them. (2, Informative)

dark-nl (568618) | more than 11 years ago | (#4265308)

If you number individual words and phrases, then you can only use each word or phrase once, otherwise it's not a one-time pad anymore. Think about it... how long would it take a cryptanalyst to figure out the code for "the" or "you"?

The pad should simply be a chunk of random bits, and both sides need to keep track of which bits have been used. Then encrypt your messages by xoring them with an unused stretch of bits.

This was completely predicable because... (0)

TerryAtWork (598364) | more than 11 years ago | (#4265128)

it's why AES was chosen in the first place. The NSA checked the competing cyphers and picked one that was looked good to the crowd yet was hard but not impossible to break. Did you really think they would have picked one they couldn't handle? That's why TwoFish didn't get the gig.

Re:This was completely predicable because... (1)

BigBadBri (595126) | more than 11 years ago | (#4265155)

And I thought Rijndael was picked because there was an 8-bit implementation of it suitable for smart card use - Doh!

MAYBE? (2, Insightful)

Winterblink (575267) | more than 11 years ago | (#4265132)

maybe we need to assume that any given type of crypto is only temporary

If I'm not mistaken, this is rule #1 of cryptography. Doesn't really matter what algorithm you use or how secure everyone or anyone thinks it is, they're always able to be cracked. Which cryptosystem you use is more a measure of reasonable security -- do you want your messages secured for years, decades, etc., with an assumed increase of computing power?

What Schneier really meant to say... (4, Interesting)

BigBadBri (595126) | more than 11 years ago | (#4265141)

Serpent and Rijndael are vulnerable to this attack - it seems Twofish isn't - damn government should have chosen Twofish for AES instead...

Seriously, though - any approach that manages to reduce the difficulty of cracking these algorithms by a factor of 2^100 is impressive, and Schneier at least simplifies it enough that us folks with very rusty number theory can appreciate the achievement.

His comment later in Cryptogram about his name appearing on a list of banned words is much, much scarier - looks like he's upset someone in the content censorship Gestapo. That same content filter would deny access to today's Slashdot front page - nasty.

Re:What Schneier really meant to say... (0)

Anonymous Coward | more than 11 years ago | (#4265187)

Ooohhh... his name is censored by a anti porn software. Big deal.

I wouldn't care if my name was censored by default as long as it would keep the porn off my kids' e-mail accounts and browsers.

Re:What Schneier really meant to say... (0, Flamebait)

BigBadBri (595126) | more than 11 years ago | (#4265267)

It means that your lovely intelligent children will never be exposed to his intelligent and reasoned analysis of cryptographic issues - but then your offspring probably wouldn't be able to absorb such complex ideas, given your obvious stupidity. You obviously don't mind your name being censored, since you choose to post anonymously. Arsehole.

Funny... but sad. (0, Troll)

Lumpy (12016) | more than 11 years ago | (#4265168)

real crypto can be near impossible to be broken, but it can never be uncrackable or unbreakable. I can take any easily broken crypto scheme and make it ultra secure by placing several techniques used in 1920's and the 1940's on top of it. How about adding some obscurity? Padding? one time ciphers? How about making sure the data has no predictable components? (sending it as a Word file or Zipped and then encrypt it... pure stupidity!) I can think of at least 2 dozen ways to make sure you cant decrypt that one message fast enough for it to be useful to you. hell I have a $9.95 book on cryptology that has some super basic encryption techniques that the best cryptologists out there couldnt break it for at least a year.. maybe 10 if I screw with it a bit. (how about reversing the entire text before encryption?)

basically if you really have a need to communicate secretely you will be able to do it without much worry.. this only affects daily-mundane things that really dont matter except to keep honest people honest, or at least to make the criminal have 1/2 a brain.

Troll (0)

Anonymous Coward | more than 11 years ago | (#4265217)

Why don't you go and do Schneier's job, then - with your $9.95 book on crypto, you sound like a real expert^H^H^H^H^H^Hjerk.

You may be able to create something that you can't crack, but then you are a lame arsehole, not a professional codebreaker.

Fucking troll.

¿¿¿Quaumtum Computer will change the scene??? (1)

Lolaine (262966) | more than 11 years ago | (#4265177)

There is a theorem of cryptography that states that that more powerful computers can crack codes generated by less powerful computers faster and easier, but if everybody has more powerful computers, the scene will be the same, am I wrong? ... as long that everybody has more powerfull computers.

One Time Pad != Encryption (4, Insightful)

Kjella (173770) | more than 11 years ago | (#4265220)

Basicly, it's just a delay mechanism that will let you transfer messages securely at a later time assuming you've transmitted equally much information securely already. So the question is, why don't you use the secure medium in the first place? Ok granted, you can send an agent out on a mission with an OTP and he can communicate securely with home base, but I mean for everyday use?

The typical idea about cryptography is to use a secure medium to provide the key, while using the insecure medium to send the data, because the insecure medium is much faster/better/easier to use. So I can meet you in person and get the key, or call you on the phone and verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well), and then use the Internet as a medium from then on.

The OTP "solution" would be to say a random sequence of 1s and 0s, then use those to decrypt the irc converation later, not really an option. You'd "run out" of pad rather quickly. Oh, and quantum computing does as far as I know not affect encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).

Kjella
Kjella

As Bruce says, relax...for now. (2)

mbourgon (186257) | more than 11 years ago | (#4265260)

My fear is that we could see optimizations of the XSL attack breaking AES with a 2^80-ish complexity, in which case things starts to get dicey about ten years from now. (emphasis added by me)

So, ten years or more. Heck, at that point, shouldn't quantum computers be breaking this stuff anyhow?
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...