# How to design a reversible shifted XOR with an S-box?

According to this post, S-boxes are invertible.

Inverting S-boxes can be very easy: you simply create a lookup table that reverse all the possible substitutions of the S-box. E.g. if the S-box maps 0xA5 to 0x3F (this would be an 8x8 S-box), then the inverse transformation would map 0x3F to 0xA5. Thus, you simply enumerate all the possible values the S-box can have, and create an inverse table that "undoes" all those transformations (this effectively limits how large the S-boxes can be in practice).

Now, consider f, which XOR the higher bits in x by a mask determined by the lower bits with an S-box.

s_box = [
8, 7, 0, 10, 1, 3, 5, 12,
11, 13, 15, 14, 2, 6, 9, 4
]

def f(x):
x ^= s_box[x & 0xF] << 2
return x


It turns out that this particular configuration is not invertible, since it produces fewer than 256 unique outputs.

>>> unique = set(f(x) for x in range(0xFF))
>>> len(unique)
192


Question: how do I design the S-box and/or shift amount such that shifted XOR with an S-box is invertible? Bonus points if your answer applies to other reversible integer operations, e.g. multiplication by an odd integer determined by an S-box.

In case you are wondering about the background, I am designing a perfect (i.e. collision-free) hash function that maps a 14-bit input to a 14-bit output. It doesn't need to be cryptographically secure, but I want good statistical properties (e.g. the avalanche effect). Intuitively, S-boxes can induce good mixing, but I cannot afford to store an S-box of $$2^{14}$$ entries, so I'm considering reversible integer operations based on a tiny S-box lookup. Moreover, I want to minimize the computational cost of $$f$$, but I don't care how long it takes to compute $$f^{-1}$$. Any suggestions are appreciated.

• if x is 4-bit (that's how the Sbox is defined) what's the point of the mask with 0..01111? if x is larger than 4-bits then the map cannot be one-to-one (and invertible) by definition, no? I don't necessarily understand the c notation. Does masking with 0xF mean zero out all bits other than the 4 LSB bits? Commented May 1 at 6:24
• the first problem you use << not rotation and this causes information lost for inverses. Commented May 1 at 7:47
• @kodlu I am thinking about 8-bit input/output. You are right that x & 0xF extract the 4 LSB bits, so s_box[x & 0xF] is not invertible, but my question is how to make $f$ invertible, i.e. compute x from x ^ (s_box[x & 0xF] << 2). Commented May 1 at 14:38
• @kelalaka Can you explain further? I think operations like hash ^= hash << 3 are invertible despite using <<. See for example this page. Commented May 1 at 14:40
• @kelalaka is right. the examples you point to at that link are defined for integers $\mathbb{Z}$ and that is an infinite ring and they use no masking. Masking destroys the ring structure. Commented May 1 at 15:05

The kind of S-box you're trying to use is a permutation, and your goal is to build a permutation out of it. The easiest way to show that something is a permutation, and the approach we typically use in cryptography, is to make each step in its computation invertible. This is not the only way, but it is the easiest and most common one.

However, your operation is not invertible. You have 8 bits of input and you're taking the bottom four bits and using them to modify the middle four bits. In general, that isn't going to result in an invertible value since there's overlap in that set of bits. Even if it did in your case, that would probably not be a good sign for your S-box, since S-boxes are typically not supposed to have that kind of structure.

If you generate an approach where the bottom four bits are used to modify the top four bits and vice versa, that's invertible. You can perform bitwise rotates, modular additions and subtractions, XORs, bitwise negations, and so on, and as long as each of the steps is individually invertible, you'll continue to have a permutation. This is the approach of the SPARKLE ARX-box and the AES S-box.

An example of what you can do is below. Note that I've switched to range(256) since that produces the values from 0 to 255.

I make no claims that this is a secure or useful permutation, that it has good linear or differential characteristics, or that it can be of any general benefit. It's only an example of what can be done.

s_box = [
8, 7, 0, 10, 1, 3, 5, 12,
11, 13, 15, 14, 2, 6, 9, 4
]

def ror(x, n):
return ((x >> n) | (x << (8 - n))) & 0xff

def f(x):
x ^= s_box[x & 0xF] << 4
x = ror(x, 3)
x = (x + 0x1b) & 0xff
x = ~x
x ^= s_box[x >> 4]
x ^= 0xa5
return x

unique = set(f(x) for x in range(256))
print(len(unique))

• Thanks for the help! In general, is the "shifted XOR with an S-box" operation always invertible as long as there is no overlap between the bits used in S-box lookup (i.e. lower 4 bits) and the bits being XOR'ed (i.e. upper 4 bits)? I cannot see why that's the case. Commented May 2 at 5:59
• As long as the S-box is a permutation, it should be. That's because in this case, the operation is the inverse of itself, and it will operate correctly as long as the bits that are the input to it are unchanged. Commented May 2 at 21:57