Description

Block cipher “Kuznyechik” (Grasshopper) is defined in the National Standard of the Russian Federation GOST R 34.12-2015 (effective date 01.01.2016). It has 128 bit block and 256 bit key. This code builds upper bound estimates of its practical resistance to integer differential cryptanalysis. This cryptanalytic method first appeared in works of Biham and Shamir: input and output differences were taken regarding XOR operation. Integer differentials modulo $2^{32}$ were first introduced by Thomas A. Berson. The “integer” modification is quite new, so when many ciphers were designed they were not tested for resistance to it.

This cipher is based on SPN (Substitution-permutation network). It has 10 rounds, of which first 9 rounds have round-function in the form: $F(x,k)=P(S(x*k))$, where $x$ is input block, $k$ is roundkey, $P$ is linear transformation (permutation), $S$ is nonlinear transfromation (substitution), * is the operation which combines input block and the roundkey. The last round is simply $(x*k)$. Worth mentioning, that exactly S-blocks are the targets of integer differential cryptanalysis.

btw, I don’t use parallelization because my laptop is unable to parallelize

P-layer: Linear Transfromation

The original linear transformation of the cipher creates problems for this cryptanalytic method. So we substitute the original P-layer by another linear operators, with the property: inversions of these operators in the ring $Z_{2^8}$ have only 0s and 1s in all rows (rationale is given in [2]). Usage of linear operator with these properties gives us the ability to build uppper-bound estimates of practical resistance of this cipher against integer differential cryptanalysis, similar to those, described by Biham, Shamir and Berson. This modification makes cryptanalysis focuse on S-block and its properties.

This code generates operators of that kind and deletes singular matrices among them (l is a maximum number of 1s that can occur in each row, size is the size of square matrix, quan is the number of matrices we want to generate).

MatrL[l_,size_]:= MatrL[l,size,1];
MatrL[l_,size_,quan_]:= Block[{rows,tabs={},t,d,tnew},
    rows = Table[PadLeft[ConstantArray[1,i],size],{i,1,l}];
    Table[Do[AppendTo[tabs,RandomSample[rows[[RandomInteger[{1,l}]]]]],{size}],{quan}];
    t = Partition[tabs,size];
   d = Det/@t;
   tnew = Delete[t,Position[d,0]]
               ]

This code builds inverse of a matrix in the ring $Z_{2^8}$.

Inv[matrix_,mod_]:= Map[Mod[#,mod]&,
    Table[(-1)^(i+j) Det[Delete[#,j]&/@Delete[matrix,i]],{j,16},{i,16}]*PowerMod[Det[matrix],-1,mod],{2}];

S - block: Nonlinear Transformation

This is the substitution layer specifed in the cipher [1]

S={252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,233,119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,249,24,101,90,226,92,239,33,129,28,60,66,139,1,142,79,5,132,2,174,227,106,143,160,6,11,237,152,127,212,211,31,235,52,44,81,234,200,72,171,242,42,104,162,253,58,206,204,181,112,14,86,8,12,118,18,191,114,19,71,156,183,93,135,21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,177,50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,223,245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,224,15,236,222,122,148,176,188,220,232,40,80,78,51,10,74,167,151,96,115,30,0,98,68,26,184,56,130,100,159,38,65,173,69,70,146,39,94,85,47,140,163,165,125,105,213,149,59,7,88,179,64,134,172,29,247,48,55,107,228,136,217,231,137,225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,97,32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,89,166,116,210,230,244,180,192,209,102,175,194,57,75,99,182}

It substitutes your bytes given in integer form by an integer, for which your byte is treated as index in this S-block. For example (I add 1, because bytes can be 0...255 and indices are 1...256):

S[[#+1]]&/@{0,5,7,255}

gives {252,110,22,182}.As we can see 0 gives us the first element in S-block - 252, 5 gives the sixth element - 110, and so on.

Evaluation

Here I do evaluate the cipher’s resistance in two cases:

1. operation * is bitwise XOR and round differences are modulo $2^8=256$

$$\Delta = \max_{ \alpha , \gamma = 1,...,255}2^{-8} \sum_{k=0,...,255} \sum_{z=0}^{8+1} \delta \left(S (k \oplus\alpha)-S(k),\gamma+z\right) $$ is the average probability of the integer differential. Implemneted as

    DeltaXorPlus[alp_,gam_]:=
    N[0.00390625 
        Sum[
          Count[
          Mod[gam+Range[0,8],256],
          Mod[S[[BitXor[k,alp]+1]]-S[[k+1]],256]],
        {k,0,255}],
    8];

This finds the maximal value, which would be the upper bound.

    Max@Table[DeltaXorPlus[alp,gam],{alp,1,255},{gam,1,255}]

I've obtained the estimate of this parameter for the 8-bit S-block specifed in [1] equal 0.08203125. Let's take a look at the distribution of parameter $\Delta$ for 8-bit S-blocks. The statistic may not show the whole picture, because it takes values only of one million random S-blocks, when there are 256! of them.

As we can see, estimate for Kyznyechik is close to the least value among obtained results. This means the cipher is resistant against th integer differential cryptanalysis of this kind.

2. operation * is addition modulo $2^8$ and round differences are modulo $2^8=256$

$$\Delta_+ = \max_{ \alpha , \gamma = 1,...,255}2^{-8} \sum_{k=0,...,255} \sum_{z=0}^{8+1} \delta \left(S (k +\alpha)-S(k),\gamma+z\right) $$ is the average probability of the integer differential. Implemneted as

    DeltaPlus[alp_,gam_]:=
    N[0.00390625 
        Sum[
          Count[
          Mod[gam+Range[0,8],256],
          Mod[S[[Mod[k+alp+1,256]]]-S[[k+1]],256]],
        {k,0,255}],
    8];

The maximal value (upper bound) is found the same way as the in the previous case. The estimate of this parameter for Kyznyechik is equal 0.0898437. If we look at the distribution of parameter $\Delta_+$ for 8-bit S-blocks we'll see it is also close to the least value.

We can claim the cipher is resistant against th integer differential cryptanalysis of this kind.

Conclusion

According to the estimates of practical resistance we now canclaim that the S-block specified for Kuznyechik cipher is resistant to integer differential cryptanalysis. This result is really cool for cryptology, because Kuznyechik seems to be the first cipher in history, to use by default the S-block designed with respect to resistance on this attacks (of course, we can’t say for sure if this was made on purpose or is just a coincidence).

Acknowledgements

I would like to thank my mentor Dr. Ludmila Kovalchuk for guidance and assistance with obtaining those results. Unfortunately, there is only one of her works available in English [2].

Thank you for reading!

References

1. National Standard of the Russian Federation GOST R 34.12–2015 (English Version)

2. L. V. Kovalchuk , N. V. Kuchinska Upper-bound estimates for the average probabilities of integer differentials of round functions of certain block ciphers

UPD:

Improved some code. Thanks to Sander Huisman