Subject: [ietf-dkim] Deployment Scenario 7: Cryptographic Upgrade and Downgrade Attacks

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 23 Feb 2007 10:54:24 -0800

Issue 1386:

Deployment Scenario 7: Cryptographic Upgrade and Downgrade Attacks

In the case that a signer advertises key records for multiple signature algorithms this may allow an attacker to circumvent an insufficiently expressive signature policy.

Example: 

Legitimate sender advertises key records A, B. Record A describes a signature key for a widely supported signature algorithm. Record B describes a signature key for a signature algorithm that is not generally supported. The senders signature policy says 'I always sign every message'. The sender always signs messages with algorithm A (whether algorithm B is used by the legitimate sender as an additional algorithm or not does not affect the success of the attack).

[Such a situation will inevitably arise any time that there is a transition from one signature algorithm to another. If policy is to have any utility it must be possible to complete such a transition without negating the value of the policy during the transition]

Mallet creates an entirely bogus message M and creates a false signature using only algorithm B.

A recipient of the message that supports algorithm B is capable of determining that the message signature is false and that the message is not in compliance with the signature policy.

A message recipient that only supports algorithm A is unable to verify the signature and determine that it is fake. The recipient is thus unable to determine that the message is in compliance even though the recipient is perfectly capable of checking the signature on every legitimate message sent.

In order to twart the attack the policy language must be sufficiently expressive to allow the sender to describe their actual signature policy 'I always sign with algorithm A and with algorithm B'.

Since we would like to confine considerations such as signature, canonicalization algorithms to the key records the natural mechanism for expressing this policy is to state restrictions on the key selectors. The sender organizes key records into groups such as xxx.alg-a.example.com and xxx.alg-b.example.com.

NOTES

The statement that 'invalid signatures are treated as unsigned' still applies when policy is advertised. The purpose of policy is to allow a recipient to draw inferences from the lack of a signature. So it is incorrect to say that the attack does not matter because invalid is the same as unsigned. The point here is that by ADDING a bogus signature the attacker is able to ensure that their message is considered to be compliant with the signature policy when it is not.

The outcomes for DKIM without policy are 'VALID SIGNATURE' and 'NO VALID SIGNATURE' where the latter includes no signature at all and an invalid signature.

The point of policy is to allow the legitimate sender to divide the 'NO VALID SIGNATURE' outcome into 'CONSISTENT' and 'INCONSISTENT'. There is no value to deploying policy unless you can reliably discriminate between more actionable outcomes than you can without policy.

Further the attack becomes possible as soon as the legitimate sender advertises a record for the new algorithm. What this means is that as soon as the legitimate sender advertises the record for algorithm B their policy record becomes vulnerable to attack. It is higly unlikely that the legitimate sender is going to ever migrate algorithms under these circumstances and thus as far as I am concerned policy does not meet the requirement for algorithm agility unless it is possible for a recipient to determine that even though the signer supports other algorithms there is a signature that can be checked.

There is also a downgrade attack using essentially the same principle except that in this case algorithm A is actually broken and Algorithm B has a sunstantial amount of deployment. Instead of creating a nonsense signature that will fail validation the attacker forges a valid signature for the untrustworthy algorithm.

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

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 23 Feb 2007 11:35:49 -0800

In general, I agree with Phill that this is a requirement. Please do 
not take my disagreements below as negating the need for the section 
and for the policy language to be able to express signing algorithm 
usage.

At 10:54 AM -0800 2/23/07, Hallam-Baker, Phillip wrote:
>In the case that a signer advertises key records for multiple 
>signature algorithms this may allow an attacker to circumvent an 
>insufficiently expressive signature policy.
>
>Example:
>
>Legitimate sender advertises key records A, B. Record A describes a 
>signature key for a widely supported signature algorithm. Record B 
>describes a signature key for a signature algorithm that is not 
>generally supported. The senders signature policy says 'I always 
>sign every message'. The sender always signs messages with algorithm 
>A (whether algorithm B is used by the legitimate sender as an 
>additional algorithm or not does not affect the success of the 
>attack).
>
>[Such a situation will inevitably arise any time that there is a 
>transition from one signature algorithm to another. If policy is to 
>have any utility it must be possible to complete such a transition 
>without negating the value of the policy during the transition]
>
>A recipient of the message that supports algorithm B is capable of 
>determining that the message signature is false and that the message 
>is not in compliance with the signature policy.
>
>A message recipient that only supports algorithm A is unable to 
>verify the signature and determine that it is fake. The recipient is 
>thus unable to determine that the message is in compliance even 
>though the recipient is perfectly capable of checking the signature 
>on every legitimate message sent.

+1 to all the above.

>In order to twart the attack the policy language must be 
>sufficiently expressive to allow the sender to describe their actual 
>signature policy 'I always sign with algorithm A and with algorithm 
>B'.

This would be better worded as: In order to twart the attack, the 
policy language must be sufficiently expressive to allow the sender 
to describe their actual signature policy, such as 'I sign only with 
algorithm A' or 'I sign with both algorithm A and algorithm B'.

>Since we would like to confine considerations such as signature, 
>canonicalization algorithms to the key records the natural mechanism 
>for expressing this policy is to state restrictions on the key 
>selectors. The sender organizes key records into groups such as 
>xxx.alg-a.example.com and xxx.alg-b.example.com.

This is unnecessary here; there are other ways for a sender to group 
their keys. We are only talking about the policy statements in this 
document.

>NOTES
>
>The statement that 'invalid signatures are treated as unsigned' 
>still applies when policy is advertised. The purpose of policy is to 
>allow a recipient to draw inferences from the lack of a signature. 
>So it is incorrect to say that the attack does not matter because 
>invalid is the same as unsigned. The point here is that by ADDING a 
>bogus signature the attacker is able to ensure that their message is 
>considered to be compliant with the signature policy when it is not.

+1

>The outcomes for DKIM without policy are 'VALID SIGNATURE' and 'NO 
>VALID SIGNATURE' where the latter includes no signature at all and 
>an invalid signature.
>
>The point of policy is to allow the legitimate sender to divide the 
>'NO VALID SIGNATURE' outcome into 'CONSISTENT' and 'INCONSISTENT'. 
>There is no value to deploying policy unless you can reliably 
>discriminate between more actionable outcomes than you can without 
>policy.

These two paragraphs are quite important, and should be in the 
introduction of the document, not in this section.

>Further the attack becomes possible as soon as the legitimate sender 
>advertises a record for the new algorithm.

Yes.

>What this means is that as soon as the legitimate sender advertises 
>the record for algorithm B their policy record becomes vulnerable to 
>attack.

No. The policy record is not vulnerable: the messages are.

>It is higly unlikely that the legitimate sender is going to ever 
>migrate algorithms under these circumstances and thus as far as I am 
>concerned policy does not meet the requirement for algorithm agility 
>unless it is possible for a recipient to determine that even though 
>the signer supports other algorithms there is a signature that can 
>be checked.

Predicting what a sender will or will not do when faced with multiple 
signing algorithms is silly and does not belong in this document.

>There is also a downgrade attack using essentially the same 
>principle except that in this case algorithm A is actually broken 
>and Algorithm B has a sunstantial amount of deployment. Instead of 
>creating a nonsense signature that will fail validation the attacker 
>forges a valid signature for the untrustworthy algorithm.

Correct.

--Paul Hoffman, Director
--Domain Assurance Council
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Dave Crocker <[email-masked]>
Date: Fri, 23 Feb 2007 12:09:14 -0800

>> generally supported. The senders signature policy says 'I always sign 
>> every message'. The sender always signs messages with algorithm A 
>> (whether algorithm B is used by the legitimate sender as an additional 
>> algorithm or not does not affect the success of the attack).

Color me confused.  I thought we agreed long ago that downgrade attacks were 
not an issue for the problem DKIM addresses.

In general, there are myriad ways to break a signed message, to render the 
signature invalid.  We have chosen not to attempt to prevent breakage.

More basically, we are moving quickly into the morass of requiring SSP lookups 
for signed messages, rather than limiting SSP for use with unsigned messages.

Besides the technical hassle of adding overhead, this also means that current 
potential adopters of DKIM will see DKIM -base use as remaining unstable.  And 
I hope folks do not understimate the danger from this, because it has already 
been a point of discussion in industry meetings among potential adopters.

There is a very simple distinction we can make:

    If a message is signed, then the signature (and associated key 
information) speaks for itself.  If the organization has constraints on who is 
allowed to sign a message or what message they are allowed to sign, or what 
algorithms they are supposed to use, then that is a matter for internal 
management within the organization.  It is not the job of a public standard to 
recruit a recipient into enforcing sender-side internal administrative 
policies.  If an organization chooses to publish support for a weak algorithm, 
again, that is their problem, not the recipient's.

    Hence, SSP should be used for receipt of unsigned messages.  Statements 
like "I sign everything" and "I send no mail" are examples.

d/

-- 

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

---

From: Hector Santos <[email-masked]>
Date: Fri, 23 Feb 2007 15:42:30 -0500

Dave Crocker wrote:
> information) speaks for itself.  If the organization has constraints on 
> who is allowed to sign a message or what message they are allowed to 
> sign, or what algorithms they are supposed to use, then that is a matter 
> for internal management within the organization.  It is not the job of a 
> public standard to recruit a recipient into enforcing sender-side 
> internal administrative policies.  If an organization chooses to publish 
> support for a weak algorithm, again, that is their problem, not the 
> recipient's.

Whoa, whoever convinced or turned your head, I want to thank them.

Metaphorically, throw everything out the window and just consider the 
avalanche of mail a system has to process.  If DKIM is going to "raise 
the bar" then it better had some chutzpah behind it.  IOW, the only way, 
this vendor will turn the switch on DKIM is when there is a DOMAIN 
POLICY concept behind it.

>    Hence, SSP should be used for receipt of unsigned messages.  
> Statements like "I sign everything" and "I send no mail" are examples.

These are the boundary conditions and represents, in my view, the 
highest benefits for the domains, in one way or another.  Either they do 
or they don't, and if they want a mix bag, then they MUST have a policy 
that helps categorized failures with success.

Remember, never mind DKIM, think of the amount of mail receivers have to 
process.  If they have to being to lump DKIM into the picture with some 
"special meaning" behind it then that "special meaning" better be well 
defined with a "PAYOFF."

Broken DKIM messages on a on-going basis will not be tolerated or they 
will be simply ignored altogether - no overhead will be exerted, and 
that just makes all this a waste of time.

Thanks

---
HLS

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 23 Feb 2007 13:27:13 -0800

At 12:09 PM -0800 2/23/07, Dave Crocker wrote:
>>>Legitimate sender advertises key records A, B. Record A describes 
>>>a signature key for a widely supported signature algorithm. Record 
>>>B describes a signature key for a signature algorithm that is not 
>>>sign every message'. The sender always signs messages with 
>>>algorithm A (whether algorithm B is used by the legitimate sender 
>>>as an additional algorithm or not does not affect the success of 
>>>the attack).
>
>
>Color me confused.  I thought we agreed long ago that downgrade 
>attacks were not an issue for the problem DKIM addresses.

What Phill describes is not a downgrade attack: it is an attack based 
on algorithm agility. If we allow multiple algorthims, and not all 
the algorithms are the the "MUST implement" level, this attack is 
feasible. Every protocol with algorithm agility but not a fixed list 
of "MUST implement" algorithms has this issue.

