From: pgut001@cs.auckland.ac.nz (Peter Gutmann)
Newsgroups: sci.crypt
Subject: Broken GOST implementation on FTP sites
Date: 11 Aug 1996 23:45:33 GMT
Organization: University of Auckland
Lines: 440

I was looking for a GOST implementation to wave at some government department
and found one (the same one) on a number of FTP sites.  I noticed that the
output values seemed a bit suspicious with a fixed input of "0123" for the data
and key so I stepped through it with a debugger.  The data isn't being
transformed much, and in fact the original plaintext drops back out in round 24
of the encryption.  Either:

1. GOST is broken.
2. The implementation is broken.

I suspect its probably not the former.  I don't have any of the GOST specs or
analyses here at the moment to look at to see where the problem is, but I
thought I'd let people know that if they're using this code they may want to
check the implementation.  I don't know if this is the code used in AC 2, I'll
check tonight.

I've included the code below, with fixed values substituted for the original
random ones.

Peter.

-- Snip --

/*
 * The GOST 28147-89 cipher
 *
 * This is based on the 25 Movember 1993 draft translation
 * by Aleksandr Malchik, with Whitfield Diffie, of the Government
 * Standard of the U.S.S.R. GOST 28149-89, "Cryptographic Transformation
 * Algorithm", effective 1 July 1990.  (Whitfield.Diffie@eng.sun.com)
 *
 * That is a draft, and may contain errors, which will be faithfully
 * reflected here, along with possible exciting new bugs.
 *
 * Some details have been cleared up by the paper "Soviet Encryption
 * Algorithm" by Josef Pieprzyk and Leonid Tombak of the University
 * of Wollongong, New South Wales.  (josef/leo@cs.adfa.oz.au)
 *
 * The standard is written by A. Zabotin (project leader), G.P. Glazkov,
 * and V.B. Isaeva.  It was accepted and introduced into use by the
 * action of the State Standards Committee of the USSR on 2 June 89 as
 * No. 1409.  It was to be reviewed in 1993, but whether anyone wishes
 * to take on this obligation from the USSR is questionable.
 *
 * This code is placed in the public domain.
 */

/*
 * If you read the standard, it belabors the point of copying corresponding
 * bits from point A to point B quite a bit.  It helps to understand that
 * the standard is uniformly little-endian, although it numbers bits from
 * 1 rather than 0, so bit n has value 2^(n-1).  The least significant bit
 * of the 32-bit words that are manipulated in the algorithm is the first,
 * lowest-numbered, in the bit string.
 */


/* A 32-bit data type */
#ifdef __alpha  /* Any other 64-bit machines? */
typedef unsigned int word32;
#else
typedef unsigned long word32;
#endif

/*
 * The standard does not specify the contents of the 8 4 bit->4 bit
 * substitution boxes, saying they're a parameter of the network
 * being set up.  For illustration purposes here, I have used
 * the first rows of the 8 S-boxes from the DES.  (Note that the
 * DES S-boxes are numbered starting from 1 at the msb.  In keeping
 * with the rest of the GOST, I have used little-endian numbering.
 * Thus, k8 is S-box 1.
 *
 * Obviously, a careful look at the cryptographic properties of the cipher
 * must be undertaken before "production" substitution boxes are defined.
 *
 * The standard also does not specify a standard bit-string representation
 * for the contents of these blocks.
 */
static unsigned char const k8[16] = {
	14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 }; 
static unsigned char const k7[16] = {
	15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 };
static unsigned char const k6[16] = {
	10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 };
static unsigned char const k5[16] = {
	 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 };
static unsigned char const k4[16] = {
	 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 };
static unsigned char const k3[16] = {
	12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 };
static unsigned char const k2[16] = {
	 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 };
static unsigned char const k1[16] = {
	13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 };

/* Byte-at-a-time substitution boxes */
static unsigned char k87[256];
static unsigned char k65[256];
static unsigned char k43[256];
static unsigned char k21[256];

