Re: truncated hashes

bram (bram@gawth.com)
Tue, 30 Jun 1998 12:52:03 -0700 (PDT)

• Next message: Joshua Hill: "a question RE: PKCS1 known cyphertext attack"
• Previous message: Paulo Barreto: "Yet another optimized Skipjack"

On Mon, 29 Jun 1998, Perry E. Metzger wrote:

> bram writes:
> >
> > [truncation] can also leave you more vulnerable to attacks where an
> > enemy substitutes phony messages for real ones - it's easier to find
> > substitutes which slip by the MAC.
>
> Nope, it isn't. It is harder, assuming that we are attempting an
> attack and not brute force. If you are assuming a brute force attack
> of, say, 2^96th texts being sent to you is reasonable, then I suppose
> you would be correct, but we are making the assumption that isn't
> true.

That's assuming that a brute force attack is the best possible one. The
definition of a secure hash is that it's computationally infeasible to
find a bitstring which hashes to an arbitrary value, and also
computationally infeasible to find any two bitstrings which hash to the
same thing. For an arbitrary hash function, there is no particular reason
to assume a priori that it has any truncation properties.

As a trivial case, consider the hash function which is 160 bits of zero
followed by a SHA-1 hash. It trivially has the same security as SHA-1, if
a bit less efficient in space, but is completely worthless when truncated.

It is also dubious to assume that truncating the hash will leak less
information about the message. Consider the case of SHA-1 repeated twice.

Further, one gains no runtime speed by truncation, and saves very little
memory.

Going to the source, this is what it says in FIPS180-1:

> Applications: The SHA-1 may be used with the DSA in electronic mail,
> electronic funds transfer, software distribution, data storage, and
> other applications which require data integrity assurance and data
> origin authentication. The SHA-1 may also be used whenever it is
> necessary to generate a condensed version of a message.

There's no reference to 'truncation' anywhere in that document. I find it
highly unlikely that the authors would have skipped saying anything about
truncation if they thought it was a good idea.

It is interesting that there don't seem to be any cryptographically strong
MACs around which aren't related to secure hashes. I suspect this is a
matter of practicality - to convince someone that a MAC is bad it is
necessary to go through an involved argument about a convincing attack. To
do the same for a hash simply involves giving two bitstrings which
collide.

> Try starting with the references in RFC2104 on the tradeoffs of
> truncation.

That RFC says the following:

> We recommend that the output length t be not less than half the length
> of the hash output (to match the birthday attack bound)

Which is completely reasonable. It then goes on to say the following:

> These properties, and actually stronger ones, are commonly assumed for
> hash functions of the kind used with HMAC.

Notice the word 'assume'. Cryptographers aren't normally in the business
of assuming.

It then says:

> In particular, a hash function for which the above properties do not
> hold would become unsuitable for most (probably, all) cryptographic
> applications

This is completely untrue, given my trivial counterexamples above.

Of course, if the designer of a hash I were using were to say that it was
a good idea to truncate it, I'd go along with that, but until then I'll
just use hashes as specified.

-Bram

• Next message: Joshua Hill: "a question RE: PKCS1 known cyphertext attack"
• Previous message: Paulo Barreto: "Yet another optimized Skipjack"