A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony
A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony
复制标题
DOI：
10.1007/s00145-013-9154-9
复制
发表时间：
2010-08
影响因子：
3
通讯作者：
O. Dunkelman;Nathan Keller;A. Shamir
中科院分区：
文献类型：
--
作者：
O. Dunkelman;Nathan Keller;A. Shamir
在过去的20年里，大多数GSM电话通话的隐私是由A5/1和A5/2流密码保护的，这些密码被反复证明是密码薄弱的。它们现在被基于分组密码KASUMI的新的A5/3和A5/4算法所取代。在本文中，我们描述了一种新的攻击类型，称为三明治攻击，并使用它来构造一个简单的关联密钥区分符，用于8轮KASUMI中的7轮，具有惊人的2−14的高概率。通过使用此区分符并分析剩下的单个回合，我们可以通过相关密钥攻击获得完整KASUMI的完整128位密钥，该攻击仅使用4个相关密钥，226data， 230字节的内存和232时间。在不到两个小时的时间里，在一台单核PC上进行了攻击，实验验证了这些完全实用的复杂性。有趣的是，无论是我们的技术还是任何其他公开的攻击，都不能比穷举搜索更快地破解原始的MISTY分组密码（KASUMI基于该分组密码）。因此，我们的结果表明，ETSI的SAGE小组在从MISTY移动到KASUMI时所做的修改使得它在允许相关密钥攻击时非常弱，但并不意味着它对单键攻击的抵抗力有任何变化。因此，没有迹象表明KASUMI在GSM和3G网络中实现的方式在任何现实的攻击模型中实际上都是脆弱的。
Over the last 20 years, the privacy of most GSM phone conversations was protected by the A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They are being replaced now by the new A5/3 and A5/4 algorithms, which are based on the block cipher KASUMI. In this paper we describe a new type of attack called asandwich attack, and use it to construct a simple related-key distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2−14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128-bit key of the full KASUMI with a related-key attack which uses only 4 related keys, 226data, 230bytes of memory, and 232time. These completely practical complexities were experimentally verified by performing the attack in less than two hours on a single-core of a PC. Interestingly, neither our technique nor any other published attack can break the original MISTY block cipher (on which KASUMI is based) significantly faster than exhaustive search. Our results thus indicate that the modifications made by ETSI’s SAGE group in moving from MISTY to KASUMI made it extremely weak when related-key attacks are allowed, but do not imply anything about its resistance to single-key attacks. Consequently, there is no indication that the way KASUMI is implemented in GSM and 3G networks is practically vulnerable in any realistic attack model.