2
$\begingroup$

I generated this single-cycle substitution box and I want to post it as an example for understanding what a good S-box would be like. I get the feeling that this particular one is weak. Here it is (upper four bits of input are matched with the row and the lower four bits are match with the column:

AC 17 FB CB 60 93 35 50 F7 83 DF B3 8B 66 25 05
9B 16 0E 96 04 2A 95 62 FD 43 BE 37 4D 38 D9 07
E7 9C 80 3F D2 8E BA 1E 2F 36 F4 2E 2B AF A8 5A
9E 4C C0 19 82 3B 30 E9 4E DE 01 C8 15 8D 20 0B
39 CA E6 D0 F6 E3 57 D6 A3 1B 03 69 81 CE 22 AD
31 5E 57 34 70 A8 68 09 F2 B9 EA 6A 02 3E 21 78
C6 86 2C 85 6F D3 5C 2D 24 FF 92 D4 CF 18 4F B7
C5 12 FE 51 B1 B4 1C A1 97 40 C4 2F 47 F1 0A DA
F3 A2 8A 29 EE 10 32 F0 3D 48 D7 E8 6D A4 26 DC
B8 FC 91 DB A7 49 0C 5B 9F 13 F8 76 6C 11 73 58
B0 67 CD 88 44 27 75 D5 FA 8C 58 AE 14 7F 0F BB
B5 B6 46 E2 89 A6 63 08 E1 5F 1F 9D F9 98 64 79
4B 1A 42 AC D1 59 61 41 87 EB 77 A0 C2 DD CC 74
45 7D B2 8F C1 E5 99 C7 7E 3A 7B E4 F9 6E A5 7A
1D 53 56 ED 0D EC C9 71 C3 65 AB 06 EF 3C A7 5D
E0 7C 90 9A D8 06 23 A9 54 33 4A BF BD 72 84 6B

I'm noticing several things:

  • There are a few places where the upper four bits of the output match the upper four bits of the byte right above or below it in the table. There are also ones where it is the lower four bits that match.
  • There are a few places where the output's lower four bits match the lower four bits of the output to the left or right of it in the table. Same goes for the upper four bits.

I'm not well-versed in the art of S-box construction, but I'm getting the feeling that this one is a poor one.

What I'd like to know is: what rule for a good S-box is this one violating here and how it relates to non-linearity and all that?

Update #1

Richie Frame has pointed out that the S-box above is not bijective. Here is the correct one:

AC 17 FB CB 60 93 35 50 F7 83 DF B3 8B 66 25 05
9B 16 0E 96 04 2A 95 62 FD 43 BE 37 4D 38 D9 07
E7 9C 80 3F D2 8E BA 1E 2F 36 F4 2E 2B AF 55 5A
9E 4C C0 19 82 3B 30 E9 4E DE 01 C8 15 8D 20 0B
39 CA E6 D0 F6 E3 52 D6 A3 1B 03 69 81 CE 22 AD
31 5E 57 34 70 A8 68 09 F2 B9 EA 6A 02 3E 21 78
C6 86 2C 85 6F D3 5C 2D 24 FF 92 D4 CF 18 4F B7
C5 12 FE 51 B1 B4 1C A1 97 40 C4 28 47 F1 0A DA
F3 A2 8A 29 EE 10 32 F0 3D 48 D7 E8 6D A4 26 DC
B8 FC 91 DB A7 49 0C 5B 9F 13 F8 76 6C 11 73 AA
B0 67 CD 88 44 27 75 D5 FA 8C 58 AE 14 7F 0F BB
B5 B6 46 E2 89 A6 63 08 E1 5F 1F 9D F9 98 64 79
4B 1A 42 00 D1 59 61 41 87 EB 77 A0 C2 DD CC 74
45 7D B2 8F C1 E5 99 C7 7E 3A 7B E4 BC 6E A5 7A
1D 53 56 ED 0D EC C9 71 C3 65 AB F5 EF 3C 94 5D
E0 7C 90 9A D8 06 23 A9 54 33 4A BF BD 72 84 6B

It still has the same problems I noted before.

|improve this question
$\endgroup$
4
$\begingroup$

I have a software tool for analyzing basic differential and linear properties of s-boxes.

Submitting your s-box to my tool yields the following output:

The most probable differential characteristic(s):

1 -> 215 with probability 10/256 (xor -> xor) (weight 1 -> 6)

Linearity: 18.0 ((166, 166))

Differential probability

So we can see that the most likely difference is that a difference of 1 will output a difference of 215 with probability 10/256. The type of difference used was xor, it is possible to use other functions such as addition to attempt to find other differentials. A probability 10/256 differential is not horrible, but it could be better; For reference, the AES s-box has a max differential probability of 4/256.

Linearity

Linear cryptanalysis is analogous to differential cryptanalysis, but to many it may slightly more complex to reason about. The "linearity" value shows the distance to the nearest linear function. The more closely that the s-box approximates a linear function, the more easily it can be attacked. Again, the value for the s-box you presented is moderately good, but is again not as good as the AES s-box, which has a linearity value of 16.0.

Further Understanding

For a true understanding of the above, I recommend this resource for studying differential and linear cryptanalysis. It is a relatively gentle introduction compared to an actual paper on the subject. I developed my software for analyzing s-boxes while following these tutorials.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Note: This answer assumes that you are presenting a regular 8-bit s-box. The upper bits and lower bits stuff in you question makes me wonder if you have multiple 4x4 s-boxes or are doing anything other then substituting 8 contiguous bits... $\endgroup$ – Ella Rose♦ Nov 18 '17 at 18:32
  • $\begingroup$ It is an S-box derived using sixteen iterations of an ARX-based pseudorandom permutation used in the way to make a single-cycle permutation that poncho describes here. $\endgroup$ – Melab Nov 19 '17 at 1:43
  • $\begingroup$ Is a differential probability of one over two hundred fifty-six achievable? Is this the only metric that matters? $\endgroup$ – Melab Nov 19 '17 at 1:44
  • $\begingroup$ @Melab I think the theoretically ideal differential probability for an 8-bit s-box is 2/256. These are not the only metrics that matter, these are only the basics. There are other aspects such branch count and circuit depth/complexity. A paper like this might help you find some other qualities to look for. $\endgroup$ – Ella Rose♦ Nov 19 '17 at 2:07
  • 1
    $\begingroup$ @RichieFrame thank you for double checking, guess I need to fix the LAT part of my script (and add checks for bijective-ness) $\endgroup$ – Ella Rose♦ Nov 19 '17 at 16:13
2
$\begingroup$

You have multiple issues with that s-box which means the software Ella Rose is using is producing incorrect results.

The Differential Uniformity is indeed 10, but the Nonlineary is only 93, which is a linearity of 35. You also have an AutoCorrelation of 100 and SSI of 283888, both of which are higher than optimal.

The problem is you do not have a bijective s-box, some elements are missing, some are duplicated.

Your s-box is missing: 0x00, 0x28, 0x52, 0x55, 0x94, 0xAA, 0xBC, 0xF5

It also has 2 of the following: 0x06, 0x2F, 0x57, 0x58, 0xA7, 0xA8, 0xAC, 0xF9

This is what I consider a "good" s-box based on finite field inversion, it is one of the best I was able to generate within the confines of fast algorithmic generation:

A2 B8 4F 8C 29 EC 68 82 CD D9 EB 1D D0 CF A9 36
41 BF 57 72 65 E1 23 AE A3 37 3C 84 2F CC A8 9E
39 25 03 1B 07 2E DA 70 90 FB D3 CE 5F 6D E8 EF
5A 83 4E 58 99 3B 66 C3 24 6C 86 BE 62 64 F8 A5
02 B4 97 63 E6 F7 BD 04 E9 D7 8B A0 94 67 1C D8
2C 27 76 34 13 1E 0C 79 19 52 C5 9A AD 00 74 15
05 89 8A 11 D1 DE 54 18 DD 1F 4D 61 6E 9C C8 B7
FC 43 FD C9 4B 7E EE 28 C1 3A 7B 53 31 5E C7 C2
0E 5D 80 40 5B 95 75 9D B3 FA 30 77 44 92 F0 14
46 AB 6A E2 AF 2A 1A 59 AA E4 DF BC 48 42 51 71
A4 F4 98 0A EA A7 06 F6 9B 3D 35 0F 0B 2D 7A 21
C0 22 CB 45 D5 8D F1 78 D4 3F 26 DB D6 AC F5 91
60 87 81 E7 01 3E 2B BA F3 7D A6 09 8F E5 20 8E
32 FF 49 5C B6 E0 BB 69 33 9F DC ED 73 4A B1 0D
4C D2 FE 96 16 B2 7C B5 56 CA B0 6B 50 E3 A1 C6
F9 08 85 B9 47 C4 38 12 93 6F 88 7F 55 10 17 F2
|improve this answer
$\endgroup$
  • $\begingroup$ It's not bijective? WTF? I was sure that it was. I reversed the ARX operations and everything. $\endgroup$ – Melab Nov 19 '17 at 17:10
  • $\begingroup$ Does the generation run in constant time? $\endgroup$ – Melab Nov 19 '17 at 17:47
  • $\begingroup$ I have since updated the S-box. $\endgroup$ – Melab Nov 19 '17 at 18:59
  • $\begingroup$ I see similar patterns in your S-box. $\endgroup$ – Melab Nov 19 '17 at 19:01
  • $\begingroup$ @Aleph mine is an APA s-box and not generated using the same polynomial, and is not in the same affine equivalence class $\endgroup$ – Richie Frame Nov 20 '17 at 10:30

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.