SOLUTION FILE 
TABLE OF CONTENTS

Introduction ........................................................ Section 0
Usage ............................................................... Section 1
Description of Algorithm ............................................ Section 2
Code Analysis and Obfuscation ....................................... Section 3
Bibliography ........................................................ Section 4


-- SECTION 0 -------------------------------------------------- INTRODUCTION --

The code is a diminutive implementation of the  KGB  block  cipher,  GOST,  in
Simple Substitution Mode as described in the Soviet Standard (GOST  28147-89).
An English translation by Josef Pieprzyk and Leonid Tombak is  available  from
ftp://vipul.net/pub/gost/specs.ps.gz. (You don't really want to read  this,  a
functional description of the algorithm is included in this file.)

Besides implementing the encryption algorithm, the  code  also  also  computes
the key-store-unit and s-box permutations as a function of the pass-phrase.  



-- SECTION 1 --------------------------------------------------------- USAGE --

code -e -p=pass_phrase plain_text_file   (Encryption)
code -d -p=pass_phrase cypher_text_file  (Decryption)



-- SECTION 2 -------------------------------------- DESCRIPTION OF ALGORITHM --

GOST is a 64-bit block cipher with  a  265-bit  key.  Since  the  specs  don't
discuss how to generate the s-boxes, this implementation uses the 354 bits  of
permutations as key material; the effective key length of this  implementation
is,  therefore,  is 610 bits. [ Which, of course, makes  it  a  deadly  weapon
according to the U. S. Export Administration  Regulations  and  Anti-terrorism 
Controls ;-) ] 

The GOST Algorithm consists of the following components: 

o  256-bit Key Store Unit (KSU) which contains 8 32-bit sub-keys. 
o  32 bit adder modulo 2**32.                          
o  Bit wise exclusive OR adder for 32-bit words. 
o  Eight s-boxes. 
o  S-box substitution. 
o  11 bit left circular shift. 

The plaintext is broken into 64 bit long blocks. Each block  goes  through  32
iterations of the encryption algorithm illustrated in FIGURE 2.0 and explained
below: 

    The text is broken into two 32-bit halves. The right half and the ith sub-
    key are added modulo 32. The result is broken into eight 4-bit chunks  and
    each chunk becomes the input to a different s-box. All s-box  outputs  are
    recombined into a 32-bit word and the entire word goes through  a  11  bit
    circular shift. Finally, the results are XORed to the left half to  become
    the new right half and the old right half becomes the new left half.   

S-BOX Substitution. 

    There are eight s-boxes in GOST and each s-box consists of  a  permutation
    of the Numbers 0 through 15. The input to the substitution  components,  a
    32-bit integer is broken into 4-bit chunks. Each of these chunks  is  used
    as an index to one s-box. For example, if the s-box is (14, 11, 4, 12,  6,
    13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9), then input of 0 will output 14, input
    of 4 will output 6 and so on. The  outputs  are  collated  into  a  32-bit
    integer which is the final product of the substitution phase.  

The same algorithm is used for decryption, with a change in the the  order  of 
sub-keys used in different rounds. (See FIGURE 2.1) 

------- FIGURE 2.0 ------------------------------------------------------------
 ONE ROUND OF GOST                    

                   /---------------\                
                  (     R [i-1]     )==============================\\
                   \---------------/                                || 
                          ||                                        || 
                          ||                                        ||
                          \/                                        ||
                        +----+                /----------------\    ||
                    ADD | ++ |<==============(  Key Store Unit  )   ||
                        +----+                \----------------/    ||
                          ||                                        || 
                          ||                                        ||
                          \/                                        ||
                /---------------------\                             ||  
               (  S-box Substitution   )                            ||
                \---------------------/                             ||       
                          ||                                        ||
                          ||                                        ||
                          \/                                        ||
                /---------------------\                             ||
               (  Left Circular Shift  )                            ||
                \---------------------/                             ||
                          ||                                        ||
                          ||                                        ||
                          \/                                        ||
 /---------------\      +----+                                      ||
