Cryptography Reference
In-Depth Information
2.
For i from 1 through t, generate the hash h(P
i
), and store it with the message P
i
.
, say P
*
. Search the table for a
message P
k
such that h(P
k
) = h(P
*
) for some k. (The search of the table can be done in
constant time if a hash table is used.)
3.
Generate a minor modification of the bogus message P
If the search is successful, stop. The current P
*
is the fraudulent message, to send in place
of P
k
. If the search is not successful, return to step 3.
4.
Depending on n (the hash size), the birthday attack can have enormous storage require-
ments. If n = 64, the table will contain 2
32
4 billion elements. If each modified message
and its hash takes, say, one thousand bytes each, then we are talking storage space of about
4 terabytes. Though this seems large, it is feasible, or soon will be. Thus, digest functions
which produce 128 bit (or larger) hashes are preferable.
Note that it may be possible for the “bad guy” to modify only the bogus message. This
considerably increases the amount of selections one should make before expectations of
finding a match are high. As an example, suppose your birthday is July 15. How many peo-
ple should you randomly sample from the population so that the odds are greater than 50
percent that you will find someone with your birthday?
There are many other attacks on digest functions. Unfortunately, due to space consider-
ations, we cannot cover them here. An excellent reference for this topic (and many other top-
ics in cryptography) is The Handbook of Applied Cryptography, by Menezes, van Oorschot,
and Vanstone, published by CRC.
16.9
ZERO KNOWLEDGE IDENTIFICATION
Sometimes all that is desired in an exchange between two parties is that one be assured of
the identity of the other. (This is common among military protocols.) There are various
ways to do this, but one of the most interesting ways is to use “Zero Knowledge Identifi-
cation.” This refers to convincing someone that you are who you claim to be by convinc-
ing them that you know certain information that only you could know, but without revealing
that information to anyone, including the entity you are trying to convince! In these types
of exchanges, the entity trying to prove their identity is called the respondent, and the entity
trying to establish the identity of the respondent is called the challenger.
For example, suppose individual A is known to be using a public modulus n, where n is
the product of two large strong primes both congruent to 3 modulo 4, say p and q. A can con-
vince another individual, say B, that he knows these primes, without revealing them to B.
If A can do this, B is assured that A is really who he claims to be. A and B proceed in this
way:
1.
Let A (the respondent) choose n as the product of two strong primes, p and q. A also
chooses some integer s such that s has a square root modulo n. The integers s and n are
public, and registered with a Trusted Third Party (TTP). A computes t, the lnr of a square
root of s modulo n; that is, he computes t such that
t
2
s (mod n)
0
≤
t < n.
Search WWH ::
Custom Search