I have a question about the future of cryptography.

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

emo samurai
Posts: 53
Joined: Fri Jan 18, 2008 3:29 am UTC

I have a question about the future of cryptography.

Postby emo samurai » Fri Jan 18, 2008 3:35 am UTC

I'm writing a sci-fi book in which the main character has a distributed computer like seti@home that he spreads like a computer virus in order to hack computers. People don't know they have a client installed on their computers, and he has around 50 million pc's and future iphone equivalents taken over.

This book takes place 50 years in the future and assumes no major advances in quantum computing. If Moore's law stayed more or less constant, how many bits would standard encryption use? I know they use 1024 bit encryption now. And how long do you think it would take him to crack the code with his distributed computer?

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Fri Jan 18, 2008 4:22 am UTC

According to http://www.ssh.com/support/cryptography ... etric.html, 2048 should be secure for decades to come. So it would not be unreasonable to say that everyone is using 2048 in your future.

Particularly since Moore's law cannot last that long.

There is a minimum amount of heat that has to be released in any irreversible computation. Our computers do a lot of irreversible computations. There is an upper limit on how fast heat can be conducted away by any known materials. The result is an upper limit on how rapidly irreversible computations can be done.

Based on a Google search (I did not buy the article), the details should be discussed in http://csdl2.computer.org/persagen/DLAb ... 002.998636.

Now nobody knows how close we'll get to this theoretical limit. We think that there are a few more years left. But if you're setting your article 15 years out, it would make sense to say that Moore's Law continued until, say, 2020. Give your basic computers specs that are about 20 times today's top of the line desktops.

However you can then get more impressive with ubiquitous computing. The idea here is that there is an upper limit on what one CPU can do, but nothing stops you from having lots and lots of CPUs in parallel. (In fact computers are already moving in this direction.) The problem is, though, that lots of CPUs in parallel, each putting out a minimum amount of heat, takes a lot of energy and produces a lot of heat. You can deal with this in a data center, but in a handheld device, it isn't such a big win.

So your future should have more powerful computers than todays, but not astoundingly so. However computers will be embedded everywhere.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

emo samurai
Posts: 53
Joined: Fri Jan 18, 2008 3:29 am UTC

Re: I have a question about the future of cryptography.

Postby emo samurai » Fri Jan 18, 2008 5:46 am UTC

Actually, that makes it perfect for the sake of his distributed codebreaker. If computers don't become a lot more powerful, but they become smaller and more plentiful, then the codes can't become that much more complicated without clogging up communications, but his distributed computer becomes 15 times as powerful as a desktop-dominated market would be. I mean, the individual computers couldn't handle very powerful cyphers, but since he has so many computers to use, he can hack any 2048 bit cypher with ease.

User avatar
Daemonic
Posts: 32
Joined: Sat Sep 22, 2007 9:40 pm UTC
Location: Waterloo, On
Contact:

Re: I have a question about the future of cryptography.

Postby Daemonic » Fri Jan 18, 2008 1:29 pm UTC

1024/2048 bits for what kind of cryptography?

For public (asymmetric) key, it probably is on the low side for 50 years from now... even more so depending on which method of public key encryption you are talking about (for example, a 1024-bit ECC key is a stronger key than a 1024-bit RSA key).

For symmetric key, it is probably more than sufficient (256-bit is considered very good right now).

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

Re: I have a question about the future of cryptography.

Postby Workaphobia » Fri Jan 18, 2008 9:12 pm UTC

First of all, as Daemonic said, the strength of a keysize depends on the algorithm you're talking about. For instance, RSA uses the product of two prime numbers as part of its keys, but not all bitstrings of the required length are valid numbers in this sense. Symmetric algorithms in contrast can often use all possible keys, so far fewer bits are necessary for the same level of security. In the old days (i.e., early 90s) of very strict US export rules that classified reasonably strong encryption as munitions, it was illegal to ship products outside the country that were capable of using encryption with keysizes greater than 40 bits. This was laughably weak, even for those times. Netscape essentially had to release two versions of their browser: one for America that had normal SSL, and one for the international community that was exactly the same but leaked most of the key bits. This restriction also forced CSS (Content Scrambling System, the DRM mechanism on DVDs) to only use 40 bits, making it possible for desktop computers to actually brute-force a movie in a few minutes. 128-bit and 256-bit keys on the other hand are considered secure these days, for symmetric algorithms. 512-bit for public-key algorithms are not so great, compared to 1024 or 2048.

By the way, if you've ever seen the movie Swordfish, the moment I laughed/cried the hardest during the entire movie was when they made use of a 128-bit RSA key.


btilly wrote:Now nobody knows how close we'll get to this theoretical limit. We think that there are a few more years left. But if you're setting your article 15 years out, it would make sense to say that Moore's Law continued until, say, 2020. Give your basic computers specs that are about 20 times today's top of the line desktops.

To be pedantic, 2 ^ ((2020-2008)/1.5) ~= 256 times more powerful.
btilly wrote:However you can then get more impressive with ubiquitous computing. The idea here is that there is an upper limit on what one CPU can do, but nothing stops you from having lots and lots of CPUs in parallel. (In fact computers are already moving in this direction.) The problem is, though, that lots of CPUs in parallel, each putting out a minimum amount of heat, takes a lot of energy and produces a lot of heat. You can deal with this in a data center, but in a handheld device, it isn't such a big win.

Yes, but the number of processors wouldn't increase exponentially as Moore's Law has, would it?

emo samurai wrote:Actually, that makes it perfect for the sake of his distributed codebreaker. If computers don't become a lot more powerful, but they become smaller and more plentiful, then the codes can't become that much more complicated without clogging up communications, but his distributed computer becomes 15 times as powerful as a desktop-dominated market would be. I mean, the individual computers couldn't handle very powerful cyphers, but since he has so many computers to use, he can hack any 2048 bit cypher with ease.


No no no no no no no no.

Ok, let's assume that you have a cryptographic message you want to decode (break, since you don't have the key; you are an adversary). Let it be a symmetric 256-bit cipher, for instance. If you don't know any algorithm that breaks the system, as is the case for all good systems that would be in use, then the only thing you can do is try decrypting it with every single possible key (2^256 choices). This is called a brute-force attack, because it's very simple and requires computational "strength". When the correct key is found, you (or rather, the automated program you run) will know because the resulting plaintext will actually make sense instead of looking like random gibberish.

