Кузнечик шифр (GOST Kuznechik - 128) C - версия

Note :

For Easy Explanation Purposes I'm Reusing my README for Python Implementation Here

History

This is a SP Network (Substitution Permutation) Cipher Based Encryption on 128 bit blocks as per Specs Defined by Russian Union Standards (GOST). This is aimed as an Alternative to the NSA Approved AES (Rijndael) Cipher. Kuznechik was apparently named after the three proposers for the algorithm (Kuzmin Nechaev and Company)(Ru:Кузьмин, Нечаев и Компания). However the GOST Standard for the same does not declare the гост (МАГМА) шифр ( GOST MAGMA Cipher ) as defunct. Recently VeraCrypt also Adopted Kuznechik Cipher for Disk Encryption.

Structure

This is a Symmetric Key Block Cipher With Profile:

  Network     : SPN + Fiestel (For Key Deployment)
  Block Size  : 128 bits  
  Key Size    : 256 bits
  SubKey Size : 128 bits
  No SubKeys  : 10 Sub Keys
  No Of Rounds: 10 Rounds
  P-Box       : 16x16 -> 256
  P-Inv_Box   : 16x16 -> 256

Details

1.Inputs

Key : 256 bit 
Message(hex) : n bit (will be divided into 128 bit blocks)

My Comments

The key should be generated using a PseudoRandom Bit Generator ( 256 bits ). Please Refer MersenneTwister BlumBlumShub PRNG in my Repository.

Try Setting a script to generate 256 PseudoRandomly generated bits . This will be your Key. I'll leave it to your discretion . Also Kuznechik Employs Galois Field Arithmetic (Operations On Field GF(2)[x]->p(x) ) with p(x)=x8+x7+x6+x+1 So to understand the Source code will require some Knowledge on Galois Field Arithmetic and Number Theory.

2.P-BOX

The Non Linear Bijective Transformation P-Box is defined in the standards as P = V₈ π^-1Int₈ Where V₈ is a Bijective Mapping associated with the ring of the Z_2⁸=>V₈- Z_2⁸ and

Int₈ refers to inverse mapping to the vector V^-1 that is V₈=> Z_2⁸- V₈

Transformations {Encryption}

The Kuznechik cipher uses a variety of transformations in order to perform Substitution and Permutation wrt each block

1.S Transformation

---

Herewith We Refer the S-Transformation as The Substitution from the p-box This Transformation is defined formally int the 128 bit Vector Space Mapping of

V128->V128 : S(x):S(x15||...||x0)= π(x15)||...|| π(x0)

|| Refers to Concat Operation.

Implementation:

Maintain a variable s such that s is left shifted by 8 bits every iteration (16) such that (16*8=128) bits of substituted bits from P box obtained 0xff acts as an 8-bit mask.

s=0
for i in range(15,-1,-1):
  s<<=8
  s^=(self.pi[(x>>8*i&0xff)])

return s

---

2.R Transformation

The R transformation defined in the standards Map 128 bit Vector Space :

V128->V128 : R(x):R(x15||...||x0)=L(x15||...||x0)||x15||...||x1

Where L(k) k=x15||...||x0 refer to Linear Transformation Function .

Implementation : Apply Linear Transformation to the Entire Input xor with All other x Except x₀ (8 bits LSB)

((linear_Transformation(x)<<120)^(x>>8))

3.L Transformation

The L Transformation defined in the standards Map 128 bit Vector Space : V128->V128 : R16(x) Meaning Repeatedly apply R(x) to x 16 times Implementation: (Apply R(x) to X )* 16

for _ in range(16):
  x=self.R_Transformation(x)

---

4. Linear Transformation:

The Linear transformation is defined from the Vector Space Mapping: V168->V8: _iter=[148,32,133,16,194,192,1,251,1,192,194,16,133,32,148,1] Define l(x): ∇(_iter[0]Δ(x₁₅)||...||_iter[-1]Δ(x₀)) Operations of Addition And Multiplication closed under Field. Implementation:

    
    _map_=[148,32,133,16,194,192,1,251,1,192,194,16,133,32,148,1][::-1]
    res=0

    for i in range(15,-1,-1):
         res^=self.Mod_Polynomial_Reduction(self.M(_map_[i],(x>>8*i)&0xff),0b111000011)

Transformations {Decryption}

1.S-Inverse Transformation

---

Herewith We Refer the S^-1-Transformation as The Substitution from the p-box This Transformation is defined formally int the 128 bit Vector Space Mapping of

V128->V128 : S-1(x):S-1(x15||...||x0)= π-1(x15)||...|| π-1(x0)

|| Refers to Concat Operation.

Implementation:

Maintain a variable s such that s is left shifted by 8 bits every iteration (16) such that (16*8=128) bits of substituted bits from P^-1 box obtained 0xff acts as an 8-bit mask.

s=0
for i in range(15,-1,-1):
      s<<=8
      s^=(self.pi_inv[(x>>8*i&0xff)])
            

2.R Inverse Transformation

The R^-1 transformation defined in the standards Map 128 bit Vector Space :

V128->V128 : R-1 (x):R-1 (x15||...||x0)=x14||...||x0||L(x15||...||x0)

Where L(k) k=x15||...||x0 refer to Linear Transformation Function .

Implementation : Apply Linear Transformation to the Entire Input xor with All other x Except x₁₅ (8 bits MSB)

((x<<8)^self.linear_Transformation(x<<8^((x>>120)&0xff)))

3.L Inverse Transformation

