Subject: Re: [ietf-dkim] Interesting Dupe Signatures

From: Barry Leiba <[email-masked]>
Date: Sun, 1 Nov 2009 11:34:05 -0400

> But I have to consider customer sites patterns with heavy facebook
> users seeing tons of fb notifications and see if a simple check can
> add to the optimization.

Mike has a point, but I agree that this would be a problem for large
ISPs, where adding 10% more overhead for all Facebook messages would
be something they'd want to avoid.  But...

Why is computing the hash a problem?  Surely, you'd only compute the
hash once, regardless of how many signatures (dups or not) the message
has.  Why ever compute it more than once?  And then if the hash
doesn't match, you toss the sig without further processing.  If the
hash does match, then you validate the sig.

Then the only optimization that seems to matter is that there's no
value in verifying more than one sig for the same i=... so you see
that you already have a valid sig for i=@facebookmail.com, and you
skip the duplicates that way.

Now the only time there's more overhead is if the hash DOES match, but
the signature still fails to validate.  That ought never to be true
for real Facebook mail.  (Of course, attackers could put in fake sigs
with valid hash values, as a form of DoS.  But we've discussed that
before.)

Shouldn't that work for everything, and be very easy?

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

---

From: hector <[email-masked]>
Date: Sun, 01 Nov 2009 12:30:03 -0500

Barry Leiba wrote:

> has.  

Good point, the body hash is calculated once for the message. No 
overhead there.

> the signature still fails to validate.  

Right, in general, that is what came to mind. bh= and b= would have to 
be the same.

 > That ought never to be true for real Facebook mail.

Right, that would be the expectation because the domain is recognized, 
well known and 1st party only.  There is a sense of (unverified) 
"higher" trust (or lesser suspicion) with 1st party signatures from 
well known domains.

But you do realize FB has a *major* social network virus/hacking 
problem?   Once a user is infected, all their friends get comments on 
their pages and/or emails with "click this" phishing attacks:

     "look at what they are saying about" click this
     "Oh, this is funny!"  click this
     "OMG! WTF!" Click this.
     "Oh, so cute!" click this

etc. The last one I got yesterday from my cousin

    XXXXX sent you a message.

    Subject: hi

    "! C00l Vide0 !
    http://www.facebook.com/xxxxxxxxxxxxxxxxxxxxx/"

That prompted me to call him to tell him about this and he said
"I know, everyone is bitching at me."  So I advise him to delete his 
yahoo account used for facebook and get another one from yahoo, 
hotmail or whatever. I had all the power to give him one of ours but I 
avoided bringing up that suggestion. :)

I joined FB for a July family reunion thing and wow, nearly once a 
week a lay person gets hit and had to delete their account because all 
their friends (or maybe hijacked address book on pc) were getting 
slammed with these social network email, feed or wall comments with 
attack propagations.

Back in the day, many people blocked other well known domains when 
their easily exploited domains and abusive nature became a major 
burden for users and their hosting systems. That included, msn.com, 
yahoo.com, juno.com, hotmail.com, compuserv.com, aol.com and all the 
other early well known domains, etc.  So just like they were 
eventually scrutinized more than others, obviously FB is not going to 
get a free pass.

All I am saying here is I prefer to first design the software that 
treats all the domains the same.  It is a powerful idea to know that 
FacebookMail.com is signing with 1st party valid signatures. That is a 
great first step.  But that also comes a danger of given users a false 
impression that "everything is ok" because it was signed by: 
Facebookmail.com and probably even worst if coupled with a Certified 
Reputation Service vendor lookup to stamp it with a Gold Certification 
Star.

(This is why I think what Facebook should be more worry about is 
making sure failures are kicked out. The best way right now to do that 
is ADSP.  Can't do much about the good stuff, even when stamped with a 
gold star)

> (Of course, attackers could put in fake sigs

At this point Barry, it was more an observation while working on a 
DKIM log stats analyzer finding subtle patterns and considering 
whether its worth further analysis.  Optimization is always on my mind 
that might be useful for coding and operations.

The software is in auto-pilot.  The original version followed concepts 
in the drafts and as well concepts talked about here (or in the 
original list), especially when Eric was move involved regarding 
multiple signatures and how to best handle them with specific concerns 
on mixed results.  The most common issue was:

        Why should 1 valid signature trump all other
        signature failures?

Hence the ideas of resigners who modify content or specific hashed 
headers to strip older signatures.

I don't recall a consideration or mentioning when duplicates were 
found, and if I recall, it might have been before we added the body 
hash concept in an attempt to determine which part (head or body) 
broke the integrity.

In any case, with the software in auto-pilot, you are right, there is 
no redundancy in body hash calculation with multi-signature messages.

So what have I learned here?

1) Support Issue

    This was a FB bug and we can pass the buck and avoid the issue.
    However, vendors in the market can't always afford to pass
    the buck and need to deal with support issues. Smaller vendors
    are more nimble and can quickly do things to help customers
    faster (and directly) than larger ones. That level of support
    is why I am still in business.  I am presuming there is a FB
    employer lurker here and will have the problem fixed.  So I
    am not going to worry about this.

    Our goal is to minimize support cost. Not saying this was
    one that raises it, but its all part of the process of
    minimizing it.

