A guess-and-determine attack on GSM Cipher A5/1

摘要

A5/1 is an encryption algorithm used by about 130 million GSM customers in Europe to protect the privacy and confidentiality of over-air conversations. In this paper, we present a new possible guess-and-determine attack on the A5/1 stream cipher. By analyzing the clocking mechanism of the cipher and guessing both some bits and some clocking states, the key can be recovered efficiently. The attack has an average time complexity of 239, which is much less than the brute-force attack with a complexity of 264. The attack has a 100% success rate and requires about 64GB storage.