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

then she may nd 2nd preimages for the chaining variables and produce the valid MAC for arbitrarily many messages.

The secret envelop o ers a far smaller pro t than expected from the length of the secret key material used in the scheme [416]. Having a message m and a secret k = (kp; ks), the MAC is computed as H(kp k m k ks). One would expect that the attack on the MAC should involve exhaustive search of the keys space K2 if ks; ks 2R K. This is not true and now we show why.

Assume that an attacker can make enquires about the envelop MAC by composing her messages and collecting corresponding digests. The birthday paradox guarantees that if the attacker knows O(2n=2) observations f(m; H(kp k m k ks); m 2 Mg where the set jMj 2n=2, then there is at least one internal collision (n is the size of the digest). To identify the pair, the attacker

{Composes messages (m0; r; m00); m = (m0; m00) 2 M where r is a random message block and asks for their MACs.

{Two messages m1; m2 2 M have internal collision if their H(kp k m01; r; m001 k ks) = H(kp k m02; r; m002 k ks) where mi = (m0i; m00i ), for i = 1; 2.

Having two messages with internal collisions, the attacker now can exhaustively search the key space to identify kp. If jKj = n, then one pair of such messages is enough to identify kp with a high probability. In other words, k = kp if

H(k k m1) = H(k k m2):

Having identi ed kp, the second key ks can be also exhaustively searched through. Overall complexity of the attack is 2n=2 + 2n + 2n which is much smaller than the expected 22n.

Note that keyed hashing should use the secret key repeatedly throughout the whole hashing process. The keyed hash scheme MDx-MAC [416] uses a mod- i ed secret envelop and applies secret keys every time the underlying hashing algorithm is called. MDx-MAC can be based on any hashing algorithm (such as MD4, MD5, HAVAL, SHA) which uses internal constants (for example HAVAL uses in all iterations in the passes 2, 3, 4, and 5). The secret key is added to the constant in each iteration of the underlying hash algorithm. The advantage of this scheme is that it can be collision free even is the underlying hash algorithm is not. The main drawback of MDx-MAC is its speed. It is always slower than its keyless underlying algorithm.

282 6 HASHING

6.8 Problems and Exercises

1.Explain the di erence between strong and weak one-way hash function.

2.Prove that strong collision freeness of a function implies that the function is one-way.

3.Consider the birthday paradox. Let p be the probability that there are at least two pupils with the same birthday. What is the minimum size of the class so

{p = 0:1,

{p = 0:9.

What is the probability p when the class has 100 students?

4.To see how the birthday attack works, let us model a hashing function by a probabilistic

algorithm. For a given message, the algorithm chooses at random its digest from the set ZN where N is an integer. Implement the hash function using the accessible pseudorandom

number generator. Prepare two collections of digests (one for the original message the other for the bogus message). Each collection should have pN random numbers. Run your program several times and count how many times it is possible to nd colliding messages.

5.Let the encryption algorithm be based on exponentiation modulo a prime p so Ek(m) = ck mod p. Use the algorithm to hash messages (m1; m2) 2 Zp2 according to the following:

h1 = Em1 (IV ) and d = Em2 (h1)

Implement the meet-in-the-middle attack on the scheme using the MAPLE programming environment. To generate variants of bogus messages use a pseudorandom number generator.

6.Suppose a hash function is de ned using a good-quality encryption algorithm Ek(m). For

an arbitrary message m = (m1; : : : ; mn), the digest is computed as d = Emi (IV ) : : : Emn (IV ). Discuss advantages and drawbacks of the function.

7.In the Gibson scheme, the modulus N = p q is public, while its factors are secret. The hashing function is de ned as h(m) = gm mod N where g is a generator of the cyclic

group ZN . Let N = 4897 and g = 2231. Compute digests for the following two messages: m = 132748 and m0 = 75676. Assume that you have two colliding messages, show that it is possible to nd factors of N . Demonstrate that the knowledge of factors of N, allows

to nd colliding messages.

are two primitive elements such that logg1 g2 mod p is not known. Assume that p = 65867, g1 = 11638 and g2 = 22770. Find digests of the following two messages:

{ m = (33123; 11789) { m0 = (55781; 9871)

Prove that nding collisions is equivalent to solving the corresponding instance of discrete logarithm problem i.e. logg1 g2 mod p.

9. Consider the knapsack hashing that generates a digest

h(m) = X a (mod 2`)

a2Sm

for ` = 16 and the vector A = (a1; : : : ; a20) = (38434; 29900; 51969; 11915; 44806; 40745; 58466; 34082; 51216; 29628; 45210; 37681; 13804; 57494; 13287; 43391; 28827; 6822; 51901; 3782). Produce the digest for m = (1; 1; 1; 0; 0; 1; 0; 1; 1; 0; 0; 1; 0; 1; 0; 1; 0; 0; 0; 1). Write a program which nds collisions. Analyze the eÆciency of your program.

10.Implement a hashing scheme based on SL(2; 23 ) which operates on arbitrary long messages and produces 12-bit digests (four binary polynomials of degree 2).

7 DIGITAL SIGNATURES

Digital signatures should be, in a sense, similar to hand-written ones. Unlike a written one, an electronic document is not tied up to any particular storage media. Thus it can be easily copied, transmitted, and manipulated. Digital signatures have to create a some sort of digital \encapsulation" for the document so any interference with either its contents or the signature will be detected with a very high probability. Typically, a signed document is requested to be veri able by anyone using some publicly accessible information.

Most books on public-key cryptography also include a chapter or section on digital signatures. Stinson in [497], Menezes et al. in [338], and Schneier in [452] provide good text for introductory reading. The book [402] by P tzmann is useful for more advanced study of digital signatures.

7.1 Properties of Digital Signatures

One would expect that digital signatures should be legally binding in the same way as the hand-written ones. To design a signature scheme, it is necessary to determine two algorithms: one for signing and the other for signature veri cation. The veri cation algorithm has to be accessible to all potential receivers. The signing algorithm is executed by a signer, Sally, who for a message m 2 M determines a signature s 2 S. The signature s is next attached to the message. A veri er, Victor, takes the pair (m; s) and some public information about the alleged signer and performs the corresponding veri cation algorithm. The algorithm returns a binary result: OK if the signature is Sally's,, or FAIL otherwise.

A digital signature scheme is a collection of two algorithms.

1.The signing algorithm SG : K M ! S assigns a signature s to a pair: the secret key d 2 K of the signer and the message m 2 M, that is s = SG(d; m) = SGd(m). The signing algorithm can be also probabilistic.

286 7 DIGITAL SIGNATURES

2.The veri cation algorithm V ER : K0 M S ! fOK,FAILg takes a public information e 2 K0 of the signer and the message m 2 M and checks whether the pair (e; m) matches the signature s 2 S. If there is a match, the algorithm returns OK. Otherwise, it outputs FAIL.

3.The signing algorithm executes in polynomial time when the secret key d is known. For an opponent, Oscar, who does not know the secret key, it should be computationally intractable to forge a signature, that is to nd a valid signature for the message.

4.The veri cation algorithm is public { anyone can use it and check whether the message m matches the signature s. Veri cation should be easy (takes polynomial time).

Clearly, a valid signature must pass the veri cation or V ER(e; m; SGd(m)) = OK for any message m and the pair of keys (d; e).

The crucial issue for security of signature scheme is the meaning of forged signatures. Clearly, Oscar is successful in forging a signature if the veri cation algorithm fails to detect the forgery. The veri cation algorithm takes three variables: the identity of the alleged signer (equivalent to e), the message m, and the signature s. Oscar can tamper with all of them. Consider the identity of the alleged signer. Oscar can always apply the masquerade attack in which he selects the secret key d 2 K, sets up the scheme and try to register the scheme under Sally's name with the matching public e 2 K0. To protect the signature schemes against the masquerade attack, there has to be a trusted registry, PKI, which keeps the list of all signers with their public veri cation algorithms V ERe() in the public read-only memory. New entries are included after a proper identi cation of the signer.

If PKI are set up and work correctly, Oscar can only manipulate messages and signatures. His aim is to nd collisions for veri cation algorithm so V ERe(m; s) = V ERe(m0; s0) where m; s are original elements and m0; s0 are forged (m 6= m0). Thus the veri cation algorithm has to be collision free for any e 2 K0. This implies that the signing algorithm has to be collision free too.

Note that the requirement about public veri ability of signatures many times throughout their life time, can be satis ed when signatures are generated using conditionally secure schemes.

Signature schemes are requested to provide a relatively short signature for a document of an arbitrary length. We assume that the document (of arbitrary

length) is rst hashed, and later the signature is produced for its digest. Clearly, the hashing employed has to be collision free. Moreover, hashing and signing must be analyzed together to avoid attacks which exploit existing algebraic structures in both schemes. For instance, Coppersmith showed that hashing based on squaring together with an RSA based signature scheme is not collision free [107].

7.2 Generic Signature Schemes

This class of signature schemes can be implemented from any one-way function. Historically, these schemes were rst developed using private-key cryptosystems. We will follow the original notation. The applied one-way function is an encryption algorithm. The signer sets up her signature scheme by choosing a one-way function (encryption algorithm). Next she selects an index k (secret key) randomly and uniformly from the set K. The index determines an instance of the one-way function, that is, Ek : n ! n. Note that n has to be large enough to thwart possible birthday attacks. Also the index (secret key) k is known to the signer only.

7.2.1 Rabin Signatures

Rabin [424] designed a scheme in which the signer uses many secret keys (or indices) and later in the veri cation stage Sally reveals a part of her keys. In the Rabin scheme veri cation is done with the help of the signer.

Rabin signatures

Initialization: The scheme is set up by Sally who generates 2r random keys k1; k2; : : : ; k2r 2 n:

They are secret and known to Sally only. Next, she creates two sequences which are needed in the veri cation stage. The rst sequence is chosen at random:

S = (S1; S2; : : : ; S2r)

where Si 2 n for i = 1; : : : ; 2r. The second sequence

R = (R1; R2; : : : ; R2r)

288 7 DIGITAL SIGNATURES

consists of cryptograms of the sequence S, that is,

Veri cation: Veri er selects at random a 2r-bit sequence of r ones and r zeros. A copy of the binary sequence is forwarded to the signer. Using this 2r-bit sequence, Sally forms an r-element subset of the keys. The key ki belongs to the subset if the ith element of the 2r-bit sequence is 1; i = 1; : : : ; 2r. The subset of keys is then communicated to Victor. To verify the key subset, Victor generates and compares suitable r cryptograms of S to the originals kept in the public registry.

7.2.2 Lamport Signatures

The scheme invented by Lamport [297] allows veri cation to be conducted without any help from the signer. This is what is expected from signature schemes. More eÆcient version can be found in [50].

Lamport signatures

Initialization: The signer rst chooses at random n key pairs, namely,

each element kij 2 n; i = 1; : : : ; n, j = 0; 1. The pairs of keys are kept secret and are known to Sally only. Next, she generates a sequence S at random and encrypts it using the secret keys so

S = ((S10; S11); (S20; S21); : : : ; (Sn0; Sn1))

R = ((R10; R11); (R20; R21); : : : ; (Rn0; Rn1)) and

Rij = Ekij (Sij) for i = 1; : : : ; n and j = 0; 1

2 n and Ek is the encryption algorithm used. Now S and R are sent to the public registry.

SGk(m) = (k1i1 ; k2i2 ; : : : ; knin )

where ij = 0 if bj = 0 otherwise ij = 1; j = 1; : : : ; n.

Veri cation: Victor validates the signature SGk(m) by checking whether suitable pairs of S and R match each other for the keys known.

7.2.3 Matyas-Meyer Signatures

Matyas and Meyer [326] designed a signature scheme based on the DES algo-

rithm. Clearly, any one-way function can be used in the scheme. In the description we use Ek : n ! n.

Matyas-Meyer signatures

Initialization: Sally rst generates a random matrix U = [ui;j] i = 1; : : : ; 30, j = 1; : : : ; 31 and ui;j 2 n. Next she constructs 31 31 matrix KEY = [ki;j] where ki;j 2 n. The rst row of the KEY matrix is chosen at random but the rest is generated as follows:

ki+1;j = Eki;j (ui;j )

for i = 1; : : : ; 30 and j = 1; : : : ; 31. Finally, Sally communicates the matrix U and the vector (k31;1; : : : ; k31;31) (the last row of KEY ) to the public registry.

Signing: Sally takes a message m 2 n and computes cryptograms ci = Ek31;i (m) for i = 1; : : : ; 31:

Cryptograms are treated as integers and ordered according to their values so ci1 < ci2 < : : : < ci31 . The signature of m is the sequence of keys

SGk(m) = (ki1;1; ki2;2; : : : ; ki31;31):

Veri cation: Victor takes the message m recreates the cryptograms ci, orders them according to increasing order. Next he puts keys of the signature in the \empty" matrix KEY in the places indicated by the ordered sequence of cis. Victor then repeats Sally's steps and computes all keys below the keys of the signature. He accepts the signature if the last row of KEY is identical to the row stored in the registry.

290 7 DIGITAL SIGNATURES

Note that the Lamport and Matyas-Meyer generic signature schemes can be veri ed many times. However, signing a new message requires the secret key(s) to be regenerated. This is why they are called one-time signatures.

7.3 RSA Signatures

Due to its algebraic structure, the RSA cryptosystem can be easily modi ed for signing documents [432]. It is enough to let Sally initialize the system. Again PKI keeps public elements of Sally's RSA scheme.

One-time RSA signatures

Initialization: Sally chooses two strong primes p; q and calculates the modulus N = p q. Next she selects at random a public key e 2 ZN such that gcd (e; N) = 1. The secret key d 2 ZN satis es the following congruence

e d 1 mod (p 1)(q 1)

The signer lodges both the modulus N and the key e with the PKI registry.

The signature is attached to the message.

Veri cation: Victor looks up the PKI registry for Sally's public entry with her modulus N and public key e. Subsequently, he takes the pair (m;~ s~) and checks whether

V ERe(m;~ s~) = s~ m~ (mod N)

e ?

If the congruence is satis ed the signature is accepted as authentic.

An opponent, Oscar, can always circumvent potential veri ers using the following attack. He rst selects at random a false signature s0 2 ZN . Next he computes the matching false message m0 s0e (mod N). This attack is always successful if there is no redundancy of the message source or all messages in ZN are meaningful. The other feature of the attack is that Oscar has no control over forged messages. To prevent against the attack, it is enough to introduce a suÆciently large redundancy in the message source so all forged messages will be meaningless with a high probability.