[ietf-clear] more on no callbacks, please

> From: Dave Crocker
> Sent: Tuesday, October 05, 2004 10:31 AM
>
>
> Thanks for the clarification.
>
>
> >  I'm sorry for leaving out some key details.  The sender does
> >  not store the per-message hash anywhere.  The hash is signed
> >  with an HMAC-SHA1, and both are included in the return-path
> >  or signature header.  To validate this signature, the
> >  validation server only needs to know the secret key and the
> >  signature format for the domain.
> That creates another question:
>
> When the server decrypts the signature, how does it know the
> string is valid?  Presumably it is some pre-established string
> that it recognizes?  That kind of repeatition of the contents
> (ie, predictability) makes the mechanism easier to break.
We assume that an attacker has already figured out exactly what the
signature format is, since many sites will use the defaults in any MTA patch
provided.  We make it hard to break by virtue of the cryptography.  This is
feasible because the signature has a limited lifetime and the signature is
inherently hard to crack.  Given that the attacker already know the exact
format, this type of signature really has two cryptographic features to
attack:  the HMAC and the digest.  Recall that the HMAC signs the digest, so
that limits the possible cryptographic attacks.  Here are the three main
ones.  Very similar considerations apply to DK signatures.

1) HMAC key guessing

Using a HMAC with SHA1 as the underlying one-way hash function and a 512-bit
key, an attacker needs 2^256 messages signed with the same key to
autonomously attempt to crack the key, assuming they have the full 160-bit
HMAC result.  Even with the requisite number of messages, this is considered
unsolvable today by cryptographers.  If keys are rotated with any reasonable
frequency, the number of messages signed with the same key is limited.  In
any practical case, _very_ few messages signed with the same key are
available to the attacker.  It is possible to mount a key guessing attack
with fewer than the optimal number of messages, but the attacker must then
involve your validation server, which makes the attack take longer.  With a
truncated HMAC result, as we use in the return-path signature, the attacker
will experience many more hash collisions, but will need even more
involvement from the validation server to resolve those collisions.  With
key lifetimes of the order that we are talking about, this attack is still
infeasible.

Cracking a key after it has expired is of no benefit to the attacker.  Even
though the keys are updated algorithmically, knowing one key does not help
you guess future keys.  RSA keys are generated in a similar way, and in fact
you can use the FIPS-186 method for RSA keys to generate a deterministic but
unpredictable sequence of secret keys for the HMAC.

2) Trivial modifications to the digest (chosen text attack on HMAC)

The attacker tries to substitute a message digest that matches their message
and also satisfies the HMAC.  Without knowing the HMAC key, the attacker is
forced to use your validation server to test every guess.  The validation
server can take classic measures to stem such a dictionary attack, such as
limiting negative responses to a given IP to a fixed number per second or
banning IP's, but an attacker can theoretically overcome this with a large
enough group of zombies.  Making the conservative assumption that any
dictionary attack countermeasures will be defeated and the attacker can use
your full validation server bandwidth for as long as they wish, the attack
is ultimately limited by the validation server bandwidth and the HMAC
signature lifetime.  Knowing these two values, a sender can set the number
of HMAC result bits to give the attack any desired probability of success.
Sites with very large bandwidth and/or more effective countermeasures can
use fewer than this number of HMAC result bits if the attacker cannot make
use of the full bandwidth of the validation server for the full signature
lifetime.  For the header signature, there is no reason to truncate the HMAC
result below its full 160-bit length and this attack becomes totally
infeasible.

3) Trivial modifications to the message (chosen text attack on digest)

The attacker takes their own headers and message and makes trivial
modifications to it until they create one with the same message digest as
contained in the signature.  Since the message digest algorithm is known,
this attack does not involve the validation server, is fully parallelizable
and off-line.  The attack is limited by the number of parallel hosts, the
number of HMAC's per second that each host can perform and the HMAC
signature lifetime.  Given these three variables, a sender can set the
number of message digest bits to give the attack any desired probability of
success.  For the header signature, there is no reason to truncate the SHA1
digest result below its full 160-bit length and this attack becomes totally
infeasible.

--

Seth Goodman