Authentication is a process by which UE and Network check if the other party has right authority to communicate each other. It is very similar to 'login process' when you use a computer. The only difference is that in computer login process, only the computer is checking your authority and you are not technically checking the PC's authority (Of course, you have your own 'will' to use it or not to use it.. but it is not the technically determistic authentication algorithm). In LTE (in WCDMA as well), Network authenticate UE and UE also authenticate the Network. Authetication on both side should be passed for the communication to proceed. Followings are the list of topics that will be described in this page.

• Overall Process
• [Figure 1] Overall protocol sequence for Authentication (Authentication Key Generation and Exchange)
• [Figure 2] USIM Parameters and Derived Parameters for Authentication
• What is inside AUTN, and how does the UE check it ?
• Key Generation for Test USIM (based on 34.108)
• [Table 1] Input and output parameters of 3GPP Test USIM Algorithm
• [Figure 3] Calculation of Authentication Key(AUTN) and IK,CK based on 3GPP 34.108 TestUSIM Algorithm
• Example
• Key Generation for Milenage
• [Figure 4] Overview of Milenage Algorithm
• [Table 2] Input and output parameters of Milenage Algorithm
• Testing with Uknown USIM Algorithm / Parameters
• [Table 3] Input and output parameters of Unknown Algorithm/Unknown Input
• What happens after authentication succeeds ?
• What can go wrong, and what does the UE send back ?
• Reference

Overall Process

Authentication" process is a process similar to 'log in' process when you use a computer. In C2K and GSM, this authentication process is 'uni-directional', meaning that only Network authenticate UE and UE does not authenticate the network. As you may easily guess, this would cause a serious security problem. If I make a fake network which accept any UE, I can cheat a UE to camp on the fake network rather than the one the UE is supposed to camp on to. (But this kind of 'uni directional' authentication would make it so easy to test a UE using network simulator -:)

To improve this security issues, in LTE (in WCDMA as well) they do 'bi-directional' authentication, meaning that UE has to pass the authentication process and Newtork also has to pass the process as well.

The overall authentication process  is as follows.

[Figure 1] Overall protocol sequence for Authentication (Authentication Key Generation and Exchange)

There are three main components of this authentication process :

i) Input Parameters

ii) Authentication Algorithm

iii) Output Values (calcuated by Authentication Algorithm using the Input Parameters).

Both UE and Network uses the same Input Parameters and the same Authentication Algorithms, so they both should produce the same Output Values, otherwise Authentication fails.

One thing you have to keep in mind is that UE and Network exchange only Input Parameters and Output values, not the authentication Algorithm. Authentication Algorithm on UE side is stored in USIM and Authentication Algorithm on NW side is stored in Authentication Center. Both UE and NW just assume that they would use the identical algorithms.

Normally use use diffent Authentication Algorithm for testing and for live network. The most commonly used algorithm for testing is what we often call "Dummy XOR" algorithm which is defined in 36.508 section 4.9 Common test USIM parameters for LTE and 34.408 section 8 Test USIM Parameters for WCDMA.

The most common used algorithm in live network (as far as I know) is Milenage algorithm.

One example of Authentication Request and Authentication Response is as follows. You would notice that RAND, AUTN are carried by Authentication Request message and RES value is carried by Authentication Response.

< Authentication Request > NAS capture. Field values come from a live capture, not from the specification.

NAS_LTE:EMM,Authentication request
Authentication request ::= DIVISION
  +-Security header type ::= V
  | +-Security header type ::= CHOICE [Plain NAS message, not security protected]
  +-EPS mobility management protocol discriminator ::= V
  | +-Protocol discriminator ::= PD [7]
  +-Authentication request message type ::= V
  | +-Message type ::= MSG [52]
  +-Spare half octet ::= V
  | +-Spare half octet ::= FIX [0]
  +-NAS key set identifier ASME ::= V
  | +-TSC ::= CHOICE [native security context (for KSI ASME)]
  | +-NAS key set identifier ::= CHOICE [possible values for the NAS key set identifier 0]
  +-Authentication parameter RAND ::= V
  | +-Octet1-Octet16 ::= DIVISION
  |   +-RAND value ::= OCTETARRAY SIZE(16..16) [A3DE0C6D363E30C364A4078F1BF8D577]
  +-Authentication parameter AUTN ::= LV
    +-Octet1 ::= DIVISION
    | +-Length of AUTN contents ::= LEN (0..255) [16]
    +-Octet2-Octet17 ::= DIVISION
      +-AUTN ::= OCTETARRAY SIZE(0..16) [5E726B56B4EC9001A3CF2E5E726BC6B5]
        

