RE: CBV

> From: Mark Shewmaker
> Sent: Saturday, May 15, 2004 12:46 PM
>
>
> On Thu, 2004-05-06 at 22:36, Seth Goodman wrote:
> > > From: Mark Shewmaker
> > > Sent: Thursday, May 06, 2004 6:04 AM
>
> [Deleting a lot of stuff on how and where we're in agreement, (very well
> worded stuff, btw, helpful for people following along in the archives
> later.)]
>
> > 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.
>
> I would note that it's harder for an attacker to find valid
> inner-hash/outer-hash pairs than to simply figure out a valid inner
> pair, because while doing a brute force test of an inner hash is a
> cpu-bound activity that can be done entirely on the attacker's machines
> in a couple milliseconds, checking to see if any particular inner/outer
> pair matches Because checking to see if a forged header/body matches
> requires a CBV test--far more expensive in terms of clock-time, and
> detectable by the server.

Without knowing the key for the outer truncated HMAC, I think an attacker is
pretty much stuck.  Remember, there is more than one possible key that will
give the same HMAC on a given block of data.  This particular situation gets
worse for the attacker when we shorten the result string, even though his
effort to find a candidate key is made easier.  Shortening the hash result
weakens the protection quite a bit, but it is still an extremely difficult
problem.

Shevek can better address the required compute resources to crack the
shortened hash than myself, since he researched the minimum length required
for SRS.  However, even if the attacker did succeed in getting one candidate
key from the truncated hash result, at very considerable CPU effort, they
have no assurance that this is the actual key used by the mail sender.  From
a probabilistic standpoint, since the number of possible keys that would
yield the same truncated HMAC result from the same data block is larger when
the hash string is truncated more, it is rather unlikely that the attacker's
first successful candidate key would be the correct key.  After all the work
of cracking multiple candidate hash secrets to get the correct one, all the
attacker has is the hash key for one local address at the domain in
question.  All you have to do to stop the joe-job is to change the hash
secret for that one single user.  There are easier ways to make a living and
that's all we need to accomplish.

What's more important here is my assertion, backed up by Tony's anecdotal
observation, that signed return-paths are, in general, not harvestable.
Since part of the spec would be that the receiving MTA strip the signature
part and just put the usable email address in the Return-Path: header, only
malicious parties that run hacked MTA's would have access to the full signed
return path. Normal users of email don't send mail to such parties.  Mailing
lists already rewrite the return path so the original SES signed address is
gone.


<...>

> > 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.
>
> I am not at all confident that that is a good idea.
>
> 24 bits gives just 16 million combinations.
>
> Since the end verification takes place on the server, an attacker would
> have to present ~8 million combinations to expect a 50% chance of
> getting making a match by chance.
>
> We can detect that many attempts. :-)

Hopefully, you'd cut them off well before then :)  Guessing the outer hash
is therefore not a realistic attack method.

>
> However, with that small an outer hash, validation might become possible
> without contacting the server because an attacker will have many valid
> mail_froms to look at.
>
> (We should assume a dedicated attacker can  collect many valid MAIL
> FROMs for any given inner-local-part, hundreds, thousands maybe.  It's
> not unrealistic to think this--places that send enormous amounts of
> emails for constant local-parts are the very places most valuable for an
> attacker to focus on.)

I still assert that signed return path harvesting is only possible from a
relatively small number of promiscuous mail senders.  Those are the only
accounts that need to worry about replay attacks, so the rest of us can use
the original, much simpler form of SES address with no protection against
replay attacks.  Owners of promiscuous accounts, or those who, because of
their job functions, must communicate with spammers, can use one of the
protected SES formats we have been discussing.  I'll list those in a
separate post to give everyone the most up-to-date versions to criticize.


>
> While having many valid H27=sha1(rest_of_mail_from+secret)'s from many
> different mail_froms might result in the secret being hard to compute
> when sha1 outputs 160bit, the secret may not be as hard to find when the
> output is truncated to 24 bits.
>
> I worry that
> truncated_to_24_bits(H27=sha1sum(rest_of_mail_from+secret_1)) is
> equivalent to simpler_hash(rest_of_mail_from+secret_2), in which secret
> is much easier to find and vulnerable to a known plaintext attack.  In
> fact, I would also worry that there could be *many* potential secret_2's
> for any secret_1.

Shortening the hash to 24-bits does make it easier to crack, but recall that
a good hash key for a SHA-1 is 64-bytes, which is 512-bits.  Each MTA can
generate keys anyway they want and the attacker has no knowledge of the
local key-generation mechanism.  Unless the MTA uses a cryptographically
inferior method of generating keys (we can address this by providing
recommendations), the attacker is left to guess a 512-bit key.  Again, I
would call on Shevek to provide the specifics, since he already did the
detailed research on this, but it appears pretty obvious that at some
minimum of hash length, this job becomes intractable.  On such a matter, I
would definitely trust Shevek's research over either my own or your
intuition.

>
> If, let's say, an attacker can collect 4000 good mail_froms from a
> single day, then he'll have 1/4000 of the whole problem space to study,
> (4k/16M=1/4k), which I think is a conveniently large percentage to have
> at hand for a known plaintext attack.

As I've argued above, being able to collect this many signed return paths
would be pretty difficult.  If you have an account that is prone to this,
you can use one of the more secure SES alternatives.

>
> So if there's no reason to keep HHHH at 4 characters, I'd suggest making
> it of variable length.

I changed the description to a minimum of four base-64 characters.


>
> > 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.
>
> I can grudgingly accept that logic.  I would suggest that while a two
> digit timestamp seems sufficient, that there is still no need for SES to
> nail it down to two digits as a requirement.
>
> If we later find that there is a need for sub-second timestamps here,
> (doubtful), and servers start using T6's, recipients parsing the SES
> format should be required to still deal with such a longer T.
>
> (Or SES sending machines might have other reasons to later overload the
> T field by adding in another character of information.  There's no need
> to cut off that possibility.)

I agree, so I also changed the description to a minimum of two base-32
digits with more digits possible to the left or right of the binary point.

--

Seth Goodman