[ietf-dkim] Issue 1386 and downgrade attacks
2007-02-26 15:35:02
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
<Prev in Thread] |
Current Thread |
[Next in Thread>
|
- [ietf-dkim] Issue 1386 and downgrade attacks,
Eric Allman <=
|
|
|