8
$\begingroup$

While playing around with the AES SBOX, I found out that there are 85 unordered triplets (a, b, c) that have the following characteristics:

  • a ^ b ^ c = 0
  • SBOX[a] ^ SBOX[b] ^ SBOX[c] = SBOX[0]

Furthermore, the 85*3 = 255 values from the triplets cover the [1, 255] range, which is cute as zero was singled out on the other side of the equation.

Here is some python code that demonstrates this property:

SBOX = [
        99, 124, 119, 123, 242, 107, 111, 197,  48,   1, 103,  43, 254,
       215, 171, 118, 202, 130, 201, 125, 250,  89,  71, 240, 173, 212,
       162, 175, 156, 164, 114, 192, 183, 253, 147,  38,  54,  63, 247,
       204,  52, 165, 229, 241, 113, 216,  49,  21,   4, 199,  35, 195,
        24, 150,   5, 154,   7,  18, 128, 226, 235,  39, 178, 117,   9,
       131,  44,  26,  27, 110,  90, 160,  82,  59, 214, 179,  41, 227,
        47, 132,  83, 209,   0, 237,  32, 252, 177,  91, 106, 203, 190,
        57,  74,  76,  88, 207, 208, 239, 170, 251,  67,  77,  51, 133,
        69, 249,   2, 127,  80,  60, 159, 168,  81, 163,  64, 143, 146,
       157,  56, 245, 188, 182, 218,  33,  16, 255, 243, 210, 205,  12,
        19, 236,  95, 151,  68,  23, 196, 167, 126,  61, 100,  93,  25,
       115,  96, 129,  79, 220,  34,  42, 144, 136,  70, 238, 184,  20,
       222,  94,  11, 219, 224,  50,  58,  10,  73,   6,  36,  92, 194,
       211, 172,  98, 145, 149, 228, 121, 231, 200,  55, 109, 141, 213,
        78, 169, 108,  86, 244, 234, 101, 122, 174,   8, 186, 120,  37,
        46,  28, 166, 180, 198, 232, 221, 116,  31,  75, 189, 139, 138,
       112,  62, 181, 102,  72,   3, 246,  14,  97,  53,  87, 185, 134,
       193,  29, 158, 225, 248, 152,  17, 105, 217, 142, 148, 155,  30,
       135, 233, 206,  85,  40, 223, 140, 161, 137,  13, 191, 230,  66,
       104,  65, 153,  45,  15, 176,  84, 187,  22
       ]

