RE: CBV

> From: Mark Shewmaker
> Sent: Thursday, May 06, 2004 6:04 AM
>
>

Thanks for the feedback and ideas, Mark.  You've obviously put a lot of
thought into this.

> On Fri, 2004-04-30 at 11:24, Seth Goodman wrote:
> > Let me try to address both Tony's and Wayne's questions at the
> > same time.
> > Wayne's second point is a valid objection about mailing lists breaking
> > content checks.  This is a real problem today and it breaks any content
> > check, including S/MIME.
>
> I don't think these are valid objections.
>
> Mailing lists shouldn't be sending out emails to subscribers using the
> same MAIL FROM given by the original sender anyway, so even if they have
> edited the message contents before sending them to their subscribers,
> they'll have created a new MAIL FROM to go with that edited content.

Wayne's original objection was that mailing lists change the body of the
email by appending list subscription info, etc.  This will break any test of
message body integrity.  This had nothing to do with the MAIL FROM:.

However, mailing lists have to change the MAIL FROM: per RFC2821, so the
original SES-signed MAIL FROM: is discarded after any verification they do.
As you correctly pointed out, the mailing list would have to create a new
MAIL FROM: that included new hashes.  This actually does answer Wayne's
objection while still retaining the full body check.  Thanks for thinking of
this solution!  I should have realized this myself.

That takes care of mailing lists, but any forwarding system that appends or
prepends anything to the body would similarly break any check of the message
body.  The simple answer to that is, "don't do that", but changing any
existing practice is hard.  That was a lot of the motivation behind SES in
the first place, that is, not breaking any existing practice.  Fortunately,
there is an easy fix for forwarding systems that feel the need to prepend
lines like "Virus-checked by XYZ Company's Fabulous AV Product":  put that
very important information in an X-header, where it belongs.  I don't think
that we have to accept the practice of forwarding machines adding anything
to message bodies.  As long as it is a minority of systems, I think that
having their outgoing mail rejected will motivate them to find another
solution.


>
> As far as MS exchange and other MTA's munging the body of emails and
> thus causing checksums to become invalidated--well, I would consider it
> a feature that corrupted emails can be detected.

Strongly agree.  I believe these same MTA's can deliver S/MIME messages that
verify properly, so it appears that the are capable of delivering
uncorrupted message bodies.


<...>

> > Though something ultimately needs to be done about
> > this in general, let's assume that nothing changes and we have
> > to deal with
> > the status quo.  For the purpose at hand, which is preventing a
> > harvested
> > SES address from being used for spoofing, I will change my proposal and
> > suggest that we only need to protect the headers, not the body
> > content to
> > avoid Wayne's valid objection.
>
> Except for being prepared ahead of time for any future SMTP extension
> that allows body headers to be sent before the rest of DATA, I don't see
> any advantage in limiting the checksum to body headers.

Now that you've found a solution to the mailing list problem, I completely
agree with you.  We should return the inner hash to covering the message
body so as to more fully prevent replay attacks.


>
> More below.
>
> > In Wayne's exploit of SES, the spammer harvests signed addresses from
> > responses sent from general sales accounts or other loosely administered
> > accounts at large sites.  Since this method of exploit is now
> > known, you can
> > protect yourself against it by limiting the outgoing mail to a single
> > recipient and include a hash in the MAIL FROM: that protects the same
> > headers that S/MIME would protect.  Please correct me if I have
> > these wrong,
> > but I believe that these are To:, cc:, bcc:, From:, Sender: and
> > Date:.  With
> > a single recipient on the outgoing message and a hash that
> > protects these
> > headers, the signed return path would only be useful for the
> > spammer to spam
> > himself.
>
> I don't think I'd be the only one to object to solutions that disallow
> multiple recipients in the envelope headers.

This restriction was not intended for most email.  It was only intended for
accounts that are very promiscuous and send out responses to anyone who
asks, thereby exposing their signed return-paths to harvesting by malicious
parties.  Now that the inner hash can cover the message body, this
restriction isn't needed anymore.


