From: daw@joseph.cs.berkeley.edu (David Wagner) Newsgroups: sci.crypt Subject: Re: Broken GOST implementation on FTP sites Date: 12 Aug 1996 01:46:22 -0700 Organization: ISAAC Group, UC Berkeley Lines: 115 In article <4ulrat$8l0@net.auckland.ac.nz>, Peter Gutmann 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. [...] > I've included the code below, with fixed values substituted for the original > random ones. > I dunno -- I couldn't reproduce the effect you were seeing. Maybe you were using some different values or something. (Or maybe it's an endianness thing!??) I dunno. 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? P.S. I took the opportunity to glance through the source, and a few things struck me right away: > /* > * 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. [...] > */ > > /* The constants for addition */ > #define C1 0x01010104 > #define C2 0x01010101 Poor choices. I criticize the GOST standard here -- the GOST stream cipher mode *does* have short cycles -- it is guaranteed to repeat every 2^32 - 1 blocks. If the GOST designers had just incremented the whole block mod 2^64, like in counter mode, this problem would not be present. Furthermore, the designers chose a value for C1 which has many factors in common with the modulus: in fact, (2^32 - 1) / C1 = 255. This means that the left half of the input to GOST (temp[0]) repeats every 255 blocks. That seems like it's tempting the fates... > /* > * 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++; [...] I hope that's an implementation bug: the last quoted line should read n2 ^= *in++; The xor is *very* important; otherwise there's a 2^16 birthday attack on the MAC. Using just 16 rounds for the MAC mode seems scary. food for my damned news gateway: < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie < cookie