Subject: [ietf-dkim] Proposal for specifying syntax and semantics for multiple signatures

From: Paul Hoffman <[email-masked]>
Date: Thu, 30 Mar 2006 12:36:25 -0800

Greetings again. This follows up on the desire to allow multiple
signatures in the same message.

---------------------
Summary:
A sender signing a message that already has one or more DKIM-Signature
headers keeps the earlier headers, signs over them, and optionally says
whether or not they were verified before signing.

---------------------
Rationale:
Signers need a way to attach multiple signatures when transitioning from
one signature algorithm to another, when transitioning from one hash
algorithm to another, and even from one protocol version to another.
Further, there are many scenarios where a sender is forwarding a message
that is already signed,  and wants to add its own signature. This must
be done in a way to prevent bid-down attacks during transitions, and
also must be done in a way so the recipient can unambiguously determine
the order in which the signatures appeared.

---------------------
Changes:

Add to section 3.5:

	p= Earlier signatures (plain-text; REQUIRED if there is already one
	or more DKIM-Signature header in the message). This tag lists the
	hashes of the DKIM-Signature headers that exist before this
	DKIM-Signature header is added, possibly adding the result of a
	verification of done by the party creating the current
	DKIM-Signature header. The hash is computed using the hash algorithm
	that is used in the signing algorithm (taken from the "a=" tag),
	using "simple" header canonicalization on the DKIM-Signature header.
	The signer MAY include an indication of whether or not a particular
	DKIM-Signature header was verified; the absence of this indication
	is interpreted by the recipient that the verification was not
	performed. The order of the hashes MUST be from the last
	DKIM-Signature header in the message to the first.

	sig-p-tag = %x70 [FWS] "=" [FWS] sig-p-tag-body
	                   0*( *FWS ":" *FWS sig-p-tag-body)

	sig-p-tag-body = sig-p-tag-hash [ "," sig-p-tag-result ]

	sig-p-tag-hash = base64string

	sig-p-tag-result = "verified-ok" / "verified-failed"
	                     / "not-verified" / x-sig-p-tag-result

Change in the "h=" description of section 3.5:
OLD:
	The field MUST NOT include the DKIM-Signature header field that is
	being created or verified.
NEW:
	The field MUST NOT include any DKIM-Signature header field.

Change section 4 to read:

	4.  Semantics of Multiple Signatures

	A signer that is adding a signature to a message inherently signs
	all DKIM-Signature headers that exist in the message before the new
	signature using the "p=" tag. If a single signer adds multiple
	signatures, such as using different signing or hashing algorithms,
	each signature stands on its own, meaning each signature covers all
	of the previous signatures, even ones from the same signer.

	A receiver can always determine the order in which the signatures
	were applied based on the "p=" tag. If the tag is absent, that
	signature is the first signature on the message. If the tag is
	present, the number of hashes in the value indicate how many
	signatures were present before this signature was applied.

	A signer applying multiple signatures with different signing
	algorithms SHOULD first sign with its most-preferred algorithm, then
	with the next-most-preferred, and so on. This ordering prevents an
	attacker from removing more-preferred signatures from a message
	without the recipient being able to detect the removal.

	Signers MUST NOT remove any DKIM-Signature headers from messages
	they are signing, even if they know that the headers cannot be
	verified. Doing so would break the chain of signatures.
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Jim Fenton <[email-masked]>
Date: Thu, 30 Mar 2006 16:54:32 -0800

Some comments below.

