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

Question

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.

Answer 1

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))