United States Patent (19)
`Reeds, III et al.
`
`||||||||||||||||
`USOO553919A
`5,153,919
`11
`Patent Number:
`Oct. 6, 1992
`45
`Date of Patent:
`
`(54 SERVICE PROVISION AUTHENTICATION
`PROTOCOL
`75) Inventors: James A. Reeds, III, New
`Providence; Philip A. Treventi,
`Murray Hill, both of N.J.
`73 Assignee: AT&T Bell Laboratories, Murray
`Hill, N.J.
`21 Appl. No.: 759,311
`22 Filed:
`Sep. 13, 1991
`51) Int. Cl. ............................................... HO4L 9/00
`52 U.S. C. ........................................ 380/44; 380/21;
`380/2.3
`58) Field of Search ........................ 380/23, 25, 21, 44
`(56)
`References Cited
`U.S. PATENT DOCUMENTS
`4,555,805 l/1985 Talbot ................................... 380/2.3
`4,658,093 4/987 Hellman ................................ 380/25
`4,811,377 3/1989 Krolopp et al. ...................... 380/2.3
`4,995,083 2/1991 Baker et al. ........................... 380/23
`5,077,790 12/1991 D'Amico et al. ..................... 380/2.3
`Primary Examiner-Salvatore Cangialosi
`Attorney, Agent, or Firm-H. T. Brendzel
`57)
`ABSTRACT
`A protocol for authenticating a cellular telephone to a
`service provider for the purpose of preventing the pi
`
`racy of cellular services. A service provider assigns a
`unique "secret", along with other information such as a
`telephone number, to each cellular telephone when the
`telephone service is established with the service pro
`vider. Each base station of a service provider continu
`ously broadcasts a periodically changing randon num
`ber to all of the cellular telephones within the base
`station's jurisdiction. When a cellular telephone first
`enters the jurisdiction of a base station, it registers itself
`with the base station by concatenating a secret pass
`word and the most recently broadcast random number,
`along with other information, and passing the concate
`nated information to a hash function. The cellular tele
`phone then sends the output of the hash function, along
`with other identifying information to the service pro
`vider. The service provider, upon learning of the cellu
`lar telephone's identity, feeds the secret assigned to that
`cellular telephone and the random number, along with
`other information, into the same hash function. When
`the result of the hashing performed by the service pro
`vider matches that provided by the cellular telephone,
`authentication for that cellular telephone is complete.
`Thereupon, the provider sends the cell a shared secret
`data field which is known to the mobile unit, and subse
`quent authentication processes are carried out between
`the mobile unit and the cell itself.
`
`39 Claims, 7 Drawing Sheets
`
`CONTROLMESSAGE CRYPOTSYSTEM
`
`
`
`Page 1 of 16
`
`PETITIONERS' EXHIBIT 1013
`
`

`

`U.S. Patent
`
`Oct. 6, 1992
`
`Sheet 1 of 7
`
`5,153,919
`
`FIG.
`
`
`
`
`
`PROVIDER 3
`
`PROVIDER 1
`
`
`
`
`
`
`
`
`
`COMMON
`CARRIER
`II
`
`
`
`COMMON
`CARRIER
`I
`
`13
`
`SW
`COMMON
`CARRIER
`
`
`
`
`
`SW
`COMMON
`CARRIER
`
`COMMON
`CARRIER
`I
`
`22
`
`23
`
`PROVIDER 4
`
`
`
`
`
`PROVIDER 3
`
`
`
`
`
`
`
`Page 2 of 16
`
`

