# How can one construct the weakest S-box ever?

Is it possible to come up with an NxN S-box which would have a difference distribution table with N entries of 100% probability?

I am studying the properties of S-boxes and I don't quite understand how a poorly designed S-box can destroy all the cipher's security.

For example, if one replaces the AES-256's S-box table with such an S-box I described above, would he/she be able to crack the cipher with some known plaintext/cipherext pairs?

EDIT:

Here is a variation of the most useless S-box:

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


But I cannot figure out by what rule it was constructed.

• The above mentioned Sbox has a non-lineraity of 0 and its DDT shows that an input difference of 0x01 produces a output difference of 0x8A with a probability of 254/256, which is very high, almost linear. In best case scenario from attacker point of view, 10 rounds of AES produce a minimum of 55 Active Sboxes, which will reduce the probability to 2^-6 only. So breaking AES with this SBox will be an easy task. And If algebraic relation of Sbox can be found, it may make it easy to break the cipher using algebraic equations. – khan Aug 28 '17 at 5:55
• @Raza Thank you for the answer! Indeed I managed to find the algebraic relation of the Sbox. Could you provide me with an example how the algebraic equation would look like in case of AES? – JoaoAlby Sep 6 '17 at 16:59
• see Annex A (page 17) of this paper eprint.iacr.org/2002/044.pdf – khan Sep 7 '17 at 13:23
• Take the identity permutation! – pushpen.paul Sep 30 '18 at 18:08

Any affine function will do. Let your Sbox be $$S(x)=Mx\oplus c$$ where $M$ is an $n\times n$ binary matrix and $c$ is an $n-$bit constant vector.
The output difference for this Sbox is, for any nonzero $a$ $$S(x \oplus a)\oplus S(x)=(M(x\oplus a)\oplus c )\oplus Mx\oplus c= M a\oplus c$$ which is a constant for fixed $a$ so all the output differences for that input difference take on the same value.
For nontriviality pick either $c$ nonzero or $M$ a non identity matrix. The matrix must be invertible (over $GF(2)$) for the Sbox to be invertible, i.e., a proper substitution.