Ciphertext only attacks against GSM security

Abstract

Mobile communications play a center role in today's connected society. The security of the cellular networks that connect billions of people is of the utmost importance. However, even though modern third generation and fourth generation cellular networks (3G and 4G) provide an adequate level of security in the radio interface, most networks and mobile handsets can fall back to the old GSM standard designed almost three decades ago, which has several known security weaknesses. In this work we study the security provided by the family of ciphering algoritms known as A5 that protects the radio access network of GSM, with emphasis on A5/1. We review the existing attacks against A5/1 and existing countermeasures, and show that the existing ciphertext only attacks against algorithm A5/1 [9], adapted to use the most recent Time Memory Data Tradeoff, are realistic threats to fielded GSM networks when attacked by a resourceful attacker which uses current state of the art GPUs and CPUs. We also study the existing Time Memory Data Tradeoff algorithms, extending the best known results for the Perfect Fuzzy Rainbow Tradeoff attack to the multi target case. These results allow the practitioner to calculate the parameters and tradeooff constants that best suit his application. We implemented the algorithms using parallel programming on CUDA GPUs and successfully validated the theoretical estimations. The main contributions of this work can be summarized as follows: Extending the existing best results for the Perfect Fuzzy Rainbow Tradeoff attack in the single target scenario to the multi target scenario. Validating the theoretical calculation of the parameters and tradeoff constants of the Perfect Fuzzy Rainbow tradeoff through implementation for several scenarios. Describing one of the possible procedures for the choice of parameters for the Perfect Fuzzy Rainbow tradeoff. Presenting a new ciphertext only attack against A5/1 using the voice channel in GSM communication. Calculating the details of the ciphertext only attack in [9] and showing that the attack is a realistic threat today using a perfect fuzzy rainbow tradeoff attack and modern GPUs.