That said, brute-forcing any real system is essentially impossible in practice. To understand why requires a good working knowledge of the exponential function. Suppose that everyone used N many key bits for an algorithm, and that you were *just* on the verge of having enough computational power to be able to decrypt it. Now, if everyone switched over to using just 10 more bits, the problem difficulty suddenly increased by a factor of 2^10 = 1024 times! Because the users' normal tasks of encrypting and decrypting *with* the key are not exponential operations, whereas your task of brute-forcing the system is, you are at a severe disadvantage.

So suppose you wait a bit for Moore's law, if it's still around, to catch up, giving your computer dozens to hundreds of times more power than it had before. And suppose you gain access to a few billion new machines around the world, increasing your computational abilities by that factor. So what? You only have a hundred billion times more computational power, so all everyone else needs to do is tack on another 37 bits (2^37 ~= 128 billion) and you're right back where you started.

Let's use some actual numbers. Suppose you can perform one million decryption attempts per second. A 16-bit key could be broken in 66 milliseconds. A 64 bit key could be broken in 584,555 years. A 256-bit key would take more millennia than there are atoms in the observable universe. And symmetric ciphers in the absurd range of thousands of bits are *well* beyond astronomical comparisons.

This is why I'm not moved when you speak of being able to crack encryptions in a few hundred years (or indeed, at any time before the heat death of the universe), without significant advances in finding ways to break various encryption schemes that do not involve brute-force.
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

User avatar
taby
Posts: 154
Joined: Thu Nov 01, 2007 8:39 pm UTC
Location: Canada

Re: I have a question about the future of cryptography.

Postby taby » Fri Jan 18, 2008 9:20 pm UTC

With all this said, the overall security is not entirely based on the key length/algorithm alone. Encoding a certain plaintext message with a certain RSA key will always produce the same ciphertext message. That in itself is as insecure as the Caesar Cipher (the kind you used in grade 2 to write notes in class).

To add security one must salt (prepend, append, combination of both) the plaintext message with a series of random bits (preferrably a one time pad) before it's encrypted. This way encrypting the same plaintext message with the same RSA key results in a different ciphertext message every time. Less of a pattern leaves less leverage for the attacker.

Most modern operating systems that store their user's passwords using one-way hashes (ex: MD5, etc) usually salt the plaintext password as well. That way the attacker cannot use a simple rainbow attack, for if your password is "dog", the MD5 hash stored in the password database is not necessarily 0x06d80eb0c50b49a509b49f2424e8c805.

emo samurai
Posts: 53
Joined: Fri Jan 18, 2008 3:29 am UTC

Re: I have a question about the future of cryptography.

Postby emo samurai » Sat Jan 19, 2008 5:49 am UTC

To Workaphobia: So how much processing power does it take to encrypt in those 37 extra bits? I know it isn't 237 times as much; is it something trivial depending on the size of the current cypher? Like, it's just a linear progression?

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

Re: I have a question about the future of cryptography.

Postby Workaphobia » Sat Jan 19, 2008 8:38 am UTC

In principle, yeah, it's trivial no matter what size you use. The algorithm for encrypting and decrypting using the key scale well with its size, or else the system would be unusable. I see no reason why DES and similar iterated ciphers wouldn't simply scale linearly. Algorithms like RSA scale a little worse than others, so moving from 1024 to 2048 bits does more than just double the cost, but it's certainly still polynomial and doable.
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Sat Jan 19, 2008 6:09 pm UTC

Workaphobia wrote:
btilly wrote:Now nobody knows how close we'll get to this theoretical limit. We think that there are a few more years left. But if you're setting your article 15 years out, it would make sense to say that Moore's Law continued until, say, 2020. Give your basic computers specs that are about 20 times today's top of the line desktops.

To be pedantic, 2 ^ ((2020-2008)/1.5) ~= 256 times more powerful.

D'oh. Yup.
Workaphobia wrote:
btilly wrote:However you can then get more impressive with ubiquitous computing. The idea here is that there is an upper limit on what one CPU can do, but nothing stops you from having lots and lots of CPUs in parallel. (In fact computers are already moving in this direction.) The problem is, though, that lots of CPUs in parallel, each putting out a minimum amount of heat, takes a lot of energy and produces a lot of heat. You can deal with this in a data center, but in a handheld device, it isn't such a big win.

Yes, but the number of processors wouldn't increase exponentially as Moore's Law has, would it?

Actually it could. The history of technology shows that Moore's Law is actually ubiquitous. When there is a product with a clear criterion of "better", there tends to be exponential improvement in that criterion for long periods of time. Usually decades. This has held whether we are talking about the amount of dirt a backhoe can scoop, or how far a steam engine can sail, or the density of transistors on a chip. (See The Innovator's Dilemma for a reference and a discussion of the consequences of this.)

What is exceptional about Moore's Law is the rate of exponential improvement, not the fact of it.

However that said, CPUs are already moving in the direction of having multiple cores on a single CPU rather than trying to make those CPUs go faster. And the number of cores on a CPU seems to be expanding exponentially with time at a similar rate to Moore's Law. Of course there are physical limits which probably limit this long-term.

But then we get into the fact that the cost of a fixed chip has been decreasing exponentially over time. For instance they still make x386 chips but now they are very cheap. Even if we run out of ability to improve density exponentially, there is a lot of potential for continued declines of cost indefinitely, and there is every reason to believe that if the cost decreases exponentially, then the number of chips people can buy will increase exponentially.
Workaphobia wrote:
emo samurai wrote:Actually, that makes it perfect for the sake of his distributed codebreaker. If computers don't become a lot more powerful, but they become smaller and more plentiful, then the codes can't become that much more complicated without clogging up communications, but his distributed computer becomes 15 times as powerful as a desktop-dominated market would be. I mean, the individual computers couldn't handle very powerful cyphers, but since he has so many computers to use, he can hack any 2048 bit cypher with ease.


No no no no no no no no.

Ok, let's assume that you have a cryptographic message you want to decode (break, since you don't have the key; you are an adversary). Let it be a symmetric 256-bit cipher, for instance. If you don't know any algorithm that breaks the system, as is the case for all good systems that would be in use, then the only thing you can do is try decrypting it with every single possible key (2^256 choices). This is called a brute-force attack, because it's very simple and requires computational "strength". When the correct key is found, you (or rather, the automated program you run) will know because the resulting plaintext will actually make sense instead of looking like random gibberish.