>In general, there are myriad ways to break a signed message, to 
>render the signature invalid.  We have chosen not to attempt to 
>prevent breakage.

Phill's example does not deal with breaking a signed message, nor 
rendering a signature invalid.

>More basically, we are moving quickly into the morass of requiring 
>SSP lookups for signed messages, rather than limiting SSP for use 
>with unsigned messages.

I agree that this is an example of an SSP lookup for signed messages. 
I hope it does not mean that we are opening the door for other 
purposes. It is also not requiring an SSP lookup; the only time you 
care if the message is signed with an algorithm you don't understand 
is if you know that they sign all messages. Therefore, you already 
did the SSP lookup to find out that information. The algorithm list 
would come along with the "I sign everything" information.

>Besides the technical hassle of adding overhead, this also means 
>that current potential adopters of DKIM will see DKIM -base use as 
>remaining unstable.

Only if you tell them that it is. SSP does not destabilize dkim-base.

>And I hope folks do not understimate the danger from this, because 
>it has already been a point of discussion in industry meetings among 
>potential adopters.

Fully agree.

>information) speaks for itself.  If the organization has constraints 
>on who is allowed to sign a message or what message they are allowed 
>to sign, or what algorithms they are supposed to use, then that is a 
>matter for internal management within the organization.  It is not 
>the job of a public standard to recruit a recipient into enforcing 
>sender-side internal administrative policies.  If an organization 
>chooses to publish support for a weak algorithm, again, that is 
>their problem, not the recipient's.

Fully agree.

>Statements like "I sign everything" and "I send no mail" are 

...and so is "I sign everything with Algorithm A".

--Paul Hoffman, Director

---

From: Douglas Otis <[email-masked]>
Date: Fri, 23 Feb 2007 13:40:38 -0800

> SSP lookups for signed messages, rather than limiting SSP for use  

A signed message will not necessarily bypass a need to verify an  
associated policy record.

> remaining unstable.  And I hope folks do not understimate the  
> danger from this, because it has already been a point of discussion  
> in industry meetings among potential adopters.

Early adopters still benefit from a reduction in false positive  
phishing detection.

> information) speaks for itself.

The signature/key must be handled in combination with various message  
headers containing various email-addresses.  These email-addresses  
may or may not be within the signing domain.  The header within the  
signing domain may or may not be the From header.  A mailing list  
will not be able to association with the From header, for example.

>   If the organization has constraints on who is allowed to sign a  
> message or what message they are allowed to sign, or what  
> algorithms they are supposed to use, then that is a matter for  
> internal management within the organization.

To say some header's email-address domain "Signs all" should also be  
able to deal with a transition in the algorithms used.  Such a  
transition would not only impact the signer, but also all verifiers  
as well.  When two signatures are applied as the _only_ means to  
facilitate a non-disruptive transition, which signature MUST be present?

>   It is not the job of a public standard to recruit a recipient  
> into enforcing sender-side internal administrative policies.  If an  
> organization chooses to publish support for a weak algorithm,  

There must be a benefit for the recipient.  This might be to exclude  
replay abuse when white-listing, to assure questionable DSNs, or  
assure the proper annotation of messages.

> Statements like "I sign everything" and "I send no mail" are examples.

This simplification is simply to simple to be correct.  The "I" in  
this statement implies which header?  Which policies are applied when  
there are multiple email-addresses used within the "I" header, such  
as those to be found with EAI, as example?

-Doug

---

From: Dave Crocker <[email-masked]>
Date: Fri, 23 Feb 2007 15:17:57 -0800

Paul Hoffman wrote:
> What Phill describes is not a downgrade attack: it is an attack based on 
> algorithm agility. If we allow multiple algorthims, and not all the 

1. If the signer publishes support for multiple algorithms, then the publisher 
supports those algorithms.  If they made poor choices, that's their problem.

2. If the publication of multiple algorithm support is part of a transition, 
then, yes, there is a window during which some recipients will not support the 
new one, or might be unhappy with signatures by the old one, or whatever.

3.  If a recipient cannot validate a signature, then the message is to be 
treated as unsigned.  -base is quite clear about this point.  Since there are 
myriad reasons a signature might validate, the case being presented here does 
not seem anything other than one more.

Doing something that causes a signature to fail is something I class as a 
downgrade.

Since we have already dealt with the 'failed validation' case extensively, I'm 
still missing what is interesting here.

> I agree that this is an example of an SSP lookup for signed messages. I 

Then we have a very basic problem.

> hope it does not mean that we are opening the door for other purposes. 
> It is also not requiring an SSP lookup; the only time you care if the 
> message is signed with an algorithm you don't understand is if you know 
> that they sign all messages. Therefore, you already did the SSP lookup 
> to find out that information. The algorithm list would come along with 
> the "I sign everything" information.

I'll translate this into:  The SSP lookup would be after validation failure, 
because at that point, the message is to be treated as unsigned, and that's 
when an SSP lookup is to be done.

>> Besides the technical hassle of adding overhead, this also means that 
>> current potential adopters of DKIM will see DKIM -base use as 
>> remaining unstable.
> 

If it requires lookup for a signed message -- as in, during validation or 
after validation succeeds -- then yes it does.

> ...and so is "I sign everything with Algorithm A".

By its nature, that implies a lookup for a signed message, including one that 
validates.  Bad idea.

d/
-- 

   Dave Crocker

---

From: Douglas Otis <[email-masked]>
Date: Fri, 23 Feb 2007 16:20:13 -0800

On Feb 23, 2007, at 3:17 PM, Dave Crocker wrote:

> Paul Hoffman wrote:
>> What Phill describes is not a downgrade attack: it is an attack  
>> based on algorithm agility. If we allow multiple algorthims, and  
>> not all the
>
> 1. If the signer publishes support for multiple algorithms, then  
> the publisher supports those algorithms.  If they made poor  
> choices, that's their problem.

This problem is made more significant when policy is applied.  When  
acceptance depends upon verifier supported algorithms, and where an  
improved algorithm might curtail a threat vector, both might be  
applied in hopes verifiers will quickly adopt the improved  
algorithm.  This would be a case where some protection is better than  
none, and where a policy can also still require more than none.

> 2. If the publication of multiple algorithm support is part of a  
> transition, then, yes, there is a window during which some  
> recipients will not support the new one, or might be unhappy with  
> signatures by the old one, or whatever.

This window of time will likely be measured in years.  Without some  
method to indicate a required superior algorithm, improved protection  
is not be assured over this long transition window.

> 3.  If a recipient cannot validate a signature, then the message is  
> to be treated as unsigned.  -base is quite clear about this point.   
> Since there are myriad reasons a signature might validate, the case  
> being presented here does not seem anything other than one more.

While indeed one might declare a signature to be invalid, the base  
draft also used incorrect terms regarding deprecated as being  
something determined by the verifier.  The problem is that a signer  
must wait years before being assured of improvements possible with an  
improved algorithm.

> Doing something that causes a signature to fail is something I  
> class as a downgrade.

This is not about causing a signature to fail, but not being able to  
depend upon an improved algorithm even when both the signer and  
verifier happen to support the improved algorithm.  This problem  
exists because there is no practical means to negotiate which  
algorithms should be applied to the message.

> Since we have already dealt with the 'failed validation' case  
> extensively, I'm still missing what is interesting here.

One can envision several scenarios where this failing could prove to  
have been a very poor choice in the algorithm.

> Then we have a very basic problem.

What happens when a mailing list signs their messages?  What happens  
when a provider signs messages independent of email-addresses used by  
their customers?  A signed message will not assure that a policy may  
not prove beneficial.

>> hope it does not mean that we are opening the door for other  
>> purposes. It is also not requiring an SSP lookup; the only time  
>> you care if the message is signed with an algorithm you don't  
>> understand is if you know that they sign all messages. Therefore,  
>> you already did the SSP lookup to find out that information. The  
>> algorithm list would come along with the "I sign everything"  
>> information.
>
> I'll translate this into:  The SSP lookup would be after validation  
> failure, because at that point, the message is to be treated as  
> unsigned, and that's when an SSP lookup is to be done.

Again, a message with a valid signature may still allow a policy to  
benefit the recipient.

>>> that current potential adopters of DKIM will see DKIM -base use  
>>> as remaining unstable.
> If it requires lookup for a signed message -- as in, during  
> validation or after validation succeeds -- then yes it does.

This added step might also extend protections afforded by DKIM.  
Unless there is an added benefit, there should be no expectation that  
a recipient will go to the trouble.   On the other hand, if the  
policy offers an assurance that some expensive threat analysis can be  
safely avoided, then the cost of obtaining the policy might be well  
worth the effort.

> By its nature, that implies a lookup for a signed message,  
> including one that validates.  Bad idea.

This mechanism belongs within the key.  Placing this in the key  
allows assertions without causing added transactions.

-Doug

---

From: "Charles Lindsey" <[email-masked]>
Date: Sun, 25 Feb 2007 13:11:01 -0000

> algorithm or not does not affect the success of the attack).

Note that this attack also works for minor changes to the way some  
signature algorithm is used. For example, B might be a new  
canonicalization algorithm introduced because the existing ones were  
failing too often due to unanticipated mungings by intermediate sites.

-- 
Charles H. Lindsey ---------At Home, doing my own thing------------------------
Tel: +44 161 436 6131                       
   Web: http://www.cs.man.ac.uk/~chl
Email: [email-masked]      Snail: 5 Clerewood Ave, CHEADLE, SK8 3JU, U.K.
PGP: 2C15F1A9      Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: John Levine <[email-masked]>
Date: 25 Feb 2007 16:31:51 -0000

> Every protocol with algorithm agility but not a fixed list of "MUST
> implement" algorithms has this issue.

Is there any reason that SSP couldn't require that anyone who makes a
statement that he signs messages must sign with all the signature algs
he supports?

This would be an SSP MUST, not a DKIM MUST.

R's,
John

---

From: Tony Hansen <[email-masked]>
Date: Sun, 25 Feb 2007 13:09:10 -0500

Douglas Otis wrote:
>> By its nature, that implies a lookup for a signed message, including
>> one that validates.  Bad idea.
> 
> This mechanism belongs within the key.  Placing this in the key allows
> assertions without causing added transactions.

Either that, or a pointer with the key to the additional information,
that is only present if the sender has a policy of the nature where a
lookup for signed messages is warranted. If you posit that the general
case is to *not* have such policies, then a pointer would do fine. If
you posit that the general case *is* to have such policies, then either
placing it in the key or not doing it at all would be preferable.

	Tony Hansen
	[email-masked]

PS. My brain is fuzzy from too much traveling and too little sleep.
Hopefully the above makes sense. :-)
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Michael Thomas <[email-masked]>
Date: Sun, 25 Feb 2007 10:46:23 -0800

> In order to twart the attack the policy language must be sufficiently expressive to allow the sender to describe their actual signature policy 'I always sign with algorithm A and with algorithm B'.
I just don't get this: if hash B is broken, isn't the right thing to
do is just kill off any selectors with hash B? Why do I need
policy when simply invalidating the selector would work even
better -- if it's still there, there's a pretty good chance that somebody
won't invoke ssp and still be fooled after all. This isn't just about
attacks in the interim transition period is it? If a hash like, oh say,
sha1 was suddenly catastrophically compromised you really wouldn't
have any choice but to move to the new algorithm.

       Mike

---

From: Michael Thomas <[email-masked]>
Date: Sun, 25 Feb 2007 10:53:27 -0800

