-1

It is well-known that, doing a XOR of a file against a short key is highly insecure encryption (can be broken with frequency analysis).

But if the length of the key is equal to (or has same order of magnitude than) the length of the file to be encrypted, then the situation is close to a one-time-pad / Vernam cipher and it is secure (no frequency analysis can be done).

Is there a rule of thumb for which XOR cipher is generally considered as safe?

e.g.:

  • key size = file size => super safe, one-time pad
  • key size = (1/2) file size => looks really really safe, I don't see how a freq analysis could work with only 4 repetitions

  • key size = (1/100) file size => ?

  • key size = (1/10000) file size => ?

Let's say the file is 10 GB if it helps to get the order of magnitudes.


Example with key size = (1/2) file size:

file:       0101 0111    (size 8)
key:        0100 0100    (0100, i.e. size 4, repeated twice)

cyphertext: 0001 0011

Here the key 0100 is repeated twice. How could someone having only the size-8 cyphertext and knowledge of the fact the key is of size 4 break it?

  • to answer the bold question: they wouldn't, unless some of the text was known. If you know that a key repeats exactly once, and you know part of the file contents (EXIF, headers, BOM, etc), you can tell exactly what's on the other part of the CT keyed by the same offset. Contextually expanding those areas allows crawling beyond the duplicated materials. You can also use file format analysis to eliminate options, like a missing reserved char in a run of binary data. – dandavis Oct 17 '17 at 4:35
  • 1
    to answer the title's question, the percentage is 100%. – dandavis Oct 17 '17 at 4:48
4

It’s not just frequency analysis. If you reuse any part of a key that’s being XORed, an attacker just has to XOR the two ciphertexts with each other, and the key drops out entirely and you get the same result as XORing the two plaintexts with each other, which is pretty easy to decode.

A xor K xor B xor K = A xor B xor K xor K = A xor B, since K xor K will always be null.

  • So even with keylength = filesize / 2, you claim that it can be broken? If so could you provide an example with filesize = 10? (would help a lot for getting the idea!) – Basj Oct 16 '17 at 19:30
  • 1
  • 1
    @Basj - Real cryptographers use very conservative definitions of "broken". Try a search for "IND-CPA" and "IND-CCA" for examples. Reusing even a single bit of key material in an XOR cipher will render it insecure by the IND-CPA criterion. Using XOR at all (without a MAC) is already insecure by the IND-CCA criterion. – Nemo Oct 16 '17 at 19:49
  • 1
    My example was just one extreme simple case. There's plenty of realistic cases like it. For example, many files have lots of null bytes. By XORing the two halves of the ciphertext together, everywhere that was a null byte in one half of the plaintext results in a byte of plaintext. Any type of regular pattern in the file (such as the predictable frequencies of english ASCII characters or formatting data from many popular file formats) can be similarly exploited. An encryption scheme that is only safe for completely unpredictable/random plaintexts is not good and very far from state of the art. – Macil Oct 16 '17 at 21:20
  • 1
    @Basj An attacker will often know part of the plaintext. Here's an example for you. Suppose the plaintext you're encrypting is "From: Basj\nTo:Mike Scott:\nSet off the bomb now". Since the attacker can easily guess the first half of the text, because he already knows it's a message from you to me, he can decrypt the important part. – Mike Scott Oct 17 '17 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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