Nobody is talking about brute force. We're talking about breaking public key cryptography. Which is theoretically much simpler - after all the attacker can get the public key.

In this case emo samurai is perfectly correct. If 2056 bit public key cryptography is today regarded as safe for decades to come, and Moore's Law tops out, then it would likely be still in use in 50 years - but might be susceptible to attack from a motivated attacker with a very large attacker.
taby wrote:With all this said, the overall security is not entirely based on the key length/algorithm alone. Encoding a certain plaintext message with a certain RSA key will always produce the same ciphertext message. That in itself is as insecure as the Caesar Cipher (the kind you used in grade 2 to write notes in class).

To add security one must salt (prepend, append, combination of both) the plaintext message with a series of random bits (preferrably a one time pad) before it's encrypted. This way encrypting the same plaintext message with the same RSA key results in a different ciphertext message every time. Less of a pattern leaves less leverage for the attacker.

This is only true if you are sending one of a fairly small number of signals. In fact the way that RSA is used in practice is in a Diffie-Hellman key exchange. Which means that everything is immediately encrypted with 2 keys - so that a given site can only possibly repeat communication with a given customer. But you are never going to communicate the same plaintext twice because what is communicated is a symmetric key to use for the rest of the communication. All further communication uses that symmetric key. That symmetric key is generated for that one conversation, and therefore you never will have 2 conversations using the same encryption. So you're safe, even if every conversation has the same plaintext.
taby wrote:Most modern operating systems that store their user's passwords using one-way hashes (ex: MD5, etc) usually salt the plaintext password as well. That way the attacker cannot use a simple rainbow attack, for if your password is "dog", the MD5 hash stored in the password database is not necessarily 0x06d80eb0c50b49a509b49f2424e8c805.

This is necessary because people consistently use a fairly small set of passwords and so without salting you could just prepare a database of likely plaintexts.

That said, I repeat again that for how RSA is used in practice this point is moot. Because the set of equally likely conversations in the key exchange are very large, and the encryption algorithm changes for each conversation.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

emo samurai
Posts: 53
Joined: Fri Jan 18, 2008 3:29 am UTC

Re: I have a question about the future of cryptography.

Postby emo samurai » Sat Jan 19, 2008 8:59 pm UTC

Which one is more commonly used, assymetric or symmetric? Keep in mind he'll also be trying to break government cyphers. Which one would a conspiracy use, and how big would the key be?

And does anyone know of any good Ubuntu Linux software for encrypting or decrypting stuff, including zip and 7z archives?

User avatar
taby
Posts: 154
Joined: Thu Nov 01, 2007 8:39 pm UTC
Location: Canada

Re: I have a question about the future of cryptography.

Postby taby » Sat Jan 19, 2008 11:20 pm UTC

btilly wrote:That said, I repeat again that for how RSA is used in practice this point is moot. Because the set of equally likely conversations in the key exchange are very large, and the encryption algorithm changes for each conversation.


Imagine that I have generated a random string, which when using your public key, encrypts to the same ciphertext packet that I intercepted from you. I now know how to decode everything you send without fail. If you salt every packet, do I still have this same advantage?

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: I have a question about the future of cryptography.

Postby Ended » Sun Jan 20, 2008 1:48 am UTC

taby wrote:Imagine that I have generated a random string, which when using your public key, encrypts to the same ciphertext packet that I intercepted from you. I now know how to decode everything you send without fail. If you salt every packet, do I still have this same advantage?

Yes, if you have the session key, you should be able to read all the traffic exactly as the recipient does. Salting in this context (I would call it padding) just serves to make each ciphertext look different, even if it's encrypting the same message with the same key. As I understand it, you would just mix some random bits in with your message, in a publicly-known way (e.g. prepend and append 256 random bits to the plaintext or something). Then the recipient just discards this portion of the plaintext.

emo samurai wrote:Which one is more commonly used, assymetric or symmetric? Keep in mind he'll also be trying to break government cyphers. Which one would a conspiracy use, and how big would the key be?

I would say 4096 bits for a public key. It's borderline believable that an attacker in 50 years with a vast global distributed network could break this (considering that this recommends using 2048 bits keys only up to 2030).

Usually, this would be the length of your public key, which you would use to establish a secret key, by asymmetric cipher key-exchange. This secret key would then be used as a symmetric cipher session key. This secret key would be much shorter - say 512 bits in 50 years - because it is generally a lot harder to break symmetric ciphers (ideally, brute-force should be the only attack possible). Alternatively, you could use asymmetric encryption exclusively, but this is much much slower.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Sun Jan 20, 2008 2:32 am UTC

taby wrote:
btilly wrote:That said, I repeat again that for how RSA is used in practice this point is moot. Because the set of equally likely conversations in the key exchange are very large, and the encryption algorithm changes for each conversation.

Imagine that I have generated a random string, which when using your public key, encrypts to the same ciphertext packet that I intercepted from you. I now know how to decode everything you send without fail. If you salt every packet, do I still have this same advantage?

Your hypothesis is wrong. Your conclusion is wrong. Your question is silly. Where do I begin?

I'll start with the conclusion. With Diffie-Hellman, even if you know the entire conversation for the exchange, you still don't know the shared secret that has been agreed on for the rest of the conversation. The only problem with doing the conversation in public is the possibility of a man-in-the-middle attack. The point of RSA is digital signing of the conversation, proving to both ends that there is no man-in-the-middle attack going on.

Now let's move on to the hypothesis. You ask me to imagine that you have a random string which encrypts to the right thing. Well how did you come up with that random string? Did you guess it? With the number of possible strings that could have been sent, guessing the right answer is essentially impossible, and brute forcing it is likewise infeasible.

Now let's move on to your question. You're asking in essence whether adding random data to every communication makes the cryptographic problem harder. Obviously it does. However the critical question in this case is, Do you trust your cryptography? If you don't, then you can trivially move to a stronger crypotography without having to waste bandwidth. If you do trust it, then adding salt to everything you communicate is a waste of energy.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: I have a question about the future of cryptography.

Postby Ended » Sun Jan 20, 2008 2:50 am UTC

