Cryptography Reference
In-Depth Information
is given and we try to find
x
2
. This is called second preimage resistance or weak
collision resistance. The second case is given if an attacker is free to choose both
x
1
and
x
2
. This is referred to as strong collision resistance and is dealt with in the
subsequent section.
It is easy to see why second preimage resistance is important for the basic
signature with hash scheme that we introduced above. Assume Bob hashes and
signs a message
x
1
. If Oscar is capable of finding a second message
x
2
such that
h
(
x
1
)=
h
(
x
2
), he can run the following substitution attack:
Alice
Oscar
Bob
k
pub
,
B
←−−−−−
z
=
h
(
x
1
)
s
= sig
k
pr
,
B
(
z
)
(
x
2
,
s
)
←−−−−−
(
x
1
,
s
)
←−−−−−
substitute
z
=
h
(
x
2
)
ver
k
pub
,
B
(
s
,
z
)=true
As we can see, Alice would accept
x
2
as a correct message since the verification
gives her the statement “true”. How can this happen? From a more abstract view-
point, this attack is possible because both signing (by Bob) and verifying (by Alice)
do not happen with the actual message itself, but rather with the hashed version of
it. Hence, if an attacker manages to find a second message with the same fingerprint
(i.e., hash output), signing and verifying are the same for this second message.
The question now is how we can prevent Oscar from finding
x
2
. Ideally, we would
like to have a hash function for which weak collisions do not exist. This is, unfor-
tunately, impossible due to the
pigeonhole principle
, a more impressive term for
which is
Dirichlet's drawer principle
. The pigeonhole principle uses a counting ar-
gument in situations like the following: If you are the owner of 100 pigeons but in
your pigeon loop are only 99 holes, at least one pigeonhole will be occupied by 2
birds. Since the output of every hash function has a fixed bit length, say
n
bit, there
are “only” 2
n
possible output values. At the same time, the number of inputs to the
hash functions is infinite so that multiple inputs must hash to the same output value.
In practice, each output value is equally likely for a random input, so that weak
collisions exist for all output values.
Since weak collisions exist in theory, the next best thing we can do is to assure
that they cannot be found in practice. A strong hash function should be designed
such that given
x
1
and
h
(
x
1
) it is impossible to
construct x
2
such that
h
(
x
1
)=
h
(
x
2
).
This means there is no analytical attack. However, Oscar can always randomly pick
x
2
values, compute their hash values and check whether they are equal to
h
(
x
1
).This
is similar to an exhaustive key search for a symmetric cipher. In order to prevent this
attack given today's computers, an output length of
n
= 80 bit is sufficient. However,
we see in the next section that more powerful attacks exist which force us to use even
longer output bit lengths.
