Subject: AES/SHA1/Must/Should

From: Ian G <[email-masked]>
Date: Wed, 13 Apr 2005 22:06:47 +0100

Is the draft 12 the current working text?  I noticed it
expires in another month.

Did we resolve the question of whether to make changes
to the MUST / SHOULD algorithms?

I'm all in favour of saying AES-128 is now the MUST and
triple DES becomes the SHOULD.  In practice, most
implementations would be there already as they will have
done both (Cryptix Java is, and so is Perl's Crypt::OpenPGP).

SHA is harder as we've discussed.  If we agree to leave
matters lie, then here's one potential addition to 13
(I cribbed the wording from the other points, but any
wording could be considered....):

13. Security Considerations  - suggested addition

* In October 2004, the Shandong university team of Wang, Yin, Yu
announced attacks on reduced rounds of SHA1.  Collisions are
predicted in 2^69 steps rather than the full 2^80 steps.  For this
reason SHA1 is widely expected to be deprecated in coming years.
Implementors may prefer to move to wider length SHA algorithms
as appropriate.

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

---

From: David Shaw <[email-masked]>
Date: Wed, 13 Apr 2005 17:51:45 -0400

> done both (Cryptix Java is, and so is Perl's Crypt::OpenPGP).

I don't have a very strong feeling one way or another on making
AES-128 a MUST.  However, I have a very strong feeling against
changing the status of 3DES.

There are too many years and too many implementations where 3DES is
the algorithm of last resort, and changing 3DES to a SHOULD
necessitates a different algorithm of last resort.  We cannot change
that overnight.

By all means, add some new MUSTs to start the algorithm changing
process, but 3DES needs to stay as MUST as well for a good long time.

I recommend not making any change in default algorithms for 2440bis.
If and when we take up v5 keys, we can easily set the cipher of last
resort for v5 keys to something other than 3DES.

David

---

From: Jon Callas <[email-masked]>
Date: Fri, 15 Apr 2005 10:41:12 -0700

> process, but 3DES needs to stay as MUST as well for a good long time.

I understand how you feel. I feel the same way. However, I have a 
question to ask:

When? How long is "a good long time"? Forever?

The counter-argument is that there is no better time than now. The 
reasons to keep 3DES there only get stronger as time goes on. This 
problem becomes worse with time, not better.

	Jon

---

From: Ian G <[email-masked]>
Date: Fri, 15 Apr 2005 20:09:12 +0100

>> necessitates a different algorithm of last resort.  We cannot change

I think there is a big difference between what the
implementations do, and what the standard says.  If
there is an issue in the short term, then implementations
are free to ignore the standard.  It's not as if anyone
ever lost a contract because they couldn't prove absolute
compliance with the standard.

In this happy state of affairs, I am not sure why we
cannot (as a standards body) wiggle our fingers with
fierceness about 3DES and have the implementations
broadly ignore us for many months or even years...

Is the "algorithm of last resort" actually specified
in the draft RFC, is it?

If an implementation
chooses 3DES as its algorithm of last resort, that doesn't
need to change.  It just seems likely that in a couple
of years or so, AES would make more sense for that decision.

 > resort for v5 keys to something other than 3DES.

The issue I see with that is that this group has been
working for ... 8 years?  and hasn't got a standard
out.  I'd love to see some action on a v5 key layout,
but I don't have much hope.

iang

---

From: David Shaw <[email-masked]>
Date: Fri, 15 Apr 2005 16:32:32 -0400

> broadly ignore us for many months or even years...

If we mean it, put it in the standard.  If we don't, then don't put it
in the standard.  No need for wink-wink with implementations.  This is
a pretty straightforward issue.  Even before 2440, in 2440, and until
today, 3DES has been the algorithm of last resort.  There are a
significant number of deployed systems that base their behavior on
that design.  You can't declare a flag day after which the algorithm
of last resort is different without causing incompatibility.

Where comes this desire to remove 3DES?  Are there any new attacks
that raise the desire to dispose of it?  The only complaint I can see
with 3DES is that it's *slow*.  Not that it's insecure.

> Is the "algorithm of last resort" actually specified

Section 12.1:

   Since TripleDES is the MUST-implement algorithm, if it is not
   explicitly in the list, it is tacitly at the end. However, it is
   good form to place it there explicitly. Note also that if an
   implementation does not implement the preference, then it is
   implicitly a TripleDES-only implementation.

   An implementation MUST NOT use a symmetric algorithm that is not in
   the recipient's preference list. When encrypting to more than one
   recipient, the implementation finds a suitable algorithm by taking
   the intersection of the preferences of the recipients. Note that
   the MUST-implement algorithm, TripleDES, ensures that the intersection
   is not null. The implementation may use any mechanism to pick an
   algorithm in the intersection.

> of years or so, AES would make more sense for that decision.

So add AES as a MUST implement to get it out there, and then in a few
years we can revisit what the algorithm of last resort is.  Just leave
poor 3DES alone.

David

---

From: David Shaw <[email-masked]>
Date: Fri, 15 Apr 2005 17:02:08 -0400

> When? How long is "a good long time"? Forever?

I'd say "a good long time" is more than 2, but less than 5 years.  I
base this on the surprising number of requests I still get to help get
GnuPG working with PGP 5 and PGP 6.  There are people using these old
programs every day, (naturally installed years earlier, by someone who
no longer works there), and making this change would wreak all sorts
of havoc for these poor folks.  A AES-is-default program can pretty
easily send them a message they cannot decrypt.

Changing the algorithm of last resort from 3DES sets up some cases of
incompatibility with PGP 6 and earlier, and GnuPG 1.0.3 and earlier on
one side, and modern versions on the other.  It's easy to say that
people shouldn't be using these versions any longer (and I say that
often), but they are.

> problem becomes worse with time, not better.

I agree.  That's why I'd like to sidestep the problem and change the
algorithm of last resort as part of a v5 key.  There are no
compatibility problems then, as we're changing new keys, and not
retroactively changing the meaning of old keys.

Basically, I'm thinking this: given that it'll take a few years to
change from 3DES, and given that we must change the default hash away
from SHA-1 within the next few years, and given the Mister/Zuccherato
attack, and given the desire to publish 2440bis already, why not kill
a whole bunch of birds with one stone?  Finish up 2440bis, publish it,
then sit down and design v5.

I'd probably feel differently about all this if 3DES was broken in
some way, but it's not broken.  It's just slow.

David

---

From: Ian G <[email-masked]>
Date: Fri, 15 Apr 2005 22:34:02 +0100

> with 3DES is that it's *slow*.  Not that it's insecure.

Well, it is not "remove 3DES" but rather move over to
AES.  The attacks that were mentioned are the ones based
on the birthday attack, I do not know the details, but
it is based on the block size being too small.  This
is not a validated threat but it is a signal to start
moving to a bigger block size, being 16 bytes.

>    implicitly a TripleDES-only implementation.

OK, so if we add AES as a MUST algorithm, leaving TripleDES
in place as a MUST also, then that paragraph needs to be
clarified.

Possibly:

    Since TripleDES and AES are MUST-implement algorithms,
    if they are not explicitly in the list, they are implied
    to be at the end.  However, it is good form to place the
    algorithms there explicitly, and as algorithms may be
    reduced in status from MUST to SHOULD in the future,
    this is highly recommended.  Note also that if an
    implementation does not implement the preference, then
    it implicitly implements the MUST algorithms.

Hmmm... that's getting clumsy.  I'd say that such a default
should be deprecated, if possible:

Is there any good reason why implementations shouldn't
implement the preference?  Are there any implementations
that do not implement the preference?

Also, is there any good reason to imply the MUST algorithms
into the list?  Obviously there are implementations that
do this.  But why not just deprecate that implication and
say that implementations MUST include all their preferences,
with a footnote that older implementations may implicitly
assume TripleDES at the end of the list?

How about:

     At least one MUST-implement algorithm SHOULD be in the
     list.

     Older implementations may deliver an empty list, and may
     imply TripleDES at the end of the list.  This behaviour
     is deprecated.

> years we can revisit what the algorithm of last resort is.  Just leave

OK, so at least we seem to have consensus on adding AES
as a MUST algorithm.  Anyone else demur?

iang

---

From: David Shaw <[email-masked]>
Date: Fri, 15 Apr 2005 22:50:42 -0400

>     imply TripleDES at the end of the list.  This behaviour

I think this is overcomplicated.  There is no way to phrase this that
is safe for old implementations - if a new implementation uses AES
instead of 3DES, older implementations lose.

Here is what I propose.  It doesn't really matter right now whether
AES becomes the default in a v5 key format or by a future revision to
v4.  Either way, this change is safe:

1) In section 9.2, change AES from a SHOULD to a MUST.

