3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – khan Aug 28 '17 at 5:55
  • $\begingroup$ @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? $\endgroup$ – JoaoAlby Sep 6 '17 at 16:59
  • $\begingroup$ see Annex A (page 17) of this paper eprint.iacr.org/2002/044.pdf $\endgroup$ – khan Sep 7 '17 at 13:23
  • $\begingroup$ Take the identity permutation! $\endgroup$ – pushpen.paul Sep 30 '18 at 18:08
6
$\begingroup$

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.

AES with this type of Sbox can be trivially broken.

Edit: See the answer to this question for details.

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