`

`U.S. Patent
`
`Oct. 6, 1992
`
`Sheet 2 of 7
`
`5,153,919
`
`FIG. 2
`
`MOBILE UNIT
`HOME CGSA
`-N
`-N
`
`RANDSSD
`ESN
`A-KEY
`
`A-KEY
`ESN
`RANDSSD
`
`JUMBLE
`
`O
`O
`JUMBLE - 49.
`UPDATE ORDER
`(RANDSSD)
`
`SSD-A NEW
`
`SSD-A NEW
`
`SSD-B NEW
`
`O2
`1
`RANDBS
`
`
`
`UMBLE
`
`BASE STATION
`CHALLENGE ORDER
`(RANDBS)
`
`SSD-B NEW
`
`JUMBLE
`
`AUTH
`BASE STATION
`
`
`
`
`
`
`
`104
`
`
`
`AUTHBS is AUTHBS
`
`BASE STATION
`CHALLENGE CONFIRMATION
`(AUTHBS)
`
`SSD UPDATE CONFIRMATION
`(SUCCESS / FAILURE)
`
`Page 3 of 16
`
`

`

`U.S. Patent
`
`Oct. 6, 1992
`
`Sheet 3 of 7
`
`5,153,919
`
`FIG. 3
`
`HOME CGSA
`VISITED CGSA
`MOBILE UNIT
`- ;-N -
`
`RANDSSD
`
`
`
`
`
`
`
`
`
`
`
`
`
`SSD-B NEW
`
`A-KEY
`RANDSSD
`
`UPDATE ORDER
`(RANDSSD)
`
`JUMBLE
`VISITED STATION)
`
`BASE STATION
`CHALLENGE
`ORDER
`(RANDBS)
`
`SSD-B NEW
`
`AUTH
`BASE STATION
`
`
`
`
`
`
`
`
`
`BASE STATION
`CHALLENGE
`CONFIRMATION
`(AUTHBS)
`
`;
`
`
`
`SSD UPDATE CONFIRMATION
`(SUCCESS / FAILURE)
`
`Page 4 of 16
`
`

`

`U.S. Patent
`
`Oct. 6, 1992
`
`Sheet 4 of 7
`
`5,153,919
`
`FIG. 4
`
`RANDSSD
`
`ESN
`
`A-KEY
`
`UMBLE
`
`SSD-A
`
`SSD-B
`
`FIG. 5
`
`ESN
`
`MIN
`
`SSD-A-NEW
`
`JUMBLE
`
`AUTHBS
`
`Page 5 of 16
`
`

`

`U.S. Patent
`
`Oct. 6, 1992
`
`Sheet 5 of 7
`
`5,153,919
`
`FIG. 6
`
`FIG. 7
`
`JUMBLE
`
`AUTH
`
`Page 6 of 16
`
`

`

`U.S. Patent
`
`-Oct. 6, 1992
`
`Sheet 6 of 7
`
`5,153,919
`
`FIG. 8
`
`1 2 3 4----------issDA
`
`3Ol
`
`-----1
`2k
`
`302
`
`JUMBLE
`
`303
`
`MOBILE UNIT
`SPEECH
`
`
`
`
`
`ENCRYPT
`
`
`
`
`
`
`
`
`
`
`
`DECRYPT
`
`BASE STATION
`SPEECH
`
`FIG. 9
`
`JUMBLE
`
`AUTHU
`
`Page 7 of 16
`
`

`

`U.S. Patent
`
`Oct. 6, 1992
`
`Sheet 7 of 7
`
`5,153,919
`
`FIG. 10
`
`CONTROLMESSAGE CRYPOTSYSTEM
`
`SELF-INVERTING
`TRANSFORMATION
`
`
`
`240
`
`
`
`
`
`TRANS/REC
`ELECTRONICS
`
`210
`PROCESSOR
`
`Page 8 of 16
`
`

`

