Time-Memory Trade-Offs Sound the Death Knell for GPRS and GSM

This paper introduces a practical TMTO-based attack against GSM (A5/3) and GPRS (GEA-3), which are both technologies used in 2G mobile networks. Although designed in the 80 s, these networks are still quite active today, especially for embedded systems. While active attacks against 2G networks with a fake base station were already known for a while, the attacks introduced in this paper rely on a passive attacker. We explain in this paper how to find material in GPRS and GSM communications to perform a TMTO attack. We performed validation experiments with off-the-shelf devices operated in real-life networks. We provide the success probability of the attack and its performances for several real-life scenarios. We optimized the implementation of KASUMI with AVX2 instructions, and designed a specific TMTO implementation to get around the SSD access latency. As a motivating example, an attacker passively eavesdropping a GSM communication between a target and a base station can decrypt any 2-h call with probability 0.43, in 14 min.