Paul Hoffman wrote:
> on algorithm agility. If we allow multiple algorthims, and not all the 
> algorithms are the the "MUST implement" level, this attack is 

At this point, all we have is MUST implements. Considering there is
no opportunity for negotiation with mail, MAY/SHOULD implement
algorithms seems like a pretty bad idea altogether. So is this still a real
problem for DKIM?
> is if you know that they sign all messages. Therefore, you already did 
> the SSP lookup to find out that information. The algorithm list would 
> come along with the "I sign everything" information.

Cf my previous mail, we already transmit algorithm information in the
selector itself. I don't understand why simply nuking selectors with bad
algorithms isn't an adequate defense.

       Mike

---

From: Jon Callas <[email-masked]>
Date: Sun, 25 Feb 2007 11:50:14 -0800

> attacks were not an issue for the problem DKIM addresses.

We did. Downgrade attacks are not an issue for the problem DKIM  
addresses.

	Jon

---

From: Jon Callas <[email-masked]>
Date: Sun, 25 Feb 2007 12:02:18 -0800

> have any choice but to move to the new algorithm.

Bingo. You win, Mike.

The main thing that people seem to forget is that DKIM is not a long- 
term signature mechanism.

If I, the signer yank some set of keys (selectors, actually), then  
the only downside to me is that there are messages in-flight that may  
have no valid selector. I can fix this if I need to by changing my  
sending policy at the same time.

The only fly in that ointment is TTLs on any DNS objects other people  
have cached.

However, Phill has created a cute case that isn't *quite* a classic  
downgrade attack, but is at least a kissing cousin of one. The  
solution to it he proposes is that the policy language be rich enough  
to say, "I always sign with A and B." If we want to be complete, the  
policy statement could merely say, "I always sign with all of set S"  
and if you only use one algorithm, then it trivially falls out of it.  
Good suggestion, let's do it. End of story.

	Jon

---

From: Dave Crocker <[email-masked]>
Date: Sun, 25 Feb 2007 12:04:56 -0800

Michael Thomas wrote:
>>    If we allow multiple algorthims, and not all the
>> feasible. 
...
> algorithms seems like a pretty bad idea altogether. So is this still a real

It is probably worth making sure that we are all in synch about some 
relatively basic email protocol points:

1. SMTP permits negotiation. That's hop-by-hop, rather than end-to-end, which 
is what I assume you meant.

2. It turns out that there is also a newly-defined capability for negotiation 
between originator and recipient, but it is neither broadly adopted nor useful 
for DKIM-related issues, IMO.

3. Email has been doing upgrades for a long time. New header fields.  MIME. 
HTML.  Text line-wrapping.  And so on.   None of these has used any sort of 
policy publication mechanism.  All have had massive, long-term success.

So,

As much as upgrades might be made easier by being able to query a record 
published by the signer, there is no track-record of requiring such a thing, 
for email or, I believe, any other Internet protocol.  This means that we need 
to be extremely clear about the reason that any such a record is absolutely 
essential.

d/

-- 

   Dave Crocker

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 25 Feb 2007 13:23:40 -0800

At 10:53 AM -0800 2/25/07, Michael Thomas wrote:
>algorithms seems like a pretty bad idea altogether.

We have no prohibition on implementing additional algorithms, so it 
is fine for someone to implement, for example, DSA signatures.

>So is this still a real

Yes, it still is, because we didn't say (and should not have said) 
"MUST NOT implement any other signature algorithm".

--Paul Hoffman, Director

---

From: Dave Crocker <[email-masked]>
Date: Sun, 25 Feb 2007 14:01:26 -0800

>> So is this still a real problem for DKIM?
> 
> Yes, it still is, because we didn't say (and should not have said) "MUST 
> NOT implement any other signature algorithm".

How is that a problem?

d/

-- 

   Dave Crocker

---

From: John Levine <[email-masked]>
Date: 25 Feb 2007 22:09:06 -0000

>Good suggestion, let's do it. End of story.

Hold on a minute.  The SSP discussion is chronically plagued by
proposals for sender declarations that are useless to receivers, and I
think it's just happened again.  I'm trying to envision how a
recipient makes use of an assertion about signing algorithms, and
failing.

I'm a receiver, a message shows up with some signatures.  For each
signature that uses an algorithm I understand, I check and see if it
verifies, which either it does or it doesn't.  For each one that uses
an algorithm I don't understand, what should I do?  I can't verify it.
I can't assume it's good unless I want to create a whale-sized
security hole. So I ignore it.

So now let's say I have a message that has at least one good
signature.  As far as I'm concerned, I'm done, it's verified.  If I
were to check the SSP, the most that could happen is a variation on
the "I sign nothing" scenario, if the SSP claims there's some set of
signature algorithms other than what I found.  That is not useful to
the receiver, other than perhaps to identify senders insufficiently
competent to publish consistent key and SSP records.

Or I have a message that didn't have any good signatures.  I can't
tell whether that was because it was unsigned, it had a good signature
that broke in transit, it had a good signature that I didn't know how
to verify, or it had a bogus signature applied by a bad guy.  So, as a
receiver, this is all the same situation, it's unsigned.  If you
believe that SSP can state "I sign everything", you might throw it
away if that's what the SSP says.  Otherwise, what?

How does a SSP list of signing algorithms provide any useful
information to a receiver?  Unless I'm missing something rather
fundamental, it doesn't.

Regards,
John Levine, [email-masked], Primary Perpetrator of "The Internet for Dummies",
Information Superhighwayman wanna-be, http://www.johnlevine.com, Mayor
"More Wiener schnitzel, please", said Tom, revealingly.

---

From: Michael Thomas <[email-masked]>
Date: Sun, 25 Feb 2007 15:05:00 -0800

Paul Hoffman wrote:
> We have no prohibition on implementing additional algorithms, so it is 
> fine for someone to implement, for example, DSA signatures.

Well, I can implement rot13 too, but that doesn't make it standard or
useful. If we standardize something in the future, all we need to do
is make it a MUST for the extension and it stays within your bounds.
I can't see any reason why we'd _ever_ make an algorithm anything
less than MUST since the senders and receivers can't exchange their
capabilities.
> "MUST NOT implement any other signature algorithm".

I'm sorry but this doesn't make any sense at all to me.

       Mike

---

From: Douglas Otis <[email-masked]>
Date: Sun, 25 Feb 2007 16:45:38 -0800

On Feb 25, 2007, at 2:09 PM, John Levine wrote:

> signature that uses an algorithm I understand, I check and see if  
> it verifies, which either it does or it doesn't.  For each one that  
> uses an algorithm I don't understand, what should I do?  I can't  
> verify it. I can't assume it's good unless I want to create a whale- 
> sized security hole. So I ignore it.
>
> the "I sign nothing" scenario, if the SSP claims there's some set  
> of signature algorithms other than what I found.  That is not  
> useful to the receiver, other than perhaps to identify senders  
> insufficiently competent to publish consistent key and SSP records.

John,

Section 4.2. Interpretation states "a verifier that by policy chooses  
not to accept signatures with 'deprecated' cryptographic algorithms  
would consider such signatures invalid."

This represents a conceptual error, as previously described.  An  
invalid signature would not be "deprecated", but rather would be  
"obsoleted".  It is only possible for a signer to assert a signature  
is "deprecated" by identifying a replacement, but such has not been  
accommodated.

Imagine commerce related messages come to depend upon DKIM signatures  
for assuring delivery.  Say algorithm X proves problematic when some  
weakness is occasionally exploited.  The signer may decide it is less  
disruptive to assert that algorithm X is "deprecated", and then  
include an improved algorithm.  Receiving just a deprecated signature  
would be invalid.  By allowing signers to assert algorithm X is  
"deprecated," then once both verifier and signer support a common non- 
deprecated algorithm, the "deprecated" algorithm can be avoided.   
Avoiding an asserted "deprecated" algorithm when there is a common  
non-deprecated algorithm supported prevents a type of downgrade attack.

The interval before a downgrade attack can be curtailed in current  
scheme requires the problematic algorithm be "obsoleted".  Such may  
depend upon wide acceptance of a different algorithm to avoid greater  
disruption, which might be measured in years.  In addition, a  
"deprecated" assertion should be within the key to minimize any  
related overhead.

-Doug

---

From: "Charles Lindsey" <[email-masked]>
Date: Mon, 26 Feb 2007 11:04:05 -0000

> competent to publish consistent key and SSP records.

If the message has enough good signatures which match the From (whatever)  
header to meet whatever your local policy requires, then indeed you accept  
it; end of story; no need for SSP.
> away if that's what the SSP says.  Otherwise, what?

Eh? If it was unsigned, you know that.
     If it was signed with an algorithm you couldn't verify, you know that,
     If the signature was broken, you know that (but not why it was broken).
All those situations are to be classified as 'unsigned' (but more detailed  
information is available to you if you want to use it).

So, being "unsigned", you consult the SSP, which maybe tells you "we sign  
everything". You might then reject it regardless on that basis and thus  
lose some genuine message simply because you couldn't verify the algorithm  
in use; more likley, you would want to allow such cases through (whilst  
also persuading your local geeks to implement the new algorithm ASAP).  
But, in the example quoted (message signed only by unverifiable algorithm  
B) you would then accept the bogus message. But an SSP response of "we  
sign everything with both A and B" would allow you to accept genuine  
messages from that site (because you can veriffy algorithm A) but reject  
the bogus one.

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 26 Feb 2007 11:30:19 +0000

It seems to me that the exchange between John and Charles
below captures the crux of the issue.

Option 1: If we agree with Charles (& Phill I guess) that
looking up SSP and then passing on the only-signed-with-B
message will be common practice then there seems to be a
sufficient reason to include the "I sign all with A"
statement or equivalent in SSP.

Option 2: If OTOH, we agree with John, that further processing
(after sig check & SSP lookup) SHOULD or MUST treat the
only-signed-with-B message as unsigned, with no code branching
on the presence of the putative B-sig, then the additional SSP
expressiveness is useless.

I don't see a rough consensus either way, though I would
guess I've seen a little more support for option 1 in the
last few days than for option 2.

Just to help me out, could you say which option you prefer?
Thanks,
Stephen.

PS: If you prefer some other option or would like to quibble
with my text above, feel free, but maybe change the subject.

Charles Lindsey wrote:
> All those situations are to be classified as 'unsigned' (but more 
> detailed information is available to you if you want to use it).
> 
> So, being "unsigned", you consult the SSP, which maybe tells you "we 
> sign everything". You might then reject it regardless on that basis and 
> thus lose some genuine message simply because you couldn't verify the 
> algorithm in use; more likley, you would want to allow such cases 
> through (whilst also persuading your local geeks to implement the new 
> algorithm ASAP). But, in the example quoted (message signed only by 
> unverifiable algorithm B) you would then accept the bogus message. But 
> an SSP response of "we sign everything with both A and B" would allow 
> you to accept genuine messages from that site (because you can veriffy 
> algorithm A) but reject the bogus one.
>>
> --Charles H. Lindsey ---------At Home, doing my own thing------------------------ 
> 
> Tel: +44 161 436 6131                      
> NOTE WELL: This list operates according 
> tohttp://mipassoc.org/dkim/ietf-list-rules.html
>

---

From: Michael Thomas <[email-masked]>
Date: Mon, 26 Feb 2007 05:50:45 -0800

> with my text above, feel free, but maybe change the subject.

