19
\$\begingroup\$

Rijndael's S-box is a frequently used operation in AES encryption and decryption. It is typically implemented as a 256-byte lookup table. That's fast, but means you need to enumerate a 256-byte lookup table in your code. I bet someone in this crowd could do it with less code, given the underlying mathematical structure.

Write a function in your favorite language that implements Rijndael's S-box. Shortest code wins.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Bonus points (upvotes from me) if the resulting function is constant-time (i.e. no data-dependent code paths or array accesses or whatever your language supports). \$\endgroup\$ Oct 4, 2011 at 8:08
  • 1
    \$\begingroup\$ @PaŭloEbermann array accesses are constant time in many languages (it's adding a (scaled) value to a pointer and dereferencing it, this is why a lookup table is so very fast) \$\endgroup\$ Oct 4, 2011 at 8:58
  • \$\begingroup\$ @ratchetfreak Array accesses are O(1), but the actual access time depends on cache hits or misses, for example, which leads to side-channel attacks on AES. \$\endgroup\$ Oct 4, 2011 at 9:01
  • \$\begingroup\$ @PaŭloEbermann, but you can use the shorter code to fill a lookup table, which will then fit in well under a page of memory. \$\endgroup\$ Oct 4, 2011 at 9:32
  • \$\begingroup\$ @PaŭloEbermann and if the 256-length table is stored along the code (as enum generated at compile time) you nearly guaranteed a cache hit \$\endgroup\$ Oct 4, 2011 at 9:35

9 Answers 9

10
\$\begingroup\$

x86-64 Machine code - 23 22 20 19 bytes

Uses the AES-NI instruction set

66 0F 6E C1          movd        xmm0,ecx
66 0F 38 DD C1       aesenclast  xmm0,xmm1
0F 57 C1             xorps       xmm0,xmm1  
66 0F 3A 14 C0 00    pextrb      eax,xmm0,0
C3                   ret

Using Windows calling conventions, takes in a byte and outputs a byte. It is not necessary to reverse the ShiftRows as it does not affect the first byte.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ For once, x86_64 pulls a mathematica, and has a builtin for that. \$\endgroup\$ Jul 10, 2019 at 5:55
8
\$\begingroup\$

GolfScript, 60 characters

{[[0 1{.283{1$2*.255>@*^}:r~^}255*].@?~)={257r}4*99]{^}*}:S;

This code defines a function named S that takes in a byte and applies the Rijndael S-box to it. (It also uses an internal helper function named r to save a few chars.)

This implementation uses a logarithm table to compute the GF(28) inverses, as suggested by Thomas Pornin. To save a few chars, the whole logarithm table is recalculated for each input byte; even so, and despite GolfScript being a very slow language in general, this code takes only about 10 ms to process a byte on my old laptop. Precalculating the logarithm table (as L) speeds it up to about 0.5 ms per byte, at the modest cost of three more chars:

[0 1{.283{1$2*.255>@*^}:r~^}255*]:L;{[L?~)L={257r}4*99]{^}*}:S;

For convenience, here's a simple test harness that calls the function S, as defined above, to compute and print out the whole S-box in hex like on Wikipedia:

"0123456789abcdef"1/:h; 256, {S .16/h= \16%h= " "++ }% 16/ n*

Try this code online.

(The online demo precalculates the logarithm table to avoid taking too much time. Even so, the online GolfScript site may sometimes randomly time out; this is a known issue with the site, and a reload usually fixes it.)

Explanation:

Let's start with the logarithm table calculation, and specifically with the helper function r:

{1$2*.255>@*^}:r

This function takes two inputs on the stack: a byte and a reduction bitmask (a constant between 256 and 511). It duplicates the input byte, multiplies the copy by 2 and, if the result exceeds 255, XORs it with the bitmask to bring it back under 256.

Within the log-table generating code, the function r is called with the reduction bitmask 283 = 0x11b (which corresponds to the Rijndael GF(28) reduction polynomial x8 + x4 + x3 + x + 1), and result is XORed with the original byte, effectively multiplying it by 3 (= x + 1, as a polynomial) in the Rijndael finite field. This multiplication is repeated 255 times, starting from the byte 1, and the results (plus an initial zero byte) are collected into a 257-element array L that looks like this (middle part omitted):

[0 1 3 5 15 17 51 85 255 26 46 ... 180 199 82 246 1]

The reason why there are 257 elements is that, with the prepended 0 and with 1 occurring twice, we can find the modular inverse of any given byte simply by looking up its (zero-based) index in this array, negating it, and looking up the byte at the negated index in the same array. (In GolfScript, as in many other programming languages, negative array indexes count backwards from the end of the array.) Indeed, this is exactly what the code L?~)L= at the beginning of the function S does.

The rest of the code calls the helper function r four times with the reduction bitmask 257 = 28 + 1 to create four bit-rotated copies of the inverted input byte. These are all collected into an array, together with the constant 99 = 0x63, and XORed together to produce the final output.

\$\endgroup\$
6
\$\begingroup\$

Ruby, 161 characters

R=0..255
S=R.map{|t|t=b=R.select{|y|x=t;z=0;8.times{z^=y*(x&1);x/=2;y*=2};r=283<<8;8.times{r/=2;z^r<z/2&&z^=r};z==1}[0]||0;4.times{|r|t^=b<<1+r^b>>4+r};t&255^99}

In order to check the output you can use the following code to print it in tabular form:

