Re: GOST for sale

[JMKELSEY@delphi.com]

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

>Date: Fri, 24 Nov 1995 03:43:25 +0100 (MET)
>From: Mats Bergstrom <asgaard@sos.sll.se>
>Subject: GOST for sale

>According to a short article in a Swedish newspaper (DN)
>with the title 'Spy Code of KGB can make computers safe',
>JETICO INC., located in Finland (Tammerfors), introduced
>a new crypto system on the world market last week. It's
>based on GOST, the Russian federal standard algorithm.
>This product, called BestCrypt, is implemented at least
>partly in hardware. Alledgedly it uses 'GOST 28147-89',
>whatever that stands for.

Hmmm.

>GOST is probably very secure - a huge keyspace (256 bits) and
>KGB would not have left a trapdoor for NSA to take advantage
>of, would they?

If this is the cipher I've seen, it's not overwhelmingly impressive,
though it may be OK.  I haven't ever made any serious attempt to
attack it, and I don't know anyone else who has.  Anyone have a
reference?

Basically, GOST is a balanced Feistel network (like DES), but its
F-function is much simpler.  Basically,
F(X,K) = Rotate_Left(S(X+K),11),
where S(t) denotes parallel application of eight 4:4 S-boxes.

Depending on the implementation, these S-boxes' contents could be
key-dependent and pseudorandom, or fixed.  Unfortunately small
random S-boxes are likely to have some weaknesses W.R.T.
differential cryptanalysis.  This can be true even when the S-boxes
are secret and key-derived--see Biham and Birkyov's paper in
Auscrypt '94 on a DES variant with variable S-boxes, for a quick
discussion of this.  And the security of this scheme is very much
going to depend upon the S-boxes used.  If the S-boxes are generated
at (pseudo)random from the key, I'd expect there to be some pretty
nasty weak key conditions that could occasionally come up.

On the other hand, GOST is defined with 32 rounds, so it may be hard
to find any useful differential or linear characteristics, even for
relatively bad S-box choices, that have high enough probability to
get through 29-31 rounds.  And it has a 256-bit key, so even if
someone determines some attack which recovers 160 bits of the key,
there are still 96 bits of key left to provide security.

The GOST key schedule is really simple, though it avoids the most
obvious kind of related key attack.  I wouldn't be surprised to see
some interesting related key attacks be possible.  This is
interesting because there is also a hash function based on GOST--I'd
be pretty reluctant to use this without a lot of analysis.

>The newspaper article ends:
>
>'The Finnish entrepreneurs asseverate that their
>Russian colleagues have never had anything to do
>with the KGB.'

I may be mistaken, but wasn't there some other internal organization
in the USSR that did cryptography?

>Mats

Note:  Please respond via e-mail as well as or instead of posting,
as I get CP-LITE instead of the whole list.

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

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

iQCVAwUBMLv0kkHx57Ag8goBAQFH3AP+JR1sEQCH0ANmNSDFhzpCZb4jn4uqq23v
PjZfFOrYc9SrD1xn+3azqfHFpiHIubfWzZ8u1aNEf4erAErbQLPAUOLPv17zhn//
6UEVKX4GhPqoLfou+wO38rF2DwWdeCjuQm2GgxuFpw5b0D4M3V1mv5ocLOoOMq2N
twdfxiMtO6Y=
=BOER
-----END PGP SIGNATURE-----