2) New Dupe Checking rule for code:

    If the bh= and b= (which implies h=) are the same, then
    its a dupe, no need rehash b=.  This means new software
    coding to check for signature dupes to avoid code loops.

    However, its probably note worth the extra coding. Just
    it it rehash b= to find the same end result.

    I can see a useful warnings or note in the logs, "Duplicate
    Signatures."  People like to see such things.

3) New AVS Tracking rule:

    If as particular FB email notification is marked for having
    SNPA (Social Network Phishing Attack) then the bh= can be
    recorded for short circuiting future notifications.

    This is generally only efficient in short term periods as
    new similar attacks are slightly modified.

Not saying it will be done, but I try to look all things. :)

--

---

From: John Levine <[email-masked]>
Date: 1 Nov 2009 19:45:21 -0000

>> users seeing tons of fb notifications and see if a simple check can

Assuming you make the generally useful optimization to do the body
hash only once, it's hard to see a significant load from an extra
signature check.  

If it's the same signature, you'll already have the validation key in
the DNS cache, so it's just the cost of the header hash, which will be
small since headers are small, and the signature verification.

R's,
John

---

From: hector <[email-masked]>
Date: Sun, 01 Nov 2009 22:44:06 -0500

John Levine wrote:

> Assuming you make the generally useful optimization to do 

 > the body hash only once, it's hard to see a significant
 > load from an extra signature check.

+1.

But a body hash is calculated per signature because it might have a 
different c14n parsing.  So the ideal optimization would be to reduce 
the body hashing to unique c= c14n types. Given a ridiculous multiple 
signatures case:

   DKIM-Signature: .... c=relaxed/relaxed;   // dupe
   DKIM-Signature: .... c=relaxed/relaxed;   // dupe
   DKIM-Signature: .... c=relaxed/relaxed;   // dupe
   DKIM-Signature: .... c=simple/relaxed;    // other signer
   DKIM-Signature: .... c=relaxed/relaxed;   // other signer

A reduction consideration with body hash calculations per signature 
c14n type has some merit when mail size is a consideration.  In this 
case, a minimum of two calculations are necessary.

--
HLS

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Mon, 2 Nov 2009 10:05:55 -0800

> -----Original Message-----
> From: [email-masked] [mailto:ietf-dkim-
> [email-masked]] On Behalf Of hector
> Sent: Sunday, November 01, 2009 7:44 PM
> To: John Levine
> Cc: [email-masked]; [email-masked]
> Subject: Re: [ietf-dkim] Interesting Dupe Signatures
> 

You need two header and one body canonicalizations in that example.  And that presumes there's no "l=", which creates another dimension in the matrix of canonicalizations you need to run.

I've had a lot of success doing this sort of common factoring work in my implementation, though I sadly have no data about how much computation work it really saves.

---

From: "John R. Levine" <[email-masked]>
Date: 2 Nov 2009 13:15:20 -0500

> You need two header and one body canonicalizations in that example.  And that presumes there's no "l=", which creates another dimension in the matrix of canonicalizations you need to run.

I don't see much benefit for saving the header hash, since it depends on 
the order that the headers are listed in the h= header.

On the other hand, doing both the simple and relaxed body hashes in a pass 
over the body would handle about 99.999% of the signatures that anyone 
cares about.  I haven't seen many l= signatures, other than from Cisco, 
and I don't think I've seen any where the l= didn't cover the whole 
message.

R's,
John

---

From: Dave CROCKER <[email-masked]>
Date: Mon, 02 Nov 2009 10:33:18 -0800

Murray S. Kucherawy wrote:
> I've had a lot of success doing this sort of common factoring work in my
> implementation, though I sadly have no data about how much computation work
> it really saves.

My guess is that it took you a significant bit of effort to formulate that 
enhancement.

At that level, it /added/ computation work.  Yours.

d/

ps.  It's Monday.  I've having trouble focusing on anything serious.
-- 

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

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Mon, 2 Nov 2009 10:33:37 -0800

> From: John R. Levine [mailto:[email-masked]]
> Sent: Monday, November 02, 2009 10:15 AM
> To: Murray S. Kucherawy
> Cc: [email-masked]
> Subject: RE: [ietf-dkim] Interesting Dupe Signatures
> 

Right, but if the "h=" and the "c=" for the header are the same, you can reuse them.

> and I don't think I've seen any where the l= didn't cover the whole

That might also be a good optimization, especially if we can assume that SHA is cheap.

---

