# Your protocols must use timestamp and encrypt and sign

228SIMPLE AUTHENTICATION PROTOCOLS

The Fiat-Shamir protocol, as illustrated in Figure 9.32, proceeds as follows. Alice selects a random

r, and she sendsx=r2modNto Bob. Bob then chooses a random valuee∈ {0,1}, which he sends to Alice. In the third message, Alice responds withy=rSemodNand Bob then verifies that

*y*2= *xve*mod *N*

and *equation 9.1* becomes If *e* = 0 in Fiat-Shamir,
thenAlice responds in the third message with *y* = *r* mod
*N*

*y*2= *r*2= *x* mod *N.*

Suppose Trudy expects Bob to send the challenge

e= 0 in message two. Then Trudy can sendx=r2modNin message one andy=rmodNin message three. In other words, Trudy simply follows the protocol in this case, since she does not need to know the secretS.On the other hand, if Trudy expects Bob to send

e= 1, then she can sendx=r2v−1modNin message one andy=rmodNin message three. Then Bob will com-putey2=r2andxve=r2v−1v=r2and he will find thatequation 9.1holds, and he will accept the result as valid. But if Bob choosese∈ {0,1}at random (as required by the protocol), then Trudy can only fool Bob with probability1 2. And, as with Bob’s Cave, afterniterations, the probability that Trudy can fool Bob is only(1 2)n.

Asignificantadvantageofzeroknowledgeproofsisthattheyallowforauthentication with anonymity. In Fiat-Shamir, both sides must know the public value

v, but there is nothing invthat identifies Alice, and there is nothing in the messages that are passed that must identify Alice. This is a significant advantage that has led Microsoft to include support for zero knowledge proofs in its “next generation secure computing base,” or

230SIMPLE AUTHENTICATION PROTOCOLS

• What delay is tolerable?

• What type of crypto is supported—public key, symmetric key, or hash functions?• Is mutual authentication required?

9.7SUMMARYIn this chapter we discussed several different ways to authenticate and establish a session key over a network. We can accomplish these feats using symmetric keys, public keys, or hash functions. We also learned how to achieve perfect forward secrecy, and we considered the benefits (and potential drawbacks) of using timestamps.

3.Provide a way to achieve perfect forward secrecy that does not use Diffie-Hellman.

4.The insecure protocol in Figure 9.24 was modified to be secure in Figure 9.26. Find two other ways to slightly modify the protocol in Figure 9.24 so that the resulting protocol is secure. Your protocols must use a timestamp and “encrypt and sign.”

“I’m Alice”, R

E(R, KAB)

8.What is the primary advantage of using timestamps in an authentication protocol. What is the primary disadvantage of using timestamps?

9.Consider the following protocol, whereK=h(S, RA, RB)and CLNT and SRVR are constants:

a. Does Alice authenticate Bob? Why or why not?

b. Does Bob authenticate Alice? Why or why not?

Alice | E(SRVR, K) | Bob |
---|

**232** SIMPLE AUTHENTICATION PROTOCOLS

[T + 1]Bob, {K}Alice

Alice Bob

[RB]Bob

{S}Bob, E(RA, K)

{RA, RB}Alice

E(RB, K)