D. Dhebar - The Mechanics of 3g Cryptography

Published by Silverkey Books, United Kingdom

ISBN 978-1-4457-0145-5

Text copyright D. S. Dhebar 2010

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or in any form or by any means, without the prior permission in writing of the publisher, nor be otherwise circulated in any form of binding or cover other than that in which it is published and without a similar condition including this condition being imposed on the subsequent purchaser.

A copy of the British Library Cataloguing in Publication Data is available from the British Library

Printed and bound in the USA

I should like to thank Professor Peter Wild, Royal Holloway, University of London (Information Security Group), for taking the time to read the original draft (2002) of this project and for much helpful feedback. I am also grateful to Steven Babbage, Vodafone Group - Research and Development, for sending me some very useful links and for answering some of my queries. My appreciation also to William Perera who - whilst well qualified in his field, is neither a mathematician nor a cryptographer - kindly agreed to proofread even though amidst a mountain of necessary work a meticulous effort far exceeding my expectations. It should be noted that none of the above have seen this final draft, so any errors are solely down to the inadequacies of the author.

This project covers exactly what the title suggests, The Mechanics of 3G/UMTS, and not a great deal else. It assumes that the reader is familiar with basic cryptography and the concept of mobile telephones, i.e. the general idea behind the communications made between the User Equipment (UE), the Radio Network Controller (RNC), Radio Access Link (RAL), Authentication Centre (AuC), and so on. There are explicit examples throughout, along with appendices A and B which help some mathematics [2].

A conscious effort has been made to conform to conventional notation along with that found in the documents from which these algorithms came. However, much of the notation from such documents had to be changed in order to avoid ambiguity. There are no surprises mind; L and R still refer to the left and right sides of a data string, the symbol still means a bit-wise exclusive-OR operation, and so on.

The first chapter introduces the Third Generation Partnership Project (3GPP) - the partnership that is responsible for the algorithms of 3G/UMTS and many other related issues - and the main security and legal aspects concerned. These issues are straight to the point; no great detail is given or was intended. The rest of the book, save chapter seven, is split into two main parts, the standardised algorithms and the non-standardised algorithms.

Part one consists of the standardised algorithms used in 3G/UMTS: the Kasumi algorithm (chapter two), the confidentiality algorithm, f8 (chapter three), and the integrity algorithm, f9 (chapter four). Chapter two briefly discusses Kasumi, the kernel for functions f8 and f9, and then details the mechanics of this very intricate algorithm. This is followed by an explicit example, so large it required a sub-section of its own.

The two functions, f8 and f9, are each set out in a similar style. Both include a brief discussion, followed by individual calculations and examples simultaneously. The f8 function serves to keep the user and signalling data confidential, and the f9 function serves to protect against unauthorised modification, insertion, and the replay of messages.

Part two consists of the non-standardised algorithm set recommended by 3GPP; the Rijndael algorithm (chapter five) and the Authentication and Key Agreement (AKA) algorithms, f1-f5, f1* and f5* (chapter six). Rijndael is the kernel algorithm for the AKA functions. A brief discussion of the algorithm is followed by its description. As each part of the algorithm is given it is immediately followed by an example of that part, unlike Kasumi, for which the entire example is given at the end of the chapter. The AKA functions are laid out in exactly the same way as for the Rijndael algorithm. These functions produce outputs which are used by the standardised functions, such as the confidentiality key used by f8, and the integrity key used by f9.

The final chapter, Conclusions, draws this project to a close. Among other things, it includes a very brief discussion on the security aspect of 3G-telecommunications as a whole, including the possible effects of 3G operators generating their own random numbers.

There are numerous documents and books on the topic of 3GPP algorithms and functions. However, most of these only discuss what they are for and where they are used, normally with a diagram that shows the inputs and outputs. The nearest that they get to the actual algorithm is a diagram of a box with a suitable caption. Few actually explain the detailed mechanics of these algorithms, and those that do seem to be written for those already familiar with mathematics and cryptography algorithms in particular. Although many books are accompanied by a program that can be (with minor adjustments) cut and pasted, this is only useful to those who understand programming and/or experienced cryptographers.

The aim of this project is quite straightforward. The reader, with the aid of this project (and of the aforementioned level) should be able to pencil-and-paper all the outputs, given - or in some cases attaining - all the relevant inputs. This aim might appear overly simple, but consider Kasumi for a moment. This algorithm has a very complicated key schedule, including sub-keys of sub-keys, and then sub-keys of these sub-keys. It also includes concatenations split into unequal parts. It is made of a function that is made of two further functions. One of these functions has so-called inner rounds, i.e. rounds that occur within the actual main rounds of the algorithm. Kasumi also has two different orders of operation, depending on the parity of the round. All this and other particulars of this algorithm make it difficult to understand from the available 3GPP documents of the algorithm.

The Kasumi document, as with all other functions documents, has been written in a kind of programming style. Many of the input and output variables have been given the same notation, in much the same way as a program that has set local variables. There are no outlined equations for these input/output variables and some of the notation, such as fi in the Kasumi algorithm, can be confused with other functions. The notation used does not differentiate (in most cases) which left and right parts of the algorithm belong to which function. Thus, part of the aim was to improve upon the way these algorithms were described, to formalise exactly what the input/output variables are and where they come from.

The intention is not to criticise the 3GPP documents in any way; the writers make no claim to being an introduction or to which level they are aimed [9].

Overall, the objectives of this project can be summarised as follows:

1. i) To briefly introduce 3GPP and its main security aspects.
2. ii) To re-write the description of the mechanics of the 3G/UMTS algorithms in a mathematical style.
3. iii) To provide ample and clear examples of all necessary calculations involved in these algorithms.