in reply to How secure is XOR encryption?

Update: Thanks to talexb and Fletch for the missing HTML encodings. Sorry to all who tried to follow a non-existent link.

Distilled from the Cryptography FAQ:

8.2. How do I break a Vigenere (repeated-key) cipher?

A repeated-key cipher, where the ciphertext is something like the plaintext xor KEYKEYKEYKEY (and so on), is called a Vigenere cipher.

If the key is not too long and the plaintext is in English, do the following:

  1. Discover the length of the key by counting coincidences. (See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of the ciphertext against itself, count those bytes which are equal.

    If the two ciphertext portions have used the same key, something over 6% of the bytes will be equal. If they have used different keys, then less than 0.4% will be equal (assuming random 8-bit bytes of key covering normal ASCII text). The smallest displacement which indicates an equal key is the length of the repeated key.

  2. Shift the text by that length and XOR it with itself. This removes the key and leaves you with text XORed with itself. Since English has about 1 bit of real information per byte, 2 streams of text XORed together has 2 bits of info per 8-bit byte, providing plenty of redundancy for choosing a unique decryption. (And in fact one stream of text XORed with itself has just 1 bit per byte.)

    If the key is short, it might be even easier to treat this as a standard polyalphabetic substitution. All the old cryptanalysis texts show how to break those. It's possible with those methods, in the hands of an expert, if there's only ten times as much text as key. See, for example, Gaines [GAI44], Sinkov [SIN66].

XOR "encryption" is a toy. Play with it, have fun. Don't treat it as something real.

Russ
Brainbench 'Most Valuable Professional' for Perl

  • Comment on Re: How secure is XOR encryption? (Russ: not at ALL)

Replies are listed 'Best First'.
Re: Re: How secure is XOR encryption? (Russ: not at ALL)
by Anonymous Monk on May 03, 2004 at 16:26 UTC
    >in fact one stream of text XORed with itself Is this a typo? If so, why do you repeat the same mistake several times? Do you just not have a clue? 0 XOR 0 = 0. 1 XOR 1 = 0. Thus any bit string, XORed with itself, is a string of 0 bits as long as the input string. MVP my ass... Dag Johansen
      (And in fact one stream of text XORed with itself has just 1 bit per byte.)
      Yep, Dag, you're right when you say "Thus any bit string, XORed with itself, is a string of 0 bits as long as the input string."

      Therefore, it has one bit per byte.

      Perhaps you missed the part about shifting the string...

      I'm sorry if you believe an XOR "encryption" scheme is meaningful. Cryptography experts disagree.

A reply falls below the community's threshold of quality. You may see it by logging in.