Cryptogram: AES Broken?

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."

Comments

Quantum computing for white hats

[kingpin2k]

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

[tanveer1979]

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

[BESTouff]

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

[ch-chuck]

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!".

Re:Quantum computing for white hats

[smallfries]

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

[jpvlsmv]

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

Re:Quantum computing for white hats

[RobertNotBob]

because you can't tell if it'll be decryptable in the future

I think you might have missed the point. Everything that is encrypted now will be decryptable in the future. The idea of storing data untill it can be decrypted has always been an issue. That's why crypto has always been only one part of the security puzzle.

Re:Quantum computing for white hats

[smallfries]

But isn't the authentication on a bit-by-bit basis, so that the first bit that is intercepted signals that fact and the rest of the message could be dropped.

Isn't this the same as can't be broken and it gives an indication that somebody is sniffing?

Re:Quantum computing for white hats

[Fnkmaster]

Not necessarily. Quantum computing is a technique that is potentially very useful for operations that are highly parallelizable, and less so for operations that tend to be inherently sequential.

More complex algorithms for encryption do not necessarily mean more security. If factoring, for example, is only linearly hard in the number of digits of the large pseudoprime, then you could theoretically generate absolutely massive pseudoprimes, but at some point the method becomes useless.

The problem is that our notion of "hard" and "one-way" problems is all based on the concept of NP-completeness. This concept is broken by quantum computation. We would need to find new problems that are QC-complete, in other words, problems that are hard (exponential time and # qubits) even with quantum computation, and base new encryption methods around such problems.

I'm not up to date on the literature of computational complexity, but I'm fairly sure such problems should be possible to find, a class of harder problems than NP-complete problems. But since functional QC is so far off, this is not really a practical issue yet, but I'm sure it's of theoretical interest to many.

Re:Quantum computing for white hats

[Zeinfeld]

Unfortunately this thread does not appear to be talking about the AES issue at all, but garbled understanding of what quantum crypto can do.

According to the cryptographer's panel at RSA quantum computing is much less of a threat than many assume. In the first place quantum computing tends not to be effective against symetric algorithms. Secondly RSA turns out to be based on a problem that is very very hard with conventional computing and very very easy with quantum computing. It is not clear that all possible public key algorithms are susceptable to attack using quantum techniques.

In other words don't get the idea that quantum computing immediately means the end of cryptography.

On the actual topic of AES I would not call this a 'break', in fact nothing less than breaking the cipher for real should count as a break. There are plenty of 'breaks' of DES but none of them are easier than brute force when applied in practice. What we have is a theoretical compromise that is way outside the capabilities of any current technology.

Or consider it this way, given the known problems with 3DES (limited block size, severe limitation on safe amount of ciphertext generation) I don't feel like sticking with 3DES as a result of the article.

Re:Quantum computing for white hats

[ghjm]

It's easy to get confused here. There is a quantum computer algorithm for factoring, because factoring happens to map well to quantum concepts. But factoring is not NP-complete - in fact, it is in P. If you could reduce an NP-complete problem to a factoring operation, you would have proven that P=NP.

The theories that posit QC as the solution to P=NP tend to involve poorly-defined "oracle machines" based on QC hand-waving, rather than any actual well-defined algorithms. It is very much an open question whether QC has anything interesting to say about P=NP.

-Graham

Re:Quantum computing for white hats

[billstewart]

Quantum computing means that you can either tell what color somebody's hat is or how many hats they'r ewearing, but not both simultaneously :-)

Quantum computing appears to allow the user to cheat, by picking the correct n-bit value out of 2**n bits, for a class of problems that mostly look like the factoring problems that make RSA public key crypto work. This doesn't appear to make things faster for the white hats, because the white hats already knew what the correct bits were for data that was intended for them or data that they were trying to sign.

• We need to start exploring the theory of QC, to find algorithms that don't get exponentially faster with QC.
• We also need to start remembering and improving the symmetric-key-based Key Distribution Center (KDC) models like Kerberos that don't depend on public-key crypto. We abandoned most of these, because public-key is much more convenient and doesn't have big obvious centralized security targets that can be attacked, but they still do an amazing number of jobs just fine.
• Today's problem is attacks on the Rijndael and Serpent AES winner/candidate symmetric-key algorithms, which has been proposed as a replacement for 3DES, the current highly-trusted-but-slow symmetric-key algorithm. We need to watch the crypto math folks apply their new techniques to the other AES candidates, so we can tell if any of them are still usable or if we have to get the NSA to run another contest. These aren't particularly affected by Quantum Cryptography.

Re:Quantum computing for white hats

[Fnkmaster]

Sorry I was mistaken - you are right that factoring is not proven to be NP hard or NP complete (dredging up CS knowledge from 4 or 5 years back here).

However, you are not 100% correct either. Most practical experience does not suggest a polynomial time solution exists (with the exception of Shor's Algorithm and the quantum factoring algorithm - this does mean the problem is in BQP, the new class of bounded-error, quantum polynomial time). If you look up the modern definitions of P, it seems to refer only to deterministic sequential machines, and I don't think that includes quantum computers strictly speaking.

I guess this is a quibble, but a worthwhile one, since the whole point is that there is a class of problems that _seems_ to be made easier (i.e. polynomial) by quantum computing, though it's not clear that those same problems don't have non-quantum polynomial solutions, it certainly appears that way based on everything we know.

You seem to be correct though that there is no proof of anything about P=NP from QC (I just looked it up and I'll be damned if I could make any sense of the articles I found without some serious study).

Re:Quantum computing for white hats

[Master of Transhuman]

Nuts! Found out again before I even got started...

I'm no mathematician,

[3.5 stripes]

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,

[sydneyfong]

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,

[Marlin099]

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,

[26199]

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,

[blancolioni]

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.

Re:I'm no mathematician,

[3.5 stripes]

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

Re:I'm no mathematician,

[Rich0]

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,

[jmauro]

Except the process involves reducing the number of cycles needed to be thrown at the problem. It reduces a problem with 2^192 stages to a problem with 1^100 stages. This results in reducing the time it takes to break the key by probably a few millions of years. It'll still take a long time (again probably millions of years). The whole system still won't help you though if you have no idea what your looking for.

Re:I'm no mathematician,

[iabervon]

That's how you break the encryption on a document. People will generally choose the strength of the encryption (that is, how long it will take to break it by the best known method) so that, by the time you've done this, they don't care any more.

Breaking an encryption method is a different thing. This is done by analyzing the method in order to try to find a better method for breaking encrypted documents than the best method previously known. If this is sucessful, it means that all of the encryption that has been done with that method so far is weaker than had been thought. Of course, the initial method is just trying all possible keys, and it may actually be somewhat foolish to think that there is any cryptosystem which doesn't have a better method; that would mean that all of the key contributes to strength, rather than any of it being weak but necessary to get the algorithm to work. And, from the perspective of what you should use, even the strongest attack so far (if it even works) on AES is harder than brute force on triple DES.

Re:I'm no mathematician,

[ichimunki]

Factorisation of large primes

Good luck factoring any primes. Except for the obvious case of the number itself times 1, if you can factor the number it is not prime.

What you are probably thinking of is the case where you take two prime numbers and multiply them together to form a product which has as its only factors the two prime number. Given just that large number, finding its two prime factors is very difficult.

Re:I'm no mathematician,

[shillis]

For RSA and most encryption schemes that involve primes, the steps are:

1. Pick two very large prime numbers - the trick is ensuring (with some confidence) that they are prime by using Miller-Rabin or some such algorithm.
2. Compute the product of the two primes.
3. Publish the product without the two primes - this is one of the keys in RSA.

The strenght of the encryption is the difficultly of factoring the very large (non-prime) number. Until a non-linear factoring technique is developed, such encryption schemes will continue to be viable. I haven't seen yet any real research that quantum computing will be able to do this - but who knows.

Re:I'm no mathematician,

[Anonymous Coward]

That's 18 billion billion chips. That would cost a lot.

Perhaps, but you'd get a substantial discount for buying in bulk.

Re:I'm no mathematician,

[chris_mahan]

What you'd really want is all the computers in all the universes working an infinite amount of time... But if you had that much computing power. I'd say use it to design a really bitching weapon system and invade their ass/kill them with a vengence and don't worry about decrypting their feeble call for help. (All our base are belong to them)

Re:I'm no mathematician,

[ksorim]

The strenght of the encryption is the difficultly of factoring the very large (non-prime) number. Until a non-linear factoring technique is developed, such encryption schemes will continue to be viable.I haven't seen yet any real research that quantum computing will be able to do this - but who knows.

Do a search on google for Shor's algorithm. It can factor a product of two primes in O((log N)^3) time.

Re:I'm no mathematician,

[mencik]

The actual problem you are thinking of is finding the prime factors of very large numbers. As already noted, finding the factors of prime numbers is trivial.

Re:I'm no mathematician,

[psamuels]

The actual problem you are thinking of is finding the prime factors of very large numbers. As already noted, finding the factors of prime numbers is trivial.

Oh, come on. It takes longer to find the factors of a large prime number than a non-prime in the same ballpark.

(I'm assuming, obviously, that you don't already know it's prime. If you did know, it means you're not actually finding the factors, since you've already been told what they are.)

Re:I'm no mathematician,

[Rich0]

One would hope that before embarking on a factoring job requiring a computer the size of the moon and a few millenia one would perform a primality test that requires a couple of seconds on an old 386...

Re:I'm no mathematician,

[ebyrob]

O(n^1.5) seems slightly worse than linear to me.

quantum computers

[ch-chuck]

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]

Quantum cryptography

[ljubom]

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

[gazbo]

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

[smallfries]

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

[kasperd]

key distribution problem

If we get quantum computers and quantum cryptography, it will be the end of public key cryptography. We will need to exchange the initial keys face to face. The keys will not be used for encryption but rather integrity, which is a requirement for quantum cryptography to work. Obviously we will need to use unconditionally secure message-authentication-codes on our messages. Luckily the key needed for integrity does not grow linearly with the key size like keys needed for confidentiality.

This means that once we have exchanged the initial keys, we can just append new key material to our messages whenever we send quantum encrypted data. This will provide us with a key for integrity the next time we need to communicate.

To be very secure, I would not like to use a fixed key size for all future communication. I'd rather increase the key size by a few bits whenever a message is being exchanged. With a fixed key size, the chance of breaking the system will converge toward 100% as the number of attempts converges toward infinity. With a growing key size, the chance of every breaking the system will converge toward a small number, that is exponentially small as a function of the initial key size.

This still leaves the DoS problem. An attacker might just keep messing up the messages until we run out of key material for signing messages. I see no solution other than keeping a lot of key material ready for the future, and not keep trying too many times in a short period of time if we keep seeing false signatures.

Even though we have no public keys, we can still build up trust networks. If Alice has already exchanged keys with Bob and Charlie, Alice can do the key exchange for Bob and Charlie. Of course this will only work if Bob and Charlie trust Alice. But if Bob and Charlie has exchanged keys with different middlemen, they can once send messages signed with all their keys. Unless all middlemen are corrupt, Bob and Charlie will discover any invalid key.

Re:Quantum cryptography

[psamuels]

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.

But you can't route it, right? It has to go point-to-point? I don't think I really understand this stuff (scratch that - I know I don't understand this stuff) but if something needs to use a direct p2p (no that's not "peer-to-peer") link, it kind of defeats the whole purpose of having an Internet. (No, I'm not referring to the "purpose" of efficient pr0n distribution.)

Re:Quantum cryptography

[psamuels]

To be very secure, I would not like to use a fixed key size for all future communication. I'd rather increase the key size by a few bits whenever a message is being exchanged. With a fixed key size, the chance of breaking the system will converge toward 100% as the number of attempts converges toward infinity.

Adding a few bits to the key every message or two does not really help, if you assume the attacker archives all your ciphertext.[*] Say ten years from now he breaks your first message. He just has to connect the dots and he has now broken your new thrice-as-long key.

Even if he only has some of your messages ... say for example he is missing a message where 8 bits are added to the key. He knows your 160-bit key but needs your 168-bit key. Guess what? He only has to break an 8-bit key, which can be done on the Atari 2600 in his basement.

Here I'm assuming your key is for a symmetric algo. Your scheme wouldn't work at all for, say, RSA. You can't just take a valid RSA key, add a few random bits and get a new valid key.

[*] Perhaps you are assuming that nobody can archive your ciphertext because the message is unobservable - to observe it you must disrupt it. Is there really such a strong guarantee that QC does not allow a mitm to archive your conversation for later analysis?

Re:Quantum cryptography

[kasperd]

Even if he only has some of your messages ... say for example he is missing a message where 8 bits are added to the key. He knows your 160-bit key but needs your 168-bit key. Guess what? He only has to break an 8-bit key, which can be done on the Atari 2600 in his basement.

You missed the point.

Adding bits does help. And breaking the system is not about just trying the possible combinations. You cannot decrypt the quantum encrypted data, your only chance of breaking the system is forging a message from one of the two parties during the communication. You cannot just try all possible keys, you have only one try. If you send an invalid message, it will be discovered.

And when talking about adding a few bits every time, I talk about a few bits larger key. All the bits in the new key are brand new random bits. So basically you will have to start all over again every time you try. And every time you try, your chance of breaking the system is smaller than last time you tried.

Quantum

[caluml]

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

[The Original Yama]

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.

Re:Quantum

[bracher]

read up on quantum crypto.

Golden Age of Privacy

[marko123]

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.

Comment removed

[account_deleted]

Comment removed based on user account deletion

The end of privacy

[bjelkeman]

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

[Winterblink]

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".

Re:The end of privacy

[Methusalem]

Privacy.... I had a lot more privacy 20 years ago, that is for certain.
I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays. The only difference is that they didn't send you spam, but for sure your butcher knew that you didn't know the difference between a normal and an excellent steak, and sold you the first one for the price of the second one. So you were f*cked even then, only you didn't know it.

In order to provide some on-topic content also: I thought the basis of all (public-key) encryption was based on one "hard to solve" problem only, namely the "factoring in prime numbers" problem -- are there any problems that I missed?

Re:The end of privacy

[dogfart]

Someone once said:

Privacy is what existed between the time people stopped believing God saw everything they did and the time the government saw an opportunity.

Re:The end of privacy

[moebius_4d]

el gamal is based on discrete logs on a finite field

Re:The end of privacy

[God! Awful]

I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays.

Uhh... sorry to be literal, but 20 years ago I didn't know my butcher personally and I still don't. I buy mostly buy meat at the supermarket. I think it was more like 60 years ago that everyone bought meat from the local butcher.

On the other hand, my credit card issuer knows far more about me than any e-mail marketer. They know that I play golf once a week, how much I spend in the grocery store, when and where I go on vacation, etc. All the average e-mail marketer (thinks they) know about me is that I like rape pr0n.

-a

Re:The end of privacy

[ssimpson]

are there any problems that I missed?

RSA is based upon the Integer Factorization Problem (IFP) (*).

Elgamal / DH are based upon the Discrete Log Problem (*)

Eliptic Curves Cryptography is based upon, erm, Eliptic Curves.

(*) Note: there are no proofs that RSA or DH/Elgamal are actually as hard as the underlying IFP or DLP - e.g. they could be broken even if factoring is "hard".

security thru obscurity

[buttahead]

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...

[maya]

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

[TechnoVooDooDaddy]

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 will happen along (or maybe the man himself) and we'll be dealing with the golden age of quantum cryptography.

gross oversimplification

[jukal]

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? :)

Re:gross oversimplification

[Lord Ender]

What's the problem? You should have seen all of that stuff, at least on a basic level, in high school if you went to school in the USA. This is assuming you took the college prep route of courses.

Re:gross oversimplification

[jukal]

>What's the problem?

The fact that my and your sense of humour did not intersect. :) To me, it seemed that the clip was like straight from Dilbert mission statement generator. Anyway, the description is very good, but to one like me, who does not use math terms actively, it takes some time to understand what it means in practise and how to use the information. And at first sight it seems like the recipe for Energy Bolt spell. But then again, I am mathematic moron :)