>
> > Wayne's first point was that we couldn't really protect the
> > content with a
> > checksum.  I certainly agree with that and I proposed a SHA-1
> > hash rather
> > than a checksum to fix this.  If we are protecting only headers
> > and not the
> > message body, I think it becomes an intractable problem to synthesize a
> > group of headers that generates the same SHA-1 hash as the
> > original message
> > headers.
>
> I disagree with the implication that an attacker would effectively find
> it any easier to find a collision by adding/changing random characters
> in the full message body versus adding/changing random characters in a
> limited set of message body headers.
>
> Remember that for a good hash, when you change one bit of the data being
> hashed, there's a 50% chance that each bit in the hash output is
> flipped.
>
> You don't get any advantage when searching for a hash-collision in
> altered 10M files versus 10k files, if a hash collision is your only
> goal.  (In fact, it's probably slightly easier, given that the hash will
> have less data to have to, well, hash.)
>
> The attacker could simply limit the search to changing and testing bits
> in *any* of the headers that are looked at.  If you're truncating the
> hash to four characters then there's more than enough space in even
> these few headers in which one could find a collision.  (Most users
> wouldn't notice a CC: to "dfb89q3n028 <[email protected]>", just as they
> wouldn't notics an html comment of "dfb89q3n028bas98hjg" were it
> embedded in the message body instead.)
>
> BTW, I think four characters is not nearly enough..

I believe you're right here, but only for the header/body hash.  Computing
the outer hash that protects the MAIL FROM: requires knowing the hash
secret.  Unless you can crack that, you can't verify that a modified address
string will produce the correct outer hash value.  Therefore, the outer hash
length only has to be long enough to prevent cracking the hash secret.


>
> If the hash data is truncated to four characters, (as you suggest in
> another message I've quoted below) then you should expect a 50%
> likelyhood of finding a hash collision by going through every
> just-as-many-bits changes as bits in the truncated hash output.

OK.


> In this
> case that's 4 characters multiplied by 6 bits per character, or 24 bits,
> meaning 16 million tests--pretty easy to run through, and no matter if
> the data being hashed is limited to a few headers or consists of the
> entire body, you're still merely cpu bound.
>
> I'm typing this email on a 1.6GHz Athlon, where doing an sha1sum of
> /etc/inittab took me .002 seconds.  Making the simplifying assumption
> that I can do any sha1sum in .002 seconds means that in less than 9
> hours and twenty minutes I can test 64^4=2^24=16777216 combinations of
> data, for which I would expect a 50% likelyhood of coming across any
> specific truncated-to-4-base-64-characters hash I wanted to find.
>
> (In reality the time should be much less, as I wouldn't be actually
> loading and dynamically linking the same sha1sum program 64^4 times, but
> the point is that this is very doable.)
>
> In any event, four characters is not possibly enough.

For the inner (header/body) hash where the algorithm is defined ahead of
time and no hash secret is required, you are right and this is a real
vulnerability.  This makes it clear that the header/body hash in MAIL FROM:
needs to be longer, or we can use another trick that I propose below.


>
> Truncating less would obviously improve things, perhaps having the SES
> format allow for a variable number of characters for the
> verifiable-SES-hash section, and just including enough characters so
> that the cpu bound process is intractable at any given time.

This is a nifty idea and I really like it.  The only difficulty is that
getting everyone to gradually lengthen it over time will not be easy.


<...>

> 1.  Imagine an SES-enabled MTA sends out emails with the following
>     mail_from format, slightly different from the above:
>
>     SES0=H27=T4=L27=local-part@domain
>
>     Or:
>
>     SES0=   Unchanged.
>     H27=    A 27-character base-64 representation of all 160 sha1
>             bits of all of the following:  ("SES0", local secret,
>             T4, C27, local-part@domain).
>     T4=     A 4-character base-64 representation of a 32-bit time_t,
>             the number of seconds since the epoch.
>     L27=    A 27-character base-64 representation of all 160 sha1
>             bits of all of the following ("SES0", local secret, TT,
>             local-part@domain.)
>
>     For completeness:
>
>     B27=    A 27-character base-64 representation of all 160 sha1
>             bits of all of the following ("SES0", TT,
>             local-part@domain, message body.)
>
>             Note that C27 is not included in this mail_from, but
>             it is included in the computation of H27.

I assume that B27 above was a typo and you meant C27.

As I've argued above, the outer hash doesn't need to be 160-bits long.
Since the attacker would need the hash secret to check possible new return
paths, the outer hash only needs to be long enough to prevent cracking the
hash secret.  Shevek did look into this and suggested 24-bits as adequate.
Therefore, I suggest that we stay with a 24-bit outer hash.

Next let's consider the timestamp.  The timestamp has two possible
functions:  to date the signed return path so it can be expired and to act
as a salt for the outer hash.  For the purpose of expiring the timestamp,
all we really need is resolution in days.  Once we add an inner hash, there
is no longer a need to salt the outer hash calculation.  Therefore, I
suggest that we stay with two base-32 digits with one day resolution.

Making the inner hash longer is definitely one way to fix the vulnerability
that you found.  Assuming my arguments above hold water, what we're left
with is:


SES0=HHHH=C27=TT=local-part@domain

where

   HHHH = first four base-64 digits of the SHA-1
          hash of "C27=TT=local-part@domain"
          prepended with the hash secret
          (MSA login password) for
          local-part@domain

   C27  = 27 base-64 digits comprising the SHA-1
          hash of the concatenation of the From:,
          Sender:, Reply-To:, Date: and Subject:
          headers plus the message body in
          unencoded form

   TT   = first two base-32 digits of the UNIX
          integer day number mod 1024

The "SES0=HHHH=C27=TT=" overhead is 41 characters, leaving only 23
characters left for "local-part" before we exceed the 64-byte limit.  We
don't really need the full 160-bits to protect the message, so we can
shorten it somewhat to accommodate longer local parts.  How much we can
shorten it is unfortunately a moving target.

Given the above, I can suggest three possible courses of action.  There are
probably lots of others.

1) Use the full 160-bit inner (content) hash and live with the fact that any
local part longer than 23 characters will break the RFC2821 64-byte limit.
This will not occur often and it is not without precedent.  SRS can cause a
local part to exceed 64-characters and no one has gotten particularly upset
about that.  SRS does not have as much overhead as the above address format,
so the problem will occur less often but it will still occur.  This is the
simplest approach of the three.


