United States Patent [191
`Brown
`
`ll?llllllllllllllllllllilllllilllllillillllllillllilllillillllillli
`
`USOO5740361A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,740,361
`Apr. 14, 1998
`
`[54] SYSTEM FOR REMOTE PASS-PHRASE
`AUTHENTICATION
`[75] Inventor: Gary S. Brown. Columbus, Ohio
`
`Bird. et aL. Systematic Design of a Family ofAttack-Resis
`rant Authentication Protocols, Sep. 1992. pp. 1-26.
`21143338383; Kgplioags‘ight Authenncaao" and Key D18?"
`
`[73] Assignee: CompuServe Incorporated, Columbus.
`Ohio
`
`Primary Examiner-—Robert B. Harrell
`Attorney, Agent, or Firm-Standley & Gilcrest
`
`Jun‘ 3’ 1996
`[22] F??d:
`[51] rm. Cl.6 .................................................... .. G06F 12/14
`[52] us. 61. ....................................................... .. 39s/1s7.o1
`[58] Field of Search ..................... .. 364/DIG. 1 MS File.
`364/DIG_ 2 MS File; 380/4“ 2 1_ 23_ 46_
`49; 395,6OL 609_ 761_ 762 186‘ 187_01_
`183.01. 200‘3_ 20033
`
`[56]
`
`References Cited
`
`Us PATENT DOCUMENTS
`7/1996 Ganesan .................................. .. 380/25
`8/1996 Geus ________ __
`2/1997 Aziz _____ __
`6/1997 Nguyen ................................... .. 380/29
`
`5,535,276
`5,550,934
`5,604,303
`5,638,448
`
`UI‘HER PUBLICATIONS
`
`Dave Raggett. Internet Draft. Mediated Digest Authentica
`lion, Mar. 1995. pp. 1-12.
`Bird. et al.. A Modular Family of Secure Protocols for
`Authentication and Key Distribution, Nov. 1992. pp. 1-15.
`
`A system and method are disclosed for authenticating users
`and services communicating over an insecure network Each
`user and Service has a Pass-Phrase used for authentication
`H°W°v°r~ ‘11° Pass-Phrases are 11°‘ "vealed during ‘ha
`authentication process as challenge-response techniques are
`used to keep the pass-phrase secret. In addition. the users
`and services do not need to know nor do they learn each
`other‘s pass-phrases making the process useful in a distrib
`uted environment. Pass-phrases are known by an authenti
`cation entity with which the service communicates to
`authenticate both users and services. Users may have iden
`titles in and scrviccs may Support a number °frea1ms~ “ch
`of which may be viewed as large collection of users (e.g..
`CompuServe.com). Users choose the realm in which they
`would like to be authenticated In one embodiment of the
`present invention. the system and method are adapted for use
`with the Hyper’I‘ext Transfer Protocol of the World Wide
`Web so that secure transactions may be accomplished
`between users and services communicating via the Internet.
`
`26 Claims, 3 Drawing Sheets
`
`User
`1
`
`Uger
`
`Authentication Deity I
`compuservacom
`
`16
`
`12
`
`44
`
`Network
`N d 0 e \ Server
`
`Computer
`Network 10
`
`46
`
`32
`
`Authentication Deity II
`aol. com
`
`18
`
`20
`
`Service
`A
`
`22
`
`Service
`B
`
`1
`
`USAA 1035
`
`

`
`U.S. Patent
`
`Apr. 14, 1998
`
`Sheet 1 of 3
`
`5,740,361
`
`User
`1
`
`Uger
`
`Authentication Deity I
`compuservacom
`
`16
`
`12
`
`44
`
`Network 24
`Node \ Server
`
`Computer
`Network 10
`
`46
`
`Authentication Deity II
`aoLcom
`
`18
`
`Figure 1
`
`20
`
`Service
`A
`
`22
`
`Service
`B
`
`2
`
`

`
`&U
`
`47.,
`
`1M
`
`|.I...||IY$M3.50mmuoom.8HmoscommeP:o:mo::o£:<uo_>._omBD
`
`
`EfiomAEmE_«8mo853%mIIII.
`
`2.5:838$2cocoflom
`
`
`
`
`
`M.’moowcozmnoEowcmmm|..--......V€A:2
`
`slIl|u||l.||l||wEo
`
`
`
`:0ow=o=_£uEoucmm
`
`
`
`ExExflooim3.3%.&.=v~$8.conmomEV8532
`
` co.§o.:=o£:<HE.u|lnIn|u|VM.atamM60SD52.22:2$252:o:mo.a=o£:<%QI
`
`amomcommomA5»
`
`0.,No.:.w_,m
`
`5Exmooi32$>3coawom
`
`IM:
`
`3
`
`