> signatures in the same message.
I believe that some signer and verifier APIs have trouble handling
"simple" canonicalization because they don't present the whole header
field.  It may be problematic to mandate "simple" here; why not use the
same header canonicalization specified for the signature?
>                          / "not-verified" / x-sig-p-tag-result
I'm concerned that including verification results is going to introduce
a whole bunch of new semantics (and possibly transitive trust) to the
multiple-signature case.  If a later signer says they didn't verify the
previous signature, or that verification failed, are they taking
responsibility for the message or not?  If they are in either case, how
is their verification result relevant to the recipient's verifier?
>     verified. Doing so would break the chain of signatures.
Aside from wording nits ("header" -> "header field") I don't see
anything else wrong with this proposal, other than its complexity.  As
far as the bid-down attacks are concerned, I think this is an
overreaction; signers wouldn't have a good reason to use any algorithm
that's that thoroughly broken.  I'm also concerned about the prospect of
DKIM verification yielding other than a binary result, if valid
signatures cite others that they say they couldn't verify.

-Jim

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 30 Mar 2006 17:26:56 -0800

Interesting issues; see below.

At 4:54 PM -0800 3/30/06, Jim Fenton wrote:
>  >     The hash is computed using the hash algorithm

I'm open to that change; I thought "simple" was the easiest, but 
maybe not. How do others feel about this?

>multiple-signature case.

It only introduces semantics if the receiver wants it to. There is 
nothing in the spec that says whether or not a receiver would want to 
trust these results. However, not including them, and believing that 
some signers might break signatures by munging headers or the body, 
prevents the receiver from having any idea where a message might have 
changed. That's OK, but I thought I heard folks wanting to pass the 
information forward in the signing chain.

>If a later signer says they didn't verify the
>responsibility for the message or not?

Of course they are. They are taking responsibility for the message 
that they passed. There is nothing in the above semantics that says 
anything about responsibility.

>If they are in either case, how

I'm not sure, but I thought that others wanted this. If no one wants 
it, it is easy to remove.

>anything else wrong with this proposal, other than its complexity.

Aw, c'mon. One set of options isn't complex! :-)

>As
>that's that thoroughly broken.

True, but we need a way to allow signers to use more than one type of 
signature until they are reasonably sure that all recipients are able 
to verify with the "better" algorithm. This is the crux of the 
Rescorla-Bellovin paper. We are sanguine on bid-down attacks because 
we don't have any real-world cases yet for them; that could change in 
the future.

>I'm also concerned about the prospect of

The verification is still binary, but I see your concern about the 
interpretation being fuzzy.
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Mark Delany <[email-masked]>
Date: Fri, 31 Mar 2006 03:47:46 +0000

> maybe not. How do others feel about this?

I agree that 'simple' is the easiest - in the original DomainKeys
drafts there was a sample perl implementation that took 4 or 5 lines
of code. Unfortunately because sendmail milter has a bug (that SMI
have promised to fix) some of those who are bound by milter
implementations want to bias the specification to match up with the
limitation of milter.

I expect that most of us have moved well beyond that sort of
mono-culture mentality, and I know the SMI folk are *not* the ones
pushing for this constraint, but nonetheless, it seems to live on in
pockets.

Mark.

---

From: Michael Thomas <[email-masked]>
Date: Fri, 31 Mar 2006 07:11:54 -0800

> signatures in the same message.

As a point of order, multiple signatures in the same message work just
fine today. It should be noted that this is a proposal for enhancing
multiple signatures.

> This must
> be done in a way to prevent bid-down attacks during transitions, 

I believe that Mark also has a proposal on the table for how to deal
with bid-down attackes.

> and

The downside of this are MTA's that reorder headers, which they do
unless they know it's a trace header. Which they don't for DKIM
since it's new.

I really don't understand the benefit of this proposal. We can already
sign DKIM-Signature headers today with h=. Why do we need a different
way, not to mention a REQUIRED different way? If the main motivation is
to be able to transmit "verified" or "unverifed", we have a really big
disconnect. See below.

>                          / "not-verified" / x-sig-p-tag-result

I'm afraid that this is really naive. The verification process
produces *many* more states than two, and we are not chartered
to deal with them cf the auth-res draft. That and I really dislike
the implicit nod to transitive trust from potential adversaries.
Mail is an open sewer, and need to be mindful of creating more
harm than we fix.

