Binary functions

or "Why cryptographers like XOR"

In this essay I intend to explore the binary functions of two bits and their possible use in cryptography. I shall, nonetheless, try to keep the maths simple.

Let's start with binary functions

We are looking for functions suitable for cryptographic use. Let's say we're striving for something suitable to go between a clear-text stream of bits and an OTP stream of bits. Before we explore what type of function we want, let's have a look at what functions there are.

A binary function is defined by a truth table. Let's take a familiar example, logical AND, and display the truth table.

A B A & B

0 0 0

0 1 0

1 0 0

1 1 1

Now we have an idea of what we're working with. How many potential functions are there? You'd think that there's no end, but there are in fact, exactly 16. This is why:

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

A B A op B

0 0 b₀

0 1 b₁

1 0 b₂

1 1 b₃

A	B	A op B
0	0	b₀
0	1	b₁
1	0	b₂
1	1	b₃

We see that we can characterise a function by a 4-bit number, using the number b_Ab_B to refer to a bit in a specific number. And there are obviously only 16 different 4-bit numbers.

Curiously, this very idea of numbering functions show up in a lot of places, though the most obvious (and still unexplained) place would be in the X11 GraphicsContext data structure, where the GCFunction member is exactly this (the function tables are described in the XCreateGC(3x) man page on my machine), though there is no explanation of why each number gives the logic function it does.
MUX-based boolean function units
MUX-based functional units, ignoring A, B and result lines

And now, on to cryptographic needs

For the type of encryption we're looking at doing (a stream cipher), we will need a function that takes two bits, returns a result and lets us figure out one if the two source bits if we have the other. There's some more constraints, too.

Thinking about it, we will want a function that has a numbering above in one of these ways: 01xx or 10xx ; xx01 or xx10. This is so we have a way of figuring out the plain-text (the B above) when we have a bit of the key (the A above). Looking at the signatures we want, we find that there are four possible functions, tabled below:

K P P K^P !P K==P

0 0 0 0 1 1

0 1 1 1 0 0

1 0 0 1 1 0

1 1 1 0 0 1

K	P	P	K^P	!P	K==P
0	0	0	0	1	1
0	1	1	1	0	0
1	0	0	1	1	0
1	1	1	0	0	1

Looking at these four functions, we can see that two are patently unsuitable, because they don't involve the key bit, at all (one is P as-is, the other is the complement of P) and are therefore not really of cryptographic interest. One is about as secure as ROT-13, the other as secure as ROT-26.

That leaves us with two possible functions, XOR and EQL. On the surface, they're both equally suitable, though there is a crucial difference. Looking at how to go from C (the cipher-text) to P (plain-text) given K (key), we can just use XOR again, if we started with XOR. If we have EQL, we can still recover the plain-text, it's just a bit hairier. This makes the encryption method and the decryption method asymmetric and that means you need to know if you're encrypting or decrypting. Messy and failure-prone.

Why symmetry matters

It's much easier dealing with cryptography the more symmetry there is. Ideally, both encryption and decryption use the same key and method. More often, either key or method are shared and the other is different (typical example of "same method, different key" is public-key cryptosystems like RSA).

The fact that there's no more expressive power with the EQL-based stream cipher means there's no actual advantage using it over XOR (same expressiveness, one less convenient aspect).

Is EQL of any cryptographic interest?

We could, in principle, imagine a stream encryption that uses one bit stream to select XOR or EQl and one bit stream as the key data (or, possibly, a single stream where we use two sequential bits to determine EQL and XOR).

This is possible, but is, essentially, the same as just XOR-ing the two key bits together, then use that as the key (at least if you take 0 to mean XOR and 1 to mean EQL).

So, in short, no EQL is of no cryptographic interest. It does the job, but it's more cumbersome than XOR and it isn't interesting for being combined with XOR.

It is possible that a bit stream using three key bits for each bit of plain-text might be of interest, but I imagine it would reduce to being no harder to analyse than a plain single bit key for single-bit plain-text XOR encryption and would require more key generation (pseudo-random and thus having its own set of problems) or longer one-time-pad (cumbersome and expensive).

This is one of Ingvar's essays