I think taby was referring to a direct RSA key exchange, rather than Diffie-Hellman? I.e., I directly send you a secret key encrypted with your public key. In this case, if an attacker somehow finds a random string which encrypts to the same, they do indeed have the session key. Admittedly, this is somewhat unlikely.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Sun Jan 20, 2008 6:21 am UTC

Ended wrote:I think taby was referring to a direct RSA key exchange, rather than Diffie-Hellman? I.e., I directly send you a secret key encrypted with your public key. In this case, if an attacker somehow finds a random string which encrypts to the same, they do indeed have the session key. Admittedly, this is somewhat unlikely.

Logically that shouldn't be since taby was responding to me talking about Diffie-Hellman. That said, it is quite possible that he didn't really understand what I was talking about.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

Re: I have a question about the future of cryptography.

Postby Workaphobia » Sun Jan 20, 2008 10:41 am UTC

btilly wrote:Nobody is talking about brute force. We're talking about breaking public key cryptography. Which is theoretically much simpler - after all the attacker can get the public key.

Huh? You mean private key? Well yeah, same applies for symmetric cryptography. It's very easy to break a code if you *have* the key already. But in any situation we actually care to discuss when talking about computational security, you either need to brute-force or use some unknown algorithm that breaks the system. If you can't suggest the latter, we're left with the former.
btilly wrote:In this case emo samurai is perfectly correct. If 2056 bit public key cryptography is today regarded as safe for decades to come, and Moore's Law tops out, then it would likely be still in use in 50 years - but might be susceptible to attack from a motivated attacker with a very large attacker.

But how? If it's secure today, and there are not any significant technological improvements, or at least not enough to motivate people to switch over, then why wouldn't it be secure tomorrow? And conversely (actually, contrapositively), if it were insecure tomorrow, wouldn't people switch over? I don't understand your argument.

emo samurai wrote:Which one is more commonly used, assymetric or symmetric? Keep in mind he'll also be trying to break government cyphers. Which one would a conspiracy use, and how big would the key be?

Asymmetric and symmetric cryptography are used for entirely different purposes. Symmetric is used when transmitting data between two endpoints that already have a shared secret to be used as a key. Asymmetric adds a powerful cryptographic primitive to the mix, in that it allows the parties to have secrets that the others don't know, while still communicating securely amongst each other. Asymmetric is slower, so often it is only used long enough to agree on a shared secret, at which point everything switches over to symmetric for the remained of the session.

In general, you may have a system that relies totally on symmetric cryptography when you are communicating in a small, closed community where everything is set up by some central administrator (think Kerberos). Asymmetric is used all the time when the opposite is true, i.e., on the Internet. I don't think that implies that asymmetric wouldn't also be used in a conspiracy scenario though.

taby wrote:Imagine that I have generated a random string, which when using your public key, encrypts to the same ciphertext packet that I intercepted from you. I now know how to decode everything you send without fail. If you salt every packet, do I still have this same advantage?

Huh? If you have a known plaintext/cipertext pair, how does that allow you to decrypt all ciphertexts? Or did you mean that the one you guessed was the session key used henceforth?
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

EvanED
Posts: 4330
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: I have a question about the future of cryptography.

Postby EvanED » Sun Jan 20, 2008 4:41 pm UTC

Workaphobia wrote:Yes, but the number of processors wouldn't increase exponentially as Moore's Law has, would it?

Where else do you think those transistors are going?

Now it may be slower than what Moore's Law says, but it will almost certainly be exponential. (Either that, or Moore's Law will stop.) To a fair extent, architects just don't know how else to spend the transistors that would actually help as much.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Sun Jan 20, 2008 5:40 pm UTC

Workaphobia wrote:
btilly wrote:Nobody is talking about brute force. We're talking about breaking public key cryptography. Which is theoretically much simpler - after all the attacker can get the public key.

Huh? You mean private key? Well yeah, same applies for symmetric cryptography. It's very easy to break a code if you *have* the key already. But in any situation we actually care to discuss when talking about computational security, you either need to brute-force or use some unknown algorithm that breaks the system. If you can't suggest the latter, we're left with the former.

I said public key, and I meant public key. As for how to get it, it is public, I'm willing to tell it to anyone. The trick is that figuring out the private key from the public key is difficult enough that I don't think that anyone can do it.
Workaphobia wrote:
btilly wrote:In this case emo samurai is perfectly correct. If 2056 bit public key cryptography is today regarded as safe for decades to come, and Moore's Law tops out, then it would likely be still in use in 50 years - but might be susceptible to attack from a motivated attacker with a very large attacker.

But how? If it's secure today, and there are not any significant technological improvements, or at least not enough to motivate people to switch over, then why wouldn't it be secure tomorrow? And conversely (actually, contrapositively), if it were insecure tomorrow, wouldn't people switch over? I don't understand your argument.

As I said, public key cryptography is one where I'm willing to give anyone the information needed to break it, safe in the knowledge that figuring out how to break it takes more computational power than anyone can throw at it. What that means, though, is that an attacker with more computational power than I expect can be a problem for me.
Workaphobia wrote:In general, you may have a system that relies totally on symmetric cryptography when you are communicating in a small, closed community where everything is set up by some central administrator (think Kerberos). Asymmetric is used all the time when the opposite is true, i.e., on the Internet. I don't think that implies that asymmetric wouldn't also be used in a conspiracy scenario though.

Asymmetric would be useful for a conspiracy scenario. For example you need to know that certain messages really come from certain people. Digital signatures are a good way to do that.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

Re: I have a question about the future of cryptography.

Postby Workaphobia » Sun Jan 20, 2008 9:11 pm UTC

btilly wrote:
Workaphobia wrote:
btilly wrote:Nobody is talking about brute force. We're talking about breaking public key cryptography. Which is theoretically much simpler - after all the attacker can get the public key.

Huh? You mean private key? Well yeah, same applies for symmetric cryptography. It's very easy to break a code if you *have* the key already. But in any situation we actually care to discuss when talking about computational security, you either need to brute-force or use some unknown algorithm that breaks the system. If you can't suggest the latter, we're left with the former.

I said public key, and I meant public key. As for how to get it, it is public, I'm willing to tell it to anyone. The trick is that figuring out the private key from the public key is difficult enough that I don't think that anyone can do it.

