Subject: Re: Adding GOST as a cipher?

From: [email-masked] ("Hal Finney")
Date: Fri, 21 Jan 2005 10:32:11 -0800 (PST)

I'm not happy about adding a cipher with a 64 bit block size in this day
and age.  Putting it into the spec seems to be an implicit endorsement to
some degree.  We took out ElGamal signatures because of the difficulty of
using them securely, and I think we should continue to demand that we only
add algorithms to the spec if they provide acceptable levels of security.

I don't know the details of GOST but it is often called the "Russian
DES" and we certainly wouldn't want to add a DES-strength cipher now.
GOST has a much larger key so it is not quite the same but overall it
seems like an old cipher whose time has passed.

For those who want to use it, would an acceptable alternative be
a short informational RFC which specified an algorithm ID from the
private/experimental range?

Hal

---

From: "Vlad \"SATtva\" Miller" <[email-masked]>
Date: Sat, 22 Jan 2005 01:09:52 +0600

> seems like an old cipher whose time has passed.

You're absolutely right. Aside from the longer key, more rounds, and linear
and differential cryptanalysis resistence, it has many disadventages even
compared to DES. Some of these includes:

* key schedule virtually non-existent (subject to related key attacks)
* very simple round function with cyclic linear shift (smaller avalanche
effect)
* S-boxes' size is too short, and criteria for their choosing is not available
(something to think about in connection with "A Family of Trapdoor Ciphers" by
Vincent Rijmen and Bart Preenel)
* weak keys and short cycles exists

A few years ago it was theoretically estimated that an effective strength of
GOST cipher is approximately 2^56, that is about the same value as DES's. Not
quite what we need by today's standards. And not quite what has been always
officially supported by OpenPGP.

Respectfully yours,

 Vladislav "SATtva" Miller
 http://www.pgpru.com

---

From: Ian G <[email-masked]>
Date: Fri, 21 Jan 2005 19:35:33 +0000

>add algorithms to the spec if they provide acceptable levels of security.

I think of it as a chess game.  Advancing a pawn
into line of attack of the queen is not a good
strategy, for the pawn, and perhaps we should
take away the pawn from the game's rules?

By putting GOST into OpenPGP we are offering
a product that conforms to "the rules."  That
means those rule-takers are more likely to use
OpenPGP than another product.

Not only is the other product likely to be more
insecure (any arguments there? ;) it won't also
come with AES, etc.  All OpenPGP products these
days come with a lot of other nice strong options;
these are the knights covering the pawn's move.

The rule-takers that we are talking about are
notoriously poor at following the spirit of the
rules....  For the most part, "we use OpenPGP
and OpenPGP has GOST" is probably sufficient
to get a pass.

>private/experimental range?

If it is specified it shouldn't be in the private/
experimental range.  That range should be for
stuff that isn't specified, by definition.

iang

-- 
News and views on what matters in finance+crypto:
        http://financialcryptography.com/

---

From: Ian G <[email-masked]>
Date: Fri, 21 Jan 2005 19:45:04 +0000

Vlad "SATtva" Miller wrote:

[bad news snipped!]

>officially supported by OpenPGP.

How about doing a triple-GOST?  That would
meet the letter of the rules, and give a boost
to the security?  Just brainstorming here...

iang

---

From: David Shaw <[email-masked]>
Date: Fri, 21 Jan 2005 15:06:34 -0500

On Fri, Jan 21, 2005 at 10:32:11AM -0800, "Hal Finney" wrote:

> For those who want to use it, would an acceptable alternative be a
> short informational RFC which specified an algorithm ID from the

That feels a bit like cheating to me.  As soon as there is an RFC
(informational or otherwise), an algorithm should not be in the
experimental range.  Otherwise, we'd be effectively moving that
experimental algorithm number into the operational range.  We couldn't
use it for experimental purposes any longer.

(Not arguing for or against GOST.  Just for algorithm numbering
cleanliness.)

David

---

From: "Vlad \"SATtva\" Miller" <[email-masked]>
Date: Sat, 22 Jan 2005 04:23:52 +0600

> to the security?  Just brainstorming here...

Well, this may be helpful if GOST is really subject to "sliding" attacks, and
would put excercises in "meet in the middle", et cetera to pure theoretic
field (because of memory requirements). But this is hardly a good decision
anyway. Maybe GOST multiple encriptions -- on the assumpsion of architectual
similarity to DES -- isn't forming a group, but look at the keylength.
Standard variant has 256 bits + secret S-boxes give us something about 610
bits of secret data. In 3GOST (or whatever) it would be more than 1800 bits --
for symmetric cipher! Moreover, there are speed considerations...

---

From: Ian G <[email-masked]>
Date: Fri, 21 Jan 2005 22:59:37 +0000

>for symmetric cipher! Moreover, there are speed considerations...

Let's see now.  1800 bits of secret key data.
That's less than a millisecond of random data
from my /dev/urandom.  So that's not an issue.

Secret key data, certainly in the OpenPGP
world is *primarily* used as a secret key
exchange encrypted by public key.  So, if
one looks at the public key algoriths, they
mostly have the characteristic that when
they are encrypting, they do so over a block
that is the same size as the key.  E.g., a
1024 bit key can encrypt a 1024 bit block.

(Or something - can someone post the real
cryptographer's viewpoint on this?)

So we may be limited to using 2048 bit public
keys and above when using GOST.  Oh well,
that's not a biggie!  Some would say that
should be mandated anyway.

Then there is the notion of straight secret
key encryption;  that's solved by a key expansion
algorithm.  The strength of the key then becomes
the determining issue, so doesn't matter how
long it is.

iang