RE: CBV

Here are the latest SES methods incorporating some suggestions and
refinements for all to criticize.  All of the methods below validate that
the message originated from the address in the return path, including the
local part of that address.

I) This format is the simplest and is suitable for most email senders.  This
format has no protection against replay attack, so it is assumed that these
senders do not send messages to known spammers, malicious individuals or
organizations.

SES0=HHHH=TT=local-part@domain

where

   HHHH = minimum of the first four base-64 digits of the
          SHA-1 HMAC of "TT=local-part@domain" using a
          key unique for local-part@domain

   TT   = minimum of the first two base-32 digits of the
          integer part of the  UNIX day number mod 1024;
          additional digits for the integer or fractional
          day parts may be added

This format has 13 characters of overhead, which allows 51 characters in the
local-part before exceeding the 64-byte limit.  All messages sent out by
that local-part with the same timestamp will have the same HMAC.  If this is
a concern, adding fractional day digits to the timestamp acts to salt the
hash and the HMAC value will change whenever the timestamp does.  For
example, adding three factional day digits to the timestamp will give a
timestamp resolution of 2.6 seconds, which should be adequate for typical
users.  This reduces the available local-part to 48 characters, which is
still fairly long.


II) A relatively small number of accounts have, by their nature, a
significant chance of having their signed return path harvested and used in
a replay attack.  To partially mitigate the threat of replay attack, use the
same format as in I) above but extend the timestamp field with enough
fractional day digits to act as a unique message identifier for that
local-part on that day.  By adding four fractional day digits to the
timestamp field, this gives 82msec time resolution, and a maximum of 1
million messages per day for a given local-part.  This reduces the available
local-part to 47 digits, which is still fairly long.

For each local-part, the MTA maintains a list of invalidated timestamps that
are not expired.  For any incoming CBV for a local-part, the MX first checks
for expiration of the timestamp, then for invalidation of the timestamp and
finally validates the SHA-1 HMAC.  This method requires the owner of that
local-part address to realize that a joe-job is taking place and to request
that the specific return-path timestamp being used in the attack be
invalidated.  It only requires a minimal extra burden on the originating
gateway MTA to maintain an invalidated timestamp list for each local
address.


III) Where much stronger and automatic protection against replay attacks is
desired, another option is to use II) above, but the sending MTA
additionally maintains a database of all outgoing timestamps that are not
expired for each local sending address.  The database record for each
timestamp contains the list of RCPT-TO: addresses for that particular
message.  Since the database records function as mailing list expansions,
there may be existing mechanisms in the MTA to accomplish the database
function.

For any incoming CBV for a local-part, the MX first checks for expiration of
the timestamp, then for invalidation of the timestamp and finally validates
the SHA-1 HMAC.  If the result is a 250 response, the SMTP-client then
issues an EXPN command for "TT=local-part@domain".  The SMTP-server looks up
the timestamp entry for the local-part in the database (or does mailing list
expansion, if implemented that way) and sends the SMTP-client the list of
original RCPT TO: addresses that were on the outgoing message.  If the CBV
resulted in a 5xx response, the EXPN command is declined.

Since all the recipients listed on a given message will be served by the
same destination MTA, that MTA should have access to a whitelist of any
forwarding accounts that it's users have set up that forward to that MTA.
If the list of recipients does not match the list of recipients (including
whitelisted forwarders) for the current message, the MTA can reject the
message as a forgery before DATA.  Just as in II) above, if the owner of a
sending account notices that a joe-job is taking place with their return
address, they can request that the specific return-path timestamp be
invalidated to give additional protection in case the final recipient does
not issue the EXPN command during the CBV.

This approach gives the best immunity to replay attacks while still being
able to detect and reject them before DATA.  However, it does require the
originating gateway MTA to maintain a database with the list of all
recipients for every outgoing message.  The database entries expire when the
timestamp indexing them expires.


IV) Another option for very strong protection against replay attacks is to
include a MAC in the MAIL FROM: that covers the entire DATA part, minus the
headers that are unknown or may change during message transit.  This has the
advantage that no database is required at the sending end.  It has two
disadvantages:  first, the MAC cannot be verified until the end of the DATA
phase, and second, including a strong MAC in the MAIL FROM: reduces the
available length for the local part of the address.  Here is the format:

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

where

   HHHH = minimum of the first four base-64 digits of the
          SHA-1 HMAC of "TT=C27=local-part@domain" using a
          key unique for local-part@domain

   TT   = minimum of the first two base-32 digits of the
          integer part of the  UNIX day number mod 1024;
          additional digits for the integer or fractional
          day parts may be added

   C27  = 27 base-64 digits comprising the SHA-1 MAC of
          the From:, Sender:, Reply-To:, Date:, Subject:,
          In-Reply-To: and References: headers plus the
          unencoded message body; the MAC may be shortened
          down to the first 14 base-64 digits, as
          necessary to accommodate the local-part

This format has between 27 and 41 characters of overhead, which limits the
local-part to 37 downto 23 characters, respectively, before exceeding the
64-byte limit.  The final gateway MTA should do a CBV upon receiving the
MAIL FROM: command to make sure that the message originated with the
purported sending MTA.  Though the initial CBV will detect casual forgeries
and allow rejection before DATA, more sophisticated replay attacks will be
detected only at the end of  DATA.  The recipient MTA can still reject the
message at the end of DATA and have no further responsibility for dealing
with it.

Here's an attempt at a brief justification for a shorter MAC, only when
necessary, of course.  Shortening the C27 MAC down to 14-digits still
maintains at least 80-bits, as recommended in RFC2104.  Here's a
"back-of-the-envelope" justification for doing this when needed.  The SHA-1
MAC takes on the _order_ of millisecond to compute with today's hardware.
In order to brute force a message to give an identical MAC shortened to 14
base-64 digits (84-bits), one would need to compute roughly 2^42 trials.
Assuming the originating MTA will expire the timestamp in two weeks, the
average MAC computation time would have to be 275nsec.  This is a factor of
3600 faster than is possible today.  As a hardware engineer, my opinion is
that this is _very_ unlikely in the foreseeable future with silicon-based
transistors (or SiGe, or HEMFET's, etc.), proponents of Moore's law
notwithstanding.  Parallelizing the problem is certainly possible, but then
communications bandwidth becomes the limiting factor.  Assuming that typical
message data covered by the MAC is 1Kbyte, this would require 29Gbits/sec
communication bandwidth, exclusive of overhead.  While this is within reach
in the foreseeable future using an advanced TCA backplane architecture with
multiple bit lanes, since this means using _local_ CPU's you would need a
very large CPU farm which would be prohibitively expensive.  This kind of
network bandwidth will not be available outside of a single facility for a
very long time, so the idea of using an army of hijacked PC's would not be
practical.

----------------------------------

Here is a question for those more knowledgeable than myself on the
practicalities of SMTP.  What are the _practical_ consequences, aside from
breaking RFC compliance, of exceeding the 64-byte limit for the local part
of MAIL FROM: addresses?  How do the majority MTA's deal with this error
today?

--

Seth Goodman


As a general question to those who know more about