Let's not take this on until we're really ready to, ie when we
recharter and take on Murray's Auth-Res draft.

>     signatures were present before this signature was applied.

So a good way to disable a signer is to add the 822 header buffer
overflow number of DKIM-Signatures, right?

>     without the recipient being able to detect the removal.

This has a big problem as far as I can see: how does the receiver
know what constitutes a "signer"? There is no such role that can
be determined on the wire right now. Differentiating off of d=
is not sufficient -- you may have multiple signers in a single
domain, etc.

		Mike

---

From: Barry Leiba <[email-masked]>
Date: Fri, 31 Mar 2006 10:42:23 -0500

> I believe that Mark also has a proposal on the table for how to deal

And actually, as I recall the discussion in Dallas it seems that even 
Russ and EKR were not worried about this issue.  The idea was that it's 
down to the verifier to determine which algorithms it's willing to 
accept, and the removal of a "stronger" signature only matters if the 
verifier isn't willing to accept the remaining, "weaker" one.  I have no 
opinion on this; I'm just bringing it up to the mailing list from the 
session in Dallas.

> unless they know it's a trace header. Which they don't for DKIM

Someone else had suggested adding some sort of signature sequence field, 
which, if we did that, could robustly identify the order, and could make 
is clear which are missing.  Something like this:

   DKIM-Signature: seq=3,1,1; ...
   DKIM-Signature: seq=2,2,2; ...
   DKIM-Signature: seq=2,1,2; ...
   DKIM-Signature: seq=1,1,1; ...

...where the numbers represent signer sequence, signature sequence for 
this signer, number of signatures that this signer added.  Mike is right 
that we can already sign all the existing sigs when we add a new one, so 
it's really only the ordering that we have to worry about.

Barry

--
Barry Leiba, Pervasive Computing Technology  ([email-masked])
http://www.research.ibm.com/people/l/leiba
http://www.research.ibm.com/spam
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Michael Thomas <[email-masked]>
Date: Fri, 31 Mar 2006 08:28:22 -0800

> opinion on this; I'm just bringing it up to the mailing list from the 

That might be ok too. I get the impression that DKIM is in the
crossfire of a larger discussion where these issues make a lot
more difference. I'm all for keeping some perspective.

> it's really only the ordering that we have to worry about.

Somebody needs to help me out here. What problem is getting solved with
this geneology exercise? I've been at this a while, and I've never had
a moment where I thought "it would really be nice to know which begat
what".

		Mike

---

From: Barry Leiba <[email-masked]>
Date: Fri, 31 Mar 2006 13:20:55 -0500

>> Someone else had suggested adding some sort of signature sequence 
>> field, which, if we did that, could robustly identify the order, and 
>> could make is clear which are missing.  Something like this:
>>
>> this signer, number of signatures that this signer added.  Mike is 
>> right that we can already sign all the existing sigs when we add a new 
>> one, so it's really only the ordering that we have to worry about.
> 

Well, the issue is that if, say with the above example, signer #3 signs 
the other three signature headers, and then the next hop re-orders them, 
the verifier can still figure out which records signed which others.

Barry

---

From: Dave Crocker <[email-masked]>
Date: Fri, 31 Mar 2006 10:31:48 -0800

> the verifier can still figure out which records signed which others.

So what?

There are many "interesting" things that we might build into a protocol.

The question is what compelling need is served by the feature?

Each feature makes the protocol more complex and therefore raises the adoption 
barrier.

So we should feel obligated to explain why a feature offers long-term, strategic 
benefits.

d/
-- 

Dave Crocker
Brandenburg InternetWorking
<http://bbiw.net>
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Barry Leiba <[email-masked]>
Date: Fri, 31 Mar 2006 13:58:30 -0500

>> Well, the issue is that if, say with the above example, signer #3 
>> signs the other three signature headers, and then the next hop 
>> re-orders them, the verifier can still figure out which records signed 
>> which others.
> 
> So what?

So the signature can survive the reordering; it's essentially a helper 
for canonicalization.

