4
$\begingroup$

Stream ciphers use a deceptively simple mechanism: you combine the plaintext data, bit by bit, with “key” bits, using the exclusive or operation.

enter image description here

Why can't I use other opeartions such as NAND, AND, OR . Can you guys give me one real time example which brings advantage of using XOR over other operations.

Improve this question
$\endgroup$
1
  • $\begingroup$ Well, have you tried working it out? to see what would happen with NAND, AND or OR? $\endgroup$
    – ilkkachu
    Dec 22, 2022 at 10:18

6 Answers 6

Reset to default
21
$\begingroup$

Why can't I use other opeartions such as NAND, AND, OR

Because it needs to be invertible.

For example, if you use NAND, then if the bit from the key generator is a 0, then the output of the NAND will be 1, no matter what the data bit was. Hence, when the decryptor tries to recover that data bit, it can't.

If you assume that the operation works on individual bits, is invertable, is stateless and adds security (hence having the output which is just the plaintext bit is not acceptable), then the only two possibilities that work are XOR and XNOR (which is just XOR with the output inverted).

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ XNOR is the same as "equals", i.e. $a\,\mathrm{XNOR}\,b \Leftrightarrow a = b$ $\endgroup$
    – rexkogitans
    Dec 22, 2022 at 7:33
  • $\begingroup$ though in practice you could use per-byte operations, too, allowing e.g. addition along with XOR. $\endgroup$
    – ilkkachu
    Dec 22, 2022 at 10:20
  • 1
    $\begingroup$ @ilkkachu: actually, if you process multiple bits at once, there are lots of possible operations. As long as the operation is a latin square, there's no security difference, hence it comes down to practical considerations. And, xor does have some practical advantages; for example, if you add mod 256, well, a 64 bit processor might not have a 'multiple-add-by-256-in-parallel' instruction, and hence it is not as efficient as it could be. $\endgroup$
    – poncho
    Dec 22, 2022 at 13:25
  • $\begingroup$ @poncho, yes, indeed. I just mean that while defining stream ciphers in bits is nice in theory, in practice most messages are byte-granular anyway, so one could instead use some multi-bit operation too, instead of XOR/XNOR being the only options. $\endgroup$
    – ilkkachu
    Dec 22, 2022 at 13:28
8
$\begingroup$

Edit: For any additive group operation, including addition modulo $k$ if the added keystream symbols $z_t$ are uniformly distributed, which means $$ Pr(z_t=a)=1/k, \quad \forall a \in \{0,\ldots, k-1\} $$ then the ciphertext symbols $c_t=x_t+z_t \pmod k$ are themselves uniformly distributed, $x_k$ being the plaintext symbol. You can show this in exactly the same manner as in the new answer by @user93353. Essentially addition of symbols corresponds to convolution of the probability distributions of $z_t$ and $x_t$ to get the probability distribution of $c_t$.

The idea of using addition is older than modern ciphers. In classical alphabetic ciphers, addition modulo $k$ over a finite alphabet of size $k$ will work. Note that XOR is a special case of this where addition is modulo 2.

Addition modulo $k$ just means that you add $a,b \in \{0,1,\ldots,k-1\}$ by taking the remainder after division by $k,$ if necessary; this is sometimes informally referred to as clock addition: If the time is 10 am, 4 hours later the time is $10+4 = 14 \pmod{12} \equiv 2$ hence you obtain 2 pm.

Consider the alphabet $\{A,B,\ldots,Z\}$ modelled by $\mathbb{Z}_{26}$ the integers modulo 26 under addition where we have the encoding $$ A\leftrightarrow 0, B\leftrightarrow 1,\ldots,Z\leftrightarrow 25. $$ or pictorially here

