Subject: A question on Twofish / AES / PGP

From: "Simpson, Sam" <[email-masked]>
Date: Mon, 8 Mar 1999 16:48:04 +0000

(hmmm. This isn't good etiquette, start reading a list one minute
and posting the next - but hopefully you'll all agree this is
'on-topic' for this list?).

First a mesage I sent (earlier today to the PGP-Users mailing
list):

It has previously been mentioned that Twofish would be added to
PGP before completion of the AES process.  I think everyone would
agree that the move to a 128-bit block, 128/192/256-bit key
cipher is a Good Thing, but the point of this message is to ask
"why the choice of Twofish?"

Is strength (or "expected strength" at this stage) the criteria? 
If you're going to select a cipher from the x candidates (many of
which, including Twofish, have only had 8 months peer-review)
then surely you would go for the most ultra-conservative design? 
Even better, wouldn't you select a cipher which has been analysed
for a longer period?

Is speed a selection criteria for block ciphers in PGP (if so why
3DES <g>)?

Is heritage the criteria?  If so, there are other candidates with
a similar heritage: MARS (Coppersmith) , RC6 (Rivest), Serpent
(Anderson, Biham & Knudsen), Rijndael (Daemen & Rijmen), DFC
(Vaudenay), CAST-256 (Adams) etc.

Are patent issues part of the criteria?  We would expect so (in
view of IETF views on this matter and the OpenPGP standard). 
This potentially discounts RC6 & MARS and one or two others.

Are some of the more obscure (and of little practical importance
in PGP?) criteria being considered?  For example: key agility,
resistance to timing / power analysis, smart card / hardware
implementation, scalability to 64-bit architectures.

I am a great fan of Bruce Schneier (and Twofish actually) - but
isn't it to soon jump on the bandwagon?  One notes that Twofish
has received some criticism in AES Conference II papers:

  1) "Report on the AES Candidates" by Vaudenay et al.  Points
out that S-Boxes should "no longer be called key-dependant". Also
says "consists of a collection of patches" & "we do not think
this design comes from deep investigation".  Of course, this
paper is written by the authors of another AES candidate.

  2) "An observation on the Key Schedule of Twofish" by Mirza &
Murphy (RHBNC), points out several deficiencies with the key
schedule.  Implications unknown, but it does directly contradict
implicit claims in the original Twofish paper.

*None* of the candidates escaped criticism from a "cryptographic
security" point of view, but if one wanted to objectively select
an AES candidate by any combination of the above criteria, would
we logically select Twofish at the moment?

My main concern is that naive users will see "Twofish" &
"Schneier" and create keys specifying this algorithm.  Sure, the
User Manual will no doubt state "Twofish is new blah blah blah"
but, in my experience, users never RTFM anyway.

I hope NAI employees don't see this is as a criticism of them (I
have nothing but respect for you guys).  Rather, I suspect I'm
missing something quite obvious...

Then someone pointed me to your archives and I had a read through
the posts referring to Twofish.... So my follow-up is:

I'm even less convinced now.  The Twofish topic seems to have
started with the comment "because Twofish is one of most
promising candidates for AES".  People don't seem to have
challenged this statement (or even discussed it!).  Is Twofish
one of the most promising?  By what metric?  Is it that much
better than all of the other candidates that you should run with
it now?  Really?  Even after the recent AES Conference II papers?

Even worse there was the comment (I'm not going to publish e-mail
addresses to save embarrassment!): "I suggest *replacing*
Blowfish with Twofish. If you trust one, why not the other?"

Extremely naive!  Blowfish and Twofish are radically different
(ok - they are both BFN etc and the key schedule consists of
iterations of a function used in encryption, but come on!). 
Years of analysis and faith in Blowfish certainly does not carry
forward to Twofish.

Small changes in block ciphers can move a cipher from "thought to
be secure" to "trivially" broken.

I don't want to "throw a Sternlight" on this point - but frankly
I am concerned.

Please be gentle with replies :-)

Sam Simpson
Communications Analyst
- -- http://www.scramdisk.clara.net/ for ScramDisk hard-drive
encryption & Delphi Crypto Components.  PGP Keys available at the
same site.

---

From: "William H. Geiger III" <[email-masked]>
Date: Mon, 08 Mar 1999 12:23:06 -0600

In <[email-masked]>, on 03/08/99 
   at 11:48 AM, "Simpson, Sam" <[email-masked]> said:

>I don't want to "throw a Sternlight" on this point - but frankly I am
>concerned.

Well IMHO we have enough good symetric cyphers in there right now:

 9.2. Symmetric Key Algorithms 
 
        ID           Algorithm 
        --           ---------
        0          - Plaintext or unencrypted data 
        1          - IDEA [IDEA]
        2          - Triple-DES (DES-EDE, as per spec - 
                     168 bit key derived from 192)
        3          - CAST5 (128 bit key, as per RFC 2144)
        4          - Blowfish (128 bit key, 16 rounds) [BLOWFISH]
        5          - SAFER-SK128 (13 rounds) [SAFER]
        6          - Reserved for DES/SK
        7          - Reserved for AES with 128-bit key 
        8          - Reserved for AES with 192-bit key 
        9          - Reserved for AES with 256-bit key 
        100 to 110 - Private/Experimental algorithm.
 
    Implementations MUST implement Triple-DES. Implementations SHOULD 
    implement IDEA and CAST5.Implementations MAY implement any other 
    algorithm.

