Subject: [ietf-dkim] Issue 1386 and downgrade attacks

From: Eric Allman <[email-masked]>
Date: Mon, 26 Feb 2007 14:31:15 -0800

Folks, I've been trying to understand the issues here, and I just 
can't seem to wrap my head around it, which means that either (a) 
there isn't actually an issue, and (b) there is and I just don't get 
it.  Let me try to argue for why (a) looks to be true to me.

There are three algorithms that might transition: the Signature 
Algorithm, the Hash Algorithm, and the Canonicalization Algorithm. 
I'll take those one at a time.  But first, let me rephrase EKR's 
model slightly, since it should apply to all the cases.  I'm adding a 
case SN here to mean "sender does not sign at all".  I'm also 
ordering things a bit differently so that the expected transition 
moves from the top left to the bottom right:

        RA      RAB     RB
SN      N*      N*      N*
SA      A       A       X*
SAB     A       AB      B
SB      X*      B       B

Of course N means that there is no signature to verify and X means 
there is a signature that cannot be validated.  Pragmatically X and N 
have the same semantics since -base says that an unverifiable 
signature is equivalent to no signature. "*" means that the recipient 
will do an SSP lookup, at least as we (well, myself at least) 
currently envision things.  Also, any signature that R cannot verify 
is treated as the SN case.

ASSUMPTION 1: A < B strength-wise.

ASSUMPTION 2: No old algorithm A becomes "too weak" overnight, where 
"too weak" means that there is a feasible exploit before a transition 
can complete (that is, until no "interesting" R use algorithm A). 
If, for example, someone figures out a way to crack RSA in O(N) time, 
then we (and the entire rest of the net) need to move off of it at 
once, and we are all hosed, and frankly DKIM will not be the biggest 
problem on the net.  The exception to this is Canonicalization, since 
that applies only to DKIM (but see below).

ASSUMPTION 3: Attackers can not change or insert selector records for 
S.  If that were true then this wouldn't be a downgrade attack, and 
there are lots of simpler ways to forge messages.

CASE I: SIGNATURE ALGORITHM

Scenario: S (the sender) starts signing using both A and B, and 
publishes selectors for each (i.e., we move down in the chart from SA 
to SAB).  As the time goes on we move from left to right in the 
chart: R first checks using A, then can try either (and presumably 
prefers B), then refuses to use A any more.  If S still does not 
implement B then we've dropped back to the SN case.  This is the 
O(years) transition.  If an attacker can successfully mount an attack 
using A during this transition time (i.e., before S pulls all 
selectors using A), then Assumption 2 (that A is not "too weak") is 
not true, and we have bigger problems as described above.

If R upgrades first, then we move right and then down rather than 
down and then right, but the arguments remain the same.

If S only uses B, an attacker trying to use A would have to somehow 
be able to create a selector for an A key, but that violates 
Assumption 3.

ASSUMPTION 4: Keys for algorithms A and B are not compatible.  This 
is ensured by the k= tag in the selector.

There might be a case where S supports both A and B but chooses which 
algorithm it uses based on knowledge of R (for example, S always 
signs with B but includes or excludes A based on some exception 
list).  In this case an attacker might sign a message using A and a 
valid selector.  But this violates Assumption 2.

CASE II: HASH ALGORITHM

The transition is similar.  If A is shown to have a feasible 
pre-imaging attack, then Assumption 2 is violated and S has to stop 
publishing selectors using A --- and by the way every protocol on the 
net using A is also vulnerable.  For example, if A == SHA-1 then DKIM 
isn't the biggest target out there.

S can indicate which hash algorithms it uses by using h= in the 
selector record, so this case pretty much reduces to the previous 
one.  This implies that although h= is optional, it should always be 
used once there are any deprecated hash algorithms --- not an onerous 
requirement.

CASE III: CANONICALIZATION ALGORITHM

