Improved Ciphertext-Only Attack on GMR-1

Abstract

The GEO-Mobile Radio Interface-1 (GMR-1) is a satellite communication standard used in Thuraya, a United Arab Emirates-based regional mobile satellite service provider. The specification of the encryption algorithm used in GMR-1 was not disclosed until it was uncovered by Driessen et al. in 2012 through reverse engineering. Given that A5-GMR-1, a stream cipher used in GMR-1, is primarily based on A5/2, Driessen et al. presented a ciphertext-only attack from the attacks on A5/2. Their ciphertext-only attack recovers the session key from multiple sets of 24 ciphertexts in an average of 32.1 min and requires 400 GB of pre-computed data. This study enhances Driessen et al.’s ciphertext-only attack on A5-GMR-1 in all aspects of time, memory, and data. Our contributions are fourfold. First, we optimize the inefficient part of the previous attack. As a result, our ciphertext-only attack recovers the session key from multiple sets of 13 ciphertexts in less than 1 second and requires 400 MB of pre-computed data. Second, we propose novel memory-saving techniques. These techniques reduce the memory complexity to 216 ~ 289 MB without increasing the time and data complexity. Third, we present several time-memory-data tradeoff techniques. Using these techniques, we can present an attack that meets the desired conditions, such as memory minimization or data minimization. Furthermore, while the complexity of the previous attack is presented vaguely as “multiple sets” of 24 ciphertexts, these techniques allow us to accurately calculate the time, memory, and data complexity of the attack. Finally, we demonstrate that A5-GMR-1 can be attacked without frame numbers. To find out the frame number of each ciphertext, it is necessary to analyze and synchronize multiple channels. We present a plaintext recovery attack that does not require these processes.

Keywords

• A5-GMR-1
• ciphertext-only attack
• cryptography
• stream cipher