`5
`
`O
`
`40
`
`1.
`
`SERVICE PROVISION AUTHENTICATION
`PROTOCOL
`
`BACKGROUND OF THE INVENTION
`This invention relates to authentication protocols and
`more particularly to protocols for insuring validity of
`communicating radio-telephones and the like.
`In conventional telephony each telephone set (fax
`unit, modem, etc) is physically connected to a unique
`port on a switch at a local central office. The connec
`tion is through a dedicated wire, or through a desig
`nated channel on a dedicated wire. The wire connection
`is installed by the service provider (who, typically, is
`the common carrier) and, therefore, the service pro- 15
`vider can be reasonably sure that transmission on the
`channel arrives from the subscriber. By comparison,
`authentication of a subscriber in wireless telephony is
`less certain.
`Under the current cellular telephony arrangement in 20
`the United States, when a cellular telephone subscriber
`places a call, his or her cellular telephone indicates to
`the service provider the identity of the caller for billing
`purposes. This information is not encrypted. If an inter
`oper eavesdrops at the right time, he or she can obtain 25
`the subscriber's identification information. This in
`cludes the subscriber's phone number and the electronic
`serial number (ESN) of the subscriber's equipment.
`Thereafter, the interioper can program his or her cellu
`lar telephone to impersonate that bona fide subscriber to 30
`fraudulently obtain services. Alternately, an interloper
`can inject himself into an established connection, over
`power the customer's cellular telephone equipment by
`transmitting more power, and redirect the call to his or
`her purposes by sending certain control codes to the 35
`service provider. Basically, such piracy will succeed
`because the service provider has no mechanism for
`independently authenticating the identity of the caller at
`the time the connection is established and/or while the
`connection is active.
`Technology is available to permit an eavesdropper to
`automatically scan all of the cellular frequencies in a
`given cell for such identification information. Conse
`quently, piracy of cellular telephone services is ran
`pant. Also, the lack of enciphering of the speech signals 45
`lays bare to eavesdroppers the content of conversations.
`In short, there is a clear and present need for effective
`security measures in the cellular telephony art, and that
`suggests the use of cryptology for the purposes of en
`suring authentication and privacy.
`50
`Several standard cryptographic methods exist for
`solving the general sort of authentication problem that
`exists in cellular telephony, but each turns out to have
`practical problems. First, a classical challenge/response
`protocol may be used, based on a private key crypto- 55
`graphic algorithm. In this approach, a subscriber's mo
`bile station is issued with a secret key which also known
`by the home system. When a serving system wishes to
`authenticate a subscriber, it applies to the home system
`for a challenge and a response to use with the given 60
`subscriber. The home system composes a random chal
`lenge and applies a one-way function to the challenge
`concatenated with the subscribers key to obtain the
`corresponding response. The challenge and response
`are supplied to the serving system, which issues the 65
`challenge to the mobile station. The mobile station in
`turn replies with the response, which it calculates from
`the challenge and from its stored secret key. The serv
`
`5,153,919
`2
`ing system compares the responses supplied by the
`home system and by the mobile station, and if they
`match, the mobile station is deemed authentic.
`The problem with this approach is that often the
`serving system is unable to contact the home system
`quickly enough to allow authentication of a call setup,
`or that the database software on the home system is
`unable to look up the subscriber's secret key and con
`pose the challenge/response pair quickly enough. Net
`work or software delays of a second or two would add
`that much dead time till the subscriber hears a dial tone
`after picking up the handset when placing a call, and
`longer delays (given the control networks and switch
`ing apparatus currently used by cellular providers)
`would be common. In the present milieu, such delays
`are unacceptable.
`Public key cryptography provides another standard
`class of ways for solving authentication problems. Gen
`erally speaking, each mobile station would be provided
`with a "public key certificate' of identity, signed by the
`public key of the service provider, stating that the mo
`bile station is a legitimate customer of the service pro
`vider. In addition, each mobile would also be given
`secret data (private keys) which it can use, together
`with the certificate, to prove to third parties (such as the
`serving system) that it is a legitimate customer.
`For example, service provider could have a pair of
`RSA keys, (F,G), with F private and G public. The
`service provider could supply each mobile with its own
`pair (D,E) of RSA keys, together with F(E) (the en
`cryption of the mobile's public key E using the provid
`er's private key F). Then a mobile asserts its identity by
`sending (E.F(E)) to the serving system. The serving
`system applies G to F(E) to obtain E. The serving sys
`tem generates a challenge X, encrypts it with the no
`bile's public key E to obtain ECX) which it sends to the
`mobile. The mobile applies its private key D to E(X) to
`obtain X, which it sends back to the server in the clear
`as a response.
`Although some variations on this theme involve less
`computation or data transmission than others, no public
`key authentication scheme yet exists which is efficiently
`executable in less than a second's time on the sort of
`hardware currently used in cellular telephones. Even
`though network connectivity between the serving and
`home systems is not needed at the moment of authenti
`cation, as it is in the classical approach, the same time
`constraints which rule out the classical approach also
`rule out the public key approach.
`Another technique is proposed by R. M. Needham
`and M. D. Schroeder in Using Encryption for Authentica
`tion in Large Computer Networks, Comm. of the ACM,
`Vol. 21, No. 12,993-999 (Dec. 1978). In brief, the Need
`ham-Schroeder technique requires that a third, trusted,
`party (AS) should serve as an authentication server
`which distributes session keys to the prospective parties
`(A and B) who are attempting to establish secure com
`munications. The protocol is as follows: when party A
`wishes to communicate with party B, it sends to authen
`tication server AS his own name, the name of party B
`and a transaction identifier. Server AS returns the name
`of party B, a session key, the transaction identifier and a
`message encrypted with B's key. All that information is
`encrypted with A's key. Party. A receives the informa
`tion, decrypts it, selects the portion that is encrypted
`with B's key and forwards that portion to party B. Party
`B decrypts the received messages and find it the name
`
`Page 9 of 16
`
`

`

`5
`
`O
`
`20
`
`30
`
`35
`
`5,153,919
`3
`4.
`of party A and the session key. A last check (to prevent
`FIG. 10 illustrates the three stage process for en
`"replays") is made by party B issuing a challenge to
`crypting and decrypting selected control and data Ines
`sages; and
`party A and party. A replies, using the session key. A
`FIG. 11 presents a block diagram of a mobile unit's
`match found at party B authenticates the identity of
`party A.
`hardware.
`SUMMARY OF THE INVENTION
`The security needs of cellular telephony are met with
`an arrangement that depends on a shared secret data
`field. The mobile unit maintains a secret that is assigned
`to it by the service provider, and generates a shared
`secret data field from that secret. The service provider
`also generates the shared secret data field. When a mo
`bile unit enters the cell of a base station, it identifies
`15
`itself to the base station, and supplies to the base station
`a hashed authentication string. The base station consults
`with the provider, and if it is determined that the mobile
`unit is a bona fide unit, the provider supplies the base
`station with the shared secret data field. Thereafter the
`mobile unit communicates with the base station with the
`assistance of authentication processes that are carried
`out between the mobile unit and the base station, using
`the shared secret data field.
`One feature of this arrangement is that the various
`25
`base stations do not have access to the secret that was
`installed in the mobile unit by the provider. Only the
`base stations which successfully interacted with the
`mobile unit have the shared secret data field; and that
`number can be limited by the provider simply by direct
`ing the mobile unit to create a new shared secret data
`field.
`Another feature of this arrangement is that the more
`elaborate authentication process that utilizes the secret,
`which is more time consuming and which takes place
`only through involvement of the provider, occurs infre
`quently; when a mobile unit first enters the cell (or
`when it is suspected that the shared secret data field has
`been compromised).
`Call originations, call terminations, and other func
`tions are authenticated using essentially the same au
`thentication protocol and the same hashing function.
`The few differences manifest themselves in the informa
`tion that is hashed.
`45
`BRIED DESCRIPTION OF THE DRAWING
`FIG. 1 illustrates an arrangement of network provid
`ers and cellular radio providers interconnected for ser
`vice to both stationary and mobile telephones and the
`like;
`FIG. 2 depicts the process for directing the creation
`of a shared secret data field and the verification of same;
`FIG. 3 depicts the registration process in a visited
`base station, for example, when the mobile unit first
`enters the cell serviced by the base station;
`FIG. 4 shows the elements that are concatenated and
`hashed to create the shared secret data;
`FIG. 5 shows the elements that are concatenated and
`hased to create the verification sequence;
`FIG. 6 shows the elements that are concatenated and
`hashed to create the registration sequence when the
`mobile unit goes on the air;
`FIG. 7 shows the elements that are concatenated and
`hased to create the call initiation sequence;
`FIG. 8 depicts the speech encryption and decryption
`process in a mobile unit;
`FIG. 9 shows the elements that are concatenated and
`hashed to create the re-authentication sequence;
`
`DETAILED DESCRIPTION
`In a mobile cellular telephone arrangement there are
`many mobile telephones, a much smaller number of
`cellular radio providers (with each provider having one
`or more base stations) and one or more switching net
`work providers (common carriers). The cellular radio
`providers and the common carriers combine to allow a
`cellular telephone subscriber to communicate with both
`cellular and non-cellular telephone subscribers. This
`arrangement is depicted diagrammatically in FIG. 1,
`where common carrier I and common carrier II con
`bine to form a switching network comprising switches
`10-14. Stationary units 20 and 21 are connected to
`switch 10, mobile units 22 and 23 are free to roam, and
`base stations 30-40 are connected to switches 10-14.
`Base stations 30-34 belong to provider 1, base stations
`35 and 36 belong to provider 2, base station 37 belongs
`to provider 4, and base stations 38-40 belong to pro
`vider 3. For purposes of this disclosure, a base station is
`synonymous with a cell wherein one or more transmit
`ters are found. A collection of cells makes up a cellular
`geographic service area (CGSA) such as, for example,
`base stations 30, 31, and 32 in FIG. 1.
`Each mobile unit has an electronic serial number
`(ESN) that is unique to that unit. The ESN number is
`installed in the unit by the manufacturer, at the time the
`unit is built (for example, in a read-only-memory), and it
`is unalterable. It is accessible, however.
`When a customer desires to establish a service ac
`count for a mobile unit that the customer owns or
`leases, the service provider assigns to the customer a
`phone number (MIN1 designation), an area code desig
`nation (MIN2 designation) and a "secret' (A-key). The
`MIN1 and MIN2 designations are associated with a
`given CGSA of the provider and all base stations in the
`FIG. 1 arrangement can identify the CGSA to which a
`particular MIN2 and MIN1 pair belongs. The A-key is
`known only to the customer's equipment and to the
`provider's CGSA processor (not explicitly shown in
`FIG. 1). The CGSA processor maintains the unit's
`ESN, A-key, MIN1 and MIN2 designations and what
`ever other information the service provider may wish to
`have.
`With the MIN1 and the MIN2 designations and the
`A-key installed, the customer's unit is initialized for
`service when the CGSA processor sends to the mobile
`unit a special random sequence (RANDSSD), and a
`directive to create a "shared secret data' (SSD) field.
`The CGSA sends the RANDSSD, and the SSD field
`generation directive, through the base station of the cell
`where the mobile unit is present. Creation of the SSD
`field follows the protocol described in FIG. 2.
`As an aside, in the FIG. 1 arrangement each base
`station broadcasts information to all units within its cell
`on some preassigned frequency channel (broadcast
`band). In addition, it maintains two way communica
`tions with each mobile unit over a mutually agreed,
`(temporarily) dedicated, channel. The manner by which
`the base station and the mobile unit agree on the com
`munications channel is unimportant to this invention,
`and hence it is not described in detail herein. One ap
`proach may be, for example, for the mobile unit to scan
`
`50
`
`55
`
`65
`
`Page 10 of 16
`
`

`

`C
`
`5
`
`35
`
`s(t) = t for Osts d
`
`st)=2d-2-t for dists 2d-3, and
`
`s(t)=S(t-2d-2) for all t.
`
`5,153,919
`5
`6
`all channels and select an empty one. It would then send
`the mod 256 function), addition, multiplication, and
`to the base station its MIN2 and MIN1 designations
`bit-wise Exclusive-OR functions.
`(either in plaintext form or enciphered with a public
`Returning to the SSD field initialization process of
`key), permitting the base station to initiate an authenti
`FIG. 2, when a RANDSSD sequence and the directive
`cation process. Once authenticated communication is
`to create a new SSD field (arrow 100 in FIG. 2) are
`established, if necessary, the base station can direct the
`received by the nobile station, a new SSD field is gen
`mobile station to switch to another channel.
`erated in accordance with FIG. 4. The mobile unit
`As described in greater detail hereinafter, in the
`concatenates the ESN designation, the A-key, and the
`course of establishing and maintaining a call on a nobile
`RANDSSD sequence to form an authentication string.
`telephony system of this invention, an authentication
`The authentication string is applied to Jumble block 101
`process may be carried out a number of times through
`(described above) which outputs the SSD field. The
`out the conversation. Therefore, the authentication
`SSD field comprises two subfields: the SSD-A subfield
`process employed should be relatively secure and sin
`which is used to support authentication procedures, and
`ple to implement. To simplify the design and lower the
`the SSD-B subfield which is used to support voice pri
`implementation cost, both the mobile unit and the base
`vacy procedures and encryption of some signaling mes
`station should use the same process.
`sages (described below). It may be noted that a larger
`Many authentication processes use a hashing func
`number of SSD subfields can be created; either by sub
`tion, or a one-way function, to implement the processes.
`dividing the SSD field formed as described above or by
`A hashing function performs a many-to-one mapping
`first enlarging the SSD field. To increase the number of
`which converts a "secret" to a signature. The following
`20
`bits in the SSD field one needs only to start with a
`describes one hashing function that is simple, fast, effec
`larger number of data bits. As will be appreciated from
`tive, and flexible. It is quite suitable for the authentica
`the disclosure below, that is not a challenging require
`tion processes of this invention but, of course, other
`hashing functions can be used.
`ent.
`The home CGSA processor knows the ESN and the
`25
`The Jumble Process
`A-key of the mobile unit to which the received MIN2
`and MIN1 designations were assigned. It also knows the
`The Jumble process can create a "signature' of a
`RANDSSD sequence that it sent. Therefore, the home
`block of d "secret' data words, b(i), with the aid of a
`k-word key x(j), where d, i, j, and k are integers. The
`CGSA processor is in position to duplicate the SSD
`'signature' creation process is carried out on one data
`field creation process of the mobile unit. By concatenat
`word at a time. For purposes of this description, the
`ing the RANDSSD signal with the ESN designation
`words on which the Jumble process operates are 8 bits
`and the A-key, and with the above-described Jumble
`long (providing a range from 0 to 255, inclusive), but
`process, the CGSA processor creates a new SSD field
`any other word size can be employed. The "secret' data
`and partitions it into SSD-A and SSD-B subfields.
`block length is incorporated in the saw tooth function
`However, the SSD field created in the home CGSA
`processor must be verified.
`In accordance with FIG. 2, verification of the created
`SSD field is initiated by the mobile unit. The mobile unit
`generates a challenge random sequence (RANDBS
`sequence) in block 102 and sends it to the home CGSA
`processor through the serving base station (the base
`station that serves the area in which the mobile unit is
`located). In accordance with FIG. 5, the home CGSA
`processor concatenates the challenge RANDBS se
`quence, the ESN of the mobile unit, the MIN1 designa
`tion of the mobile unit, and the newly created SSD-A to
`form an authentication string which is applied to the
`Jumble process. In this instance, the Jumble process
`creates a hashed authentication signal AUTHBS which
`is sent to the mobile station. The mobile station also
`combines the RANDBS sequence, its ESN designation,
`its MIN1 designation and the newly created SSD-A to
`form an authentication string that is applied to the Jun
`ble process. The mobile station compares the result of
`its Jumble process to the hashed authentication signal
`(AUTHBS) received from the home CGSA processor.
`If the comparison step (block 104) indicates a match, the
`mobile station sends a confirmation message to the
`home CGSA processor indicating the success of the
`update in the SSD field. Otherwise, the mobile station
`reports on the failure of the match comparison. As an
`aside, it is possible that the serving system, acting as an
`agent for the home CGSA, could respond to the chal
`lenge from the mobile unit, if the home GCSA were to
`send a copy of the newly generated SSD-A to the serv
`ing system along with the RANDSSD sequence it used
`to create it.
`
`where
`ik is i modulo k, SBOX(z)=y+y/2048 mod 256,
`y = (zelé)(z-- 111)(z),
`y/2048 is the integer portion of y divided by 2048,
`and CD represents the bit-wise Exclusive-OR func
`tion; and
`b) z is updated with: z=z--b(s(i)) mod 256.
`It may be appreciated that in the process just de
`55
`scribed there is no real distinction between the data and
`the key. Therefore, any string that is used for authenti
`cation can have a portion thereof used as a key for the
`above process. Conversely, the data words concate
`nated with the key can be considered to be the "authen
`tication string'. It may also be noted that each word
`b(i), where 0SiCd is hashed individually, one at a time,
`which makes the hashing "in place'. No additional
`buffers are needed for the hashing process per se.
`The process just described can be easily carried out
`with a very basic conventional processor, since the only
`operations required are: shifting (to perform the divi
`sion by 2048), truncation (to perform the function and
`
`This function is used in the following process where,
`starting with z=0 and i-0, for successively increasing
`interger values of i in the range OS 6d-5,
`a) b(s(i)) is updated by:
`bis(i)) = b(s))--x(iR)--SBO(z)mod 256
`
`45
`
`50
`
`65
`
`Page 11 of 16
`
`

`