< Authentication Response > NAS capture. Field values come from a live capture, not from the specification.

NAS_LTE:EMM,Authentication response
Authentication response ::= DIVISION
  +-Security header type ::= V
  | +-Security header type ::= CHOICE [Plain NAS message, not security protected]
  +-EPS mobility management protocol discriminator ::= V
  | +-Protocol discriminator ::= PD [7]
  +-Authentication response message identity ::= V
  | +-Message type ::= MSG [53]
  +-Authentication response parameter ::= LV
    +-Octet1 ::= DIVISION
    | +-Length of Authentication response parameter contents ::= LEN (0..255) [8]
    +-Octet2-17 ::= DIVISION
      +-RES ::= OCTETARRAY SIZE(0..16) [A3CF2E5E726B56B4]
        

As you see from the two messages above, there are only three values which plays critical roles. RAND, AUTN, RES. RAND is not a calculated value.. it is just randomly assinged by network Authentication Center and AUTN and RES is calculated by special algorithm as illustrated below. (If you want to know the very detailed process, refer to 3GPP TS 35.206 V4.0.0 (2001-04) and analyze the source code line by line. If you just want to get general understanding, following illustration would be enough.)

[Figure 2] USIM Parameters and Derived Parameters for Authentication

The drawing above takes the same parameters and shows where each one is produced. The USIM feeds OPc, K, RAND, SQN and AMF into f1, which returns MAC-A. It feeds OPc, RAND and K into f2345, which returns RES, CK, IK and AK. The bottom row gathers the three values that leave the USIM for the air interface: AUTN = (SQN XOR AK) || AMF || MAC-A. Everything else stays inside the card.

What is inside AUTN, and how does the UE check it ?

[Figure 2] gives AUTN as SQN Xor AK || AMF || MAC, and that one line carries the whole of mutual authentication. It is worth unpacking. Almost every authentication problem you will debug is one of those three fields going wrong, and each field fails in its own way.

The three fields are different sizes. SQN Xor AK is 48 bits, AMF is 16 bits, and MAC is 64 bits. Together they make the 128 bits that [Figure 2] gives for AUTN. Each one answers a different question.

MAC answers the question "did someone holding K build this ?". [Figure 2] defines it as f1K(SQN||RAND||AMF), so only a party that knows K can produce it. This is the field that authenticates the network to the UE. Without it, the fake network described in the Overall Process section above would work exactly as the author says it does.

SQN answers the question "is this challenge fresh ?". A MAC on its own does not stop a replay. An attacker could record one valid RAND and AUTN pair, send it again, and it would still verify. The sequence number moves forward on every authentication, so the USIM can refuse a vector it has already accepted.

AMF answers the question "what is this vector for ?". In LTE a single bit of it decides whether the vector is usable at all. The section on failures below comes back to that bit.

AK is the parameter that is not really in AUTN, and it is easy to miss why it exists at all. SQN counts authentications for one subscriber, so sending it in the clear would leak how often that subscriber attaches. 33.102 says the anonymity key conceals the sequence number, because the sequence number may otherwise expose the identity and location of the user. So the network sends SQN Xor AK, and the USIM recovers SQN by computing AK for itself. 33.102 is careful to add that this protects against passive attacks only. Where no concealment is wanted, f5 returns zero, AK is zero, and SQN travels in the clear.

The USIM works through AUTN in a fixed order, and 33.102 clause 6.3.3 sets that order out. The steps below are worth following with [Figure 2] beside them.

• Compute the anonymity key AK = f5K(RAND).
• Recover the sequence number as SQN = (SQN Xor AK) Xor AK.
• Compute XMAC = f1K(SQN || RAND || AMF).
• Compare XMAC with the MAC carried inside AUTN. If the two differ, the USIM abandons the procedure and reports a failure.
• Check that the recovered SQN is in the correct range. If it is not, the USIM reports a synchronisation failure instead.

