Hot answers tagged

56

There is a great graphical representation (which I found on cryptosmith, but they keep changing their url structures, so I've added the graphics in here) of the possible problems that arise from reusing a one-time pad. Let's say you have the image and you encrypt it by using the binary one-time-pad (xor-ing on black and white) . You get the following ...


46

Well, the classical answer to "what is the correct thing to do after you have the XOR of the two original messages" is crib-dragging. That is, you take a guess of a common phrase that may appear in one of the plaintexts (the classical example against ASCII english is the 5 letter " the "), and exclusive-or that against the XOR of the two original messages ...


25

There are two methods, named statistical analysis or Frequency analysis and pattern matching. Note that in statistical analysis Eve should compute frequencies for $aLetter \oplus aLetter$ using some tool like this. A real historical example using frequency analysis is the VENONA project. EDIT: Having statistical analysis of $aLetter \oplus aLetter$ like ...


22

Let's assume that the plaintexts consist only of spaces and ASCII letters. Given the hint, that seems like a reasonable assumption to start with, even if it might turn out to be only mostly correct. Now, take one of the ciphertexts and XOR it with each of the others. Of course, the XOR operation cancels out the keystream, so you end up with the plaintext ...


22

Collisions of RSA keys should never happen for realistic key sizes and good random number generators. Assume a 1024 bit RSA key; the primes from which it has been derived are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about $2^{500}$ or $10^{150}$ ...


19

In general, knowledge of $m_1 \oplus m_2$ is not enough to uniquely determine $m_1$ and $m_2$, even if both are known to be, say, English text. For a simple example, $$\text{"one one"} \oplus \text{"two two"} = \text{"one two"} \oplus \text{"two one"}.$$ However, in practice it may be possible to obtain fairly good guesses for $m_1$ and $m_2$; the typical ...


16

Here, since the key is used more than one time, an attack called “crib dragging” can be used to attack the cipher-text. The blog post Many Time Pad Attack - Crib Drag could give you a greater understanding on the implementation part: Many Time Pad Attack – Crib Drag The one time pad (OTP) is a type of stream cipher that is a perfectly secure method ...


15

Yes, the attacker would have a realistic chance of recovering plaintext, and preventing him from knowing the IV values does not reduce this risk. The problem is that CTR mode encryption is effectively: $C = P \oplus F(Key, IV)$ where $P$ is the plaintext, $C$ is the ciphertext, and $F$ is a complex function of its two inputs. The problem with this is if ...


14

Yes, encrypting two different random "plain texts" with the same "pad" is indistinguishable from using two different random one time pads for encrypting the same plain text. You get perfect secrecy in the latter case, so you will get corresponding secrecy in the former case as well. However, usually there is a functional difference between the key and the ...


10

A recent (2006) paper that describes a method is "A natural language approach to automated cryptanalysis of two-time pads". The abstract: While keystream reuse in stream ciphers and one-time pads has been a well known problem for several decades, the risk to real systems has been underappreciated. Previous techniques have relied on being able to ...


10

Well, reusing a key isn't a problem; after all, RSA keys are generally used many times. However, if you fix the padding, there does exist one other potential problem; message malleability. To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$. To send these, Alice actually sends: $E(X_1), E(X_2)$ $E(Y_1), E(Y_2)$ Now, Eve can't ...


9

Yes, this is a fine approach. This sort of technique is known as "key separation". Since your master key is a cryptographically secure key, you do not need to use a large iteration count. Also, you could use any PRF, in place of PBKDF2. (The iteration count is normally used if you are applying PBKDF2 to a passphrase, instead of a cryptographically secure ...


8

If you encrypt the messages $m_1$ and $m_2$ with the pad $p$ as $$\begin{aligned} c_1 &= m_1 \oplus p, \\ c_2 &= m_2 \oplus p, \end{aligned}$$ where $\oplus$ denotes the binary operation of a finite group (e.g. addition on integers modulo $n$, or XOR on bitstrings, etc.) and $p$ is a random element of the group, then, indeed, an attacker who ...


8

You're missing a piece in your understanding of modern encryption. AES is a symmetrical block encryption cipher. It describes how to use a key (which can be 128, 192 or 256 bits) long to encrypt and decrypt a single block of fixed size (128 bits) of data. That's it. In order to have a complete encryption/decryption system, you need to couple it with ...


6

CBC mode encrypts as follows: $$ C_0 = E_K(IV\oplus P_0);\\ C_i = E_K(C_{i-1}\oplus P_i), $$ where $P_i$ are plaintext blocks and $C_i$ are ciphertext blocks. Traditionally, IV must be random and is published alongside the ciphertext to enable decryption. If it is also published in your case, then this reveals the key and is trivially insecure. If the $IV=K$...


5

You would retain perfect security in the situation you described. Consider your question in reverse. Use the ciphertext as a OTP and use the n-time-pad as the ciphertext. Since your ciphertexts are random their concatenated result is also random and would qualify as an OTP. At this point is doesn't matter what the OTP was, the conditions for perfect ...


5

Yes, there are secure alternatives to support random-access based encryption. I did not come up with a way to break the proposed combination. Still, instead of inventing a new mode, I would recommend to take consider existing modes for this kind of operation, such as XTS mode. The existing modes are more studied, and (in some ways) more efficient. XTS mode (...


4

Each zero in $m_1\oplus m_2$ indicates a matching character. These are known as coincidences. The number of coincidences can possibly indicate what language they are communicating in since different languages have a different character frequency distribution. (Random data should have coincidences 1/26 of the time if using only lowercase letters, whereas ...


4

This is considered in §6 of Bogdanov et al., who go on to devise an alternative 2-round AES-based Even-Mansour cipher—$\text{AES}^2$. The problem is, essentially, that 1-round Even-Mansour is only secure up to $2^{n/2}$ blockcipher queries, for an $n$-bit block. Specifically, a collision between $\text{SEM}_K(P) \oplus P$ and $E(P) \oplus P$ immediately ...


4

No, it is not necessarily secure. Here is a simplified example of why not. Assume one block zero messages are encrypted without padding. The ciphertext is $I||E(I \oplus 0)$. The MAC value is thus $E(E(I) \oplus E(I)) = E(0)$. So regardless of the IV, the MAC is the same for all such messages. So if you encrypt several zero messages you can leak that fact ...


4

Apologies if this is too basic but all the explanations about AES focussed on the details of the protocol, not these more basic concepts. In fact you are asking about general secret key management :) 1) Is the point of this (and other encryption techniques) to reuse the same private key for multiple messages? If we're using one-time keys, ...


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


3

Some remarks: a 16 byte IV is required by CBC, but you may not require a 128 bit unique value for your protocol CBC relies on an IV that is indistinguishable from random to an attacker, fixing bits in the IV is not a good idea CBC requires a padding mechanism, unless you can use ciphertext stealing Now a few calculations reveal that if you rely on the ...


3

I think what you are looking for is a Password-Based Key Derivation Function (PBKDF). You can take a moderately strong password, like 12-14 random letters and numbers (no dictionary words though!), and throw it into the PBKDF function together with some other parameters, e.g. salt, number of iterations and the desired key length. After that you have a ...


3

The thing here is: When you just XOR the cyphertexts with each other, what you get is in fact the XOR result of both cleartexts. $f(a) \oplus f(b) = a \oplus b$ And after that point, all that's left is to use statistical analysis, as ir01 has mentioned. In fact, the early cell phones used to implement a somewhat similar encryption scheme. They had a ...


3

I just came across this question and was surprised that no one referenced the paper: A Natural Language Approach to Automated Cryptanalysis of Two-time Pads by Mason et al. at ACM CCS 2006. This shows how to solve this problem in an automated and intelligent way.


3

Let me get this straight; if you are sending a 256 bit message, and get a 256 bit reply, the obvious way using OTP would be the message to use up 256 bits of pad, and the reply to use up a separate 256 bits of pad, using a total of 512 bits. Instead, you propose to use a total of 512 bits to send the message (and a temporary pad), the reply will then be ...


3

The scheme you describe is perfectly secure, so long as you are only sending a message as long as the pre-shared key. So basically it's an inefficient way to do a One Time Pad. Let's see what happens when you try to send 768 bits of message when you only have 512 bits of pre-shared key: Let $A$ and $B$ be the two blocks of pre-shared key material (each ...


3

Such keys are called static keys. Keys that are newly generated each time are called ephemeral keys. Note that you need to trust the public keys of the key pairs to use them for authentication. Please note that there is an issue if you use static keys only for plain Diffie-Hellman: the generated secret will be static as well, as the whole scheme has now ...


3

No, it's not a problem. What you've found is known as the square computational diffie-hellman problem(SCDH) and it can be shown that this is equivalent to the computational diffie-hellman problem(CDH). For completeness: SCDH: Given $g$ (your $G$) and $g^x$ (your $Q$), find $g^{x^2}$ (your $d_A^2G$). It is shown here that this problem is as hard as the ...



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