enciphering keys;brute-force attack; Yuval; Van Oorschot;collision;security">
###
Question 96. How does the length
of a hash value affect security?

The essential cryptographic properties of a hash function are
that it is both one-way and collision-free
(see Question 94).
The most basic attack we might mount on a hash function is to
choose inputs to the hash function at random until either we find
some input that will give us the target output value we are looking
for (thereby contradicting the one-way property), or we find two
inputs that produce the same output (thereby contradicting the
collision-free property).

Suppose the hash function produces an *n*-bit long output.
If we are trying to find some input which will produce some target
output value *y*, then since each output is equally likely
we expect to have to try *2*^{n} possible input values.

If we are trying to find a collision, then by the birthday paradox
(see Question 95) we would expect that after trying *2*^{n/2}
possible input values we would have some collision. Van Oorschot
and Wiener
[VW94] showed how such a brute-force attack might be
implemented.

With regard to the use of hash functions in the provision of digital
signatures, Yuval
[Yuv79] proposed the following strategy based
on the birthday paradox, where *n *is the length of the message
digest:

- Adversary selects the target message to be signed and an innocuous
message that Alice is likely to want to sign.
- The adversary generates
*2*^{n/2} variations of the innocuous
message (by making, for instance, minor editorial changes), all
of which convey the same meaning, and their corresponding message
digests. He then generates an equal number of variations of the
target message to be substituted.
- The probability that one of the variations of the innocuous
message will match one of the variations of the target message
is greater than 1/2 according to the birthday paradox.
- The adversary then obtains Alice's signature on the variation
of the innocuous message.
- The signature from the innocuous message is removed and attached
to the variation of the target message that generates the same
message digest. The adversary has successfully forged the message
without discovering the enciphering keys.

To avoid an attack that depends on brute-force methods, the output
from the hash function must be sufficiently long.