This one is somewhat different from the others, since there is no way 
for S to communicate to R which canonicalization algorithms it uses. 
However, since the DKIM-Signature header field is included in the 
signature and that field includes the canonicalization algorithm, 
then for an attacker to change a message would be equivalent to 
either I or II.

CASE IV: SIGNATURE AND HASH ALGORITHMS SIMULTANEOUSLY

There may be a case that would be problematic.  Suppose both the 
signature and hash algorithms were changing at once.  We have 
signature algorithms A and B, and hash algorithms H and J.  Let us 
further suppose that for some reason

   AH << AJ < BH < BJ

In particular, AH is an unacceptable ("too weak") algorithm 
combination, but any of the other combinations are strong enough (the 
ordering between them is irrelevant).  In this case there is no way 
for S to tell R not to use AH, and just has to rely on all the Rs out 
there to be smart about it.  I suspect this isn't a terrible burden 
on receivers if this understood when the software is upgraded (that 
is, when the RABHJ code is installed).  If it's not understood then 
there is a problem.  To fix this rather unlikely case would require a 
policy lookup on every message and a policy language rich enough to 
express the combinations.  My take is that it is unlikely enough that 
not handling it is a valid engineering tradeoff.

EPILOGUE

Much of this relies a lot on Assumption 2, and perhaps that's what 
actually being discussed in this straw-poll thread.  But I think I've 
argued for why that's a good assumption.  In summary, this why I 
think we should just close 1386.

Fire away.

eric

[By the way, there was also some confusion about whether transitions 
are O(years) or O(days).  Changing selector records is O(days), 
whether or not those selectors change algorithms, but changing 
algorithms requires software updates and hence is O(years).]

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

---

From: Douglas Otis <[email-masked]>
Date: Mon, 26 Feb 2007 16:23:47 -0800

On Feb 26, 2007, at 2:31 PM, Eric Allman wrote:

> there isn't actually an issue, and (b) there is and I just don't  
> get it.  Let me try to argue for why (a) looks to be true to me.
>

There are more aspects related to DKIM than just signature, hash, and  
canonicalization algorithms.  At this point, it would be difficult to  
predict which area will prove most problematic.  Assumptions about  
header ordering together with weak associations may prove to be a  
problematic area.

> model slightly, since it should apply to all the cases.  I'm adding  
> a case SN here to mean "sender does not sign at all".  I'm also  
> ASSUMPTION 2: No old algorithm A becomes "too weak" overnight,  
> where "too weak" means that there is a feasible exploit before a  
> transition can complete (that is, until no "interesting" R use  
> algorithm A). If, for example, someone figures out a way to crack  
> RSA in O(N) time, then we (and the entire rest of the net) need to  
> move off of it at once, and we are all hosed, and frankly DKIM will  
> not be the biggest problem on the net.  The exception to this is  
> Canonicalization, since that applies only to DKIM (but see below).

DKIM also has other unique features.

> ASSUMPTION 3: Attackers can not change or insert selector records  
> for S.  If that were true then this wouldn't be a downgrade attack,  
> and there are lots of simpler ways to forge messages.

However it might be possible to incorporate deprecation information  
into various third-party services to bolster possible server weaknesses.