2) In section 12.1, change

this:
   Since TripleDES is the MUST-implement algorithm, if it is not
   explicitly in the list, it is tacitly at the end.

to this:
   TripleDES is the current default OpenPGP algorithm, so if it is not
   explicitly in the list, it is tacitly at the end.

and this:
   Note that the MUST-implement algorithm, TripleDES, ensures
   that the intersection is not null.

to this:
   Note that the current default algorithm, TripleDES, ensures that the
   intersection is not null.

or other text amounting to the same thing.  The reason for this change
is that the current text refers to TripleDES as the only
MUST-implement algorithm.  If we add AES as another MUST, this text is
no longer correct.

End result is to leave 3DES as the default, and make AES a MUST.  In n
years, we'll either have v5 keys or can just redefine v4.  Either way,
we've laid the groundwork.

David

---

From: Ian G <[email-masked]>
Date: Sat, 16 Apr 2005 10:38:53 +0100

> instead of 3DES, older implementations lose.

Exactly, this is the problem with having both a list
of algorithms and also implicit defaults.  One should
have one or the other, IMHO, not both, unless one is
seeking revenge on coders for unimaginable crimes long
past.

>    explicitly in the list, it is tacitly at the end.

Right, so TripleDES remains a default, but the
status of default is delinked from the MUST status.

AES becomes a MUST, but is not a default.

>    intersection is not null.

Looks good.

The only question I would have is whether (in v4) we
would continue to assume the presence of a default
algorithm.  If we are agreed that defaults are a
bad thing, then some warning should be put in there
to suggest all new keys should include their full
list.  Alternatively, I suggest we bite the bullet
and state that TripleDES is the default and that
will never change (in v4).

> we've laid the groundwork.

OK, so your view would be "in v4, TripleDES is a
default and a MUST and that should not change."

Fair enough.

iang

---

From: David Shaw <[email-masked]>
Date: Thu, 21 Apr 2005 23:55:48 -0400

> default and a MUST and that should not change."

Not exactly what I'm saying, but close.

What I'm saying is, "Don't change it overnight.  If we can do this as
part of a v5 key, great.  If we must do it in v4, then give warning
about the upcoming for the change for a year or three first."

My suggested change for 2440bis works with either of those two cases.

David