One-time pad

Why isn't One-time pad widely used? Can someone explain?

You need a secure channel where you can exchange the key that is as long as the message that you want to encrypt. But if you already have this secure channel, why not just send the message itself?

>>394 Ok. So, for asymmetric cryptography the process is centralized on the key exchange, right? But for symmetric encryption? For example, if I want to encrypt a hard drive using OTP and I put the key on a usb stick? Wouldn't this be a good use? Why is this not used?

>>396 The key has to be as big as the data you want to encrypt. For a 1 TB hard drive you would need a 1 TB key.

>>397 Actually, since re-encrypting a disk block with new data would need another chunk of the key (you can't reuse OTP keys or encryption becomes moot) for OTP disk encryption you'll need (disk_size + avg_write_bandwidth * time) of the key. But if you can forget (securely erase) the pieces of the key are that no longer used you'll only need to store disk_size of the key (but you'll need a way to generate more on-demand). The problem with OTP for disk encryption is that while your disk is perfectly encrypted now you have a problem of defending your OTP key. When the bad guys decide to raid you, you'll need to forget disk_size of the OTP key really fast. Much easier to do for 256bit key than for 1Tb key. But it could work for something like Tox for IRL friends, though. It's not like you need that much of a key to encrypt the contents even for low-bandwidth VOIP. For text-only chat 1Gb of OTP key exchanged IRL is like 10 years of perfect perfectly forward secret post-quantum encryption, if you can forget the used chunks. Metadata still has to be layered with some kind of PK encryption for onion routing, though.

>>399 >problem of defending your OTP key ok, how about everyday it generates a new key (one time password) and then compress it using a high compression ratio algorithm? I (OP) think OTP is very limited, yes, but I can't see why it's not used in some situations, where you really need security. Let's say, a war. As a example, If you create a communication device for soldiers communicate while in war, and it has a OTP key inside every single device.

>>406 >then compress it using a high compression ratio algorithm? Would be pointless. You can't compress random data.

>>393 I'll expand on the answer given by >>397 and why it is necessary. The reason you'd want to use OTP is because it provides perfect secrecy. Otherwise you'd have any old stream cipher of which there are plenty. Perfect secrecy means, roughly speaking, that knowledge of the ciphertext gives you absolutly no information about the plaintext. More precisely, for all plaintexts x and ciphertexts y, if it is the case that P[x|y]=P[x], then the cryptosystem provides perfect secrecy. In particular, this means that someone with infinite computing power wouldn't learn anything _at all_ from looking at the ciphertext. It is easy to prove that for this to hold, you'd need at least as many keys as plaintexts. Let K be the set of keys, P the set of plaintexts and C the set of ciphertexts. Now, suppose |K| < |P|, i.e., there are strictly less keys than ciphertexts (this is the case with all practical cryptosystems). Suppose our ciphertext is y. Now, we can simply compute D_k(y) (the decryption of y under the key k) for all keys in K. Note that this set (lets call it P*) is strictly less than P (actually, we would have |P*| <= |K|). But this would tell us that the (true) plaintext could not have come from P\P* (i.e., the difference of P and P*). But then this in turn implies that knowing y actually _do_ give us some information about what x could be, in particular, x could not have come from this difference, which is non-empty since |P*| <= |K| < |P|. Thus, if |K| < |P|, the cryptosystem cannot be perfectly secure.

>>421 I'll provide a more formal proof (because I'm procrastinating). p[x] denotes the probability of x and p[x|y] denotes the probability of x given knowledge of y. Claim: If |K| < |P| then the cryptosystem cannot be perfectly secure. Proof: We proceed by contradiction. Let (P, C, K, g, e, d) be a cryptosystem such that |K| < |P|, i.e., we have strictly less keys than possible plaintexts. Note that "possible plaintexts" implies that p[x] > 0 for all plaintexts x. Assume ftso. contradiction that this cryptosystem is perfectly secure. Let y in C be a ciphertext (which exists as |C| >= |P| holds for any cryptosystem) and compute d_k(y) for all k in K. Note that, as stated in my previous post, this gives us a set P* for which we have |P*| <= |K| < |P|. In particular, we now know that p[x' | y] = 0 for all x' in P \ P*. But this cryptosystem is perfectly secure, which means we have p[x | y] = p[x] > 0 for _all_ x in P -- in particular those in P \ P* -- which gives us a contradiction, thus this cryptosystem cannot be perfectly secure. QED.

>>420 Well, to be more precise, the amount of compression is small, I think. The probability that some key k cannot be compressed with c bits can be computed using the theorem in https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression. This works because keys must be uniformly distributed, otherwise the cryptosystem cannot be perfectly secure. Note that this is for keys of length exactly n, but can easily be transformed into an expression for keys up-to length n. For example, if you consider keys up to length 10 (i.e., K = {0,1} U {0,1}^2 U ... U {0,1}^10) then you cannot compress around half of you keys with more than 1 bit. In other words, any compression would be more or less meaningless.

>>406 OTP has been used in war. What they did is roll dice to generate random numbers until they had pages and pages, then assign each page to a day for the duration of the field mission.

>>431 I should specify that they did all this before the mission began, then on the mission, when they needed to decode a message they got that day, they used that day's page. The USSR fuarrrked this up by reusing pages. Apparently they didn't catch the name, "One Time."

>>406 >Let's say, a war. As a example, If you create a communication device for soldiers communicate while in war, and it has a OTP key inside every single device. Because the average soldier's communications don't require that level of security and you'd run into problems with device synchronizing (unless each individual soldier has their own OTP codebook of random numbers and every other soldier they might communicate with has a copy, which would quickly require large amounts of storage and run the risk of not being able to communicate with other teams). Overall, it's not worth it when compared to other encryption methods that aren't perfectly secure when implemented correctly but are more easily implemented at a large scale.

They are still used in the right contexts and spies have been caught with hard drives full of random data, presumably with an identical hard drive kept back at HQ. It's a very narrow channel of usage though.