> publishes selectors for each (i.e., we move down in the chart from  
> SA to SAB).  As the time goes on we move from left to right in the  
> implement B then we've dropped back to the SN case.  This is the O 
> (years) transition.  If an attacker can successfully mount an  
> attack using A during this transition time (i.e., before S pulls  
> all selectors using A), then Assumption 2 (that A is not "too  
> weak") is not true, and we have bigger problems as described above.

However, during an N year transition, a verifier is still be prone to  
a downgrade attack.  Such an attack might only be seen by high value  
targets.

> be able to create a selector for an A key, but that violates  

During a long transition, the B only option will be highly  
disruptive.  This disruption prevents prompt prevention of downgrade  
attacks, even when both signer and verifier have upgraded without a  
means to assert that an algorithm has been deprecated.

> There might be a case where S supports both A and B but chooses  
> which algorithm it uses based on knowledge of R (for example, S  
> always signs with B but includes or excludes A based on some  
> exception list).  In this case an attacker might sign a message  
> using A and a valid selector.  But this violates Assumption 2.

The level of exposure may vary depending upon target value.  A high  
value target may see expensive exploits at a rate higher than  
generally seen elsewhere.  The signer may need to wait a long time  
before being able to drop a problematic algorithm.  Selectively using  
a algorithm based upon the recipient would be fairly onerous.  The  
actual endpoint of the message is not really known, where verifier  
compliance can not be easily determined.  Once a majority of users  
are protected by adoption of a newer algorithm in conjunction with a  
deprecation assertion, this will greatly reduce the opportunity for a  
successful exploit.

> CASE II: HASH ALGORITHM
>
> The transition is similar.  If A is shown to have a feasible pre- 
> imaging attack, then Assumption 2 is violated and S has to stop  
> publishing selectors using A --- and by the way every protocol on  
> the net using A is also vulnerable.  For example, if A == SHA-1  
> then DKIM isn't the biggest target out there.
>
> one.  This implies that although h= is optional, it should always  
> be used once there are any deprecated hash algorithms --- not an  
> onerous requirement.

The level of expense needed to stage an attack may limit the number  
of sites exploited.  The exploit overhead might change some  
assumptions when compromised systems are focused into attacking  
specific targets, for example.  This might have a significant payoff  
when these messages are otherwise trustworthy.

> This one is somewhat different from the others, since there is no  
> way for S to communicate to R which canonicalization algorithms it  
> uses. However, since the DKIM-Signature header field is included in  
> the signature and that field includes the canonicalization  
> algorithm, then for an attacker to change a message would be  
> equivalent to either I or II.

There are already changes coming that might wreck havoc with DKIM  
canonicalization.  What changes might be required to thwart  
weaknesses created when EAI headers are adopted?  There are also  
known weaknesses with respect to signature/header association.  These  
weaknesses may be an inability to ensure a verifier is not also  
exposed to DDoS exploit without also foregoing DKIM protections.

> combination, but any of the other combinations are strong enough  
> (the ordering between them is irrelevant).  In this case there is  
> no way for S to tell R not to use AH, and just has to rely on all  
> the Rs out there to be smart about it.  I suspect this isn't a  
> terrible burden on receivers if this understood when the software  
> is upgraded (that is, when the RABHJ code is installed).  If it's  
> not understood then there is a problem.  To fix this rather  
> unlikely case would require a policy lookup on every message and a  
> policy language rich enough to express the combinations.  My take  
> is that it is unlikely enough that not handling it is a valid  
> engineering tradeoff.

By adding a "Please use X" to the AH algorithm within the key or  
signature would not require a rich language or additional  
transactions.  If X is not available, then AH would be invalid.  This  
simple statement prevents a downgrade attack, which is especially  
important when verifiers understand X.

> actually being discussed in this straw-poll thread.  But I think  
> I've argued for why that's a good assumption.  In summary, this why  
> I think we should just close 1386.
>
> Fire away.

Rather than assuming nothing unexpected will be discovered in coming  
years, plan for a graceful transition now.  This may greatly increase  
the protection DKIM offers in the face of adversity.  This involves  
rather simple definitions that can remained unused until a problem  
becomes evident.

-Doug

---

From: Eliot Lear <[email-masked]>
Date: Tue, 27 Feb 2007 09:41:14 +0100

Eric,

I agree with your analysis, which only leads to the question of whether 
or not Assumption 2 is reasonable.  I think we have operational 
experience that says that it is, but even if it were not, if an 
algorithm is broken and people care they will put pressure on their 
vendors to provide updates.  One can then apply a weighting to various 
valid signatures.  Furthermore, I claim that in a algorithm fast 
transition there otherwise is no neat solution, because one is depending 
on the administration of other systems for a transition to complete.

And so going back to Phillip's message:

> 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 this case, the recipient should discard the signature.  Since there 
will be no valid signature using algorithm A, the message will be 
treated according to SSP.  I see no problem, except with short 
transitions, since in these proposed circumstances  recipient would be 
unlikely to trust the sender's algorithm A, leaving no way for the 
recipient to validate the message.

Eliot

---

From: Eric Allman <[email-masked]>
Date: Wed, 28 Feb 2007 09:23:03 -0800

(For some reason Charles didn't copy the group on his reply to my 
message, so I've included the entire thing even though I only have 
one comment.

--On February 27, 2007 1:16:05 PM +0000 Charles Lindsey 
<[email-masked]> wrote:

> On Mon, 26 Feb 2007 22:31:15 -0000, Eric Allman
> <[email-masked]>  wrote:
>
>>         RA      RAB     RB
>> SN      N*      N*      N*
>> SA      A       A       X*
>> SAB     A       AB      B
>> SB      X*      B       B
>>
>> there   is a signature that cannot be validated.  Pragmatically X
>> and N have the   same semantics since -base says that an
>> unverifiable signature is   equivalent to no signature. "*" means
>> that the recipient will do an SSP   lookup, at least as we (well,
>> myself at least) currently envision   things.  Also, any signature
>> that R cannot verify is treated as the SN   case.
>>
>
>> SA to   SAB).  As the time goes on we move from left to right in
>> the chart: R   first checks using A, then can try either (and
>> presumably prefers B),   then refuses to use A any more.
>
> Stop right there!
>
> Go back to the time before R starts using B (i.e. we are in state
> SAB  + RA).
>
> That state may persist for some considerable time (>>days, if not
> quite  years), and that is the window of opportunity for the
> attacker.
>
> He constructs bogus messages signing them with B (who cares whether
> they  are valid or not?).
>
> R cannot check their validity, but he can recognise that B is a
> valid  algorithm for messages sent from S, and also that "S signs
> everything".  So, knowing that the problem is likely at his end, he
> allows the (bogus)  messages through.

Any R that allows a signature through that it can't verify just 
because there is a DKIM-Signature header field in the message 
deserves everything it gets.  I'm not interested in adjusting the 
protocols to make life easier on outrageously stupid implementations.

I guess I need to add a new assumption to my analysis:

ASSUMPTION 5: Whoever implements the verifier at R must actually 
implement the specification as written.

> The proposed solution is that the SSP should enable S to say "I
> sign  everything with both A and B". In that case, R can observe
> that an A  signature (which be could have verified) is absent, and
> so he knows it is  bogus.

eric

---

From: Eric Allman <[email-masked]>
Date: Wed, 28 Feb 2007 10:00:03 -0800

--On February 26, 2007 4:23:47 PM -0800 Douglas Otis 
<[email-masked]> wrote:
> There are more aspects related to DKIM than just signature, hash,
> and  canonicalization algorithms.  At this point, it would be
> difficult to  predict which area will prove most problematic.
> Assumptions about  header ordering together with weak associations
> may prove to be a  problematic area.

Yes, it may be a problematic area, but it is completely irrelevant to 
this discussion.

>> model slightly, since it should apply to all the cases.  I'm
>> adding   a case SN here to mean "sender does not sign at all".
>> I'm also   ordering things a bit differently so that the expected
>> transition   moves from the top left to the bottom right:
>>        RA      RAB     RB
>> SN      N*      N*      N*
>> SA      A       A       X*
>> SAB     A       AB      B
>> SB      X*      B       B
>>
>>  move off of it at once, and we are all hosed, and frankly DKIM
>> will   not be the biggest problem on the net.  The exception to
>> this is   Canonicalization, since that applies only to DKIM (but
>> see below).
>

Yes, it does.  But that's also irrelevant to this discussion.

>> for S.  If that were true then this wouldn't be a downgrade
>> attack,   and there are lots of simpler ways to forge messages.
>

I have no idea what you are talking about here.  Third parties such 
as reputation servers?

>> presumably   prefers B), then refuses to use A any more.  If S
>> still does not   implement B then we've dropped back to the SN
>> case.  This is the O  (years) transition.  If an attacker can
>> successfully mount an   attack using A during this transition time
>> (i.e., before S pulls   all selectors using A), then Assumption 2
>> (that A is not "too   weak") is not true, and we have bigger
>> problems as described above.
>
> However, during an N year transition, a verifier is still be prone
> to  a downgrade attack.  Such an attack might only be seen by high
> value  targets.

