"Few false ideas have more firmly gripped the minds of so many intelligent men than the one that, if they just tried, they could invent a cipher that no one could break."
October 11, 2010 9:03 PM Subscribe
An animated Flash demonstration of the Advanced Encryption Standard.
The stick figure guide, previously on MetaFilter, might help you understand this.
The stick figure guide, previously on MetaFilter, might help you understand this.
"Few false ideas have more firmly gripped the minds of so many intelligent men than the one that, if they just tried, they could invent a cipher that no one could break."
OTP
"In cryptography, the one-time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly."
posted by jet_manifesto at 9:52 PM on October 11, 2010
OTP
"In cryptography, the one-time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly."
posted by jet_manifesto at 9:52 PM on October 11, 2010
JM, the problem with the one-time pad is that the sender and receiver have to have identical copies. Which means there has to be a trustworthy courier to carry it from one to the other.
If the courier isn't trustworthy, or if one side or the other has been penetrated by spies, then the one-time pad is not secure at all.
This would fall under the category of "using it incorrectly", but in the real world spies and untrustworthy couriers happen.
Meanwhile, in the real world the biggest problem with the one-time pad is that it can't handle the traffic level that usually is required. It's really only good for sending occasional brief messages. And only if there's a trustworthy courier, and no spies, and...
posted by Chocolate Pickle at 10:28 PM on October 11, 2010 [1 favorite]
If the courier isn't trustworthy, or if one side or the other has been penetrated by spies, then the one-time pad is not secure at all.
This would fall under the category of "using it incorrectly", but in the real world spies and untrustworthy couriers happen.
Meanwhile, in the real world the biggest problem with the one-time pad is that it can't handle the traffic level that usually is required. It's really only good for sending occasional brief messages. And only if there's a trustworthy courier, and no spies, and...
posted by Chocolate Pickle at 10:28 PM on October 11, 2010 [1 favorite]
Indeed. Which is why we have an encryption industry.
There are many other issues with OTPs in addition to the ones you mentioned, as you are probably aware. Generating "truly" random numbers is a serious one.
Nevertheless, as I'm not a practicing spy myself (...or am I...?) I'm more interested in the abstract concept of OTPs and their theoretical significance. Some of the mathematical concepts illuminated by OTPs are deeply linked to philosophical inquiries into determinism, for example.
The fact that OTPs are truly "information-theoretically secure" suggests to me that they are 'perfect circles', that is, something that exists in theory but is nowhere to be found in reality. Reality is a bitch.
Then again, if quantum cryptography can allow perfectly trustworthy 'couriers' and unfailing detection of 'spies', then OTPs may very well be the way forward. In fact, I think that's what the big fuss made about QC in the crypto world is really all about.
posted by jet_manifesto at 11:32 PM on October 11, 2010
There are many other issues with OTPs in addition to the ones you mentioned, as you are probably aware. Generating "truly" random numbers is a serious one.
Nevertheless, as I'm not a practicing spy myself (...or am I...?
The fact that OTPs are truly "information-theoretically secure" suggests to me that they are 'perfect circles', that is, something that exists in theory but is nowhere to be found in reality. Reality is a bitch.
Then again, if quantum cryptography can allow perfectly trustworthy 'couriers' and unfailing detection of 'spies', then OTPs may very well be the way forward. In fact, I think that's what the big fuss made about QC in the crypto world is really all about.
posted by jet_manifesto at 11:32 PM on October 11, 2010
Unlike asymmetric crypto, OTPs require secure key exchange. They are at a disadvantage even compared to symmetric crypto though because one bit on encrypted information requires one bit of OTP. The key exchange quickly becomes so onerous that you might as well hand carry the information.
posted by atrazine at 12:39 AM on October 12, 2010
posted by atrazine at 12:39 AM on October 12, 2010
Anyway, back to this, no matter how I look at it it seems to be a 128 bit key. And at the rate that cost-of-computing is dropping, that may be vulnerable to a brute-force attack.
And unless I'm missing something, the only way to make the system more secure is to encrypt multiple times, using a different key each time. Is that the case?
posted by Chocolate Pickle at 1:03 AM on October 12, 2010
And unless I'm missing something, the only way to make the system more secure is to encrypt multiple times, using a different key each time. Is that the case?
posted by Chocolate Pickle at 1:03 AM on October 12, 2010
JM, it isn't hard to create random sequences which are sufficiently random for purposes of security. You take 26 tiles out of a Scrabbble game, dump them into a bag and shake it up. Reach in, draw one out, write down the letter, then put it back in the bag and shake it up again. That's good enough.
But if you have a secure courier to deliver the OTP, you may as well just use the secure courier to deliver the clear, since they'll be the same size. (joke)
The only place a OTP makes any sense is for a spy going into action. He carries his OTP with him, and he doesn't expect to send much back, so he doesn't need a very big one. Historically that was how they were used, and it worked well. But it isn't a useful solution for anything else I can think of.
posted by Chocolate Pickle at 1:19 AM on October 12, 2010
But if you have a secure courier to deliver the OTP, you may as well just use the secure courier to deliver the clear, since they'll be the same size. (joke)
The only place a OTP makes any sense is for a spy going into action. He carries his OTP with him, and he doesn't expect to send much back, so he doesn't need a very big one. Historically that was how they were used, and it worked well. But it isn't a useful solution for anything else I can think of.
posted by Chocolate Pickle at 1:19 AM on October 12, 2010
That's an interesting paradox (joke), isn't it? OTPs are only information-theoretically secure if a perfectly secure courier can exist, but if that courier is perfectly secure, the OTP is unnecessary.
posted by jet_manifesto at 2:47 AM on October 12, 2010
posted by jet_manifesto at 2:47 AM on October 12, 2010
Well, no; because as Chocolate Pickle has just pointed out, security is not time-invariant. Also, if all you have is a secure channel from B to A, you can transmit a one-time pad that will let you secure communications via an insecure channel from A to B.
posted by flabdablet at 4:55 AM on October 12, 2010
posted by flabdablet at 4:55 AM on October 12, 2010
It seems like One-Time-Pads also require some kind of meta-security in case the pad falls into the wrong hands and "the enemy" can then send a message back with whatever they want in it.
posted by wobh at 5:30 AM on October 12, 2010
posted by wobh at 5:30 AM on October 12, 2010
CP: you are underestimating the magnitude of 128 bits. While advances in mathematics may weaken a cipher or QM may allow us to short-circuit it entirely, it takes more energy IIRC to merely run a 128 bit counter through all its states (there being a certain amount of energy in a single bit) than is contained in the sun. And that doesn't even allow for attempting to decrypt with each key.
Schneier has a good description in the intro to Applied Crypto. The real threats are backdoors and undiscovered weaknesses in the ciphers, e.g. some smartarse mathematician discovering an efficient way to factorise huge numbers.
posted by polyglot at 5:32 AM on October 12, 2010 [2 favorites]
Schneier has a good description in the intro to Applied Crypto. The real threats are backdoors and undiscovered weaknesses in the ciphers, e.g. some smartarse mathematician discovering an efficient way to factorise huge numbers.
posted by polyglot at 5:32 AM on October 12, 2010 [2 favorites]
And multiple encryption, if done wrong, can be weaker than a single stage.
posted by polyglot at 5:33 AM on October 12, 2010
posted by polyglot at 5:33 AM on October 12, 2010
Isn't the WoW keyring an OTP? That's a useful solution, no?
posted by symbioid at 6:45 AM on October 12, 2010
posted by symbioid at 6:45 AM on October 12, 2010
The problem with this one-time pad sidebar is that we're comparing computationally secure and socially secure. RSA, AES, and the like might be crackable after the sufficient application of computing power, but they are also defeated by sufficient pressure to the sender or receiver. Just as a one-time pad could be stolen or coerced, a decryption key could be recovered by some of the same social means.
posted by mikeh at 6:48 AM on October 12, 2010
posted by mikeh at 6:48 AM on October 12, 2010
symboid, the WoW keyring is not an OTP. It is a third-factor for an authentication system. You have a username, which never changes, a password which rarely does, and the keyring's number, which changes every 60 seconds. The server knows your username, and has a (presumably) hashed version of your password, and it knows what keyfob you have.
The keyfob runs through a pseudorandom sequence every 60 seconds. At the heart of this sequence is an initialization vector to the pseudorandom number generator. Given this vector, and the current value of the keyfob, you can determine all future values on the keyfob. But only if you know the algorithm and the time (which both the keyfob and WoW do).
Therefore, it's simply an easy way to change your password every minute, and it is not an OTP (not least because nothing is encrypted with it, but also because it is not truly random, as it never repeats).
posted by Xoder at 6:56 AM on October 12, 2010
The keyfob runs through a pseudorandom sequence every 60 seconds. At the heart of this sequence is an initialization vector to the pseudorandom number generator. Given this vector, and the current value of the keyfob, you can determine all future values on the keyfob. But only if you know the algorithm and the time (which both the keyfob and WoW do).
Therefore, it's simply an easy way to change your password every minute, and it is not an OTP (not least because nothing is encrypted with it, but also because it is not truly random, as it never repeats).
posted by Xoder at 6:56 AM on October 12, 2010
but also because it is not truly random, as it never repeats
Well, eventually it will repeat its entire cycle. Psuedorandom sequences are deterministic and periodic.
posted by jedicus at 7:08 AM on October 12, 2010
Well, eventually it will repeat its entire cycle. Psuedorandom sequences are deterministic and periodic.
posted by jedicus at 7:08 AM on October 12, 2010
Correct, Jedicus, but the idea is long before it can repeat either the battery will die, or you will be issued a new one with a new hop set.
posted by Xoder at 8:40 AM on October 12, 2010
posted by Xoder at 8:40 AM on October 12, 2010
And at the rate that cost-of-computing is dropping, that may be vulnerable to a brute-force attack.
Yeah, no:
posted by Rhomboid at 4:49 PM on October 12, 2010
Yeah, no:
Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years.The power-based argument that polyglot refers to is also mentioned on the wikipedia page for brute force attacks which comes to the conclusion that the world's most perfect (non-reversible) computer operating at room temperature would require 30 GW for one year just to count up to 2128. But I find that's kind of a confused way of stating it. If you're brute forcing a key you have to check on average half of the keyspace, so if you compute the energy required to simply load 2127 keys each 128 bits, you get about 6.3 x 1019 J or about 2 TW constantly for a year. (And that's an absolute physical lower limit that considerably underestimates reality, unless reversible computing somehow takes off.)
posted by Rhomboid at 4:49 PM on October 12, 2010
(And not to mention that that's just loading each key into memory, let alone doing any decryption.)
posted by Rhomboid at 4:51 PM on October 12, 2010
posted by Rhomboid at 4:51 PM on October 12, 2010
« Older The mother of all airplane trips | The Multifunction In-Dorm Automation System Newer »
This thread has been archived and is closed to new comments
posted by mindsound at 9:24 PM on October 11, 2010 [2 favorites]