S.map{|x|"%02x"%x}.each_slice(16){|l|puts l*' '}
\$\endgroup\$
6
\$\begingroup\$

The table can be generated without computing inverses in the finite field GF(256), by using logarithms. It would look like this (Java code, using int to avoid problems with the signed byte type):

int[] t = new int[256];
for (int i = 0, x = 1; i < 256; i ++) {
    t[i] = x;
    x ^= (x << 1) ^ ((x >>> 7) * 0x11B);
}
int[] S = new int[256];
S[0] = 0x63;
for (int i = 0; i < 255; i ++) {
    int x = t[255 - i];
    x |= x << 8;
    x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
    S[t[i]] = (x ^ 0x63) & 0xFF;
}

The idea is that 3 is a multiplicative generator of GF(256)*. The table t[] is such that t[x] is equal to 3x; since 3255 = 1, we get that 1/(3x) = 3255-x.

\$\endgroup\$
6
  • \$\begingroup\$ shouldn't it be 0x1B (one 1 in the hex literal) instead of 0x11B \$\endgroup\$ Oct 4, 2011 at 12:31
  • \$\begingroup\$ @ratchetfreak: no, it must be 0x11B (I tried). The int type is 32-bit in Java; I must cancel out the higher bit. \$\endgroup\$ Oct 4, 2011 at 12:36
  • \$\begingroup\$ ah didn't realize that \$\endgroup\$ Oct 4, 2011 at 12:47
  • \$\begingroup\$ Is that a >>> instead of a >> in line 4? \$\endgroup\$
    – Joe Z.
    Jan 22, 2013 at 17:22
  • \$\begingroup\$ @JoeZeng: both would work. In Java, '>>>' is the "unsigned shift", '>>' is the "signed shift". They differ by how they handle the sign bit. Here, the values will never be wide enough for the sign bit to be non-zero, so it makes no real difference. \$\endgroup\$ Jan 22, 2013 at 17:39
6
\$\begingroup\$

GolfScript (82 chars)

{256:B,{0\2${@1$3$1&*^@2/@2*.B/283*^}8*;;1=},\+0=B)*:A.2*^4A*^8A*^128/A^99^B(&}:S;

Uses global variables A and B, and creates the function as global variable S.

The Galois inversion is brute-force; I experimented with having a separate mul function which could be reused for the post-inversion affine transform, but it turned out to be more expensive because of the different overflow behaviour.

This is too slow for an online demo - it would time out even on the first two rows of the table.

\$\endgroup\$
1
  • \$\begingroup\$ Mine's faster (and shorter ;). +1 anyway, though. \$\endgroup\$ Apr 8, 2015 at 23:15
4
\$\begingroup\$

Python, 176 chars

This answer is for Paŭlo Ebermann's comment-question about making the function constant time. This code fits the bill.

def S(x):
 i=0
 for y in range(256):
  p,a,b=0,x,y
  for j in range(8):p^=b%2*a;a*=2;a^=a/256*283;b/=2
  m=(p^1)-1>>8;i=y&m|i&~m
 i|=i*256;return(i^i/16^i/32^i/64^i/128^99)&255
\$\endgroup\$
2
  • \$\begingroup\$ Multiplication being constant-time is platform dependent (even on 32-bit platforms, e.g. ARM Cortex M0). See this related question \$\endgroup\$
    – fgrieu
    Mar 6, 2015 at 13:46
  • 1
    \$\begingroup\$ @fgrieu Sure, but these are all multiplications by constants, which can be easily implemented in constant time using shifts and adds. \$\endgroup\$ Mar 6, 2015 at 19:55
2
\$\begingroup\$

d

ubyte[256] getLookup(){

    ubyte[256] t=void;
    foreach(i;0..256){
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * 0x1B);
    }
    ubyte[256] S=void;
    S[0] = 0x63;
    foreach(i;0..255){
        int x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        S[t[i]] = cast(ubyte)(x & 0xFF) ^ 0x63 ;
    }
    return S;

}

this can generate the lookup table at compile time, I could save some by making ubyte a generic param

edit direct ubyte to ubyte without array lookups, no branching and fully unrollable loops

B[256] S(B:ubyte)(B i){
    B mulInv(B x){
        B r;
        foreach(i;0..256){
            B p=0,h,a=i,b=x;
            foreach(c;0..8){
                p^=(b&1)*a;
                h=a>>>7;
                a<<=1;
                a^=h*0x1b;//h is 0 or 1
                b>>=1;
            }
            if(p==1)r=i;//happens 1 or less times over 256 iterations
        }
        return r;
    }
    B s= x=mulInv(i);
    foreach(j,0..4){
        x^=(s=s<<1|(s>>>7));
    }
    return x^99;
}

edit2 used @Thomas' algo for creating the lookup table

\$\endgroup\$
2
\$\begingroup\$

Stax, 53 bytes

ë■ÿÆ♂◄º5hUø√!«mr¿¡ƒR3Å←ç≥#/$taJkαn∩╓▒ÿ╔τy╫π§╪S♫╔┴H╔║Ö

Run and debug it

I have no particular understanding of S-boxes. This is a conversion of Thomas Pornin's (8 year old!) solution.

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 70 bytes

⎕⊃99,1↓(2⊥¨(⊂b⊤99)≠≠⌿(⍳5)∘.⌽⌽p)[⍋2⊥¨p←{(2≠/⍵,0)≠b⊤27×⊃⍵}\,b⍴⊂1⊤⍨b←8⍴2]

Try it online!

\$\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.