24
$\begingroup$

I am a programmer, so when I hear XOR, I think about the bitwise operator (e.g. 0110 ^ 1110 = 1000).

The mention of "XOR" comes up quite a bit in cryptography. Is this the same XOR as the bitwise operator? If so, how is it used to encrypt a large amount of data rather than just an integer? Wouldn't you need the "password" to be the same length as the data you are encrypting?

$\endgroup$
  • $\begingroup$ In a simple word XOR means if one of them says no then it is yes. The only way it will be no is if both says yes. $\endgroup$ – iamnamrud Jan 31 '18 at 13:24
  • $\begingroup$ @iamnamrud From google: XOR is "a Boolean operator working on two variables that has the value of one if one but not both of the variables has a value of one". That is: 0^0=0, 0^1=1, 1^0=1, 1^1=0 $\endgroup$ – John Wiersba Dec 24 '18 at 19:20
27
$\begingroup$

Yes, it's the same XOR. It gets used inside most of the algorithms, or just to merge a stream cipher and the plaintext.

Everything is just bits, even text. The word "hello" is in ASCII 01101000 01100101 01101100 01101100 01101111. Just normal bits, grouped in 5 bytes. Now you can encrypt this string with a random string of 5 bytes, like an One-time pad. Let's say we got the randomly generated string 10001001 10000010 00001011 01001101 11101101 (generated with www.random.org). Now we XOR both strings, getting 11100001 11100111 01100111 00100001 10000010. If you never reuse or reveal the key, nobody can crack this cipher. (Well, I did reveal the key, so it's not secure anymore.)

Many block ciphers use XOR. Let's take AES: The Advanced Encryption Standard uses xor on single bytes (some other algorithms use blocks of 16 or 32 bits; there's no problem with sizes other than 8 bits). The round key will be XORed with the intermediate result and after that permuted and substituted. XOR also gets used in the key shedule.

IDEA also uses XOR as one of its three main functions: XOR, addition and multiplication.

XOR has (inter alia) these advantages when used for cryptography:

  • Very fast computable, especially in hardware.
  • Not making a difference between the right and left site. (Being commutative.)
  • It doesn't matter how many and in which order you XOR values. (Being associative.)
  • Easy to understand and analyse.

Of course, some of this "advantages" can be disadvantages, depending on the context. The fast speed makes it possible to use XOR often without huge performance drops. The security of Threefish, another block cipher, relies on the non-linearity of alternately using modulo addition and XOR. Despite of the use of 72 rounds (as the base of the hash function Skein) it's still quite fast.

XOR alone is not enough to create a secure block or stream cipher. You need other elements like additions, S-boxes or a random, equally long bit stream. This is because of the linearity of the XOR operation itself. Without non-linear elements, a cipher can easily be broken. See Why do block ciphers need a non-linear component (like an S-box)? for more details on why non-linearity is important.

$\endgroup$
  • $\begingroup$ Left "side". I don't get the disadvantages in the first to last section. $\endgroup$ – Maarten Bodewes Sep 30 '18 at 2:59
  • $\begingroup$ It might be worth emphasizing that XOR is its own inverse in that $a = (a \wedge b) \wedge b$. So, if $m$ is a message and $k$ is a key, then $k$ can be used to both encrypt the message $e = m \wedge k$ and decrypt $m = e \wedge k$. $\endgroup$ – sfmiller940 Dec 26 '18 at 19:35
11
$\begingroup$

Yes, the XOR used in cryptography means the same bitwise XOR operator you're familiar with.

And yes, to securely encrypt a message with XOR (alone), you do need a key that is as long as the message. In fact, if you have such a key (and it's completely random, and you never reuse it), then the resulting encryption scheme (known as the one-time pad) is provably unbreakable!

Of course, in most circumstances, using such long keys would be extremely impractical. Instead, the trick we use is to generate the XOR key "on the fly" from a shorter key, basically by using the short key to seed a suitable pseudorandom number generator and XORing the message with the output of the generator.

Of course, for this trick to work, there cannot be any easy way for an attacker to recover the short key (or anything else that would let them predict the output of the generator) by observing the encrypted message (or even the raw output of the generator, which they may obtain if they can guess or choose the plaintext). Most simple commonly used RNGs don't withstand this test, but we do have various kinds of generators believed to be secure against such attacks.

This kind of an encryption scheme is known as a (synchronous) stream cipher; see the Wikipedia article (and/or the tag here) for more details.

$\endgroup$
0
$\begingroup$

If you think about ciphers, their purpose is to combine a message with a secret key in such a way that the message is concealed without knowing the key (and the data, obviously). For example, take a look at an old Caesar cipher.

With Caesar cipher, you first enumerate English letters and come up with a secret passphrase. To encrypt the message you add a number corresponding to message letter to a number corresponding to passphrase letter, then decode resulting number back to English letter to obtain the encrypted message. And if the resulting number is >26, you loop from the start of the alphabet. This can be displayed as:

$E_n(x) = (x + n) \mod 26$

In this case we perform addition modulo 26.

But since the most efficient way to represent data on a modern computer is the binary system, cryptographic algorithms also evolved to process binary-encoded data rather then English alphabet (it allows to process generic data as well, not only English words). And the operation of addition when working with binary data — means adding modulo 2.

Now to intuitively understand why specifically XOR is so ubiquitous in cryptography it's helpful to look at the essence of this operation in arithmetic context.

While in boolean algebra XOR is an eXclusive OR logic operation, in arithmetic context it's just an addition modulo 2.

So to answer the original question: in modern cryptography XOR means addition, and addition is used every time we need to combine two blocks of binary data (which in many ciphers happens quite often).

$\endgroup$
  • $\begingroup$ Addition modulo 256 is working perfectly fine for a binary Caesar cipher - that's not a good reason to use XOR / addition modulo 2. $\endgroup$ – Maarten Bodewes Sep 30 '18 at 3:01
  • $\begingroup$ @MaartenBodewes Good reason to use modulo 2 is efficiency, which is specified in the answer. Caesar cipher was just an example to show how addition (any kind of addition) is often used in ciphers and then later demonstrate that XOR is also an addition (just modulo 2), as from my experience programmers tend to only consider XOR purely from a boolean logic point of view. $\endgroup$ – zoresvit Sep 30 '18 at 4:45
  • $\begingroup$ @MaartenBodewes The reason I pointed that out is that none of the answers above described XOR as essentially just an addition modulo 2. And then I tried to come up with a simple example why addition is often used. I'm open to better examples :) $\endgroup$ – zoresvit Sep 30 '18 at 5:00

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.