66

For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can be expressed with 100 bits. That's not the reason why one-time-pads are considered secure. The reason is that even if you try all possible keys that you get ...


41

No. As long as each pad is completely random and independent, you can encrypt literally anything of the appropriate size (no larger than the pad) and retain information theoretic secure confidentiality. This attack is termed a known-plaintext attack, or KPA. The OTP encryption scheme is only vulnerable to this if you re-use padding material, which breaks the ...


37

Brute force on OTP will give you all sorts of messages which are meaningful and not meaningful. For example, you have a 4-character encrypted text: weaw. Now brute-forcing will give you all sorts of meaningful and not meaningful messages like: erwe hell road .... Now, which one was the real message? That would be difficult, rather impossible to guess.


25

The short answer: No As long as the key is not reused, OTP has perfect secrecy. Even at some point if the attacker knows the plaintext, he will only get a key that is used once. A problem may occur if the generation algorithm is predictable; that is, the attacker may use the weakness in the generation algorithm to produce previous and next bits.


24

To begin with, your definition of perfect secrecy is non-standard. The standard definition is given in an excellent answer to the question how is the OTP perfectly secure?. Essentially, perfect secrecy means that observing the ciphertext does not affect the relative likelihoods of various plaintexts under the unknown key. So the fact that different ...


23

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is ...


23

You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext. This is not true as you have observed. The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this: Definition 2.3 An encryption scheme $(\text{Gen, Enc, Dec})$ with message space $\mathcal M$...


22

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able and willing to pull off active attacks of various types (in which the attacker can modify or forge messages to achieve some goal). One-time pads are extremely ...


22

What you are missing is the fact that every resulting message is equally possible. There is no way to verify that any of the resulting messages was indeed the message that was sent. If you have $P_1P_2P_3P_4 \oplus K_1K_2K_3K_4 = C_1C_2C_3C_4$ where each $P$, $K$ and $C$ are one bit, then $C_1C_2C_3C_4$ can have any value possible. Now assume your brute ...


22

A one-time pad requires a true random sequence that is as long as the material you want to encrypt. If you have a pseudo-random sequence, then you don't have a one-time pad: you have a stream cipher. If you have a stream of data that is only “nearly random”, then you don't have a one-time pad, you have a broken stream cipher. Concretely, if the nearly-...


21

There are two main reasons. First, when we encrypt data with a symmetric algorithm, we generally want each unit to encrypt or decrypt to a unit of the same size (ignoring padding and MACs). In your case, when we're using English letters, we'd want to also get English letters out, and not a set of random numbers. Similarly, when we're encrypting a byte, we ...


21

Does that violate the perfect secrecy in any way? Yes, obviously. Restricting the message space doesn't hurt in any way (the attacker can't get any additional information about the message, even if he knows quite a lot about it already); restricting the key does. OTP uses a group operation to combine the message and the key; one thing that it needs to ...


19

Not using modulus leaks information. For the English language, it's not so obvious. For an image, on the other hand... Left half uses addition and modulus, right half uses addition and division by two (i.e. half brightness).


18

