This document is only for use within 3GPP
ETSI/SAGETechnical report / Version: 1.0
Date: 6th February 2006
Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2.
Document 5: Design and Evaluation Report
Blank Page
Reference
Keywords
3GPP, security, SAGE, algorithm
ETSI Secretariat
Postal address
F-06921 Sophia Antipolis Cedex - FRANCE
Office address
650 Route des Lucioles - Sophia Antipolis
Valbonne - FRANCE
Tel.: +33 4 92 94 42 00 Fax: +33 4 93 65 47 16
Siret N° 348 623 562 00017 - NAF 742 C
Association à but non lucratif enregistrée à la
Sous-Préfecture de Grasse (06) N° 7803/88
X.400
c= fr; a=atlas; p=etsi; s=secretariat
Internet
http://www.etsi.fr
Copyright Notification
No part may be reproduced except as authorized by written permission.
The copyright and the foregoing restriction extend to reproduction in all media.
© European Telecommunications Standards Institute 2006.
All rights reserved.
Contents
1 Scope 8
2 References 8
3 Abbreviations 8
4 Structure of this report 10
5 Background to the design and evaluation work 10
6 Summary of algorithm requirements 11
6.1 f8 – Confidentiality algorithm 11
6.2 f9 – Integrity algorithm 11
6.3 Generic requirements for 3GPP cryptographic functions and algorithms 12
7 3GPP confidentiality and integrity algorithms 13
7.1 SNOW 3G 13
7.2 Confidentiality function UEA2 13
7.3 Integrity function UIA2 14
8 Rationale for the chosen design 16
8.1 General comments 16
8.1.1 Use of AES in UMTS 16
8.1.2 Selection of SNOW 2.0 17
8.2 Design Policy of SNOW 2.0 17
8.3 Changes from SNOW 2.0 to SNOW 3G 18
8.4 Choice of integrity mechanism 18
9 Algorithm evaluation 18
9.1 Evaluation criteria 18
9.1.1 General principles 18
9.1.2 Implementation aspects 19
9.1.3 Mathematical evaluation 19
9.1.4 Statistical evaluation 19
9.1.5 IPR investigations 19
9.2 Principles of algorithm evaluation 19
9.2.1 Analysis of various components of SNOW 3G 20
9.2.2 Analysis of SNOW 3G as a stream cipher 20
9.2.3 Analysis of the encryption and integrity modes 20
9.3 Security principles of UEA2 and UIA2 21
9.3.1 Supporting arguments for the UEA2 construction 21
9.3.2 Rationale behind the Construction of UIA2 22
9.4 Mathematical analysis of SNOW 3G 24
9.4.1 Properties of components 24
9.4.2 Resistance against attacks 25
9.5 Implementation attacks 30
9.5.1 Evaluation of SNOW 3G 30
9.5.2 Conclusion on implementation attacks 31
9.6 Results from complexity evaluation 31
9.6.1 KASUMI HW performance 32
9.6.2 SNOW HW performance 32
9.6.3 UIA2 complexity 33
9.6.4 SW performance 33
9.7 Results from independent evaluation 33
9.7.1 Evaluator 1 33
9.7.2 Evaluator 2 35
9.8 Results from IPR investigations 37
9.9 Conclusion of evaluation 37
10 Annex A - External references 39
Intellectual Property Rights
IPRs essential or potentially essential to the present document may have been declared to ETSI. The information pertaining to these essential IPRs, if any, is publicly available for ETSI members and non-members, and can be found in SR000314: "Intellectual Property Rights (IPRs); Essential, or potentially Essential, IPRs notified to ETSI in respect of ETSI standards", which is available from the ETSI Secretariat. Latest updates are available on the ETSI Web server (http://www.etsi.org/ipr).
At the time of writing of this report, no information of any Intellectual Property Rights (IPRs) has been drawn to the attention neither to the Task Force nor to ETSI. See Section 9.8 of this report for further information about IPR investigations conducted by the Task Force.
No guarantee can be given as to the existence of other IPRs not referenced in SR000314 (or the updates on the ETSI Web server (http://www.etsi.org/ipr) which are, or may be, or may become, essential to the present document.
Foreword
This Report has been produced by ETSI SAGE Task Force 278 on Design of the second UMTS encryption and integrity protection algorithms UEA2 and UIA2 (SAGE TF 3GPP).
The work described in this report was undertaken in response to a request made by 3GPP.
Version 1 of this report was submitted to the 3GPP SA3 group in January 2006.
1 Scope
This public report contains a detailed summary of the design and evaluation work performed during the development of the 3GPP Confidentiality and Integrity Algorithms UEA2 and UIA2. The report also includes summaries of evaluations that were conducted by independent external evaluators, and reflects modifications that were done to the design based on this feedback.
2 References
For the purposes of this report, the following references apply:
[1] 3G TS 33. 102 V 6.3.0 (2004-12) 3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Security Architecture.
[2] 3G TS 33. 105 V 6.0.0 (2004-06) 3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Cryptographic Algorithm Requirements.
[3] 3G TR 33. 901 V 1.0.0 (1999-06) 3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Criteria for cryptographic algorithm design process.
[4] 3G TS 25.321 V3.0.0: 3rd Generation Partnership Project; Technical Specification Group (TSG) RAN; Working Group 2 (WG2); MAC protocol specification.
[5] ETSI/SAGE Specification. Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 1: UEA2 and UIA2 Specification; Version: 1.0; Date: 10th January 2006.
[6] ETSI/SAGE Specification. Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 2: SNOW 3G Specification; Version: 1.0; Date: 10th January 2006.
[7] ETSI/SAGE Specification. Specification of the MILENAGE-2G Algorithms: an Example Algorithm Set for the GSM Authentication and Key Generation Functions A3 and A8. Version 1.0. May 2002.
Additional references to external documents are provided in Annex A.
3 Abbreviations
For the purposes of the present report, the following abbreviations apply:
AES / Advanced Encryption StandardAuC / Authentication Centre
CK / Cipher Key
ETSI / European Telecommunications Standards Institute
GF(q) / The finite field of q elements
GSMA / GSM Association
3GPP / 3rd Generation Partnership Project
FSM / Finite State Machine
f8 / UMTS confidentiality (encryption) algorithm
f9 / UMTS integrity algorithm
HW / Hardware
IBS / Input Bit Stream
IK / Integrity Key
IPR / Intellectual Property Rights
IV / Initialization Vector
LFSR / Linear Feedback Shift Register
MAC / Message Authentication Code
OBS / Output Bit Stream
OTP / One Time Pad
PDU / Protocol Data Unit
RLC / Radio Link Control
RNC / Radio Network Controller
SA3 / 3GPP Systems and Architecture Group
SAGE / Security Algorithms Group of Experts
SAGE TF 3GPP / SAGE Task Force for the design of the standard 3GPP Confidentiality and Integrity Algorithms
SDU / Signalling Data Unit
SW / Software
UE / User Equipment
UEA2 / UMTS Encryption Algorithm Suite 2
UIA2 / UMTS Integrity Algorithm Suite 2
UMTS / Universal Mobile Telecommunications System
USIM / User Services Identity Module
XL / Extended Linearization
XSL / Extended Sparse Linearization
4 Structure of this report
The material presented in this report is organised in the subsequent clauses, as follows:
- Clause 5 provides background information on the second 3GPP Confidentiality and Integrity Algorithms UEA2 and UIA2;
- Clause 6 provides a summary of the algorithm requirements;
- Clause 7 consists of a brief presentation of the actual designs;
- Clause 8 provides information on the design criteria and the design work;
- Clause 9 gives an overview of the evaluation work carried out by SAGE TF 3GPP and other parties and the conclusions of the evaluations;
- Annex A includes a list of external references that are related to the results in this report.
5 Background to the design and evaluation work
The development of the second issue of standardised 3GPP confidentiality and integrity algorithms was undertaken in response to an initiative from 3GPP SA3 and GSMA Security Group. Due to the fact that deployment of new algorithms in networks and handsets takes a very long time, it was decided to develop a second suite of confidentiality and integrity algorithms for 3GPP in case the transition to new algorithms was needed. Even without any indications of weaknesses in the KASUMI-based versions of f8 and f9, the new algorithms should be fundamentally different from the previous, so that an attack on one algorithm is very unlikely to translate into an attack on the other.
The new version of f8 and f9 should meet all relevant security goals with a high degree of confidence, but the available resources for design and evaluation were rather limited in terms of time and funding. The ETSI SAGE group therefore decided on the following strategies for the work:
· Reuse of people and results from the previous 3GPP project.
· Investigate published and well-studied algorithms and schemes for the design.
· Concentrate new designs to establish cryptographic resistance against algebraic attacks.
· Initiate additional evaluation by inviting leading researchers for independent review of the final design.
Based upon the 3GPP requirements and the work conducted by the task force, a modified version of SNOW 2.0 [20] was developed and named SNOW 3G. SNOW 3G is the cryptographic engine of the second suite of 3GPP encryption and integrity algorithms f8 and f9 (UEA2 and UIA2).
6 Summary of algorithm requirements
The general security architecture for 3GPP is specified in ref. [1]. The complete set of security services needed is realised using a set of cryptographic functions identified in ref. [2]. Out of the full algorithm set there is a need for two algorithms fully standardised. These are:
· f8 – Confidentiality algorithm
· f9 – Integrity algorithm
The requirements for the f8 and f9 algorithms were specified in ref. [2]. For the second suite of 3GPP cryptographic algorithms, the same functional and security requirements apply. In addition to cryptographic separation from the KASUMI-based f8/f9 algorithms, the only modification was to support a throughput of 10 Mbit/s. For the completeness of this report we include some of the main requirements:
6.1 f8 – Confidentiality algorithm
The function f8 shall only be used to protect the confidentiality of user data and signalling data sent over the radio access link between UE and RNC.
The algorithm should be designed to accommodate a range of implementation options including hardware and software implementations.
For hardware implementations, it should be possible to implement one instance of the algorithm using less than 10,000 gates (working assumption).
It must be possible to implement the algorithm to achieve an encryption speed in the order of 10 Mbit/s on the downlink and on the uplink. This throughput should be available at a minimal clock speed of 20 MHz.
The f8 algorithm will be used to encrypt frames of variable length up to approximately 20000 bits.
The function f8 should be a symmetric synchronous stream cipher.
The length of the cipher key CK is 128 bits. In case the effective key length should need to be made smaller than 128 bits, the most significant bits of CK shall carry the effective key information, whereas the remaining, least significant bits shall be set zero.
Additional input parameters: COUNT, BEARER, DIRECTION and LENGTH.
This plaintext block consists of the payload of the particular RLC PDUs / MAC SDUs to be encrypted in a single 10ms physical layer frame for a given bearer and transmission direction. It may consist of user traffic or signalling data. The structure of the plaintext block cannot be specified at present.
6.2 f9 – Integrity algorithm
The MAC function f9 shall be used to authenticate the data integrity and data origin of signalling data transmitted between UE and RNC.
The algorithm should be designed to accommodate a range of implementation options including hardware and software implementations.
The function f9 shall be a MAC function.
The length of the integrity key IK is 128 bits. In case the effective key length should need to be made smaller than 128 bits, the most significant bits of IK shall carry the effective key information, whereas the remaining, least significant bits shall be set zero.
Additional input parameters: COUNT, FRESH and LENGTH.
The algorithm shall output a 32-bit MAC.
6.3 Generic requirements for 3GPP cryptographic functions and algorithms
The functions should be designed with a view to their continued use for a period of at least 20 years. Successful attacks with a workload significantly less than exhaustive key search through the effective key space should be impossible.
The designers of above functions should design algorithms to a strength that reflects the above qualitative requirements.
The algorithm will be openly published for public scrutiny. A number of independent and qualified parties shall, prior to publication, evaluate the strength of the algorithm.
Legal restrictions on the use or export of equipment containing cryptographic functions may prevent the use of such equipment in certain countries.
It is the intention that UE and USIMs that embody such algorithms should be free from restrictions on export or use, in order to allow the free circulation of 3G terminals. Network equipment, including RNC and AuC, may be expected to come under more stringent restrictions. It is the intention that RNC and AuC that embody such algorithms should be exportable under the conditions of the Wassenaar Arrangement [30].
7 3GPP confidentiality and integrity algorithms
The detailed specifications of the UEA2 and UIA2 algorithms are found in ref. [5] and ref. [6]. For this report we include a general overview of the designs. The basic building block is the stream cipher SNOW 3G, which is a two component stream cipher with an internal state of 608 bits initialized by a 128-bit cipher key CK and a 128-bit initialization vector IV.
7.1 SNOW 3G
The structure of SNOW 3G is depicted in the following diagram:
Figure 1: Schematic drawing of SNOW 3G
SNOW 3G consists of a Linear Feedback Shift Register (LFSR) and a Finite State Machine (FSM). The LFSR is constructed from 16 stages, each holding 32 bits and the feedback is defined by a primitive polynomial over the finite field GF(232). The FSM is based upon three 32-bit registers R1, R2, and R3. The operation of the FSM involves input from the LFSR and uses two substitution box ensembles S1 and S2. The mixing operations are exclusive OR and addition modulo 232. See ref. [6] for details on the specification of S-boxes, the S-box ensembles, the loading of key variable and IVs and the generation of the keystream.