Well, I have one small quibble in that I don't understand what
the actual problem is. While that's not a huge problem in the
global scope of things, I do need to understand this enough to
transcribe the outcome. In particular, I haven't seen any clarification
as to why the algorithm bindings in -base are not sufficient to
cover this attack; having -base already solve the problem is
the best outcome, right?

		Mike

---

From: Michael Thomas <[email-masked]>
Date: Mon, 26 Feb 2007 06:11:33 -0800

Charles Lindsey wrote:
> If the message has enough good signatures which match the From 
> (whatever) header to meet whatever your local policy requires, then 
> indeed you accept it; end of story; no need for SSP.
>>

I suspect the key word here is "signed". All you know is that it has
something that looks like a DKIM-SIGNATURE. The verifier has no way to
differentiate sha0 from sha1024 since it is ignorant about both. Thus
for all intents and purposes it is just as broken as any other reason
that a signature might break, and needs to be handled in the identical
way lest you give attackers a leg up.

> algorithm ASAP). 

Um, that sounds like a great way to make dkim completely impotent: if
an attacker knows that you treat unverifiable signatures better, they
only have to put those majick bytes in the signature header and voila.

But, in the example quoted (message signed only by
> algorithm A) but reject the bogus one.

As I mentioned, you can already determine what algorithms are supported
by a given selector. Why does putting in SSP help?

		Mike

---

From: Douglas Otis <[email-masked]>
Date: Mon, 26 Feb 2007 06:13:28 -0800

> statement or equivalent in SSP.

Unless John, Jon, Dave, and Mike can assure the WG that current  
algorithms will always be sufficiently strong, and that a transition  
sufficiently swift, then a means for the _signer_ to apply different  
algorithms where one is "deprecated" should be possible.   Philip's  
point that this represents a type of signer's policy is valid.   
However, the deprecation assertion (use Y instead of X) should be  
possible within in either the key or signature to avoid unnecessary  
overhead.  Nothing needs to change in terms of these current  
structures, however verifiers should be able to recognize when an  
algorithm has been deprecated by the signer.

Option 1.

-Doug

---

From: Michael Thomas <[email-masked]>
Date: Mon, 26 Feb 2007 06:27:44 -0800

Jon Callas wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 

But if it's a problem for TTL's on selectors, it's a problem for TTL's
on anything else too, including SSP records. I suspect getting wrapped
around the axle about the interim period of a catastrophic hash failure
is a good way to madness.

> Good suggestion, let's do it. End of story.

Except for the fact that in order to know that, I'd have to do an SSP
lookup. But look at it this way: I have an authoritative source in the
selector as well as a proposed authoritative source in the SSP. They
are functionally the exact same information to the verifier. The
verifier already has to look up the selector; why would it be motivated
to look up SSP for the same information? Especially in the light of
the fact that -base and -ssp are and should be severable.

		Mike

---

From: Douglas Otis <[email-masked]>
Date: Mon, 26 Feb 2007 06:40:29 -0800

On Feb 26, 2007, at 6:11 AM, Michael Thomas wrote:

> I suspect the key word here is "signed". All you know is that it  
> has something that looks like a DKIM-SIGNATURE. The verifier has no  
> way to differentiate sha0 from sha1024 since it is ignorant about  
> both. Thus for all intents and purposes it is just as broken as any  
> other reason that a signature might break, and needs to be handled  
> in the identical way lest you give attackers a leg up.

The goal is to prevent a downgrade attack.  A message is signed with  
algorithm A and B, where A is asserted to be deprecated, then when  
once both the signer and verifier support B, then A can be avoided.   
Not avoiding A when signer and verifier support both algorithms  
represents a vulnerability to a downgrade attack.  That said, a  
policy that in effect says "only reject messages when you support B"  
would not be the best solution.

>> If the signature was broken, you know that (but not why it was  
>> broken). All those situations are to be classified as  
>> 'unsigned' (but more detailed information is available to you if  
>> you want to use it). So, being "unsigned", you consult the SSP,  
>> which maybe tells you "we sign everything". You might then reject  
>> it regardless on that basis and thus lose some genuine message  
>> simply because you couldn't verify the algorithm in use; more  
>> likely, you would want to allow such cases through (whilst also  
>> persuading your local geeks to implement the new algorithm ASAP).
>
> Um, that sounds like a great way to make dkim completely impotent:  
> if an attacker knows that you treat unverifiable signatures better,  
> they only have to put those majick bytes in the signature header  
> and voila.

You have a point, but unless there is some means to transition  
algorithms, it is not likely to happen soon enough and these changes  
will need to happen in a panic.  "All this domain's messages are all  
signed with B" is a valid policy assertion that at least provides a  
forward path.

>> But, in the example quoted (message signed only by unverifiable  
>> algorithm B) you would then accept the bogus message. But an SSP  
>> response of "we sign everything with both A and B" would allow you  
>> to accept genuine messages from that site (because you can veriffy  
> As I mentioned, you can already determine what algorithms are  
> supported by a given selector. Why does putting in SSP help?

One can not determine what has been implied with respect to  
algorithms with just "this domain's messages are always signed".   
Signed using what algorithm?  This becomes very important when there  
happens to be more than one.

-Doug

---

From: John Levine <[email-masked]>
Date: 26 Feb 2007 15:13:27 -0000

>information is available to you if you want to use it).

I would really like a security analysis of this paragraph.  In
particular, how do you tell a valid signature with an algorithm you
couldn't verify from a spammer's forged header that happens to look
like a signature?  You can't.  DKIM doesn't have signatures that
"almost" or "sort of" verify.  Either they verify or they don't.

With that in mind, of what use to a receiver is a policy statement
that depends on a header that is trivially forged by any bad guy?

Regards,

---

From: John Levine <[email-masked]>
Date: 26 Feb 2007 15:32:21 -0000

>algorithms where one is "deprecated" should be possible. 

Let's say I am a signer, you are a receiver.  I publish a policy that
says "don't trust that old fashioned sha256 signature, just the new
rot13 one."  What should you do with that policy record?  Why should
you do anything other than ignore it because it's stupid?

More generally, I hear an implicit assumption in all of this that
senders know more about crypto than receivers do.  Why would that
be so?  Why shouldn't receivers use their own best judgement about
what hashes are adequately strong, and why should they believe
statements from random spammers about relative strengths of
crypto algorithms?

R's,
John

---

From: Douglas Otis <[email-masked]>
Date: Mon, 26 Feb 2007 08:03:26 -0800

On Feb 26, 2007, at 7:32 AM, John Levine wrote:

>> algorithms will always be sufficiently strong, and that a  
>> transition sufficiently swift, then a means for the _signer_ to  
>> apply different algorithms where one is "deprecated" should be  
>> possible.
>
> Let's say I am a signer, you are a receiver.  I publish a policy  
> that says "don't trust that old fashioned sha256 signature, just  
> the new rot13 one."  What should you do with that policy record?   
> Why should you do anything other than ignore it because it's stupid?

You receive a message where the signer has indicated that sha256 has  
been deprecated, or perhaps the original signature association scheme  
has been deprecated, or perhaps the canonicalization algorithm has  
been deprecated.  To permit a graceful transition, both the  
deprecated algorithm (whatever that might be) and some shiny new  
algorithm must now be included with the message.  Once your verifier  
adopts the shiny new algorithm, both you and the sender have obtained  
a higher level of protection not vulnerable to downgrade attack.   
This protection depends upon a means for the signer to assert which  
algorithm is deprecated, and what shiny new algorithm is being offered.

> be so?

SMTP is a store and forward protocol.  As such it is impossible to  
negotiate between signer and verifier the highest supported  
algorithm.  It is not possible for the verifier to assert what is  
deprecated.  This is where DKIM base is very much conceptually in  
error.  The verifier can only assert which algorithms are obsolete,  
but the signer is able to assert which algorithms are deprecated.   
The signer must lead the transition by providing an improved option.   
It is not possible for the verifier to offer an improved option.   
There is no method to negotiate such a verifier option.

>   Why shouldn't receivers use their own best judgement about what  
> hashes are adequately strong, and why should they believe  
> statements from random spammers about relative strengths of crypto  
> algorithms?

Without a means for the signer to assert which algorithms are  
deprecated, until the problematic algorithm can be obsoleted, a  
downgrade vulnerability will exist.  This period of this  
vulnerability will likely be measured in years.  Defining a way  
forward does not need to alter existing structures, but instead  
simply define how the signer can make the assertions when they are  
needed.

-Doug

---

From: Michael Thomas <[email-masked]>
Date: Mon, 26 Feb 2007 08:13:27 -0800

Douglas Otis wrote:
> algorithms will always be sufficiently strong,  [...]

I'm sorry, this is a straw-poll, not a straw-man. I've said nothing
of the sort.

		Mike

---

From: Dave Crocker <[email-masked]>
Date: Mon, 26 Feb 2007 08:48:01 -0800

John Levine wrote:
>> sufficiently swift, ...

Folks,

Before we take a straw poll on solutions, perhaps we should take one on problems?

The proposed mechanism incurs an additional lookup for every signed message.

The goal of this mechanism is to deal with a potential danger, during a 
transition.

We can assume that there will, indeed, be transitions.

Whether we can assume that there will be danger in using the older algorithm 
is the question.

1. Given a 35 year history of Internet transitions, it would help to document 
previous ones that have a) had this problem, and b) ones that were helped by 
this sort of mechanism.

2. Unless I'm missing something pretty basic, the duration of a transition is 
the time between the last message is signed with an algorithm and the signer 
deletes the key record.  For DKIM intended use, I believe this duration will 
be in the range of 3-10 days.  If I'm wrong, it would help for someone to 
explain how.

3. If an older mechanism is somehow "dangerous", then why is the algorithm 
still being supported by the sender?  (We know it is still supported, because 
the sender still publishes a key record for it.)

4. We should also consider the impact of the transition to the mechanism 
itself.  DKIM is already deployed.  Before the SSP work is published, there 
will be more deployment.  Further, not everyone is going to implement this SSP 
mechanism.  So, what does it mean to have partial support throughout the DKIM 
service?

In other words, we appear to be talking about embedding permanent, per-message 
overhead, for a mechanism that is designed to cover an event that has no 
precedent in 35 years of Internet history, and to embed it in a system that is 
explicitly intended to provide security features that are limited in time and 
scope.

d/
-- 

   Dave Crocker

---

From: EKR <[email-masked]>
Date: Mon, 26 Feb 2007 08:50:26 -0800

> simply define how the signer can make the assertions when they are

I'm sure I'm going to regret wading in here, but...

We have two algorithms, A and B. Let's stipulate that B is stronger
than A. Now, the sender can have three policies: send A (SA) Send B
(SB) and send A+B (SAB). The receiver can similarly have three
policies, accept A (RA), accept B (RB) and accept A or B (RAB).

If you cross these you get the following matrix:

                 Sender
             SA    SB    SAB
         RA   A     X      A
Receiver RB   X     B      B
         RAB  A     B     AB

Because implementations are supposed to ignore signatures they
can't verify, the only context in which downgrade attacks matter
is if the sender is implementing SAB and the receiver is implementing
RAB. In this case, assuming there's no policy information, the 
attacker can strip a signature and convince the receiver that the
sender implemented SA or SB. Since we've stipulated that B>A, 
only the former makes sense.

Now, again there are two cases:

1. A is so weak that an attacker can readily mount attacks on it
   at a practical level.
2. It's not.

Only in the first case does a downgrade attack buy you anything.

