Notes on the GSM A5 Algorithms
I was doing some browsing around and reading a bit about the new GSM mandated over-the-air communications cipher called A5/3 or the KASUMI cipher [3]. This is a more power cipher recommended as a replacement for the older A5/1 and A5/2 ciphers
[1] that have proven to be susceptible to real-time attack. Of course, I wanted to learn more about the said cipher and its parent ciphers. So, let us take a closer look at the A5 ciphers used to secure (I use the term loosely) our mobile communications [2].
- A5/0. Dummy cipher definition. This is not a cipher. This means your communications are unprotected. I hope nobody is using this and actually thinks they are secure.
- A5/1. This is the original GSM cipher defined by ETSI for used in European mobile communications (in the early days of GSM). This was originally kept confidential. As described, it composed of three (3) linear feedback shift registers. In English,
uses feedbacked bits and XOR to mess your data around in a reversible way. This is one of the classic confuse and diffuse tactics [4]. It takes in a 64-bit secret key. The IV is common for the entire network. Actually, this is not pretty strong anymore as weaknesses have been discovered that allow breaking the algorithm in real-time [5]. - A5/2. Weaker version of A5/1 to be released to “unfriendly” countries. Like A5/1, the algorithm details where originally kept confidential. This weaker cousin has four (4) linear feedback shift registers but each register has a loaded bit (value is forced to 1), fewer masked values and output delayed by one clock cycle. In short, it has stuff that purposely makes parts of the output predictable. This algorithm is due for phase out by the GSMA.
- A5/3. Newer cipher introduced for 3GPP mobile communications which is based on an existing SAGE algorithm called MISTY1. It uses a Feistel structure (block cipher that uses multi-round transformations) similar to the popular DES and Blowfish cipher. It also uses a 128-bit key similar to 3DES [3]. This Feistel cipher is definitely more complex than its LFSR predecessors. This would mean that A5/3 will need more computing resources than A5/1 and A5/2. So a lot of lower end handsets would still probably use A5/1. Fortunately, there is no known practical real-time exploit for this algorithm yet.
Interesting reading and it seems that the search for a new and secure voice encryption algorithm (to be called A5/4) for mobile communications is on. I am sure that cryptanalysts will find a way, or computing resources will be abundant enough, to make real-time cracking of A5/3 possible. If this occurs then another “Hello Garci” is in the wings?
[1] Reversed Engineered A5/1 and A5/2 code at the CryptoDox wiki.
[2] Summary of the A5 ciphers used in GSM communications from the CryptoDox wiki.
[3] Published A5/3 code as 3GPP TS 35.202 found via 3GPP confidentiality and integrity page.
[4] CE. Shannon. 2001. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review. January 2001.
[5] E. Biham, O. Dunkelman. 2000.
Cryptanalysis of the A5/1 GSM Stream Cipher. Proceedings of the First International Conference on Progress in Cryptology INDOCRYPT ‘00.
