Hi Mark,
Mark Delany wrote:
(This is an idea that germinated from discussions at the DKIM summit
in Santa Clara yesterday, and I'd like to bring it on-list. It's not
my idea, but I think it's a good one).
Hopefully it's obvious to all that the algorithms we pick today for
signature and hash calcs will not survive the lifetime of DKIM. Many
will have seen sha256 popping up as a potential replacement for sha1.
It's been said before that the most obvious solution to supporting
algorithm upgrades consists of three parts:
o a signer MUST sign with the strongest algorithm and MAY
additionally sign with a weaker algorithm. In short, multiple
signature headers.
o a verifier MUST select the strongest signature they recognize and
verify with that. All lessor signatures are ignored.
o A future spec that defines new algorithms MUST define relative
strengths. Eg, sha256 is stronger than sha1. If relative strength
is not clear, then why introduce a new alg?
While that provides a transition mechanism and a backward
compatibility mechanism, it is vulnerable to downgrade attacks.
For example, say a vulnerability is found in sha1 and a future spec
defines sha256 as the stronger hash alg. A dutiful signer will
generate a sha256-based signature and an sha1-based signature.
The downgrade attack is to remove the stronger sha256-based signature
and apply the attack to the weaker sha1-based signature.
The problem for the unwitting verifier is that they don't know the
signer originally added a stronger signature. All they see is the
weaker sha1 signature.
The simple solution is to provide an indication to the verifier that
the signer generates a stronger signature. That indication could
possibly go in one of three places:
o SSP, but that's not normally consulted on a successful verify.
o The signature header, but all message content is vulnerable to the
downgrade attack so the indicator cannot be trusted.
o The Selector of all the signatures excepting the strongest.
The latter seems the best choice and is the crux of the idea.
Picking some random tag, say, U= which indicates that this is a
downgrade Selector. The rules become:
o a signer MUST sign with the strongest algorithm and if they also
add signatures with weaker algorithms, the Selectors for those
weaker algorithms must have a U= tag.
o a verifier MUST select the strongest signature they recognize and
verify with that.
Assuming verification success:
o If the Selector of the strongest recognizable signature has no U=
tag, then accept the verification.
o If the Selector of the strongest recognizable signature has a U=
tag *AND* the verifier is capable of recognizing stronger, then
reject the verification as a potential downgrade attack.
o If the Selector of the strongest recognizable signature has a U=
tag *AND* this is the strongest signature recognized by the
verifier, suggest to your owner that you upgrade and cautiously
accept the verification.
With just one algorithm upgrade that logic works just fine. However,
with two or more upgrades, we need to introduce further logic; here's
why.
In a future world, what if DKIM has evolved to support three hash
algs: rsa1, rsa256 and rsa1024? Let's say the verifier recognizes rsa1
and rsa256. The signer OTOH is more modern and additionally knows
about rsa1024.
If the signer were to sign with rsa1024 and rsa1, then the verifier
will think such an email is a downgrade attack as it will recognize
the rsa1-based sig and detect a U= tag. However it will not recognize
the stronger sha1024-based sig and thus conclude a possible downgrade
attack.
The gap created by the signer is the problem here so the rule needs to
be that a signer must sign from strongest to weakest, WITH NO GAPS.
A signer need not use every algorithm, it simply cannot create gaps, so
Asha1024 and sha256 is fine as is a sole sha1024. While sha256 and
sha1 do meet the "no gaps" requirement, they do not meet the "use the
strongest you know" requirement.
Just a few additional considerations:-
- SHA-1 is now considered to be 2^63 "strong" & that'll only get worse.
The IESG will get more and more strict about allowing even SHA-1 to
be used, esp. where they don't see a backwards compatibility problem.
In those cases, I expect they'll want to see SHA-256 used. An issue
for DKIM is whether to include SHA-1 for anything at all, or for
more than compatibility with pre-standards versions.
- Algorithms don't necessarily have a fixed, known, order of "strength",
but are perhaps better considered to be "strong", "dodgy" or "broken".
at a given moment in time. There should be no reason to use a known
broken algorithm. Dodgy ones (like SHA-1 is now) should only be used
for backwards compatibility. There may be more than one "strong" at
any given time, e.g. sha-256, sha-512 or perhaps whirlpool, and
perhaps their use will break down not by strength, but say,
geographically, or by industry or whatever.
- If an algorithm is dodgy, then an attacker may be able to generate
collisions that remove or modify, any "U=" attribute, or equivalent,
depending on the details of the attack. With "standard" (i.e. pkcs#1)
signing, I don't think we can do much better really and I don't
think we want to get into modifying pkcs#1 here. Even so, it may be
worthwhile including a "U=" attribute, or something, to help
verifiers handle good signatures.
- If you sign anything with a really weak algorithm, and the attacker
can easily generate >1 collision, then the attacker can probably
create many many different signed messages, perhaps giving rise to
other threats.
- Lastly, DKIM needs to plan for sha-1 being retired (2010) and probably
for sha-256 being superseded by some new NIST-competition-winning
algorithm in the next 5+ years. So even if we start now with "only
sha-256", all of the above is still an issue down the road.
Stephen.
_______________________________________________
NOTE WELL: This list operates according to
http://dkim.org/ietf-list-rules.html