Nice article...

[26199]

...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...

[Jugalator]

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

Re:Well... If AES isn't sufficient...

[Tikiman]

For the curious, a decoder

Re:Well... If AES isn't sufficient...

[Jugalator]

LOL

I suppose some of you *cough*the moderators*cough* didn't get it? :)

Maybe?

[mischief]

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?

[Noryungi]

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

Since the one-time pad, 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?

[troc]

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?

[jonatha]

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?

[Dwonis]

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

Re:Maybe?

[autocracy]

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 :)

Re:Maybe?

[dfay]

AES, DES, Serpent are all symmetric, as were all of the entries to the NIST AES contest. I forget if it was a condition of the contest.

Since these are all symmetric, key distribution must either happen over another channel, or through a public key exchange method, all of which (AFAIK) use asymmetric algorithms. I don't know that I'd say that asymmetric algorithms are more susceptible, though. The biggest disadvantage to those algorithms is that they tend to require a lot more computing power, and one of the goals of the NIST AES contest was to provide an algorithm that would be implementable on really small platforms, such as embedded devices and smart cards. In fact, one of the best traits of Rijndael is that it seemed just as secure as the other entries while remaining very simple. It has been implemented on a few small 8-bit microcontrollers, and, when optimized, can take as little as 32 bytes of state (RAM).

Re:Maybe?

[Majin Bubu]

Cyphers that use the same key for decryption and encryption are symmetric. Examples are AES, Serpent, Twofish, Blowfish, IDEA, DES...
Cyphers that use different keys for encryption and decryption (usually called private key and public key) are asymmetric. Examples are RSA and DH/DSS.
The fact that a cypher is symmetric or asymmetric has no impact on its "crackability" per se, unless a method different from brute force is used.

Re:Maybe?

[plcurechax]

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


Yes, AES and Serpent are symmetric. They use a single secret key for both encryption and decryption.

Re:Maybe?

[Pike65]

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

You can't really compare symmetric and asymetric algorithms in terms of which is 'better'. You're never going to use a symmetric algorithm for digital signatures, and crypt(4) is not going to use public and private keys.

They're different tools for different jobs.

Re:Maybe?

[swillden]

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.

1. All of the mentioned algorithms are symmetric.
2. Symmetry/asymmetry has nothing whatsoever to do with "susceptibility to cracking methods". It's about whether the same key is used for both enciphering and deciphering (symmetric) or whether two different keys are used (asymmetric).

In theory it may appear that asymmetric ciphers are easier to break, because the attacker has more information -- the public key, which has a known mathematical relationship with the private key. However, the relationships between the keys are based on hard problems in math. In most cases, finding a way to determine the private key from the public key would constitute a major advance in mathematics, and one that has defeated mathematicians for centuries.

Symmetric algorithms, on the other hand, are not based on unsolved math problems, but rather on piling up carefully-chosen linear and non-linear operations until the result is too complicated to unravel. The papers referenced describe some new tools for modeling such complex structures, and claim that the new tools can unravel them far enough to produce a better-than brute force attack with very few known plaintext/ciphertext pairs.

To sum up: asymmetric crypto systems rely on the fact that we have no known method of solving the mathematical problems on which they are based. Symmetric crypto systems rely on the fact that we have no mathematical tools known to be capable of unraveling such complex sequences of simple operations.

In both cases, the ciphers can fall to new mathematics, and there's really no reason to think one is more likely to fall than the other.

Re:Maybe?

[psamuels]

The fact that a cypher is symmetric or asymmetric has no impact on its "crackability" per se, unless a method different from brute force is used.

Except that no public-key algorithms have been found which are anywhere near as efficient in terms of strength per bit. AES-160 is quite a bit harder to crack than RSA-512, right?

So if you determine "crackability" as "per key size", then the best symmetric algorithms are a lot better than the best asymmetric ones.

Yes, you're missing something.

[Kjella]

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:Yes, you're missing something.

[MrFredBloggs]

"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."

Surely, given identical hardware, its still easier to encrypt a message than it is to decrypt it? Isn't this a given, even if you are talking about quantum computing?

Re:Yes, you're missing something.

[Zaak]

Surely, given identical hardware, its still easier to encrypt a message than it is to decrypt it? Isn't this a given, even if you are talking about quantum computing?
With current computers that is true. Quantum computers, however, make factoring numbers very fast, so there isn't as much difference between the encryption and decryption of assymetric ciphers.

Re:Yes, you're missing something.

[MrFredBloggs]

Sure,but won't there just be a whole new set of problems which quantum computers allow, which would again be easier to set than to solve?

Quantum computers and privacy

[Skal Tura]

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

[hillct]

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

[sql*kitten]

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

[Beautyon]

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

Where of course, Numbers Stations 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

[thogard]

There was no privacy in most small towns all over the world. Until people started moving around, there was a local neighbor who knew what was going on. Ever try to hide something in a small school? The local gossip made sure you didn't. Most of our privacy today is an illusion based on non-existent anonymity.