(     L [i-1]     )====>| -- | XOR                                  ||
 \---------------/      +----+                                      ||  
                          ||                                        || 
                        \ || /                                    \ || /
                         \||/                                      \||/
                          \/                                        \/ 
                  /---------------\                          /---------------\  
                 (      R [i]      )                        (      L [i]      )
                  \---------------/                          \---------------/         


                                                                 FIGURE 2.0
--------------------------------------------------------- ONE ROUND OF GOST --


---------- FIGURE 2.1 --------------------------------------------------------
 USE OF GOST SUB-KEYS
  IN DIFFERENT ROUNDS

There are "eight" 32-bit sub-keys, each key is  used  4  times  in  32  rounds
according to the following rule-set: 

For encryption:                            For decryption:           
                                                                    
Rounds 01-08 => Sub-keys 1-8               Rounds 01-08 => Sub-keys 1-8
Rounds 09-16 => Sub-keys 1-8               Rounds 09-16 => Sub-keys 8-1
Rounds 16-24 => Sub-keys 1-8               Rounds 16-24 => Sub-keys 8-1
Rounds 25-32 => Sub-keys 8-1               Rounds 25-32 => Sub-keys 8-1


                                                                 FIGURE 2.1
                                                       USE OF GOST SUB-KEYS
------------------------------------------------------- IN DIFFERENT ROUNDS ---

SECTION 3 
CODE ANALYSIS AND OBFUSCATION 

The obfuscation in the code is a result of resource  (code  size)  constraints
met with clever semantic optimizations implemented by exploiting the wonderful
mix of high- and low-level features of perl.  For  example,  while  the  s-box
permutations are stored as lists, 4-bit s-box substitutions  are  carried  out
with bit operations. A few bytes of syntactic noise is added  to  augment  the
general flavor. ;-) 

The logic can be pieced together with the comments in the code below. 

#!/usr/bin/perl -s 

##  Variable Definitions. 
##
##  @R -- Key Store Unit, Array of 32-bit integers. 
##  $R -- '_', Scalar.
##  $S -- S-boxes, List of List. 
##  $t -- Text, Scalar. 
##  $e -- Non-zero indicates encryption mode, scalar. 
##  $d -- Non-zero indicates decryption mode, scalar. 
##  $v -- Left half in a GOST round, scalar. 
##  $w -- Right half in a GOST round, scalar. 


sub R {                                                                  ## 00
    int$_[0] || return vec $_[1], $_[2]/4,32;                            ## 01
    int$_[0]*rand                                                        ## 02
}                                                                        ## 03

##  Sub R () 
##
##  Takes either one or three integer parameters. 
## 
##  Returns  a random number between  0..$_[0]  when the first parameter is  a
##  positive integer. 
##
##  If  the first argument is non-numeric, returns a 32-bit integer at  offset
##  $_[2] from bit-field $_[1]. 

($R) = $^ =~ '([\]-\`])';                                                ## 04

## Line 04 
##
## $^ by default contains the name of the currently selected output filehandle
## with _TOP appended. The regex, '([\]-\`])' matches the "_"  in  "_TOP"  and 
## assigns it to $R. 

sub F {                                                                  ## 05
    $u=0;                                                                ## 06
    grep $u |= $S->[ $_ ][ $_[0] >> $_ * 4 & 15 ]<< $_ * 4,reverse 0..7; ## 07

##  Line 07 
## 
##  Line 7 implements the s-box substitution. It  iterates  a  's-box  lookup'
##  routine eight times, and selects  the  appropriate  input  bits  for  each
##  iteration with bit shifts. $u is ORed with the result of  every  iteration
##  such  that  after  eight  rounds  it  contains  the   32-bit   result   of
##  substitution. 
             
    $u << 11 | $u >> 21                                                  ## 08

## Line 08 
## 
## Returns $u left circular shifted by 11 bits. 

}                                                                        ## 09

$t = $e||$d ? join '', <> : (($p,$d)=($R,1), unpack u, "(3=MCV7%2W'<`"); ## 10