No, that's just wrong.  That's the point of my posting.  If you have 
something valuable to say about my logic (I accept that it could be 
wrong) then please point it out, but don't just keep waving the 
"downgrade attack" flag.  And the point about high value targets is 
irrelevant.  The spec is designed to work for everyone.

>> If S only uses B, an attacker trying to use A would have to
>> somehow   be able to create a selector for an A key, but that
>> violates   Assumption 3.
>
> disruptive.  This disruption prevents prompt prevention of
> downgrade  attacks, even when both signer and verifier have
> upgraded without a  means to assert that an algorithm has been
> deprecated.

I'm tempted to say "well, duh."  That's the reason why senders will 
probably want to support both A and B for a fairly long period.  But 
there will always be some verifiers that do not upgrade, and at some 
point the signers are going to drop support for A, and that will 
create problems for verifiers who haven't upgraded.

If the transition is short, then I'll be concerned about it.  But if 
the transition is multiple years and the verifiers still haven't 
upgraded I'm not going to lose any sleep over it.  By the way, this 
is Assumption 2.

If a signer does go from SA to SB without passing through SAB (or not 
maintaining it long enough) then they will be hurting themselves, 
since (Assumption 5, from my previous mail to Charles, saying that 
verifiers actually implement the spec as written) their mail will be 
treated like any unsigned message --- which in the long run means 
"poorly".

