|Project |IEEE 802.16 Broadband Wireless Access Working Group |
|Title |Nonce based TEK Update for Handover |
|Date Submitted |2008-01-21 |
|Source(s) |Stavros Tzavidas |Voice: +1-847-632-4313 |
| | |E-mail: stavros.tzavidas@motorola.com |
| |Motorola Inc. | |
| | | |
| |1501 W. Shure Dr. | |
| |Arlington Heights IL 60004 | |
| | | |
|Re: |IEEE 802.16 Working Group Letter Ballot Recirc #26a |
|Abstract |This contribution identifies several problems with the currently existing procedures for updating Traffic Encryption Keys (TEKs) during HO. |
| |More specifically, we identify a security vulnerability when TEKs are shared between the Serving and the Target BS, and we also identify |
| |problems with TEK update through RNG-RSP in the case of fully optimized HHO. We propose a solution that mitigates both problems by updating |
| |TEKs through the exchange of nonces prior to HO. |
|Purpose |Accept the proposed specification changes on IEEE P802.16Rev2/D2 |
|Notice |This document does not represent the agreed views of the IEEE 802.16 Working Group or any of its subgroups. It represents only the views of |
| |the participants listed in the “Source(s)” field above. It is offered as a basis for discussion. It is not binding on the contributor(s), who|
| |reserve(s) the right to add, amend or withdraw material contained herein. |
|Release |The contributor grants a free, irrevocable license to the IEEE to incorporate material contained in this contribution, and any modifications |
| |thereof, in the creation of an IEEE Standards publication; to copyright in the IEEE’s name any IEEE Standards publication even though it may |
| |include portions of this contribution; and at the IEEE’s sole discretion to permit others to reproduce in whole or in part the resulting IEEE|
| |Standards publication. The contributor also acknowledges and accepts that this contribution may be made public by IEEE 802.16. |
|Patent Policy |The contributor is familiar with the IEEE-SA Patent Policy and Procedures: |
| | and . |
| |Further information is located at and . |
Nonce based TEK Update for Handover
Motorola

Introduction – Problem Description

Several methods exist in the standard [IEEE802.16-Rev2/D2] for updating Traffic Encryption Keys during Hard Handover (HHO). When low HHO delay is desired, as is commonly the case, .the two available solutions are TEK sharing and TEK update through SA-TEK-Update TLV in RNG-RSP. Unfortunately, both methods are problematic as we explain in the following.

