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

who has a single secret key. There are, however, many other keys which can be used to produce the same signature and match the public key. Thus there is a high probability that the key computed or guessed by powerful Oscar will be di erent from the one held by Sally.

Let x be a secret key known to Sally only and K be the public key. Then Sally's signature is s = SGx(m) for the message m. A fail-stop signature must satisfy the following conditions:

1. An opponent with unlimited power can forge signature with a negligible probability. More precisely, if Oscar knows the pair (s = SGx(m); m) and Sally's public key K, he can create a collection of all keys Ks;m such that x 2 Ks;m i s = SGx (m) = SGx(m). The size of Ks;m has to be exponential with the security parameter n. As Oscar does not know the secret x, he may only guess an element from Ks;m. Let this element be x . Now if Oscar signs another message m 6= m, it is required that s = SGx (m ) 6= SGx(m ) with an overwhelming probability.

2.There is a polynomial-time algorithm which for the input: a secret key x, a public key K, a message m, a valid signature s and a forged signature s , returns a proof of forgery.

3.Sally with polynomially bounded computing power cannot construct a valid signature which she can later deny by proving it to be a forgery.

Clearly, after Sally has provided a proof of forgery, the scheme is considered to be compromised and is no longer used. That is why it is called \fail-stop."

We are going to discuss a scheme invented by van Heyst and Pedersen [240]. Their scheme can be used to sign a single message and verify the signature many times.

van Heyst-Pedersen signature

Initialization: The security of the scheme is based on intractability of discrete logarithm. This stage is done jointly by a trusted third party (TTP) and the signer (Sally). The TTP chooses a prime modulus p (p 1 = 2q where q is prime), an element g 2 Zp of order q and a random integer r 2 Zq . Next it computes R = gr and sends (p; q; g; R) to Sally while r is kept secret by the TTP.

Sally chooses at random x = (a1; a2; b1; b2) 2 Zq5 and computes:

302 7 DIGITAL SIGNATURES

Next she sends K = (g; p; R; A; B) to the public registry while x is kept secret by Sally.

Signing: For a message m, Sally produces s = SGx(m) = ( 1; 2)

Veri cation: Victor takes the signature s~ = ( 1; 2), message m~ , and the public key K and checks whether

Proof of forgery: Sally gets a forged signature s0 = ( 10 ; 20 ) on message m. Then she computes

P ROOF (s0) ( 1 10 )( 20 2) 1 (mod q)

where s = ( 1; 2) is the original signature for m. After the proof is generated the scheme is no longer used.

Theorem 30. Let Oscar have an unlimited computational power. Then public information K = (g; p; R; A; B) and the signature s = ( 1; 2) on a mes-

The system can be rewritten as

