Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
76

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


28

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


28

"Hint: XOR the ciphertexts together, and consider what happens when a space is XORed with a character in [a-zA-Z]." 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 ...


26

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


26

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


26

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


14

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


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


14

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


13

Yes, but the answer is more or less embedded in the question here; you can only say that you encrypt too much data in case the secret key and / or plaintext becomes vulnerable. Most modes of operation define how much data can be encrypted. This could mean real limits to the amount of data (approx. $2^{36}$ bytes or 64 GiB for AES-GCM) or it may be ...


10

If you reuse a nonce, you lose confidentiality for the messages with that nonce. Messages with other nonces retain their confidentiality. However, the attacker can also attack the MAC part (Poly1305) and generate a third and more messages with the same nonce. See: Why is Poly1305 popular given its 'sudden death' properties? So unless you have a way ...


10

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


9

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


9

Based on comments it seems the question asks if this is as secure as OTP as opposed to finding a practical attack. It is clearly not as secure as OTP. It is not information thetorical secure. With sufficient messages totalling more than key size we can brute force the key, just iterate over possible keys until you find one which works with all messages. ...


8

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


8

One potential issue with GCM is that it can potentially make the problems you get from repeating nonces worse; instead of allowing you to forge, and revealing the plaintext for the packets with the repeated nonces, it can become a key recovery issue. Here's one way it can happen; suppose the AAD is the 128 bit key, and you repeat the nonce with three ...


7

Generate key-pair Generate random salt, hash password with proper password hash (scrypt or PBKDF2) to derive a master key. Use HKDF to derive one login key and one encryption key from master key Encrypt private key with encryption key from previous step Upload it to server, download only possible by proving possession of login key (either send over SSL, or ...


7

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.


7

A character is usually encoded as an ASCII. This means that it uses up one byte. That's a number from $0 - 255$. It can be represented as a hexadecimal $\text{0x00} - \text{0xFF}$. All your operations must be done character by character. From now on by "message", "key" and "cipher" i mean a single $0-255$ number. $$ message1 \oplus key = cipher1 \\ message2 \...


6

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


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


6

A OTP is by definition just that, one time. Reuse allows analysis. Taking the OTP and applying a fixed algorithm to it, even using different encryption each time to refresh it, simply gives two codes to crack; the encryption key for the OTP, and the algorithm applied to the message using the OTP. Repeatedly reusing the same key, same OTP, or resending the ...


6

You've constructed a (somewhat artificial) special case where what you call the "plaintexts" also meet the requisites that one-time pad keys are supposed to meet: Secret Chosen uniformly at random Never reused So we can analyze this by flipping the labels, so that we regard what you label the "key" and the "plaintexts" the other way around, and the ...


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


5

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


5

I think the realistic answer is that we don't know if it's dangerous. In cryptography, anything we don't know the security properties of needs to be treated by default as if it's insecure. To my knowledge, GCM (and similarly HMAC) haven't been extensively analyzed from the perspective of having the key included as the message, either in whole or in part. ...


5

As a concrete example of a recent discussion where a similar question was considered, the IRTF draft for AES-GCM-SIV was at one point revised because of possible attacks on protocols that (unjustifiably) assume that their AAD is confidential: The major change in this update is the use of nonce-specific POLYVAL keys. Previous versions of GCM-SIV did not do ...


5

Why else are ephemeral keys used? Ephemeral keys are not a specific form of keys, they are just short lived keys within a key establishment protocol. Usually they are not directly trusted as they are generated on the fly. ECIES may also use an ephemeral private key, to name a single other usage. In particular, if I don't care about Perfect Forward ...


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

Yes, the same keypairs can be used to derive shared secrets between multiple pairs of parties. If knowing the shared secret between Alice and Bob would help Eve find out the shared secret between Alice and Carol, Eve could just create her own random private key and calculate a "shared" secret between that key and Alice's public key to get the same advantage....


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