/*
 * Build byte-at-a-time subtitution tables.
 * This must be called once for global setup.
 */
void
kboxinit(void)
{
	int i;
	for (i = 0; i < 256; i++) {
		k87[i] = k8[i >> 4] << 4 | k7[i & 15];
		k65[i] = k6[i >> 4] << 4 | k5[i & 15];
		k43[i] = k4[i >> 4] << 4 | k3[i & 15];
		k21[i] = k2[i >> 4] << 4 | k1[i & 15];
	}
}

/*
 * Do the substitution and rotation that are the core of the operation,
 * like the expansion, substitution and permutation of the DES.
 * It would be possible to perform DES-like optimisations and store
 * the table entries as 32-bit words, already rotated, but the
 * efficiency gain is questionable.
 *
 * This should be inlined for maximum speed
 */
#if __GNUC__
__inline__
#endif
static word32
f(word32 x)
{
	/* Do substitutions */
#if 0
	/* This is annoyingly slow */
	x = k8[x>>28 & 15] << 28 | k7[x>>24 & 15] << 24 |
	    k6[x>>20 & 15] << 20 | k5[x>>16 & 15] << 16 |
	    k4[x>>12 & 15] << 12 | k3[x>> 8 & 15] <<  8 |
	    k2[x>> 4 & 15] <<  4 | k1[x     & 15];
#else
	/* This is faster */
	x = k87[x>>24 & 255] << 24 | k65[x>>16 & 255] << 16 |
	    k43[x>> 8 & 255] <<  8 | k21[x & 255];
#endif

	/* Rotate left 11 bits */
	return x<<11 | x>>(32-11);
}

/*
 * The GOST standard defines the input in terms of bits 1..64, with
 * bit 1 being the lsb of in[0] and bit 64 being the msb of in[1].
 *
 * The keys are defined similarly, with bit 256 being the msb of key[7].
 */
void
gostcrypt(word32 const in[2], word32 out[2], word32 const key[8])
{
	register word32 n1, n2; /* As named in the GOST */

	n1 = in[0];
	n2 = in[1];

	/* Instead of swapping halves, swap names each round */
	n2 ^= f(n1+key[0]);
	n1 ^= f(n2+key[1]);
	n2 ^= f(n1+key[2]);
	n1 ^= f(n2+key[3]);
	n2 ^= f(n1+key[4]);
	n1 ^= f(n2+key[5]);
	n2 ^= f(n1+key[6]);
	n1 ^= f(n2+key[7]);

	n2 ^= f(n1+key[0]);
	n1 ^= f(n2+key[1]);
	n2 ^= f(n1+key[2]);
	n1 ^= f(n2+key[3]);
	n2 ^= f(n1+key[4]);
	n1 ^= f(n2+key[5]);
	n2 ^= f(n1+key[6]);
	n1 ^= f(n2+key[7]);

	n2 ^= f(n1+key[0]);
	n1 ^= f(n2+key[1]);
	n2 ^= f(n1+key[2]);
	n1 ^= f(n2+key[3]);
	n2 ^= f(n1+key[4]);
	n1 ^= f(n2+key[5]);
	n2 ^= f(n1+key[6]);
	n1 ^= f(n2+key[7]);

	n2 ^= f(n1+key[7]);
	n1 ^= f(n2+key[6]);
	n2 ^= f(n1+key[5]);
	n1 ^= f(n2+key[4]);
	n2 ^= f(n1+key[3]);
	n1 ^= f(n2+key[2]);
	n2 ^= f(n1+key[1]);
	n1 ^= f(n2+key[0]);

	/* There is no swap after the last round */
	out[0] = n2;
	out[1] = n1;
}
	

/*
 * The key schedule is somewhat different for decryption.
 * (The key table is used once forward and three times backward.)
 * You could define an expanded key, or just write the code twice,
 * as done here.
 */