>> ASSUMPTION 4: Keys for algorithms A and B are not compatible.
>> This   is ensured by the k= tag in the selector.
>>
> generally seen elsewhere.

No, the level of exposure does not very depending on target value, 
although the likelihood of an attack might.  I think that's what you 
are trying to say, but it's not what you did say.

>                            The signer may need to wait a long time
> before being able to drop a problematic algorithm.

Yes, that's expected, and not a bad thing.  See Assumption 2.

>                                                     Selectively
> using  a algorithm based upon the recipient would be fairly
> onerous.

For the general case yes, but not for special cases.

>           The  actual endpoint of the message is not really known,
> where verifier  compliance can not be easily determined.

I assume this sentence is intended to emphasize how hard it is.  Yes, 
for the general case it is hard --- very, very hard.

>                                                           Once a
> majority of users  are protected by adoption of a newer algorithm
> in conjunction with a  deprecation assertion, this will greatly
> reduce the opportunity for a  successful exploit.

You've said this many times without providing evidence.  That's not 
helpful.

> specific targets, for example.  This might have a significant
> payoff  when these messages are otherwise trustworthy.

I have no idea what you are trying to say.

>>  uses. However, since the DKIM-Signature header field is included
>> in   the signature and that field includes the canonicalization
> known weaknesses with respect to signature/header association.
> These  weaknesses may be an inability to ensure a verifier is not
> also  exposed to DDoS exploit without also foregoing DKIM
> protections.

Not relevant to this discussion.

> transactions.  If X is not available, then AH would be invalid.
> This  simple statement prevents a downgrade attack, which is
> especially  important when verifiers understand X.

It's not at all clear to me what "X" is.  Assuming it is the name of 
another algorithm (AJ, BH, or BJ) then your proposal doesn't work. 
An attacker isn't going to include a signature that says "by the way, 
I'm a bad algorithm", and the selector corresponding to A can't say 
that it should not be used because it can be used fine with J.

