Subject: RE: [ietf-dkim] Supporting alternate algorithms

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 20 Feb 2006 13:34:50 -0800

> [mailto:[email-masked]] On Behalf Of Dave Crocker

> 1. I can't guess what you interpreted as "frightening" in my 
> characterization. 
> All I did was note your own reference to a 5-year timeframe 
> and the lack of our having any details about what would be 
> chosen by then. As for vagueness, the lack of detail could 
> hardly be characterized otherwise.

Actually I think it is very clear what we will be using in 5 years time,
either what we are using today or the NSA suite B with the possible
replacement of the hash algorithm.

A better question would be 'do we know how to manage the trasition from
one algortihm to another'. That is what has never been effectively
acomplished in the field to date.

> In other words, you think it appropriate to *require* that 
> all signers *always* 
> use SHA-256?
> 
> This would mean, for example, that support for the next, 
> preferred algorithm, 
> would require revising and re-issuing the specification.

This is actually a problem across all the IETF security specs and across
all the standards organizations. What we really need is a WG that
describes how to deploy a replacement crypto set across the board.

Having discussed this issue with the cryptographers the clear consensus
there is that the announced weaknesses in SHA-1 almost certainly affect
SHA-256 and that we should be looking for hash functions designed on
different principles rather than promoting SHA-256 as a cure.

Even with the known compromise SHA-1 is considerably stronger than the
RSA keys we are expecting to use. Break the hash and you may be able to
fake one bit in one document. Factoring the RSA key is less work and
allows you to sign any document you like.

It is not rational to be obsessing about SHA256 when we have bigger
problems with RSA. If it was not for the patent issues I would push for
ECC as per suite B.

_______________________________________________
NOTE WELL: This list operates according to 
http://dkim.org/ietf-list-rules.html

---

From: "Daniel Dreymann" <[email-masked]>
Date: Mon, 20 Feb 2006 15:09:27 -0800

> different principles rather than promoting SHA-256 as a cure.

I concur. Last week I used the opportunity of the RSA conference to conduct
an informal survey with many of the world's best known cryptographers. They
have no evidence that SHA-256 is more than marginally better than SHA-1. The
consensus was that SHA-1 can still be used in the next few years, and that
when looking for a replacement we have to look beyond SHA-256.

Daniel

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 20 Feb 2006 23:32:59 +0000

While I wouldn't quibble with anyone's position on whether sha-1 is
still ok, or whether sha-256 is interestingly stronger, (not being
qualified myself), I do think the place from which DKIM ought to
accept guidance is the saag.

The saag minutes [1] from Vancouver contain the following:

  Security Area Response to Hash Function Breaks
      Russ said we should "walk, not run."  This is not a problem yet
      but as attacks are improved it will become a problem.  NIST held
      a hash workshop.  Conclusions from that workshop include a
      reminder that SHA-1 will reach end-of-life  for digital signatures
      by 2010.  Also, we cannot expect any new standardized hash
      functions before then.  The security ADs have decided that we need
      to transition to sha-256 now.  There will probably be a later
      transition to something new after it is developed.  So, we need
      to become good at transitions as we have at least two.
      Protocols with active WGs will be analyzed within those WGs;
      others in SAAG.

  Directives to WGs/Chairs:
       Do analysis on every protocol in the WG by IETF 65
       Start standards work on transition to sha-256, but plan for
       future transitions.

So, I'd encourage folks who want to debate algorithm specifics to do so
on the saag list, where such discussion is more appropriate and where
there is more expertise available. (And so the discussion can be
repeated less often:-)

For DKIM, I think we ought to try to take action as per the above,
but, in the knowledge that things can, and do, change, so the more
agile we can be, as a group, and in terms of the specs we write, the
better.

If there's an argument that DKIM should not follow saag's line on
this, then that of course would be appropriate to discuss, but I
find it hard to see what's that different about DKIM in this respect.

Stephen.

[1] http://www3.ietf.org/proceedings/05nov/saag.html

---

From: Dave Crocker <[email-masked]>
Date: Mon, 20 Feb 2006 15:52:08 -0800

> accept guidance is the saag.

Is there some reason that the DKIM working group needs to spend much effort 
discussing the details of the preferred algorithm?  I would think that that is 
primarily a recommendation to be made by the security community.

The DKIM WG must to specify a choice of specific algorithms, of course, but the 
design of DKIM and the specification of its mechanism for labeling its 
algorithms is fully flexible.  The spec document can plug in any algorithm that 
the IETF security community recommends.

That is,

1. DKIM needs to have a mechanism that permits specifying alternative 
algorithms.  And it already does. So that requirement is already satisfied.

2. DKIM needs to specify a requirement for signer and validator support of a 
core sets of algorithms, where a set may have a single member or multiple. It 
already does, but clearly one or more of the sets need to be changed.