Re:Quantum Computing and Privacy

[swillden]

Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats.

Very true, but it bears pointing out that the direction of the advantage seems to be different.

In the battle between warhead and armor, the warhead tends to retain the lead most all of the time, because it's basically easier to blow holes in something than to withstand massive force.

In the battle between cipher and cryptanalyst, the ciphers have tended to retain the lead, which seems to imply that creating an algorithm that munges data in complex ways is basically easier than unraveling said munging. This is *not* to say that good cipher design is easy or that anyone can do it; it's fiendishly difficult, because the attackers are fiendishly clever. Still, over the last 50 years or so, history shows us that the ciphers have tended to stay ahead of the cryptanalysts. DES is a shining example, given that it has been the #1 target for 30 years and has stood essentially undamaged.

Re:Quantum Computing and Privacy

[swillden]

Yes, that is the tradition. But the mind and effect of man is finite. Eventually we will end up with "The Answer" -- and no further cycle.

Only if there is a "The Answer". It's certainly not clear that there will be such an answer in the case of either the warhead/armor evolution or the cryptographer/cryptanalyst evolution, mainly because what often happens to allow one side to take the lead over the other is a changing of the rules.

To use some examples from the armor/warhead debate, consider that the debate started as armor vs. blade, progressed to armor vs. projectile, then to armor vs. explosive warhead, then to armor vs. shaped charge, then to armor vs. ultradense projectile backed by shaped charge. Further consider that armor changed radically a few times along the way as well, changing materials, thickness and composition (especially lately, with highly-engineered composites). Not only that but armor has even acquired the ability to actively "fight back" -- reactive armor. In tanks it takes the form of explosives attached to the tank's armor plate that explode to slow penetrators and distort shaped charges. In naval warfare, you can even view anti-missile defensive systems as part of the "armor". A set of Aegis-equipped ships with high-speed data links and layered missile defensive systems creates a sort of a "virtual" armor that encloses all of the ships. Now consider how far removed that is from a bronze sword hitting a boiled leather cuirass, and tell me that man's imagination is limited.

Things like quantum computing are based on the fundimental physics of the universe. While I can't say if they are, or are not, the end-game cycle -- they're surely isn't much left to work with.

Which does not mean that quantum computers will be able to solved all problems. In fact, there are already plenty of problems known that quantum computers will not be able to solve, and there is only a tiny set of problems for which it's clear that quantum computers will be any help at all.

Plus, QM does not give us a "fundamental" understanding of the universe; it has numerous well-known flaws (mainly in terms of what it does not explain), and who knows what else we may be able to do given a deeper understanding of How Things Work.

Re:Quantum Computing and Privacy

[plover]

I'm picking a few nits here, but there are several chinks in DES's armor.

• It has been known for some time that there are many weak keys in DES.
• In 1990, Biham and Shamir published a differential cryptanalysis attack on reduced round variants of DES.
• In 1993 Matthew Wiener published an initial design for a DES-breaking machine. At the time, it would have cost $2M.
• In 1998 Biryukov and Kushilevitz published a ciphertext-only attack on reduced round DES reducing the workload by 2^20.
• Near this time, I recall seeing a paper claiming to reduce DES to a 2^48 problem, but I'm unable to find a citation tonight.
• In 1998, Wiener's machine was built by the Paul Kocher and EFF for about $250,000, and it breaks DES keys in about three days, on average.

So yes, I agree that DES is the granddaddy of Feistel network ciphers. Few of the cryptanalytic attacks work without ungodly amounts of chosen plaintext or artificially reduced round counts. But code breaks have generally occurred within months or years of implementation, not decades. As Gwido Langer, the chief of Poland's Biuro Szyfrow, said about breaking the German Enigma (when the British were unable to) "You don't have the same motivation as we do." Until after World War II, most code systems were broken during the same wars they were supposed to be protecting, and for that same reason.

The wartime and/or government codebreakers also have one more advantage: they don't typically announce their breaks to their enemies du jour. The recently released Venona papers show how Soviet spies who were given (faulty) one-time pads in 1942-1946 had them broken between 1948 and 1980.

Yes, it's a constant struggle. Yes, DES looks pretty good. But I wouldn't want to trust ALL of the national eggs to any single one of the currently commercially-available baskets.

Re:Quantum Computing and Privacy

[swillden]

It has been known for some time that there are many weak keys in DES.

Depending on your definition of "many", this is true. The complementation property of DES is a small weakness as well. These issues reduce the strength of DES by a miniscule amount.

Near this time, I recall seeing a paper claiming to reduce DES to a 2^48 problem, but I'm unable to find a citation tonight.

You're probably thinking of Matsui's Linear Cryptanalysis.

In 1998, Wiener's machine was built by the Paul Kocher and EFF for about $250,000, and it breaks DES keys in about three days, on average.

The DES key size was always too small, but that was what the NSA wanted. Remember that the original cipher (Lucifer) had a 128-bit key. 3DES addresses this problem handily, if not elegantly.

Also, if you'll permit me to pick nits, Deep Crack recovers a key in about 5 days, on average.

Overall, though, all of the concerted effort focused on DES has reduced its effective key size very little. That effective key size was too small to begin with, but 3DES has an effective key size that is adequate for a few years yet, particularly since linear and differential attacks cannot be used to speed up the "meet-in-the-middle" attack.

This is a pretty impressive record, in my opinion.

Do not fear the Quantum Age

[psicE]

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

Quantum computing is a *good* thing.

Quantum Cryptography

[alekd]

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.

Re:Quantum computing =/= no privacy

[stevelinton]

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.

Strictly Speaking

[Beautyon]

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

[sql*kitten]

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

[Beautyon]

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

[gclef]

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.

Re:Strictly Speaking

[Beautyon]

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.

I totally agree with you about OTP being a pain in the ass to manage, but as far as its impact in the real world, you could not be more wrong.

Numbers Stations have relied on OTP for decades, and continue to do so till today.

Like anything, it depends how much you want a to protect your communications. If OTP is going to save your life, as in espionage, it becomes much less of a pain in the ass. If you want to encrypt your daily email with the 20 people in your Mozilla address book, then things get very messy very quickly, and of course, you can forget stuff like ecommerce, which instantly become "unwieldly" to put it mildly.

Re:Strictly Speaking

[Delta]

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

OTP is not unbreakable.

While the algorithm itself isn't breakable, the strenght of a OTP based solution will still depend on several weak points, like the random number source.

There's plenty of room for trying to attack it, using statistical analysis and estimates to try to be able to break it.

Re:Strictly Speaking

[Beautyon]

OTP is not unbreakable.

OTP *is* unbreakable.

This is a well established fact. Like I said elewhere in this thread, its clear that I mean "when it is implimented correctly", as it would make absolutely no sense to imply "OTP is unbreakable when it is implimented poorly".

Re:Strictly Speaking

[bytesmythe]

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

Sure it does: mind reading. ;)

Re:Strictly Speaking

[Delta]

I have no idea why you replied to my post, as it's obvious that we agree.

One interesting point though. I don't see how you can easily proove a OTP based solution to be correct. Random numbers are not easy.

What I'm merely trying to do is point out that OTP-based solutions are not the holy grail to perfect privacy. It's tempting to draw a parallel between regular symmetric cryptogaphy and OTP. You're still basing your security on components which you don't know how hard it will be to break. What if a new discovery is made which will help in statistically predicting the output of whatever you use for a random number source?

Another issue entirely is that you seem to claim that there's no need to worry about things like quantum cryptography because "we can just use OTP". While I'm not one of the "Quantum Cryptography will ruin our privacy"-crowd, I don't agree with your claim. OTP does quite simply not solve all the problems we use cryptography to solve today.

For one thing it'll only help you out when you have some way of distributing the PAD securely. You can't easily replace a public key cryptography system with a OTP based one.

You can do some of the same things with OTP-based solutions by having every user agree on a PAD with a certificate authority, thus having a channel they can use to negotiate keys with 3rd parties which also have an agreement with that CA, but there's a lot of isses involved there, and the easiest solutions would normally result in the CA having copies of the keys.

Just some thoughts.

Well... yeah!

[rocjoe71]

...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

[BESTouff]

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:Old data is the problem

[fermion]

IANASE, but it seems to only a problem if one is foolish enough to believe that the encryption method protects data forever. In the few situations where I was involved with security, we explicitly defined the span of time the data had to be secured. Surprisingly, the time can range from minutes to years.

In your first example, the responsible bank will keep the data secure for a finite amount of the time. At the end of that time, the data will be destroyed. The importance of this second step to the security of corporate world was shown in the Andersen/Enron case.

In the second example, in which transactions are saved by a 'man in the middle' for later decryption, the problem depends on the data. For instance, some data is extremely time sensitive, and future description is not a problem. If in 10 years we deciphered a message in which Martha Stewarts told her stockbroker to sell all of IM Clone, it probably would not be a smoking gun. Again, the issue is more a matter of appropriate security.

Re:Old data is the problem

[SN74S181]

Generally, 'very sensitive data' doesn't transit on 'the net.' Anybody who thinks highly critical data gets shuttled around on the public Internet has a lot to learn.

Re:Old data is the problem

[bug506]

I've thought about this problem before for the most common secure activity I do online--purchasing something with my credit card. I was worried that someone could decrypt my credit card number and expiration date and "security code" when technology improves.

Then I realized that the credit card numbers expire in a relatively short period of time (all of the credit cards in my wallet expire within two years).

Assuming the technology to decrypt this information doesn't come out within two years, I'm safe with these cards. Of course, I suppose this means that when the security is breakable (quantum computer or whatever) I should immediately cancel all of my credit cards that are active at the time, and refrain from using any new cards I get.

However, this concern will make me think hard about whether to do other types of secure transactions... For example, I've been thinking it would be convenient if my insurance company could let me see my claims history online. However, this is information that I can't just "cancel" when someone in the future is able to decrypt it. Another example are the sites that require the use of social security numbers--again, you can't just cancel that information.

Re:Old data is the problem

[cookd]

I dunno 'bout you, but the last two times I got my credit cards renewed, I got back the same number on a new card with a new expiration date.

No, the security in credit cards comes from the fact that most people are honest, and that the credit card companies are *relatively* good (i.e. good enough for them to eat the loss and still make a profit) at clamping down on fraud. The real danger doesn't come from anyone breaking the https encryption, or even from someone wiretapping the phone. The danger comes from someone breaking into a company's database (whether the data were collected online or physically makes no substantial difference) or some other easy-to-grab cache of numbers. Everything else is just common theft that we've been dealing with for thousands of years, albeit a much greater value can be lifted in a much smaller package.