I'm not suggesting it's critical, only that it was suggested, that we 
had no further discussion on it, and that it's an alternative to Paul's 
proposal and should be discussed together with it.

Barry

---

From: Michael Thomas <[email-masked]>
Date: Fri, 31 Mar 2006 11:13:13 -0800

Barry Leiba wrote:

>>> re-orders them, the verifier can still figure out which records 
>>> signed which others.
>>
>>
>> So what?
>
>
> had no further discussion on it, and that it's an alternative to 
> Paul's proposal and should be discussed together with it.

Signatures can already survive reordering right now by not signing
the DKIM-Signature.

My question was much more basic: what useful thing would a receiver do
differently if it knew the order in which signatures were applied? I really
can't think of anything.

       Mike

---

From: Douglas Otis <[email-masked]>
Date: Fri, 31 Mar 2006 11:15:40 -0800

On Mar 31, 2006, at 10:31 AM, Dave Crocker wrote:

>> signs the other three signature headers, and then the next hop re- 
>> orders them, the verifier can still figure out which records  
>> signed which others.
>
> So what?
>

The goal is to ensure when there are two signatures added to the  
message, an attacker does not toss out the stronger signature in  
order to exploit the weaker signature added within a transition period.

There could be a flag that marks the signature as primary or  
secondary.  Only seeing a secondary signature from the same domain  
should cause the message to be refused.

The concept of signature roles at the meeting was to do this and also  
allow the MDA to add a signature to protect results information and  
ensure this signature was not mistaken as being from a sender.  The  
same flag that marks primary/secondary signatures could also  
differentiate signatures added by senders or by the MDA.

This approach would be far simpler, as in most cases it would be a  
static bit of information, such as "w=S" (primary) or  
"w=s" (secondary) or "w=d" (mda).

-Doug

---

From: Douglas Otis <[email-masked]>
Date: Fri, 31 Mar 2006 12:02:30 -0800

> "w=s" (secondary) or "w=d" (mda).

Small mistake.  If Upper case is used to denote primary, then for  
consistency, the example should have been:

"w=S" (primary) or "w=s" (secondary) or "w=D" (mda)

The need for noting a signature added by the MDA is not the same as  
that of sender would be important when the sender and the MDA share  
the same domain.  Perhaps the MDA signature encompasses a results  
header added by the MDA at the edge of the recipient AdmD or AU.   
This different role is needed to prevent an added signature from  
allowing an exploit.

-Doug

---

From: Tony Hansen <[email-masked]>
Date: Fri, 31 Mar 2006 16:06:17 -0500

Paul Hoffman wrote:
> I'm open to that change; I thought "simple" was the easiest, but maybe
> not. How do others feel about this?

My experience doing interop testing says to stay away from simple as
much as possible. It doesn't interop well.

	Tony Hansen
	[email-masked]

---

From: Tony Hansen <[email-masked]>
Date: Fri, 31 Mar 2006 16:08:31 -0500

> pushing for this constraint, but nonetheless, it seems to live on in

Sendmail milter is not the only interface with this problem. There is at
least one other that has the same problems as milter; I think it was
qmail but would have to look it up for certain.

	Tony Hansen
	[email-masked]

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 31 Mar 2006 13:21:13 -0800

Barry Leiba <[email-masked]> writes:

> Russ and EKR were not worried about this issue.  The idea was that
> it's down to the verifier to determine which algorithms it's willing
> to accept, and the removal of a "stronger" signature only matters if
> the verifier isn't willing to accept the remaining, "weaker" one.  I
> have no opinion on this; I'm just bringing it up to the mailing list
> from the session in Dallas.

I think that's a fairly accurate statement of my position, yes.

> one, so it's really only the ordering that we have to worry about.

Note that how effective this is depends on the attacks you are
concerned about on your hash function. If, for instance, there
is a preimage attack, then this doesn't help. I don't have
a useful opinion on how likely a preimage attack is.