Actually, the problem with OTP isn't the storage of the pad (although secure erasure of the parts of the pad you used is trickier than it looks), and it isn't the pad generation (although, again, that's trickier than it looks), but the secure transport. After all, it's not enough for you (Alice) to have the secure pad, you also have to give a copy to the ...


17

Very short answer: No Quite Short answer: No, because a scheme can only be a One-Time-Pad if the entire pad is perfectly random and secret. Concise answer: It sounds like you're trying to build a stream cipher. The security of it really comes down to how much of the scheme you think can be kept secret. If I listen in to your wifi and hear you requesting a ...


17

There is no such thing as a random key. There are only randomly generated keys. What I mean by that is that randomness is not a property of the key (or message, or number, or whatever), but of the process that generates it. For example, it is not meaningful to ask whether the number 5 is random, or whether it is somehow more or less random than the number ...


16

First you have to understand why it is possible to do exhaustive key searches on other systems. Suppose you have a plaintext of length n, ciphertext of the same length n, and a key of length k (all in bits). Then by trying all possible keys we obtain at most 2k candidate plain texts. If the system has some kind of validation or message integrity built into ...


16

Your interesting questions deserve to be answered more thoroughly, but here goes: According to a highly classified document written in 1947 and finally declassified in 2013, the Germans started using a one-time pad system for diplomatic traffic in 1925. This system (GEE) used a one-time pad of digits to encrypt codes by modulo addition. To be clear, these ...


16

Why is OTP perfectly secure? Let's assume you would like to encrypt a plaintext $m$ using OTP. In order to do that, you would need to pick $m$ from a possible message space of $M$ with a given length. $M$ hereby represents all possible messages of this length. Further, you choose a key $k$ from the given keyspace $K$. Note that $K$ and $M$ have the same ...


15

While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth. What they are talking about is a Carter-Wegman authentication method that uses a stream of random bits as a part of the process (just like a one time pad uses a stream of random bits to encrypt). Normally, when we implement CW, we use some almost universal (au) ...


15

accepted wisdom that OTP encrypted messages are secure & unbreakable OTP encrypted messages are secure & unbreakable assuming the pad is secret, uniformly random, and not reused... and the message does not otherwise leak! The last point is where the "Bit Flip" attack comes to play. Imagine the message is conventionally a digit send in ASCII, and ...


15

An OTP is completely broken if you use a key that can be predicted. As such, $\pi$ would be a terrible choice. The key needs to be unpredictable, nonrepeating, and completely random. $\pi$ satisfies the nonrepeating aspect, and (looks like it) satisfies the randomness attribute, but is predictable since I can simply search online for 1 million digits of $\pi$...


13

I'll try a practical example: I trade stocks. Instructions to my broker use a simple Caesar shift cipher, but the shift varies by values in a one-time encryption pad. Common 8-char instructions include: "buy more" "sell all" and "short it". You intercept an instruction to my broker: "AAAAAAAA" What is my instruction? Buy, sell, or short?


13

The answer is incorrect, but it's a bit more subtle than it seems. To make this clear, note that encrypting $x$ by computing $c=\operatorname{AES}_{0}(k) \oplus x$ would be perfectly secure (here the key is fixed to 0, but any fixed key value would give the same effect). This is due to the fact that AES is a permutation and so when $k$ is uniformly ...


13

There are different objectives when it comes to security. One objective is to make messages confidential. An OTP provides this in an information-theoretical secure way. Of course, the premise of OTP is that the key stream is fully random, which is hard to prove conclusively. Other security goals could be maintaining message integrity: making sure that the ...


12

The general scheme is called Three-pass protocol and works for all commutative ciphers. It is secure for some of them, but xor (and modular addition) are insecure choices. Your scheme: A->B: $c_1 = m \oplus a$ B->A: $c_2 = c_1 \oplus b$ A->B: $c_3 = c_2 \oplus a$ B computes $m = c_3 \oplus b$ an attacker sees all of $c_1$, $c_2$ and $c_3$. So they can ...


12

Synchronous stream cipher, or just stream cipher. In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with ...


12

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$? No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational theoretic. Here's why: Poly1305 is based on a polynomial universal hash. This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^...


11

No, you can reuse a message as often as you want with the OTP. (But never reuse the key!) What happens if you reuse a key? The attacker can xor the two encrypted messages (ciphertexts) and gets the xor of the two plaintexts. The xor of two messages is highly insecure and can be easily turned into two plaintexts with some know patterns. What happens if you ...


11

What you propose is equivalent to trying to do cryptanalysis without any cipher text or other material. Equivalently, you could just take the small plaintext seed that you know, and nothing else, and run it through a probabilistic language model to predict the most likely message. (e.g., a Markov chain text generator). Obviously, it doesn't get you very far....


Only top voted, non community-wiki answers of a minimum length are eligible