A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony

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 a sandwich 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, 2²⁶ data, 2³⁰ bytes of memory, and 2³² time. 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.     

A Link Between Integrals and Higher‐Order Integrals of SPN Ciphers

Integral cryptanalysis, which is based on the existence of (higher‐order) integral distinguishers, is a powerful cryptographic method that can be used to evaluate the security of modern block ciphers. In this paper, we focus on substitution‐permutation network (SPN) ciphers and propose a criterion to characterize how an r‐round integral distinguisher can be extended to an (r+1)‐round higher‐order integral distinguisher. This criterion, which builds a link between integrals and higher‐order integrals of SPN ciphers, is in fact based on the theory of direct decomposition of a linear space defined by the linear mapping of the cipher. It can be directly utilized to unify the procedure for finding 4‐round higher‐order integral distinguishers of AES and ARIA and can be further extended to analyze higher‐order integral distinguishers of various block cipher structures. We hope that the criterion presented in this paper will benefit the cryptanalysts and may thus lead to better cryptanalytic results.     

Security analysis of mCrypton proper to low‐cost ubiquitous computing devices and applications

mCrypton, which is a mini‐version of Crypton, is a 64‐bit block cipher with three key size options (64 bits, 96 bits, 128 bits). It was designed for use in low‐cost ubiquitous wireless devices and resource‐constrained tiny devices such as low‐cost Radio‐Frequency Identification tags and sensors in Ubiquitous Sensor Network. In this paper we show that 8‐round mCrypton with 128‐bit key is vulnerable to related‐key rectangle attack. We first describe how to construct two related‐key truncated differentials on which 7‐round related‐key rectangle distinguisher is based and then we exploit it to attack 8‐round mCrypton. This attack requires 2⁴⁶ dada and 2⁴⁶ time complexities, which is faster than exhaustive search. This is the first known cryptanalytic result on mCrypton. Copyright © 2009 John Wiley & Sons, Ltd.     

Multi-Verifier Signatures

Multi-verifier signatures generalize public-key signatures to a secret-key setting. Just like public-key signatures, these signatures are both transferable and secure under arbitrary (unbounded) adaptive chosen-message attacks. In contrast to public-key signature schemes, however, we exhibit practical constructions of multi-verifier signature schemes that are provably secure and are based only on pseudorandom functions in the plain model without any random oracles.     

The Security of Feistel Ciphers with Six Rounds or Less

This paper considers the security of Feistel networks where the round functions are chosen at random from a family of 2 ^k randomly chosen functions for any k . Also considered are the networks where the round functions are themselves permutations, since these have applications in practice. The constructions are attacked under the assumption that a key-recovery attack on one round function itself requires an exhaustive search over all 2 ^k possible functions. Attacks are given on all three-, four-, five-, and six-round Feistel constructions and interesting bounds on their security level are obtained. In a chosen text scenario the key recovery attacks on the four-round constructions, the analogue to the super pseudorandom permutations in the Luby and Rackoff model, take roughly only the time of an exhaustive search for the key of one round. A side result of the presented attacks is that some constructions, which have been proved super pseudorandom in the model of Luby and Rackoff, do not seem to offer more security in our model than constructions which are not super pseudorandom.     

HIGHT算法的积分攻击

对轻量级分组密码算法HIGHT在积分攻击方法下的安全性进行了研究。首先纠正了现有研究成果在构造区分器时的不当之处,重新构造了HIGHT算法的11轮积分区分器,并构造了相应高阶积分扩展下的17轮区分器;其次利用所构造的17轮区分器,结合“时空折中”原理对25轮HIGHT算法进行了积分攻击;最后对攻击算法的复杂度进行了分析,攻击算法需要的数据复杂度为262.92,时间复杂度为266.20,空间复杂度为2119。分析结果表明,所给出的攻击算法的攻击轮数和时间复杂度要优于现有研究结果。     

MIBS算法的积分攻击

对分组密码算法MIBS在积分攻击下的安全性进行了研究,构造了MIBS算法的5轮积分区分器,利用Feistel结构的等价结构以及MIBS密钥扩展算法中主密钥和轮密钥的关系,对10轮MIBS算法实施了积分攻击,给出了攻击算法。攻击10轮MIBS-64的数据复杂度和时间复杂度分别为 和 ,攻击10轮MIBS-80的数据复杂度和时间复杂度分别为 和 。分析结果表明,10轮MIBS算法对积分攻击是不免疫的,该积分攻击的轮数和数据复杂度上都要优于已有的积分攻击。     