>> I've argued for why that's a good assumption.  In summary, this
>> why   I think we should just close 1386.
>>
>> Fire away.
>
> Rather than assuming nothing unexpected will be discovered in
> coming  years, plan for a graceful transition now.  This may
> greatly increase  the protection DKIM offers in the face of
> adversity.  This involves  rather simple definitions that can
> remained unused until a problem  becomes evident.

When did I assume that nothing unexpected will be discovered?  On the 
contrary.  If I believed that I would have argued against specifying 
the algorithms at all.  I *do* make Assumption 2 that there won't be 
a major breakthrough that makes an existing, believed-strong 
algorithm into something that is trivial to attack overnight, and I 
state that very clearly.  As I argued before, if Assumption 2 is 
wrong then the DKIM problem will be the least of our worries.  If 
SHA-1 turns out to have a trivial pre-imaging attack then the banking 
industry is toast.  If RSA turns out to be a P rather than an NP 
problem, then security as we know it on the net is gone.  Hence, in 
the context of DKIM, Assumption 2 is valid.

eric

---

From: Dave Crocker <[email-masked]>
Date: Wed, 28 Feb 2007 10:48:15 -0800

Eric Allman wrote:
> [By the way, there was also some confusion about whether transitions are 
> O(years) or O(days).  Changing selector records is O(days), whether or 
> not those selectors change algorithms, but changing algorithms requires 
> software updates and hence is O(years).]

Important distinction.  Thanks.

It's probably worth noting that a catastrophe with a deployed algorithm, so 
that a rapid transition is required, has no precedent in the large-scale, open 
Internet, and probably would take considerably more effort and mechanism than 
anything we are discussing here.

As such, building in anything designed a) to deal with highly problematic, 
systemic failures, and b) incurring overhead for most/much regular traffic in 
anticipation of that catastrophe is probably not such a good idea.

As we have seen in other such algorithm transitions for mechanisms in 
end-points -- rather than infrastructure -- they tend to have a distinctive 
characteristic:

      While it is O(years) to achieve very broad adoption, it can be O(months 
or even weeks) to gain a useful degree of adoption, within smaller communities 
of interchange.

In general, this means that slower algorithm transitions are acceptable and 
can be handled in the same way as we handle other transitions on the Internet. 
  None of them include a publication mechanism.

d/
-- 

   Dave Crocker
   Brandenburg InternetWorking
   bbiw.net

---

From: Douglas Otis <[email-masked]>
Date: Wed, 28 Feb 2007 11:34:49 -0800

On Feb 28, 2007, at 10:00 AM, Eric Allman wrote:

> --On February 26, 2007 4:23:47 PM -0800 Douglas Otis <dotis@mail- 
> abuse.org> wrote:
>>
> Yes, it may be a problematic area, but it is completely irrelevant  
> to this discussion.

Actually it is.

Axiom 1: Any element of a DKIM signature can be asserted as being  
superseded (deprecated).

Axiom 2: Only the signer can deprecate an algorithm.

Axiom 3: Only the verifier can obsolete an algorithm, but this is  
highly disruptive.

Axiom 4: Only by placing deprecation information in the key can  
additional transactions be avoided.

Axiom 5: Only by indicating the superseding algorithms can additional  
transactions be avoided.

Axiom 6: The verifier may not know which signers are being exploited.

> Yes, it does.  But that's also irrelevant to this discussion.

See axiom 1 and the end of this message.

>> However it might be possible to incorporate deprecation  
>> information into various third-party services to bolster possible  
>> server weaknesses.
>

A type of accreditation service could republish deprecation  
information as a means to avoid infrastructure related exploits.

>> However, during an N year transition, a verifier is still prone to  
>> a downgrade attack.  Such an attack might only be seen by high  
>> value targets.
>
> No, that's just wrong.  That's the point of my posting.  If you  
> have something valuable to say about my logic (I accept that it  
> could be wrong) then please point it out, but don't just keep  
> waving the "downgrade attack" flag.  And the point about high value  
> targets is irrelevant.  The spec is designed to work for everyone.