I brought up brute-force originally as an example of an approach that would work but whose average required time is of exponential complexity. Regardless of whether or not you call deriving an RSA private key from a public key a brute-force attack, it still takes exponential time, and is therefore not "much simpler" in my opinion.

btilly wrote:
Workaphobia wrote:
btilly wrote:In this case emo samurai is perfectly correct. If 2056 bit public key cryptography is today regarded as safe for decades to come, and Moore's Law tops out, then it would likely be still in use in 50 years - but might be susceptible to attack from a motivated attacker with a very large attacker.

But how? If it's secure today, and there are not any significant technological improvements, or at least not enough to motivate people to switch over, then why wouldn't it be secure tomorrow? And conversely (actually, contrapositively), if it were insecure tomorrow, wouldn't people switch over? I don't understand your argument.

As I said, public key cryptography is one where I'm willing to give anyone the information needed to break it, safe in the knowledge that figuring out how to break it takes more computational power than anyone can throw at it. What that means, though, is that an attacker with more computational power than I expect can be a problem for me.

You keep bringing up the fact that in asymmetric cryptography one of the keys is available to the attacker, but that doesn't mean anything special. What you said applies no more to public key crypto than it does to secret key (symmetric) crypto.

A system where an attacker has the necessary information to decrypt the messages in principle, if he has arbitrarily high computational resources or time, but cannot do so in practice because the problem is intractable, has what is called Computational Security. Systems whose only known attacks are intractable provide computational security, and this clumps DES and RSA in the same category.

Yes, an attacker with more power than you expect is a problem, but the two things to remember are: 1) this isn't a fault or weakness of public-key crypto, in comparison with most other systems used; and 2) if the problem indeed remains intractable, then you have nothing to worry about, because by definition there cannot be a real attacker who has enough power to threaten you.

btilly wrote:
Workaphobia wrote:In general, you may have a system that relies totally on symmetric cryptography when you are communicating in a small, closed community where everything is set up by some central administrator (think Kerberos). Asymmetric is used all the time when the opposite is true, i.e., on the Internet. I don't think that implies that asymmetric wouldn't also be used in a conspiracy scenario though.

Asymmetric would be useful for a conspiracy scenario. For example you need to know that certain messages really come from certain people. Digital signatures are a good way to do that.

Yeah, I'm just wary of jumping to conclusions about what the situation might require. For instance, there's no reason symmetric can't provide good authentication, if you have separate pairwise keys for everyone in the group. But on the other hand, a reader familiar with crypto is much more likely to immediately associate public-key with authentication than he would secret-key.
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Sun Jan 20, 2008 9:54 pm UTC

Workaphobia wrote:
btilly wrote:I said public key, and I meant public key. As for how to get it, it is public, I'm willing to tell it to anyone. The trick is that figuring out the private key from the public key is difficult enough that I don't think that anyone can do it.

I brought up brute-force originally as an example of an approach that would work but whose average required time is of exponential complexity. Regardless of whether or not you call deriving an RSA private key from a public key a brute-force attack, it still takes exponential time, and is therefore not "much simpler" in my opinion.

Not true. There are subexponential algorithms for factoring and finding discrete logarithms. (The two most common problems that you need to solve for asymmetric cryptography.) This makes them much simpler to break that symmetric cryptography.

The increased simplicity is why key sizes for public key cryptography need to be much larger than the ones used in symmetric cryptographic algorithms.
Workaphobia wrote:
btilly wrote:As I said, public key cryptography is one where I'm willing to give anyone the information needed to break it, safe in the knowledge that figuring out how to break it takes more computational power than anyone can throw at it. What that means, though, is that an attacker with more computational power than I expect can be a problem for me.

You keep bringing up the fact that in asymmetric cryptography one of the keys is available to the attacker, but that doesn't mean anything special. What you said applies no more to public key crypto than it does to secret key (symmetric) crypto.

I say it because there is a real difference. In symmetric cryptography there is never a reason for the people who are communicating to give the attacker enough information to break the cryptography. They advertise nothing about the algorithm or the key. They are free to switch keys as often as they want, and have no reason to tell that to the attacker. Sure, the secrecy is unneeded, but since you can add that obscurity, why not?

In asymmetric cryptography there are lots of valid reasons why people tell potential attackers the exact algorithm and public key. Which makes it clearer what problem you need to solve. Furthermore, as I noted, we have better algorithms than straight brute force for breaking asymmetric cryptography.
Workaphobia wrote:A system where an attacker has the necessary information to decrypt the messages in principle, if he has arbitrarily high computational resources or time, but cannot do so in practice because the problem is intractable, has what is called Computational Security. Systems whose only known attacks are intractable provide computational security, and this clumps DES and RSA in the same category.

Yes, this is a similarity between DES and RSA. Even if the attacker has all of that information, they can't easily break the cryptograpy. The difference remains, though, that in the case of DES the attacker has to do more work to potentially break the cryptography.
Workaphobia wrote:Yes, an attacker with more power than you expect is a problem, but the two things to remember are: 1) this isn't a fault or weakness of public-key crypto, in comparison with most other systems used; and 2) if the problem indeed remains intractable, then you have nothing to worry about, because by definition there cannot be a real attacker who has enough power to threaten you.

Yes, I understand both points.
Workaphobia wrote:
btilly wrote:Asymmetric would be useful for a conspiracy scenario. For example you need to know that certain messages really come from certain people. Digital signatures are a good way to do that.

Yeah, I'm just wary of jumping to conclusions about what the situation might require. For instance, there's no reason symmetric can't provide good authentication, if you have separate pairwise keys for everyone in the group. But on the other hand, a reader familiar with crypto is much more likely to immediately associate public-key with authentication than he would secret-key.

Agreed.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

EvanED
Posts: 4330
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: I have a question about the future of cryptography.

Postby EvanED » Mon Jan 21, 2008 6:08 am UTC

Workaphobia wrote:You keep bringing up the fact that in asymmetric cryptography one of the keys is available to the attacker, but that doesn't mean anything special. What you said applies no more to public key crypto than it does to secret key (symmetric) crypto.

That's not true.

In public key crypto, an attacker trying to read a message knows (1) [at least part of] the encryption method, (2) the public key, and (3) the message.

In secret key crypto, an attacker necessarily knows (3) the message.

