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?
$\begingroup$
$\endgroup$
1
asked Jul 12, 2011 at 22:15
-
$\begingroup$ If this was presented as a criticism, it sounds like an attack on stream ciphers: (as opposed to block ciphers,) they really are "just [a CSPRNG composed with] XOR". Block ciphers do have a number of security advantages, but it is definitely a reductionist criticism that by no means addresses the biggest flaws. I'd be worried if it were presented anywhere more serious than, say, a TED talk. $\endgroup$– JamesTheAwesomeDudeApr 21, 2021 at 20:45
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ I am a bit confused. Would it be really safe to encrypt(or XOR) P with the secret regardless it's one-time pad or not? Can't you just recover the secret buy undoing the XOR on P and resulting C? I think what we mean here as "secret" maybe something that you can't recover the key from. For instance, a keystream/KS where KS = F(Secret, Nonce/IV). $\endgroup$– stdoutOct 20, 2019 at 11:01
-
$\begingroup$ @stdout If you transmit $\oplus(m_1,S)$, and then later transmit $\oplus(m_2,S)$, then an attacker who saw both might start deducing $m_1$ and $m_2$. If you're XORing [something] with your message to hide its content before transmission, then, by definition, that [something] is your OTP key $S$ (if previously shared privately), or must have been derivable from your key $k$ (if you were using, say, a stream cipher, then your shared key). $\endgroup$ Apr 21, 2021 at 20:26
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ 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? $\endgroup$– user93Jul 12, 2011 at 23:42
-
1$\begingroup$ @Soumya92, even if it is a picture or exe, those file formats are well known, so you can still attack those. $\endgroup$ Jul 13, 2011 at 0:44
$\begingroup$
$\endgroup$
6
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.
-
1$\begingroup$ 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. $\endgroup$ Jul 13, 2011 at 1:25
-
1$\begingroup$ 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. $\endgroup$ Jul 13, 2011 at 14:25
-
$\begingroup$ RIght, that's utility weighted. Since everyone has a different utility function, that's not very useful. $\endgroup$ Jul 13, 2011 at 19:20
-
$\begingroup$ @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. $\endgroup$ Jul 13, 2011 at 19:22
-
$\begingroup$ "A simple XOR cipher is easily decrypted using frequency analysis" - this does NOT apply when you're not reusing key data, right? $\endgroup$ Dec 13, 2018 at 20:46
$\begingroup$
$\endgroup$
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).
answered Jul 12, 2011 at 22:41
$\begingroup$
$\endgroup$
1
Practically though, if you were to ship (securely) a one tera-byte disk containing random bytes to a friend, then you would have a very safe channel for up to one TB of communication, enough for quite some time.
