# What is this AES SBOX triplet property?

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),
(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.

• 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. – slv Apr 29 at 13:01

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.

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

• 85 is twice the average of the random sbox case. – slv Apr 29 at 13:25
• 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. – Daniel Shiu Apr 29 at 17:24

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

• 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. – slv Apr 29 at 22:03
• @slv white-box/side-channel collision attacks? – Fractalice May 1 at 14:13
• yes, indeed (stackexchange automatically retagged the question to "collision-resistance", not so appropriate as we are not in a hash context) – slv May 3 at 11:36