It is always possible to brute force a public key system. It is not always possible to brute force a secret key system. (Witness: one time pads, though from a practical sense you still have to be careful about message length.)

If you have outside information, breaking secret key crypto looks more like breaking public key crypto, but it's still not completely the same. For instance, the attacker may know what the encryption method is. But not necessarily. What about stuff the CIA uses? Are they using a public algorithm, or something the NSA cooked up (or at least modified)? You can't do a brute force search of the key space if you don't even know how to decrypt.

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

Re: I have a question about the future of cryptography.

Postby Workaphobia » Mon Jan 21, 2008 9:51 am UTC

btilly wrote:
Workaphobia wrote:
btilly wrote:I said public key, and I meant public key. As for how to get it, it is public, I'm willing to tell it to anyone. The trick is that figuring out the private key from the public key is difficult enough that I don't think that anyone can do it.

I brought up brute-force originally as an example of an approach that would work but whose average required time is of exponential complexity. Regardless of whether or not you call deriving an RSA private key from a public key a brute-force attack, it still takes exponential time, and is therefore not "much simpler" in my opinion.

Not true. There are subexponential algorithms for factoring and finding discrete logarithms. (The two most common problems that you need to solve for asymmetric cryptography.) This makes them much simpler to break that symmetric cryptography.

The increased simplicity is why key sizes for public key cryptography need to be much larger than the ones used in symmetric cryptographic algorithms.

I wikipedia'd those problems expecting to find something I could cite saying they're both NP-complete problems, but found nothing of the sort. That surprises me. Ah well, point taken. At least they're still super-polynomial.


btilly wrote:
Workaphobia wrote:
btilly wrote:As I said, public key cryptography is one where I'm willing to give anyone the information needed to break it, safe in the knowledge that figuring out how to break it takes more computational power than anyone can throw at it. What that means, though, is that an attacker with more computational power than I expect can be a problem for me.

You keep bringing up the fact that in asymmetric cryptography one of the keys is available to the attacker, but that doesn't mean anything special. What you said applies no more to public key crypto than it does to secret key (symmetric) crypto.

I say it because there is a real difference. In symmetric cryptography there is never a reason for the people who are communicating to give the attacker enough information to break the cryptography. They advertise nothing about the algorithm or the key. They are free to switch keys as often as they want, and have no reason to tell that to the attacker. Sure, the secrecy is unneeded, but since you can add that obscurity, why not?

In asymmetric cryptography there are lots of valid reasons why people tell potential attackers the exact algorithm and public key. Which makes it clearer what problem you need to solve. Furthermore, as I noted, we have better algorithms than straight brute force for breaking asymmetric cryptography.

Obscurity aside, in symmetric crypto the parties *do* give enough information to break the encryption, unless the message they send is so short so as to be below the unicity distance. If we want to add obscurity, we can throw in some sort of key cycling scheme. And while, typically, open internet protocols don't try to mask the type of encryption they're using, I see no reason why in principle you can't use asymmetric in an obfuscated way. As for telling people the exact algorithm and public key, that's not inherent in asymmetric crypto, that's just how we normally use it. It's what we do when we want to broadcast our identities to the world and communicate securely with anyone who'll listen. But if we're talking about a closed conspiracy, the participants can simply exchange public keys and arrange to authenticate in a way that does not make the nature of their communication so conspicuous.

Guess we're in agreement about everything else. Thanks for the info on the asymmetric complexity. ;)

EvanED wrote:That's not true.

In public key crypto, an attacker trying to read a message knows (1) [at least part of] the encryption method, (2) the public key, and (3) the message.

In secret key crypto, an attacker necessarily knows (3) the message.

It is always possible to brute force a public key system. It is not always possible to brute force a secret key system. (Witness: one time pads, though from a practical sense you still have to be careful about message length.)

If you have outside information, breaking secret key crypto looks more like breaking public key crypto, but it's still not completely the same. For instance, the attacker may know what the encryption method is. But not necessarily. What about stuff the CIA uses? Are they using a public algorithm, or something the NSA cooked up (or at least modified)? You can't do a brute force search of the key space if you don't even know how to decrypt.

All of that is a matter of obscurity, not of fundamental differences in complexity as btilly brought up. But as I said, you can make RSA just as obscure if you take away all its padding and message redundancy. I think under certain cases you could even go below the unicity distance. Well, that is, if the public key isn't known.

Ug, the problem here is that we're not being clear on exactly what's known and what's unknown for the attacker. It doesn't make sense to compare the obscurity of symmetric and asymmetric if you're going to assume the attacker knows the public key anyway.
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