`5,153,919
`7
`8
`Having initialized the mobile station, the SSD field
`tion string created by the mobile unit's home CGSA
`remains in force until the home CGSA processor directs
`processor matches the hashed authentication string
`the creation of a new SSD field. That can occur, for
`created in the mobile unit and supplied by the serving
`example, if there is reason to believe that the SSD field
`base station, then verification is deemed successful. In
`has been compromised. At such a time, the home 5
`such a case, the home CGSA processor supplies the
`CGSA processor sends another RANDSSD sequence
`serving base station with the unit's SSD field. As an
`to the mobile unit, and a directive to create a new SSD
`aside, to keep the ESN designation and the SSD field
`field.
`secure, the communication between the base stations
`As mentioned above, in cellular telephony each base
`and the CGSA processor is carried in encrypted form.
`station broadcasts various informational signals for the 10
`In the above-described protocol, the mobile unit's
`benefit of all of the nobile units in its cell. In accor
`CGSA processor attempts to verify the validity of the
`dance with FIG. 1 management, one of the signals
`hashed authentication string. When the verification is
`broadcast by the base station is a random or pseudoran
`unsuccessful, the CGSA processor informs the serving
`dom sequence (RAND sequence). The RAND se
`base station that the mobile unit was not authenticated
`quence is used by various authentication processes to 15
`and may suggest that either the contact with the mobile
`randomize the signals that are created and sent by the
`unit be dropped or that the mobile unit be directed to
`mobile units. Of course, the RAND sequence must be
`retry the registration process. To retry the registration
`changed periodically to prevent record/playback at
`process the hone CGSA processor can either continue
`tacks. One approach for selecting the latency period of
`participation in the authentication process or it can
`a RAND signal is to make it smaller than the expected 20
`delegate it to the serving base station. In the latter alter
`duration of an average call. Consequently, a mobile
`native, the serving base station informs the home CGSA
`unit, in general, is caused to use different RAND signals
`processor of the ESN sequence and the MIN1 designa
`on successive calls.
`tion of the mobile unit, and the CGSA processor re
`In accordance with one aspect of this invention, as
`sponds with the SSD field of the mobile unit and the
`soon as the mobile unit detects that it enters a cell it 25
`RANDSSD with which the SSD field was created.
`registers itself with the base unit so that it can be authen
`Authentication, in the sense of creating a hashed au
`ticated. Only when a mobile unit is authenticated can it
`thentication string and comparing it to the hashed au
`initiate calls, or have the base station direct calls to it.
`thentication string sent by the mobile unit, is then car
`When the mobile unit begins the registration process
`ried out by the serving base station. A retry directive
`it accepts the RAND sequence broadcast by the base 30
`can then be carried out without the home CGSA pro
`station and, in turn, it sends to the serving base station
`cess by the serving station sending the RANDSSD to
`its MIN1 and MIN2 designations and its ESN sequence
`the mobile unit. This "registration' protocol is depicted
`(in plaintext) as well as a hashed authentication string.
`in FIG. 3.
`According to FIG. 6, the hashed authentication string is
`Once the mobile unit has been "registered' at the
`derived by concatenating the RAND sequence, the 35
`serving base station (via the above-described process)
`ESN sequence, the MIN1 designation and the SSD-A
`the serving base station possesses the ESN and the SSD
`subfield to form an authentication string; and applying
`field of the mobile unit, and subsequent authentication
`the authentication string to the Jumble process. The
`processes in that cell can proceed in the serving base
`hashed authentication string at the output of the Jumble
`station without reference to the home CGSA proces
`process is sent to the serving base station together with 40
`sor-except one. Whenever, for any reason, it is desir
`the ESN sequence.
`able to alter the SSD field, communication is effectively
`In some embodiments, all or part of the RAND se
`between the home CGSA processor and the mobile
`quence used by the mobile unit is also sent to the serving
`unit; and the serving base station acts only as a conduit
`base station (together with the ESN sequence and the
`for this communication. That is because creation of a
`MIN1 and MIN2 designations), because the possibility 45
`new SSD field requires an access to the secret A-key,
`exists that the RAND value has changed by the time the
`and access to the A-key is not granted to anyone by the
`hashed authentication string reaches the base station.
`CGSA processor. Accordingly, when a new SSD field
`On the base station side, the serving base station
`is to be created and the mobile unit is not in the area of
`knows the RAND sequence (because the base station
`the hone CGSA, the following occurs:
`created it) and it also knows the ESN and the MIN2 and 50
`the home CGSA processor creates a RANDSSD
`MIN1 designations with which the mobile unit identi
`sequence and alters the SSD field based on that
`fied itself. But, the serving base station does not know
`RANDSSD sequence,
`the SSD field of the mobile unit. What it does know is
`the home CGSA processor supplies the serving base
`the identity of the mobile unit's home CGSA processor
`(from the MIN1 and MIN2 designations). Conse- 55
`station with the RANDSSD sequence and the
`quently, it proceeds with the authentication process by
`newly created SSD field,
`sending to the mobile unit's home CGSA processor the
`the serving base station directs the mobile unit to alter
`MIN1 designation, the ESN sequence, the hashed au
`its SSD field and provides the mobile unit with the
`RANDSSD sequence,
`thentication string that the mobile unit created and
`transmitted, and the RAND sequence that the serving 60
`the mobile unit alters the SSD field and sends a chal
`lenge to the serving base station,
`base station broadcast (and which the mobile unit incor
`porated in the created hashed authentication string).
`the serving base station creates the AUTHBS string
`From the mobile unit's MIN1 designation and ESN
`(described above) and sends it to the mobile unit,
`sequence the home CGSA processor knows the mobile
`and
`unit's identity and, hence, the mobile unit's SSD-A 65
`the mobile unit verifies the AUTHBS string and in
`subfield. Therefore it can proceed to create an authenti
`forms the serving base station that both the mobile
`cation string just as the mobile unit did, and apply it to
`unit and the serving base station have the same
`the Jumble process (FIG. 6). If the hashed authentica
`SSD fields.
`
`Page 12 of 16
`
`

`

`O
`
`15
`
`5,153,919
`9
`10
`Having been registered by the serving base station,
`the base station. As an aside, the hashed sequence may
`also include the dialed digits so as to make the hijacking
`the mobile unit can initiate calls with an authentication
`process as depicted in FIG. 7. The call initiation se
`of the channel even more difficult. The base station, at
`this point, is in a position t