Only after those checks pass does the USIM produce RES, and only then does the network get to compare RES against its own XRES. Notice the order, because it is the opposite of what the message names suggest. The UE authenticates the network first, and the network authenticates the UE second. You can see that in [Figure 1]. The note numbered 2 on the UE side checks the network's result before the UE sends the Authentication Response.

• MAC authenticates the network : only a party holding K can produce f1K(SQN||RAND||AMF), so a fake base station cannot build a valid AUTN.
• SQN is what stops a replay : a recorded RAND and AUTN pair still passes the MAC check. The sequence number is what makes each challenge single-use.
• AK hides the counter, not the key : it conceals SQN, which would otherwise leak how often a subscriber attaches. 33.102 limits that protection to passive attacks.
• The UE checks first : the USIM verifies MAC and SQN before it computes RES, so the network is authenticated before the UE is.

Key Generation for Test USIM (based on 34.108)

Most of the USIMs that you are using with Test Equipment (i.e, Cellular Network Simulator) is based on what we call 3GPP Test USIM or Dummy XOR USIM. (Note : Recently.. espcially for LTE, some network operator requires using Test USIM using Milenage Algorithm. It might be because they want to use same/similar algorithm that they are using in live network). In this section, I will show you how to generate Authentication Key (AUTN) using 3GPP Test USIM algorithm and what kind of parameters are required for this. Since 3GPP Test USIM algoirthm is so simple and requires very small set of parameter, it is easy to implement and easy for debugging.

[Table 1] Input and output parameters of 3GPP Test USIM Algorithm

Followings are Parameters for the Input and Output of the 3GPP Test USIM Algorithm. Pay special attention to which parameter you have to know from your test USIM.

If you need to create a customized USIM or USIM Profile, you need to ask your USIM vendor if they can hardcode all the input parameters in the SIM and ask Test Equipment Vendor if user can specify all of the input parameters arbitrarily. (As far as I am experienced, most of the equipment vendor allow user to specify any K value and use the internal/hardcoded value for AMF, SQN. But some equipment vendor allows the user to set other input parameters as well)

NOTE 1 : IMSI is stored in USIM and play an important roles in some part of signaling, but it is not used in Authentication Process.

NOTE 2 : OP, OPc is not used in Test USIM Algorithm

[Figure 3]  Calculation of Authentication Key (AUTN) and IK, CK based on 3GPP 34.108 Test USIM Algorithm

Following is procedure of calculating Authentication Key (AUTN) and IK, CK based on 3GPP 34.108 Test USIM Algorithm.

< Example >

Following is an example USIM parameter and the result of each step described above. You would not need any special program to try this. Just try with your hand.. if you are on a boring trip, this can be very good for killing time -:)

Key Generation for Milenage

Refer to 3GPP TS 35.206 and you can get the C implementation of this algorithm and the code would tell you everything. Before reading that code, though, it helps to carry the shape of the algorithm in your head. Milenage is not a new cipher. It is a construction around a single 128-bit block cipher, which the specification writes as E_K. Milenage calls that cipher six times with different inputs, and those six calls produce everything the authentication needs.

[Figure 4] Overview of Milenage Algorithm

Following illustration is based on 35.206 Annex 1 and I added a couple of items.

NOTE : In every USIM parameter setting, the K value is one of the most important parameter. Where is the K in this diagram ?  Actually the K is used to derive E_K value.

Reading [Figure 4] from the top makes the shape of Milenage clear. RAND is combined with OPc and encrypted under K to give one temporary value, and that value feeds five parallel branches. Every branch does the same three things in the same order. It exclusive-ors with OPc, rotates by r1 to r5, exclusive-ors with c1 to c5, then encrypts under K again. Only the rotation and the constant differ between branches, which is why one block cipher produces seven different outputs.

The outputs are where the branches stop looking alike. The first branch yields f1 as MAC-A and f1* as MAC-S. The second yields f5 as AK and f2 as RES. The third and fourth yield CK and IK. The fifth yields f5*, a second anonymity key used only during re-synchronisation. The inset at the top right is the author's addition rather than part of 35.206 Annex 1. It shows OPc derived from OP and K, which is why a USIM can store either one.

[Table 2] Input and output parameters of Milenage Algorithm

Followings are Parameters for the Input and Output of the Milenage Algorithm.  This is what most of network operator uses. Pay special attention to which parameter you have to know from your test USIM.