User avatar
Indon
Posts: 4433
Joined: Thu Oct 18, 2007 5:21 pm UTC
Location: Alabama :(
Contact:

Re: I have a question about the future of cryptography.

Postby Indon » Wed Jan 23, 2008 6:58 pm UTC

One big deal-breaker I should note that applies to any length of the RSA encryption method is the development of a stable, large quantum computer. The quantum computer could allow for certain super-polynomial calculations pretty readily, to include the factoralization required to break the RSA method wide open.

On the other hand, physical technology that applies quantum principles may prove to be a strong defense to some attacks (generally on things like military networks), regardless of software used.
So, I like talking. So if you want to talk about something with me, feel free to send me a PM.

My blog, now rarely updated.

Image

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: I have a question about the future of cryptography.

Postby Robin S » Wed Jan 23, 2008 7:09 pm UTC

emo samurai wrote:This book takes place 50 years in the future and assumes no major advances in quantum computing.
However, I would like to point out that quantum encryption has already been demonstrated over a reasonable distance.
This is a placeholder until I think of something more creative to put here.

User avatar
davean
Site Ninja
Posts: 2498
Joined: Sat Apr 08, 2006 7:50 am UTC
Contact:

Re: I have a question about the future of cryptography.

Postby davean » Wed Jan 23, 2008 7:37 pm UTC

Robin S wrote:
emo samurai wrote:This book takes place 50 years in the future and assumes no major advances in quantum computing.
However, I would like to point out that quantum encryption has already been demonstrated over a reasonable distance.


Cooled very well IIRC (I'll find a citation if required). Making it operate warm would be a "major advance" I do believe.

This puts it out of the range of consumers, never mind it needs optical switching if you don't need a direct line. Direct lines are untenable for most installs.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: I have a question about the future of cryptography.

Postby Robin S » Wed Jan 23, 2008 8:27 pm UTC

Was cooling necessary for all of the examples mentioned in the "implementations" section of the Wikipedia article?
This is a placeholder until I think of something more creative to put here.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Wed Jan 23, 2008 9:31 pm UTC

Robin S wrote:
emo samurai wrote:This book takes place 50 years in the future and assumes no major advances in quantum computing.
However, I would like to point out that quantum encryption has already been demonstrated over a reasonable distance.

Quantum encryption and quantum computing have almost nothing to do with each other.

I'm sure that in 50 years there will be lots of dedicated links using quantum encryption. Whether we'll be breaking cryptography with quantum computing still remains to be seen.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
Indon
Posts: 4433
Joined: Thu Oct 18, 2007 5:21 pm UTC
Location: Alabama :(
Contact:

Re: I have a question about the future of cryptography.

Postby Indon » Wed Jan 23, 2008 9:35 pm UTC

Oops, didn't see the thing about no significant quantum computing advancements. Still, as noted, quantum encryption is a pretty viable technology right now, though it's better for intranet arrangements, such as you might find in the military or a company.

Robin S wrote:Was cooling necessary for all of the examples mentioned in the "implementations" section of the Wikipedia article?


There were a number of companies which offer commercial quantum encryption systems listed in the article. Fifty years of simply the technology becoming a bit more affordable means that no corporate net of appreciable size could be readily 'hacked' without drastic physical measures (such as having a signal intercept point inserted into the network before it was initially turned on).

Of course, it's not like science fiction books are generally accurate about that sort of thing anyway; the concept of just any 'hacker' being able to get into an organization's website and getting information which if the management has any sense, should be on a physically seperate network, is silly.
So, I like talking. So if you want to talk about something with me, feel free to send me a PM.

My blog, now rarely updated.

Image

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: I have a question about the future of cryptography.

Postby Robin S » Wed Jan 23, 2008 9:38 pm UTC

btilly wrote:Quantum encryption and quantum computing have almost nothing to do with each other.
No, but if quantum encryption becomes widespread in the next 50 years it will make the basis of the intended plot redundant.
This is a placeholder until I think of something more creative to put here.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: I have a question about the future of cryptography.

Postby btilly » Wed Jan 23, 2008 10:17 pm UTC

Robin S wrote:
btilly wrote:Quantum encryption and quantum computing have almost nothing to do with each other.
No, but if quantum encryption becomes widespread in the next 50 years it will make the basis of the intended plot redundant.

Doubtful.

Quantum encryption is a way to establish point to point communications that can't be tapped. The problem is that as soon as you try to change the point to point nature of it, you lose all of your guarantees unless you trust whoever is doing routing in the middle. And setting up quantum encryption links takes visible infrastructure.

There are many use cases where these limitations are not a problem. For instance it is great for a connection between two offices within an organization. However if you have a situation where you don't know where someone is going to connect from (think of a consumer ordering from a website, or a spy connecting to the home office), these limitations are a show-stopper.

Therefore no matter how widespread quantum encryption becomes, there is a large role for public key cryptography for the foreseeable future.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
snails
Posts: 124
Joined: Sun Mar 23, 2008 11:58 am UTC

Re: I have a question about the future of cryptography.

Postby snails » Sun Mar 30, 2008 3:29 pm UTC

btilly wrote:I'm sure that in 50 years there will be lots of dedicated links using quantum encryption. Whether we'll be breaking cryptography with quantum computing still remains to be seen.


There are alternate encryption schemes that are quite possibly quantum-proof:

http://scottaaronson.com/democritus/lec8.html wrote:Oded Regev has recently proposed public-key cryptosystems that are provably secure against quantum eavesdroppers, assuming SVP is hard for quantum computers. Note that his cryptosystems themselves are purely classical.

User avatar
Arancaytar
Posts: 1642
Joined: Thu Mar 15, 2007 12:54 am UTC
Location: 52.44°N, 13.55°E
Contact:

Re: I have a question about the future of cryptography.

Postby Arancaytar » Mon Mar 31, 2008 10:12 am UTC

I've read up on Quantum Encryption but I'm still not sure: Is it actually a cipher rather than a technology for a secure optical fibre link? Because the latter sounds like information would still be vulnerable while it isn't inside the link - for example, through a worm program on the receiving computer - and would still need to be encrypted conventionally.
"You cannot dual-wield the sharks. One is enough." -Our DM.
Image

User avatar
Xanthir
My HERO!!!
Posts: 5291
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: I have a question about the future of cryptography.

Postby Xanthir » Mon Mar 31, 2008 2:45 pm UTC

The quantum encryption scheme I'm familiar with is simply a way of securely exchanging a standard symmetric key. Since symmetric cyphers are much more secure than asymmetrics for a given key length, it's useful to be able to use them. But, since they're symmetric, the same key is used for encrypting and decrypting, and thus it's difficult to use in general situations due to key-transport problems. This quantum-encryption scheme exploits superposition to establish a shared symmetric key while making it unlikely (exponentially with the length of the key) that an eavesdropper would be able to successfully steal the key.

Once you establish the key, you don't need anything fancy - you can do traditional communication using unsecured wires, radio waves, whatever.

Information is *always* vulnerable inside the computers, however. There's really no way to guard against that except good computer hygiene.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Yakk
Poster with most posts but no title.
Posts: 11078
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: I have a question about the future of cryptography.

Postby Yakk » Tue Apr 01, 2008 9:43 pm UTC

The point of crypto algorithms is keeping the ratio of "decryption with permission" and "decryption without permission" high, with the ability to ramp either up.

A "good" crypto algorithm should require effort exponential in n to decrypt without permission, and time polynomial in n to decrypt with permission.

Let's also assume moore's law: namely, that computer power doubles every 2 years.

Next, let's assume a networking law, that you can double the number of computers working on a problem every 2 years.

Finally, let's assume that every 1 unit increase in key complexity increases the cost to decrypt without permission by a factor of 2, and increases the cost to decrypt with permission by 1 unit.

The time it takes to decrypt with permission should be relatively constant. So the effort to decrypt without permission grows with 2^(2^(y/2)).

The number of computers grows with 2^(y/2), and the power of each computer grows with 2^(y/2), producing an attack strength that grows with 2^y.

The time it takes to hack is then:
2^(2^(y/2)) / 2^y = 2^[2^(y/2)-y]
this diverges extremely rapidly.

Practically, programmers slack. The strength of encryption, instead of scaling with computer power, scales with the effort it takes to crack it. This allows cheaper decryption with permission, and more fine-grained encryption rules.

...

So why isn't encryption unbreakable? It sort of is at this point. Attacks on encryption systems either rely on attacking short key lengths, flaws discovered in the encryption system, or infrastructure attacks. Encryption seems to be getting more reliable, not less...
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Arancaytar
Posts: 1642
Joined: Thu Mar 15, 2007 12:54 am UTC
Location: 52.44°N, 13.55°E
Contact:

Re: I have a question about the future of cryptography.

Postby Arancaytar » Wed Apr 02, 2008 11:58 am UTC

Xanthir wrote:The quantum encryption scheme I'm familiar with is simply a way of securely exchanging a standard symmetric key. Since symmetric cyphers are much more secure than asymmetrics for a given key length, it's useful to be able to use them. But, since they're symmetric, the same key is used for encrypting and decrypting, and thus it's difficult to use in general situations due to key-transport problems. This quantum-encryption scheme exploits superposition to establish a shared symmetric key while making it unlikely (exponentially with the length of the key) that an eavesdropper would be able to successfully steal the key.

Once you establish the key, you don't need anything fancy - you can do traditional communication using unsecured wires, radio waves, whatever.

Information is *always* vulnerable inside the computers, however. There's really no way to guard against that except good computer hygiene.


Ah, I think now I understand. I kept thinking that the entire communication would be passed through the quantum superposition process, not just the secret key during key exchange.

(Though perhaps this key exchange could be strengthened in combination with a One-Time Pad instead of a normal key, which would then require constant communication of the key stream over the "quantum" line? I have no idea how much security would be gained from that.)
"You cannot dual-wield the sharks. One is enough." -Our DM.
Image

User avatar
Yakk
Poster with most posts but no title.
Posts: 11078
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: I have a question about the future of cryptography.

Postby Yakk » Wed Apr 02, 2008 1:50 pm UTC

A perfect, random one-time pad is perfect security over the communication link. Even if you guess the pad, there is no way to distinguish it from a "wrong" key -- the communicated data could say "bob is your uncle" or "we eat dogs at noon" or "we eat dogs at dusk" with no way to tell which.

I suppose you do have timing of communication and length to try to figure out what is being said. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: I have a question about the future of cryptography.

Postby BlackSails » Wed Apr 02, 2008 11:59 pm UTC

If I ran a global conspiracy, I would just use a code, rather than a cipher. Codes are unbreakable.

For example, I write:

12 321 53 3118 31 34 549 31.

My co-conspirator then looks up the information in whatever book was agreed on beforehand (or newspaper, etc), does whatever was agreed on beforehand to do with the words in the book, and he has the message.

Breaking this requires:
1) Knowing how the numbers themselves are encrypted. (Ie, perhaps you are supposed to double all of them. Or subtract 1. Or both. Or multiply by the day of the week and divide by the month)
2) Knowing what codebook to use.
3) Knowing how to decode the text from the code book.

