Score:1

Crypto

How does this code calculating AES S-Box work?

Aktar1990

5/28/23, 9:23 AM

How does this code calculating the AES S-Box work? I don't understand the overall calculation procedure. Code is attached below:

function generate(irreducible_poly){
    try{
        p = parseInt(eval(irreducible_poly.replace(/x/g, '10')), 2);
    } catch(err){
        console.log('Irreducible Polynomial invalid');
        return;
    }

    let t = new Uint32Array(256);
    for (let i = 0, x = 1; i < 256; i ++) {
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * p);
    }

    let Sbox = new Uint32Array(256);
    Sbox[0] = 0x63;
    for (let i = 0; i < 255; i ++) {
        let x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        Sbox[t[i]] = (x ^ 0x63) & 0xFF;
    }

    return Sbox;
}


// Inverse of Sbox
function inverse(sbox){
    let InvSbox = new Uint32Array(256);
    for (let i =0; i < 256; i++){
        InvSbox[i] = sbox.indexOf(i);
    }

    return InvSbox;
}

236

0 + 0

s-boxes

aes

kelalaka

5/28/23, 9:38 AM

What is not clear? Did you try it by hand? Look at the examples on our site? Did you see this http://www.moserware.com/assets/stick-figure-guide-to-advanced/A%20Stick%20Figure%20Guide%20to%20the%20Advanced%20Encryption%20Standard%20%28AES%29.pdf

kelalaka

5/28/23, 10:30 AM

Does this answer your question? [How to do Hexadecimal multiplication in GF(2^8)](https://crypto.stackexchange.com/questions/63139/how-to-do-hexadecimal-multiplication-in-gf28). Possibly this question is a dupe of that, or [How are these AES MixColumn multiplication tables calculated?](https://crypto.stackexchange.com/q/71204/18298). Could you indicate that those solved your confussion?

kelalaka

5/28/23, 1:12 PM

Where did you get this code? Well, one might have seen this code, however, could you [edit](https://crypto.stackexchange.com/posts/98396/edit) your question to indicate where did you get this and even link to the paper? https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture8.pdf

Aktar1990

5/31/23, 2:08 PM

https://merricx.github.io/aes-sbox/

Aktar1990

6/1/23, 8:32 AM

you should inspect the elements to find the code

Ilmari Karonen

6/1/23, 10:35 PM

Hope you're not feeding untrusted input to that `generate` function. ;) I suppose it's not that bad as long as the code only runs on the client side, since all you can compromise with it is the browser's JS sandbox, which the user of the browser has full control over anyway with dev tools. If that was a server-side script, though…

Score:2

Crypto

fgrieu

5/31/23, 4:36 PM

Big picture: this code needs to compute the inverse modulo binary irreducible polynomial $P$ of every non-zero binary polynomial $R$ of degree less than that of $P$. Towards this, it has selected a generating polynomial $G=1+x$, and tabulates $Q_i=G^i\bmod P$, which reaches all the desired $R$. The multiplicative inverse of $R=Q_i$ is $Q_{255-i}$.

This code evaluates the AES S-box and it's inverse as follows:

(code block starting in try) It evaluates p = 0x11b = 283 that represents the binary polynomial $P=1+x+x^3+x^4+x^8$ as an integer: the value obtained when evaluating this polynomial for integer $x=2$. This common convention is used in AES to map binary polynomials to integers.
(code block starting in let t) It computes table t[i] representing the binary polynomial $Q_i=(1+x)^i\bmod P$ per this convention. That $Q_i$ is computed per the recurrence $Q_{i+1}=Q_i\,(1+x)\bmod P$ with $Q_0=1$, translating¹ to t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) with t[0] = 1 under said convention.

For example: $Q_0$ is the (binary) polynomial $1$, represented by t[0] = 1. $Q_1=1+x$, represented by t[1] = 3. $Q_2=(1+x)^2=1+x^2$, represented by t[2] = 5. $Q_7=(1+x)^7=1+x+x^2+x^3+x^4+x^5+x^6+x^7$, represented by t[2] = 0xff = 255. $Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4$, represented by t[8] = 0x1a = 26.
(code block starting in let Sbox) Tabulating $Q_i=(1+x)^i\bmod P$ was useful because $(1+x)^{255}\bmod P=1$, therefore $Q_{255-i}$ is the multiplicative inverse of $Q_i$. And $Q_i$ reaches all non-zero binary polynomials of degree $<8$ (that is $1+x$ is a generator). Therefore integer t[255 - i] represents the multiplicative inverse of the polynomial that integer t[i] represents. And when in the loop i goes from 0 to 254 that yields the multiplicative inverse of each of the 255 non-zero polynomials of degree $<8$. The loop then merely applies² the affine transformation specified in the rest of the definition of the AES S-box. The zero polynomial is special-cased.

For example: when in the loop i = 8, t[i] is t[8] = 0x1a = 26 representing $Q_8=x+x^3+x^4$, and t[255-i] (going to x, unrelated to $x$) is t[247] = 0xfd = 253 representing the polynomial $Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7$. That $Q_{247}$ is the multiplicative inverse of $Q_8$. By the definition of the AES S-box, there only remains to apply the affine transformation² to x, then set the result in Sbox[t[i]] = Sbox[26].
(function inverse) The inverse table is computed by searching each entry in the table. That works but is inefficient. InvSbox[i] = sbox.indexOf(i); could be replaced by the straightforward and more efficient InvSbox[sbox[i]] = i;.

¹ Justification: in t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))

