Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 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 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 at 8:29

1 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.

share|improve this answer
    
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) –  user3029680 Jul 4 at 1:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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