0
$\begingroup$

(My interest is academic; I certainly have no intention of rolling my own crypto, especially the known-broken type!)

I know that if the nonce gets reused in a CTR stream, the two cipher blocks can be XOR'ed together to produce a XOR of the plaintexts. From there, the plaintext is recovered using analysis, such as searching for words. This makes unathenticated memory encryption, used in practice, insecure against someone who can edit the counter and trigger reuse.

But my understanding is that such analysis is enabled by the very low entropy of sample plaintexts - the usual examples are English text or bitmap images, which only use a small fraction of the block's information capacity.

Since txt files and bitmaps are relics at this time (easily found in OS files, though), could the attacker still recover the key from XORs of higher-entropy plaintexts in modern data formats?

Specifically to consider .docx, which is compressed with zip (weak compression), and lossy-compressed images or video (high entropy, but they include structure and headers, and can be useful even if severely damaged).

What if the nonce was reused many times, giving the attacker a much larger amount of information? I have a feeling that there might be some mathematical limit, e.g. best-case plaintext recovery requiring at least 1-(1-(entropy/Shannon_limit))^number_of_pairs>entropy/Shannon_limit.

But no idea if that holds, or if there are techniques to reconstruct plaintexts from XORs of general-case data, rather than specific kinds such as natural language.

Improve this question
$\endgroup$
4
  • $\begingroup$ Note that attacks become a lot stronger when the key-stream is used more than two times. $\endgroup$
    – CodesInChaos
    Commented Feb 12, 2018 at 16:34
  • $\begingroup$ Possible duplicate of Decrypting two XORed compressed messages? $\endgroup$
    – Meir Maor
    Commented Feb 12, 2018 at 17:21
  • $\begingroup$ Thanks, that question helped me get the idea. Mine is somewhat similar, but I'm interested in a more general case. If the plaintext or the key indeed can't be recovered, unless the plaintext contains easily analyzed content like uncompressed natural language, does that mean that even reused XOR pads still end up securing practical data? $\endgroup$
    – Therac
    Commented Feb 12, 2018 at 17:54
  • $\begingroup$ I flagged as duplicate, but now I notice though the question is similar to the one I asked, my question doesn't actually have much in the way of answers. It has content in comments and in the history of the accepted answer which was retracrted for being false. $\endgroup$
    – Meir Maor
    Commented Feb 12, 2018 at 18:16

1 Answer 1

Reset to default
2
$\begingroup$

A block cipher in CTR mode is just a stream cipher. You have a stream of bits that are indistinguishable from random (assuming good things about the block cipher) and you xor that stream with your plaintext.

What happens when you reuse the stream? It allows an attack to take their knowledge of one plaintext and use that knowledge to expose information about the other plaintext. If you encrypt all-zeros as the plaintext (or any message entirely known by the attacker) then the attacker knows the stream and can perfectly decrypt the second message, no matter what that message is. If, for the re-used portion of the stream, you encrypt two different perfectly random and secret bitstrings then the attacker will learn the relation between the bitstrings, $M_1 \oplus M_2$ but nothing more.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I figure, so the latter two cases (entropy very close to the limit) would never reveal the plaintext or the key. What about high, but not near-limit entropy, such as non-encrypted, weak (zip) compression? Can such plaintexts be conceivably recovered from a XOR of two blocks, or, as CodesInChaos pointed out, many XORs of block pairs in multiple nonce reuse? $\endgroup$
    – Therac
    Commented Feb 12, 2018 at 17:25
  • 2
    $\begingroup$ I imagine there is lots of structure and ordering to compressed data that could be used by the attacker as known plaintext. There's a magic number at the beginning, file headers, version numbers, data descriptors, file comments, etc etc. $\endgroup$
    – Thomas M. DuBuisson
    Commented Feb 12, 2018 at 18:03
  • $\begingroup$ M1 ^ M2 of two perfectly random strings does seem useless to an attacker. But are there padding bytes for strings that are not even multiples of the block length that, if known could be used? In essence, is just knowing the length of the strings enough to successfully attack? I suppose that if both strings are of the same length, you would have both padded with 0s and XORing them together gives 0s whereas if they are different lengths you leak the differing part of the longer string? $\endgroup$
    – ajl
    Commented Jun 7, 2019 at 15:51

Your Answer

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

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