If you have the plaintext ATTACK it is represented by the sequence $$0,1,1,0,2,10$$ and if you additively apply the key SECRET represented by the sequence $$18,4,2,17,4,19$$ you obtain the ciphertext $$ 0+18,1+4,1+2,0+17,2+4,10+19=18,5,3,17,6,29 $$ which after applying the modulo 26 reduction becomes $$ 18,5,3,17,6,3 $$ giving the ciphertext SFDRGC.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ TL:DR in practical terms: add or sub with wrapping at any chunk-size boundary would also work, usingadd to encrypt and sub to decrypt or vice-versa. XOR is just add-without-carry, or addition in 1-bit chunks instead of for example 8-bit or 32-bit chunks like you could do with CPU instructions like x86 paddb or paddd respectively to operate on 128 bits at a time (16 uint8 or 4x uint32) like with pxor (128 separate bits). (SIMD add/sub have worse throughput than SIMD bitwise booleans on some older CPUs, but still better than 1/clock so it wouldn't be a bottleneck.) $\endgroup$
    – Peter Cordes
    Dec 22, 2022 at 10:59
  • 1
    $\begingroup$ It might be interesting to mention that this is a property of what is known as the "Haar measure" of a group. Viewed in this way, you can do things like define the one-time pad over non-abelian groups, or even infinite groups. Neither is useful (and the infinite group case is insecure due to requiring a variable-length encoding of group elements). $\endgroup$
    – Mark
    Jun 23 at 4:56
  • $\begingroup$ @Mark, interesting. Why do you say non-abelian is not useful, is it because you cannot decrypt with the same key? But there may be an actual interest in the interplay between a left key addition and a right key addition for some applications? $\endgroup$
    – kodlu
    Jun 23 at 5:20
  • 1
    $\begingroup$ You can decrypt with the same key. For a group $G$ sample from the haar measure on the group, and let $\mathsf{Enc}_s(x) = sx$, and $\mathsf{Dec}_s(c) = s^{-1}c$. Correctness is immediate. Security follows from the Haar measure being invariant under group multiplication (combined with essentially the same proof as the security of the one-time pad). And "not useful" here isn't some formally provable thing, just it's not clear why not being ablian would help. Generally, having more algebraic structure is better (except when it enables attacks). Both schemes here are info-theoretically ... $\endgroup$
    – Mark
    Jun 23 at 19:47
  • 1
    $\begingroup$ secure though. So what's the benefit of giving up the abelian structure? $\endgroup$
    – Mark
    Jun 23 at 19:47
7
$\begingroup$

  1. The first reason obviously is that XOR is reversible. AND and NAND are not reversible.

  2. But the important reason is found by looking at the truth table for XOR

Let $x$ be the plain text bit & let $s$ be the bit from the keystream generator.

x s output
0 0 0
0 1 1
1 0 1
1 1 0

If the keystream bit $s$ is perfectly random, then it has 50% chance of being $0$ or $1$. In this case, the output also is perfectly random - i.e. has a 50% chance of being $0$ or $1$

XOR function is perfectly balanced, i.e., by observing an output value, there is exactly a 50% chance for any value of the input bits. This distinguishes the XOR gate from other Boolean functions such as the OR, AND or NAND gate.

This can also be proved more formally.

Let the probability of the clear text bit $x$ being $0$ is $p$. $p$ can be any value.

$P(x = 0) = p$

$P(x = 1) = 1 - p$

$P(s = 0) = 0.5$

$P(s = 1) = 0.5$

$P(x\text{ XOR } s == 0) $ (Probability of output of $XOR$ being $0$)

$= P(s = 0) \star P(s = 0) + P(x = 1) \star P(s = 1) =$

$= p \star 0.5 + (1 - p) \star 0.5$

$= 0.5x + 0.5 - 0.5p$

$= 0.5$

$P(x \text { XOR } s == 1)$ (Probability of output of $XOR$ being $1$)

$= P(x = 1) \star P(s = 0) + P(x = 0) \star P(s = 1) $

$= (1 - p) \star 0.5 + p \star 0.5$

$= 0.5 - 0.5p + 0.5p $

$ = 0.5$

So we see that irrespective of what is the probability of the cleartext bit $x$ being $0$ or $1$, the output has exactly 50% probability of being $0$ or $1$.

Improve this answer
$\endgroup$
0
5
$\begingroup$

As the other answers say, the reason is that XOR is invertible. Your diagram shows exactly that: $$f(P, K) = C$$ $$f(C, K) = P$$

Actually, there are many functions that are invertible.

If we operate on separate bits (argument length is 1 bit, or arity = 1), then besides XOR we can construct other invertible functions, for instance: $$f(P, K) = \lnot (P \oplus K)$$ Its inversion function is: $$f^{-1}(C, K) = (\lnot C) \oplus K$$

We can also define many other functions that operate not on a single bit, but on groups of 2 bits or even on 8 bits. For instance, the definition may look as follows:

|  a       |  b       | f(a,b)   |
|----------|----------|----------|
| 00000000 | 00000000 | 11010011 |
| 11010011 | 00000000 | 00000000 |
| ...      | ...      | ...      |
| 00110010 | 01001101 | 10010110 |
| 01001101 | 10010110 | 00110010 |
| ...      | ...      | ...      |

But implementation of such function can take much resources. E.g. for $arity = 8$ the definition would contain $2^8 * 2^8 = 2^{16}$ elements in generic case. But since it needs to be invertible, it will contain 2 times less elements, $2^{15} = 32K$. Means, just the function definition would need 32K memory. Hardware operations with such function can be relatively slow.

Whereas hardware implementation of XOR is very simple and very efficient.

Improve this answer
$\endgroup$
1
$\begingroup$

This says what the other answers say (necessarily) but in a way which is simpler and which may be more intuitive. It may be useful to see things put this way.

  • XOR inverts a data bit if the key is 1 and does not invert it if the key is 0.
    (A random key data stream randomly does or doesn't invert data bits.)

  • When the same key stream is applied to the encrypted data stream it reinverts the bits which were inverted during encoding, thus restoring the original data bit AND does not invert bits that were not inverted during encoding, so you obtain a data stream identical to the original.

  • No function other than XOR has these properties*.

*XNOR is simply XOR inverted - XNOR inverts on key = 0 and dooes not invet on key = 1 - the end to end result is the same.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Things like integer addition or subtraction in some chunk size (like 8-bit) would also work, but then the decryption function has to be different than encryption, doing the opposite operation. So your middle property isn't satisfied, but it's still usable as a more-complicated way to use a stream cipher. $\endgroup$
    – Peter Cordes
    Dec 22, 2022 at 11:05
  • $\begingroup$ @PeterCordes Yes/and ... :-) . I was addressing a bit by bit encoding system (as (most?) others here do). Doing things with more than one bit at a time opens up all sorts of possibilities. $\endgroup$
    – Russell McMahon
    Dec 22, 2022 at 11:30
  • $\begingroup$ Indeed, kodlu and mentallurg both posted answers about working in chunks. $\endgroup$
    – Peter Cordes
    Dec 22, 2022 at 11:32
-1
$\begingroup$

Because those papers were written after The Great God Gates invented the computer. Computers find XOR easy/fast/boring.

Invertability is crucial in encrypting and then decrypting a message. But it doesn't have to be XOR. It only has to be a varied bijective function, i.e. a one-to-one correspondence subject to an external variable. So for example "A" maps to "giraffe" given 200, "B" maps to "5" given 1 and "C" maps to $\Psi$ given 65 but maps to $\mu$ given 64, e.t.c. And in reverse. Uniquely. It's just luck that XOR happens to be bijective.

Since cryptography is more of an art than science, it's up to you to develop your own fun mapping. As long as its 1:1. Perhaps it'll look like:-

pad

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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