But then again everyone has their pet algorithm that they want to put into
the code. Code ranges from 100 to 110 are reserved for
private/experimental algorithms and that is where twofish and the rest
should go. Unfortunately if NAI decides to start using ID #10 for twofish
there is very little the rest of us can do about it (as seen with the
PhotoID). I have asked several times for us to establish a formal
mechanism for assigning ID numbers, as it stands now it is first come
first serve.

-- 
---------------------------------------------------------------
William H. Geiger III  http://www.openpgp.net
Geiger Consulting    Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 5.0 at: http://www.openpgp.net/pgp.html
Talk About PGP on IRC EFNet Channel: #pgp Nick: whgiii
---------------------------------------------------------------

---

From: Werner Koch <[email-masked]>
Date: Mon, 8 Mar 1999 19:38:47 +0100

> "why the choice of Twofish?"

Twofish has not been chossen as the AES algorithm for OpenPGP but 
just as another optional algorithm.  The only required algorithm
is 3DES - all others are optional.  Leaving out CAST5, there are only
two other algorithms:  IDEA which can't be used due to patent
restrictions and Blowfish which has a someone strange design but is
much faster than 3DES.  According to Schneier, we should replace
Blowfish by Twofish right now because he (and others too) trusts
Thwofish more.  The algorithm identifiers for AES are still reserved.

Anayway it it optional and noone is required to implement it.  The
preference system gives every user/implementor a chance to disallow
optional algorithms. 

> "Schneier" and create keys specifying this algorithm.  Sure, the

How can a user create keys?  The symmetric ciphers are only used for 
session keys and if you have the requirement for really secure
encryption you won't use PK but use 2 symmetric algorithms in turn
with 2 randomly created passphrases.

More on AES in 2 weeks.

-- 
Werner Koch at guug.de           www.gnupg.org           keyid 621CC013

---

From: Werner Koch <[email-masked]>
Date: Mon, 8 Mar 1999 20:26:18 +0100

> PhotoID). I have asked several times for us to establish a formal

These are different stories.  We discussed Twofish here on my request
and agreed to use id 10 for it.  

How the PhotoID or the split key mechanism works has not been
discussed here (afaik).

---

From: Jon Callas <[email-masked]>
Date: Mon, 08 Mar 1999 17:11:24 -0800

At 04:48 PM 3/8/99 +0000, Simpson, Sam wrote:

|It has previously been mentioned that Twofish would be added to
|PGP before completion of the AES process.  I think everyone would
|agree that the move to a 128-bit block, 128/192/256-bit key
|cipher is a Good Thing, but the point of this message is to ask
|"why the choice of Twofish?"

That's an over-simplification of what has happened.

Two groups of developers, the NAI/PGP group and the GNU Privacy Guard
group, have each said that they want to put Twofish into their
implementations. If there was only one group who wanted to do this, the
proper thing for them to do is use the experimental/private range. (By the
bye, this was my opinion at NAI.) However, when two groups want to do the
same thing, and they both come to the working group, the working group
should do something.

We exist as a working group to foster interoperability between
implementors. If two groups of implementors want Twofish, we ought to
oblige them. Or at least consider it. 

As part of that consideration, one thing to remember is that in OpenPGP, we
spcifically designed the protocol so that the receiver decides which
algorithms they accept. When we did that, we didn't have all the new AES
algorithms as examples of tempting, but controversial algorithms. I pushed
the point myself with the ROT-N algorithm. OpenPGP is safe from
controversial algorithms because of the algorithm negotiation procedure. If
you don't want to use Twofish, you don't have to. It's that simple.

|Even worse there was the comment (I'm not going to publish e-mail
|addresses to save embarrassment!): "I suggest *replacing*
|Blowfish with Twofish. If you trust one, why not the other?"

Well, that suggestion didn't make the consensus. Thanks for agreeing with
consensus.

By the bye, thanks for your observations. They're quite lucid, and provide
a good analysis of why an individual might not want to use Twofish.
However, it's still attractive enough of an algorithm to have some
groundswell behind it, and it's that support the working group responds to.
It is indeed possible that in a year we will deprecate the identifier.
(Heck, it's possible that in two weeks we'll deprecate it.) But it does
seem like a reasonable thing to permit, here in the early part of 1999. If
you disagree strongly, and believe that the consensus has gone the wrong
way, keep arguing! It's not too late to change people's minds. We're
listening.

	Jon

-----
Jon Callas                                  [email-masked]
CTO, Total Network Security                 3965 Freedom Circle
Network Associates, Inc.                    Santa Clara, CA 95054
(408) 346-5860                              
Fingerprints: D1EC 3C51 FCB1 67F8 4345 4A04 7DF9 C2E6 F129 27A9 (DSS)
              665B 797F 37D1 C240 53AC 6D87 3A60 4628           (RSA)