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

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?

-
I think you will find S-boxes are generally just not arbitrary permutations but often need to fulfill security properties such as resistance against linear/differential cryptanalysis (in the context of the ciphers they are used with) and not all S-boxes can be (reasonably) reached by your first algorithm, which means you also cannot efficiently "invert" the procedure to find $(p, q)$ from an arbitrary S-box, not even for 8-bit ones (perhaps it can be done if you add more degrees of freedom to your formula, but then you run the risk of being too expensive/vulnerable to side channel attacks). – Thomas Jul 3 '14 at 5:30
I am currently designing algorithms to generate and test 16-bit sboxes, and I need to devote thousands of hours of computing power to test them. It takes millions or even billions times the work of 8-bit sboxes (where I am basing my start to fine tune). See this link for some properties: www2.imm.dtu.dk/~naah/f/… – Richie Frame Jul 3 '14 at 6:47
I can think of $\;$ Pros: simplicity; speed; no cache-induced timing dependency. $\;$ Cons: the outcome does not have all desirable S-box security properties so more rounds are needed, and its hard to tell if that's like two more or twice more rounds; multiplication is not constant-time on many architectures (e.g. low-end ARM). – fgrieu Jul 3 '14 at 7:45
This seems open to a timing attack... The duration of the computation may be linked to some secret data. – user1028028 Jul 3 '14 at 8:29

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.