Re:Old data is the problem

[DrGreenGenes]

"Anybody who thinks highly critical data gets shuttled around on the public Internet has a lot to learn."

It is you who has a lot to learn. Unless you have a different definition of `highly critical data`. How do you think government departments all over the world communicate with each other? Online ordering (with credit card details)? Affairs behind partners backs? Credit card transactions over TCPIP?

The Code Book

[kmac06]

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

[wiredog]

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

[kmac06]

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

[GigsVT]

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

[autocracy]

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

[lars_stefan_axelsson]

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.

Re:So use one-time pads

[Luyseyal]

Postal Workers of the world rejoice! :)
-l

Re:So use one-time pads

[afidel]

A much more common source of randomness that was published in Phrack Volume 8 Issue 54 is to use a cleaned white noise signal from a soundcard. See This link for more details.

Definition of "Broken"

[therealmoose]

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"

[virve]

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?

Re:Definition of "Broken"

[RobertNotBob]

They use the Marketing term broken. A product is only broken if its reputation is so bad that people will not buy it.

Therefore the only broken product M$ ever had is WindowsCE. They had to rename it to PocketPC to get people to keep buying it.

"Clearly Office isn't broken. Look at the sales!"

Frightening...isn't it?

MAYBE?

[Winterblink]

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...

[BigBadBri]

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...

[leuk_he]

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.)

You said "and Schneier at least simplifies it ". AES is save to me! no way i am going to be able to break this in my lifetime. I might need read that sentence in a week or so, le alone the original paper.

Also note:It seems that the XSL might break AES 256 bits, but it is not certain. There is little chance however that it will break the most used AES 128 bits.. Funny, i would have gone with bigger keys, but they seem to get less secure.

Re:What Schneier really meant to say...

[BitterOak]

Also note:It seems that the XSL might break AES 256 bits, but it is not certain. There is little chance however that it will break the most used AES 128 bits.. Funny, i would have gone with bigger keys, but they seem to get less secure.

Recall that "breaking" an algorithm means finding a method of attack with a work factor less than 2^k where k is the key length in bits. "Breaking" in this context doesn't mean recovering plaintext of encrypted communications. Since they have demonstrated an attack with a work factor of 2^200, that means that 256-bit AES was "broken" but 128-bit AES was not.

Re:What Schneier really meant to say...

[leuk_he]

Like i said....

AAAARHG!!!!

Factorisation of large primes is easy

[Anonymous Coward]

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:This was completely predicable because...

[BigBadBri]

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

Re:Quantum computing =/= no privacy

[AxelTorvalds]

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.

���Quaumtum Computer will change the scene???

[Lolaine]

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.

Addendum

[seizer]

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

(See here)

Re:Addendum

[krtek]

In fact, number factoring problem was one of the first showed to be efficiently solved using quantum computer. No so long after there was showed that quntum computation couldn't buy much more. That is, yes, it's massively parallell but it doesn't bring all exponential problems into polynominal time. It's just a bit better parallell computer.

Re:Addendum

[rew2]

True, but the number they factored was 15.
Even *I* can do that. The problem with quantum computing is scaling it up, which is very difficult to do. I suspect it will happen, but not anytime soon.

Re:Quantum computing =/= no privacy

[afidel]

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.

One Time Pad != Encryption

[Kjella]

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

Re:One Time Pad != Encryption

[DavidMonks]

Why use OTP?

Because you can send a large quantity of key data, (handcuffed to a courier's wrist), verify they've arrived untampered with, then use them to encrypt future comms.

If someone intercepts the OTP key data, send a new lot with, if necessary, a new courier. So what if the key's pretty large? A courier could easily carry 10s-100s of DVDs if required.

OTP is as much a form of encryption as other methods which require secret key distribution. It isn't a public key system, that's all.

Re:One Time Pad != Encryption

[Sycraft-fu]

One Time Pads are still practial for situations where absolute privacy is a must. The intelligence community still uses them and I could even see a bussiness use them if it was necessary. IT's not quite as difficult as you might think:

You get a source of random data, there are plenty available and prepare a harddrive or harddrives that contain that data. Being that harddrive capacities are now in the 200GB range, you can get quite a lot of data. You then duplicate the drives once and only once. A secure, trusted courier then takes the drives to the other location where they are installed. You now have a good OTP system setup. Your encrypting/decrypting stations just need to be physically secure and keep track of what part of the pad has been used. When it's all used up, you destroy the drives.

Now I can't think of anything that needs this level of security today, but it's not so impratical that a company couldn't or wouldn't do it if there was a reason. Under this system you just have an encryption channel that will give you X total GB of data (half duplex) transfer before it has to be refreshed. This would give you teh capacity to use this to secure a company intranet or something, but it wouldn't be unreasonab;e to get a years worth of small messages that require the utmost secearcy to be transfered this way.

Re:One Time Pad != Encryption

[plcurechax]

So the question is, why don't you use the secure medium in the first place?

Because I only get to see my brother once a year in Cuba. And he has a problem carrying back CD-Rs of random pad material through customs.

verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well),

Passive evesdropping (aka wiretapping) does not interefere while verifing a public key fingerprint. So you can verify fingerprints of a public key in a public place.

OTP has other problems, beyond the typical key distribution problem. If a non-random source is used for generating the key material, or if the key pad is accidential reused, then trouble stikes, like it did with Venoma.

OTP also lacks message integerity, so if an attack could cut and paste blocks of encrypted ciphertext, Bob would not be able to detect the altered message if the decrypted text make sense (deposit $1000 to account #1233335632 rather than the modified message of deposit $4950292.95 to #1233335632)

encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).

Now what methods are you referring to here? Elliptic Curve Cryptography normally is used as a faster version of the Discrete Logarithm Problem (DLP) where it is faster and easier to Exponentiate (x^y) than it is to calculate its discrete logarithm (x such that g^x = h) which is the inverse operation and is much harder to calculate.

So I would be interested in this method of using elliptic integrals.

Quantum computing changes the games of cryptography, but it does not end the struggle of cryptographer vs. cryptanalysis. AES when used with a 256-bit key is expected to withstand a bruce force key search using quantum computing within the near future (less than 10-20 years). Of course quantum computing being a young field there is a chance that a radical discovery may ruin our present best estimates for future capabilitities.

Re:One Time Pad != Encryption

[shimmin]

If you're just sending text, then there's really no risk of running out of pad. Fill a zip disk with noise. Give it to the other party. Now, how long will it be before you've exchanged 100M of correspondence?

1 personal meeting yields a lifetime of secure communication.

Re:One Time Pad != Encryption

[ssimpson]

The definitive text on cryptography, The Handbook of Applied Cryptography, defines the OTP as a type of encryption...I know this is Slashdot but I don't think your arbitrary definitions help here.

Sending a CD worth of random data via a secure channel in advance and then sending an encrypted message with the knowledge that it will be unbreakable is sometimes worth prior thought. Sure, it may not be usefull for the masses who require this kind of security or don't know their going to communicate in the future but to claim that this cipher "isn't encryption" is bull.

Re:One Time Pad != Encryption

[Zygo]

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.

Ummm, it works just as well if your phone is being wiretapped. Public keys (and therefore their fingerprints) are public. All that anyone listening to the conversation can do is learn what GPG public keys you're using, so they can know which encrypted messages to archive. Later, after recovering the private keys from your cold, dead fingers, they can decrypt the messages and sit down for an evening of light reading.

It doesn't work if someone redirects your call to an agent who is unusually adept at voice impersonations, and who can supply you with a fingerprint different from mine. Of course there would have to be two such agents, otherwise we might later discover that we were not having the phone conversation with each other at exactly the same time, and we'd know that they keys were compromised.

As Bruce says, relax...for now.

[mbourgon]

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?

That's the wrong way to use them.

[dark-nl]

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.

Re:This was completely predicable because...

[Anonymous Coward]

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

One of the requirements of the AES contest was that the algorithms could run on an 8-bit smartcard. Therefore Twofish, Mars, RC6, etc also have 8-bit implementations.

Quantum computers will not change symmetric encryp

[j_dot_bomb]

It has been shown that quantum computers do not have the same effect on symmetric encryption that they do on public key encryption. They only cut the number of symmetric bits in half. Public key encryption however is changed to a polynomial problem.

Sounds like sour grapes...

[mh_cryptonomicon]

The Cryptonomicon.Net BLOG seems to imply that Mr. Schneier is doing a disservice to the community by limiting his dissing of algorithms only to the ones that competed with TwoFish... The blog author goes on to say that existing weaknesses in RC4 are probably more important than weaknesses in AES and asks the question, why didn't Bruce jump up and down about exploitable weaknesses found in RC4 over the last couple of years... It does sound a little like sour grapes...

Re:Sounds like sour grapes...

[epine]

I was in contact with the Twofish team during their candidacy concerning some work I had done on an improved instruction sequencing. One member of the team told me they figured rinjy was the most elegant proposal and that they would be very happy to see it prevail. Sure, they wanted to win. But more than that, they wanted the security industry to adopt a solid foundation.

There are times when Bruce has struck me as shrill or biased, but this isn't one of those times. What he's dealing with here is the very deep theme about whether the world's cryptographic fraternity is capable of sensing the right turn more often than not. If the wise men can't lead us to paradise, who can?

I'd say that's an issue worth talking about.

Re:Sounds like sour grapes...

[viega]

This is because RC4 has no significant attacks. Only the key setup had new significant problems, and there are two easy workarounds. That quickly brings RC4 back to the point where it's just as secure to use as AES in a streaming mode such as OFB or CTR.

That is, with every cipher out there, if you deploy it improperly, you might be subjecting yourself to problems. RC4 can still be deployed properly if you follow RSA's recommendations on how to use it.

The XSL attack

[jlcooke]

The XSL attack is highly subjective.

All you "so is GPG broken?" put your pants back on.

Summary of attack:
XSL stands for three of the basic operations in Rijndael and Serpent. The reason why this attack works is because the substitution layer of Rijndael/AES and Serpent can be expressed very neatly as the same domain as the Linear layers.

Now when I say 'neatly' I mean 'it would be possible' not no one's shown us this monster set of equations relatnig the (128+128/192/256) bit inputs to the 128 bit outputs. The Rijndael/AES and Serpent ciphers may be what we call "over defined".

Think back to high school when you have N liniearly independent linear equations and N-1 unknowns. You had an infinate number of posibilities for solutions. If you had N eqns and N unkn's you had 1 sol'n. If you had N eqns and N+1 unkn's you were in a funny place.