Your assumption assumes either a sharp or extremely slow  
vulnerability timeline profile.  A pronounced transition of  
vulnerability still does not justify providing only an "obsolete"  
mechanism.  While indeed the signer can simply stop using an  
algorithm, or a verifier can obsolete an algorithm, this still leads  
to Axiom 3.  Per Axiom 2, only the signer is able to provide a means  
to deprecate an algorithm and avoid the repercussions of Axiom 3.

> probably want to support both A and B for a fairly long period.   
> But there will always be some verifiers that do not upgrade, and at  
> some point the signers are going to drop support for A, and that  
> will create problems for verifiers who haven't upgraded.
>
> If the transition is short, then I'll be concerned about it.  But  
> if the transition is multiple years and the verifiers still haven't  

By not providing a means to deprecate an algorithm, the transition  
period will be extended.  The reason for it being extended would be  
that the signer must decide whether they wish to forego having their  
messages seen as signed, or endure some level of exploit that has  
induced the change.  While there are changes where obsolesce is not  
problematic, it is impossible to predict this vulnerability profile.   
The major concerns regarding DKIM appear to be those areas that for  
some reason have been excluded from this conversation!  See Axiom 1.

>> Once a majority of users  are protected by adoption of a newer  
>> algorithm in conjunction with a  deprecation assertion, this will  
>> greatly reduce the opportunity for a  successful exploit.
>

By providing a means to deprecate an algorithm (any algorithm  
associated with DKIM), then also offering a weaker option will no  
longer expose users where both the signer and verifier have  
upgraded.  The distribution of providers has a rather steep profile  
of user populations.  By having a hand full of major providers  
upgrade using a deprecation tactic, very rapidly a large percentage  
of the user population can be protected without disrupting email, or  
increasing the user's exposure by presenting to them valid messages  
that appear to be once again unsigned.

>> The level of expense needed to stage an attack may limit the  
>> number of sites exploited.  The exploit overhead might change some  

A distribution of difficult exploits will mean signers are best able  
to decide when an algorithm or mechanism should be deprecated.   
Waiting for an algorithm or mechanism to become obsolete may result  
in many more victims that would have been necessary had there been a  
deprecation mechanism.

> Not relevant to this discussion.

Axiom 1 suggests otherwise.

> It's not at all clear to me what "X" is.  Assuming it is the name  
> of another algorithm (AJ, BH, or BJ) then your proposal doesn't  
> work. An attacker isn't going to include a signature that says "by  
> the way, I'm a bad algorithm", and the selector corresponding to A  
> can't say that it should not be used because it can be used fine  
> with J.

Imagine a new optional deprecation parameter defined for the key  
structure.  This parameter is as follows:

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

The presence of this parameter within a key means the associated key/ 
signature have been deprecated by the signer.  In addition, this also  
states that there will also be a companion signature containing the  
specified tags and parameters.  This allows _any_ algorithm to be  
deprecated.

> When did I assume that nothing unexpected will be discovered?  On  
> the contrary.  If I believed that I would have argued against  
> specifying the algorithms at all.  I *do* make Assumption 2 that  
> there won't be a major breakthrough that makes an existing,  
> believed-strong algorithm into something that is trivial to attack  
> overnight, and I state that very clearly.  As I argued before, if  
> Assumption 2 is wrong then the DKIM problem will be the least of  
> our worries.  If SHA-1 turns out to have a trivial pre-imaging  
> attack then the banking industry is toast.  If RSA turns out to be  
> a P rather than an NP problem, then security as we know it on the  
> net is gone.  Hence, in the context of DKIM, Assumption 2 is valid.

DKIM offers many unique mechanism where a problem could be uncovered  
and still not impact the rest of the Internet.  See Axiom 1.

-Doug