void
gostdecrypt(word32 const in[2], word32 out[2], word32 const key[8])
{
	register word32 n1, n2; /* As named in the GOST */

	n1 = in[0];
	n2 = in[1];

	n2 ^= f(n1+key[0]);
	n1 ^= f(n2+key[1]);
	n2 ^= f(n1+key[2]);
	n1 ^= f(n2+key[3]);
	n2 ^= f(n1+key[4]);
	n1 ^= f(n2+key[5]);
	n2 ^= f(n1+key[6]);
	n1 ^= f(n2+key[7]);

	n2 ^= f(n1+key[7]);
	n1 ^= f(n2+key[6]);
	n2 ^= f(n1+key[5]);
	n1 ^= f(n2+key[4]);
	n2 ^= f(n1+key[3]);
	n1 ^= f(n2+key[2]);
	n2 ^= f(n1+key[1]);
	n1 ^= f(n2+key[0]);

	n2 ^= f(n1+key[7]);
	n1 ^= f(n2+key[6]);
	n2 ^= f(n1+key[5]);
	n1 ^= f(n2+key[4]);
	n2 ^= f(n1+key[3]);
	n1 ^= f(n2+key[2]);
	n2 ^= f(n1+key[1]);
	n1 ^= f(n2+key[0]);

	n2 ^= f(n1+key[7]);
	n1 ^= f(n2+key[6]);
	n2 ^= f(n1+key[5]);
	n1 ^= f(n2+key[4]);
	n2 ^= f(n1+key[3]);
	n1 ^= f(n2+key[2]);
	n2 ^= f(n1+key[1]);
	n1 ^= f(n2+key[0]);

	out[0] = n2;
	out[1] = n1;
}

/*
 * The GOST "Output feedback" standard.  It seems closer morally
 * to the counter feedback mode some people have proposed for DES.
 * The avoidance of the short cycles that are possible in OFB seems
 * like a Good Thing.
 *
 * Calling it the stream mode makes more sense.
 *
 * The IV is encrypted with the key to produce the initial counter value.
 * Then, for each output block, a constant is added, modulo 2^32-1
 * (0 is represented as all-ones, not all-zeros), to each half of
 * the counter, and the counter is encrypted to produce the value
 * to XOR with the output.
 *
 * Len is the number of blocks.  Sub-block encryption is
 * left as an exercise for the user.  Remember that the
 * standard defines everything in a little-endian manner,
 * so you want to use the low bit of gamma[0] first.
 *
 * OFB is, of course, self-inverse, so there is only one function.
 */

/* The constants for addition */
#define C1 0x01010104
#define C2 0x01010101

void
gostofb(word32 const *in, word32 *out, int len,
	word32 const iv[2], word32 const key[8])
{
	word32 temp[2];         /* Counter */
	word32 gamma[2];        /* Output XOR value */

	/* Compute starting value for counter */
	gostcrypt(iv, temp, key);

	while (len--) {
		temp[0] += C2;
		if (temp[0] < C2)       /* Wrap modulo 2^32? */
			temp[0]++;      /* Make it modulo 2^32-1 */
		temp[1] += C1;
		if (temp[1] < C1)       /* Wrap modulo 2^32? */
			temp[1]++;      /* Make it modulo 2^32-1 */

		gostcrypt(temp, gamma, key);

		*out++ = *in++ ^ gamma[0];
		*out++ = *in++ ^ gamma[1];
	}
}

/*
 * The CFB mode is just what you'd expect.  Each block of ciphertext y[] is
 * derived from the input x[] by the following pseudocode:
 * y[i] = x[i] ^ gostcrypt(y[i-1])
 * x[i] = y[i] ^ gostcrypt(y[i-1])
 * Where y[-1] is the IV.
 *
 * The IV is modified in place.  Again, len is in *blocks*.
 */

