Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have heard criticism of various cryptosystems saying that "at their heart, they were just XOR."

Is this just ignorance, or is there something inherently wrong with XOR based ciphers?

share|improve this question

4 Answers 4

up vote 23 down vote accepted

It's important to make the distinction between ciphers which use XOR internally as a component operation (which is nearly all of them), and 'ciphers' which just XOR the plaintext with a secret. If the key is the same length as the plaintext, then it's a one time pad, so in some sense, yes, with "sufficient randomness" you can safely encrypt with XOR. The problem with this is that it only applies if the key is exactly as long as the plaintext, and is perfectly uniform random. If it's not, then you've basically created a Vigenere cipher, which can be trivially broken. It's interesting, and unfortunate, how the 'provable security' of the OTP fools people into thinking they can just take a little shortcut or two and still get something safe.

Typically, people who implement simple XOR ciphers compound their mistake by using hard-coded keys, in which case a single known plaintext/ciphertext pair is sufficient to decrypt anything. That's probably mostly because if you were some kind of prebuild crypto toolkit, it would be easier to just use AES along with your RSA key management, etc, versus using a decent key distribution scheme and then using XOR with your safely shared keys.

share|improve this answer

If the key used to XOR your plaintext is any shorter than your plaintext, then the repeats will give it away. If the key is truely random, and never reused, it is effectively a one-time-pad.

The historical name for XOR encryption is Vernam cipher.

is there something inherently wrong with XOR based ciphers

The amount of effort you need to put into ensuring that your key is random enough is as much effort as you need to put into coming up with a more secure algorithm. By using XOR, there is a very weak link that you have to put huge amounts of effort into securing.

If you were doing something like in your other post, making the key out of the hash of the message, then your key is now the length of your hash output (160 bits for SHA-1, 512 bits for SHA-512). If your messages are guaranteed to be less than the length of the hash, then you're ok. If any message is longer, an attacker has a place to start.

share|improve this answer
    
But that's only true for text messages, right? What if we have, say, an executable file, or an image file? Is it still vulnerable? –  Soumya Jul 12 '11 at 23:42
1  
@Soumya92, even if it is a picture or exe, those file formats are well known, so you can still attack those. –  Tangurena Jul 13 '11 at 0:44

The most known example of just XOR would be the One-time pad (or at least, one of its implementations). It just takes a random key stream and XORs it with the plaintext stream to create the cipherstream. The one-time pad is also the only provably perfect cipher, where knowing any amount of ciphertext and plaintext does not help to know any single additional bit of plaintext.

For a more practical example: The Output feedback mode and the Counter Mode for using block ciphers to create a stream cipher also are essentially just XOR: they each create a key stream from the key, and then XORs the key stream with the plaintext to create the ciphertext, or XOR the key stream with the cipher text to get back the plaintext.

Both the OTP and the OFM/CTR for stream ciphers have the same problem, which is inherent in just XOR: If you are doing a MITM-attack and can guess (parts of) the plaintext, you can replace the corresponding parts of the ciphertext to modify the plaintext to something of your choosing, without knowing anything at all about the key.

Whether this is a real problem depends on your application, and it can be avoided by combining the encryption with a message authentication code (MAC).

share|improve this answer

I've got a feeling that I'm going to write this a lot on here: define "sufficient". The question you must answer is "what do you want to protect and how much is it worth to you"? In general, a plain XOR cypher with a key shorter than the total plaintext encrypted is pretty weak, and methods for decrypting are more or less trivial. So if there's a lot of value there, it's not adequate.

On the other hand, rot-13 is even more trivial to decrypt (after reading USENET for years and years I can almost read rot-13 directly.) It is, however, adequate (or nearly adequate, given the existence of freaks like me) for its usual purpose: preventing someone from being offended without having to take a purposeful step to agree to read something.

There is a good way to make this decision: base the decision on risk. By definition, risk is

$$R = P · H$$

where $R$ is the risk, $P$ is the probability of an undesired event happening, and $H$ is the hazard, or consequences of that undesired event. Currency is almost always a good measure for H.

Now, consider the choice of a password rule. The probability of a password being guessed in one try of a brute force attack is roughly $2^{-h(p)}$ where $h(p)$ is the entropy of the password $p$ that satisfies some password rules, and the value is given in bits. (And entropy is $\log_2$ of the number of possible passwords that satisfy the rule, who says security is complicated?) The old fashioned all-lower-case alphabetic password of length $\le 8$ characters is about 38 bits. The entropy of an ATM card 4-digit pin number is only about 13 bits.

Now, let's say that your average ATM card account has a balance of \$3000, and you don't want to lose more than about \$10 per account per year from guessed PIN numbers. Is a 4 digit PIN sufficient?

$$R = 2^{-13} · \$3000$$

or about \$0.36. Plenty sufficient.

(Pop quiz: what about for the guy who apparently had a \$99 million checking account balance?)

A simple XOR cipher is easily decrypted using frequency analysis, so it's not very suitable for anything important. Why? Because as the length to the ciphertext grows, the probability of successfully decrypting the message approaches 1. Thus the risk approaches H. But if the value of what you're encrypting is near 0, then the risk is also near 0, and so an XOR encryption might be suitable.

share|improve this answer
    
There are non-linear risk measures - many people prefer loosing only a little (with high probability) than loosing much (with low probability), even when your formula says that it is the same risk. –  Paŭlo Ebermann Jul 13 '11 at 1:25
1  
For your ATM-card/PIN example, you are supposing that for each account the card gets stolen once a year, and then only one PIN is tried there. –  Paŭlo Ebermann Jul 13 '11 at 14:25
    
RIght, that's utility weighted. Since everyone has a different utility function, that's not very useful. –  Charlie Martin Jul 13 '11 at 19:20
    
@Paulo you're right that could be carried out a little further, say by having a rul that blocks the PIN after 3 unsuccessful tries. The important point, though, is still to identify risk as the driver. –  Charlie Martin Jul 13 '11 at 19:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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