So, as I understand Doug's argument, A is strong enough that the
receiver thinks it conveys *some* informational value (otherwise
he would simply implement RB) but strong enough that it's
being regularly broken. So, the sender wants to implement SAB
and securely tell the receiver that so that receivers which
do implement RAB will get the benefit of B. Do I have this
right?

If so, I find this scenario fairly implausible. If algorithms
are being routinely broken, I would expect people to turn them
off entirely or *at least* for receivers to quickly roll out
the new algorithms allowing senders to safely send the newer
ones without the older ones. And if algorithms are being broken
enough to mandate this kind of policy indicator, I find it
hard to believe they carry much informational value.

As a thought experiment: SHA-256 has a nominal security value
of 256-bits against preimage attacks (the kind that's most
likely relevant here). At what bit strength do you believe
receivers would still trust it but downgrade attacks would be
practical enough to mandate this kind of indicator?

-Ekr

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 26 Feb 2007 16:59:13 +0000

> The proposed mechanism incurs an additional lookup for every signed 

That isn't my understanding of Phill's proposal. But then
I don't understand why his proposal is a good idea, so maybe
I'm wrong on this too, but I doubt it.

Stephen.

---

From: Michael Thomas <[email-masked]>
Date: Mon, 26 Feb 2007 09:02:18 -0800

Douglas Otis wrote:
> has been deprecated, or perhaps the canonicalization algorithm has been 
> deprecated.  To permit a graceful transition, both the deprecated 
> algorithm (whatever that might be) and some shiny new algorithm must now 
> be included with the message.  Once your verifier adopts the shiny new 
> algorithm, both you and the sender have obtained a higher level of 
> protection not vulnerable to downgrade attack.  This protection depends 
> upon a means for the signer to assert which algorithm is deprecated, and 
> what shiny new algorithm is being offered.

Phill -- do you agree with this?

At least I can see the potential issue here.

	Mike

---

From: Mark Delany <[email-masked]>
Date: Mon, 26 Feb 2007 09:22:36 -0800

> The proposed mechanism incurs an additional lookup for every signed 

Whatever algorithm policy you embed in a separate SSP can just as easily 
be embedded in the Selector of the weakened key.

But maybe that just means I don't get any of the discussion about 
downgrade attacks or weakened keys needing a separate SSP. As others 
have said TTL is irrelevant because they are always going to be many 
orders of magnitude smaller than the response time of human 
administrators. Heck most administrators haven't even heard of DKIM yet 
alone the discovery of any algorithmic weakness.

I was under the impression that a separate SSP can only add value for 
domains *not* verified by the signature.

Mark.

---

From: Mark Delany <[email-masked]>
Date: Mon, 26 Feb 2007 09:30:27 -0800

Michael Thomas wrote:
>> been deprecated.  To permit a graceful transition, both the deprecated 
>> algorithm (whatever that might be) and some shiny new algorithm must 
>> now be included with the message.  Once your verifier adopts the shiny 

[ Two valid signatures in the message ]

Wasn't this always the transition plan? The only crucial point is that 
the Selector associated with the "weaker" signature has to tell the 
verifier to expect the presence of "stronger" signature.

If the verifier doesn't understand the "stronger/newer" signature or 
can't find it, then it has a risk decision to make about the weaker 
verification. Selector-embedded SSP could give guidance to local policy 
here.

> At least I can see the potential issue here.

With the solution or the problem?

Mark.

---

From: Douglas Otis <[email-masked]>
Date: Mon, 26 Feb 2007 09:53:32 -0800

On Feb 26, 2007, at 8:48 AM, Dave Crocker wrote:

> 1. Given a 35 year history of Internet transitions, it would help  
> to document previous ones that have a) had this problem, and b)  
> ones that were helped by this sort of mechanism.

There are few comparable protocols unable to negotiate the highest  
level of compatibility, and few where rapidly obsoleting a  
problematic algorithm is likely to break the protocol.  This might  
become the case for DKIM once the signature becomes a basis for  
acceptance of commerce related messaging.

> 2. Unless I'm missing something pretty basic, the duration of a  
> transition is the time between the last message is signed with an  
> algorithm and the signer deletes the key record.  For DKIM intended  
> use, I believe this duration will be in the range of 3-10 days.  If  
> I'm wrong, it would help for someone to explain how.

The transition would be the period of time needed before a verifier  
can "obsolete" an algorithm.  Until a substantial portion of the  
signers have adopted an improved algorithm, making a prior algorithm  
"obsolete" without creating a sizable disruption may require years.   
Unless the algorithm has suffered a catastrophic failure, a long  
transition should be anticipated.  Few security related protocols  
suffer a catastrophic failure.

> 3. If an older mechanism is somehow "dangerous", then why is the  
> algorithm still being supported by the sender?  (We know it is  
> still supported, because the sender still publishes a key record  
> for it.)

Until arriving at a sufficient level of adoption where messages are  
unlikely to be considered unsigned, offering two alternatives will  
likely be required when an improved algorithm is desired.  It is not  
reasonable to assume the weakness causing the desire to be  
catastrophic, but the transition may take many years.  Without a  
mechanism to assert that an algorithm is deprecated, over this long  
transition period there will exist a downgrade vulnerability.

> 4. We should also consider the impact of the transition to the  
> mechanism itself.  DKIM is already deployed.  Before the SSP work  
> is published, there will be more deployment.  Further, not everyone  
> is going to implement this SSP mechanism.  So, what does it mean to  
> have partial support throughout the DKIM service?

Defining a means to assert that an algorithm is deprecated does not  
require that the existing structures be changed.  The best place to  
permit these assertions would be within the key or signature.  Both  
are extensible.  Those that adopt the assertion mechanism can thwart  
a future downgrade vulnerability. That that don't can't.

> In other words, we appear to be talking about embedding permanent,  
> per-message overhead, for a mechanism that is designed to cover an  
> event that has no precedent in 35 years of Internet history, and to  
> embed it in a system that is explicitly intended to provide  
> security features that are limited in time and scope.

This is not correct.  There is a long history of algorithms being  
deprecated.  When done properly, a deprecation assertion mechanism  
will not add to the overhead.  Why not prevent a downgrade  
vulnerability when it does not cost anything?

-Doug

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 26 Feb 2007 09:54:14 -0800

>The proposed mechanism incurs an additional lookup for every signed message.

You keep saying this without justifying it. Others have shown it to 
be wrong. Please stop repeating it or support your statement.

>The goal of this mechanism is to deal with a potential danger, 
>during a transition.

That is only one goal. Another goal is to let a sender who wants to 
use a different algorithm *for any reason they wish* to do so. That 
is a requirement for security protocols.

>We can assume that there will, indeed, be transitions.

Yes

>Whether we can assume that there will be danger in using the older 
>algorithm is the question.

Maybe, but Ekr's message brings that into question.

>1. Given a 35 year history of Internet transitions, it would help to 
>document previous ones that have a) had this problem, and b) ones 
>that were helped by this sort of mechanism.
>

Simple: we allow signers to sign with multiple algorithms. Therefore 
the transition can last as long as the signer wants. It is possible 
that this might be many years.

>algorithm still being supported by the sender?  (We know it is still 
>supported, because the sender still publishes a key record for it.)

As Ekr pointed out, it is not necessarily "dangerous" and "safe", but 
"less good" and "better". People use "less good" algorithms during 
transitions until they are sure that swithching completely to 
"better" algorithms will suit their needs, namely that the recipient 
will be able to correctly interpret their signature.

This is *exactly* what is being played out in the PKIX world today 
with the attacks on MD5 and SHA-1.

>mechanism itself.  DKIM is already deployed.  Before the SSP work is 
>published, there will be more deployment.  Further, not everyone is 
>going to implement this SSP mechanism.  So, what does it mean to 

That's a very good question, and the unfortunate answer is "not 
much". I might make some sender feel better, but it is not likely to 
help any verifier. That combination usually leads to senders 
misunderstanding the value of the feature and confusion in the 
market. That should give us pause.

The bigger question is, "Given that dkim-base is completely clear 
that a message is validly signed or it is unsigned, what extra value 
to each party is gained from adding signature algorithms to 'I sign 
everything'?". I don't think the sender gets any value because the 
recipient either validates with one of the algorithms (success, no 
SSP needed) or it doesn't. It doesn't help the recipient in the case 
where they can validate one of the signatures. The only possible 
value is when the recipient wants to know why they can't validate, 
and this addition to SSP doesn't tell them anything definitive.

I don't support SSP giving hints or partial information, so I am -1 
on the proposal.

--Paul Hoffman, Director

---

From: Dave Crocker <[email-masked]>
Date: Mon, 26 Feb 2007 10:10:24 -0800

Paul Hoffman wrote:
> You keep saying this without justifying it. Others have shown it to be 
> wrong. Please stop repeating it or support your statement.

Actually, they haven't.  They have suggested an optimization that something 
could be added to the regular key query response, but I still don't understand 
what it is, exactly, or what presumed value-add is supplies.

After all, if there is a key query that returns a successful result, then that 
means that the signer does, in fact, support the algorithm.

But, of course, I've been asking some deeper questions that also aren't 
getting answers...

>> The goal of this mechanism is to deal with a potential danger, during 
>> a transition.
> 
> That is only one goal. Another goal is to let a sender who wants to use 
> a different algorithm *for any reason they wish* to do so. That is a 
> requirement for security protocols.

And isn't it nice that DKIM allows that.  So, the proposed mechanism is not 
about that requirement.  It is about something else.

>> document previous ones that have a) had this problem, and b) ones that 
>> were helped by this sort of mechanism.

These are two of the deeper questions we ought to answer, before polling about 
solutions.

> Simple: we allow signers to sign with multiple algorithms. Therefore the 
> transition can last as long as the signer wants. It is possible that 
> this might be many years.

Were DKIM intended to have signatures that lasted years, that might make 
sense.  Since it isn't, I am pretty sure it doesn't.

> transitions until they are sure that swithching completely to "better" 
> algorithms will suit their needs, namely that the recipient will be able 
> to correctly interpret their signature.

Perfection is costly.  Why is this "improvement" worth the cost?

> The bigger question is, "Given that dkim-base is completely clear that a 
> message is validly signed or it is unsigned, what extra value to each 
> party is gained from adding signature algorithms to 'I sign 
> recipient either validates with one of the algorithms (success, no SSP 
> needed) or it doesn't. It doesn't help the recipient in the case where 
> they can validate one of the signatures. The only possible value is when 
> the recipient wants to know why they can't validate, and this addition 
> to SSP doesn't tell them anything definitive.
> 
> I don't support SSP giving hints or partial information, so I am -1 on 
> the proposal.

ack.

d/
-- 

   Dave Crocker

---

From: Hector Santos <[email-masked]>
Date: Mon, 26 Feb 2007 13:10:38 -0500

In my view, it doesn't matter if its A, B, AB, XYZ or weaker or 
stronger.   It is about expectations.

if S says I only sign with A, then R should not see signatures with B, X 
or Y.

Expected behavior is what I consider a strong part of the negotiation if 
we want to call it that. Anything short of that produces uncertainty and 
hence risk.

Just consider that bad guys may find using the weakest covers 80% of
all systems, and when it needs to, it uses the stronger method for the 
remaining.

But guess what?

He might not use it at all or create a conditions that produces a FAULT 
simply because systems still need to deal with LEGACY operations

So in other words, until we have a SPECIFICATION, BCP or what have you 
on how to deal with failure, it really doesn't matter what strength you
have.