The authors suggest Rijndael/AES Serpent is in the latter catagory of the differential nature (and not the linear nature you learned in high school).

So what does this mean? The possibility HAS NOT BE EXCLUDED that this attack is possible. It really proves demostrates nothing that it's at all possible. Which is best anyone's been able to do in the past 6 years.

JLC

See sci.crypt thread:
http://groups.google.ca/groups?q=XSL+group%3Asci.c rypt

The end of my world?

[andika]

Uh, I was afraid that my boss would fire me tomorrow, because I have chosen the wrong algorithm. But wait, no, he have to wait until at least 2^80-ish days ...

Re:The end of my world?

[mh_cryptonomicon]

Well... actully it's more like the square root of 2^(100 - 16 - 20) days. The original attack indicated a complexity of 2^100. There's about 2^16 seconds in a day, and a standard PC can probably do 2^20 trial encryptions per day (um.. someone check my math on this... I haven't had very much coffee.) And you get the square root because I'm assuming it's sufficient to show that the ability to guess ANY plaintext / ciphertext pair in less time than brute force demonstrates the weakness. So, by my calculations, you're only safe for another 11 million years.

Re:Quantum computing =/= no privacy

[smyle]

when quantum computers arrive

I have a Quantum hard drive, but I didn't know they were getting in the PC business.

Hmmm... now that I think about it, I thought they got bought out by Maxtor. I think you're just bluffing about "Quantum computers" and this power they will supposedly have.

Re:US has quantum computing....

[mh_cryptonomicon]

Are you talking about the quantum computer that factored 15? Well... I hate to tell you this, but many 10 year olds can factor 15 in a tractable amount of time, but I don't feel threatened by their ability to "break" AES.

Bruce Schneier on the subject

[prostoalex]

Here's Bruce Schneier on the subject:

Some of the confusion stems from different definitions of "attack." To a cryptographer, an attack is anything that breaks the algorithm faster than brute force, even if it is completely impractical. To an engineer, an attack is something that is practical, or at least might be practical in a few years. An attack that breaks AES to a cryptographer might not to an engineer. The rest of the confusion stems from not being sure the attack actually works.

Some corrections to the article

[swillden]

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

This is really only true of public key cryptography. Symmetric ciphers (like AES, Twofish, Serpent and DES) depend upon really complex applications of transposition and substitution, not on mathematical problems hoped to be NP-hard (when recast as a decision problem, blah, blah, blah).

The breakthrough in the mentioned papers is just a collection of techniques used to try to create usable mathematical models of these complex mishmashes of operations, thereby allowing them to be analyzed and attacked. This is fundamentally different from public key encryption algorithms which are very simple and trivially easy to model, but reduce to models of (we hope) intractable problems.

Whether or not it is possible to create a symmetric cipher of sufficient complexity and non-linearity that it is impossible to cryptanalyze is, of course, an open question that will probably never be fully answered. In the arms race between cipher designers and cryptanalysts the top cipher designers have always managed to stay substantially ahead of the top cryptanalysts, however. Witness the fact that DES has withstood 30 years of concerted attack, without a significant attack being found (other than the built-in small key size, of course).

Speaking of DES, what I'm most interesting in knowing right now is if these new attacks can be applied to it. 3DES is still the most important cipher in the real world and will be for some time.

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

Again, bcrowell doesn't know the difference between symmetric and asymmetric ciphers. No one has devised a way to use quantum computers to attack symmetric ciphers. That's not to say it won't happen, but, as I understand it (not much), modelling complex problems in a QC is very, very difficult. QCs are good at simple problems with a large solution space.

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

If we lose all of our privacy it will be because we choose to, not because of any lack of technological tools.

Re:Some corrections to the article

[Effugas]

Asymmetric algorithms, by nature of their highly condensed problems(factor this number) are both vulnerable in polynomial time to an arbitrarily precise quantum computer, as Shor explains:

"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"
http://epubs.siam.org/sam-bin/dbq/artic le/29317

Given that all modern crypto protocols use some variant of asymmetric crypto to transmit their symmetric key, a break in the asymmetry eventually breaks the symmetry too.

That being said, I'm personally suspicious of quantum computing. Naive students learning about lossless compression algorithms inevitably believe they can apply the same algorithm multiple times, each time shrinking the data further and further. This actually works for some algorithms, for one or two runs. Eventually Shannon takes hold; the system refuses to compress below the level of entropy in the data (indeed, it starts to expand).

I suspect there's an analogous limit on the quantum scale, past which entropic capacity will prevent computation at high qubit levels. I could be wrong, and I'll be suitably impressed when the hardware shows up on my doorstep. But computationally relevant quantum logic hasn't been shown yet, and we shouldn't act like "it's only a matter of time".

It'll be something to be excited about if quantum computing proves feasible. I'd hate to see that achievement spoiled by "We've known it was possible for a decade."

Of course, I'm just being mildly cranky. I ain't a fan of quantum crypto either -- entanglement and crypto don't work too well in the same conceptual universe. A little skepticism is useful :-)

Yours Truly,

Dan Kaminsky
DoxPara Research
http://www.doxpara.com

Re:Some corrections to the article

[swillden]

Given that all modern crypto protocols use some variant of asymmetric crypto to transmit their symmetric key, a break in the asymmetry eventually breaks the symmetry too.

Actually, this is not always true.

It is true of most protocols used on the net, but other areas of secure computing rely pretty much exclusively on symmetric algorithms. For example, my work is primarily in security for systems involving smart cards. Given that:

• Distributing secure tokens like smart cards solves the key distibution problem;
• Symmetric algorithms are more vulnerable to certain non-cryptographic attacks when performed by small devices;
• The most common asymmetric algorithms have key sizes and processing times which strain the resources of small devices; and
• The asymmetric algorithms with small key sizes are often encumbered by patents...

...symmetric crypto makes more sense. Similarly, the banking system relies almost entirely on 3DES, more because of inertia than any security reasoning but, still, PK is rare.

In many, many real-world security scenarios, key distribution can be solved without PK, and in many cases the result is simpler and therefore more secure (complexity being the enemy of security).

I suspect there's an analogous limit on the quantum scale, past which entropic capacity will prevent computation at high qubit levels.

I'm not qualified to comment, but the more far-out claims for QC, even from those who understand it, seem much too good to be true.

Of course, I'm just being mildly cranky. I ain't a fan of quantum crypto either -- entanglement and crypto don't work too well in the same conceptual universe. A little skepticism is useful :-)

Certainly is :-)

I see quantum crypto as an interesting idea, but in practice I don't think it offers very much over what can be accomplished with standard cryptography. Sure, it's nicer to have a theory that allows you to say "I *know* no one is tapping this line", but unless your attacker is a major world government, a good symmetric stream cipher with a decent automatic rekeying system, plus some strong message authentication codes, is perfectly adequate. Actually, it's almost certainly adequate even if your attacker *is* a major world governnment.

Re:Some corrections to the article

[Effugas]

Excellent response.