##  Line 10 
## 
##  Reads text from STDIN if -e or -d flags are specified on the command line,
##  otherwise it sets text to binary equivalent of "(3=MCV7%2W'<`"), which  is
##  the GOST encrypted version of the string "TPJ." Sets password to  is  "_",
##  the password that was used to encrypt the string ($p = $R)  and  sets  the
##  the decrypt flag. ($d = 1). 
## 
##  The encrypted string was intended as a 'hook' into the code to make-up for 
##  the lack of 'usage' information.  

@b = @t = 0..15;                                                         ## 11
for (; $i<length$p; $i+=4) {                                             ## 12
    srand ( $s ^= R$R,$p,$i )                                            ## 13
}                                                                        ## 14

##  Lines 11-14
##
##  Generates a 'hash' of the pass phrase by 'breaking' it into  32-bit  parts
##  and  XORing  them  together.  perl's  pseudo-random  number  generator  is
##  'seeded' with this hash. Subsequent calls to rand () are a  'function'  of
##  the pass-phrase, therefore rand () is used for computing the secret  s-box
##  permutations and the key-store-unit.  
## 
##  When  the pass-phrase is  longer than 4  characters,  srand ()  is  called 
##  multiple times. Harmless redundancy that saves a couple of bytes. :-)


while ( $c < 8 ) {                                                       ## 15
    grep { push @b, splice @b, R(9), 5 } @t;                             ## 16

##  Permutes @b by 'cutting' 5 elements from random offsets and appending them 
##  to the list. This is done 15 times to generate one permutation.

    $R[$c] = R (2**32);                                                  ## 17

##  Line 17
##  
##  Generates a 32-bit key and assigns it to the key-store-unit.

    @{$S->[$c++]} = @b                                                   ## 18

##  Line 18
##
##  Assigns the permutation the s-box. 

} 

@h=0..7;                                                                 ## 19
@o = reverse @h;                                                         ## 20

while ( $a < length $t) {                                                ## 21

##  Line 21 
## 
##  Loops  over  the entire text,  which is encrypted or decrypted  in  64-bit
##  chunks.

    $v = R$R,$t,$a;                                                      ## 22
    $w = R$R,$t,($a+=8)-4;                                               ## 23

##  Lines 22-23
## 
##  Computes 32-bit left and right hand halves from  the  64-bit  text  to  be
##  processed.  

grep $q++%2?$v^=F$w+$R[$$R]:($w^=F$v+$R[$$R]),$d?(@h,(@o)x3):((@h)x3,@o);## 24

##  Line 24 
##
##  These 71 bytes implement the 32 rounds of GOST for encryption as  well  as
##  decryption. The grep loop takes one of the  two  lists  depending  on  the
##  current mode of the  algorithm  (  $d?(@h,(@o)x3):((@h)x3,@o)  ).  If  the
##  decrypt flag is switched on, (@h, (@o)x3) or (0..7 7..0 7..0 7..0) is used
##  otherwise encryption mode is assumed and  the  list  ((@h)x3,@o)  is  used
##  instead.  This  list  provides  the  index  into  the  key-store-unit  for
##  different rounds of de/encryption (see FIGURE 2.1). A counter $q  is  used
##  to decide which part (left or right) of the text should be operated on  in
##  a particular round. Odd means the left  part  ($v^=F$w+$R[$$R])  and  even
##  means the right part ($w^=F$v+$R[$$R]). (If you look at the structure of a
##  GOST round, you'll see that this simple alternation provides  the  correct
##  correspondence between the "new" left and right halves.) One half is added
##  to the sub-key for that round ($R[$$R] -- $$R is just $_) and passed to  F
##  where it goes through s-box substitution and an 1-bit left circular  shift
##  and assigned to the other half. This happens 32 times. At the end  of  the
##  grep loop the $v and $w contain GOST de/encrypted text. 

    $_.=pack N2,$w,$v 

##  Pack two 32-bit numbers into a binary string and append it to "$_". 

}

print 

##  Print "$_" which contains the de/encrpyed text. 


-- SECTION 4 -------------------------------------------------- BIBLIOGRAPHY --

0. Perl Programmers Reference Guide or the Perl man peges.

1. Soviet Encryption Algorithm from Russian translated by Josef  Pieprzyk  and 
   Leonid Tombak.  

2. Applied Cryptography (Second Edition) by Bruce Schneier. 

 