Seeing failure as unsigned just doesn't cut it for me simply because 
there will be MORE failures then success and we will need a way to deal 
with that.

My hope is that DOMAIN POLICY helps in every way it can, including 
having a bit saying "I SIGN WITH THIS OR THAT ALGORITHM."

Just look at it this way:

I can see companies doing a preliminary "check" on receivers to see what 
"DKIM" support it has before it accepts email addresses from users.  A 
high value company policy account may mandate this before begins to do 
high value transactions with the user.  If the user's email domain is 
not "secured" enough in the eyes of the company, it might even provide 
the user its own email or some other more secured domain ISP address.

---
HLS

---

From: EKR <[email-masked]>
Date: Mon, 26 Feb 2007 10:20:12 -0800

Hector Santos <[email-masked]> writes:

> if S says I only sign with A, then R should not see signatures with B,
> X or Y.

OK, but we're discussing what sorts of policies S should be able to
communicate. In particular, should S be able to say "I sign with
both A and B and any signature you see from me will have both,
not just either."

> there will be MORE failures then success and we will need a way to
> deal with that.

It seems to me that you're denying a basic premise of the system.
>From base S 4.2:

   Verifiers SHOULD ignore failed signatures as though they were not
   present in the message.  Verifiers SHOULD continue to check
   signatures until a signature successfully verifies to the
   satisfaction of the verifier.  To limit potential denial-of-service
   attacks, verifiers MAY limit the total number of signatures they will
   attempt to verify.

-Ekr

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 26 Feb 2007 10:38:29 -0800

At 10:10 AM -0800 2/26/07, Dave Crocker wrote:
>Actually, they haven't.

Well, at least I have. If a recipient gets a message with a valid 
signature, they never need to look up an SSP record. That refutes 
your statement pretty fully, doesn't it?

>>>algorithm and the signer deletes the key record.  For DKIM 
>>>intended use, I believe this duration will be in the range of 3-10 
>>>days.  If I'm wrong, it would help for someone to explain how.
>>
>>Simple: we allow signers to sign with multiple algorithms. 
>>Therefore the transition can last as long as the signer wants. It 
>>is possible that this might be many years.
>
>Were DKIM intended to have signatures that lasted years, that might 
>make sense.  Since it isn't, I am pretty sure it doesn't.

And you would be wrong. If I am signing a message with both A and B, 
it doesn't matter how long the key for each signature lasts; the 
transition lasts for as long as I am using both algorithms. This is 
no different than any other security protocol.

--Paul Hoffman, Director

---

From: Hector Santos <[email-masked]>
Date: Mon, 26 Feb 2007 13:44:29 -0500

> both A and B and any signature you see from me will have both,

I understand. I wrote a first draft (DSAP) proposing the concept back in 
July/2006:

http://tools.ietf.org/wg/dkim/draft-santos-dkim-dsap-00.txt

section 4.4

4.4.  DSAP Tag: a=<hash-algorithm>

    The a=<hash-algorithm> tag defines the possible signature hashing
    algorithms used by the domain DKIM message signer.  The a= tag is NOT
    optional.

    The current algorithms are defined in DKIM [DKIM-BASE] section 3.3.

    o  rsa-sha1
    o  rsa-sha256

    Example:

    a=rsa-sha1,rsa-sha256;

    The main purpose of the a= tag is to allow domain signers the design
    and implementation opportunity to determine the highest strength
    possible by a particular target verifier by looking the DSAP DNS
    record for the target recipient domain host.  If this query results
    with no a= tag information, the default should be rsa-sha1 is the
    highest strength possible.

    Essentially, this is a negotiation and backward compatibility
    concept.  It is quite possible earlier pre-standard DKIM
    implementations supporting only rsa-sha1 may still exist.  The domain
    DKIM message signer's desire is to achieve the highest protection
    possible.  Instead of signing mail with a particular algorithm and
    hoping for the best, the signer can predetermine what the receiving
    system can handle in terms of hashing strength.

    [[anchor17: This verifier lookup concept is best utilize for high-
    value domains in 1 to 1 transactions.  It would not be practice
    Mailing List resigners with large distributions to use this
    concept.]]

>    attacks, verifiers MAY limit the total number of signatures they will

You are seeming 100% correct. :-)

Its no secret I had seen this as a flawed concept since day UNO and I 
strongly believe its the genesis of most of the unsolvable debates here.

This alone is enough to make DKIM unadoptable and unacceptable across 
the board in practice. Its like buying a new car knowing you have a 
cracked rack and pinion.  You shouldn't be surprise there will be 
problems with this. :-)

The only redeeming solution is a POLICY based concept that will help put 
a definition around inevitable failure.  Unhanded Blind Failure is not 
going to be tolerated.

Just consider that once you begin to send in a NON-SSP environment, the 
default policy is "NEUTRAL."

Whats the point behind DKIM receivers checking X unsigned message vs Y 
unsigned message from the same domain?  Whats the value between the two?
The concept that there is no value between a REAL unsigned messaged and 
a failed signed message in relation to a single domain, to me, is a 
flawed concept.  To expect receivers to treat these two the same is 
asking bit more out of the ordinary logic.

--
HLS

---

From: Dave Crocker <[email-masked]>
Date: Mon, 26 Feb 2007 10:56:01 -0800

Paul Hoffman wrote:
> signature, they never need to look up an SSP record. That refutes your 
> statement pretty fully, doesn't it?

I have no idea.

The discussion is about algorithm transitions.  Those aren't interesting 
things to talk about unless there is a signature.  My understanding of the 
current topic is that it pertains to an SSP query that is only worth making 
when there is a signature.

Some of the discussion seems to be about having a signature that is valid but 
not "strong enough".  That might not be a scenario that you have in mind, but 
it sure seems to be one that is being discussed.

If there are no valid signatures, then I do not see how it is relevant to talk 
about algorithm agility.

All of which suggests that we have a few people who each feel they have a 
clear and solid understanding of the topic, but not necessarily that they 
share the same clear and solid understanding.

It further leaves out poor folk like me, whose only clear and solid 
understanding is that I have no clear or solid understanding of the problem 
that is claimed to be solved or why the problem is worth solving.

> And you would be wrong. If I am signing a message with both A and B, it 
> doesn't matter how long the key for each signature lasts; the transition 
> lasts for as long as I am using both algorithms. This is no different 
> than any other security protocol.

It does if the entire premise for a signature is that it is very short-lived, 
because it means that a transition can -- and should -- be targeted also to be 
short-lived for a given signer.

That is, indeed, very different from other security protocols.

d/

-- 

   Dave Crocker

---

From: Damon <[email-masked]>
Date: Mon, 26 Feb 2007 16:04:16 -0500

> The proposed mechanism incurs an additional lookup for every signed message.

I don;t understand this statement. Can you clarify please? How would
this happen exactly.

> Whether we can assume that there will be danger in using the older algorithm

Yeah.. I regularly crack PGP with my morning coffee now-a-days :)

Regards,
Damon Sauer

---

From: Jon Callas <[email-masked]>
Date: Mon, 26 Feb 2007 13:45:38 -0800

> expressiveness is useless.

I don't understand the choices. I *think* I prefer 2.

I think the example is interesting in theory, but I really think we  
don't have an agreement on some SSP basics. Here's some handwaving at  
some formalism in some principles:

(1) The receiver is always in control. The receiver can do anything  
they want to a message for whatever reason they want to. (I treat  
this as an axiom, and one that is independent of DKIM. If the is  
false, then a receiver can't delete spam.)

(Corollary) Checking a DKIM signature is optional. The fact that you  
signed a message does not obligate me to verify your signature. I can  
look at a properly-constructed DKIM message from the domain "419- 
guild.ng" and decide to trash it out of hand.

(2) If a DKIM signature is valid, the receiver isn't going to check  
SSP. The receiver will make whatever action they will take based upon  
knowing the responsible domain combined with content analysis, the  
direction of the wind, and so on.

(3) If a DKIM signature is missing, a receiver might check SSP, but  
don't count on it.

(4) If a DKIM signature is present but broken, a receiver *might*  
check SSP, but is under no obligation to. (This is derivable from  
(1), but I think it needs to be stated.)

(5) A receiver might consider a signature made with parameters that  
they don't speak to be either a broken signature or a non-existent  
signature.

I think that these principles get us out of the apparent "downgrade  
attack." Let's suppose that SHA-1 was broken yesterday. I can deploy  
DKIM software that just considers all SHA-1 signatures to be noise  
and thus anything signed with SHA-1 is a non-DKIM message. End of  
problem. Yeah, this is going to be an operational annoyance, but  
there's no *problem*, where a problem is a forged signature or  
something akin to one.

I think that we tend to forget (1). We also tend to forget (4) and (5).

None of the sender's actions with DKIM creates an obligation on the  
receiver's part. To be blunt, DKIM is one big MAY. (It might be a big  
SHOULD, but a SHOULD is just a MAY with an attitude.) On top of that,  
SSP is a big MAY, as well. Now I hope and expect that many people  
will decide to do these MAYs, but I don't expect DKIM to become  
mandatory.

There is going to be a *receiver* policy system that we aren't going  
to standardize, but the implementers will create. That receiver  
system is going to include options like whether the receiver should  
bother to check SSP. It will include options as to how to deal with  
SHA-1, eventually.

Okay, now on to more of the poll question. I think Phill came up with  
a fine example of why it's a good idea to have the SSP language  
expressive enough to say, "I sign with both RSA-sha1 and ECDSA- 
sha256." It removes ambiguity, and removing ambiguity is always good.

But if the receiver only implements RSA and thinks that SHA-1 is  
crap, then we may not ever get to checking SSP. I may trash the  
message, flag it as spam, content-scan it, or anything else I desire.

This is why I also agree with John. It is unambiguous that the  
receiver is in control. If you publish a crap policy, it's not *my*  
problem. I'm going to flag you messages or trash them, or whatever  
else. If you write something in a policy that is useless or non- 
actionable, I'm going to ignore it.

Furthermore, I may not even check your policy. *My* policy may  
include a list of "phish-likely" domains, and I trash all messages  
from them that aren't signed with a 4096-bit RSA key and SHA-512, and  
if you don't like it (or don't implement SHA-512), tough. Open an  
SMTP connection to the hand.

In general, I support expressiveness in SSP language. I also think  
that SSP is a *hint*, not a mandate (and that that is a real-world  
fact, not a protocol issue). If we remember that SSP provides  
guidance to the receiver for the case of broken signatures and  
nothing more, we can keep from getting around a large number of axles.

	Jon

---

From: "John R Levine" <[email-masked]>
Date: 27 Feb 2007 02:56:49 -0500

>> algorithm is deprecated, and what shiny new algorithm is being offered.

Wearing, as usual, my receiver hat, I still don't see any reason to be
interested in random senders' opinions about the relative merits of
various algorithms.

Like I said before, let's say someone publishes SSP saying sha256 is
deprecated and rot13 is shiny and new.  What should I do with that info?

Assuming we agree that it's stupid and I should ignore it, how am I
supposed to tell stupid deprecation advice from non-stupid deprecation
advice?

Regards,
"I shook hands with Senators Dole and Inouye," said Tom, disarmingly.

---

From: "Charles Lindsey" <[email-masked]>
Date: Tue, 27 Feb 2007 12:51:28 -0000

> policies, accept A (RA), accept B (RB) and accept A or B (RAB).

I don't think it's necessarily anything to do with the strengths of
algorithms or with deprecating anything. All we know is that the signer
has declared that he signs with two algorithms A and B, where the
deployment of A and B within verifiers worldwide may be different
(withoiut loss of generality, we are supposing that deployment of B is
worse than for A).