From: hector <[email-masked]>
Date: Mon, 02 Nov 2009 13:59:41 -0500

> You need two header and one body canonicalizations in that example.  And that presumes there's no "l=", which creates another dimension in the matrix of canonicalizations you need to run.

Right, c= c14n order post bug.  Flip it! :)

Off hand, the only reason I see to consider this is when the mail size 
is somewhat, frequently and/or commonly relatively huge.

Comparing public APIs, it appears DKIM-MFILTER is doing some reduction 
  logic, but hard to read spaghetti code. :)

ALT-N's C/C++ cleaner library does not appear optimize it.

---

From: Jim Fenton <[email-masked]>
Date: Mon, 02 Nov 2009 10:29:49 -0800

Barry Leiba wrote:

I'd go a little further than this:  If you already have a valid
signature from a given domain, why check any more signatures from that
domain?  It doesn't tell you any more than you already know.  It
doesn't matter if the signatures are identical or not.

-Jim

---

From: hector <[email-masked]>
Date: Mon, 02 Nov 2009 14:24:10 -0500

Jim Fenton wrote:

> I'd go a little further than this:  If you already have a valid signature from a 
> given domain, why check any more signatures from that domain?  It doesn't tell 
> you any more than you already know.  It doesn't matter if the signatures are 
> identical or not.

I pointed that out to Barry myself.  It was discuss long ago.

The question is this:

      Why is there is failure in the first place and why should
      single valid signature trump all failures?

Add to that, why should a 3rd party valid signature trump a broken 1st 
party signature?

Is that not the reason the recommendation for the remailer to strip 
and resign to avoid conflictive result analysis?

If DKIM is going to become the Broken Signature "Patch" framework, 
basically the last signing hop model, then the "chain of trust" is 
going to be presumed here.

How can that happen if remailers are exempt from checking if the first 
  signature was authorized in the first place before it breaks, 
strips, resigns, forwards the message?

Here is a scenario:

1st party signs message:

    Dkim-signature: x=X days

Non mail altering (simple list expander) 3rd party signs message:

    Dkim-signature: x=Greater than X days

Both are valid signatures, what expiration prevails here? What order?

If we use the 1st valid signature idea, then the 1st party prevails. 
But there might be logic that ask, is there another signature that 
extends the life of the message?

Same idea with reputation.

Both valid signature, one reputation feedback says "Account Suspended 
for reason XYZ."  The other says "This is a good guy."  I don't know. 
I don't know what reputation feedback models are being complicated in 
the back alleys.  But is that possible?

--

---

From: John Levine <[email-masked]>
Date: 2 Nov 2009 19:47:20 -0000

>cares about. ...

New improved answer: if you've taken my pipelining suggestion and
checked the DKIM signatures as soon as you see the end of the header,
you already know exactly what body hashes you need, so you can do
exactly those in one pass over the body.

R's,
John

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Mon, 2 Nov 2009 13:58:32 -0800

> From: HLS [mailto:[email-masked]] On Behalf Of hector
> Sent: Monday, November 02, 2009 11:00 AM
> To: Murray S. Kucherawy

Hector,

I happily welcome constructive criticism, but if it's all the same to you, I'd rather do without the cheap shots at open source work that has many hundreds of hours of time invested by volunteers.  If you can do better, you're cordially invited to contribute to the work.

And you might want to look up the definition of "spaghetti code" before using it foolishly in any more missives.  Wikipedia's entry is pretty accurate, for example.

---

From: hector <[email-masked]>
Date: Mon, 02 Nov 2009 18:31:03 -0500

> I happily welcome constructive criticism, but if it's all the same to you, I'd rather do without the cheap shots at open source work that has many hundreds of hours of time invested by volunteers.…

Murray,

I am sorry if you were offended. I am also sorry, and the chairs 
should take note, you took an off list discussion back to the list 
with what appears to be a vain attempt at another cheap shot. "If I 
can do better..."  don't you think that can be interpreted as 
offensive as you did with "spaghetti."

As I stated off list, even though it wasn't my intent to criticize and 
I even stated we have lots of "spaghetti" code developed over time, 
which doesn't always mean its bad but time test engineered, I 
understood that developers are sensitive to such things and that for I 
apologize.

Apparently, even though you thanked me for the apology,  that wasn't 
enough for you and wanted more!   You couldn't leave it there and not 
waste any more bandwidth here with this nonsense?

As for an interest in contributing to OPENDKIM, please talk to SM if 
did not cite interest in helping and also port the code to WIN32/64 
when he first announced it.  I thought an "open dkim" project was 
great to have a single single API for faster adoption.

Whether you agree or not, please respect my assessment.

After a quick review of the code, and I did begin to alter the headers 
imports for portability, I saw making it single source would require 
more time I was willing to provide at the time for this free effort. 
Maybe over the Christmas/New Years holidays I will look at it again.

Thanks

---
HLS