6
$\begingroup$

I was examining the S-Boxes of the Kalyna Cipher and found that 3 of the 4 S-boxes have reverse fixed points i.e S[x] = (255 - x). Is this an exploitable weakness? I was not able to find any open literature on how these S-Boxes were generated except for:

S-boxes for 'Kalyna' were selected from the set of randomly generated permutations (random sequences for generation were taken from hardware-based generator).

+-------------------------+------------+------------+----------+----------+
|                         |     π0     |     π1     |    π2    |    π3    |
+-------------------------+------------+------------+----------+----------+
| NonLinearity            |        104 |        104 |      104 |      104 |
| Differential Uniformity |          8 |          8 |        8 |        8 |
| Absolute Indicator      |         72 |         72 |       72 |       72 |
| Distance To SAC         |        456 |        496 |      508 |      512 |
| Algebraic Degree        |          7 |          7 |        7 |        7 |
| Fixed Points            |          0 |          0 |        0 |        0 |
| Reverse Fixed Points    |   2(45,152)|          0 |     1(46)|2(129,132)|
| SumOfSquaresIndicator   |     200320 |     199936 |   203008 |   206464 |
| SNRDPA                  | 10.1132412 |   7.658872 | 9.398253 | 9.208378 |
| Transparency            |   7.834804 | 7.81397057 | 7.820098 | 7.823284 |
+-------------------------+------------+------------+----------+----------+

I was able to observe the following: Kalyna S Box - Pi 1 (Non-Linearity : 104, Differential Uniformity: 8)

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

After swapping 41 Elements given by ()

New S Box (Non-Linearity : 112, Differential Uniformity: 4)

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

Is it possible that this S-box was generated by randomly swapping elements from an initial S-box that was made the same way as an AES S-box?

$\endgroup$
  • 1
    $\begingroup$ S[x] = 255 - S[x] doesn't make any sense; perhaps you mean S[x] = 255 - x ? $\endgroup$ – poncho Aug 2 '16 at 13:06
  • $\begingroup$ @poncho. yes you are correct. its a typo $\endgroup$ – vinu Aug 3 '16 at 16:13
  • $\begingroup$ The Kuznyechik s-box was claimed to be selected from random too, but has been reverse engineered.. Granted that's a different cipher, but the claim of generating an s-box randomly would appear to deserve scrutiny, especially in light of your observation of it appearing to be a modification of the AES s-box. Also, I would think S[x] = 255 - x admits a simple algebraic description for the points in question; I have no idea if that is exploitable, unfortunately. Wish I had more then +1 to give... $\endgroup$ – Ella Rose Aug 3 '16 at 16:55
  • $\begingroup$ how many reverse fixed points did they have? $\endgroup$ – kodlu Aug 3 '16 at 23:23
  • $\begingroup$ How did you find the algebraic properties (non-linearity etc.)? $\endgroup$ – xxx--- Feb 19 '17 at 3:34
4
$\begingroup$

If you take a look at the discussion at http://eprint.iacr.org/forum/read.php?16,947 one of the authors of Kalyna, Oleksandr Kazymyrov, states that the S-boxes were generated randomly according to the paper A Method For Generation Of High-Nonlinear S-Boxes Based On Gradient Descent:

The generation method of substitutions was described in [eprint.iacr.org]. All parameters were taken randomly, except $x^{-1}$.

$\endgroup$
  • $\begingroup$ Nice! Welcome to crypto, oink. $\endgroup$ – Maarten - reinstate Monica Aug 4 '16 at 11:33
  • $\begingroup$ you might be right about choosing f(x) = x^-1, since the distribution of Coefficients of Linear Approximation Table and Difference Distribution table of the 4 Parent S-Boxes are same as that of AES S Box $\endgroup$ – vinu Aug 4 '16 at 13:10
2
$\begingroup$

I was able to find Parent S-Boxes For other Kalyna S-Boxes (using a C# program i created for the same).

Parent S-Box For π1

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

Parent S-Box For π2

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

Parent S-Box For π3

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

So i think it is fair to conclude that these S-Boxes were created by swapping elements (to remove any linear redundancy) from S-Boxes generated using power mappings in Galois Field.

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