From: John Kelsey <jmkelsey@delphi.com>
Newsgroups: sci.crypt
Subject: Much-improved chosen-key relation attack on GOST
Date: Thu, 10 Oct 96 10:19:06 -0500

-----BEGIN PGP SIGNED MESSAGE-----

[ To: sci.crypt ## Date: 10/08/96 09:33 pm ##
  Subject: Much-improved chosen key-relation attack on GOST ]

David Wagner, Bruce Schneier, and I published a related-key
attack on (among other things) GOST at Crypto this year.  However,
the attack in that paper wasn't really practical unless the S-boxes
(which aren't specified in the GOST standard) were remarkably bad.

A couple weeks ago, I came up with an improved key-relation which I
believe will make the related-key attack practical with nearly all
S-box choices for GOST.  If we have an input difference into the
F-function (which must go into S2) that will lead to an output
difference in the F-function of only the high-order bit, then we can
carry out a related-key attack on GOST using two related keys and
probably about 2^{28} chosen plaintexts encrypted under each key.  I
will probably firm these numbers up when I have some time.

Let's review terms here:  A related-key attack is an attack where a
specific relationship exists between several keys, K, K*, K**, etc.
(In some contexts, the relationship may simply be observed, but
typically, the relationship is something the cryptanalyst chooses.
Sometimes, this is called a chosen-key attack or a chosen
key-relation attack.  However, I've never actually seen an attack
published in which arbitrary relationships between keys could be
exploited--this would be very interesting to see.)  The keys
themselves are unknown to the cryptanalyst--he tries to learn them
with the attack.  Typically, this also involves some known- or
chosen-plaintexts.  I would argue that related-key attacks are
somewhat practical when the number of different related keys needed
is small.  As the number of different related keys grows, the attack
usually becomes less practical.  However, it's possible to design
systems so that the cipher is simply never exposed to any kind of
related-key attack, i.e., by hashing the key with a good hash
function before feeding it into the cipher.

GOST is a 32-round balanced Feistel cipher--similar to DES (except
that DES has only 16 rounds).  Let S(X) represent applying eight
four-bit S-boxes in parallel to a X, let rol(x,a) represent rotating
x left a bits, and let a+k be the sum of a and k, modulo 2^{32}.
Then, the F-function for GOST is
     f(X,K) = rol(S(X+K),11).

The interesting thing about GOST is that it has a *really* simple
key schedule.  Start with a 256-bit key, broken into eight 32-bit
words:  K0, K1, ..., K7.  Now, the first 24 rounds use these keys in
order.  The last eight rounds use them in reverse order.  (This was
apparently done to prevent related-key attacks based on rotating the
key 32 bits in either direction.)

In our paper, we simply discussed putting some useful difference,
mod 2^{32}, into K0.  We could compensate for this difference in the
plaintext we fed in.  The result was that we dropped this difference
into the eighth round of the cipher--bypassing the first eight
rounds with probability one.  The same difference would wind up
being dropped in a couple more times, but this still looked
interesting.  Unfortunately, this didn't solve the problem of
getting some kind of useful difference through 20 or so rounds of
GOST, which is apparently still very hard.  We could see how to do
this only for very bad S-box choices.

However, there's a much better way to do this.  Let's find an input
delta to the F-function with only one active S-box--call this input
difference D0, and the corresponding most-likely output XOR
difference DX.

Now, let's imagine trying to solve the equation:

A + K1 = (A XOR DX) + (K1 XOR D1).

This is fairly easy to solve--swapping parallel bits in the two
operands of an addition operation can't affect the outcome, but
flipping parallel bits in the operands always affects the outcome
except in the high-order bit.  Thus, if DX winds up only in the
high-bit, this works with probability one--otherwise, it works with
probability 2^{-t}, where t is the number of one bits in DX.

Now, with all of this, we're ready to talk about our attack:

First key:     K0     ,K1        , K2,...,K7
Second key:    K0 + D0, K1 XOR DX, K2 + D0, K3, K4, ..., K7

Now, let's think about what's going on in the first three rounds.
We're encrypting with the first key, K, and the second key, K*.
Let's also assume that we've chosen D0 so that DX = 2^{31}.

First key: K
L1 = L0 XOR f(R0,K0)
R1 = R0 XOR f(L1,K1)
L2 = L1 XOR f(R1,K2)
...

Second key: K*
L1* = L0 XOR f(R0,K0 + D0) = L1 XOR DX (with probability p)
R1* = R0 XOR f(L1 XOR DX,K1 XOR DX) = R1 (with probability 1)
L2* = L1 XOR DX XOR f(R1,K2 + D0) = L2 (with probability p)

Thus, we wind up with a related-key differential characteristic that
is only active for three rounds out of each eight, and which cancels
itself out with fairly high probability.  This must pass through
three rounds, and it will do so with probability p^6, where p is the
probability of our specific desired output XOR.  If this had
probability p = 2^{-4} (as low as single S-box probabilities can
get), we'd have a 2^{-24} probability of passing this through the
first 29 rounds.  There should be better output probabilities
available, which will significantly improve this probability.

Comments?

   --John Kelsey, jmkelsey@delphi.com / kelsey@counterpane.com
 PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMl0BHkHx57Ag8goBAQE+YwP/RL8tXPY2aGKc39Sglg3oaiGv3O0EJRM2
o1q+Cnb+F3spTKMvdMg6+ZZNJyzZXLLHvVDw+NfUavQ0JEZ0xEZkLMy4ghIXT9tF
2zF1q4O9plK1tAswCeITR8XUwQRGAZ9QnMaUXfplp2dRR9NEsDprqk7BOpBWi6lu
Oi1UIpfl4x8=
=X+/q
-----END PGP SIGNATURE-----