Sebery J.Cryptography.An introduction to computer security.1989

L R

f

g

S T

Fig. 5.3. Permutation generator R(f; g)

Comparator

Fig. 5.4. A distinguishing circuit for R(f; g)

{Collects the answers (S1; T1) and (S2; T2) from the oracle gates.

{There are two possible cases:

1.A tested permutation is an instance of R(f; g), then S1 = L1 f(R) and S2 = L2 f(R) so L1 L2 is equal to S1 S2.

2.Otherwise S1 and S2 are n-bit random string and L1 L2 6= S1 S2 with the probability 2 n.

{Returns the result from the comparator as its guess.

Luby and Racko [308] analyzed permutation generators based on Feistel transformations. In particular, they de ned a permutation generator R(f; g; h) = f 2n(f; g; h) j f; g; h 2R R; n 2 Ng which uses three Feistel permutations and three random functions. They proved the following theorem.

242 5 PSEUDORANDOMNESS

Theorem 24. Let f; g; h 2R R be three independent random functions and C2n be a probabilistic circuit with m < 2n oracle gates, then

As the number m has to be polynomially bounded (the witness circuit has to be of a polynomial size), the two generators cannot be told apart by any polynomial witness. Note that the permutation generator R(f; g; h) can be implemented by no polynomial time algorithm as it uses three random functions f; g; h 2R R. But if the functions f; g; h are chosen from a pseudorandom function, then the resulting permutation generator is pseudorandom. Let our

for some constant k.

An interesting observation is that the pseudorandom permutation (f; g; h) is immune against the chosen plaintext attack. Oracle gates allow the circuit to query about cryptograms for messages chosen by the circuit.

Another interesting issue is the number of pseudorandom functions used in the permutation generator. Ohnishi [386] proved that both (f; g; g) and(f; f; g) are pseudorandom. Rueppel [438] showed that R(f; f; f) can be ef-ciently distinguished from . The distinguisher is depicted in Figure 5.6. It employs two oracle gates O1 and O2 only. The circuit chooses L; R 2R n and queries the oracle gate O1. The two n-bit strings of the answer are swapped and the oracle gate O2 is queried for the swapped answer. If the oracle gates are evaluated using a function from R(f; f; f), then O2 has to return a string that is equal to (L; R) as O2 undo the process done by O1. Otherwise, if the oracle gates are evaluated using a function from , O2 returns a random string that is di erent from (L; R) with the probability 2 2n. Zheng, Matsumoto, and Imai showed in [546] that (fi; fj; fk) is not pseudorandom where i; j; k 2 N and fi = |f Æ :{z: : Æ f}i. They gave a construction of a probabilistic polynomial

6 HASHING

In many cryptographic applications, it is necessary to produce a relatively shortngerprint of a much longer message or electronic document. The ngerprint is also called a digest of the message. Cryptographic applications of hashing include, among others, the generation of digital signatures.

6.1 Properties of Hashing

A hash function is required to produce a digest of a xed length for a message of an arbitrary length. Let the hash function be

h : ! n;

where = Si2N i. It is said that two di erent messages m1, m2 collide if h(m1) = h(m2):

It is obvious that there are in nitely many collisions for the hash function h. The main requirement of a secure hashing is that it should be collision resistant in the sense that nding two colliding messages is computationally intractable. This requirement must hold not only for long messages but also for short ones. Observe that short messages (for example single bits) must also be hashed to an n-bit digest. In practice, this is done by rst padding the message and later by hashing the padded message. Clearly, a padding scheme is typically considered as a part of the hash function.

Given a hash function h : ! n. We say that the function is

{Preimage resistant if for (almost) any digest d, it is computationally intractable to nd the preimage (message m) such that d = h(m). This means that the function is one-way.

{2nd preimage resistant if given the description of the function h and a chosen message m1, it is computationally intractable to nd another message m2

246 6 HASHING

which collides with m1, i.e. h(m1) = h(m2). 2nd preimage resistance is also equivalently termed weak collision resistance.

{Collision resistant if given the description of the function h, it is computationally infeasible to nd two distinct messages m1; m2 which collide, i.e. h(m1) = h(m2). Collision resistance is equivalent to strong collision resistance.

There are many di erent de nitions of hash functions depending on what properties are required from them. There are, however, two major classes of hash function de ned as follows:

1.A one-way hash function (OWHF) compresses messages of arbitrary length into digests of xed length. The computation of the digest for a message is easy. The function is preimage and 2nd preimage resistant. Equivalently, the function is termed weak one-way hash function.

2.A collision resistant hash function (CRHF) compresses messages of arbitrary length into digests of xed length. The computation of the digest for a message is easy. The function is collision resistant. Equivalently, the function is termed strong one-way hash function.

Collision resistant hash functions can be used without special care if thending collision must be always an intractable task. On the other hand, oneway hash functions do not guarantee that a given selection of two messages is collision resistant.

Note that a collision resistant hash function must be a one-way function. This statement can be proved by contradiction [497]. Assume that a hash function h is not one-way, i.e. there is a probabilistic polynomial time algorithm R which for a given digest d returns a message m = R(d) such that d = h(m). The algorithm R can be used to generate collisions in the following way:

{Select at random m and nd its digest d = h(m).

{Call the algorithm R which returns m0 = R(d) such that d = h(m0).

{If m 6= m0, then this is a collision. Otherwise select other random message and repeat the process.

6.2 Birthday Paradox

For secure hashing, it must be intractable to nd collisions. In general, it is assumed that the adversary knows the description of the hashing algorithm. It

is also assumed that the adversary can perform an attack, where she may choose messages, ask for their digests, and try to compute colliding messages. There are many methods of attack on a hash scheme. The so-called birthday attack is a general method and can be applied against any type of hash function. Other methods are applicable against only special groups of hash schemes. Some of these special attacks can be launched against a wide range of hash functions. The so-called meet-in-the-middle attack can be launched against any scheme that uses some sort of block chaining. Others can be launched only against smaller groups.

The idea behind the birthday attack originates from a famous problem from Probability Theory, called the birthday paradox. The paradox can be stated as follows. What is the minimum number of pupils in a classroom so the probability that at least two pupils have the same birthday; is greater than 0:5? The answer to this question is 23, which is much smaller than the value suggested by intuition. The explanation is as follows: Suppose that the pupils are entering the classroom one at a time. The probability that the birthday of the rst

pupil falls on a speci c day of the year is equal to 3651 . The probability that the

birthday of the second pupil is not the same as the rst one is equal to 1 3651 . If the birthdays of the rst two pupils are di erent, the probability that the

birthday of the third pupil is di erent from the rst one and the second one is

It can be easily computed that for t 23, this probability is bigger than 0:5. In general, the probability of nding at least two pupils with the same birthday is at least 0:5 if the number of pupils is roughly pn and the year has n days.

The birthday paradox can be employed to attack hash functions. Suppose that the number of bits in the digest is n. Any message m can be represented (written) in many di erent ways. A single representation of the message is called a variant. For instance, the message

On November 5, 1998, I sold my PC to Mr. John Brown for 1,000 dollars. can be equivalently written as

On November 5, 1998, I have sold my PC to John Brown for $1,000.

Due to the natural redundancy of a language, it is always possible to generate many variants of the same message. The variants can be created by adding blanks and empty lines, using equivalent words, abbreviations, and full wording, or removing some words whose existence is not essential. In the attack, an adversary generates r1 variants of an original message and r2 variants of a bogus message (Figure 6.1). The probability of nding a pair of variants (one of the genuine and one of the bogus message), which hashes to the same digest is

bits is insecure as the time complexity function for the corresponding birthday

attack is 232 . It is usually recommended that the hash value should be longer than 128 bits to achieve a suÆcient security against the attack.

This method of attack does not take advantage of structural properties of the hash scheme or its algebraic weaknesses. It can be launched against any hash scheme. It is assumed that the hash scheme assigns to a message a value that is chosen with a uniform probability among all the possible hash values. Note that if there is any weakness in the structure or certain algebraic properties of the hash function so digests do not have a uniform probability distribution, then generally it would be possible to nd colliding messages with a better probability and fewer message-digest pairs.

The birthday attack may also be modi ed to t a particular structure of the hash scheme. Consider a variant called the meet-in-the-middle attack. Instead of comparing the digests, the intermediate results in the chain are compared. The attack can be launched against schemes that employ some sort of block chaining in their structure. In contrast to birthday attack, the meet-in-the-middle attack enables an attacker to construct a bogus message with a digest selected by the attacker. In this attack the message is divided into two parts. The attacker generates r1 variants of the rst part of a bogus message. He starts from the initial value and goes forward to the intermediate stage. He also generates r2 variants on the second part of the bogus message. He starts from the desired target digest and goes backwards to the intermediate stage. The probability of a match in the intermediate stage is the same as the probability of success in the birthday attack.

Consider a hash scheme that uses an encryption function E : K M ! n where K = M = n. For a message m = (m1; m2), the digest is computed in two steps:

h1 = E(m1; IV ) and

d = h(m) = E(m2; h1);

where IV is a public initial vector. This scheme can be subject to the meet- in-the-middle attack. Let the opponent want to nd a bogus message m = (m1; m2) that collides with m with the digest d. The opponent chooses r1 variants of m1 and r2 variants of m2 (Figure 6.2). Let the two sets of variants be:

fm1;i j i = 1; : : : ; r1g and