Yes, smart cards do present an alternate solution to the key distribution problem, but as that multibillion dollar satellite tv lawsuit in Europe shows, nothing is tamperproof. (For those who don't know -- secret keys would be stored in cards that required millions of dollars of equipment to break open, but don't worry because the two competing companies would regularly fund each other's cards being broken into.)

I don't think it can be denied that certificate systems are a complete failure; however, asymmetric systems deployed with an eye for usability can actually be astonishingly interesting. SRP -- secure remote passwords -- essentially uses a password to authenticate anonymous DH. Interestingly enough, this causes the authenticating servers to have no idea what password they're authenticating, only that it works.

Sometime soon, we'll get SRP working as a centralized authentication daemon, and Kerb will finally meet its match :-)

--Dan

Re:Some corrections to the article

[swillden]

My point wasn't that smart cards are the solution, but that there are other ways to distribute keys. In fact the financial industry secures its internal communications with symmetric cryptography but without smart cards.

(As an aside, I'd like to mention that the pay TV card engineers face an insoluble problem and that their experience isn't a good example of the industry as a whole. Most smart card systems are designed such that the break of a small number of cards doesn't compromise the entire system, but the nature of broadcast systems is such that this isn't an option for pay TV. Also, besides the fundamental problem they faced, early versions were, frankly, terribly insecure in a multitude of ways.)

Regarding SRP, do you have a link to more information about the approach and how it compares to other secure password authentication protocols like EKE and SPEKE?

Re:Quantum computing =/= no privacy

[aminorex]

It will always be the case that crypto which depends
on computational intractability rather than a
demonstrable computational impossibility will always
be open to some future innovation rendering it
trivial to crack. Elliptic curve crypto seems to
have the best prospects for the future right now,
and you can use it right now: El Gamal is
implemented in GPG.

But to say that QC will render effective crypto a
historical artifact is clearly mistaken. If it
were true, it would imply that there are *no*
hard problems any more, once QC techniques are
employed. All that QC can do is compute functions
over a finite field with effectively infinite
parallelism. It's unfortunate that most crypto
systems today rely upon functions over a finite
field, but there are plenty of hard problems that
are only valid over function spaces, for example.

Heh..

[dwaggie]

The more we come up with ways with cryptology, inevitably we will come up with better cryptanalysis. Quantum computers will just introduce a need for more complex algorithms.. and not only that, but just because there's a quantum computer, that doesn't mean that current encryption protocols are laid bare like a prom-night virgin. Some of them will still perservere, if they're complex enough, past the advent of these machines.

And nothing will ever beat the age-old crypto of arranged signals.

Re:This was completely predicable because...

[mh_cryptonomicon]

Umm... you might be a little confused as to how AES was selected. AES selection criteria were public, as were discussions on the strengths (and weaknesses) of finalist algorithms. In addition, I know two of the AES conference program committee personally, and believe that had the NSA attempted any shinanigans, they would have been resisted and/or reported loudly.

These knee-jerk reactions to the NSA being evil really are counter-productive. Of course there are evil people in the US Government; there are evil people in every walk of life. I just don't think there are enough evil people in the NSA to conspire against the "good" people in the NSA.

You might be too young to remember, but back in the 70's there was a big commotion about the NSA modifying IBM's original S-Boxes. Many people at that time claimed very loudly that the NSA was inserting a back door into the algorithm. The NSA was pretty tight-lipped about why they made these changes; I think they still are, BTW. As it turns out, the original IBM S-Boxes were more succeptable to differential cryptanalysis than the ones the NSA reccomended for use with DES.

Remember that the NSA has a dual mandate. First, it is supposed to intercept, decode, and/or decrypt foreign elint intercepts. This is one of the reasons why they're one of the largest employers of foreign language specialists. Second, they are supposed to develop technologies to protect US national interests. The two missions sometimes conflict, but ever since Herb Lin at the National Academy of Sciences published his report on why it is in the US' national interest to allow widespread use of strong crypto for domestic applications, most (if not all) of the NSA types I've encountered have supported the development and use of strong crypto.

Of course, there are federal groups that like to sneak into people's homes and install keyboard sniffers. But, if that is going to be your law-enforcement surveilance technique of choice, why bother forcing bad crypto on the populous?

Where my cryptogram?

[Leto2]

If you're wondering why you didn't receive your Cryptogram this month, look in your spamfolder:

SPAM: -------------------- Start SpamAssassin results ---------------------- SPAM: This mail is probably spam. The original message has been altered SPAM: so you can recognise or block similar unwanted mail in future. SPAM: See http://spamassassin.org/tag/ for more details. SPAM: SPAM: Content analysis details: (5.6 hits, 5 required) SPAM: DOUBLE_CAPSWORD (1.1 points) BODY: A word in all caps repeated on the line SPAM: PORN_10 (0.6 points) BODY: Uses words and phrases which indicate porn (10) SPAM: ONE_HUNDRED_PC_FREE (3.4 points) BODY: No such thing as a free lunch (2) SPAM: PORN_3 (0.5 points) Uses words and phrases which indicate porn (3) SPAM: SPAM: -------------------- End of SpamAssassin results ---------------------

Re:Where my cryptogram?

[Leto2]

The Lameness filter prevented me from formatting this as an or

or

quantum computing & one time pads

[David Jao]

For a professional mathematician, reading all the uninformed opining here on quantum computing and one time pads is, frankly, painful on the eyes.

I'm a Ph.D student at Harvard. I've done cryptography research in the past. So listen up people.

1. Quantum computing does not destroy cryptography as we know it. It is important to realize exactly what quantum computing does and does not do. For symmetric ciphers, quantum computers reduce the cost of brute force search by a square root. So AES goes down from a 2^256 cipher to a 2^128 cipher. But 2^128 is still quite safe. And even if AES were to fall, it would not be an insurmountable problem to design something better.

   As for public key cryptography, most but not all public key cryptosystems are completely broken by quantum computers. Luckily we still have some public key cryptosystems that have not yet been broken using quantum algorithms. Elliptic curve discrete log is one such example.

2. One time pads are not the answer. Yes the security of one time pads has been proven but this proof relies on a stronger-than-you-think collection of assumptions that is almost never realized in real life. One time pads are very useful in certain situations but completely unsuitable for cryptography as most people use it.

Re:quantum computing & one time pads

[oh]

These slides (pdf) are a good intro to quantum computing, and explain how quantum operations could work.

Some of it is a bit above me, I think I will need to go back to my Uni text books before I can understand the proof on page 18. But it does go into some practical algorithms.

The page on error correction (page 27) is also sobering. Can anyone imagine a 100,000 bit computer that might only return one result every few seconds?

Re:quantum computing & one time pads

[Omnifarious]

The only voice of sanity I've seen in this entire discussion. Yay! Thanks.

Some Clarifications

[TheRealFoxFire]

I've seen a lot of mis-statements by various /.ers that I'd like to clarify:

- ElGamal is not an elliptic curve algorithm. Its a classical public key encryption system based on the discrete logarithm problem. Most DL problems can be refactored as elliptic curve problems though, so perhaps the poster was referring to a possible EC ElGamal. At any rate, I'm pretty sure GPG uses classical ElGamal.

- Symmetric ciphers are rarely broken by raw computational power (brute force). In fact, algorithms above about 80 bits are impossible to break by brute force due to the laws of physics.

- Quantum Cryptography today involves means of transmitting data at very low bitrates over a channel in which eavesdropping is impossible. QC is pretty much only useful for exchanging keys for symmetric algorihms (like AES, Twofish) securely, as the data rate is to slow to be practical for anything else.

- Assymetric Cryptography (public key) is based on several hard problems. The two that are used widely today:
* The prime factoring problem (RSA)
* The Discrete Logarithm problem (DSA, ElGamal)
One will become widely available soon:
* The elliptic curve problem

- Yes, OTP is still perfectly secure, but its still perfectly useless, as w/ OTP you just shift the security to two other areas; truely random pad generation, and secure distribution of the pads.

Re:Some Clarifications

[adb]

- Yes, OTP is still perfectly secure, but its still perfectly useless, as w/ OTP you just shift the security to two other areas; truely random pad generation, and secure distribution of the pads.

So? Both of those problems exist for every other crypto algorithm, too. OTP just makes them the only problems. (Well, "endpoint security" is the other problem you don't mention.)

Re:Some Clarifications

[adb]

I do not believe that is true. Regardless of your encryption method, you can't prevent man-in-the-middle attacks without information that has been securely shared in advance. That's one of the reasons for key-signing parties.

Re:The cost of decryption the cost of the data

[MultisSanguinisFluit]

Here here!
Although, the time factor should be mentioned. We must assume (and good cryptographers do) that any cryptosystem can be broken given enough time and/or enough effort. So one must consider two things:
1) How valuable is this secret? This translates into how much computing power (read: money) a cracker is willing to invest in its decryption.
2) How long does this need to remain a secret? What is infeasible to crack now will not (I say WILL NOT) be infeasble to crack in some number of years.
The secrets encrypted by the Enigma, for the quintessential example, were extremely valuable. They did not have much computing power then, but they were willing to invest a lot of effort to crack these messages. Now they can be cracked quite easily on a PC.
Why do I mention this? Sure, there may be an attack against AES that works better than brute force, but that is probably not a reason to stop using it now. It would appear that it would still require an large amount or resources to crack an AES message. Even so, assuming your keys are exchanged using asymmetric crytpgraphy, only one message gets cracked. If you want your secret to remain secret forever, you shouldn't be using an open channel to begin with.

'the' or 'you'

[wiredog]

Don't encode 'the' or 'you'. Encode them as parts of phrases, or leave them out where possible.

I used one time pads in the army. You wouldn't use one to transmit War and Peace. But you would use it to send "Attack is Tomorrow, sell IBM". Or to send "Name of agent in NSA is CowboyNeal."

Those would be encoded as the phrases "attack is tomorrow", "sell IBM", "name of agent","in NSA". The word "is" could be encoded, or dropped (the sentence would be parseable without it.) Only "CowboyNeal" might have to be encoded letter by letter. Or it could be encoded as "cowboy"+"n"+"e"+"a"+"l".

Generally, using a one time pad to encode letter by letter is a bad idea. Done only when there is no alternative.

Re:'the' or 'you'

[Peter T Ermit]

Sorry -- dark nl is correct, and you're wrong. Here's an example of how to use a one-time pad: Your pad = random string of bits, like 0111 0101 0001 Your message = string of bits, say, 1010 1010 1010 Encrypted message = pad XOR message = 1101 1111 1011 Decrypted message = pad XOR encrypted message = 1010 1010 1010. It has nothing to do with substituting for words or letters. The drawback to one-time pads is that each side needs to have the same pad, which must be at least as long as the message to be encrypted. The pad has to be shared and stored in a secure fashion, which makes it impractical in most cases.

Re:'the' or 'you'

[gclef]

I think you're arguing two different points. You're worrying about how the pad actually works, and he's worried about maximizing the use you get out of the pad (by dropping unnecessary words out of the message to be encrypted). These two worries are clearly related, but not identical.

I would say that he is correct: in practice, you would want to drop unnecessary or redundant info out of the message. Since OTPs rely so heavily on securely sharing the pad, you want to maximize the use you can get out of the pad you have without re-use. This means dropping redundant words. In common computer practice, we'd just zip the damn thing before sending it, hopefully greatly increasing the entropy (and decreasing the length) of the message before even bothering to encrypt it, but that's a whole other topic for discussion.

Re:'the' or 'you'

[Rich0]

I think the original poster was proposing an old-fashioned code book. So sending the number 01 means attack at dawn, and 02 means retreat. This is theoretically unbreakable as long as you don't send the same code more than once.

The key to a one-time pad is that the pad is random - which he achieves, and that it is used one-time. This is where he is likely to stumble. Removing common words increases the security of a codebook, but it is still breakable. It may be really good, but it will always be breakable. A true one-time pad is absolutely unbreakable - and this is mathamatically provable. To decode a one-time pad encrypted message you need the message, and the pad. It isn't even succeptible to brute-force like all symmetric cyphers (assuming the message is longer than the key - otherwise a symmetric cypher actually is a one-time pad).

Using XOR isn't really critical - it is just a quick way to transform the data.

Re:'the' or 'you'

[Peter T Ermit]

Actually, the entropy of the message doesn't matter with a one-time pad, so long as your pad is truly random, but you're right that compressing the message gives you more use out of that pad.

Re:'the' or 'you'

[Peter T Ermit]

Codebooks aren't actually unbreakable, as you point out in your second paragraph. There's still redundancy (if nothing else, through syntax) that can give you a better-than-brute-force attack, even if it's impractical to crack the message.

And as for XOR; you're right. However, it's almost always used because you need a reversible bitwise function. I can only think of four, two of which are trivial, leaving only XOR and (not XOR) as your possibilities. If you do operations on chunks larger than bits, you have more options, though.

Re:'the' or 'you'

[jareds]

Codebooks aren't actually unbreakable, as you point out in your second paragraph.

I think he meant that codebooks are unbreakable if you don't send the same codeword more than once, which is true, although nobody uses them that way.

Re:'the' or 'you'

[Qwerpafw]

you are exactly correct. Unfortunately, people have misinterpreted what you said. I will try to elaborate on what I understand your method of one time pad encryption to be.

Step one: get your message

Step two: take the message, and convert each word or phrase to a number, using a crib sheet

Step three: encode using the onetime pad.

Now, from my understanding the one time pads issued were really and truly "one use only," (or else they are not really secure) and had to be generated by some HQ guy so everyone would be on the same page.

what the above means is that you use the pad sparingly.

e.g.: If 99 means all forces, 01 means attack, and 02 means dawn, then you can encode 990102 in the one time pad, getting something like 168257, or whatever. If they have the same pad, and they decode it, they will get "990102," after which they quickly figure out the message contents.

"990102" is a heckuva lot shorter than even allforcatckdawn: 6 decimal chars vs 15 base 26 chars.


assuming you use one number per letter (base 26 or something), then changing the system to a two digit number used to encode a word is much much more efficient. Since your one time pad is probably used and then tossed, efficiency is critical. The pads are hard to come by and a good compression scheme drastically reduces the amount of pad space a message uses

