On the (In)Security of 4G - Part IX: Cryptographic Overview, Key Hierarchy and Key Derivation of 4G

Table of Contents

Cryptographic Overview - 3G and Before

Prior to 3G systems, most cryptographic algorithms were not publicly disclosed, building upon “Security by Obscurity”. Thus the security of a system relies on the design or implementation secrecy. Kerckhoffs’s principle from 1883 states that a cryptosystem should be secure even if everything about the system, except the key, is publicly disclosed.
A little out of context: The security design of 2G and prior-3G-systems happened in the 1980s. So the people designing security back then just ignored advise from some of the greatest minds behind information theory? Shannon wrote a paper entitled "Communication Theory of Secrecy Systems" in 1949, stating all of the above mention, namely that it is a bad idea to hide your security algorithms. One of my professors back in university used to phrase it with: “What would you do? Hide the key under you mattress at home and hope noone would find it there? Or would you rather build a safe, show it to the public, allow all the world to scrutinize it and only when and if the greatest minds, thieves, codebreakers, hackers could not make a dent in it over decade, would you begin to consider it somewhat secure?”
Alright, at least with Universal Mobile Telecommunications System (UMTS), the security algorithms were publicly disclosed. There we find the UMTS Encryption Algorithm (UEA), consisting of UEA1, a 128-bit block cipher called KASUMI (KASUMI Block Cipher Description, How to Break it) and UEA2, a stream cipher similar to SNOW 3G (SNOW 3G Stream Cipher Description, How to Somewhat Break it). UMTS Integrity Algorithms (UIA) describe UIA1, Message Authentication Codes (MAC) based on KASUMI, an UIA2, which calculates MACs based on SNOW 3G.

Cryptographic Overview - 4G

Similar to UMTS Encryption and Integrity keys, 4G now has three sets of algorithms for those two tasks, EPS Encryption Algorithms (EEA) and EPS Integrity Algorithms (EIA). EEA1 and EIA1 are SNOW 3G related, EEA2 and EIA2 are Advanced Encryption Standard (AES) related (Counter mode for encryption, AES-CMAC for integrity), EEA3 and EIA3 are Stream Cipher called ZUC related.
Alright now we know the algorithms to protect confidentiality and integrity. What about keys and key management?

Cryptographic Keys - 4G

In general security requirements for 4G keys foresees for the “use of encryption and integrity protection algorithms for AS and NAS protection having keys of length 128 bits and for future use the network interfaces shall be prepared to support 256 bit keys”. Thus some keys are 128 bit long, some 256 bit.

4G Cryptographic Keys Hierarchy

There is a clear key hierarchy in 4G:

4G Cryptographic Keys Derivation

It all start with a pre-shard Master Key (K), that is shared between the network (AuC) and the user (Universal Subscriber Identity Module (USIM)), via the “SIM-card” or more precisely when the Universal Integrated Circuit Card (UICC) is manufactured and then handed out to the user (for more details, look at part VII and part VIII). From K, the Integrity Key (IK) and Cipher Key (CK) are derived. IK and CK are used between UE and the Home Subscriber Server (HSS). From IK and CK the MME Base Key K_ASME is derived. K_ASME is used to derive the NAS Integrity Key (K_NASint) and the NAS Encryption Key(K_NASenc). These keys are mainly used to secure UE <-> MME communications in the NAS. K_ASME is also used to derive keys used to protect the UE <-> eNB communication. This starts with the eNB Base Key K_eNB and the Next Hop Key (NH). One step further down in the hierarchy, the K_eNB is used to derive the Radio Resource Control (RRC) Confidentiality Key (RRC_enc) and the RRC Integrity Key (RRC_int) to protect RRC (mainly control data) traffic. Lastly user plane traffic needs to be protected and thus the K_eNB is used once more to derive the User Plane Integrity Key (K_UPint) and the User Plane Confidentiality Key (K_UPenc). These two last keys are mainly used to protect user plane traffic on the Packet Data Convergence Protocol (PDCP) layer.