ing discrete logarithm instance. The coeÆcient matrix in the system has rank three { it means that Oscar deals with q possible solutions. tu

Theorem 31. Let s = ( 1; 2) be a signature on m and s0 = ( 10 ; 20 ) on a message m0 (m 6= m0). Then there is a single solution for (a1; a2; b1; b2).

Proof. As before we can get the following system of linear equations over GF (q):

This time the coeÆcient matrix has rank 4 and the system has a single solution.

ut

and concludes our proof. ut

304 7 DIGITAL SIGNATURES

Take a simple example. Sally sets up the scheme for p = 9743 with q = 4871. A primitive element of GF (9743) is e = 5 so g = 52 = 25. Let r = 3176, then R = gr = 5052. Further she chooses four random integers from Zq so

a1 = 1953; a2 = 2711; b1 = 3998; b2 = 833:

The public A = 25195350522711 4299 (mod 9743) and B = 2539985052833 6058 (mod 9743). For a message m = 2164, Sally computes s = ( 1; 2) =

(2729; 3053). Victor takes message, signature and Sally's public information and checks whether ABm = 4299 60582164 7528 (mod 9743) is equal to g 1 R 2 = 25272950523053 7528 (mod 9743). Indeed the expressions are equal

so the signature on the message is authentic.

Let Sally be given a forged signature s0 = (1179; 1529) on the message

m = 2164. Note that the signature passes the veri cation test as g 10 R 20 = 25117950521529 7528 (mod 9743). Sally should now be able to compute her

secret key

(2729 1179)(1529 3053) 1 3176 (mod 4871):

This constitutes the proof that someone powerful enough has attacked the scheme.

7.8 Timestamping

In practice, legal documents must have clear timestamps to be legally valid. This applies especially when the documents are related to patents, copyrights, and in general, to cases where the time is an important factor to make a legal or other judgement. Without timestamps, digital signatures can be subject to manipulations either by Oscar or Sally. A simple example of such manipulation is replay attack when an original message is repeated by an opponent. Timestamps provide

{The time when the document was seen, signed or processed. In this case, timestamps indicate the unique time intervals (time of the day, day, month and year).

{The logical time when the document was processed in the context of processing order of other documents. Logical clock provides integers that can be used to recover the correct order of messages processed. A logical clock can be

implemented as a long enough counter that is incremented (or decremented) after processing each document.

{The unique label that can be attached to a document so the receiver always accepts only documents with di erent labels. Labels can be implemented using truly random number generators or pseudorandom number generators. Labels are also called nouns.

Obviously, the above mentioned classes of timestamps have di erent characteristics. The rst class of timestamps indicates the precise point of time when the message was handled. These timestamps are generated from local clocks. Clearly, in distributed environment with many local (usually not synchronized) clocks it is diÆcult to compare two timestamps from two di erent local clocks.

The second class of timestamps gets around the problem of synchronization by using a single logical clock which is used to mark the correct processing order of documents. In this case all documents have to be handled by a single centre or alternatively a distributed handler of a document has to apply for a timestamp to the centre where the logical clock resides.

The third class of timestamps provides the receiver with a noun that can be used to detect copies of a document. Only the rst occurrence of message with a noun is considered to be legal. All other copies are discarded. A random selection of a noun from a large enough population of integers is enough to guarantee with a high probability that a given document will never be assigned the same timestamp. This method of timestamping is very popular in distributed environments. It does not require synchronization. The uniqueness of timestamp hinges on a probabilistic argument. Nouns provide a convenient tool to distinguish the past from the present, which is suÆcient to detect replay attacks.

7.9 Problems and Exercises

1.Let the Rabin signature be produced using the DES encryption algorithm. Discuss the following points:

{What is the length of signatures for messages m 2 64 and the parameter r = 80?

{What is the probability that all keys will be revealed by the signer after ` independent veri cations (veri ers select independently and randomly ` 2r-bit sequences)?

2.Consider the Lamport signature which allows to sign n-bit messages. The signature is the sequence of n secret keys corresponding to the particular pattern of bits in the message.

306 7 DIGITAL SIGNATURES

Suppose that the signer was careless and signed two di erent messages using the same key setting. Show how the opponent, Oscar, can use the two signatures to sign other (forged) messages.

3.Take an instance of the RSA signature scheme with p = 839, q = 983 and N = p q = 824737. Assume that the secret key is e = 132111. Compute the public key d and sign the message m = 23547.

4.Assume that signatures are produced using the RSA scheme with the modulus N = 824737 and the public key d = 26959.

{Recover the message m from the signature s = 8798.

{Is the pair (m; s) = (167058; 366314) valid?

{Knowing two pairs (m; s) = (629489; 445587) and (m0; s0) = (203821; 229149), compute the signatures for m m0.

5.Given an instance of the ElGamal signature scheme for the modulus p = 45707, the primitive element g = 41382,

{Sign the message m = 12705 for the secret key k = 38416 and the random r = 3169.

{Verify the triple (m; x; y) = (12705; 16884; 13633).

6.Show how Oscar can break the ElGamal signature if Sally has produced two signatures for two di erent messages using the same random integer r.

7.Consider an instance of the DSS scheme for the following parameters: the modulus p = 35023 with q = 449 and an integer g = 4781 (a qth root of 1 modulo p).

{Compute the signature for the message m = 401 provided k = 277 and r = 168.

{ Verify whether s = (x; y) = (262; 266) is a signature of m = 401 for gk = 24937.

8.Given an instance of the RSA blind signature. The public parameters of the signer are the modulus N = 17869 and the public key d = 10117.

{What is the secret key if you know that p = 107 and q = 167?

{Compute the blinded message c m rd mod N for m = 17040 and r = 5593, sign the blinded message c and extract the signature s mk mod N from c.

{Verify whether s = 13369 is the signature of m = 17040.

10.Suppose that Henry (the holder of messages) wishes to obtain RSA blind signatures for a

sequence of messages (m1; : : : ; mn) where mi 2 ZN . What are security implications when Henry uses the same blinding integer r for all messages (instead of the prescribed random integer r selected independently for each message mi)?

11.Consider an instance of the Chaum-van Antwerpen signature for p = 1019, q = 509, g = 475, k = 200 and K = 807 gk mod p.

{Sign the message m = 555.

{Assuming that the message m = 555 and its signature is s = 842, verify the pair. Generate a challenge c for the random pair (a; b) = (20; 411) and produce a suitable response.

8 AUTHENTICATION

Authentication is one of basic cryptographic techniques. Its aim is to provide a receiver with some kind of a proof that the information comes from the intended sender. In this chapter we are going to discuss authentication whose security is unconditional, i.e. its security is independent of the computational power of a potential attacker. Simmons wrote a good review on the subject in [476]. Stinson treated authentication in Chapter 10 of his book [497].

8.1 Active Opponents

Authentication systems involve three active parties: the sender (Alice), the receiver (Bob), and the opponent (Oscar). Alice transmits messages to Bob using a communication channel. The opponent, Oscar, controls the channel. Recall that in secrecy systems, Oscar is assumed to eavesdrop the conversation between Alice and Bob. He is a passive attacker who does not modify the stream of cryptograms sent over the channel. It is not diÆcult to realize that once Oscar has gained the control over the channel, he may become \active." Active opponents interfere with the contents of cryptograms transmitted via the channel. Here is the list of threats which may be launched by an active attacker:

1.Impersonation attack { Oscar initiates a communication with Bob by sending a forged cryptogram trying to convince Bob that the cryptogram has come from Alice.

2.Substitution attack { Oscar intercepts a cryptogram sent by Alice and replaces it by a di erent cryptogram which is subsequently transmitted to Bob. Again, Oscar tries to deceive Bob by pretending that the forged cryptogram comes from Alice.

308 8 AUTHENTICATION

3.Spoo ng attack { Oscar observes r di erent valid cryptograms sent by Alice and forms a forged cryptogram hoping that the cryptogram will be accepted by Bob as a valid one. This attack is also called spoo ng of order r.

Authentication is used to thwart the above threats. Being more speci c, we are going to investigate authentication systems which enable Bob to detect Oscar's attacks listed above with an overwhelming probability. Note that authentication systems which we are going to consider in this chapter, do not allow Bob to detect other possible active attacks such as replay of valid cryptograms, interference with the order of the transmitted valid cryptograms, duplication of one or more valid cryptograms, deletion of one or more valid cryptograms, delay of transmission, etc.

Because of the similarity between secrecy and authentication systems, there may be a temptation to use encryption for authentication. Assume that a message source (Alice) generates 64-bit messages and each message occurs with the probability 2 64. Further, let the DES be used for encryption in the electronic codebook mode. The cryptographic key is known to Alice and Bob only. Cryptograms are conveyed via the channel to Bob who decrypts them. Oscar obviously does not know the cryptographic key but can launch either an impersonation, substitution, or spoo ng attack. Clearly, Oscar will be successful in any of these attacks { it is enough for him to choose a cryptogram at random and communicate it to Bob. Bob decrypts it and has to accept it as a genuine one! Oscar has attained his goal although he does not know the message that corresponds to the forged cryptogram.

The above scheme can be salvaged if Alice introduces a redundancy to the message source. Given the message source, which generates 64-bit messages, assume that only 232 messages are meaningful. The rest 264 232 messages are meaningless. The meaningful messages occur with the uniform probability. The meaningless messages never occur. Now Oscar faces a harder task. If he applies the same strategy, that is, the random selection of a fraudulent cryptogram from the set of 264 elements, the probability of Oscar's success is 2 32. On the other hand, Bob detects with the probability 1 2 32 that Oscar cheats.

8.2 Model of Authentication Systems

The authentication theory emerged in late 1970's as a parallel branch to Shannon's theory of secrecy systems. The model described here follows Simmons' authentication model [478] and deals with authentication without secrecy. The

set of all source states (messages) generated by the message source is S. The set of all codewords (cryptograms) is denoted by M. The set of all encoding rules (keys) is E. The set of all authentication tags is T .

An authentication code or A-code is the collection hS; M; Ei such that for each source state s 2 S, an encoding rule e 2 E assigns a tag t 2 T or simply t = e(s). The cryptogram m = (s; t) so M = S T . Denote also j S j= S, j E j= E, j M j= M and j T j= T . A-codes with M = S T are also called

Cartesian A-codes.

The authentication system described in Figure 8.1 works as follows. First, Alice and Bob agree on the encoding rule e 2 E they are going to use. The rule is kept secret by the two parties. Let Alice want to send a message (state) s 2 S to Bob. She computes the tag t = e(s) and sends the cryptogram m = (s; t) to Bob via the insecure channel. Bob takes m0 = (s0; t0), which may be modi ed during

transmission, computes his tag t00 = e(s0) using the message s0 and accepts the message s0 only if t00 = t0.

As the cryptograms are pairs of a clear message and a tag, Oscar can successfully attack the system if he nds the correct tag for a false message. Note that in the impersonation attack, Oscar knows the A-code only. His knowledge increases in the substitution attack as he additionally sees a single valid cryp-

310 8 AUTHENTICATION

EnS s1 s2

e1 0 0

e2 1 0

e3 0 1

e4 1 1

Table 8.1. Authentication matrix

togram. In the spoo ng of order r, Oscar knows the A-code and r distinct valid cryptograms. In all these attacks, Oscar's goal is to form a valid cryptogram (or tag) for a false message.

An A-code can be equivalently represented by an authentication matrix B = [bij] with E rows and S columns. Rows are indexed by encoding rules. Columns are labelled by source states (messages). The entry in the intersection of the row e and the column s contains the tag t = e(s). The corresponding cryptogram is m = (s; t).

Consider an A-code with E = fe1; e2; e3; e4g, S = fs1; s2g and T = f0; 1g. Clearly M = fm1; m2; m3; m4g with m1 = (s1; 0), m2 = (s1; 1), m3 = (s2; 0), m4 = (s2; 1). The authentication matrix is presented in Table 8.1.

8.2.1 Elements of the Theory of Games

The theory of games [40],[272] investigates possible game strategies for two competing players A and B. Each player can make their move independently. For the player A, the collections of moves is X and for B { the set Y. The cardinality of sets X and Y are n1 and n2, respectively. For every pair (x; y); x 2 X, y 2 Y, there is a value g(x; y) which characterizes how much the player A wins or equivalently how much the player B loses. The matrix G = [gxy] is the matrix of the game.

The game processes as follows: The player A selects a row x of the matrix G while B (at the same time) chooses a column y. The value gxy is the gain of A (or the loss of B). Assume that the player A wants to gain as much as possible. If A is prudent he may rst compute the smallest entry in each row and select the one that gives the biggest gain, that is, the row with the gain at least: