Having never heard of one time pads, I just looked them up after coming across the term in a recent thread here. I get the concept of how they work, but I’m confused about one thing- the fact that in order to be perfectly unbreakable, the key must be “truly random”. Why is this? Lets say theres 2 people, each making a one time pad to send a 5 letter message. Person 1 generates his key with a process that creates truly random numbers, and lets say this produces “FPRSM”. Person 2 uses the random generator in his computer, (which all the sites out there say is a no-no, only pseudo-random, and thus breakable). But this happened to result in “FPRSM” also. So, according to the experts, 1’s message is perfectly secure, because he used truly random numbers, but person 2’s message is slightly less than perfectly secure?
I guess what I’m asking is, since the same key generated by a psuedo random source could also happen to coincidentally be generated by a truly random source, and psuedo-random keys are known to be crackable, then how can truly random keys be considered absolutely infallible?
If you generate a pseudo-random number and I know how, I can crack your code. It becomes a Cryptoquote of sorts. If, on the other hand, you generate a truly-random number, I have no idea what you’re sending, because there’s no discernible pattern and no way to reproduce it.
Your example is too short, and for most short messages the differences between pseudo-random and random are not sufficient to allow decryption.
However, if your random pad was ABFBDBCBFB and your pseudo-random pad was ABFBDBCBFB, but you knew that every second element in the pseudo-random pad was always going to be a B, then you can attack every second character of the crypt, and thus the message. A pseudo-random OTP can be attacked if the message is long enough, or if the generation principles are known.
This is how the Allies attacked Enigma during the war. The german machine basically had a pseudo-random OTP built in. The Poles knew the wheels, the interconnects and the per key changes, so the only thing that was needed to decrypt a message were the starting positions. These were attacked by guessing or knowing elements in the header or message, and all possible combinations of starting positions were then set up on the bombes (mechanical decrypters), and they attacked the messages until the right combination was found. Colossus did this electronically, and faster, too.
The germans never realised that the pseudo-random OTP was so weak (though Donitz had suspicions, and Naval Enigmas were strengthened with an extra wheel and codebook - cracking this (Shark) was a major problem and took 10 months).
So the key is you have to know how? That makes more sense to me, but nowhere I’ve looked stipulates that, they all just say non-random numbers = crackable code, period.
But what about the whole “can’t use the same key twice” thing? What if the random numbers happened to reproduce an already used key? Wouldn’t that make it a fallible system because of this possibliity alone?
Eventually, yes - and in less time than a truly random OTP. The point is that any pseudo-random number sequence is statistically different from a random number sequence at the large scale. And thus the crypt is also statistically different, and can be (theoretically) attacked statistically. Whether you can actually do it is a matter of time and resources.
It would not be a random OTP generator if it generated an already used key within the useful lifetime of the messages - thats the point of a random number generator. It is a theoretical possibility, but the odds are so stacked against it that it is not an issue. Reusing an OTP pad gives the opportunity to match similar items in the crypt, but this only becomes obvious after several repeats. Once this has happened, however, all messages on the OTP can be decrypted.
Much of what is written about cryptography relates to the deep mathematical truths - pseudo-random OTPs are fallible, reusing OTPs will open the crypt to attack. Practically, it always depends on the value of the message and the resources of the attacker as to whether or not it is decrypted. Weak pseudo-random OTPs will take less time, and maybe trivial time. Truly random OTPs will be safe until the message is no longer of value.
The possibility alone wouldn’t make the code fallible if it’s pure chance that a new code is identical to a previously used one. The system becomes fallible as soon as you start to re-use previous keys intentionally. Code-breakers are looking for repetitive patterns.
Take a simple substitution cipher where the same letter of plain text is always substituted by another, but always the same, letter (A becomes E, B becomes T and so on). Codes like this are deciphered by counting how frequently letters appear in the encoded text and comparing these frequencies with the common letter distribution in the language in which the cipher is written. Codes like that are rather simple to decode.
There are more elaborate codes, as for example the Videnère cipher, which use several substitution alphabets parallelly. A plain text A might be encoded to T one time, but another A from the plain text might become a G because another alphabte from the code table is used to encode it. This makes the code more difficult to crack, but there are still repetitive patterns - if the key word used in the cipher, which determines which alphabet to use for which character from the plain text, is shorter thajn the plain text itself, then there will be a pattern repeating itself throughout the cipher. These repetitions are what code-breakers are trying to detect.
It is clear that the longer your key word is, the safer the cipher is going to be. The one-time pad approach is the logical consequence of this: Make the key word just as long as the plain text (or longer); and there will be no repetitions. Of course this will leave you with the problem of transmitting the key word - in many cases, one-time pads are not worth the trouble, because if you can find a way to safely transmit the key, you can also use the same method to safely transmit the plain text message itself.
If a newly-generated code is identical to a previously used one, this does not result in a repetitive pattern if it’s the result of pure random.
That can be determined by statistical tests. That happened to the Soviet Union during World War II. Due to the pressures of war and incompetence, one-time pads were sometimes issued more than once. This was discovered by the U.S. Army’s Signal Intelligence Service and enabled them to break into many Soviet messages. See VENONA.
Yes. However those tests wouldn’t be useful at detecting the same key arising twice completely by random chance.
Weighted dice can be found out, because they’re no longer random - random streaks of sixes thrown on fair dice are still just random.
It is best not to think about individual random integers. Stick to thinking about infinite streams of digits (or other symbols). So you could get unlucky on your stream spits out 314159 as the first sequence. However anybody with brains in the code business uses really long keys (and one time pads have to be extremely long). So the chances of a randomly selected sequence of say 1000 bytes having a useful discernible pattern (like the first 1000 bytes of Pi) is so vanishingly small it’s ridiculous.
Well, they would be somewhat useful, it just wouldn’t lead to complete failure of the code.
It is obvious that a truly random process that produces the same key more than once is going to be just as easy to break on those messages as purposefully using that same key more than once. However, a truly random process is much less likely to actually repeat a key, and is similarly less likely to repeat several keys in a pattern, or to create patterns within the keys, as a non-random process might.
Another valuable property of OTPs is that there is no way for the codebreaker to tell when he’s won. In normal encryption methods, there’s only one possible plaintext from any possible ciphertext/algorithm pair. However, with an OTP there are an arbitrary number of possible plaintexts: Every plaintext the same size as the ciphertext is a possible decryption. Even knowing a part of the plaintext (for example, that it begins “Greetings, my name is Crandall Spondular”) doesn’t help you narrow down the possible decryptions of the parts you don’t know and can’t reliably guess.
It’s possible to regain this property without the massive impracticality of OTPs by using algorithms that provide ‘deniable encryption’.