Summary: Compress messages before encoding with pad to save pad space. Compression != encoding.

Re:Quantum computing =/= no privacy

[smallfries]

It will not carry over routers and absolutely cannot be used for normal internet email for instance.

Err, thats not strictly true, take a look at the top link in Google

Re:Quantum computing =/= no privacy

[stevelinton]

Very interesting. Thanks for the link. Still a long way from implementation though.

here's the proper url

[Alejo]

attacks on AES

All bets are off for current technology...

[pVoid]

Going from our 'digital' encryption schemes to quantum encryption will most likely be like the leap between analog to digital (multi band-pass filters for example don't make any sense in the digital world - at least not the way they were implemented for analog).

In the same way, the tools will most likely change radically when it comes to security. And I don't know if they'll even be called encryption at that point... maybe more like 'Eisenbergification'...

There was an interesting article a while back about a mathematician who proposed that if we could generate a constant stream of truly random bits (quantum helps here), and have that stream be broadcast around the world (in synch to everyone), that it would be possible to have unbreakably encrypted communications (basically the "throw-away pad" idea on a mass scale). (sorry, I don't have time to look up the link)

So bottom line is, probably current technology will become obsolete, but that thing those nerdy scientists are cooking up in all of those 'hoakey'
25 dimension universes called abstract/pure physics/math will probably generate some brilliant ideas.

Re:All bets are off for current technology...

[pVoid]

Here's a link to the scheme I was talking about:

http://www.interesting-people.org/archives/inter es ting-people/200103/msg00056.html

Just make bigger keys

[jeremyhu]

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

When quantum computers come around, it'll be easy for them to break, say, 1024 bit RSA encryption, but by then, we'll all be using 1024 Terabit encryption (or something gross like that). As long as we (as individuals) have access to computing power within a few orders of magnitude of those trying to break our encryption, everything will work out fine

Re:Troll

[BigBadBri]

woohoo - someone told you about one-time pads!

Physical security of the pad is the problem here - if the pad is stolen, the encryption is broken, period.

The use of public key crypto is widespread because it is proof against this sort of attack (assuming you keep your private key secure, of course ;-)) - the only issue with public key is how difficult it is to crack, which doesn't depend at all on how heavily it is used, but simply on the algorithm and the key length. The public keys can be transmitted in the clear, since it is *very* difficult to extract the private key from them. Hence they do not suffer from the security and convenience problems inherent in the one time pad methods.

The whole point of public key is that it is extremely time consuming to crack messages, so it's not worth trying most of the time.

You're still a fucking troll.
Love,
Brian.

Re:This was completely predicable because...

[BigBadBri]

Oops - didn't check first...

but it was supposed to be a humourous comment anyway....

Bri.

So please do tell...

[Julian Morrison]

Something that REALLY needs to be put on Crypto-Gram: the current guesstimated safety ratings of crypto algorithms, ranked safest-first.

Yeah I know this can never be guaranteed, but it's a damn sight better than making uneducated guesses. Because, eventually, ya gotta pick one when developing/choosing crypto based stuff. If the mathematicians won't say, Jow Blow has to guess and hope.

Not exactly...

[autopr0n]

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

Well, except for quantum crypto, which IIRC is actualy as secure as one time pad.

Re:Quantum computing =/= no privacy

[ssimpson]

No - Mix + Mash ciphers aren't automagically immune, see quote from Schneier:

"While quantum computation can make problems such as factoring and discrete logarithms (which public-key cryptography are based on) easy, they can only reduce the complexity of any arbitrary computation by a square root. So, for example, if a 128-bit key length was long enough pre quantum computation, then a 256-bit key will be long enough post quantum computation."
-- B.Schneier, 10th Oct 1998 posting to soc.history.what-if USENET group

E.g. 3DES will be pretty much toast, as will AES128.

Different implementations

[wiredog]

I'm talking about the classic implementation. You have two columns. Left column is the lits of words/phrases, right column is the list of codes used for those words/phrases. It can be done by hand (as I did it in the Army), or automated.

The Army still uses one time pads that way.

Re:Different implementations

[Peter T Ermit]

As Rich0 pointed out, this isn't a "one-time pad" as understood by cryptographers, even though you may have been using your code a single time. This is a codebook, and it is not 100% secure. One-time pads, on the other hand, are the only provably 100% secure cryptosystem.

Re:Different implementations

[Shardis]

Sorry, every cryptosystem (pretty much by definition) has weaknesses. Spouting that any cryptosystem is %100 secure is just plain silly. There are a few good books on applied cryptography out there, some even in libraries. They're worth a read.

Re:Different implementations

[Peter T Ermit]

They're worth a read. Thank you for your condescension. I've read plenty of crypto books. The one-time pad protocol is 100%, provably secure. Period. The only weaknesses don't have to do with the protocol itself. Flawed implementations (insecure pad; non-random generator of pad, etc.) will ruin any cryptosystem. And if you're objecting to my use of the term "cryptosystem" instead of "protocol" in the previous comment, you obviously know what I meant, so why the fuss?

Re:Different implementations

[Shardis]

Oh good grief... Look, I'm not going to quibble over terminology that doesn't matter. I just meant that saying that *anything* is %100 secure is just a load of poppycock. It makes the whole crypto community look bad. There are always ways, even if they're not known yet.

And yes, I know that the two examples of the "implementation" for the one time pad are pretty much the only ways to skew it...

Also, I didn't mean to be condesending, just thought you didn't know much about crypto since every cryptogeek and theorist I know is always very careful not to make blanket statements like that, since they are usually very aware that there is no such thing as a "perfect" cryptosystem. If it can be reversed at all into a decipherable message reliably and consistantly, it can be brute forced (in enough time), or weakened/broken by analysis, or both.

Re:One Time Pads Not Secure!!

[MultisSanguinisFluit]

Not correct. What you are not taking into account is that every possible plaintext is just as likely to be the correct one. A quantum computer may be able to give you a thousand different decryptions for a given ciphertext, all of which turn out to be completely valid messages according to whatever criteria you are using, but it won't be able to tell you which one is the true decryption.

Old news, Schneir just found out

[Brad Lucier]

These attacks were developed to try to analyze and defeat the Tame Transformation Method (TTM), but they failed---one can increase certain parameters in TTM, the same way one can increase the size of RSA keys, to make such attacks too expensive. Remember, every key can be broken given enough CPU power and time; all security is relative.

Schneier was informed about the TTM method years ago, and the attacks themselves are over a year old. It was clear that the same attacks applied to AES, perhaps if Schneier had taken the time and trouble to understand TTM when he first had the opportunity he would have been sounding the "alarm" earlier. Now maybe the attacks are news because AES is much better known than TTM. And perhaps one cannot increase the complexity of AES to increase the number of operations necessary for reasonable security (and 2^100 security, the numbers Scheier notes in his newsletter, will last for at over 10 years, no problem).

Unbreakable cryptosystems.

[wisemat]

It amuses me that no one has mentioned the one time pad. Granted, because the Key is as long or longer than the message being transmitted it is very, very rarely useful in practice, but it is a conventional cryptosystem which is unbreakable even with quantumn computing.

http://world.std.com/~franl/crypto/one-time-pad.ht ml

Re:One Time Pads Not Secure!!

[2short]

So, you get all possible plaintext messages. a few of them are:

Attack at noon.
Do not attack.
Let's eat squid.

Which is correct? The only way to defeat a one time pad is to have the pad.

Rijndael variant which should foil this attack

[Kiwi]

The reason why the kinds of attacks which convert Rijndael in to a complex system of equations look risky for Rijndael is because Rijndael has an S-box which is very easy to describe algebraciaclly. The solution is to replace Rijndael's S-box with another S-box.

In fact, the Rijndael designers were considering changing Rijndael's S-box during the AES process. NIST, however, for not entirely known reasons, did not allow the Rijndael designers to do this.

Now, as it turns out, the Rijndael designers have designed some other ciphers after Rijndael. These ciphers have different S-Boxes. In fact, the Rijndael designers revised ("tweaked" as they call it) each cipher to have a representation which is easy to implement in hardware; most of the die space used when implementing Rijndael on an ASIC is implementing the S-box.

The ciphers in question are Whirlpool and Anubis (Anubis uses an involutional S-box which might possibly make it weaker). In fact, my software project does not use Rijndael proper as a psudo-random-number-generator; it uses a Rijndael variant with the "tweaked" Whirlpool S-box.

- Sam

P.S. I should also mention Khazad, named after the bridge Gandalf fights balrog at, which uses Anubis' S-box.

Re:One time pads important assumptions?

[mkettler]

The fundamental problem with practical use of one time pads is that you need a separate secure mechanism by which to agree upon the pad. And of course, to be absolutely secure that pad needs to be:
1) truly random
2) only used one time
3) as long as the data to be encrypted.

Those three are the assumptions about the pad required to reach absolute security that make OTP's impractical. If all three are not met, or the exchange is not secure, the security of the OTP is no longer absolute.

Most generation mechanisms that are truly random only generate the pad at one location. That will result in you needing to courier the pads to the party that will eventually receive your messages. If you can already securely courier the data of the pads, in most cases it makes sense to just courier the data itself.

Some alleged one-time pad systems that are practical use a password or short random secret fed into a PRNG to expand the key to the length needed as a pad. However the output of a PRNG is not truly random, and thus the security of the "unbreakable" one-time pad is reduced to the strength of the PRNG against prediction. Most PRNGs are weaker than brute-force analysis of a 2^128 key block cipher. Many PRNG's are actualy highly linear and very predictable (see some of the research on TCP sequence number prediction to see just how hard it is to get a PRNG that isn't trivially predictable.) There is EXTENSIVE cryptographic research pointing out how foolhardy it is to think that a PRNG extended key is as secure as a OTP, and thus unbreakable.

Another practical problem for OTPs is the storage of the pad itself. The pad is quite lengthy, at least as large as all the secure data you want to transmit before exchanging pads again, and needs to be stored in a secure fashion at both the sender and recipient's facilities.

One of the primary reasons for the creation of block ciphers and other symmetric encryption mechanisms is that they reduce the amount of data that you need to securely exchange into a relatively small key. That small key can then be used in the transfer of a significantly larger portion of data, and it is now possible the algorithm is weak, but at least the small keys make these ciphers by far more practical to use in real-world situations than a OTP.

AC is Troll or Clueless on OTP vs QC

[billstewart]