TEK Sharing (Bit #1=1 and Bit #2=1 in HO Process Optimization TLV)
The standard allows the Serving BS (S-BS) and the Target BS (T-BS) to share TEKs. This approach suffers from the following problems: • When TEKs are shared between S-BS and T-BS the standard offers no method of correctly and securely coordinating the PN space (PN: packet number, described in section “7.5.1.2.2 Packet number PN”) associated with each TEK. This problem has apparently been overlooked in the standard and opens up the possibility of replay attacks. • TEK sharing introduces security dependencies between BSs. If TEKs are compromised in one BS, then the MS becomes vulnerable even if it has moved to a different BS. This stands in contrast with the way the rest of the keys in a Security Association are managed, where significant efforts have been made to ensure key independence between BSs (keys derived from AK, which is different for each BS).

TEK update via RNG-RSP (Bit #1=1 and Bit#2=0 in HO Process Optimization TLV)
When a TEK update is desired during HHO, the preferred method is through SA-TEK-Update TLV in the RNG-RSP MAC Management Message sent by T-BS to MS. This method is depicted in Fig. 1 below and is considered preferred because the alternative of performing SA-TEK-3-way handshake significantly increases HHO delay.
[pic]
Figure 1: Current TEK Update procedure for fully optimized HHO

When TEKs are updated through RNG-RSP, as depicted in Fig. 1, the MS cannot receive/send encrypted traffic before it receives and processes RNG-RSP from T-BS. This creates several problems: • Increased delay: the MS must wait for RNG-RSP and also must process the received TEKs before it can resume data • Increased overhead: during HO radio (RF) conditions are worse and TEK updates cost more in terms of over-the-air (OTA) resources. This problem is further aggravated by the large size of each TEK (128 bits).

Note that in both descriptions above, we concentrate on TEK updates for unicast SAs.

The proposed solution is described in the next section, while the required text changes are presented in the last section of this contribution.

Proposed Solution

We propose a method which allows TEKs to be updated during HHO without the security vulnerabilities of TEK sharing, nor the delay and overhead of TEK update through RNG-RSP.

The method is described in the following with reference to Fig. 2. in the following page.

According to the proposed TEK update algorithm, at some suitable point (defined in the following) and while the MS is still connected to the S-BS, MS and S-BS exchange a pair of nonces (termed “HO nonces”) to be used for the next HO.

A “nonce” is a random number generated using a reliable random or pseudo-random generator. Note that the PKMv2 security protocol in the standard already requires the MS and BS to implement reliable random number generators, for generating 64-bit nonces known as “MS_Random” and “BS_Random”. The nonces needed for the proposed solution (“MS HO nonce” and “BS HO nonce” in Fig. 2) can be generated using the mechanism that already exists for MS/BS_Random. If nonces longer than 64 bits are desired, each “nonce” can be easily formed by combining two MS/BS_Randoms, generated using the existing random number generators.

The MS sends to S-BS an N bit nonce. The S-BS also generates an equal length N bit nonce of its own and sends it to the MS in response. Both sides store the exchanged nonces until the next HO. No keys are derived during this nonce-exchange.

It should be emphasized that the described nonce exchange does not need to happen during HO preparation. It can instead happen long before a HO is needed. In fact, when exchanging nonces, MS and S-BS do not need to have any specific T-BS in mind (notice that no T-BS BS-ID is used as input to the nonce generation). The nonce exchange procedure simply applies to the next HO, whenever (and if) it happens, and regardless of the potential target(s) of this HO.

The timing of the HO nonce exchange can be arranged in a number of ways. One option is to allow the MS to choose an appropriate time. For example the MS can choose to perform the HO-nonce exchange when it deems that the RF conditions are good and the nonce exchange would not be costly in terms of overhead. Alternatively, the timing of the HO-nonce exchange can be regulated by the S-BS using the (already existing) mechanism of triggers (conditions), advertised by the S-BS in DCD. For example one condition can be “Initiate HO-nonce exchange when S-BS CINR > X threshold”. When the HO-nonce exchange happens at good radio conditions the overhead it creates is minimal compared to exchanges that happen right before or right after an HO.

When a HO is later initiated (according to criteria that are outside the scope of this contribution) the S-BS sends the agreed upon nonces (MS nonce and BS nonce) to the T-BS as part of the HO preparation backbone messages. When multiple target BSs are prepared, the S-BS sends the same nonces to all candidate T-BSs. MS and BS nonces can be sent over the backbone in the open and do not need to be encrypted, since (as will be apparent in the following) knowledge of nonces is not sufficient to derive the keys.

[pic]

Figure 2: Proposed TEK Update procedure (BS-initiated HO shown)

The MS and the T-BS(s) derive the new set of TEKs (termed “old TEK” and “new TEK”) for each SA as follows (the actions below are performed by both sides independently):

– Form two temporary nonces, combining bits from BS-HO-nonce and MS-HO-nonce: – “temp-nonce-1” = (first N/2 bits of MS-HO-nonce | first N/2 bits of BS-HO-nonce) – “temp-nonce-2” = (last N/2 bits of MS-HO-nonce | last N/2 bits of BS-HO-nonce) – – Encrypt old and new nonces with KEK: – old_TEK_temp = AESKEK(temp-nonce-1| SA_ID) – new_TEK_temp = AESKEK(temp-nonce-2 | SA_ID) – – Derive Old_TEK and New_TEK as follows: – Old_TEK ← truncate(old_TEK_temp, length of TEK) – New_TEK ← truncate(new_TEK_temp, length of TEK)

As can be seen from the calculation rules presented above, the input to both calculations is a combination of both MS and BS HO nonces to ensure that both sides contribute bits to both keys.

In general, for the calculation of TEKs we could have used a function of the form TEK = f(KEK, nonce, SA_ID). Here we choose f(KEK, nonce, SA_ID) = AESKEK(nonce, SA_ID) in order to minimize the changes needed to implement the proposed solution, with respect to current implementations of the standard. Indeed, the changes required for implementing the proposed solution are minimal, since the BS and MS already derive KEK, and already implement enryption using KEK.

The nonces exchanged during the HO-nonce phase, should be long enough so that probability of repeating a nonce during the lifetime of the AK is sufficiently small. In order to calculate the required nonce length, assume a highly mobile user who performs an HO every 5 sec, has max allowed AK (PMK) lifetime of 70 days and stays active during the whole lifetime of its AK (clearly an exaggerated scenario!). We can expect that such a user will perform 1,209,600 HOs during the lifetime of its AK, and clearly all TEK updates will be due to HOs (no TEK lifetime will ever expire). It can be shown that if N > 88 bits, then Prob( repeating a nonce after 1,209,600 trials) < 2.33E-15. Based on this calculation, 128 bit nonces should be sufficient.

Finally, for completeness of the solution, two additional scenarios need to be addressed: 1. When multiple T-BSs are prepared during the HO-preparation phase, the following rules apply: a. During HO preparation the same nonces are sent to all T-BSs b. If S-BS includes only a single T-BS in BSHO-REQ/RSP the MS assumes it can use the nonces only at that T-BS c. If S-BS includes multiple T-BSs in BSHO-REQ/RSP, it does not need to add extra information for each since the same nonces are used in all T-BSs. MS assumes it can use the nonces in all possible T-BSs. Note that this does not mean that the same TEKs will be derived in all possible T-BSs, because the AK and KEK are different in each T-BS. d. To prevent replay attacks in ping-pong situations, the HO-nonces should expire when the resource retain timer expires during a HO. While the nonces have not expired (i) Nonces are valid and can be re-used at a different BS and (ii) Both MS and T-BSs remember packet numbers used in data packets sent/received to/from each visited T-BS 2. When MS goes to an unprepared T-BS: a. This situation should be fairly uncommon and should be treated as an error scenario. b. In this case MS cannot assume that T-BS has knowledge of the HO nonces, and as a fall-back mechanism, we use the current TEK update algorithm (i.e. the MS expects the T-BS to send TEK updates in RNG-RSP)

The proposed solution reduces the overhead caused by TEK updates during HO, while maintaining system security. It also reduces HHO delay, since it reduces the processing time of RNG-RSP (removes TEK processing time). Finally, when the proposed solution is adopted, RNG-REQ/RSP are no longer needed for secure TEK updates during HO. This, combined with other proposals currently in progress, can eventually significantly reduce HHO delay by allowing the complete removal of RNG-REQ/RSP MAC management messages during HO.

Proposed Text Changes

Insert the following subsection right after section “11.8.4.6 Maximum number of supported security associations”

11.8.4.7 TEK derivation scheme support

This field specifies support for HO-nonce based TEK derivation scheme for handover (section 7.2.2.2.6.1).

|Type |Length |Value |Scope |
|25.5 |1 |0 = The HO-nonce based TEK derivation scheme for handover is not |SBC-REQ / SBC-RSP |
| | |supported | |
| | |1 = The HO-nonce based TEK derivation scheme for handover is supported | |

Insert the following subsection right after section “7.2.2.2.6 Traffic encryption key (TEK)”

7.2.2.2.6.1 Nonce-based Traffic encryption key (TEK) derivation for handover
When the MS and BS indicate that they both implement the HO-nonce based TEK update mechanism (see section 11.8.4.7 “TEK derivation scheme support” capability encoding) TEKs can be updated during a HO using the HO-nonce exchange procedure and the HO-nonce based TEK update procedures described in the following sub-sections.

7.2.2.2.6.1.1 HO-nonce exchange procedure
The MS initiates the HO-nonce exchange procedure by sending PKMv2 HO-nonce Request MAC management message to the serving BS. The HO-nonce attribute in the HO-nonce Request MAC management message contains a random number chosen by the MS, referred to as MS-HO-nonce. The SAID attribute in the HO-nonce Request MAC management message specifies the SA for which this procedure is performed. The serving BS upon receipt of the HO-nonce Request MAC management message saves the value of the HO-nonce attribute contained in the HO-nonce Request message and replies with a PKMv2 HO-nonce Reply MAC management message. The HO-nonce attribute of the HO-nonce Reply MAC Management message contains a random number chosen by the serving BS, which is referred to as BS-HO-nonce, and is different and chosen independently from the MS-HO-nonce.

The procedure above shall be referred to as “HO-nonce exchange”. After the end of the HO-nonce exchange the MS and the serving BS store both the exchanged HO-nonces (MS-HO-nonce and BS-HO-nonce) as part of the context of the SA specified in HO-nonce Request message.

7.2.2.2.6.1.2 HO-nonce based TEK update procedure
When the MS has performed the HO-nonce exchange procedure with the serving BS prior to a handover, then the serving BS can send the HO-nonces (MS-HO-nonce and BS-HO-nonce) to all candidate target BSs via the backbone network. During HO, the TEKs of the SAs for which the HO-nonce exchange procedure has been performed can then be updated using the procedure described in this section.

In the following “Old_TEK” refers to the older generation of keying material and “New_TEK” refers to the newer generation of keying material associated with the specific SA. The AES encryption algorithm is used as an example. For SAs employing a different ciphersuite the AES algorithm should be replaced with the encryption algorithm used by the SA for encrypting TEKs during the normal TEK update procedure.

The actions below are performed independently by the MS and by all candidate target BSs that are in possession of the MS-HO-nonce and BS-HO-nonce.

– Form two temporary nonces, combining bits from BS-HO-nonce and MS-HO-nonce: – “temp-nonce-1” = (first N/2 bits of MS-HO-nonce | first N/2 bits of BS-HO-nonce) – “temp-nonce-2” = (last N/2 bits of MS-HO-nonce | last N/2 bits of BS-HO-nonce) – Encrypt old and new nonces with KEK: – old_TEK_temp = AESKEK(temp-nonce-1| SA_ID) – new_TEK_temp = AESKEK(temp-nonce-2 | SA_ID) – Derive Old_TEK and New_TEK as follows: – Old_TEK ← truncate(old_TEK_temp, length of TEK) – New_TEK ← truncate(new_TEK_temp, length of TEK)

During HO execution, the T-BS can use Bit #14 in HO Process Optimization TLV encoding in RNG-RSP MAC management message to indicate to the MS if the procedure specified in this section should be used for updating TEKs.

Modify table “552—RNG-RSP message encodings” in section “11.6 RNG-RSP management message encodings” as indicated

Table 552 — RNG-RSP message encodings
|Name |Type (1byte) |Length |Value (variable length) |PHY scope |
| | | | | |

…

| | | | | |
|HO Process Optimization |21 |2 |For each Bit location, a value of ‘0’ indicates the associated |All |
| | | |re-entry management messages shall be required, a | |
| | | |value of ‘1’ indicates the re-entry management message | |
| | | |should be omitted. | |
| | | |Bit #0: Omit SBC-REQ management messages during | |
| | | |current re-entry processing | |
| | | |(Bit #1, Bit #2) = (0,0): Perform re-authentication and… | |
| | | |… | |
| | | |(Bit #1, Bit #2) = (1, 1): In this case the value of Bit #14 should be examined. | |
| | | |There are two cases. Case B is recommended: | |
| | | |Case A – (Bit #14 = 0) Re-authentication and SA-TEK | |
| | | |3-way handshake is not performed. The RNG-RSP | |
| | | |message does not include SA-TEK-Update TLV nor | |
| | | |SA Challenge Tuple TLV. All the TEKs received from | |
| | | |the serving BS are reused. | |
| | | |Case B – (Bit #14 = 1) Re-authentication and SA-TEK | |
| | | |3-way handshake is not performed. The RNG-RSP | |
| | | |message does not include SA-TEK-Update TLV nor | |
| | | |SA Challenge Tuple TLV. TEKs are updated using the HO nonce method | |
| | | | | |
| | | |Bit #3: Omit Network Address Acquisition management | |
| | | |messages during current reentry processing | |
| | | |… | |
| | | |Bit #13: If this bit is set to 1, MS shall trigger a higher | |
| | | |layer protocol required to refresh its traffic IP address | |
| | | |(e.g. DHCP Discover [IETF RFC 2131] or Mobile | |
| | | |IPv4 re-registration [IETF RFC 3344]). | |
| | | |#14–15: Reserved | |
| | | |Bit #14: Perform HO-nonce based TEK update. This bit shall be ignored unless (Bit | |
| | | |#1, Bit #2) = (1, 1) | |
| | | |#15: Reserved | |
| | | | | |

Modify section “6.3.22.2.8.1.6.6 Security settings” as indicated

6.3.22.2.8.1.6.6 Security settings
MS context with Serving BS: Maintained with resource retain timer,
MS context with Target BS: Context is handled per bit#1 and bit#2 settings.

Bit #1=0 AND bit#2=0:Perform re-authentication and SA-TEK 3-way handshake. BS shall not include SATEK-
Update TLV in the SA-TEK-Response message. In addition, the RNG-RSP message does not include
SA-TEK-Update TLV or SA Challenge Tuple TLV.

Bit #1=0 AND bit#2=1:Not used. MS shall silently ignore RNG-RSP message.

Bit #1=1 AND bit#2=0: One of two options is allowed:
Option 1: SA-TEK-Update TLV is included in the RNG-RSP message and updates the TEKS for all the
SAs. In this way SA-TEK 3-way handshake shall not occur. SA Challenge Tuple TLV shall not be included in the RNG-RSP message.
Option 2: SA-TEK-Update TLV is included in a SA-TEK-Response message. In this case, SATEK 3-way handshake is performed with SA Challenge Tuple TLV included in the RNG-RSP message.

Bit #1=1 AND bit#2=1:Re-authentication and SA-TEK 3-way handshake is not performed. The RNG-RSP message does not include SA-TEK-Update TLV nor SA Challenge Tuple TLV. There are two options, depending on the value of Bit #14.
Option 1: Bit #14=0: All the TEKs received from the serving BS are reused.
Option 2: Bit #14=1: The TEKs are updated using the HO-nonce method (section 7.2.2.2.6.1)
All PMK timers are maintained.

…

Modify “Table 48 PKM Message Codes” in section “6.3.2.3.9 Privacy key management (PKM) messages (PKM-REQ/PKM-RSP)” as indicated

|32 |MIH Acknowledge |PKM-RSP |
|33 |MIH Comeback Response |PKM-RSP |
|34–255 |Reserved |— |
|34 |PKMv2 HO-nonce Request |PKM-REQ |
|35 |PKMv2 HO-nonce Reply |PKM-RSP |
|36–255 |Reserved |— |

Insert the following subsection in section 6.3.2.3.9

6.3.2.3.9.32 PKMv2 HO-nonce Request message

An MS sends a PKMv2 HO-nonce Request message to the BS to provide the BS with a nonce, which is to be used in the next HO, for deriving the TEKs associated with a particular SA. This procedure is to be used only for unicast SAs.

Code: 34

Attributes are shown in Table 76a.

Table 76a—PKMv2 HO-nonce Request message attributes

|Attribute |Contents |
|Key Sequence Number |AK Sequence Number |
|SAID |Security Association Identifier |
|Nonce |A random number generated in an MS |
|HO nonce |An attribute containing the nonce chosen by the MS for TEK derivation during the |
| |next HO. The contents of this attribute shall be referred to as “MS-HO-nonce” |
|HMAC/CMAC Digest |Message digest calculated using AK |

The HMAC/CMAC Digest attribute shall be the final attribute in the message’s attribute list.

Inclusion of the HMAC/CMAC Digest attribute allows the MS and BS to authenticate the PKMv2 Key- Request message. The HMAC/CMAC Digest attribute’s authentication key is derived from the AK.

Insert the following subsection in section 6.3.2.3.9

6.3.2.3.9.33 PKMv2 HO-nonce Reply message

The BS responds to an MS’s PKMv2 HO-nonce Request message with a PKMv2 HO-nonce Reply message.

Code: 35

Attributes are shown in Table 76b.

Table 76b—PKMv2 HO-nonce Reply message attributes

|Attribute |Contents |
|Key Sequence Number |AK Sequence Number |
|SAID |Security Association Identifier |
|Nonce |A same random number included in the PKMv2 Key-Request message. |
|HO nonce |An attribute containing the nonce chosen by the BS for TEK derivation during the |
| |next HO. The contents of this attribute shall be referred to as “BS-HO-nonce”. |
| |This is not the same nonce as what was included in the PKMv2 HO-nonce Request |
| |message. |
|HMAC/CMAC Digest |Message digest calculated using AK |

The HMAC/CMAC Digest attribute shall be the final attribute in the message’s attribute list.

Inclusion of the HMAC/CMAC Digest attribute allows the MS and BS to authenticate the PKMv2 Key- Reply message. The HMAC/CMAC Digest attribute’s authentication key is derived from the AK.

Modify “Table 556 – PKM attribute types” in section 11.9 “PKM-REQ/RSP management message encodings” as indicated

|27 |PKM Configuration Settings |
|28-34 |Reserved |
|35 |Encrypted pre-PAK |
|36-255 |Reserved |
|36 |HO nonce |
|37–255 |Reserved |

Insert the following subsection in section 11.9

11.9.39 HO-nonce attribute

The HO-nonce attribute contains a quantity used for updating TEKs during HO. When this attribute is contained in PKMv2 HO-nonce Request message, it contains a random quantity generated by the MS. When contained in PKMv2 HO-nonce Reply message, it contains a random quantity generated by the BS. As always, values for nonces should be generated using reliable random or pseudo-random generators.

|Type |Length |Value (string) |
|36 |16 |Randomly generated value |

Modify table “Table 546—Trigger; Type/function/action description“ as indicated

Table 546 — Trigger; Type/function/action description
|Name |Length |Value |
| | | |

…

| | | |
|Action |3 (LSB) |Action performed upon reaching trigger condition: |
| | |0x0: Reserved |
| | |0x1: Respond on trigger with MOB_SCN-REP after the end of each scanning interval |
| | |0x2: Respond on trigger with MOB_MSHO-REQ |
| | |0x3: MS shall start neighbor BS scanning process by sending MOB_SCN-REQ, by initiating|
| | |Autonomous eighbor cell scanning (see 8.4.13.1.3) or both. |
| | |0x4–0x7: Reserved |
| | |0x4: MS shall initiate HO-nonce exchange procedure (see 7.2.2.2.6.1) |
| | |0x5–0x7: Reserved |
| | |NOTE—0x3 is not applicable when neighbor BS metrics are defined (i.e., only Function |
| | |values 0x5 or 0x6 are applicable) |

References

[IEEE802.16-Rev2/D2] IEEE Computer Society and IEEE Microwave Theory and Techniques Society, “DRAFT Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Broadband Wireless Access Systems”, P802.16Rev2/D2 (December 2007) Revision of IEEE Std 802.16-2004 and consolidates material from IEEE Std 802.16e-2005, IEEE Std 802.16-2004/Cor1-2005, IEEE Std 802.16f-2005 and IEEE Std802.16g-2007 .
-----------------------
MS switch from S-BS to T-BS

T-BS

S- BS

MS

HO-RSP

HO-REQ

new TEKs (and other updates)

UL data

DL data

UL_MAP (data allocation)

RNG_RSP

>?abcxy{‚Ž™?¥¦¶¹º»½¾ÀÁÌÜÝÞëìíþÿ ! 1 : ; W X Y ] c – ¡ j k s
}
ª
«
â ã ü÷ïüäïÞï÷üÙÔÙÔ÷ü÷Ô÷Ô÷Ï÷üËüÇËüÇËü˽ü¹üµËü½«ü§ü£Ÿ£üË’‰’h=9h&"ù0JDjh=9h&"ù0JDU[pic]h‘W'hµ7‘hohUpCUL_MAP (Fast Ranging IE)

RNG_REQ

MOB_BSHO_REQ / RSP

MOB_HO_IND

MOB_HO_IND

MOB_BSHO_REQ

HO-REQ
MS HO nonce, BS HO nonce

HO-RSP

T-BS

MS and T-BS are in possession all info necessary to derive the new TEKs

…

MS switch from S-BS to T-BS

DCD (Broadcast)
Initiate HO-nonce exchange when CINR > 7.9 dB

KEY-REQ
MS nonce to be used at next HO is “MS HO nonce”

MS

S-BS

KEY-REPLY
MS nonce
BS nonce to be used at next HO is “BS HO nonce”

Store MS nonce. Choose BS nonce

CINR>7.9 dB? Choose MS nonce and send it to S-BS

Both sides store MS nonce and BS nonce. Do NOT derive any keys yet

…

HO needed? Contact T-BS(s)

HO-nonce exchange

Handover

-----------------------
1