Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Cryptographic methods enable many seemingly impossible problems to be solved. One such problem is the construction of secure identification schemes. There are many common, everyday situations where it is necessary to electronically prove ones identity. Some typical scenarios are as follows:
In practice, these types of schemes are not usually implemented in a secure way. In the protocols performed over the telephone, any eavesdropper can use the identifying information for their own purposes. This could include the person who is the recipient of the information; many credit card scams operate in this way. An ATM card is somewhat more secure, but there are still weaknesses. For example, someone monitoring the communication line can obtain all the information encoded on the cards magnetic strip, as well as the PIN. This could allow an imposter to gain access to a bank account. Finally, remote computer login is a serious problem due to the fact that user IDs and passwords are transmitted over the network in unencrypted form. Thus they are vulnerable to anyone who is monitoring the computer network.
The goal of an identification scheme is that someone listening in as Alice identifies herself to Bob, say, should not subsequently be able to misrepresent herself as Alice. Furthermore, we should try to guard against the possibility that Bob himself might try to impersonate Alice after she has identified herself to him. In other words, Alice wants to be able to prove her identity electronically without giving away her identifying information.
Figure 9.1 Challenge-and-response protocol
Several such identification schemes have been discovered. One practical objective is to find a scheme that is simple enough that it can be implemented on a smart card, which is essentially a credit card equipped with a chip that can perform arithmetic computations. Hence, both the amount of computation and the memory requirements should be kept as small as possible. Such a card would be a more secure alternative to current ATM cards. However, it is important to note that the extra security pertains to someone monitoring the communication line. Since it is the card that is proving its identity, we have no extra protection against a lost card. It would still be necessary to include a PIN in order to establish that it is the real owner of the card who is initiating the identification protocol.
In later sections, we will describe some of the more popular identification schemes. But first, we give a very simple scheme that can be based on any private-key cryptosystem, e.g., DES. The protocol, which is described in Figure 9.1, is called a challenge-and-response protocol. In it, we assume that Alice is identifying herself to Bob, and Alice and Bob share a common secret key, K, which specifies an encryption function eK.
We illustrate this protocol with a small example.
Example 9.1
Alice and Bob use an encryption function which does a modular exponentiation:
Suppose Bobs challenge is x = 77835. Then Alice responds with y = 100369.
Virtually all identification schemes are challenge-and-response protocols, but the most useful schemes do not require shared keys. This idea will be pursued in the remainder of the chapter.
We begin by describing the Schnorr Identification Scheme, which is one of the most attractive practical identification schemes. The scheme requires a trusted authority, which we denote by TA. The TA will choose parameters for the scheme as follows:
The parameters p, q, and α, the public verification algorithm verTA and the hash function are all made public.
A certificate will be issued to Alice by the TA. When Alice wants to obtain a certificate from the TA, the steps in Figure 9.2 are carried out. At a later time, when Alice wants to prove her identity to Bob, say, the protocol of Figure 9.3 is executed.
As mentioned above, t is a security parameter. Its purpose is to prevent an impostor posing as Alice, say Olga, from guessing Bobs challenge, r. For, if Olga guessed the correct value of r, she could choose any value for y and compute
She would give Bob γ in step 1, and then when she receives the challenge r, she would supply the value y she has already chosen. Then γ would be verified by Bob in step 6.
Figure 9.2 Issuing a certificate to Alice
The probability that Olga will guess the value of r correctly is 2-t if r is chosen at random by Bob. Thus, t = 40 should be a reasonable value for most applications. (But notice that Bob should choose his challenge r at random every time Alice identifies herself to him. If Bob always used the same challenge r, then Olga could impersonate Alice by the method described above.)
Previous | Table of Contents | Next |
Copyright © CRC Press LLC