Why is the signer signing with two algorithms?

. Maybe because he is transitioning from A to B
. Maybe because dome dreadful flaw has been found in A
. Maybe because he thinks (rightly or wrongly) that B is (slightly) more
secure than A.
. Maybe because B consume less CPU resources to generate/verify
. Maybe because A's Patent Lawyers are leaning on him to pay royalties
. Maybe because it's Monday
. Maybe because he is plain stupid.

Whatever. That is what he has done, and the rest of the world has to live
with it and try somehow to keep the mail flowing and the spammers at bay.

And maybe the verifiers are stupoid too, and fail to implement the
algorithms they should be implementing, for eqally varied reasons.

---

From: "Charles Lindsey" <[email-masked]>
Date: Tue, 27 Feb 2007 12:52:13 -0000

On Mon, 26 Feb 2007 15:13:27 -0000, John Levine <[email-masked]> wrote:

>> broken).
>> detailed

If there was no signature present, then you consult the SSP of the From
(whatever) header to see if there should have been one.

Otherwise you have in front of you a signature, and its various tags tell
you that it uses

version dkim-2
algorithm rsa-sha-foo
canonicalization complicated/strained
signing-domain foo.example.com
retrieval machanism dns/funny
and, of course, the actual signature

and you have a Magic piece of software to which you give the whole thing.

Now IF the software knows how to use all of dkim-2, rsa, sha-foo,
complicated, strained and dns/funny, and IF it succeeds in obtaining a
public key for foo.example.com using dns/funny,
THEN it will verify the signature and report SUCCESS of FAIL (and maybe
the FAIL is PERM or TEMP).

But IF it does not know how to use all those things, or cannot obtain the
Public Key, then it is supposed to report FAIL.

BUT, if the Magic piece of software is Smart and Clever, it will tell you
that it failed because "I do not do sha-foo (or whatever)", or that the
format of the signature was clearly corrupted, or that the signature
failed, of that it failed but the body hash was correct. And so on.

If it reported SUCCESS (and if the signing domain matched the From header,
or whatever your policy required), then you accept the message.

But if it Reported FAIL, then you either bury your head in the sand and
reject the message regardless, or else you consider what the Magic
software actually told you, and in particular whether the failure might
have been because your Magic software was insufficient for the task, in
which case the message might well have been genuine after all.

So you consult the SSP for the signing domain to see whether the
combination of dkim-2, rsa, sha-foo, complicated, strained and dns/funny
could have come from that domain, and if so whether there should have been
a further signature which you ought to check. And then you have sufficient
information to decide whether it had failed because your Magic software
was inadequate, or because it was a bogus signature from a spammer.

Q.E.D.

---

From: "Charles Lindsey" <[email-masked]>
Date: Tue, 27 Feb 2007 13:02:12 -0000

> both A and B and any signature you see from me will have both,

The problem is that we cannot foresee (remember we are merely discussing  
SSP requirements now, not SSP itself) what may be needed for SSP in the  
future in order to counter threats we cannot even dream of at the moment.

Therefore, one requirement I would like to see for SSP is that its  
notation should be _extensible_. Indeed, using XML for reporting SSP  
policies might be a good way to go about it (except that XML is a bit  
verbose if it has to be squashed into DNS records somehow).

>    attacks, verifiers MAY limit the total number of signatures they will

And that SHOULD in base is blatantly WRONG. You cannot instruct verifiers  
as to what they SHOULD or SHOULD NOT (or even MUST) do. They are free  
agents and can do what they like.

But, in any case, we are not concerned with "failed" signatures (to which  
that SHOULD applies) here. We are concerned with signatures that are quite  
possibly valid, but where the verifier does not possess the tools needed  
to verify them. Base is totally silent on what to do in that situation.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 27 Feb 2007 13:06:05 +0000

Charles Lindsey wrote:
[big snip describing use of Magic s/w]
> And then you have sufficient

Not quite. Whatever policy anyone publishes is public. Any spammer
can always replicate everything correctly with the exception of
the signature bits and thus create a message that appears to adhere
to policy but with a broken signature.

Seems to me that that's a *very* good reason to ignore the entire
FAILed signature and not to use any supposedly Magic s/w.

What have I missed?

Stephen.

---

From: Douglas Otis <[email-masked]>
Date: Tue, 27 Feb 2007 08:51:54 -0800

On Feb 26, 2007, at 11:56 PM, John R Levine wrote:

>>> This protection depends upon a means for the signer to assert  
>>> which algorithm is deprecated, and what shiny new algorithm is  
>>> being offered.
>
> Wearing, as usual, my receiver hat, I still don't see any reason to  
> be interested in random senders' opinions about the relative merits  
> of various algorithms.
>
> Like I said before, let's say someone publishes SSP saying sha256  
> is deprecated and rot13 is shiny and new.  What should I do with  
> that info?

Why validate a signature from a domain you do not trust?  Validating  
signatures indicates the defeat of protections placed ahead of the  
verification process.

If your verifier performs rot13, and you too believe it to be  
stronger than sha256, then this information immediately protects an  
upgraded verification process from a possible downgrade vulnerability  
that might last years otherwise.

The hash algorithm is an unlikely cause for a problem, but following  
your unlikely example:

You receive a message where the key for sha256 requests rot13 be used  
instead.  When the rot13 signature is missing, essentially the signer  
has requested sha256 to then be considered invalid.  If you do not  
know anything about rot13, then continue to use sha256.

When the message is only signed with rot13 and the policy indicates  
messages are always signed, but you don't know anything about rot13,  
then consider the message to be outside the signer's policy.  By  
applying both sha256 and rot13 signatures, compliance with the policy  
is retained.  By defining a "please use" field in the sha256 key, a  
possible downgrade attack can be avoided can be avoided without _any_  
added transactions. : )

> supposed to tell stupid deprecation advice from non-stupid  
> deprecation advice?

You have exactly the same problem with _any_ signature.  If you do  
not trust domain foo, then no matter what signature is applied, you  
still will not trust domain foo.

When you trust domain foo and you also want to avoid problem X as  
soon as possible, then you'll also want to known when you can safely  
refuse messages having problem X without disrupting a large  
percentage of your email.  Not allowing or ignoring information that  
protects verifiers from a downgrade attack seems foolish.  But then  
again, why validate DKIM signatures when the signer is not trusted?

-Doug

---

From: Jim Fenton <[email-masked]>
Date: Tue, 27 Feb 2007 15:18:44 -0800

If you mean to just require that and not actually list the algorithms, 
the verifier would have no way of determining what algorithms the signer 
uses, without a list of all its selector names.

If you mean to list the algorithms, isn't that what Phill is proposing?

-Jim

---

From: Jim Fenton <[email-masked]>
Date: Tue, 27 Feb 2007 16:17:54 -0800

> wrong. Please stop repeating it or support your statement.
Absent this mechanism, a message which has at least one valid signature 
on behalf of the From address [assuming some other decisions that are 
pending] does not need to consult SSP.

With a mechanism in SSP to specify the signature algorithms that should 
be present, it is always necessary to consult SSP to find out the list 
of required signature algorithms.  This, I believe, is the additional 
lookup for every signed message to which Dave refers.

Mark Delany mentioned that this information could be included in the 
selector records (presumably via an extension, since this isn't in 
-base).  This would remove the need to consult SSP on signed messages, 
but then it's not clear that it's an SSP mechanism any more.

-Jim

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 27 Feb 2007 18:08:34 -0800

At 4:17 PM -0800 2/27/07, Jim Fenton wrote:
>With a mechanism in SSP to specify the signature algorithms that 
>should be present, it is always necessary to consult SSP to find out 
>the list of required signature algorithms.

Why?!?! If one of the signatures is good, there is no need to do the 
SSP lookup.

--Paul Hoffman, Director

---

From: Douglas Otis <[email-masked]>
Date: Tue, 27 Feb 2007 19:10:34 -0800

On Feb 27, 2007, at 6:08 PM, Paul Hoffman wrote:

>> should be present, it is always necessary to consult SSP to find  
>> out the list of required signature algorithms.
>
> Why?!?! If one of the signatures is good, there is no need to do  
> the SSP lookup.

This is purely hypothetical.  This is not to suggest DKIM has some  
major flaw, only that once it starts being used, better approaches  
might be found.

Imagine a different canonicalization handling EAI related headers  
avoids some exploit induced by a diffusion of approaches dealing with  
these oft modified headers.  The new canonicalization algorithm  
removes ambiguity and secures critical information while not also  
directly capturing the oft modified headers.  This agility is  
preferred by international senders over the canonicalization  
algorithms currently defined.  The same approach could be used with  
any algorithmic aspect of the DKIM signing process.  Imagine also  
that signing existing DKIM headers proves problematic when other DKIM  
headers are added, but then perhaps rearranged.

A downgrade attack can be prevented without the use of overlapping  
signatures by allowing a "algorithmic signer policy" to be placed  
within the existing key, such as a parameter that explicitly defines  
the key/signature pair being deprecated.  This parameter could be as  
simple as "d=c/eai", where 'c/eai' represents the shiny new algorithm  
"c=eai" specified within the signature.  An upgraded verifier will  
likely select the improved algorithm found in one of the two  
signatures added to the message.

When a message has had the signature containing the "c=eai" removed,  
and the verifier supports "c=eai", then upon seeing the "d=c/eai"  
parameter within a key supporting the signature containing  
"c=simple", this message can be detected a possible downgrade  
attack.  This "d=c/eai" represents an aspect of signer policy which  
is extremely important when making an assertion that "all messages  
are signed" in separate policy record.

An attacker might remove the signature supporting "c=simple" knowing  
most verifiers are unable to handle the new "c=eai", but a key check  
makes it appear as if the sender no longer signs using "c=simple".   
An attacker may also remove the signature supporting "c=eai" and then  
make changes where some verifiers do the wrong thing in the face of  
the EAI complexities.  Again, this is purely hypothetical.  At some  
point, any algorithm being used in DKIM will need to be deprecated.   
Only the signer is able to support a deprecation strategy.  DKIM  
currently does not support a practical method, but can be added now  
without making any changes to current implementations.

-Doug

---

From: Jim Fenton <[email-masked]>
Date: Tue, 27 Feb 2007 21:08:45 -0800

Phillip Hallam-Baker wrote:
> If the message has any valid, acceptable sig you accept and the policy 
> record is never read.
>
> So no, there is no extra lookup.
I at least partially misunderstood the proposal then, and I doubt that 
I'm alone. Apologies to Phill, who explained this to me over lunch at 
RSA as well.

The idea here, as I understand it now, is to provide some additional 
information about messages that contain a signature a verifier can't 
verify.  Rather than considering the SSP result for such messages to be 
"unknown, because I can't determine whether that signature is valid or 
not", it provides a way for the verifier to be able to say "I know that 
this fails SSP, because it lacks another signature that should be there 
(and that I probably would understand)".