void
gostcfbencrypt(word32 const *in, word32 *out, int len,
	       word32 iv[2], word32 const key[8])
{
	while (len--) {
		gostcrypt(iv, iv, key);
		iv[0] = *out++ ^= iv[0];
		iv[1] = *out++ ^= iv[1];
	}
}

void
gostcfbdecrypt(word32 const *in, word32 *out, int len,
	       word32 iv[2], word32 const key[8])
{
	word32 t;
	while (len--) {
		gostcrypt(iv, iv, key);
		t = *out;
		*out++ ^= iv[0];
		iv[0] = t;
		t = *out;
		*out++ ^= iv[1];
		iv[1] = t;
	}
}


/*
 * The message suthetication code uses only 16 of the 32 rounds.
 * There *is* a swap after the 16th round.
 * The last block should be padded to 64 bits with zeros.
 * len is the number of *blocks* in the input.
 */
void
gostmac(word32 const *in, int len, word32 out[2], word32 const key[8])
{
	register word32 n1, n2; /* As named in the GOST */

	n1 = 0;
	n2 = 0;

	while (len--) {
		n1 ^= *in++;
		n2 = *in++;

		/* Instead of swapping halves, swap names each round */
		n2 ^= f(n1+key[0]);
		n1 ^= f(n2+key[1]);
		n2 ^= f(n1+key[2]);
		n1 ^= f(n2+key[3]);
		n2 ^= f(n1+key[4]);
		n1 ^= f(n2+key[5]);
		n2 ^= f(n1+key[6]);
		n1 ^= f(n2+key[7]);

		n2 ^= f(n1+key[0]);
		n1 ^= f(n2+key[1]);
		n2 ^= f(n1+key[2]);
		n1 ^= f(n2+key[3]);
		n2 ^= f(n1+key[4]);
		n1 ^= f(n2+key[5]);
		n2 ^= f(n1+key[6]);
		n1 ^= f(n2+key[7]);
	}

	out[0] = n1;
	out[1] = n2;
}

#ifdef TEST

#include <stdio.h>
#include <stdlib.h>

/* Designed to cope with 15-bit rand() implementations */
#define RAND32 ((word32)rand() << 17 ^ (word32)rand() << 9 ^ rand())

int
main(void)
{
	word32 key[8];
	word32 plain[2];
	word32 cipher[2];
	int i, j;

	kboxinit();

	printf("GOST 21847-89 test driver.\n");

	for (i = 0; i < 1000; i++) {
		for (j = 0; j < 8; j++)
			key[j] = 0x30313233;
		plain[0] = 0x30313233;
		plain[1] = 0x30313233;

		printf("%3d\r", i);
		fflush(stdout);

		gostcrypt(plain, cipher, key);
		for (j = 0; j < 99; j++)
			gostcrypt(cipher, cipher, key);
		for (j = 0; j < 100; j++)
			gostdecrypt(cipher, cipher, key);

		if (plain[0] != cipher[0] || plain[1] != cipher[1]) {
			fprintf(stderr, "\nError! i = %d\n", i);
			return 1;
		}
	}
	printf("All tests passed.\n");
	return 0;
}

#endif /* TEST */



From: pgut001@cs.auckland.ac.nz (Peter Gutmann)
Newsgroups: sci.crypt
Subject: Re: Broken GOST implementation on FTP sites
Date: 13 Aug 1996 14:52:13 GMT
Organization: University of Auckland
Lines: 34

daw@joseph.cs.berkeley.edu (David Wagner) writes:

>In article <4ulrat$8l0@net.auckland.ac.nz>,
>Peter Gutmann <pgut001@cs.auckland.ac.nz> wrote:
>> I was looking for a GOST implementation to wave at some government department
>> and found one (the same one) on a number of FTP sites.  I noticed that the
>> output values seemed a bit suspicious with a fixed input of "0123" for the data
>> and key so I stepped through it with a debugger.  The data isn't being
>> transformed much, and in fact the original plaintext drops back out in round 24
>> of the encryption.

