1
$\begingroup$

Assume I have a block of data consisting of three segments A, B and C. With "segments" I mean a particular section of a bit stream, so if the whole binary data was simply 00 01 02 ... FF, A might be 00 ... 5C, B could be 5D ... 72 and C would then be 73 ... FF.

K1 and K2 are 128 bit AES keys that were securely exchanged such that Alice has K1 and Bob has K2.

  • Alice gets data segments ABC encrypted with K1.
  • Bob gets only data segment B encrypted with K2.

My question is: if Bob got to know Alice's full cipher text for ABC (that was encrypted with K1), what could he deduce from the information he already has? Are there any circumstances under which Bob could decrypt segments A and/or C as well?

This is question is very similar to Vulnerabilities if encrypting the same data with 2 different keys, but not quite; I'm not asking about what Eve can deduce, but Bob.

I'm fairly new to encryption, and it was my understanding that AES is mostly XOR operations. For strict XOR operations, I think if you know any two a, b or c where a ^ b = c, you can calculate the third variable using XOR on the other two, as I think this was how parity bits for RAID systems work.

I keep finding hints as to AES is not just XOR, like How is XOR used for encryption? which in turn links to Why do block ciphers need a non-linear component (like an S-box)?. But I'm not sure I'm understanding the implications of the answers given there.

I think what the answers to those questions say is that for AES, K1 and K2 are just used to continuously generate a pseudo random bit stream, and only that is then XOR'ed with the data. So all Bob could deduce was the pseudo random bit stream section that has been used for Alice's B, but the generator function is such that this doesn't give Bob a clue about K1 or the bits generated earlier for A or later for C.

Is this universally true? Or, as I have seen often mentioned, are there limitations as to how many bits B may have to keep a 128 bit K1, A and C reasonably secret from Bob?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

We assume that Bob knows B and Enc(K1, ABC) but doesn't know K1, A or C. Then the only information Bob can learn about ABC is the length of AC (not even the length of A and C individually). If Bob knows Enc(K1, M), Bob can't even tell whether B is a substring of M. This is assuming that Enc is any sensible symmetric cipher, including AES-CBC (with a random IV), AES-CTR (with a initial counter value that doesn't overlap any counter value used for another input with the same key), AES-GCM (with a non-repeated nonce), AES-CCM (with a non-repeated nonce), etc.

AES itself is a permutation on 128-bit blocks, not a way to encrypt a message. involves some xor operations internally, but this is not a xor between the message and something else. There is no simple arithmetic relation involving related inputs and related outputs, otherwise we'd consider it to be completely broken. Given AES_Enc(K, A) and AES_Enc(K, B) where A and B are 128-bit strings, the only thing you can deduce about A and B is whether they're equal or not (A = B if and only if AES_Enc(K, A) = AES_Enc(K, B)).

There are ways to encrypt a message that involve xoring the message with a keystream which is produced using AES as a building block: ciphertext = plaintext ⊕ keystream. AES-CTR is a relatively simple one, where the keystream is built by encrypting successive values. Suppose you have the encryption of two messages with the same key:

ciphertext1 = plaintext1 ⊕ keystream1
ciphertext2 = plaintext2 ⊕ keystream2

keystream1 and keystream2 are indistinguishable from random to someone who doesn't know the key. Therefore ciphertext1 and ciphertext2 are also indistinguishable from random. Any relationship between the plaintexts is completely hidden by this random data, and not visible as a relationship between the ciphertexts.

Badly used modes of operation, for example using a non-random IV, can cause keystream1 and keystream2 to be related in some way. But that's due to badly using the encryption mechanism. The standard mechanisms themselves don't have such weaknesses.

Note that this assumes that Bob doesn't know the key. If Bob knows some part of K1, all bets are off. Never reveal part of a secret key.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Initially Bob knows K2, Enc(K2, B) and - after decryption - B. Later, he also knows Enc(K1, ABC), and - if we stick with ABC being a string - he knows that B was a substring of ABC, and how many characters A and C have, but not the characters themselves. $\endgroup$
    – LWChris
    Mar 10, 2020 at 21:03
  • $\begingroup$ If I understand you correctly, there is nothing else that Bob could learn apart from the things he already knows (which is fine). $\endgroup$
    – LWChris
    Mar 10, 2020 at 21:41
  • $\begingroup$ @LWChris Right. All well-regarded encryption mechanisms are safe to use even with related data. The formal definition of a good encryption mechanism is a fairly complex mathematical statement but it boils down to “if the adversary doesn't know the secret key and doesn't know one bit of the plaintext, but knows everything else (the whole ciphertext, all the other bits of the plaintext, other complete plaintext/ciphertext pairs), they still can't tell whether this bit is 0 or 1”. $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 11, 2020 at 9:02
  • $\begingroup$ @LWChris In practice, the failure of cryptography is not the basic buidling blocks, it's that it's badly used (e.g. things that should be random but weren't made random, encrypting data without authenticating it). $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 11, 2020 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.