TSG SA WG3 Security						TSG S3-99304
Meeting #6, Sophia Antipolis, 29 Sep – 1 Oct 1999

Source: 		Siemens AG
Title: 	A generalised description of sequence number management options 
Document for:	Discussion and decision
Agenda item:	tbd

Abstract
This contribution provides a generalisation of the sequence number management schemes currently contained in Annex C of 3G TS 33.102 (UMTS Security Architecture). It also addresses an action item to all from S3#4 and #5. 
Currently, Annex C specifies the use of sequence numbers based on individual and global counters respectively. The former have the drawback that they have to be concealed so as not to supply information about the user’s identity, the latter may be difficult to reconcile with re-synchronisation and protection against counter wrap around. This contribution proposes to use generalised sequence numbers which have an individual and a global component, and suggests text for a new subsection of Annex C. It is shown that the solutions currently contained in Annex C can be described as special cases of the proposed generalised approach. It is also shown how parameters can be chosen so that the drawbacks of the existing solutions mentioned above are avoided. It is concluded that a length of 48 bits for generalised sequence numbers is sufficient.

1	Overview
The authentication and key agreement protocol specified in section 6.3 of [1] uses sequence numbers in authentication vectors generated by the Authentication Centre (AuC) and checked by the USIM to guarantee the freshness of the derived cipher and integrity keys to the user. For this purpose, counters SQNHE and SQNMS are maintained in the Home Environment (HE) / Authentication Centre (AuC) and in the USIM respectively. According to Annex C of [1], sequence numbers generated by the AuC may be global, i.e. the HE maintains one global counter from which the sequence numbers for all users are derived, or they may be individual, i.e. the AuC maintains one counter for each user. 
Sequence numbers based on global counters have the advantage that they need not be concealed using an anonymity key. However, while mechanisms for re-synchronisation [1, section 6.3] and against counter wrap-around [1, Annex C.5] have been specified for sequence numbers based on individual counters in order to cope with cases of corruption of global counters by errors or by malicious intruders in the AuC, no such mechanisms have been specified so far for sequence numbers based on global counters. It is not argued here that it is impossible to secure a system using global counters against this type of events. But it should be noted that, whereas the counter is global, it cannot be ruled out that users may still be affected in individual ways, especially in the case of an attack by an intruder. If such an attack happened it might be necessary to be able to react on a per user basis. Therefore it does not seem obvious how to specify appropriate recovery mechanisms for the case of global counters. 
An action item to all from S3#4 and #5 (see report S3#5, section 4) asked to examine the consequences of the (modified) synchronisation procedure on the option of a global counter. In response to this action item we propose an alternative here to which the re-synchronisation and counter wrap-around prevention mechanisms defined for sequence numbers based on individual counters also apply, but which does not require concealment of sequence numbers, when parameters are appropriately chosen. This alternative consists in introducing generalised sequence numbers with an individual and a global component. How such sequence numbers are generated and managed is described in the next section.
2	Use of generalised sequence numbers
The marked text in this section is proposed for inclusion in Annex C of [1]. It is left to the discussion in SA3 where in Annex C to best place the text. E. g. it may be included as Annex C.6. In view of the fact that this proposal includes the existing schemes as special cases a re-organisation of Annex C may also be considered appropriate.
“This section describes the use of generalised sequence numbers which have an individual and a global component.
(1)	The sequence number consists of two concatenated parts SQN = SQN1 || SQN2. SQN1 represents the most significant bits of SQN, and SQN2 represents the least significant bits of SQN. 
(2)	There are counters SQNMS and SQNHE in the MS and the HE respectively. Both parts of SQN are stored by these counters. SQNHE is an individual counter, i.e. there is one per user.
(3)	There is a global counter, e.g. a universal clock with an appropriate time granularity (e.g. seconds elapsed since the start of the system). For short we call the value of this global counter at any one time GLC. If GLC is taken from a universal clock it is computed mod 2n where n is the length of GLC in bits.
(4)	When the HE needs a new sequence number SQN to create a new authentication vector, HE retrieves the (user-specific) value of SQNHE = SQN1HE || SQN2HE from the database. If SQN2HE < GLC then HE sets SQN = SQN1HE || GLC. If SQN2HE  GLC then HE sets SQN = (SQN1HE +1) || GLC.
Then SQNHE  is reset to SQN. 
(5)	The sequence number SQN is accepted by the USIM if and only if SQN >SQNMS holds.
(6)	If the mechanism described in Annex C.4 (lists of sequence numbers in the USIM) is used and if SQNLO denotes the lowest sequence number in the list then (5) becomes: 
The sequence number SQN is now accepted by the USIM if and only if SQN >SQNLO holds and SQN is not in the list.
(7)	If the mechanism described in Annex C.5 (protection against counter wrap-around) is employed then (5) becomes: 
The sequence number SQN is now accepted by the USIM if and only if SQN>SQNMS and 
SQN - SQNMS<  hold.
(8)	If both the mechanisms described in Annexes C.4 and C.5 are employed and if SQNHI denotes the highest sequence number in the list then (5) becomes: 
The sequence number SQN is now accepted by the USIM if and only if SQN>SQNLO and 
SQN – SQNHI <  hold and SQN is not in the list.
When parameters are appropriately chosen then this use of sequence numbers is compatible with the re-synchronisation procedure described in section 6.3.5 and the protection against wrap around of counters described in Annex C.5, and it is not required to conceal this type of sequence numbers.
“
It is shown in the next sections that the statements in the preceding paragraph hold.
3	Examples
All lengths in this section are bit lengths. 
1)	Let n = length of SQN2 = 0. This is the case of purely individual sequence numbers as described in section 6.3 and Annex C.1 of [1]. Here, no global counter GLC is needed, of course. For the purpose of applying rule (4) in section 2 we may assume that GLC = 0 constantly. 
2)	Let  length of SQN1 = 0. This is the case of purely global sequence numbers as described in Annex C.2 of [1]. Here no individual counters SQNHE are needed, of course. For the purpose of applying rule (4) in section 2 we may assume that SQNHE = 0 for all users always. 
3)	Let  length of SQN1 = 24 and n = length of SQN2 = 32. 232 seconds equals about 128 years. Consequently, GLC will never wrap around under normal conditions, and the sequence numbers progress as for the case fo a purely global counter. SQN1 will be increased only in cases of AuC failures. 
4)	Let length of SQN1 = 24 and n = length of SQN2 = 24. 224 seconds equals about half a year, consequently SQN1 will be increased about once in half a year.
The parameters should be chosen such that is SQN2 long enough so that the sequence number does not betray significant information about the user (cf. section 4) and SQN1 is long enough so that counter wrap around protection is provided (cf. section 6). 
4	Information on user identities gained from generalised sequence numbers 
If the length n of the global part SQN2 is sufficiently high then many users will share the same sequence number SQN at a given time, hence the knowledge of the sequence number does not give significant information about the user’s identity. Consequently, concealment of the sequence number using an anonymity key is no longer needed.
In more detail: Let us assume that the global counter GLC from which the global part SQN2 of the sequence number SQN is derived is based on a universal clock with the granularity of one second and that there is at least one second between the request for the generation of one authentication vector and the next (except for the generation of batches). GLC then it wraps around every 2 n seconds. If a user requests authentication at least once every 2 n-1 seconds then SQN1 will be increased by 1 the first time an authentication vector for the user is generated after the wrap-around of GLC, and SQN1 will remain constant until the next wrap-around of GLC. This means that SQN1-values of all such users differ at most by 1. The SQN2-values are the same anyway as they are derived from the global counter.
Consider example 3 in section 3:  If users who subscribe to the system later start with the value 
SQN = 0 || GLC then, in normal operations, all users share the same sequence number at a given time.
Consider example 4 in section 3: users who request authentication at least once in three months can have only one of two possible SQN-values when new authentication vectors are generated for them. Users who do not always fulfill this condition will have a lower SQN1-value, but will blend in with other users who subscribed to the system later, assuming that all users start at SQN = 1. 
Hence, in both examples, there is no need for the concealment of the sequence number. 
When SQN1 is increased due to a failure in the AuC (e.g. if the counter SQNHE is set to a too high value which is not corrected by a re-synchronisation procedure) then indeed the user may stick out of the crowd, but as such failures are deemed very rare, and the consequences (the user being traceable now) are much less serious than the assumed cause (security problem in the AuC) this may be considered acceptable.
Note: Some limited information on the user’s identity may still be gained from eavesdropping on sequence numbers. Users from different networks may use different GLC time, and such users may be rare in a certain area. If batches of authentication vectors are generated with a contiguous string of sequence numbers then the corresponding authentication events can be chained by an eavesdropper. (This is also true for the case of purely global sequence numbers.) Both is deemed acceptable. 
5	Compatibility with re-synchronisation procedure 
This procedure is described in section 6.3.5 of [1]. We briefly recapitulate:
“Upon receiving a synchronisation failure message from the user, the SN/VLR sends an authentication data request with a “synchronisation failure indication” to the HE/AuC, . . .  
When the HE/AuC receives an authentication data request with a “synchronisation failure indication” it acts as follows: The HE/AuC verifies ... [the parameters sent to the HE/AuC]. If the verification is successful, but SQNMS is such that SQNHE is not in the correct range then the HE/AuC resets the value of the counter SQNHE to SQNMS. Otherwise, the HE/AuC leaves SQNHE unchanged. 
In all cases the HE/AuC sends an authentication data response with a new batch of authentication vectors to the SN/VLR. If the counter SQNHE was not reset then these authentication vectors can be taken from storage, otherwise they are newly generated after resetting SQNHE.”
This re-synchronisation procedure is fully compatible with the use of generalised sequence numbers. The resetting of SQNHE can be done on a per user basis. The global counter GLC will not be affected by the reset. When authentication vectors for a particular user are newly generated after resetting SQNHE  then the procedure according to section 2 (4) is applied.
Note: The parameter RANDMS  (cf. subsection 6.3.3. of [1]) is only used to conceal the sequence number, but as concealment is no longer required (see section 4) if parameters are appropriately chosen it is no longer required either to store RANDMS  on the USIM and send it as part of the synchronisation failure message.
6	Compatibility with wrap around protection
A mechanism offering protection against the wrap around of the counter SQNMS in the USIM is described in Annex C.5 of [1]. We briefly recapitulate:
“The basic idea of the alternative sequence number handling is that the MS will not accept arbitrary jumps in sequence numbers. The sequence number SQN is accepted by the MS if and only if the following holds for some :  SQN > SQNMS  (as for alternative C.1) and SQN - SQNMS <  .     . . .
Conditions on   :
(1)	 shall be sufficiently large so that the MS will not receive any  SQN with SQN - SQNMS   if the HE/AuC functions correctly [it should be added: “ . . and so that an attacker without access to the HE/AuC cannot force this condition.”.  Remark: An attacker could try to force SQN - SQNMS    e.g. by soliciting and then intercepting and discarding sufficently many authentication vectors for a particular user.]
(2)	SQNmax / shall be sufficiently large to prevent that SQNMS ever reaches SQNmax during the lifetime of the USIM.”
Recall that condition (2) is meant to protect against catastrophic failures of AuC security where an attacker gains control over the generation of sequence numbers. The violation of condition (1) will result in a re-synchronisation procedure and a re-setting of the counter SQNHE. (2) ensures that an attacker can force a wrap around SQNMS only after at least SQNmax / communications with the USIM. 
When using generalised sequence numbers the mechanism above is applicable because the re-synchronisation procedure is available. But it has to be taken into account in the choice of  that the sequence numbers in the authentication vectors for a particular user are not contiguous (because the second part SQN2 of the sequence number is derived from a global counter). They therefore progress faster from the perspective of an individual user, and  has to be chosen larger than for purely individual sequence numbers.  has also to be chosen larger than the maximum value of SQN2. Otherwise a failure condition where SQN2 > GLC could result in an increase of SQN1 according to section 2 (4) and, consequently, to USIM lock out. 
Examples for the choice of : 
For example 4 of subsection 4, one could choose  = 228. For SQNmax = 248 , this would give 
SQNmax /  = 220 which seems sufficient protection against USIM lock-out.  = 224 would not be sufficient as it cannot be ruled out under normal conditions that a USIM does not carry out a successful authentication during a period of 224 seconds (equal to half a year). 
For example 3 of subsection 4,  has to be chosen larger than 232, e.g.  = 236.
7	The use of lists
7.1	General
Annex C.4 of [1]describes the use of lists when using a global counter. We briefly recapitulate:
“[The USIM]. . . keeps track of an ordered list of the b highest values is has received, . . . If a sequence number is received that is lower [should be added: or equal] than the lowest value in that list, it is rejected. If however, a sequence number is received that is larger than the lowest, . . .[it should continue: and is not in the list] it is accepted and included in the list. 
Using this mechanism, it is not required that a previously visited SN/VLR deletes the unused authentication vectors when a user de-registers from the network and may be more efficient as regards long distance signalling when a user abroad switches a lot between two serving networks.”
This approach also applies in exactly the same way to the use of generalised sequence numbers. 
The use of windows is not appropriate here because the sequence numbers for a particular user are no longer contiguous. Windows would therefore become quite large.
7.2	Enhanced list management
In analogy to the enhanced window management described in S3-99234, it is now possible to introduce an enhanced list management. This simply consists in the MS telling the SN/VLR the value of SQNLO , the lowest sequence number in the list, when an authentication is requested. The SN/VLR can then decide whether the authentication vectors it has in storage will still be accepted by the USIM. (This will be the case when the sequence number belonging to an authentication vector is greater than SQNLO, assuming that an authentication vector which is still in storage has not been used before.) Because the sequence number is not concealed there is no need for signalling back to the old VLR for translation of SQNLO into cleartext. So, the enhanced list management here does not affect the VLR-VLR interface. However, it does affect the the VLR-MS interface even if only to a small extent. 
7.3	Consequences of using lists in USIM
The disadvantage of using lists of sequence numbers in the USIM consists in the larger amount of storage required, compared to the use of windows. The reason is that in a list sequence numbers have to be stored explicitly in full length whereas for the window technique one bit per entry is sufficient. 
Example: The storage of the sequence numbers of length 48 bits corresponding to the last 100 authentication requests accepted by the USIM in a list would require 600 bytes on the USIM.

8	Conclusion
The proposed solution contains the existing schemes as specail cases. It offers significant advantages and simplifications over the existing schemes when the parameters are appropriately chosen and should therefore be included in [1]. Among the examples in section 3, example 4 seems to be the one to be preferred as it provides the desired properties with the shortest sequence number length.

Reference
[1] 3G TS 33.102 version 3.1.0, “3G Security; Security Architecture”, 1999-07.