In figure 3, all these steps are shown from the network perspective. Similar derivation steps happen within the ME, however from a system perspective it is more interesting for us to see the derivation process per network entity. It suffices to know, that these steps also happen within the ME.

Apart from the described keys above, figure 3 also shows two more boxes: Key Derivation Function (KDF) and Truncation (Trunc).

Key Derivation Function (KDF) in depth

The KDF for each key is explained in depth in TS 33.401, in appendix A and the KDF itself is detailed in TS 33.220 in appendix B.2. We have several input parameters for the KDF:

• FC: “FC is used to distinguish between different instances of the algorithm” In TS 33.401 - Appendix A.2, we find e.g. FC=0x10 for the K_ASME key derivation or in TS 33.401 - Appendix A.3 FC=0x11 for the K_eNB key derivation.
• P0 … Pn: These are n+1 input parameter encodings. For instance in TS 33.401 - Appendix A.2, we find P0=SN id, P1=SQN ⊕ AK for the K_ASME key derivation. “Sequence Number (SQN) and the Anonymity Key (AK) is sent to the UE as a part of the Authentication Token (AUTN)” (We will detail out the authentication procedure in depth below)
• L0 … Ln: These are the two-octet representations of the length of the corresponding input parameter encodings P0.. Pn. Again in TS 33.401 - Appendix A.2 we find L0=len(SN id) (i.e. 0x00 0x03) and L1=len(SQN ⊕ AK) (i.e. 0x00 0x06).

These input parameter build an input string S, which is constructed as follows: S = FC || P0 || L0 || P1 || L1 || ... || Pn || Ln

Overall the final derived key is computed as follows: derived key = HMAC-SHA-256_Key(S) The key “Key” used for the Hash-based Message Authentication Code (HMAC) with the Secure Hash Algorithm (SHA) computation comes from the key “above” in the key hierarchy e.g. for K_ASME the input key Key “shall be equal to the concatenation CK || IK of CK and IK”.`

Key Truncation Function (Trunc) in depth

In TS 33.401 we find the following definition: “The function Trunc takes as input a 256-bit string, and returns a truncated output as defined in Annex A.7.”
Funny enough, in Annex A.7 “Algorithm key derivation functions”, we find nothing about “Trunc”.
However in chapter 6.2, we find the following definition “The function Trunc takes as input a 256-bit string [… and] the key is truncated and the 128 least significant bits are used.”

Summary

After a brief look on the 4G security architecture and its features in the last post, we now looked at its key hierarchy and key derivation. We see 4G strictly follows the cryptographic maxim “one key per purpose”. At the end, we show exactly how keys are derived on each layer and for each purpose. Next time, we are going to look at 4G’s Authentication and Key Agreement (AKA) Procedure.

Here you can read Part VIII and Part X.

See you soon. :)

Abbreviations

• Advanced Encryption Standard (AES)
• Anonymity Key (AK)
• Authentication and Key Agreement (AKA)
• Authentication Token (AUTN)
• Cipher Key (CK)
• eNB Base Key (K_eNB)
• EPS Encryption Algorithms (EEA)
• EPS Integrity Algorithms (EIA)
• Hash-based Message Authentication Code (HMAC)
• Home Subscriber Server (HSS)
• Integrity Key (IK)
• Key Derivation Function (KDF)
• Message Authentication Codes (MAC)
• MME Base Key (K_ASME)
• NAS Encryption Key(K_NASenc)
• NAS Integrity Key (K_NASint)
• Next Hop Key (NH)
• Packet Data Convergence Protocol (PDCP)
• Projects (optional)
• Radio Resource Control (RRC)
• RRC Confidentiality Key (RRC_enc)
• RRC Integrity Key (RRC_int)
• Secure Hash Algorithm (SHA)
• Sequence Number (SQN)
• Truncation (Trunc)
• UMTS Encryption Algorithm (UEA)
• UMTS Integrity Algorithms (UIA)
• Universal Integrated Circuit Card (UICC)
• Universal Mobile Telecommunications System (UMTS)
• Universal Subscriber Identity Module (USIM)
• User Plane Confidentiality Key (K_UPenc)
• User Plane Integrity Key (K_UPint)