As the other posters have pointed out, quantum computing doesn't affect One-Time Pad security. The glaring weakness in AC's argument is that the computation to determine whether a guess is correct is NOT polynomial-time - there's no way to tell if a "1" in the cyphertext is a message bit of 0 and a pad bit of 1 or the other way around.

In normal public/private hybrid systems, you use the public-key algorithm to encrypt a random secret session key, and then use the session key with a symmetric-key algorithm to encrypt the message. For some popular categories of factoring-based public-key algorithms, a hypothetical QC can instantly factor the key, and you can do the polynomial-time validation to show that the decryption key you've pulled out of the quanta matches the public encryption key. (OTPs don't let you do that.) You can then use the session key to crank the symmetric-key algorithm. The lead article that this discussion is about deals with weaknesses in the new symmetric-key algorithms that all of us were hoping we could use to replace Triple-DES, which appears to be very strong but is slow and clumsy (and neither 3DES nor AES appears to be attackable using QCs.)

Since widespread use of OTPs means a return to lots of couriers with briefcases attached to their arms, I suppose there are some non-mathematical ways to use QC to attack OTPs - hit the courier on the head with the QC, and then use the liquid helium from the qc to help shatter the handcuff chain, or offer the courier a Quantum Computer as bribe, or whatever :-)

... but crypto is mathematical

[billstewart]

No, it's not just brute force, and you'll have to think mathematically, at least real briefly, to get the concept. It's easy to build cryptosystems that are exponentially hard to crack - adding 1 bit to the key length doubles the effort required to crack it. If you have a 100-bit key, then adding 1 bit makes your job 1% harder (or more commonly 2% or sometimes a bit more) and makes the cracker's job 100% harder. Adding 10 bits makes your job 10-20% harder, and makes the cracker's job 1024 times harder. Adding 100 bits makes your job 2-4 times harder, and makes the cracker's job ~10**32 times harder. If the cracker's computer still fits on the planet, you can add a few percent to your workload, and the cracker has to buy another planet for his computer. Repeat as often as needed.

The way you crack these algorithms is to throw mathematicians at them until some of them stick. Once you've done that, if there's anything left to bother with, then you can figure out how many processor cycles you'd need to throw at the problem to break it, and decide whether that's feasible.

If your conclusion is that it's not feasible to break, then you need to decide whether to use rubber-hose cryptanalysis to get the key, or steal the target's computer where they saved the unencrypted version, or look for the yellow sticky notes next to their desk, or put a camera in their ceiling to watch them type in their keys.

Re:Quantum computing =/= no privacy

[muon1183]

I believe you hit the point right on. Cryptography based on finite calculations (no matter how difficult) can at some point be broken. As long as the cardinality of the solution space is finite, it will eventually be cracked. However, should we switch to using a completely new system, with a solution space of cardinality of at least Aleph Null, many problems would be solved. However, this is far more difficult than it sounds. Most of the work going on in L2 and infinite dimensional hilbert spaces (and any other infinite dimensional spaces) is not being applied to cryptography. This is not to say that it can't be used for cryptographic purposes, it's just that much of the mathematics that goes on in these areas is very different than what the current cryptographers, discreet mathematicians, are doing.

One-time pads

[some guy I know]

I have developed a completely unbreakable one-time pad.
Here it is:

3289743289702349802 872378238732879 238732870932098732 34278324890324 7832487923809723 23870945457 301208701912 012071203 4309873432 6210789216 320934246932 120107630128732 050 4044354543 0 207023501324 402307420 213078430 073240324

Use it as often as you wish!

Re:One time pads important assumptions?

[DrGreenGenes]

>separate secure mechanism by which to agree upon
>the pad.

Meeting a friend in person. If you meet up with friends regularly, then this is not a problem.

> 1) truly random
Lavarand. Webcam pointing out of your window mixed with lavarand mixed with the data taken from rips from each cd you play in your pc mixed with other `random` numbers from noddy programs mixed with bits and pieces from your swapfile mixed with digitized input from a PCI radio/tv tuner tuned into inter-station noise mixed with data from Numbers Stations. You could also use traditional encryption to encrypt this random noise... Really, its very easy to get random numbers.

Remember, if you`re XORing this stuff together, it doesn't matter if any given element is not random, as it will not make the resulting number less random.

2) only used one time
No problemo.

3) as long as the data to be encrypted.
See 1. You can leave that running and generate a few megs a day...you can burn as many CDs of it as you like.

"If you can already securely courier the data of the pads, in most cases it makes sense to just courier the data itself."

True in certain situations, but mostly you`ll want to communicate when you are not together physically. A few CDs of random numbers should last you a fair old while if you compress messages before encryption. Each message may only be a few k, so even 1 cd should last you months, if not years.

> storage of the pad itself

Could be anywhere. If its a CD then you could put the data as a bonus track on an audio CD. There are many storage devices available today, remember. USB non-volatile RAM, floppies, CDs, magnetic stripes on cards, files on PCs...

Re:One time pads important assumptions?

[mkettler]

Agreed, it's not impossible to use a OTP, and there are situations where it isn't much hassle. The case you describe is certainly realistic, however it is not very common and the benefit of OTP for this situation is unclear.

Generaly the most valuable data transferred is transmitted in circumstances where OTPs aren't practical. Sure it's easy to use for your buddy across town, but what about the corporate office halfway across the world that needs a product design worth 100's of millions of dollars of the open market. Or what about the corporate VPN which transfers 100's of megs a day?

And yes, OTP is possible even in these situations, but the practicalities are so difficult and costly that it's rarely, if ever used.

Let's face it, I've never had any personal information in my possession worth more than a house. Sure, some information is personal finances, and some of it might be embarrassing, but embarrassing me, or embezzling a few grand from my credit card account doesn't get anyone anything worth the effort of analyzing a decent (2^80 or longer) block cipher. Heck, I'd question if anything personal to me was worth breaking a 2^56 cipher like DES, and that doesn't take very long, but I'm not taking that chance in general.

Any block cipher can be brute-force broken given enough time and enough money. They question you have to ask is the information protected valuable enough to be worth spending the time and money on? Does someone really want to dedicate a several million dollar machine for several years to break a 2^64 strength-cipher you used? That information would still have to be worth a decent portion of the cost of the machine after a few years of crunching.

In reality the most practical uses of OTP's are the situations where the added security of a OTP is more-or-less moot. If I'm in close physical proximity with frequent meetings, and it's only to a friend, the value of the data is low, and the odds that I'm going to have anything to say that I can't say next time I see them is also low.

It's larger organizations like banks, companies, and governments that are exchanging large volumes of information that make the fattest, juiciest targets for analysis and they can't deploy OTP's for all of their needs, there's just too much data to do so.

Are your secrets worth more than theirs?

Re:One time pads important assumptions?

[DrGreenGenes]

I`m not sure why you think OTPs are so a) expensive and b) clumsy to use.
The actual program to do the en/decryption can be written in VB in a few minutes - it's trivial.

A company wanting to use crack-proof encryption to convey 'a product design worth 100's of millions of dollars ' can surely afford to buy a PC to sit in a room, filling a hard disk with random data, and occasionally burning that data onto CDs in pairs. Check the disks are identical once burned (another cheesy VB program that'll take a few mins to write), physically take one of those disks to the location you`ll be emailing with encrypted data and you`re set!

"Does someone really want to dedicate a several million dollar machine for several years to break a 2^64 strength-cipher you used?"

Who knows? I don't know if someone is onto my (fictitious!) company with its valuable product designs. No-one knows except the people snooping around, and they aren't talking. Given that the cost of implementing a 100% uncrackable OTP are in the order of 0.000001% the cost of the product designs, who wants to get it wrong so they can find out?

"It's larger organizations like banks, companies, and governments that are exchanging large volumes of information that make the fattest, juiciest targets for analysis and they can't deploy OTP's for all of their needs, there's just too much data to do so."

Possibly. Then again, they have secure vans for collecting cash - surely its not beyond the realms of possibility to create a disk for each branch in a region each day/week, ship them around in the vans and use them.

It boils down to - do you really need to have the data 100% secure. If you don't, then of course don't do it. But if you even think you might do, then surely it makes sense to have the ability to do it in place, so you can use it if you need to.

Re:One time pads important assumptions?

[mkettler]

First off, a point I agree with you on:
>It boils down to - do you really need to have the
>data 100% secure. If you don't, then of course
>don't do it. But if you even think you might do,
>then surely it makes sense to have the ability to
>do it in place, so you can use it if you need to.

Agreed. If you really need it, nothing else will do. However, encryption is only one tiny piece of security, you'd better be sure the rest of your setup is up-to-snuff:

> I`m not sure why you think OTPs are so a) expensive and b) clumsy to use.
>The actual program to do the en/decryption can be written in VB in a few minutes - it's trivial

a) because it is clumsy and b) because it is expensive. This has been proven, Governments have and do use OTP's. There is a genuine reason why OTPs are rarely used in even government/military applications anymore.. it was too clumsy and too costly FOR THEM to use in realistic scenarios. Really, People aren't just discounting it without trying it.

I'll give you the application can be trivialy written in any language, heck, you can do it by hand easily enough. But the cost of actual use of OTP's is high when you realize how much surounding security is needed:

1) secure random number generation:
hardware: ~$700, consisiting of a dedicated PC w/CD burner a camera and a few lavalamps.
software cost: free
facilities: if you want this cipher to be more costly to break than analyzing a block cipher, you'd better be damn sure that breaking in here is a multi-million dollar adventure. If someone can pick a lock, break in and copy your pads, you're lost.
Dedicated room, Monitored alarm system, tamper-seals on system, high-grade locks, extra heavy walls.
~8,000 + alarm service fees.
2) OTP software: free

3) Trusted personal exchange of OTP CD's (again, you have to be sure nobody can copy these, so it must be hand escorted).
Travel expenses: ~$10 - $1000, depending on where your associate is and how far you have to go.
Salary for 2 days: (I'm thinking corporate, or your cost of missing work for a few days) $160 - $1600, depending on payrate of person traveling. (note: this only applies if the travel isn't across town and involves flying somewhere far)

This can probably be restricted to once annually

4) Burglary Rated safe ( TL-15 or better, preferably TLTR-30 or better) to store the pads in:
~$1000 (assuming TL-15) per site, per safe.
(note: the fire safes you can buy at target are NOT designed to resist burglary attempts).
Again, if someone can break in, grab and copy your pad, it's not secure. If you aren't worried about breakins, why are you worried about unbreakable encryption? :)

So once you start including physical security to obtain a minimal level of safety against having your pad stolen, yes.. it is damn clumsy and quite expensive.