The related attack would be as follows:  A signer might deploy a 
brand-new signature algorithm (I'll call it N) that very few verifiers 
can yet handle.  The attacker sees this, and starts forging messages 
with invalid signatures referencing the N selector, in hopes that some 
verifiers will accept the message on the premise that they're just not 
"smart enough" to verify using N yet.  If this were to happen, it would 
introduce a problem getting signers to start using new algorithms.

Of course a solution to this is to make sure all verifiers treat 
signatures they can't verify (as well as those that fail verification) 
as if the signatures aren't there.  But perhaps some of the verifiers 
won't do this, because they don't want to risk adverse consequences from 
taking action against such messages.

But the downgrade attack described in the last paragraph of Phill's 

> There is also a downgrade attack using essentially the same principle except that in this case algorithm A is actually broken and Algorithm B has a sunstantial amount of deployment. Instead of crea…
would require that SSP be consulted in all cases, because the attacker 
is able to forge a valid signature.  However, I think this is adequately 
dealt with by the signing domain removing all selectors that reference 
the broken algorithm.

I am also concerned that this is a multi-dimensional problem which may 
lead to some very complex policy records.  In addition to the signing 
and hash algorithms, the body and header canonicalization algorithms are 
likely to invite this sort of policy treatment.  This would be easier 
for the attacker, since unlike the hash and signature algorithms, the 
acceptable canonicalization algorithms aren't called out in the key 
record (although an extension could be defined to do that).

My overall inclination right now is that trying to distinguish a message 
that definitely fails SSP from a message that has an unknown SSP 
(because the verifier doesn't know how to verify it) is putting too fine 
a point on SSP.  The "unknown SSP" case should just be treated as "fails 
SSP" and the signer should be cajoled into providing useful signatures.

-Jim

---

From: Douglas Otis <[email-masked]>
Date: Tue, 27 Feb 2007 21:47:02 -0800

On Feb 27, 2007, at 9:08 PM, Jim Fenton wrote:

> My overall inclination right now is that trying to distinguish a  
> message that definitely fails SSP from a message that has an  
> unknown SSP (because the verifier doesn't know how to verify it) is  
> putting too fine a point on SSP.  The "unknown SSP" case should  
> just be treated as "fails SSP" and the signer should be cajoled  
> into providing useful signatures.

There is the what-if-no-signature policy record, and the what-if- 
deprecated policy parameter that can be placed within the key record.

By adding a deprecation assertion that essentially describes the  
desired parameter that should be within a companion signature, then  
this defeats a downgrade attack without any additional transactions  
requesting a what-if-no-signature policy record, or any change made  
to the current structure.

All that is needed to ensure a downgrade attack can be defeated in  
the future would be to define the deprecation assertion within the  
existing key.

This might be as simple as:

  d=<tag>/<companion-parameter>[:...];

-Doug

---

From: Hector Santos <[email-masked]>
Date: Wed, 28 Feb 2007 08:21:55 -0500

> taking action against such messages.

Don't you see why?

Failed Signature Unsigned Status Promotion  (FSUSP) is the easy way out 
for any failed reason and it also makes it easy to exploit.  FSUSP also 
tells bad guys,

     "Huh? There isn't a need to send signed messages fake or otherwise."
     The verifier still needs to operate in "legacy mode" and if
     supports FSUSP to the letter, its going to ignore the invalidation
     anyway."

The general concern is related to FSUSP abuse.

> dealt with by the signing domain removing all selectors that reference 

Again, with the idea that you wish to trigger FSUSP.  It really doesn't 
matter how it is done. FSUSP is still the problem in my view.

> SSP" and the signer should be cajoled into providing useful signatures.

I think the issue is overblown.

First, there needs to be a sense of "purpose" to even consider DKIM 
processing. So when we offer the switch in our mail processor setup:

    [_] Enable DKIM Verification

The F1 HELP has to provide the good reasons for this.

There are three basic outcomes with a message:

    VALID SIGNATURE
    INVALID SIGNATURE
    NO SIGNATURE

Of course, how this is handled is local policy.  But INVALID status is 
not the same as NO SIGNATURE status.  We can make it behave as 
DKIM-BASE, but practically it most likely will not be implemented 100% 
according to the spec's recommendation.  There will be some "Status" 
given to it.

Now, we can augment it with a DOMAIN POLICY layer and for the sake of 
simplicity, lets call it SSP but it can be anything, including 
White/Black/Grey Listing or even some "REPUTATION" system. In either 
case, it is a "HELPER"

Without the helper, we are left with the DKIM-BASE "good needle in the 
haystack" mode of operaton which will create a very high DKIM processing 
problem (based on the fundamental premise there is always more bad mail 
than good coming in A.K.A "The Spam Problem - Its why we are here").

With a SSP helper, it can help eliminate the OBVIOUS problems in the 
unknown wide spectrum of possible reasons for failure:

   - No Mail expected from this domain
   - Signature expected, but not provided
   - Signature not expected, but it was provided

These are the OBVIOUS ones and the ones I believe will be highly 
benefitial and more used.

The others that we still havn't resolved:

   - 3rd party signed, but it wasn't allowed or expected

The issue related to HASH method can only be resolved two ways:

   1) The signer uses the lowest common demoninator in all signings
      including the new unknown hash method.

   2) The signer predetermines the verifier capabilities rather than
      take its chances with FSUSP issues.

Without something like this, it is a failure and as you say, it can fall 
into the FSUSP mode and that just breeds even more abuse and uncertainty.

Just consider if the signer has a "MUST SIGN" SSP, then FSUSP might even 
  promote a rejection because of its new "unsigned status."  I don't 
think this is what the authors wanted but that is exactly what can happen.

--
HLS

---

From: "Charles Lindsey" <[email-masked]>
Date: Wed, 28 Feb 2007 14:06:33 -0000

> to policy but with a broken signature.

The spammer cannot produce a good signature. If you see a broken signature  
with algorithm B, and the SSP tells you that the sender always signs with  
B (and possibly others) and you do not see any signatures for those  
others, then you reject the message on the grounds that it appears to be  
signed by someone who did not have the proper key.
> FAILed signature and not to use any supposedly Magic s/w.

But a signature using an algorithm that you do not know how to verify is  
not "FAILED" in any meaningful sense of that word (whatever Base may say).  
So it is grounds for consulting the SSP to see whether the signer has  
provided for this situation (e.g. by always providing an additional  
signature with the older algorithm A).

> What have I missed?

The distinction between a signature that you knew how to verify and which  
turned out to be broken, and a signature that you did not know how to  
verify.

---

From: "Charles Lindsey" <[email-masked]>
Date: Wed, 28 Feb 2007 14:14:36 -0000

> lookup for every signed message to which Dave refers.

False!

If the SSP tells you that he signs with A and B, then presumably the  
selector records will include keys appropriate for use with A and B. If  
you see a valid signature with any key in the selector records, then you  
never need to go to the SSP.

Now if the signer had also provided a key in the selector records for  
algorithm C, and had failed to mention C in his SSP, then he is being  
stupid and deserves all he gets, because people who find a valid signature  
using C will never consult his SSP.

---

From: "Charles Lindsey" <[email-masked]>
Date: Wed, 28 Feb 2007 14:30:58 -0000

John doesn't seem to have sent this to the list (maybe because a sent  
separate copies to him and to the list).

On Tue, 27 Feb 2007 07:30:03 -0000, John L <[email-masked]> wrote:

>> combination of dkim-2, rsa, sha-foo, complicated, strained and  
>> dns/funny could have come from that domain, and if so whether there  
>> should have been a further signature which you ought to check. And then  
>> you have sufficient information to decide whether it had failed because  
>> your Magic software was inadequate, or because it was a bogus signature  
>> from a spammer.
>
> You know, spammers can fetch SSP records just like you can and can use  
> them to concoct bogus signatures.
>
> Could you do me a favor and sketch out in pseudocode the algorithm to  
> distinguish an actual signature made with a signature algorithm you  
> can't check from a fake signature applied by a spammer who looked at the  
> SSP and made up a signature identical in all regards to a real one  
> except that the unverifiable signature bits are random?

You can't tell that, but you don't need to.

If the SSP says "I always sign with A and B", and the spammer reads that,  
then he knows he has to produce fake signatures for both A and B. So if he  
only provides a fake B, then you know he is spamming.

OTOH, if he provides a fake A and a fake B, then even though you can't  
check B, you can still detect that the fake A does not verify (because you  
DO know how to check A).
>
> While you're at it, how about the same thing to distinguish a real  
> message signed with a body hash you can't check from a spam that took  
> the headers and signature from a real message and a new spam body.

In exactly the same way. If the signer only uses an algorithm (including  
its hash) that you cannot verify, then you are stuck (and the signer was  
stupid for signing only with a not-widely-known hash). But if the signer  
went to the trouble of signing twice (using both older and new hashes),  
and published that fact in his SSP, then you are safe if you manage to  
verify using one of them.

---

From: Arvel Hathcock <[email-masked]>
Date: Wed, 28 Feb 2007 18:41:21 -0600

> algorithm is deprecated, and what shiny new algorithm is being

That doesn't follow at all.  The *receiver* will decide what algorithms 
are and are not sufficient and when to act on that decision.  And 
besides, the means by which a *sender* can assert which algorithm they 
like is to just stop signing with the one(s) they don't.  Whether and 
when to do that is a decision the sender will have to make.  I don't see 
how policy plays a role in any of this.

I'm starting to think that I'm completely missing something fundamental. 
  I might need some education in Prague if folk have time.

Arvel

---

From: Douglas Otis <[email-masked]>
Date: Wed, 28 Feb 2007 17:39:20 -0800

On Feb 28, 2007, at 4:41 PM, Arvel Hathcock wrote:

> That doesn't follow at all.  The *receiver* will decide what  
> algorithms are and are not sufficient and when to act on that  
> decision.

For sake of argument, imagine a new canonicalization algorithm has  
been created that handles EAI style addresses.  EAI defines twin UTF8  
email addresses which might be modified, but are not yet fully  
accommodated by DKIM.  Left to verifier heroics, some poor choice  
results in some implementations.  Messages may appear to be unsigned  
leaving recipients exposed to spoofing, or results in a possible  
exploit.  One can claim verifiers should not attempt heroics, but  
implementers are dealing with an unforeseen situation not covered in  
the initial specifications.

Rather than not signing with just the now problematic widely  
supported signature algorithm, the signer decides to add two  
signatures to the message.  Rather than overlapping signatures which  
might introduce unexpected problems when other signatures are also  
added, a deprecation mechanism is defined and placed within the key  
of the now deprecated signature.  This mechanism simply defines which  
tags and parameters must be found in the companion signature.  This  
approach can be used to deprecate _any_ of the signature related  
algorithms, although such is not likely needed for hash and signature  
algorithms.

The *verifier* should attempt to find the strongest mutually  
supported algorithm supported by the *signer* and not just any  
supported algorithm.  Only the *signer* can offer a choice.  Some  
mechanism is need to prevent a bad actor from removing an option in a  
manner not detected by the *verifier*.  Overlapping signatures might  
be a poor choice when defending against this type of problem.  Header  
order should not be assumed and can become even more confusing when  
multiple domains are involved with twin email address header  
assurances.   Don't forget about the 'i=' limitation.

> And besides, the means by which a *sender* can assert which  
> algorithm they like is to just stop signing with the one(s) they  
> don't.  Whether and when to do that is a decision the sender will  
> have to make.  I don't see how policy plays a role in any of this.

Suddenly dropping a widely deployed algorithm will cause most of  
there messages appear to be unsigned.  This is likely to be a worse  
outcome than that of some exploit that might be problematic with some  
vendors.  By having a deprecation mechanism available, the signer  
does not need to make the choice between a rock and a hard place.  A  
deprecation mechanism also allows broad protection once the new  
algorithm is embraced by major providers, even when stragglers may  
take years to upgrade.

-Doug