Hot answers tagged

33

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.


20

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 ...


13

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 ...


11

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 ...


11

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) ...


8

The bottom line answer is this: every possible 5-character ASCII string is equiprobable. Therefore, if you try all possible keys (which is practical, as you noticed), then you will certainly see the correct plaintext string at some point. But you will have no way to know that the correct string is the correct string. To make this painfully clear, consider ...


7

Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key? No. (Please keep reading…) A single mathematical formula won’t cut it. That’s where cryptographic algorithms come in. There are more than a hand full of cryptographically secure pseudo-...


7

/dev/urandom is only computationally secure, so you won't get information-theoretical security for your OTP if you draw it from /dev/urandom. If you're happy with computational security, you might as well use a stream cipher instead of a OTP. Stream ciphers are much easier to use securely than OTPs. On Linux /dev/random aims for information-theoretical ...


6

No, that doesn't work. OTP is secure because knowledge of the plaintext doesn't give you any useful information about the key. This is because the bits of the key (e.g. $P_0$) are never used to encrypt anything else. If you would somehow reuse the key then leakage of the plaintext would cause leakage of $P_0$. Leakage of $P_0$ directly leaks $P_1$. I.e. ...


6

There is no difference. In fact, any quasigroup operation will do. Specifically, the only property we really need is that, for every ciphertext symbol $C$ and every plaintext symbol $P$, there exists one (and only one) key symbol $K$ such that encrypting $P$ with $K$ yields $C$. This implies that, as long as the actual key symbols are chosen uniformly at ...


6

A simplified* Carter-Wegman MAC could be defined as: $$ t=\sum_{i=1}^n {k_1^i m_i} + k_2 \pmod p$$ $p$ is a sufficently large prime (e.g. 256 bits). You must choose a new truly random $k_2$ uniformly from $0\leq k_2 <p$. It acts as a one-time-pad that prevents an attacker who sees the tag $t$ from learning anything about $k_1$. The polynomial $\sum {...


5

We know, by the encryption rule for one-time pads, where $k$ is the re-used pad: $p_1 \oplus k = c_1$ and $p_2 \oplus k = c_2$. For $\oplus$ (xor) the following arithmetic is valid: $a \oplus a = 0$ for all $a$ (everything is its own inverse), which is clear from truth tables, e.g., and $a \oplus (b \oplus c) = (a \oplus b) \oplus c$, i.e. the operation ...


5

By two-time pad I assume you mean using a one time pad key to encrypt two messages. Lets say $K$ is the key and $m_1, m_2$ are your messages. Then from the ciphertexts $c_1 = m_1 \oplus K$ and $c_2 = m_2 \oplus K$ an adversary could trivially learn information such as $x = c_1 \oplus c_2 = m_1 \oplus m_2$. Whether or not this information is "exploitable" may ...


4

In order to achieve very high security for privacy, would it be cryptographically secure to use one time pad ciphers in emails? OTP offers perfect secrecy, so if it's feasible to use it, it is secure. However, OTP alone offers no authentication and leaves the message malleable. If Alice sends a message Y to Bob, standing for 'yes', Mallory can guess this ...


4

First things first: what you are describing there is not a one-time-pad! As I explained in another answer of mine: Per definition, OTP requires the “key“ to be… a truly random one-time pad value, generated and exchanged in a secure way, at least as long as the message, and only to be used once. What you describe (eg: using a key ...


4

There is no security difference. Of course, purely random characters with entropy rate $\log M$ where $M$ is the size of the alphabet should be independently generated and used for the OTP, whatever the size $M$ of the alphabet.


4

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....


4

You stated: "I can at the very least narrow down the list of possibilities." Here's an example of why OTP is perfect secrecy, and why your statement, although true, doesn't matter. I have a sentence which I wrote, and after encrypting it with an OTP, it looks like this: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Good luck decrypting that! ...


4

There is no security difference; there are a handful of practical ones: With xor, you can have the same code to do encryption and decryption With xor, you don't have to pick a 'word size'; a larger CPU can handle 4 or 8 bytes at a time, while a microcontroller can handle 1 byte at a time, without changing the ciphertext With xor, you don't have to worry ...


4

In a finite field $\mathbb{F}_q$, both maskings are perfectly secure, provided that $x \neq 0$ for the multiplicative masking. This is easy to see. The finite field $\mathbb{F}_q$ defines two groups: the additive group $\mathbb{F}_p^+$ (i.e., $\mathbb{F}_q$ equipped with addition) and the multiplicative group $\mathbb{F}_q^*$ (i.e., $\mathbb{F}_q \setminus ...


4

First, do not ever use RC4. Second, it depends on how you use that stream... If you use AES-CTR as a stream cipher (see more here), you will specify a key $K$ (and a nonce $IV$). The CTR mode of AES will generate a stream of bits, whose length matches the messages. All that is required is to XOR it with the message. In order to decipher. One will ...


4

Here's my understanding of the encryption process you're talking about: You take a random number $r$, and compute $t = r \bmod n$ You concatinate the two numbers $r$ and $t$, and express the concatination as a bitstring $u$ You then xor that bitstring $u$ with a secret bitstring $s$ You do the same for two different random numbers $r$ and $r'$, using the ...


4

You're never going to release this, right? If so, it doesn't matter. Use a pseudorandom stream from /dev/urandom and "pretend" that it's truly random for the sake of learning about the concepts involved.


4

As long as the keys $K_i$ are only used once, this is semantically secure. To see it, observe that if $K_i$ is a uniformly random value in $\{0,1\}^{|M|}$ then so is $C_i = M \oplus K_i$.


4

Your first sentence is entirely wrong. A OTP is a theoretical construct that requires a fully random key (at least) the size of the plaintext. Limiting the amount of random bits to 256 will by definition not be an OTP - at least not for constructions that accept a plaintext larger than 256 bits. The same idea is that if you use a key called $i$ which is ...


3

There's quite a few things wrong with this. For starters, a block cipher does not imply authentication. Common block cipher modes such as CTR, CBC, and (god forbid) ECB provide nothing but pure encryption. If you want authentication, look into the GCM block cipher. AES-GCM is possibly the better way to go here. You state that it is built on the idea that ...


3

Would it be useful for companies who need to keep their data safe? Not exactly. The One-Time-Pad is extremely inconvenient. If your client has to encrypt a piece of plaintext that's 4GB large, then they will not only have to generate 4GB of random data, they also will have to share that pad with the receivers of that message, making it a total of 8GB of ...


3

$c_2 \: = \: m\oplus k_2 \: = \: m\oplus k_1 \oplus k_1 \oplus k_2 \: = \: c_1 \oplus k_1 \oplus k_2$ $k_1 \oplus k_1 \: = \: 00000...00000$ Since fixing either argument turns xor into a bijection, the distribution of $\: k_1 \oplus k_2$ is uniform on non-zero strings. $\;\;\;$ Thus, knowledge of $c_1$ is enough to sample from $c_2$'s distribution, so ...


3

Sorry, I would only give partial points for a CCA attack on this scheme. The answer by @SEJPM is of course correct (and very informational so it's good it was posted). However, it is not the "best" answer, since this scheme can be easily broken under a chosen-plaintext attack. I will not write the full answer out (so that I can leave some work to be done for ...


3

This scheme follows the KEM/DEM approach of contructing secure asymmetric encryption schemes. However for a KEM/DEM PKCS (public key cryptosystem) to be secure it is required that both the key encapsulation mechanism (KEM) and the data encapsulation mechanism (DEM) are CPA or CCA secure for CPA or CCA of the whole scheme. Indeed the DEM looks CPA secure as ...



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