`
`US. Patent
`
`Apr. 14, 1998
`
`Sheet 3 of 3
`
`5,740,361
`
`$8.6m 6M3
`
`
`
`MU omcuzmso 525mm
`
`
`
`=0 owco=mso Eowcmm A Q
`
`a“ umcoawum
`
`A 3
`
`mm ammonium
`
`1%
`
`Y3
`
`2.5“;
`
`4
`
`

`
`5,740,361
`
`2
`with a service that wishes to learn and authenticate the user's
`identity and vice versa. To clarify the problem. there are
`three aspects of network security that may be distinguished:
`
`1
`SYSTEM FOR REMOTE PASS-PHRASE
`AUTHENTICATION
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to authentication of com
`puter users and services in distributed environments.
`Particularly. the present invention relates to a Remote Pass
`phrase Authentication scheme that provides a way to authen
`ticate users and services using a pas s-phrase over a computer
`network without revealing the pass-phrase.
`2. Description of the Related Art
`The importance of secure communication is increasing as
`world-wide networks such as the Interact and the World
`Wide Web (WWW) portion of the Internet expand. As global
`networks expand through the interconnection of existing
`networks. users may gain access to an unprecedented amber
`of services. The services. each of which may be maintained
`by a dilferent provider. give users access to academic.
`business. consumer. government. etc. information. Service
`providers are now able to make their services available to an
`ever-expanding user base.
`The ease with which services and users are able to ?nd
`each other and the convenience associated with on-line
`transactions is leading to an increase in the number of
`remote business and related transactions. However. users
`and services are not always certain who or what is at the
`other end of a transaction. Therefore. before they engage in
`business and other transactions. users and services want and
`need reassurance that each entity with whom they commu
`nicate is who or what it purports to be. For example. users
`will not be willing to make on-line purchases that require
`them to reveal their credit card nunmers unless they are
`con?dent that the service with which they are communicat—
`ing is in fact the service they wanted to access. Commercial
`and other private entities who provide on-line services may
`be more reluctant than individuals to conduct business
`on-line unless they are con?dent the communication is with
`the desired individual or service.
`Both users and services need reassurance that neither will
`compromise the integrity of the other nor that con?dential
`information will be revealed unintentionally to third parties
`while communications are occurring. Security in a global
`network. however. may be di?icult to achieve for sevm'al
`reasons. First. the connections between remote users and
`services are dynamic. With the use of portable devices. users
`may change their remote physical locations frequently. The
`individual networks that comprise the global networks have
`many entry and exit points. Also. packet switching tech
`niques used in global networks result in numerous dynamic
`paths that are established between participating entities in
`order to achieve reliable cormnunication between two par
`ties. Finally. communication is often accomplished via
`inherently insecure facilities such as the public telephone
`network and many private communication facilities. Secure
`communication is dil?cult to achieve in such distributed
`environments because security breaches may occur at the
`remote user’s site. at the service computer site. or along the
`communication link. Consequently. reliable two-way
`authentication of users and the services is essential for
`achieving security in a distributed environment.
`Two-way authentication schemes generally involve hand
`shaking techniques so that each party may verify he or she
`is in communication with the desired party regardless of
`each party’s location or the types of devices in use. The
`problem to be solved is one in which a user communicates
`
`5
`
`Identi?cation:
`
`Authentication:
`
`Authorization:
`
`10
`
`the way in which a user or service is
`referenced
`the way in which a user may prove his or her
`identity.
`a method for determining what a given user
`may do. The same aspects apply to services
`as well as users.
`
`2 O
`
`35
`
`Identi?cation
`A user’s identity consists of a user name and a realm
`15 name. A realm is a universe of identities. CompuServe
`Information Service (C15) user IDs and America Online
`(AOL) screen names are two examples of realms. The
`combination of user name and realm—typically shown as
`name@realm—identi?es a user. Any given service recog
`nizes some particular set of identities. Arealrn does not have
`to be large. though. either in number of users or size of
`service. For example. a single WWW server may have its
`own realm of users.
`Often. a service recognizes only one realm: CIS recog
`nizes only identities within the CIS realm and AOL recog
`25 nizes only identities within the AOL realm. But. one can
`imagine a service that has agreements with both CIS and
`AOL. The service gives the user a choice of realms
`“Please supply a C18 or AOL identity. and prove it"—and
`the user chooses a realm in which he or she has an identity.
`3'0 Identi?cation. thus. provides the ability to identify. or to
`refer to. a user.
`Authentication
`Authentication provides the ability to prove identity.
`When asking to do something for which a user’s identity
`matters. the user may be asked for his or her identity-—a user
`name and realm-and the service requires the user to prove
`that he is who he says he is. To accomplish this. most
`services use a secret called a pass-phrase. although it is not
`necessarily derived from text. Such a secret is sometimes
`called a secret key. but it is not necessarily used for encryp
`tion. In this context. the fundamental problem to be solved
`is: How can a user prove his pass-phrase without revealing
`the pass-phrase in the process?
`Authorization
`Authorization refers to the process of determining
`whether a given user is allowed to do something. For
`example. may he post a message? May he use a surcharged
`service? It is important to realize that authentication and
`authorization are distinct processes-one related to proving
`an identity and the other related to the properties of an
`identity. The present invention is not related to
`authorization. but it is designed to co-exist with authoriza
`tion mechanisms.
`Pass-phrase
`A service that wishes to authenticate a user requires the
`user to identify himself or herself and to prove that he or she
`knows the pass-phrase. Generally. the service prompts the
`user for the pass-phrase. However. transmitting the plain text
`60 pass-phrases through a network comprises secmity because
`an eavesdropper may learn the pass-phrase as it travels
`through the network. X.25 networks have been
`compromised. and LANs. modem pools. and "The Internet”
`likewise are not suitable for plain text pass-phrases due to
`the eavesdropper problem. Prompting for the pass-phrase.
`while su?icient in the past. no longer works for extensive
`world-wide networks.
`
`40
`
`45
`
`50
`
`55
`
`5
`
`

`
`3
`
`5,740,361
`
`25
`
`Pass-phrase Encryption
`Encryption of the pass-phrase provides additional security
`and addresses the eavesdropper problem. Using encryption.
`the user encrypts the pass-phrase. sends the result to the
`service which then decrypts it. Some techniques are based
`on a one-time key that prevents an eavesdropper from
`decrypting the pass-phrase.
`There are. however. problems with this technique as well.
`Somebody else-a spoofer-may pretend to be the service.
`The spoofer decrypts the result. learns the pass-phrase. and
`gains the ability to masquerade as the user. Some people
`have spoofed services by getting users to dial into the
`spoofer’s computer. The spooler advertises a dial up number
`for the service that is claimed to have been omitted from the
`directory of service numbers. The spoofer may entice people
`to try the “unlisted” number by claiming it is much faster
`than the listed numbers. Therefore. there is a need for a
`mechanism that will not reveal the pass-phrase to anyone.
`even if the user is interacting with a spooler.
`Challenge-response Techniques
`Challenge-response techniques involve a series of
`exchanges between a user and a service. The service sends
`the user a challenge. which is a random number. and the user
`applies a one-way function to the number to calculate a
`result that depends on the challenge and the user's pass
`phrase. The user sends the result to the service which
`performs the same calculation and compares the result to the
`result sent by the user. Done correctly. this technique reveals
`no information to eavesdroppers. nor does it allow a spoofer
`to acquire the pass-phrase-if a spoofer pretends to be the
`service. he learns the result only for a particular challenge
`which is of no value. Although such a technique works. it
`does not solve the problem completely. The service must
`know the pass-phrase in order to reproduce the user’s
`calculation and verify the user’s response to the service’s
`challenge.
`The service may not know the user’s pass-phrase for
`several reasons. A set of services may share a set of users’
`identities. For example. a collection of Web servers. scat
`tered throughout the world. may be part of a "Total Infor
`mation Service (TIS).” A user requesting access to TIS may
`use her TIS user name and pass-phrase to identify herself to
`any TIS service. In accordance with one implementation.
`each physical server may have a copy of all pass-phrases or
`access to a master database containing all pass-phrases. This
`solution may not. however. work under all scenarios
`especially if some are third-party servers. not directly under
`the control of the imaginary 118. Or consider a service that
`accepts identities in multiple realms-for example. a service
`that has agreements with both CIS and AOL. The service
`gives the user a choice of realms-—“Please supply a C15 or
`AOL identity. and prove it”—and the user chooses a realm
`in which he has an identity. It is unlikely that CIS and AOL
`will entrust a copy of their pass-phrase databases to a
`55
`third-party service. or to each other. If the service does not
`how the user’s pass-phrase. then the user cannot prove to the
`service that he knows it
`One technique to address this problem is to have the
`service prompt the user for her pass-phase. For example. a
`WWW service may display a Hyper-Text Markup Language
`(HTML) form with two boxes-one that asks for the user for
`her user name and one that asks her for her pass-phrase. A
`protocol such as SSL or SH'ITP may be used so an eaves
`dropper cannot see it. When the service receives the user‘s
`reply. the service may use a challenge-response technique to
`verify the pass-phrase with a server that knows the pass
`
`4
`phrases. But. there is a drawback to this technique. It is
`important to teach a user not to type his or her pass-phrase
`just because somebody asks for it. This technique is com
`monly used for cracking others’ accounts. Teaching users to
`provide their pass-phrases in a HTML form is not a desirable
`solution because the pass-phrase is revealed. which is pre
`cisely what should be avoided. especially if the service is a
`spoofer.
`The pass-phrase database server also has some undesir
`able side effects. Using this scheme. the service asks the user
`for a copy of her pass-phase. Now. an ordinary challenge
`response technique may be used. However. there is a need to
`get the pass-phrase from that database to the service. safely.
`If the service can look up the pass-phrase. then anybody else
`may do the same. Even worse. the entire pass-phrase data
`base may be accessed so that pass-phrases for many users
`may be obtained.
`Current authentication mechanisms are inadequate for the
`distributed systems. services. and users that comprise
`today’s world-wide networks such as the WWW/Internet.
`Users and services need a way to reliably authenticate one
`another that also meets speci?c design criteria. Users and
`services also have a need for a mechanism that is adaptable
`to the many communication protocols used throughout
`world-wide networks and that is straightforward for users to
`use. These criteria and others are met with the present
`invention.
`
`SUMMARY OF THE INVENTION
`The present invention-Remote Passphrase Authentica
`tion (RPA)—provides a way to authenticate a user to a
`service by using a pass-phrase over an insecure network.
`without revealing the pass-phrase to eavesdroppers. RPA is
`designed so that the service need not know and does not
`learn the user’s pass-phrase. Consequently. RPA is useful in
`distributed environments where it would be dii?cult or
`inappropriate to trust a service with a pass-phrase database
`or to allow the service to learn enough to masquerade as the
`user in a future authentication attempt. In one embodiment
`of the present invention. users and services on the WWW/
`Internet use the mechanism of the present invention to
`authenticate one another.
`Using the present invention. a service may authenticate a
`user and a user may authenticate a service. Authentication is
`accomplished using pass-phrases (which may be derived
`from textual phrases). The goal is to prove to the service that
`the user knows the pass-phrase. and vice versa. Techniques
`are employed to minimize the possibility that the pass
`phrase is revealed to an eavesdropper or a spoofer.
`Using RPA. a "user“ communicates with a “service” that
`wishes to learn and authenticate the user’s identity. An
`authentication “deity” knows the users’ and services‘ pass
`phrases. The service communicates with the authentication
`deity during the authentication process. Ifthe service knows
`the pass-phrases. then it acts as its own deity. simplifying the
`implementation but. otherwise having no effect on the
`mechanism.
`Identities for users exist in a “realm" which may be
`viewed as a relatively large collection of users—such as
`compuservecom or aol.com—but it may well consist of a
`small set of users (e.g.. user names and pass-phrases asso
`ciated with an individual Web server.) The service may
`specify a set of realms so that it may recognize an identity
`in any of the realms in which it participates.
`This authentication mechanism of the present invention
`consists of three related processes: authentication.
`
`20
`
`45
`
`50
`
`65
`
`6
`
`

`
`5
`reauthentication. and reauthentication cheating. Authentica
`tion is the fundamental process by which a usu and a service
`mutually authenticate one another within one of a set of
`realms. without revealing their pass-phrases to one another.
`Reauthentication is a process by which a user and service.
`having recently authenticated one another. may again
`authenticate one another. They may. of course. simply repeat
`the authentication process. but that requires interaction with
`an authentication deity. The reauthentication process is
`faster, requiring no communication with a third party. Reau
`thentication is useful when multiple connections between
`the user and service are established, whether sequential as in
`Hyper-Text Transfer Protocol (HTTP) or simultaneous.
`Preferably. each connection is authenticated. but the reau
`thentication process provides a shortcut.
`Authentication
`Three parties or entities participate in the authentication
`process:
`the user;
`the service; and
`the authentication deity.
`Each user has a user name and a pass-phrase in some
`realm of interest. Similarly. each service has a name and a
`pass-phrase in that realm. The pass-phrase is not text. but is
`instead a 128-bit (l6-octet) string of bits. However. it is
`often useful to use pass-phrases in the conventional. textual
`sense. so a procedure is de?ned for convening a textual
`phrase to the 128-bit value used by the authentication
`mechanism of the present invention.
`The service may specify a list of realms and the usa may
`choose one in which he has an identity. For example. a CIS
`user may choose to be authenticated in the CIS realm. Thus.
`a service is not restricted to authenticating identities in a
`single realm. The service possesses a name and pass-phrase
`in all realms it speci?es.
`Each realm has an authentication deity that knows the
`names and pass-phrases of its members. The service locates
`an authentication deity for each realm. If the service knows
`the user’s pass-phrase. it performs the role of the authenti
`cation deity itself. but this does not alfect the mechanism.
`The primary steps for a preferred embodiment of the present
`invention are as follows:
`The service supplies a sequence of realms. with the
`service’s name in each realm. to the user.
`The user chooses a realm. The chosen realm and the user’s
`name in that realm are communicated to the service.
`The service and user exchange random challenges.
`The user calculates a response and sends it to the service.
`The service calculates a response.
`The service sends a request to the authentication deity for
`the realm in question. The request contains the realm
`name. the user’s name. the service’s name. the user’s
`challenge. the service’s challenge. the user’s response.
`and the service’s response.
`The deity uses the realm. service. and user name to look
`up the user’s and service’s pass-phrases.
`The deity uses the values in the request. plus the service’s
`pass-phrase to verify the service’s response.
`Having veri?ed the requesting service’s identity. the deity
`uses the values in the request. plus the user’s pass
`phrase to verify the user’s response.
`Having veri?ed both the user’s and service’s identity. the
`deity creates a random. 128-bit session key for use by
`the user and service. They may use it for session
`encryption or for the reauthentication process described
`later.
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`5,740,361
`
`6
`The authentication deity generates and sends to the ser
`vice authentication proofs for the service and the user.
`The service veri?es its authentication proof and for
`wards the other authentication proof to the user. The
`user then veri?es its authentication proof.
`
`BRIEF DESCRIPTION OF THE DRAWING(S)
`
`10
`
`FIG. 1 is a system block diagram for a preferred embodi
`ment of the present invention;
`FIG. 2 illustrates an authentication protocol for a pre
`ferred embodiment of the present invention; and
`FIG. 3 illustrates a reauthentication protocol for a pre
`ferred embodiment of the present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODINIENT(S)
`Referring to FIG. 1. a system block diagram for a pre
`ferred embodiment of the present invention is shown. Three
`entities or parties participate in the authentication process of
`the present invention:
`the user 12. 14;
`the service 20. 22; and
`the authentication deity 16. 18.
`The entities communicate with one another via a global
`computer network 10 such as the Internet. In an alternative
`embodiment. the three participating entities may be part of
`a small. domestic computer network. The computer network
`10. which uses a message passing scheme for communica
`tion between entities. may be comprised of network node
`computers 24 that route messages through the network to the
`communicating entities 12. 14. 16. 18. 20. 22. The network
`node computers may rely on servers 26 that access databases
`28 to obtain routing and other information needed to facili
`tate network tra?ic.
`To communicate with one another. each entity establishes
`a connection 40. 42. 44. 46. 48. 50 to the network 10.
`Network connection options for the entities are varied and
`may include a local area network (LAN) or the public
`telephone network via a modem or a dedicated line such as
`a X.25 link or a satellite or ?ber optic link Using addressing
`information provided by the users l2. l4 and services 20. 22.
`the network facilitates communications so that any one
`entity may communicate. either in real time or by leaving
`messages. with another entity on the network. For example.
`User 1 may communicate with Service A 20. Service B 22.
`or User 2 (14). Service B 22 may communicate with Service
`A20 or with either User 12. 14. Although two users and two
`services are shown for simplicity. in reality. millions of users
`and services may communicate with one anotha through the
`computer network 10.
`To use RPA. each user 12. 14 is assigned a user name and
`a pass-phrase in some realm of interest (e.g.. compuserve
`.oom or aoLcom). Similarly. each service 20. 22 has a name
`and a pass-phrase for the realms that it supports. The
`pass-phrase is not text. but is instead a 128-bit (lo-octet)
`string of bits. However. it is often useful to use pass-phrases
`in the conventional. textual sense. so a procedure is de?ned
`for converting a textual phrase to the 128-bit value used by
`the authentication mechanism of the present invention.
`A service may support multiple realms. each of which has
`its own authentication deity 16. 18. By supporting multiple
`realm% a service may be able to increase its user base by
`making itself available to users who have a user name/pass
`phrase in only one realm. User name/pass-phrase and
`servicelpass-phrase pairs used by each authentication deity
`
`7
`
`

`
`5,740,361
`
`7
`2t). 30 that supports a particular realm may be stored in a
`database 30. 32 for retrieval during the authentication pro
`cess. The authentication deity with which a service commu
`nicates to complete the authentication process depends on
`the realms o?ered by the service and the realm selected by
`the user. The service then locates the authentication deity for
`the selected realm If the service knows the user’s pass
`phrase. it performs the role of the authentication deity itself.
`but this does not all‘ect the mechanism.
`The following values are involved in the authentication
`process of the present invention.
`
`: Authentication deity's response to service;
`proves user’s identity
`‘ Autlzntication deity's response to user;
`proves service's identity
`Challerue from service
`Challenge from user
`Sessirm key for user and service
`Session key obscured so visible only to
`service
`Session key obscured so visible only to
`user
`
`Cs:
`Cu:
`Kus:
`Kuss:
`
`Kusw
`
`20
`
`. Realm name
`: Service name
`' User name
`Service's pass-phrase, a 128 bit value
`User's pass-phrase, a 128 bit value
`: Service's response to challenge (during
`authentication process, goes to
`authentication deity; din-Eng
`reauthentication. goes to \EQI')
`: User’s response to challenge (during
`authentication process, goes via service to
`authentication deity; during
`reautheutication, goes to service)
`Padding consisting of 48 octets (384 bits)
`with all bits set to zero
`+: Ooncatentation of octet strings
`xor. Bitwise “Exclusive Or"
`
`Preferably. bit patterns for each value are speci?ed so that
`different implementations may be supported For example.
`one implementation may use ASCII. another EBCDIC. and
`another Unicode for the user name. Another implementation
`may convert the user name to lowercase and another to all
`caps. The ditferent implementations produce different
`results for the same calculation so the authentication may
`fail. The details may be left to underlying protocol. but that
`makes the service-to-deity protocol dependent on the user
`to-service protocol. Using such a scheme makes it di?icult
`to provide a single deity for each realm. By specifying the
`bit patterns. any mixture of user-to-service and service-to
`deity protocols may be used to operate on the same data.
`The following conventions facilitate the development of a
`single deity to support multiple realms. Preferably. text
`strings are represented in the Unicode character set. in
`big-endian byte order. without a trailing null character. Each
`16-bit Unicode character may be stored in two octets. with
`its high-order 8 bits in the ?rst octet. The speci?cation refers
`only to values used in the authentication calculations. not the
`underlying protocol. For example. a protocol may use ASCII
`for user names. if that character set is adequate. The ASCII
`characters may be converted to Unicode before using them
`in authentication calculations. but the protocol need not
`transmit Unicode characters.
`Names-Nr. Ns. Nu—are converted to lowercase Uni
`code.
`Challenges-Cs. Cu-arc arbitrary strings of octets. not
`text. They may contain any bit patterns. including nulls.
`and are preferably. at least eight octets in length.
`
`45
`
`55
`
`65
`
`8
`Pass-phrases—Ps. Pu—are l6-octet quantities that con
`tain arbitrary bit patterns. including nulls. If the pass
`phrase is based on a textual phrase. the textual phrase
`is converted to a 16-octet quantity by the following
`process:
`Convert the text string to a sequence of characters in
`either the Unicode or ISO 8859-1 character sets. as
`appropriate for the realm
`Convert each character to its lowercase equivalent. or
`its uppercase equivalent. or leave it alone. as appro
`priate for the realm.
`Store the sequence of characters in an octet stream.
`with each Unicode character in two consecutive
`octets in big-cndian order. or each ISO 8859-1
`character in one octet.
`Take the MDS digest of the resulting string of octets.
`The result is the 128-bit value to use in the authen
`tication calculations.
`A realm speci?es which of the preceding options—
`character set. case conversion. and hash function-it uses
`for the text-to- l28-bit value transformation. Preferably. the
`defaults are Unicode. convert to lowercase. and MD5. The
`user-service protocol may be designed to convey the appro
`priate options for each realm from the service to the user. if
`other than the defaults are to be supported. to avoid requiring
`the (human) user to manually con?gure software.
`Referring to FIG. 2. the primary steps for a preferred
`embodiment of the present invention are shown.
`The authentication process begins when a user attempts to
`access a service 60.
`In response to the user’s access attempt. the service
`supplies a sequence of realms. with the service‘s name
`in each realm. to the user 62. A user may choose a realm
`in which he has an identity. For example. a CIS user
`may choose to be authenticated in the CIS realm while
`an AOL user may choose to be authenticated in the
`AOL realm. [foo@compuserve.com bar@aol.com may
`mean “Please identify yourself with a CIS user ID. If
`you don't have one. your AOL ID will do.”] Preferably.
`the service indicates its realm preferences in most
`preferred to least-preferred order. By specifying only
`one realm. the service requires identi?cation in that
`realm.
`The user chooses a realm. Nr. and gives it and his name
`in that realm. Nu. to the service 64. That. in turn.
`determines Ns. the service’s name in that realm. Note
`that a protocol may allow the service to include a null
`realm name. meaning “I'll accept you as an anonymous
`user if you wish.” The user may make this choice by
`supplying a null name; then the process stops here. and
`no authentication is performed.
`The service transits a random challenge. Cs 66. The
`challenges are random values that make each authen
`tication unique.
`The user sends a random challenge. Cu 68.
`The user calculates a response. Ru:
`
`The response is sent to the service 70. Only the real user
`may generate the correct response because it depends
`on the user’s pass-phrase. Pu. Generally. user’s pass
`phrase may not be determined from a captured
`response because it’s generated by a one-way func
`tion (although there is the risk of a dictionary attack
`if Pu is based on a poorly chosen pass-phrase.)
`The service calculates a response. Rs:
`
`8
`
`

`
`5,740,361
`
`9
`This response is not sent to the user. It may be seen by
`the user. but the user does not need it.
`The service sends a request to the authentication deity for
`the realm in question 72. The request contains the realm
`name, Nr (included so the same deity may serve more
`than one realm), the user’s name, Nu, the service's
`name, Ns, the user’s challenge. Cu, the service's
`challenge, Cs, the user’s response, Ru, the service's
`response, Rs.
`The deity uses Nr, Ns, and Nu to look up the user’s and
`service's pass-phrases.
`The deity uses the values in the request, plus the service’s
`pass-phrase. P5, to verify Rs. If it is incorrect. the deity
`returns a negative response as this request apparently
`did not come from a legitimate service 74.
`Having veri?ed the requesting service’s identity, the deity
`uses the values in the request. plus the user’s pass
`phrase. Pu. to verify Ru. If it is incorrect, the deity
`returns a failure response to the service as the user does
`not know the correct pass-phrase 74.
`Having veri?ed both the user’s and service’s identity, the
`deity creates a random, 128-bit session key. Kus. for
`use by the user and service. They may use it for session
`encryption. In addition. it may be used in the reauthen
`tication process described later.
`The deity generates two obscured copies of the session
`key:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`10
`ally authenticate without talking to a deity. This technique is
`useful for protocols such as H'I'I‘Pwhich involve a sequence
`of connections that are independent