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

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 26 Feb 2007 06:59:33 -0800

In the scenario described A would be the legacy (depricated) algorithm, B the new one.

The reason we don't just kill off algorithm A in this case is that cryptographic algorithms are very rarely broken to the point where they become totally useless.

DES is still being used for encryption and the chances that someone will bother to break the encryption are very very small.

So we don't do a 'flag day' and insist that everyone has to upgrade their systems. That is not acceptable in the IETF. We have to have a transition period.

The problem is that UNLESS you have the ability to tell people that your signing practices are transitional the policy language will be insufficiently expressive to provide any value.

Nobody will upgrade to algorithm B because the minute they advertise the B record their policy becomes worthless unless every verifier has upgraded first.

It's a classic double ended adoption trap with the extreme constraint that no signer can move until every verifier has moved.

> -----Original Message-----
> From: Michael Thomas [mailto:[email-masked]] 
> Sent: Sunday, February 25, 2007 1:46 PM
> To: Hallam-Baker, Phillip
> Cc: IETF DKIM WG
> Subject: Re: [ietf-dkim] Deployment Scenario 7: Cryptographic 
> Upgrade and Downgrade Attacks
> 
> Hallam-Baker, Phillip wrote:
> > 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'.
> >   
> 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
> 
> >
> > 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
> >   
> 
> 

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

---

From: Michael Thomas <[email-masked]>
Date: Mon, 26 Feb 2007 07:19:20 -0800

I'm still not seeing what the problem is with things as they stand now.
We've already been through a transition with sha1 and sha256. The
solution was to make both signatures in the transition and set the
h=sha1|sha256; in the selector. All you do when you're ready to
completely transition is only sign with the new algorithm and set
h=sha256; in the selector. This is exactly the kind of case we wanted
to get right for -base and as far as I can tell it worked exactly as
intended.

I'm honestly not trying to be obtuse here.

		Mike

---

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

> I'm still not seeing what the problem is with things as they stand  

The DKIM WG would not have not provided a reasonable solution if  
there were known easily exploitable weaknesses.  Avoiding a downgrade  
attack considers what might be needed to accommodate a transition in  
algorithms.  Currently, there are no reasonable mechanism for doing so.

> h=sha1|sha256; in the selector.

Those changes are possible during the initial definition of an  
algorithm.  Once widely deployed and heavily depended upon, such  
changes without a transition scheme would be impossible to achieve.

> All you do when you're ready to completely transition is only sign  
> with the new algorithm and set h=sha256; in the selector.

There are many algorithms involved with DKIM.  Canonicalization,  
hash, crypto, header strategies, signature associations and more must  
be considered representing possible weaknesses which might require  
some future change.   Few can predict what might become problematic.

> This is exactly the kind of case we wanted to get right for -base  
> and as far as I can tell it worked exactly as intended.

No one is claiming that base is broken from a security standpoint,  
but it might be in the future.  When defining signer policy, a  
critical aspect relates to what is being used, and what has been  
deprecated.  The concept of deprecated _is_ broken in the base draft.

-Doug

---

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

> The problem is that UNLESS you have the ability to tell people that
 > your signing practices are transitional the policy language will be
 > insufficiently expressive to provide any value.

Seems to me signers will just sign with both algorithms for a period of 
time.  Regardless of what is expressed in policy, that can't help the 
sender know the level of deployment of a new verifier capable of 
handling the new algorithm.

Arvel

---

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

Mike, this is what I was trying to say in a previous post.  You are 
exactly right.  We have already faced this situation and it has proven 
itself in the field to work just fine.

Arvel