If you need to create a customized USIM or USIM Profile, you need to ask your USIM vendor if they can hardcode all the input parameters in the SIM and ask Test Equipment Vendor if user can specify all of the input parameters arbitrarily. (As far as I am experienced, most of the equipment vendor allow user to specify any K, OP/OPc value and use the internal/hardcoded value for all other parameters. But some equipment vendor allows the user to set other input parameters as well. I haven't seen any equipment to allow user to set c1,c2,c3,c4,c5 and r1,r2,r3,r4,r5. They tend to use those values from 3GPP sample source code)

NOTE 1 : IMSI is stored in USIM and play an important roles in some part of signaling, but it is not used in Authentication Process.

Testing with Uknown USIM Algorithm / Parameters

In some rare case, people wants to test protocol stack without disclosing any information about Authentication Algorithm / parameters. If it is GSM or CDMA which does not require mutual Authentication (i.e, both UE side Authentication and Network side authentication needs to be completed), you can just configure the test equipment to skip the Authentication process. However, if you are working with WCDMA or LTE it is not possible for only one side (UE or Network) to skip the authentication unless both side agrees to skip the procedure. In order to let the test equipment to work with this kind of USIM, you need to get provided with the following output parameters and hardcode the authentication parameter on test equipment.

[Table 3] Input and output parameters of Unknown Algorithm/Unknown Input

In this case, you may ask test equipment vedor if the equipment can configure following output parameters directly. and ask USIM vendor to configure USIM to use a predefined values for the following parameters all the time.

Two things have to hold for that to work, and neither is obvious from the table above. The first is RAND. Every output in the table depends on it. So a USIM that really computes will return different values for every new challenge. Fixed outputs therefore only match under one of two conditions. Either the USIM returns them whatever RAND arrives, or the equipment is pinned to a single RAND for the whole session. That is the work the phrase "all the time" above is doing, and it is worth confirming with the USIM vendor rather than assuming it.

The second is SQN. In a live network the sequence number advances on every authentication, and the USIM checks the recovered SQN against its own range. A fixed AUTN carries one fixed sequence number. A USIM applying the live rule would reject the second authentication of the session as out of range. Test USIMs freeze SQN for exactly this reason, which the notes under [Table 1] and [Table 2] already mention. Here that freeze is not a convenience. It is a requirement.

What you give up is worth stating plainly. Without a working algorithm behind the USIM, you can no longer produce the failure paths described further down this page. A deliberately wrong MAC, an out-of-range SQN and a cleared separation bit all need a real algorithm behind them. This configuration gets a protocol stack through authentication so that the rest of the call can be exercised. It is not a way to test authentication itself.

• The equipment never needs the algorithm : it only needs the output values, so fixing those is enough to get a call through.
• RAND has to be pinned or ignored : every output depends on RAND. Hardcoded values only match if the USIM returns them whatever challenge arrives.
• SQN must be frozen, not merely fixed : a hardcoded AUTN repeats one sequence number. A USIM applying the live range check would reject it on the second run.
• You give up the failure cases : a wrong MAC, an out-of-range SQN and a cleared separation bit all need a real algorithm. This setup exercises the stack, not the authentication.

What happens after authentication succeeds ?

[Figure 1] ends by saying that UE and network can now calculate IK and CK. For LTE that is true but incomplete, because E-UTRAN never uses CK and IK directly. One more derivation sits between them and the keys that actually protect NAS and RRC. That step is what makes an LTE authentication vector different from a UMTS one.

CK and IK come out of the same USIM functions that UMTS uses. That is why one algorithm description serves both systems, and why this page can cover them together. What LTE adds is K_ASME. 33.401 clause 6.1.1 puts that derivation in the ME rather than in the USIM. The USIM returns RES, CK and IK, and the ME then computes K_ASME from CK, IK and the serving network's identity.

The inputs are worth naming, because one of them carries the security argument. 33.401 Annex A.2 gives the input key as CK || IK, and the other parameters as FC = 0x10, the SN id, and SQN Xor AK. The SN id is simply MCC and MNC packed into three octets. Binding it into the key is what stops a vector issued for one serving network producing working keys in another. 33.401 states the consequence directly: SN id binding implicitly authenticates the serving network's identity when the derived keys from K_ASME are successfully used.

K_ASME is 256 bits, and it is the root of the LTE key hierarchy rather than a key applied to any message. From it the UE and the MME derive the NAS ciphering and integrity keys, and K_eNB for the access stratum. Annex A.3 derives K_eNB with FC = 0x11 and the uplink NAS COUNT. That is why a key change on the fly needs a NAS COUNT both sides agree on.

One more parameter in the capture above belongs to this step. The NAS key set identifier, KSI_ASME, is not a key. It is a short label for the K_ASME that this run produced. A later procedure can then name the security context without repeating the whole exchange.

• CK and IK are not the LTE keys : they are inherited from UMTS AKA, and E-UTRAN uses K_ASME derived from them instead.
• The ME derives K_ASME, not the USIM : the USIM hands over RES, CK and IK. 33.401 places the key derivation function in the ME.
• The serving network identity is an input : MCC and MNC go into the derivation. A vector bound to one network cannot produce working keys in another.
• KSI_ASME names the context : the NAS key set identifier in the capture above labels the resulting K_ASME rather than carrying any key material.

What can go wrong, and what does the UE send back ?

Three things can fail in an authentication challenge, and the UE reports each one differently. 24.301 clause 5.4.2.6 lists all three, and they map one for one onto the fields of AUTN taken apart earlier. Reading a failure is therefore a matter of working out which field the USIM rejected.

The first is a MAC failure. The USIM computed XMAC and it did not match the MAC inside AUTN, so whoever built the challenge did not hold K. The UE answers with an AUTHENTICATION FAILURE message carrying EMM cause #20 "MAC failure", and starts timer T3418.

The second is a synchronisation failure. The MAC was correct, so the challenge did come from a party holding K, but the sequence number was out of range. The UE answers with EMM cause #21 "synch failure", and this is the only one of the three that sends a parameter back. The USIM supplies AUTS, which 33.102 defines as Conc(SQN_MS) || MAC-S. The concealed counter is SQN_MS Xor f5*K(RAND), and MAC-S is f1*K(SQN_MS || RAND || AMF). That is where the f1* and f5* branches of [Figure 4] are used, and it is the only place they are used. AUTS carries the UE's own counter back to the network, so the two sides can re-synchronise instead of retrying blindly.

The third is specific to LTE. 33.401 clause 6.1.1 requires the ME to check the separation bit in the AMF field of AUTN. That bit is bit 0 of AMF, and it has to be set to 1. If the bit is 0, the vector was not built for EPS, and the UE answers with EMM cause #26 "non-EPS authentication unacceptable". The worked example above shows this passing. Its AMF is 8000 in hex, or 1000 0000 0000 0000 in binary. The top bit is set, so the vector is acceptable for E-UTRAN. The same example with an AMF of 0000 would authenticate correctly on a WCDMA tester and be refused by an LTE one.

None of the three fails silently, which is what makes them tractable in a log. Each one names its cause in an AUTHENTICATION FAILURE message, and Authentication Failure works through a captured example of each.

• Each failure names one field of AUTN : MAC failure points at the MAC, synch failure at SQN, and non-EPS authentication unacceptable at the AMF.
• Only synch failure sends data back : the UE returns AUTS so the network can re-synchronise on the UE's own counter instead of retrying blindly.
• AUTS is where f1* and f5* earn their place : the two starred branches of [Figure 4] exist for re-synchronisation and for nothing else.
• The separation bit makes a vector LTE-specific : bit 0 of AMF must be 1 for E-UTRAN. The example's AMF of 8000 is accepted, and 0000 would draw cause #26.

Reference

The clause and table numbers are given beside each claim above, so the wording can be checked rather than taken on trust. The algorithm specifications the figures follow, 34.108 and 35.206, are named in the body where the page uses them.

• 33.102 - 3G Security; Security architecture, v19.1.0. Clause 6.3.3 is the USIM's AUTN verification, in the order used above, and the definition of the AUTS re-synchronisation token.
• 33.401 - 3GPP System Architecture Evolution (SAE); Security architecture, v19.2.0. Clause 6.1.1 is EPS AKA and the separation bit rule. Annex A.2 is the K_ASME derivation and Annex A.3 the K_eNB derivation.
• 24.301 - Non-Access-Stratum (NAS) protocol for EPS; Stage 3, v20.0.0. Clause 5.4.2.6 lists the three causes the UE may return, with EMM causes #20, #21 and #26.