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

Improve this question
$\endgroup$
4
  • $\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$
    – crypt
    Commented Aug 28, 2017 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
    Commented Sep 6, 2017 at 16:59
  • $\begingroup$ see Annex A (page 17) of this paper eprint.iacr.org/2002/044.pdf $\endgroup$
    – crypt
    Commented Sep 7, 2017 at 13:23
  • $\begingroup$ Take the identity permutation! $\endgroup$
    – hola
    Commented Sep 30, 2018 at 18:08

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.