To be really mean, you then encrypt the message.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: I have a question about the future of cryptography.

Postby quintopia » Thu Apr 03, 2008 12:45 am UTC

No, a big conspiracy wouldn't use a book code. Way too time-consuming.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11078
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: I have a question about the future of cryptography.

Postby Yakk » Thu Apr 03, 2008 2:41 am UTC

BlackSails wrote:If I ran a global conspiracy, I would just use a code, rather than a cipher. Codes are unbreakable.


Codes are not unbreakable. Codes used sparingly are unbreakable, but so are most cyphers.

Codes used regularly are more breakable. The problem isn't that they find the code book (which is possible), but rather that they figure out that you are talking about an ambush in the flurry of messages after you ambush them...
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xanthir
My HERO!!!
Posts: 5291
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: I have a question about the future of cryptography.

Postby Xanthir » Thu Apr 03, 2008 3:33 am UTC

Arancaytar wrote:
Xanthir wrote:The quantum encryption scheme I'm familiar with is simply a way of securely exchanging a standard symmetric key. Since symmetric cyphers are much more secure than asymmetrics for a given key length, it's useful to be able to use them. But, since they're symmetric, the same key is used for encrypting and decrypting, and thus it's difficult to use in general situations due to key-transport problems. This quantum-encryption scheme exploits superposition to establish a shared symmetric key while making it unlikely (exponentially with the length of the key) that an eavesdropper would be able to successfully steal the key.

Once you establish the key, you don't need anything fancy - you can do traditional communication using unsecured wires, radio waves, whatever.

Information is *always* vulnerable inside the computers, however. There's really no way to guard against that except good computer hygiene.


Ah, I think now I understand. I kept thinking that the entire communication would be passed through the quantum superposition process, not just the secret key during key exchange.

(Though perhaps this key exchange could be strengthened in combination with a One-Time Pad instead of a normal key, which would then require constant communication of the key stream over the "quantum" line? I have no idea how much security would be gained from that.)


An OTP is perfect cryptography. Unless they discover a flaw in your pad generator, it is literally uncrackable. You have to brute-force it.

The problem is in securely transporting an OTP to your communication partner. This is identical to the problems in symmetric key exchange. Basically an OTP is just symmetric encryption with a key length equal to your message. The extremely high key length allows you to use really dumb encryption methods (ceaser cipher) without losing power, because there is no pattern to exploit.

You *could* use what I outlined above to establish an OTP which is astronomically unlikely to be intercepted. However, that's a waste of resources. All you need to do is establish a key of n bits (where n is determined by the current strength of a hypothetical attacker using best practices) to be safe.

To put it another way, if you have an OTP, you don't need quantum encryption. Just use the OTP to encrypt your message! Or use the OTP to encrypt your key, and then communicate it normally. Or just establish that on day X, you'll use the yth page on the OTP for your key. Essentially quantum encryption creates silver out of thin air, but an OTP that's already been shared with your partner is solid gold (on the other hand, an OTP that only you have is like an IOU from a stranger). When you don't have anything better, sure, make some silver. But if you've got gold in your hand, why bother?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 7 guests