3. The DKIM working group needs to worry about things like cost of the 
algorithms, availability of implementations for them, impact on backward 
compatibility, transition, and so on.  But I am failing to see why this group 
needs to put energy into discussing the relative merits of different algorithm's 
strength or lifespan.

4. On the matter of backward compatibility and transition, there has been some 
recommended text.  As nearly as I can tell, it did not get pursued or resolved.

No doubt, I am missing something fundamental that requires that we focus on the 
level of detail that occurs every time a thread touches algorithm choice, but I 
am not seeing what it is.  Can someone explain how and why this is where we 
should be putting our energy?

d/

-- 

Dave Crocker
Brandenburg InternetWorking
<http://bbiw.net>
_______________________________________________
NOTE WELL: This list operates according to 
http://dkim.org/ietf-list-rules.html

---

From: Jon Callas <[email-masked]>
Date: Wed, 22 Feb 2006 10:49:58 -0800

> replacement of the hash algorithm.

I think it will take longer than five years, but it's still coming.

> acomplished in the field to date.

On the contrary, it's been done a number of times. The OpenPGP world  
migrated away from MD5 in '97-99. It migrated away from RSA, and then  
back to it. It's doing just fine now migrating away from SHA-1. It's  
just a matter of having the right hooks in there. There are plenty of  
other places where you're right and the places where it has been  
badly handled outnumber the ones where it has been done well. But  
that's not 'never.'

This is a software engineering issue, not a crypto issue.

> problems with RSA. If it was not for the patent issues I would push  

I think 3k-4k RSA will be with us for a long, long time. But I do  
agree with the basic premise, that patent issues are a stumbling  
block to suite B. Fortunately, I don't think we'll *need* suite B  
until those are not issues.

I would not object at all to just biting the bullet and saying we're  
going to use SHA-256 now. But on the other hand, dealing with both  
SHA-1 and SHA-256 now will force the software engineering flexibility  
in place, and that will be good when the hash we want to use is  
finally invented.

	Jon

_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Jon Callas <[email-masked]>
Date: Wed, 22 Feb 2006 11:56:24 -0800

> when looking for a replacement we have to look beyond SHA-256.

Well, you didn't ask me, and I think I can arrogate my way into that  
set without causing Senate investigations into abuses of power. :-)  
On the other hand, I've been pretty vocal with my opinions, so  
information-theoretically, there would have been no information in  
asking me. Heck, when Russ said, "walk, don't run," he was quoting me.

It matters a lot on who you ask and what you ask them. Let me give an  
example. Last fall at the NIST hash bash, a respected hash designer  
said that if we tripled the number of rounds in SHA-1, we'd all feel  
much better about its security than we do about SHA-256.

I agree with this statement. I think it is a wise and subtle thing  
that says a lot about algorithm design and its challenges. On the  
other hand, it also misses a very important point. I got up and said  
that I agree completely, but --- SHA-1 has 80 bits of security. With  
an infinite number of rounds it will have only 80 bits of security.  
Does this mean that we think that SHA-256 has *less* than 80 bits of  
security? No one said they think that SHA-256 has less than 80 bits  
of security. I went on a limb and said that my guess from licking my  
finger and sticking it in the wind is that SHA-256 has 90-110 bits of  
security. (Today, I feel less good about the 110, but it's still not  
daft.) If you have to pick an algorithm *today*, then SHA-256 is your  
best choice. (Note that I said "best" and not "good." Part of  
understanding the mess we're in is understanding that "best" does not  
mean "good." Donn Parker has a great rant on why we all should stop  
talking about Best Practices.) This is the difference between a  
cryptographer who is an algorithm designer and a cryptographer who is  
an engineer. I'm an engineer. I have to choose something.

Okay, that consensus you described is something that I also agree  
completely with. SHA-1 is okay to use right now, and we need to look  
beyond SHA-256.

I also agree with the statement that you don't have to worry about  
crop failure because next year there will be a new growing season. It  
is a wise an beautiful statement --- and also utterly missing the  
point, if you happen to be caught in the intervening food shortage.

Engineering is the art and discipline of applying science and  
mathematics within constraints. These constraints include time,  
money, effort, and the laws of nature. When we engineers have to  
select a hash function, our non-daft options include SHA-1, SHA-256,  
SHA-512, Whirlpool, and even Tiger. The *best* solution is to  
parameterize the heck out of the protocol; allow SHA-1, encourage  
SHA-256, hope you don't have to go to SHA-512, and put in MAYs for  
Whirlpool, Tiger, and maybe other outré things slipping my mind so  
that we don't have to go to lots of trouble discussing them. And then  
we get on with our lives, and deal with the Godot Hash when it arrives.

There are many obvious tweaks to this strategy. Most of them have  
very good reasons for why you might want to make that tweak. But you  
get my gist.

	Jon