Cryptography: Theory and Practice:Identification Schemes

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


Chapter 9
Identification Schemes

9.1 Introduction

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” one’s identity. Some typical scenarios are as follows:

1.  To withdraw money from an automated teller machine (or ATM), we use a card together with a four-digit personal identification number (PIN).
2.  To charge purchases over the telephone to a credit card, all that is necessary is a credit card number (and the expiry date).
3.  To charge long-distance telephone calls (using a calling card), one requires only a telephone number together with a four-digit PIN.
4.  To do a remote login to a computer over a network, it suffices to know a valid user name and the corresponding password.

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 card’s 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 Bob’s 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.

9.2 The Schnorr Identification Scheme

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:

1.  p is a large prime (i.e., p ≥ 2 512) such that the discrete log problem in is intractible.
2.  q is a large prime divisor of p - 1 (i.e., q ≥ 2 140).
3.   has order q (such an α can be computed as the (p - 1)/qth power of a primitive element).
4.  A security parameter t such that q > 2t. For most practical applications, t = 40 will provide adequate security.
5.  The TA also establishes a secure signature scheme with a secret signing algorithm sigTA and a public verification algorithm verTA.
6.  A secure hash function is specified. As usual, all information is to be hashed before it is signed. In order to make the protocols easier to read, we will omit the hashing steps from the descriptions of the protocols.

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 Bob’s 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net