2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Thomas Jul 3 '14 at 5:30
  • $\begingroup$ 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/… $\endgroup$ – Richie Frame Jul 3 '14 at 6:47
  • $\begingroup$ 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). $\endgroup$ – fgrieu Jul 3 '14 at 7:45
  • $\begingroup$ This seems open to a timing attack... The duration of the computation may be linked to some secret data. $\endgroup$ – user1028028 Jul 3 '14 at 8:29
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Quick meta: OP, Peter Butler, was thought to be logged in via Google. @Dmitry Khovratovich *Why: mostly asking if good idea *Properties: simple; good bit scramble; no table = no cache timing issues; could use different s boxes in different rounds plus smaller code footprint *Confession: no consideration given to resistance to cryptanalysis (it’s important, don’t know how) $\endgroup$ – user3029680 Jul 4 '14 at 1:58
0
$\begingroup$

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

io1

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

io2

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

wmr

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.