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

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 23 Feb 2007 11:54:34 -0800

> From: Paul Hoffman [mailto:[email-masked]] 

> This would be better worded as: In order to twart the attack, 
> the policy language must be sufficiently expressive to allow 
> the sender to describe their actual signature policy, such as 
> 'I sign only with algorithm A' or 'I sign with both algorithm 
> A and algorithm B'.

s/twart/thwart/ otherwise good.

> >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.
> 
> This is unnecessary here; there are other ways for a sender 
> to group their keys. We are only talking about the policy 
> statements in this document.

I was not so much proposing language for the draft as wanting to provide some additional explanation, it should probably have been in the notes. The point I am trying to make here is that I can achieve the effect of saying  'I sign with both algorithm A and algorithm B' without having to define any means of describing this in the SSP document. We can achieve the necessary effect through an interaction between SSP and DKIM-BASE.

> >What this means is that as soon as the legitimate sender 
> advertises the 
> >record for algorithm B their policy record becomes vulnerable to 
> >attack.
> 
> No. The policy record is not vulnerable: the messages are.

OK their policy record becomes useless as a discriminator against 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.
> 
> Predicting what a sender will or will not do when faced with 
> multiple signing algorithms is silly and does not belong in 
> this document.

I don't see that. I think it is pretty clear that a sender is not likely to take a decision to deploy algorithm B as an early adopter if doing so is going to degrade security in the short term

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

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 26 Feb 2007 07:56:50 -0800

We went through that transition at a time when nobody was concerned about use of policy.

If you have policy and rely on it you are not likely to give up policy for the sake of a transition from SHA256 to the new NIST standard or from current C18N to some new algorithm we might define. 

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