>Anyhow, I note that the source below uses a weak key: all subkeys are
>set to the same value, 0x30313232.  Feistel ciphers exhibit weird
>behavior when using weak keys, so maybe that explains what you saw?

For even scarier behaviour, try using an all-zero key with all-zero data.  I 
somehow get the feeling that there are parts of GOST which still haven't been 
made public yet.  Recall that the initial translation of the standard didn't 
include the values for the S-boxes.  Then one set of S-box values appeared via 
some mysterious channel, supposedly originating from a Russian bank.  
According to AC 2, one Russian hardware implementation uses S-boxes generated 
by the chip designer with an RNG.  It could be that there are more parts of 
GOST which haven't surfaced yet, such as a proper key schedule.  In addition 
noone knows how the bank S-boxes were derived - they could just be the output 
of another RNG.  The lack of (official) test vectors means it's not even 
possible to test a given implementation.
 
At the very least I would recommend pushing any raw key through something like 
SHA (or some similar transformation) rather than using it directly.  In 
general I would avoid GOST - there are still too many unknowns involved to 
trust it.
 
Peter.

From: pgut001@cs.auckland.ac.nz (Peter Gutmann)
Newsgroups: sci.crypt
Subject: More thoughts on GOST
Date: 17 Aug 1996 15:53:16 GMT
Organization: University of Auckland
Lines: 51

A few days ago I posted a message warning about a possibly flawed 
implementation of GOST 28147 based on the behaviour I observed with certain 
keys.  After looking at the spec it appears the implementation is correct, and 
that the problem lies in the algorithm itself.  From my followup to the 
posting: 
 
>For even scarier behaviour, try using an all-zero key with all-zero data.  I 
>somehow get the feeling that there are parts of GOST which still haven't been 
>made public yet.  Recall that the initial translation of the standard didn't 
>include the values for the S-boxes.  Then one set of S-box values appeared 
>via some mysterious channel, supposedly originating from a Russian bank. 
>According to AC 2, one Russian hardware implementation uses S-boxes generated 
>by the chip designer with an RNG.  It could be that there are more parts of 
>GOST which haven't surfaced yet, such as a proper key schedule.  In addition 
>noone knows how the bank S-boxes were derived - they could just be the output 
>of another RNG.  The lack of (official) test vectors means it's not even 
>possible to test a given implementation.
 
The two problems with the incomplete GOST specification are:
 
1. The existing S-boxes are from a questionable source.
2. The direct use of a 256-bit key is inadvisable.
 
This implies that there are two portions of the algorithm not present in the 
spec:  The fixed S-boxes to use or the procedure for generating key-dependant 
S-boxes, and the procedure for processing the key to avoid weak keys.  Use of 
fixed S-boxes means they can be given specific properties to make differential 
and linear cryptanalysis difficult.  However the fact that GOST has 32 rounds 
makes this type of attack fairly challenging anyway, so it's probably better 
to just use key-dependant S-boxes.  This, and the inadvisability of using a 
key directly, leads to the need for a key schedule for GOST.  This should meet 
a number of requirements, various criteria and a list of references are given 
in AC 2.
 
A standard method I tend to fall back on for generating random keying material 
is to use the cipher which needs to be keyed to generate the data (typically 
by using the raw key to encrypt an all-zero data stream to generate the 
transformed key).  However this doesn't work with GOST because the raw key 
might be a weak key.  The alternative is to switch the roles around, and 
encrypt the raw key with a fixed non-weak key and S-boxes to get the 
transformed key.  The transformed key is then used to permute the S-boxes and 
as the 256-bit encryption key.
 
Unfortunately using this (or any other) key schedule for GOST means what 
you're using is no longer the proper GOST.  If anyone can shed some light on 
the rest of the algorithm, I'd be interested in hearing about it.
 
Peter.