triplets = [(0x01, 0xBC, 0xBD),
            (0x02, 0x61, 0x63),
            (0x03, 0xDC, 0xDF),
            (0x04, 0xC2, 0xC6),
            (0x05, 0x7A, 0x7F),
            (0x06, 0xA3, 0xA5),
            (0x07, 0x19, 0x1E),
            (0x08, 0x97, 0x9F),
            (0x09, 0x22, 0x2B),
            (0x0A, 0xF4, 0xFE),
            (0x0B, 0x43, 0x48),
            (0x0C, 0x51, 0x5D),
            (0x0D, 0xE0, 0xED),
            (0x0E, 0x32, 0x3C),
            (0x0F, 0x81, 0x8E),
            (0x10, 0x25, 0x35),
            (0x11, 0x89, 0x98),
            (0x12, 0x44, 0x56),
            (0x13, 0xEA, 0xF9),
            (0x14, 0xE7, 0xF3),
            (0x15, 0x4F, 0x5A),
            (0x16, 0x86, 0x90),
            (0x17, 0x2C, 0x3B),
            (0x18, 0xA2, 0xBA),
            (0x1A, 0xC1, 0xDB),
            (0x1B, 0x66, 0x7D),
            (0x1C, 0x64, 0x78),
            (0x1D, 0xC5, 0xD8),
            (0x1F, 0xA4, 0xBB),
            (0x20, 0x4A, 0x6A),
            (0x21, 0xD6, 0xF7),
            (0x23, 0x96, 0xB5),
            (0x24, 0x88, 0xAC),
            (0x26, 0xCF, 0xE9),
            (0x27, 0x54, 0x73),
            (0x28, 0xD5, 0xFD),
            (0x29, 0x41, 0x68),
            (0x2A, 0x9E, 0xB4),
            (0x2D, 0x87, 0xAA),
            (0x2E, 0x58, 0x76),
            (0x2F, 0xCB, 0xE4),
            (0x30, 0x5F, 0x6F),
            (0x31, 0xD2, 0xE3),
            (0x33, 0x80, 0xB3),
            (0x34, 0x99, 0xAD),
            (0x36, 0xCC, 0xFA),
            (0x37, 0x46, 0x71),
            (0x38, 0xC8, 0xF0),
            (0x39, 0x4D, 0x74),
            (0x3A, 0x91, 0xAB),
            (0x3D, 0x8F, 0xB2),
            (0x3E, 0x53, 0x6D),
            (0x3F, 0xD1, 0xEE),
            (0x40, 0x94, 0xD4),
            (0x42, 0xB7, 0xF5),
            (0x45, 0xAE, 0xEB),
            (0x47, 0x8A, 0xCD),
            (0x49, 0xB6, 0xFF),
            (0x4B, 0x9C, 0xD7),
            (0x4C, 0x85, 0xC9),
            (0x4E, 0xA8, 0xE6),
            (0x50, 0xB1, 0xE1),
            (0x52, 0x82, 0xD0),
            (0x55, 0x9B, 0xCE),
            (0x57, 0xAF, 0xF8),
            (0x59, 0x93, 0xCA),
            (0x5B, 0xA9, 0xF2),
            (0x5C, 0xB0, 0xEC),
            (0x5E, 0x8D, 0xD3),
            (0x60, 0xBE, 0xDE),
            (0x62, 0xBF, 0xDD),
            (0x65, 0xA1, 0xC4),
            (0x67, 0xA7, 0xC0),
            (0x69, 0x95, 0xFC),
            (0x6B, 0x9D, 0xF6),
            (0x6C, 0x83, 0xEF),
            (0x6E, 0x8C, 0xE2),
            (0x70, 0x8B, 0xFB),
            (0x72, 0x9A, 0xE8),
            (0x75, 0x84, 0xF1),
            (0x77, 0x92, 0xE5),
            (0x79, 0xA0, 0xD9),
            (0x7B, 0xB8, 0xC3),
            (0x7C, 0xA6, 0xDA),
            (0x7E, 0xB9, 0xC7),
            ]

for t in triplets:
  print("%02X ^ %02X ^ %02X" % t, "= %02X" % (t[0] ^ t[1] ^ t[2]), " |  SB[%02X] ^ SB[%02X] ^ SB[%02X]" % t, "= %02X" % (SBOX[t[0]] ^ SBOX[t[1]] ^ SBOX[t[2]]))

I am looking for any kind of explanation as to where this is coming from. I am familiar with AES but couldn't relate these observations to anything I know about it.

$\endgroup$
1
  • 3
    $\begingroup$ Well, it seems "too nice" to just be a random property. I suspect there is some mathematical explanation behind which I am not aware of, I am looking for it. $\endgroup$ – slv Apr 29 at 13:01
10
$\begingroup$

This is rather pretty if you understand finite fields and rather baffling if you don't. All the arithmetic takes place in $GF(256)$, so if you're not used to $1+1=0$, I apologise.

Conversion to pure $GF(256)$ arithmetic
Recall that the AES $S$-box can be written as $x\mapsto\ell(x^{254})$ where $x^{254}$ treats $x$ as an element of $GF(256)$ and $\ell$ is an invertible affine map. $x^{254}$ is some times termed the pseudo-inverse as for $x\neq 0$ we have $x^{254}=1/x$. By parity of operands, linearity and invertibility, we see that $$\ell(x)+\ell(y)+\ell(z)=\ell(0)\iff x+y+z=0.$$ It follows that $(a,b,c)$ form a triple if and only if both of the equations $$a+b+c=0$$ and $$\frac1a+\frac1b+\frac1c=0$$ hold with $a$, $b$ and $c$ distinct and non-zero.