-Ekr

---

From: Arvel Hathcock <[email-masked]>
Date: Fri, 31 Mar 2006 16:16:38 -0600

> differently if it knew the order in which signatures were applied? I
 > really can't think of anything.

I can't think of anything either.  I don't think we should add this 
additional complexity.

-- 
Arvel

---

From: Arvel Hathcock <[email-masked]>
Date: Fri, 31 Mar 2006 16:18:41 -0600

> message, an attacker does not toss out the stronger signature in order
 > to exploit the weaker signature added within a transition period.

I think that we should leave this to the verifier.  If the verifier is 
uncomfortable accepting a "weaker" signature then by all means let the 
verifier stop doing so.  Is there a problem with that approach that I 
can't see?

-- 
Arvel

---

From: [email-masked]
Date: Fri, 31 Mar 2006 14:25:49 -0800 (PST)

> qmail but would have to look it up for certain.

And let's please not forget that even if this got fixed tomorrow the amount of
time it takes to significantly deploy new MTA versions is very long - far
longer than we can afford to wait.

				Ned

---

From: Michael Thomas <[email-masked]>
Date: Fri, 31 Mar 2006 14:42:13 -0800

>>>pushing for this constraint, but nonetheless, it seems to live on in

I personally am not in favor of using that as show stopper even though I'm
impacted, but since we want to get things deployed as quickly as possible
a proposal that breaks milter's assumptions should certainly viewed in the
light that it will make adoption that much harder.

>longer than we can afford to wait.
On this front, sendmail 8.12 doesn't give milters a good way to control 
where a
header is added either, so making any sort of position-dependent 
assumptions of
DKIM-signatures is on pretty shaky grounds, which I think this proposal 
assumes.

       Mike

---

From: Mark Delany <[email-masked]>
Date: Fri, 31 Mar 2006 23:15:57 +0000

> longer than we can afford to wait.

I'm confused. We expect wide-spread use of this protocol without
deploying new MTAs? That's quite the feat.

Mark.

---

From: Michael Thomas <[email-masked]>
Date: Fri, 31 Mar 2006 15:32:59 -0800

>deploying new MTAs? That's quite the feat.
With milter, you don't have to upgrade your sendmail version. For us,
we'd probably have to go through a lot more contortions to get our
infosec folks to buy into a new sendmail version for our production
environment. Not undoable, but definitely harder.

My understanding is that other MTA's have similar plugin kinds of
capabilities too.

       Mike

---

From: Douglas Otis <[email-masked]>
Date: Fri, 31 Mar 2006 15:34:38 -0800

On Mar 31, 2006, at 2:18 PM, Arvel Hathcock wrote:

> I think that we should leave this to the verifier.  If the verifier  
> is uncomfortable accepting a "weaker" signature then by all means  
> let the verifier stop doing so.  Is there a problem with that  
> approach that I can't see?

The sender may wish to minimize the number of messages lost or  
refused due older non-compliant verifiers, and therefore includes two  
signatures within the message.  One signature is stronger, repairing  
a weakness found when using the prior convention.  To ensure a down  
grade attack does not occur when the verifier _can_ handle the  
stronger convention, primary/secondary role options would be used.   
(Note this is an option that can be used at a later time and simply  
default to a primary role, but one that should be understood by the  
verifiers.)  The simple rule used by the verifier would be to refuse  
messages that only offer a signature marked as playing a secondary  
role.  This can be done only at the key, but should also be done at  
the signature to minimize DNS transactions and to allow the sender to  
decide what is the preferred convention.  The restrictions with  
respect to what is acceptable would also be provided in the algorithm/ 
role of the referenced key.  This is extremely simple, but solid.   
Primary and secondary signatures do not impact current verifiers.   
Older verifiers (Allman 01) will ignore the role option seen in the  
signature and key.

Simple, but effective and a very small change when following the w=  
Ss Mm and Dd roles, as shown in slides. : )

-Doug