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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ S[x] = 255 - S[x] doesn't make any sense; perhaps you mean S[x] = 255 - x ? $\endgroup$
    – poncho
    Aug 2, 2016 at 13:06
  • $\begingroup$ @poncho. yes you are correct. its a typo $\endgroup$
    – vinu
    Aug 3, 2016 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, 2016 at 16:55
  • $\begingroup$ how many reverse fixed points did they have? $\endgroup$
    – kodlu
    Aug 3, 2016 at 23:23
  • $\begingroup$ How did you find the algebraic properties (non-linearity etc.)? $\endgroup$
    – hola
    Feb 19, 2017 at 3:34

2 Answers 2

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice! Welcome to crypto, oink. $\endgroup$
    – Maarten Bodewes ♦
    Aug 4, 2016 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, 2016 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.

Improve this answer
$\endgroup$

Your Answer

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

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