2) Use Mark's nifty variable length inner hash idea as follows.  Reduce the
inner hash length as necessary in order to keep the total local part down to
64 bytes, but never reduce the inner hash length below 14 base-64 digits
(84-bits; arbitrary, suggest your own number).  The hash digits will always
represent a contiguous range of the 160-bit hash starting with the first
bit.  This will allow up to 36 characters in "local-part" before breaking
the 64-byte limit at the cost of less security.


3) Use a short inner hash that protects a full SHA-1 hash inside the message
headers.  Here is one possible format:

SES0=HHHH=hhhh=TT=local-part@domain

where

   HHHH = first four base-64 digits of the SHA-1
          hash of "hhhh=TT=local-part@domain"
          prepended with the hash secret
          (MSA login password) for
          local-part@domain

   hhhh = first four base-64 digits of the SHA-1
          hash of the X-Content-Hash: header line

   TT   = first two base-32 digits of the UNIX
          integer day number mod 1024

header line added to message:

   X-Content-Hash:C27

where

   C27  = 27 base-64 digits comprising the SHA-1
          hash of the From:, Sender:, Reply-To:,
          Date: and Subject: header lines plus the
          message body in unencoded form

This will allow a 46 byte "local-part" before breaking the 64-byte limit
while retaining the full security of #1, above.  Though the inner hash
length in the MAIL FROM: is short, it protects a 160-bit hash inside the
message headers, so it still puts an insurmountable computational burden on
an attacker.  The inner hash still needs to be there to tie the MAIL FROM:
to a particular message.  Otherwise, the signed MAIL FROM: could be used in
a replay attack.

One possible form of forgery attack would be to create a message that gives
the same 160-bit hash as contained in the X-Content-Hash: header.  This is
not currently realistic.  A second approach is to come up with a new 160-bit
hash that results in the same 24-bit inner hash (hhhh) in the MAIL FROM:,
which you showed is achievable.  However, the attacker is again left with
the problem of constructing a message that gives the new 160-bit hash, which
is not tractable.

I think this third option is best, since it requires the attacker to either
crack the outer hash secret or construct a message that yields an arbitrary
160-bit SHA-1 hash result.  It also allows the longest "local-part" before
breaking the 64-byte limit.

--

Seth Goodman