Solving the simultaneous equations
Our first equation will hold iff $a+b=c$ and so we have a solution if and only if $$\frac1a+\frac1b+\frac1{a+b}=0$$ for distinct, non-zero $a$ and $b$. We multiply this equation by the non-zero quantity $ab(a+b)$ and see that we have a solution if and only $$a^2+ab+b^2=0$$ for distinct non-zero $a$ and $b$. Dividing through by $b^2$ we see that we have a solution if and only if $$\left(\frac ab\right)^2+\frac ab+1=0$$ which is true if and only if $a/b$ is a root of the equation $x^2+x+1$. This equation has two roots in $GF(256)$ as it is the defining polynomial of $GF(4)$ which is a subfield of $GF(256)$. In AES notation its roots are 0xBC and 0xBD (I'll write them as $\alpha$ and $\alpha+1$).

A recipe for triples
We can now construct all of our triples. Let $a$ be any non-zero element of $GF(256)$ (accounting for the appearance of all value in our list). Let $b=\alpha a$ and let $c=(\alpha+1) a$. We now have $$a+b+c=0$$ and $$S(a)+S(b)+S(c)=0.$$ Giving us a triple. This gives 255 solutions, but we have over counted by a factor of 3 as the process will find each triple three times. QED.

$\endgroup$
1
$\begingroup$

I ran some tests on random 8 bit permutation sboxes; I found (after running the count on 10,000 different random sboxes) that there were an average of 42.5 triples that meet the criteria (0 < a < b < c < 256, a^b^c=0, sbox[a]^sbox[b]^sbox[c]=sbox[0]).

Yes, there are a few more in the AES sbox; however not a huge amount...

$\endgroup$
2
  • $\begingroup$ 85 is twice the average of the random sbox case. $\endgroup$ – slv Apr 29 at 13:25
  • $\begingroup$ I would have expected a mean a little below 42.5 and standard deviation between 6 and 7 which would make 85 quite an outlier. $\endgroup$ – Daniel Shiu Apr 29 at 17:24
1
$\begingroup$

Here is a differential uniformity viewpoint.

We are actually talking about quadriples, and these are actually contributing to the values $\ge4$ in the DDT (Difference Distribution Table) (recall that the AES S-Box as the 8-bit field inverse is differentially 4-uniform). For APN (Almost Perfect Nonlinear) functions (differentially 2-uniform), you will not find such quadriples at all (this is in fact, an equivalent characterization).

For example, from $$S(x_1) \oplus S(x_1 \oplus \delta) = \Delta$$ $$S(x_2) \oplus S(x_2 \oplus \delta) = \Delta$$ You get a quadriple $$S(x_1) \oplus S(x_1 \oplus \delta) \oplus S(x_2) \oplus S(x_2 \oplus \delta) = 0$$ Note that any 4 values $a,b,c,d$ such that $a\oplus b \oplus c \oplus d=0$ can be expressed in form $x_1,x_1\oplus \delta, x_2, x_2\oplus \delta$ (i.e., form a 2-dimensional affine subspace).

Given that $\{x_1, x_1 \oplus \delta\} \ne \{x_2, x_2 \oplus \delta\}$, we have a differential transition $\delta \leadsto \Delta$ having at least 4 satisfying input values $(x_1, x_1 \oplus \delta, x_2, x_2 \oplus \delta)$.

$\endgroup$
3
  • 1
    $\begingroup$ I believe your answer (which I will need some time to process because I do not know all these notions) is actually very much related to how I ended up observing what I asked. I was playing with collisions in the first MixColumns output. While exploring, I noticed that certain key byte pair values where yielding more collisions than others, having me wonder what these had special about them. $\endgroup$ – slv Apr 29 at 22:03
  • $\begingroup$ @slv white-box/side-channel collision attacks? $\endgroup$ – Fractalice May 1 at 14:13
  • $\begingroup$ yes, indeed (stackexchange automatically retagged the question to "collision-resistance", not so appropriate as we are not in a hash context) $\endgroup$ – slv May 3 at 11:36

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.