SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032113(2018) https://doi.org/10.1007/s11432-017-9230-8

## A real-time inversion attack on the GMR-2 cipherused in the satellite phones

• AcceptedJul 19, 2017
• PublishedFeb 1, 2018
Share
Rating

### Abstract

The GMR-2 cipher is a type of stream cipher currently being used in some inmarsat satellite phones. It has been proven that such a cipher can be cracked using only one single-frame (15 bytes) known keystream but with moderate executing time. In this paper, we present a new thorough security analysis of the GMR-2 cipher. We first study the inverse properties of the ciphers components to reveal a bad one-way character of the cipher. By then introducing a new concept called “valid key chain according to the ciphers key schedule, we propose an unprecedented real-time inversion attack using a single-frame keystream. This attack comprises three phases: (1) table generation; (2) dynamic table look-up, filtration and combination; and (3) verification. Our analysis shows that, using the proposed attack, the size of the exhaustive search space for the 64-bit encryption key can be reduced to approximately $2^{13}$ when a single-frame keystream is available. Compared with previous known attacks, this inversion attack is much more efficient. Finally, the proposed attack is carried out on a 3.3-GHz PC, and the experimental results thus obtained demonstrate that the 64-bit encryption-key could be recovered in approximately 0.02 s on average.

### Acknowledgment

The authors wish to thank the anonymous reviewers for their valuable suggestions and comments, which greatly improve the presentation and quality of the current paper. This work in this paper was supported by National Nature Science Foundation of China (Grant Nos. 61402515, 61672530).

### References

[2] Biryukov A, Shamir A, Wagner D. Real time cryptanalysis of A5/1 on a PC. In: Proceedings of the 7th International Workshop on Fast Software Encryption. Berlin: Springer, 2000. 1--18. Google Scholar

[3] Dunkelman O, Keller N, Shamir A. A practical-time attack on the A5/3 cryptosystem used in third generation GSM telephony. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2010. 393--410. Google Scholar

[4] Kircanski A, Youssef A M. On the sliding property of SNOW 3G and SNOW 2.0. IET Inf Secur, 2011, 5: 199--206. Google Scholar

[5] Li L, Liu X H, Wang Z, et al. An improved attack on clock-controlled shift registers based on hardware implementation. Sci China Inf Sci, 2013, 56: 112107. Google Scholar

[6] Wu H J, Huang T, Nguyen P H, et al. Differential attacks against stream cipher ZUC. In: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, 2012. 262--277. Google Scholar

[7] Zhang B, Xu C, Meier W. Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2015. 643--662. Google Scholar

[8] Zhou C F, Feng X T, Lin D D. The initialization stage analysis of ZUC v1.5. In: Proceedings of International Conference on Cryptology and Network Security, Sanya, 2011. 40--53. Google Scholar

[9] Driessen B, Hund R, Willems C, et al. Dont trust satellite phones: a security analysis of two satphone standards. In: Proceedings of IEEE Symposium on Security and Privacy (SP), Oakland, 2012. 128--142. Google Scholar

[10] Driessen B, Hund R, Willems C, et al. An experimental security analysis of two satphone standards. ACM Trans Inf Syst Secur, 2013, 16: 10. Google Scholar

[11] Barkan P, Biham E, Keller N. Instant cipher-text only cryptanalysis of GSM encrypted communication. J Cryptol, 2008, 21: 392--429. Google Scholar

[12] Bogdanov A, Eisenbarth T, Rupp A. A hardware assisted real-time attack on A5/2 without precomputations. In: Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems, Vienna, 2007. 394--412. Google Scholar

[13] Li R L, Li H, Li C, et al. A low data complexity attack on the GMR-2 cipher used in the satellite phones. In: Proceedings of International Workshop on Fast Software Encryption, Singapore, 2013. 485--501. Google Scholar

[14] Golic J D. On the security of nonlinear filter generators. In: Proceedings of the 3rd International Workshop on Fast Software Encryption, Cambridge, 1996. 173--188. Google Scholar

[15] Golic J D, Clark A, Dawson E. Inversion attack and branching. In: Proceedings of Australasian Conference on Information Security and Privacy, Wollongong, 1999. 99--102. Google Scholar

[16] Golic J D, Clark A, Dawson E. Generalized inversion attack on nonlinear filter generators. IEEE Trans Comput, 2000, 49: 1100--1109. Google Scholar

• Figure 1

Overall structure of the GMR-2 cipher.

• Figure 2

Structure of the $\mathcal{F}$-component.

• Figure 3

Structure of the $\mathcal{G}$-component.

• Figure 4

Structure of the $\mathcal{H}$-component.

• Figure 5

(Color online) Links among the three inverse components.

• Figure 6

Overview of the inversion attack procedure.

• Figure 7

Table generation procedure.

• Figure 8

Diagram of the links for valid key chains in Example 5.4. (a) Case (1) in Definition 2; (b) case (2) in Definition 2;protectłinebreak (c) case (3) in Definition 2.

• Figure 9

Dynamic combination of valid key chains in Phase 2 (the number of valid key chain layers as well as the length of each valid key chain are dynamically changed).

• Figure 10

(Color online) Procedure of dynamic table look-up in Phase 2.

• Figure 11

(Color online) Frequency distribution of the number of candidate keys in Phase 2 (the numbers on the horizontal axis are in thousand of times, and each interval $a$–$b$ contains the left number $a$, but does not contain the right value $b$).

• Figure 12

(Color online) Frequency distribution of the attack time.

• Figure 13

Optimized inversion attack procedure.

Citations

• #### 0

Altmetric

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有