[ietf-dkim] Issue 1386 and downgrade attacks

[Eric Allman]

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).]