Note: Descriptions are shown in the official language in which they were submitted.
CA 02402934 2005-11-03
METHOD AND SYSTEM FOR GENERATING A SEQUENCE
NUMBER TO BE USED FOR AUTHENTICATION
FIELD OF THE INVENTION
The invention relates to a method and system for performing
an authentication, and to a method for generating a sequence
number to be used for authentication.
1o BACKGROUND OF THE INVENTION
In mobile communication, it is customary to perform an
authentication between a user and a network before starting
any new data/information transmission. When initiating a
i5 connection, a mutual authentication by the user and the
network will be achieved. The user equipment and the
network normally have knowledge of a secret key which is
shared between, and available only to, an entity of the user
such as USIM (User Service Identity Module) and an
2o authentication centre (AuC) which may be co-operating with a
central register such as a home location register (HLR) or a
home environment (HE). To support a network authentication,
the user entity such as USIM, and the central entity e. g.
of the HE may store or generate sequence numbers. The
2s authentication provides enhanced security against undesired
or unallowed use of network components.
The document 3G TS 33.102 V3.3.1 (2000-Ol) of the "Third
Generation Partnership Project (3G PP)", Title: "Technical
3o Specification Group Services and System Aspects; 3G
Security; Security Architecture", Release 1999, (published
by ETSI as ETSI TS 133 102 V3.3.1) deals with security
aspects and describes network access security mechanisms
1
CA 02402934 2005-11-03
(section 6, pages 17 ff.). In particular, section 6.3
"Authentication and key agreement" deals with a method and
system for performing an authentication between a mobile
station (MS) and a network, wherein a serving network (SN)
s having a visitor location register(VLR) (or other support
node like SGSN (Serving GPRS Support Node)) is sending an
authentication data request to a home environment (HE)
having a home location register (HLR) which responds by
sending back an authentication data response comprising a
io batch of authentication vectors.
For performing an authentication between the serving network
(SN) and the mobile station (MS), the serving network (SN)
is sending a user authentication request which contains a
15 random number and an authentication information
(authentication token) generated based on a sequence number
which is formed in the home environment according to a below
defined strategy. The mobile station verifies the received
authentication information, thus authenticating the network,
2o and computes an answer which is sent back to the serving
network and compared therein with an expected answer. If
the received response corresponds to the expected response,
the subscriber authentication is successfully performed, and
keys internally generated in the mobile station and the
25 serving network depending on a secret key are used for
ciphering and integrity purposes.
Annex C of the above-mentioned document 3G TS 33.102 V3.3.1
describes the manner of generating sequence numbers in the
3o authentication centre. These sequence numbers are used for
generating the authentication vectors in the authentication
centre and are stored in individual counters (one counter
per user).
2
CA 02402934 2005-11-03
There is also provided a global counter, e. g. a clock
giving universal time. When the home environment needs new
sequence numbers to create a new batch of authentication
vectors, the home environment retrieves the user-specific
value of the counter from the database and creates a new
sequence number based on a predefined strategy. When the
generation of the
2a
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
first authentication vector in a batch has been completed, the
user-specific counter is reset to the new sequence number, i.e.
the new sequence number is stored in the database.
Each generation of sequence number is therefore accompanied by
corresponding writing accesses to the database. These database
writing operations require time and CPU capacity.
In GSM (Global System for Mobile Telecommunication) systems,
1o the database of the authentication centre (AuC) is quite
static, and updates are only performed when new subscribers are
entered to the database. In UMTS (Universal Mobile
Telecommunications System), the sequence numbers used for
authentication should be individual ones because of re-
15 synchronisation, and should therefore be stored after every
authentication vector generation. This writing causes a high
database load and may also decrease the reliability of the
database.
20 As mentioned above, in authentication such as UMTS
authentication, a sequence number is used. This sequence number
is generated in the authentication centre (AuC) when an
authentication vector, or a batch of authentication vectors, is
generated. The USIM (User Service Identity Module) compares the
25 sequence number received from the authentication centre, to a
previously used sequence number stored in the USIM. When the
USIM does not accept the new sequence number, it sends a re-
synchronisation message to the authentication centre together
with a new seauence number. The authentication centre checks if
3o re-synchronisation is necessary, and, if yes, authenticates the
USIM and re-synchronises the sequence number. This re-
synchronisation means that the sequence number stored in the
authentication centre is reset to the sequence number received
from the USIM.
3
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
SUMMARY OF THE INVENTION
The invention provides a solution to the above described
problem of high amount of database writing operations, and
describes a new mechanism for generating sequence numbers
usable for authentication purpose.
The invention provides a method and system for performing an
authentication wherein a sequence number is used for generating
1o an authentication information transmitted to the user equipment
for authentication purpose. The authentication may be performed
between any two or more entities requiring or requesting an
identity check. In a preferred embodiment, the authentication
may be performed between an user equipment and a network entity
15 of a communication network The sequence number is generated on
the basis of a general information which changes in a defined
manner, and a value stored in a memory. The value preferably,
but not necessarily is a user-specific value, and will be used
several times for generating several different sequence
2o numbers.
The value is preferably calculated based on the difference
between a previously used sequence number and the general
information.
The general information may be derived from an standardized,
for instance international or global, parameter such as a
global counter counting a universal time (global clock).
3o Preferably, the user-specific value is changed only in a re-
synchronisation procedure so that the database writing
operations are reduced to a minimum. The re-synchronisation
procedure may be effected when the difference between the user-
specific value and the general information exceeds a certain
,., limit, or when the previously used sequence number is higher
4
CA 02402934 2005-11-03
than the general information, or when the sequence.number
received by the MS is not in acceptable range.
The previously used sequence number may be stored in a
s storage (e. g. a chip or disk memory) of the user equipment,
and may be compared with an actually received sequence
number for deciding on the necessity of a re-synchronisation
procedure.
io A preferred easy and swift manner of generating the sequence
number is to add the user-specific value to the general
information.
For reducing the number of generation of sequence numbers,
15 an index number may be concatenated to the sequence number
for forming a batch of different authentication vectors.
An alternative to the use of index numbers is to generate
consecutive sequence numbers for forming a batch of
2o different authentication vectors.
The initial values of the user-specific values may be
originally set to zero but are preferably individually set.
2s Furthermore, the invention provides a method and system for
generating sequence numbers usable for performing an
authentication e.g., between an user equipment and a network
entity of a communication network. The sequence numbers are
generated on the basis of a general information which
3o changes in a defined manner, and a value stored in a memory.
The value will be used several times for generating several
different sequence numbers.
CA 02402934 2005-11-03
According to a further broad aspect of the present invention
there is provided a device for generating a sequence number
used for generating authentication information. The device
comprises a memory for storing a value used several times
s for generating several different sequence numbers. The
device also comprises a counter for generating general
information changing in a defined manner. A calculation
section is also provided for calculating the value on the
basis of the difference between previously used or
to predetermined sequence number and the general information
and further for calculating the sequence number on the basis
of the general information and the value.
The described mechanism for generating sequence numbers is
15 usable for authentication purpose and eventually also for
key agreement.
5a
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
The invention is applicable to any system in which a sequence-
number-based authentication scheme is used, and a possibility
for re-synchronisation may be provided, and may for instance be
_> used i.n an UMTS system..
The invention reduces the amount of writing operations of the
database storing the information for generating the sequence
numbers) significantly. This also leads to a corresponding
1o decrease of the processor load handling the writing operations,
and of the necessary performance time. In addition, the
reliability of the database and of the system is increased.
15 BRIEF DESCRIPTION OF THE FIGURES
Fig. 1 shows a basic structure of a system according to one
embodiment of the invention;
2o Fig. 2 illustrates the generation of authentication vectors in
an authentication centre and shows details of generation of
authentication information and of the authentication vectors
using a sequence number SQN;
25 Fig. 3 shows the processes of authentication and key agreement
performed between a mobile station, a serving network, and an
home environment, and illustrates the basic concept of handling
of authentication requests and responses;
3o Fig. 4 illustrates the user authentication function performed
in the mobile station and shows details of the generation of a
response and further data in a mobile station;
Fig. 5 illustrates the generation of an authentication response
~s~, by the mobile station and shows details of construction of a
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
parameter AUTS sent from the user equipment (mobile station) to
the network for requesting a re-synchronisation ; and
Fig. 6 illustrates the re-synchronisation mechanism and shows
the message transmission between a user equipment, a serving
network, and an authentication centre of a home network (home
location register).
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION
Fig. 1 shows a basic structure of an embodiment of a system
according to the invention. A mobile station (MS) 1 may be or
comprise any type of user equipment such as a mobile phone, a
terminal, data equipment or the like. The MS 1 is equipped or
co-operates with a memory 2 storing a user-specific sequence
number SQNUSIM~ For handling a signal transmission and/or
receipt as indicated by a double-headed arrow, the mobile
station 1 communicates with a serving network SN 3 having a
.;. visitor location register VLR (or some other support node like
SGSr~). The serving network 3 communicates, as indicated by a
double-headed arrow, with a home environment or home network 4
having a home location register, an authentication centre AuC
not separately shown, and the like. The home environment HE 4
~5 is equipped with a database or storage 5 which stores, for each
user registered in the home environment and/or the home
location register, an individual user-specific information D.
Furthermore, the home environment 4 is equipped with a global
30 counter 6 which here is a global clock (universal time) GLC,
and a sequence number calculating section 7.
The described method and system use a global sequence number
SQN~LC which is calculated or derived from the global clock GLC
(counter 6) and a subscriber-specific difference D (stored in
7
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
memory ' of the authentication centre) to the global sequence
number.
The SQN,;,,- is generated by using the global clock (GLC). The
_. actual value of SQNc;,~ is, in this embodiment, the time gap from
an initial time point (e.g. 01.01.2000, 00:00.00) to the
current time. The rate of the GLC counter 6 is defined in such
a manner that SQNGLC or any other SQN will not wrap around. If,
for example, the clock rate of the global clock is one second,
1o a 32-bit counter wraps around only in about 136 years and will
thus not provide any problems. The SQNGLC is calculated in the
following way:
SQNGLC = GLC~ow - GLCItaI'r .
GLCNOw is the actual global time, ~L~INIT 1S the initial time.
In the authentication database contained in memory 5, every
subscriber has an individual value D. This value D is the
difference between a previously used sequence number SQN which
is stored in memory 2 of mobile station 1, i.e. in the USIM
2o thereof (SQN~SIM) , and the SQNGLC. Hence, the value of D is
calculated in the following way:
D = SQNUSIM - SQNGLC
Initially, D may be set to 0, and will be changed in a re-
synchronisation process only. It is also possible to set the
initial values of D individually. This is an useful option if
the sequence numbers are preferred to be individually
distinguished from user to user, or at least from some user
3o groups to some user groups. The parameter D may have a positive
or negative value, and is stored in the authentication database
(memory 5). The value of D is changed only in a re-
synchronisation procedure.
A re-synchronisation is performed only when the value SQNUSIr:
stored in memory 2 is bigger than SQN, or when SQNUSZM is much
8
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
smaller than the actually generated SQN, i.e. SQN - SQN~sIM ? X
wherein X stands for a threshold value which preferably is
rather large such as about, e.g., 1,700,000 (which
approximately corresponds to the number of seconds contained in
a time period of twenty days). In the latter case, a re-
synchronisation procedure is requested when a time period of
approximately twenty days has passed since the last refreshing
or storing of SQN~sIM. Of course, the threshold value can also
be set to smaller or even larger values, and will also depend
on the clock rate (in the above example, a clock rate of one
second has been assumed). In any case, the threshold should be
selected in such a manner that a re-synchronisation is
occurring only very rarely in a normal situation.
The final sequence number SQN which the authentication centre
calculates (in section 7) and sends to the USIM of MS 1 via
SN/VLR 3, for authentication and key agreement, is calculated
in the following way:
SQN = SQN~L~ + D ~ ~ IND.
The index IND is concatenated to the end of the sequence
number, i.e. is added as the final least significant bits of
the sequence number. The index IND is used to indicate the
index of the authentication vectors in a set (batch). In one
set there can be, for instance, one to five authentication
vectors, i.e. the index IND is running from one to five.
It is also possible to avoid the use of the separate additional
3o index field IND, and to use consecutive SQN numbers for vectors
in one batch. In this case, SQN may be calculated in the
following manner:
SQN = SQN~LC + D + X,
9
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
with X having consecutive values from 1 to 5 when a set of
authentication vectors comprises up to five authentication
vectors. When using this option, the system ensures that no
further batches of authentication vectors are delivered for the
same subscriber during a short time interval. If, for instance,
the clock unit is one second, and the batch size is five, this
forbidden interval is five seconds. Hence, batches of
authentication vector for a user (USIM) are generated with a
time interval of at least five seconds. Otherwise, when not
providing such a forbidden time interval, there is a
possibility that two authentication vectors will be generated
having the same sequence number which might lead to an
individual authentication failure.
15 A writing operation for writing to the authentication database
(storage 5) is necessary only when a re-synchronisation of the
sequence number is requested. In normal cases, the user-
specific value of D will simply be read from the storage S and
added to the global sequence number SQN~LC calculated from the
2o actual time. Using this mechanism, there is no need to store
the calculated sequence number SQN in the authentication centre
(storage 5).
When a re-synchronisation is requested by a MS (USIM) l, the MS
25 1 will send the SQN~sIM value to the authentication centre of HE
9 (via SN/VLR 3), and the authentication centre and/or the
calculation section 7 will calculate a new value of D according
to the above equation ( D = SQN~sIr, - SQNGLC) . This newly
calculated value of D will then be stored as new user-specific
3o value D for this user.
Fig. 2 illustrates the generation of authentication vectors by
the home environment HE such as the home network comprising an
authentication centre and a home location register (HE/HLR 4 in
35 Fig . 1 ) .
1C
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
The authentication centre of the home environment 4 starts, for
generating one or several authentication vectors AV, with the
generation of a fresh sequence number SQN ("Generate SQN") in
the above discussed manner, and an unpredictable challenge RAND
("Generate RAND") which may be a randomly selected or generated
number. Contrary to the prior art shown in the above cited
document 3G TS 33.102 V3.3.1, the authentication centre of the
home environment does no longer need to keep track of a counter
counting a specific count value for each user. The
authentication centre merely needs the user-specific
information D stored in memory 5 for generating a plurality of
sequence numbers SQN.
Further, the sequence number SQN is preferably generated in
such a way that it does not expose the identity and location of
the user. In case there is some possibility that the sequence
number SQN might expose the identity and location of the user,
an anonymity key AK may be used to conceal it. Moreover, the
sequence number generation mechanism allows protection against
2o wrap around in a USIM, i.e. the sequence number is long enough
and only relatively small jumps ahead are acceptable.
An authentication and key management field AMF is generated in
a manner known per se, and is included in the authentication
2;, token AUTN of each authentication vector. Example uses of the
AMF field are given in the above cited document. "K"
represents, as known, a long-term secret key shared between the
USIM and the authentication centre.
3~ As shown in Fig. 2, the following values are computed in the
authentication centre: a message authentication code MAC = f1K
(SQN ~~ RAND ~~ AMF) where fl is a message authentication
function; an expected response XRES = f2K(RAND) where f2 is a
(possibly truncated) message authentication function; a cipher
3~~ key CK = f3I;(RAND) where f3 is a key generating function; an
integrity key IK = f4h(RAND) where f4 is a key generating
11
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
function; and an anonymity key AK = f5,;(RAND) where f5 is
either a key generating function, or is equal to zero in case
no anonymity key is necessary for concealing the identity and
location of the user. The concealment of the sequence number is
to protect against passive attacks. If no concealment is
necessary, no anonymity key AK is generated, and the
authentication token AUTN contains the sequence number SQN in
unchanged form.
Further, the authentication token AUTN is formed which is
constructed as shown in Fig. 2: AUTN = SQN +O AK II AMF II MAC.
Finally, an authentication vector AV (or a set of AVs) is
generated as indicated in Fig. 2:
AV = RANDIIXRESIICKIIIKIIAUTN.
The symbol "I~" indicates a simple concatenation wherein the
bits of the indicated parameters are simply attached to one
another in the indicated manner.
Fig. 3 illustrates the information flow for authentication and
key agreement. The method is chosen in such a way as to achieve
maximum compatibility with the current GSM (Global System for
Mobile Telecommunication) security architecture and facilitate
migration from GSM to UMTS (or any other network type such as
packet-switched system GPRS (General Packet Radio Service)).
The method is composed of a challenge/response protocol
identical to the GSM subscriber authentication and key
establishment protocol combined with a sequence number-based
one-pass protocol for network authentication. Upon receipt of
an "authentication data request" from a serving network or a
support node (such as a serving GPRS support node SGSN)
initiated by the visitor location register VLR for instance,
J~ the authentication centre of the home environment HE 4
generates authentication vectors AV (1...n) in the above
12
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
described manner, and sends an ordered array of n
authentication vectors (the equivalent of a GSM "triplet") to
the SN/VLR 3 ("Authentication data response AV(l...n)".
Each authentication vector AV consists of the components shown
in Fig. 2. Each authentication vector is good for one
authentication and key agreement between the serving network SN
3 (for instance the VLR or SGSN) and the USIM or other
authentication equipment of the mobile station MS 1.
When the SN/VLR 3 initiates an authentication and key
agreement, it selects the next authentication vector AV(i) from
the stored array and sends the parameters RAND and AUTN to the
user as shown in Fig. 3. The USIM checks whether AUTN can be
accepted ("Verify AUTN(i)") and, if so, produces a response RES
("Compute RES(i)") which is sent back to the SN/VLR 3 as "User
authentication response". The MS 1 furthermore computes CK(i)
and IK(i). The SN/VLR 3 (or any VLR/SGSN serving for
authentication purpose) compares the received response RES with
0 XRES. If they match, the VLR/SGSN 3 considers the
authentication and key agreement exchange to be successfully
completed. The established keys CK and IK will then be
transferred by the USIM and the VLR/SGSN 3 to the entities
which performs ciphering and integrity functions.
~5
Fig. 4 shows details of the user authentication function
performed in the mobile station, e.g. in the USIM thereof. Upon
receipt of RAND and AUTN, the user first computes the anonymity
key AK = f5f;(RAND) and retrieves the sequence number SQN = (SQN
AK) O AK. Next, the computer computes XMAC = f1K (SQN~~RAND~
~AMF) and compares this with the received MAC which is included
in AUTN. If they are different, the user sends a "User
authentication reject" message back to the serving network or
support node handling the connection to the mobile station,
with an indication of the cause, and the user abandons the
procedure. Next, the mobile station l, e.g. the USIM thereof,
13
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
verifiea that the received sequence number SQN is in the
correct range. If the user considers the sequence number not to
be in the correct range, he sends a "Synchronisation failure"
message back to SN/VLR 3 including an appropriate parameter
RUTS as shown in Figs. 5 and 6, and abandons the procedure.
As shown in Fig. 5, AUTS = SQNMS O+ AKIIMACS. SQNMS here is
SQN~sIM stored in memory 2. The sequence number is concealed in
this embodiment using AK (= f5K(MACS) but may also be sent in
1U unconcealed form. MACS = fl*K(SQNMS~IRANDIIAMF). RAND is the
random value received in the current user authentication
request. fl* is a message authentication code (MAC) function
with the property that no valuable information can be inferred
from the function values of fl* about those of fl, ..., f5 and
15 vice-versa.
The sequence number generation mechanism is adapted to allow a
re-synchronisation procedure in the home environment as
described below.
Fig. 6 illustrates the re-synchronisation procedure which is
performed when the sequence number SQN contained in the
authentication vector is either smaller than SQN~sIM stored in
memory 2 or is much larger than SQNUSZM. This situation will
normally occur only in rare cases so that a re-synchronisation
procedure will be performed only rarely.
The serving network SN 3 in charge of the visitor location
register, or any support node handling the connections, may
send two types of "authentication data requests" to the
authentication centre of the home network (HE 4), i.e. the
regular one shown in Fig. 1, and one used in case of
synchronisation failures which is described below.
3~~ Upon receiving a synchronisation failure message containing
RUTS from the user (MS 1), the serving network sends an
l~
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
authentication data request with a "synchronisation failure
indication" to the authentication centre of the home network,
together with the parameters RAND (as sent to the MS 1 in the
preceding user authentication request) and RUTS which contains
the (eventually concealed) sequence number SQN~sIM of the mobile
station MSl.
When the authentication centre of the home network receives
such an authentication data request with "synchronisation
to failure indication", it acts as follows:
1) the authentication centre of the home network HE 4
retrieves SQN~sIM by computing f5K(MACS), if concealed,
otherwise it simply takes the unconcealed SQNUSZM value of
the RUTS parameter;
15 2) the authentication centre calculates the value of D based
on the above indicated equation D = SQNUSiM - SQNcLC (actual
global clock value);
3) the authentication centre resets the value of D to the new
value calculated in step 2 and stores this new value of D
2o in memory 5;
4) the authentication centre of the home network 4 (HLR/AuC)
sends an authentication data response with a new batch of
authentication vectors {Qisymbol 125 \f "Symbol" \s 12 to
the VLR or SGSN of the serving network 3.
~' S
Instead of sending a batch of authentication vectors, it is
also possible to send only one authentication vector. In the
latter case, no concatenated index "IND" is necessary (this
index IND is indicated in the drawings and above description by
a adding an index "i").
In an alternative embodiment, the mobile station 1 may be
adapted to perform the calculation of D according to the above
equation (SQN~sIM - SQNcLC) if it has access to a global clock
.. counter, and to send back this value of D (possibly concealed)
instead of SQN~sio when requesting a re-synchronisation
CA 02402934 2002-09-27
WO 01/78306 PCT/EP00/03093
procedure. The authentication centre of the home network will
then store this value D in its storage 5.
When first receiving a SQN value from the home environment 4
(via the serving network 3), the mobile station 1 may be
adapted to store this received SQN value in memory 2 as
"SQN~sIM". The system may also be adapted to use a predetermined
sequence number as "SQN~sIh," which will be stored in the memory
2 and be used in the calculation section 7 for calculating D.
The serving network 3 having a visitor location register as
shown in Fig. 1 can be any serving module handling the
communication between the mobile station 1 and the home network
4, i.e. can be an interrogating network, a mobile switching
centre (or the VLR thereof) as shown in Fig. 6, or any support
node such as an SGSN.
Although the invention has been described above by referring to
preferred embodiments, the scope of the invention is not
restricted thereto and also covers any modifications,
amendments, additions or the like.
16
