Math to replace s-boxes - Good or bad idea?

Question

The following was going through my brain for the past week. If my thoughts are generally known to the cryptographic community would someone provide a link or two. Even if I’m making a classic newbie mistake.

Cryptographic internal functions operating like $x=f(x)$ can be table lookup s boxes with the inverse s box as a separate table. A 16-bit sbox and its inverse can be implemented with a little math and no tables. Use the prime $m = (2^{16})+1$. Then pick constants $p$ and $q$ such that the recursion

Seed = Seed * p % m;

touches all values, 1..$2^{16}$. Then select $q$ such that $p * q ~~mod~~ m = 1$.

p = 49374; // example values
q = 32065;
y = ((x+1) * p % m)-1; // forward
x = ((y+1) * q % m)-1; // reverse
// x+1 puts the 16-bit x into the range (1..2^16) where the recursion works.
// the -1 at the end makes the result fit in 16 bits.

There are over 32000 values of $p$ for which the recursion touches all $2^{16}$ values.

“Mod 0x10001” can be implemented with little more than a subtract. No actual division is required. Is this a reasonable part of a good encryption algorithm? Perhaps to replace 2 8-bit s box tables?

---

Getting carried away - - 32-bit (non invertible) sbox

Because $m=2^{32}+1$ is not a prime there is no full ($2^{32}$ term) sequence recursion of the form

Seed = Seed * const % m

This % m operation can also be formed with only a subtract if we don’t care to be super accurate. Or a test and subtract 1 it we want to be accurate. Thus encryption code performing

z ^= ((x+1) * const % m)-1

can be performed in decryption to recover the prior value of $z$.

Is this “32-bit sbox” a useful concept?

Answer 1

The S-boxes in quite many encryption algorithms (for example, in AES) have been already built with math (the AES S-box is an inversion function in $GF(256)$ plus an affine transformation). The lookup tables exist solely to ease the implementation. In fact, modern Intel/AMD CPU are already equipped with AES round function instructions, so the tables are not needed at all.

When people design new S-boxes, the first question to answer is Why? and the next one is What properties do they have compared to the existing ones?. Until there are reasonable answers, the proposals are not used and even not being analyzed.

Answer 2

It's a good idea, and is effectively already in use.

An s box is used to introduce a non linear transformation into cryptographic primitives. In this answer I'll only deal with irreversible s boxes. As the question highlights, an s box calculated in real time avoids the need for look up tables. These would be 256 bytes in size for an 8 bit s box, 132KB for 16 bits and 16GB for 32 bits. All these are based on a 32 bit Java machine. Whilst the 16 bit s box is easily manageable today, a 32 bit s box isn't so practical. Going wider is not currently realistic.

The OP suggests avoiding the look up table and using an algorithm to determine the s box's output. The algorithm is:-

p = 49374; 
y = ((x+1) * p % m)-1;

Plotting the input vs. output for the first one hundred numbers gives a troubling relationship:-

whereas it should look something like this if it were random with large hamming distances:-

One way to approach the issue of an s box algorithm is from Kolmogorov complexity. The posted algorithm is only 24 bytes long, and this simplicity is reflected in the highly organised and repetitive nature of the IO graph. Kolmogorov simplicity has begat simplicity. The red IO graph was plotted with a randomly populated 256 byte s box. It's Kolmogorov complexity is 256 bytes as the table is in compressible and cannot be defined in less bytes than actually listing the raw contents. Accordingly the output is highly random with very low compressibility /high Kolmogorov complexity.

Where such an algorithmic approach is currently used in in the row mixing sub round of the Whirlpool hash. A ersatz matrix hash is performed across eight bytes using the following matrix:-

This forms the equivalent of a 64 bit wide s box with would otherwise be impossible to store. However there is a price to pay in computation effort and time. I haven't plotted this IO relationship but I expect it to be less structured that the first Op's graph, but still have recognisable form. The Kolmogorov complexity is still low as the matrix is clearly compressible either as rotated columns or an equation like x^8 + x^4 + x^3 + x^2 + 1.

For maximum non linearity a totally random matrix can be used that has a Kolmogorov complexity equal to the matrix size. Such matrices are used in randomness extractors for true random number generators. The matrix might be 1000 - 2000 bits in size forming an equivalent s box of ~40 bits width. And this can be expanded to much wider equivalent s boxes. As a example, a 2048 bit wide s box can be easily constructed with 64KB of randomly permuted Pearson hash tables.

In summary, if an s box wider than 16 bits is required, the algorithmic approach is the one currently used. However there is a time penalty to be paid as they're much slower than a plain look up table.