Cryptography Reference
In-Depth Information
the message
. In addition to other parties, both the verifier (receiver), and the signer (sender)
of a message may wish to have this ability. Why?
If a third party is able to produce a bogus message
P
P
, such that
h
(
P
) =
h
(
P
), he may be
able to convince the signer to sign
P
, then later claim this signature is for
P
. The meanings
of
P
and
P
may be totally different. For example, suppose you want your secretary to draft
a message
that orders your company bank to transfer funds to more conservative stocks.
Instead, by careful construction, he drafts a fraudulent message
P
which orders the bank
to transfer 1.3 million company dollars to his Swiss bank account! By virtue of this careful
construction, it so happens that
P
) are equal. The bank receives the bogus mes-
sage, accepts it as authentic, and the next day your secretary is nowhere to be found. The
verifier (an employee of the bank, in this case) may also want to be able to do this (if he also
leans toward dishonest activity).
The signer can also do this. Suppose you are a high-ranking official of your government,
and you want to send a message
h
(
P
) and
h
(
P
ordering the death of millions of innocent civilians. By
careful construction, you are able to produce a message
P
P
that instead conveys great love
and affection for the masses. It so happens that
to
your generals, who accept it as genuine, and then carry out your orders. Later, when NATO
is trying you for crimes against humanity, you whip out the message
h
(
P
) =
h
(
P
). You send the message
P
, claiming that it was
the message you really sent. You claim that some adversary confiscated the message
P
P
and
sent
in its place. The act of denying that you sent a signed message is known as repudi-
ation. A good digest function enforces nonrepudiation; that is, it makes it far too difficult for
a signer to find a bogus message to use in place of the real one.
Now do you see why a digest function must have the three required properties? If you
recall, they are:
P
1.
Given a hash value
h
(
m
), it must be extremely difficult to determine
m
.
2.
Given a message
m
, it must be extremely difficult to find another message
m
such that
h
(
m
) =
h
(
m
).
3.
It must be extremely difficult to find any two messages, say
m
and
m
, for which
h
(
m
) =
h
(
m
).
The Birthday Attack
The following illustrates a method to defeat a digest function,
known as the birthday attack. It is based on the following well-known principle: If you
select (with replacement) from a set of
m
objects, with high probability, you can expect to
draw some element twice within
√
m
selections.
The way we normally hear this is from the birthday problem: If you select randomly
from the population, the odds are high that you will encounter 2 people with the same birth-
day within about 19
√
365 selections.
In the birthday attack, we assume the individual with bad intent can make modifications
to both the real message (
P
), and the bogus message (
P
). Suppose the digest function pro-
duces an
n
-bit hash. Thus, there are 2
n
possible hashes (2 choices for each bit.) Note before
we begin that
√
(2
n
) = 2
n
/2
. This is what to do:
= 2
n
/2
minor modifications to the message
1.
Generate a table of
(add a space, delete a
semicolon, use a similar word, etc., etc. . . ). Label these modified messages
t
P
P
1
,
P
2
, ...,
P
t
.
Search WWH ::
Custom Search