ANALYSIS AND IMPLEMENTATION OF THE BIRYUKOV ATTACK ON THE AS/1 GSM ENCRYPTION ALGORITHM

Abstract

Radio communications was first used in 1920 in police vehicles and was then extended by using radio links with fixed telephone network to provide Public Correspondence Service in 1946. The first cellular system was implemented in 1978. From that time, interest began in mobile communications and many countries implemented their own system till 1982 when there was a need to develop a standard European mobile cellular system, which is the Global System for Mobile Communications, GSM.

The launch of the first commercial GSM network was in 1991. From that time GSM use began to grow. Now, GSM is the most popular mobile communication system. More than 860 million consumers in• 197 countries use it and it accounts for about 72 percent of the world's digital mobile phone market.

The security of such a widely used system deserves to be studied. Many security threats face the GSM system and they are classified into: threats to confidentiality, threats to integrity, threats to availability, unauthorized access to services, unauthorized access to the SIM, unauthorized access to the ME and repudiation. The security threats trigger the need for many security requirements, which should be realized in the GSM system so as to be immunized against these threats.

GSM provides three security functions, which are: subscriber identity confidentiality, subscriber identity authentication and user and signaling data confidentiality. Their role is to treat the security threats that face the system by implementing the security• requirements.

Actually, many of the security requirements are not fulfilled by the security function, thereby leaving many of the threats uncovered or partially covered. These threats were utilized to conduct various attacks on the GSM system. The attacks . are mainly directed to the GSM security algorithms and to the network interfaces.

The GSM security algorithms were protected using the "Security by Obscurity" concept, which means that the algorithms could not be broken, as Jong as their designs are not known. This concept proved failure; as the flaws in the design of the algorithms will appear once the algorithms are known and this will eventually occur, so they will be no longer secure. This was what actually happened, the algorithms were exposed to public scrutiny and flaws were found but tool late to be fixed.

Among the GSM security algorithms, there is the AS Algorithm, which is the ciphering/deciphering algorithm used to secure the information sent over the air interface.: The algorithm has a number of releases, which are AS/0, AS/I, AS/2 and AS/3. The AS/1 is the strongest version used commercially at the time of the thesis.

The AS/1 is a pseudorandom number generator whose• seed is the user's .64�bit ciphering key and it has a second input, COUNT, which is a 22-bit number that depends on the GSM frame number of the frame being processed. It consists of three MLFSRs of sizes 19, 22 and 23 bits that sum up into 64 bits. The LFSRs are irregularly clocked and this represents the only non-linearity in the algorithm design.