不可预测性与伪随机性是等价的一种应用

伪随机产生器是一种有效的确定性算法,它将随机选择的位种子扩展为较长的伪随机序列,并且这些序列在多项式时间内与真正的随机序列是不可分的。本篇文章中主要是在大整数分解是困难的假设条件下,对Goldreich已构造的一种伪随机产生器,利用不可预测性与伪随机性是等价的方法进行另一种证明。     

Zero correlation-integral attack of MIBS block cipher

MIBS is a lightweight block cipher for extremely constrained environments such as RFID tags and sensor networks. The MIBS algorithm's ability to resist zero correlation-integral analysis was evaluated. An 8-round zero corre-lation linear distinguisher of MIBS was given. Then, a 8-round distinguisher of MIBS was founded by using relationship between zero-correlation linear distinguisher and integral distinguisher. Finally, considering the symmetrical structure of the MIBS and using the partial-sum technique, it applied integral attack to 10 and 12 rounds of MIBS-80. The time com-plexities of 10 and 12 round attack on MIBS-80 are 2^27.68and 2^48.81. The data complexity is 2⁴⁸.     

UMTS security: system architecture and hardware implementation

Universal mobile telecommunication system (UMTS) has specified security mechanisms with extra features compared to the security mechanisms of previous mobile communication systems (GSM, DECT). A hardware implementation of the UMTS security mechanism is presented in this paper. The proposed VLSI system supports the Authentication and Key Agreement procedure (AKA), the data confidentiality procedure, and the integrity protection procedure. The AKA procedure is based on RIJNDAEL Block Cipher. An efficient RIJNDAEL architecture is proposed in order to minimize the usage of hardware resources. The proposed implementation performs the AKA procedure within 76 µs comparing with the 500 ms that UMTS specifies. The data confidentiality and the integrity protection is based on KASUMI Block Cipher. The proposed KASUMI architecture reduces the hardware resources and power consumption. It uses feedback logic and positive‐negative edge‐triggered pipeline in order to make the critical path shorter, without increasing the execution latency. The S‐BOXes that are used from RIJNDAEL and KASUMI block ciphers have been implemented with combinational logic as well as with ROM blocks. Copyright © 2006 John Wiley & Sons, Ltd.     

改进的CBC 模式及其安全性分析

针对CBC模式在分块适应性攻击模型下不安全这一问题,提出了一个新的分组密码工作模式。新方案引进了Gray码,改变了原有模式的输入方式,打乱了前后输出输入的内在联系。同时,利用规约的思想对其安全性进行了分析。结果表明,在所用分组密码是伪随机置换的条件下,方案在分块适应性攻击模型下是可证明安全的。     

Feistel-SPS结构的反弹攻击

该文给出了以Feistel结构为主框架,以SPS(Substitution-Permutation-Substitution)函数作为轮函数的Feistel-SPS结构的反弹攻击。通过对差分扩散性质的研究,得到这一结构的6轮已知密钥截断差分区分器,并在此区分器的基础上,给出将这一结构内嵌入MMO(Matyas-Meyer-Oseas)和MP(Miyaguchi-Preneel)模式所得到的压缩函数的近似碰撞攻击。此外,还将6轮截断差分区分器扩展,得到了7轮的截断差分路径,基于此还得到上述两种模式下压缩函数的7轮截断差分区分器。     

High-Performance Hardware Implementation of the 3GPP Algorithm KASUMI

1IntroductionWithin the security architecture of the3GPP systemthere are two standardized algorithms:a confidentialityalgorithmf8,and an integrity algorithm f9.Each ofthese algorithms is based on the KASUMI algorithm.KASUMI is a block cipher that produces…     

A Practical Implementation Attack on Weak Pseudorandom Number Generator Designs for EPC Gen2 Tags

The Electronic Product Code Generation 2 (EPC Gen2) is an international standard that proposes the use of Radio Frequency Identification (RFID) in the supply chain. It is designed to balance cost and functionality. As a consequence, security on board of EPC Gen2 tags is often minimal. It is, indeed, mainly based on the use of on board pseudorandomness, used to obscure the communication between readers and tags; and to acknowledge the proper execution of password-protected operations. In this paper, we present a practical implementation attack on a weak pseudorandom number generator (PRNG) designed specifically for EPC Gen2 tags. We show that it is feasible to eavesdrop a small amount of pseudorandom values by using standard EPC commands and using them to determine the PRNG configuration that allows to predict the complete output sequence.     