The L^-1 Transformation defined in the standards Map 128 bit Vector Space : V128->V128 : (R-1)16(x) Meaning Repeatedly apply R(x) to x 16 times Implementation: (Apply R^-1(x) to X )* 16

for _ in range(16):
      x=self.R_Transformation_inverse(x)

Miscellaneous Functions {Decryption} {Encryption}

These are functions that are used to perform Multiplication and Mod under the Galois Field F discussed above for the polynomial p(x) To Get a gist of what is being done here Kindly refer the links cited in the source .

1.M Function

This function essentially multiplies two binary polynomials and returns its product Algorithm: Performing Multiplication in the Field{0,1} is essentially left shifting bits. 1.So Keep the multiplicand constant 2.We need to just work with the multiplier and here it is y. 3.Access each LSB of y using y&1 and check if the LSB is 1 . That means that there is a power in the binary polynomial {0,1}y=>1.y^deg 4.Keep another variable as result xor with x<<deg , deg here is the degree of the polynomial (bit index ) of y where the coeff=1 5. increment deg for till we exhaust the multiplier y (y>>1)

c=0
deg=0
while y!=0:
      if(y&1):
            c^=(x<<deg)
      deg+=1
      y>>=1

2.Deg Poly

This function Does the same thing as the deg defined above but is specific to the use case which dictates where we need to find the highest power of the given polynomial ofc len (str) does the same .. but bit shifting seems more sensible. I mean the this function can be dynamically be re-used when the polynomial is constantly being reduce during an iteration (dependent variable),(k>>=1 or k<<=1).So the powers do change.

deg=0
while x!=0:
      deg+=1
      x>>=1

3. Mod Polynomial Reduction

This Function is for performing Modulus under the GF .This is to reduce the Product From the M Function Into the domain of GF (p). Here this function is not specific to a particular domain as such . But Kuznechik uses GF(2)[x]->p(x)=x8+x7+x6+x+1 (111000011) as mod as its modulus domain. So Any product Produced from the M function is essential to be reduced to the GF(2)[x]->p(x) domain.

Algorithm: 1.Iterate till deg(z) <deg(mod):while performing (m<<diff) where diff is the difference between the highest power of z and m itself

z=x
while True:
      if(self.degree_Poly(z)<self.degree_Poly(m)):
            break
      else:
            diff=self.degree_Poly(z)-self.degree_Poly(m)
            z^=(m<<diff)

Key Deployment Functions {Decryption} {Encryption} KDF

Interestingly as I had discussed above this algorithm is unique in the sense that it uses Fiestel Structure for its Key Deployment Function. Kuznechik uses 256 bit seed Key and 128 bit partition Keys for Each Round (10)

1.F Transformation

This Is the part that performs the Fiestel Swap where we essentially apply (L(S(roundconst^k1))^k2,k1) where + under the GF {0,1} implicitly implies xor operation. Returns two Parts where the k1 is untouched and returned and the other key is (k1) xor (c) where c is the round constant.Then applyed finally LS Transformation Layers in the same order.

[self.L_Transformation(self.S_Transformation(c1^k1))^k2,k1]

2. Round Function

This Function Essentially is just a utility function to compute Round const (128 bit) For i={0...9} and returns L_Transformation(round_no)

(self.L_Transformation(round_no))

3. Key Schedule Function

This Function is used to compute key partitions (subkeys) for each round using the round constant and F Transformation discussed above. The initial Key Partition are k1=K₂₅₆||...||K₁₂₈ k2=K₁₂₇||...||K₀ In short this function performs As described in the GOST Standard: (K2i+1,K2i+2)=FTransformation(RoundConst8(i-1)+8)...FTransformation(RoundConst8(i-1)+1(K2i-1,K2i) i={1,2,3,4}

k1=(key>>128)&self.MASK_32
k2=(key)&self.MASK_32
key_arr=[k1,k2]
for i in range(1,33):
      c=self.Round_constant(i)
      f=self.F_Transformation(c,k1,k2)
      k1,k2=f
      if(i%8==0):
          key_arr.extend([k1,k2])

Encryption

Encryption is done using multiple round sub keys with Composition of functions L Transformation(S Transformation(x+k)) repeated till round 9 and the final round is sans the Composition we simply perform x+k₁₀ representing the last sub key. Do Note that For Encryption we use the Functions tagged as {Encryption}/{Misc.}.

a=self.message
k=self.Key_Schedule(self.key)
for i in range(9):
      
      a=self.L_Transformation(self.S_Transformation(k[i]^a))

return a^k[-1]

Decryption

Decryption is similar to Encryption and is done using multiple round sub keys in reverse with Composition of functions S Inverse Transformation( L Inverse Transformation((x+k))) repeated till round 1 (from reverse) and the final round is sans the Composition we simply perform x+k₀ representing the first sub key. Do Note that For Decryption we use the Functions tagged as {Decryption}/{Misc.}.

pt=cipher
k=self.Key_Schedule(self.key)

for i in (range(9,0,-1)):
      pt=self.S_Inv_Transformation(self.L_Transformation_inverse(k[i]^pt))
return pt^k[0]

Implementation

Check out FileCrypt where I used my implementation of Kuznechik Cipher for Encrypting Files . (I am yet to improve its performance aspect per se.).

Dependencies

Library	Version	System
Libgmp	2:6.2.0	amd64/x86_64
openmp	4.0.3	amd64/x86_64
gcc	4:9.3.0-1	amd64/x86_64