t[i] is an integer in $[0,2^8)$ and represents $Q_i$ of degree $<8$
t[i] << 1 is an even integer in $[0,2^9)$ and represents $Q_i\,x$.
t[i] >>> 7 is either 0 or 1. It's the coefficient of the term of order $x^7$ in $Q_i$.
(t[i] >>> 7) * p is correspondingly either 0 or 0x11b = 283, representing $0$ or $P$.
(t[i] << 1) ^ ((t[i] >>> 7) * p) correspondingly represents $(Q_i\,x)$ or $(Q_i\,x)+P$, and (by examination of the two cases) is an integer in $[0,2^8)$, thus represents a binary polynomial of degree $<8$, which thus is $(Q_i\,x)\bmod P$.
t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) is thus an integer in $[0,2^8)$ and represents $Q_i+(Q_i\,x)\bmod P)=Q_i\,(1+x)\bmod P=Q_{i+1}$, of degree $<8$.

In C, the standard likely-constant-time idiom for this expression would be (essentially with & - used instead of multiplication):
t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7))).
Note: some overzealous C compilers will wrongly bark at the -, silence them.

² The statement x |= x << 8;duplicates the bits in variable x (representing the modular inverse of $Q_i$) so that subsequent right shifts become equivalent to rotation when it comes to the low-order 8 bits. The statement x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7); implements the circulant matrix multiplication. Then ^ 0x63 (representing polynomial $1+x+x^5+x^6$) is the constant addition, and & 0xFF keeps the low-order 8 bits (terms of degree $<8$), undoing the duplication.

0 + 0

poncho

5/31/23, 4:42 PM

$1+x$ is specifically used because $(1+x)^i \bmod P$ reaches all values (other than 0) for $i$ between 0 and 254; the technical term we use for this is that $1+x$ is a "generator" of this field (while the simpler term $x$ is not)

Aktar1990

6/1/23, 8:31 AM

so could you pleased explain it in your own way?? i need this algorithm for my thesis work. Actually I understand which part for what calculation, but it would be better for me if you explained it with one example rather then equation. Also; Sbox[t[i]] = (x ^ 0x63) & 0xFF; why FF used here could you pleased explain???

fgrieu

6/1/23, 6:12 PM

@Aktar1990: I added numerical examples, as well as note 2 explaining the affine transformation, including the `(x ^ 0x63) & 0xFF`. For the `Sbox[t[i]]`, it's explained in "3.".

Aktar1990

6/1/23, 6:17 PM

@fgrieu Do you have any complete coding for this AES S-Box with better explanation. I just want coding from you ,when i run it ,i get the output??do you have??do you know the time complexity and space complexity of AES S-Box??

fgrieu

6/1/23, 6:25 PM

@Aktar1990: you chose this code and it's language. I have no better explanation of it, or code with similarly low time and space complexity: `generate` is reasonably close to optimal in the language at hand. Efficient code uses polynomial math and coding techniques that take some time and effort to grasp. But since you are on a related thesis, you should be capable of that.

Aktar1990

6/2/23, 2:31 AM