SP-GFS结构的积分性质研究

该文提出了扩散级数的定义,刻画了线性置换的扩散性质。此外针对SP(Substitute Permutation)轮函数的整体结构GFS(Generalized Feistel Structure)进行了积分性质分析,通过分析线性置换P的扩散级数对积分区分器长度的影响,证明得出SP-GFS结构的积分区分器轮数下界。最后用这种方法改进了分组算法Camellia和CLEFIA的积分区分器,从而验证了结论的正确性。     

优化MISTY型结构的伪随机性

该文对4轮MISTY和3轮双重MISTY两种结构进行了优化。在保持其安全性不变的情况下,把4轮MISTY结构中第1轮的伪随机置换,用一个XOR-泛置换代替,第2,第3轮采用相同的伪随机置换,3轮结构中第1轮的伪随机置换用XOR-泛置换代替,其它轮相同。伪随机置换的数量分别由原来的4个变为2个,3个变为1个,从而缩短了运行时间,节省了密钥量,大大降低了结构的实现成本。     

Transparent random access memory testing for pattern sensitive faults

This paper presents a new methodology for RAM testing based on the PS(n, k) fault model (the k out of n pattern sensitive fault model). According to this model the contents of any memory cell which belongs to an n-bit memory block, or the ability to change the contents, is influenced by the contents of any k -1 cells from this block. The proposed methodology is a transparent BIST technique, which can be efficiently combined with on-line error detection. This approach preserves the initial contents of the memory after the test and provides for a high fault coverage for traditional fault and error models, as well as for pattern sensitive faults. This paper includes the investigation of testing approaches based on transparent pseudoexhaustive testing and its approximations by deterministic and pseudorandom circular tests. The proposed methodology can be used for periodic and manufacturing testing and require lower hardware and time overheads than the standard approaches.This work was supported by the NSF under Grant MIP9208487 and NATO under Grant 910411.     

Impossible Differential Cryptanalysis on Lai‐Massey Scheme

The Lai‐Massey scheme, proposed by Vaudenay, is a modified structure in the International Data Encryption Algorithm cipher. A family of block ciphers, named FOX, were built on the Lai‐Massey scheme. Impossible differential cryptanalysis is a powerful technique used to recover the secret key of block ciphers. This paper studies the impossible differential cryptanalysis of the Lai‐Massey scheme with affine orthomorphism for the first time. Firstly, we prove that there always exist 4‐round impossible differentials of a Lai‐Massey cipher having a bijective F‐function. Such 4‐round impossible differentials can be used to help find 4‐round impossible differentials of FOX64 and FOX128. Moreover, we give some sufficient conditions to characterize the existence of 5‐, 6‐, and 7‐round impossible differentials of Lai‐Massey ciphers having a substitution‐permutation (SP) F‐function, and we observe that if Lai‐Massey ciphers having an SP F‐function use the same diffusion layer and orthomorphism as a FOX64, then there are indeed 5‐ and 6‐round impossible differentials. These results indicate that both the diffusion layer and orthomorphism should be chosen carefully so as to make the Lai‐Massey cipher secure against impossible differential cryptanalysis.     

MD-64算法的相关密钥-矩形攻击

该文针对MD-64分组密码算法在相关密钥-矩形攻击下的安全性进行了研究。分析了算法中高次DDO (Data Dependent Operations)结构、SPN结构在输入差分重量为1时的差分转移规律,利用高次DDO结构的差分特性和SPN结构重量为1的差分路径构造了算法的两条相关密钥-差分路径,通过连接两条路径构造了算法的完全轮的相关密钥-矩形区分器,并对算法进行了相关密钥-矩形攻击,恢复出了32 bit密钥。攻击算法所需的数据复杂度为262相关密钥-选择明文,计算复杂度为291.6次MD-64算法加密,存储复杂度为266.6 Byte存储空间,成功率约为0.961。分析结果表明,MD-64算法在相关密钥-矩形攻击条件下的安全性无法达到设计目标。     

一种新的简化AES中间相遇攻击方法

A new 5-round distinguisher of AES with key whitening is presented by using the properties of its round transformation. Based on this distinguisher, we present new meet-inthe-middle attacks on reduced AES considering the key schedule and the time-memory tradeoff approach. New attacks improve the best known meet-in-the-middle attacks on reduced AES presented at FSE2008.We reduce the time complexity of attacks on 7-round AES-192 and 8-round AES-256 by a factor of at least 28. Moreover, the distinguisher can be exploited to develop the attack on 8-round AES-192.