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.     

Improved impossible differential and biclique cryptanalysis of HIGHT

HIGHT is a lightweight block cipher introduced in CHES 2006 by Hong et al as a block cipher suitable for low‐resource applications. In this paper, we propose improved impossible differential and biclique attacks on HIGHT block cipher both exploiting the permutation‐based property of the cipher's key schedule algorithm as well as its low diffusion. For impossible differential attack, we found a new 17‐round impossible differential characteristic that enables us to propose a new 27‐round impossible differential attack. The total time complexity of the attack is 2^120.4 where an amount of 2^59.3 chosen plaintext‐ciphertext pairs and 2^107.4 memory are required. We also instantiate a new biclique cryptanalysis of HIGHT, which is based on the new idea of splitting each of the forward and backward keys into 2 parts where the computations associated to each one are performed independently. The time complexity and data complexity of this attack are 2^125.7 and 2⁴², respectively. To the best of our knowledge, this is the fastest biclique attack on full‐round HIGHT.     

Efficient Slide Attacks

The slide attack, presented by Biryukov and Wagner, has already become a classical tool in cryptanalysis of block ciphers. While it was used to mount practical attacks on a few cryptosystems, its practical applicability is limited, as typically, its time complexity is lower bounded by \(2^n\) (where n is the block size). There are only a few known scenarios in which the slide attack performs better than the \(2^n\) bound. In this paper, we concentrate on efficient slide attacks, whose time complexity is less than \(2^n\). We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least \(2^n\) operations. In particular, we present the first known slide attack on a Feistel construction with a 3-round self-similarity, and an attack with practical time complexity of \(2^{40}\) on a 128-bit key variant of the GOST block cipher with unknown S-boxes. The best previously known attack on the same variant, with known S-boxes (by Courtois), has time complexity of \(2^{91}\).     

Structural Cryptanalysis of SASAS

In this paper we consider the security of block ciphers which contain alternate layers of invertible S-boxes and affine mappings (there are many popular cryptosystems which use this structure, including the winner of the AES competition, Rijndael). We show that a five-layer scheme with 128-bit plaintexts and 8-bit S-boxes is surprisingly weak against what we call a multiset attack, even when all the S-boxes and affine mappings are key dependent (and thus completely unknown to the attacker). We tested the multiset attack with an actual implementation, which required just 2¹⁶ chosen plaintexts and a few seconds on a single PC to find the 2¹⁷ bits of information in all the unknown elements of the scheme.     

Cryptanalysis of mCrypton‐64

In recent years, because of the security requirements of resource‐constrained devices, design and analysis of lightweight block ciphers has received more attention. mCrypton is a lightweight block cipher that has been specifically designed for using in resource‐constrained devices, such as low‐cost radio‐frequency identification tags and sensors. In this paper, we consider cryptanalysis of full‐round mCrypton‐64 using a new extension of biclique attack called non‐isomorphic biclique cryptanalysis. As it is known, effectiveness of the biclique attack is highly dependent to the weakness of key schedule, and it does not seem to be appropriate for block ciphers with strong key scheduling. The non‐isomorphic biclique attack, using an asymmetric key partitioning technique, provides more degrees of freedom to the attacker and makes it possible to use the diffusion layer properties of a block cipher for constructing longer bicliques. Results show that the attack on full‐round mCrypton requires 2^33.9 chosen plaintexts and a time complexity of 2^62.67 encryptions. The computational complexity reduces to 2^62.3, 2^61.4, and 2^59.75 encryptions for 10, 8, and 6 rounds of mCrypton‐64, respectively. We also have a discussion on the general form of the computational complexity for non‐isomorphic biclique cryptanalysis. Copyright © 2014 John Wiley & Sons, Ltd.     

Two-Key Triple Encryption

In this paper we consider multiple encryption schemes built from conventional cryptosystems such as DES. The existing schemes are either vulnerable to variants of meet-in-the-middle attacks, i.e., they do not provide security corresponding to the full key length used or there is no proof that the schemes are as secure as the underlying cipher. We propose a variant of two-key triple encryption with a new method of generating three keys from two. Our scheme is not vulnerable to the meet-in-the-middle attack and, under an appropriate assumption, we can show that our scheme is at least about as hard to break as the underlying block cipher. Received 22 June 1995 and revised 11 October 1996     

Attacks on Block Ciphers of Low Algebraic Degree

In this paper an attack on block ciphers is introduced, the interpolation attack. This method is useful for attacking ciphers that use simple algebraic functions (in particular quadratic functions) as S-boxes. Also, attacks based on higher-order differentials are introduced. They are special and important cases of the interpolation attacks. The attacks are applied to several block ciphers, the six-round prototype cipher by Nyberg and Knudsen, which is provably secure against ordinary differential cryptanalysis, a modified version of the block cipher SHARK, and a block cipher suggested by Kiefer. Received April 1999 and revised October 2000 Online publication 9 April 2001     

Security Analysis of A Stream Cipher with Proven Properties

Si and Ding proposed a stream cipher with two keys (the first and the second key) and an expected security strength. To further measure the security, we analyze the stream cipher by considering the selective discrete Fourier spectra attack and the fast selective discrete Fourier spectra attack. The two attacks reveal a fact that the second key is more important than the first key, that is, if the second key is leaked out, the first key can be obtained with a lower time complexity than that of the expected security. In addition, we analyze the ability of the stream cipher to resist the guess-and-determine attack. The results show an attacker is able to gain the two keys with an exponentially improved time complexity and a polynomial data complexity. It implies that we need a securer permutation over finite fields to design a new binary additive stream cipher to achieve the expected security level.     

Security analysis of pure DDP-based cipher proper for multimedia and ubiquitous device

DDP-64, based on various controlled operations, is a 64-bit Feistel-like block cipher consisting of 10 rounds with a 128-bit key. It was designed to attempt to have a high security level and a high speed performance in hardware on ubiquitous computing systems and multimedia. In this paper, however, we show that DDP-64 doesn’t have a high security level, more precisely, we show that it is vulnerable to related-key differential attack. This attack, which is much faster than the key exhaustive search, requires about 2⁵⁴ data and 2⁵⁴ time complexities. This work is the first known cryptanalytic result on DDP-64 so far.     

Provable security against a differential attack

The purpose of this paper is to show that DES-like iterated ciphers that are provably resistant against differential attacks exist. The main result on the security of a DES-like cipher with independent round keys is Theorem 1, which gives an upper bound to the probability of s-round differentials, as defined in [4], and this upper bound depends only on the round function of the iterated cipher. Moreover, it is shown that functions exist such that the probabilities of differentials are less than or equal to 2^3–n , where n is the length of the plaintext block. We also show a prototype of an iterated block cipher, which is compatible with DES and has proven security against differential attack.A preliminary version of this paper was presented in the rump session at Crypto '92. The work of Kaisa Nyberg on this project was supported by MATINE Board, Finland.     

基于FPGA平台的Piccolo功耗分析安全性评估

为了评估Piccolo密码算法的功耗分析安全性,该文提出一种针对Piccolo末轮的攻击模型,基于SASEBO (Side-channel Attack Standard Evaluation BOard)实测功耗数据对该算法进行了相关性功耗分析攻击。针对Piccolo末轮运算中包含白化密钥的特点,将末轮攻击密钥(包括轮密钥RK24L, RK24R, WK2, WK3)分成4段子密钥,逐个完成各个子密钥的攻击,使80位种子密钥的搜索空间从280降低到(2220+2212+216),使种子密钥的恢复成为可能。攻击结果表明,在实测功耗数据情况下,3000条功耗曲线即可恢复80位种子密钥,证实了该攻击模型的有效性和Piccolo硬件面向功耗分析的脆弱性,研究并采取切实有效的防护措施势在必行。     

轻量级分组密码算法ESF的相关密钥不可能差分分析

八阵图算法(ESF)是一种具有广义Feistel结构的轻量级分组密码算法,可用在物联网环境下保护射频识别(RFID)标签等资源受限的环境中,目前对该算法的安全性研究主要为不可能差分分析。该文通过深入研究S盒的特点并结合ESF密钥扩展算法的性质,研究了ESF抵抗相关密钥不可能差分攻击的能力。通过构造11轮相关密钥不可能差分区分器,在此基础上前后各扩展2轮,成功攻击15轮ESF算法。该攻击的时间复杂度为240.5次15轮加密,数据复杂度为261.5个选择明文,恢复密钥比特数为40 bit。与现有结果相比,攻击轮数提高的情况下,时间复杂度降低,数据复杂度也较为理想。     

Parent–Daughter Confusion Component: A New Approach for the Construction of Nonlinear Confusion Component

The nonlinear confusion component is one of an integral part of any modern block cipher. This nonlinear confusion component is used to hides the relationship between the ciphertext and the key. The primary objective of this article is to formulate a new mechanism for the construction this confusion component. Usually substitution box (S-box) is used to achieve this kind of characteristics in block ciphers. We have utilized deoxyribonucleic acid (DNA) sequences for the construction of new S-boxes with optimized cryptographic characteristics. The projected technique fundamentally optimized the DNA sequences along with traditional confusion component to generate a completely new S-box. The obtained S-boxes have the same cryptographic strength as a parent S-box have.

     

Constructing Chaos Based Substitution Boxes Using the Composition of Transpositions

Wireless Personal Communications - The chaotic systems have been used in the construction of the substitution boxes (S-boxes) which play a key role in modern block cipher. In this paper, we propose...     

Cryptanalysis of block-wise stream ciphers suitable for the protection of multimedia and ubiquitous systems

In this paper we introduce a general framework of related-key attack on block-wise stream ciphers which are suitable for the protection of multimedia and ubiquitous systems. As a case study, we show how our cryptanalytic framework is applied to a block-wise stream cipher TWOPRIME: we construct various related-key differentials of TWOPRIME and use them to show that recovering related keys of TWOPRIME can be performed with a data complexity of 2¹⁴ known plaintext blocks and a time complexity of 2³² 8-bit table lookups. We expect that our general framework for a related-key attack would be useful tool for analyzing many of block-wise stream ciphers.     

Cryptanalysis of mCrypton—A lightweight block cipher for security of RFID tags and sensors

mCrypton is a 64‐bit lightweight block cipher designed for use in low‐cost and resource‐constrained applications such as RFID tags and sensors in wireless sensor networks. In this paper, we investigate the strength of this cipher against related‐key impossible differential cryptanalysis. First, we construct two 6‐round related‐key impossible differentials for mCrypton‐96 and mCrypton‐128. Then, using these distinguishers, we present 9‐round related‐key impossible differential attacks on these two versions. The attack on mCrypton‐96 requires 2^59.9 chosen plaintexts, and has a time complexity of about 2^74.9 encryptions. The data and time complexities for the attack on mCrypton‐128 are 2^59.7 chosen plaintexts and 2^66.7 encryptions, respectively. Copyright © 2011 John Wiley & Sons, Ltd.     

Key Recovery Attacks on Iterated Even–Mansour Encryption Schemes

Iterated Even–Mansour (EM) encryption schemes (also named “key-alternating ciphers”) were extensively studied in recent years as an abstraction of commonly used block ciphers. A large amount of previous works on iterated EM concentrated on security in an information-theoretic model. A central question studied in these papers is: What is the minimal number of rounds for which the resulting cipher is indistinguishable from an ideal cipher? In this paper, we study a similar question in the computational model: What is the minimal number of rounds, assuring that no attack can recover the secret key faster than trivial attacks (such as exhaustive search)? We study this question for the two natural key scheduling variants that were considered in most previous papers: the identical subkeys variant and the independent subkeys variant. In the identical subkeys variant, we improve the best known attack by an additional round and show that \(r=3\) rounds are insufficient for assuring security, by devising a key recovery attack whose running time is about \(n/\log (n)\) times faster than exhaustive search for an \(n\)-bit key. In the independent subkeys variant, we also extend the known results by one round and show that for \(r=2\), there exists a key recovery attack whose running time is faster than the benchmark meet-in-the-middle attack. Despite their generic nature, we show that the attacks can be applied to improve the best known attacks on several concrete ciphers, including the full \({\hbox {AES}^{2}}\) (proposed at Eurocrypt 2012) and reduced-round LED-128 (proposed at CHES 2012).     

A Detailed Analysis of SAFER K

In this paper we analyze the block cipher SAFER K. First, we show a weakness in the key schedule, that has the effect that for almost every key there exists on the average three and a half other keys such that the encryptions of plaintexts different in one of eight bytes yield ciphertexts also different in only one byte. Moreover, the differences in the keys, plaintexts, and ciphertexts are in the same byte. This enables us to do a related-key chosen plaintext attack on SAFER K, which finds the secret key. Also, the security of SAFER K, when used in standard hashing modes, is greatly reduced, which is illustrated. Second, we propose a new key schedule for SAFER K avoiding these problems. Third, we do differential cryptanalysis of SAFER K. We consider truncated differentials and apply them in an attack on five-round SAFER K, which finds the secret key much faster than by an exhaustive search. Received 21 December 1997 and revised 29 May 1998     

Partial Key Recovery Attack Against RMAC

In this paper new “partial” key recovery attacks against the RMAC block cipher based Message Authentication Code scheme are described. That is we describe attacks that, in some cases, recover one of the two RMAC keys much more efficiently than previously described attacks. Although all attacks, but one, are of no major threat in practice, in some cases there is reason for concern. In particular, the recovery of the second RMAC key (of k bits) may only require around 2^k/2 block cipher operations (encryptions or decryptions). The RMAC implementation using triple DES proposed by NIST is shown to be very weak.     

An enhanced chaotic key‐based RC5 block cipher adapted to image encryption

RC5 is a block cipher that has several salient features such as adaptability to process different word lengths with a variable block size, a variable number of rounds and a variable‐length secret key. However, RC5 can be broken with various attacks such as correlation attack, timing attack, known plaintext correlation attack and differential attacks, revealing weak security. We aimed to enhance the RC5 block cipher to be more secure and efficient for real‐time applications while preserving its advantages. For this purpose, this article introduces a new approach based on strengthening both the confusion and diffusion operations by combining chaos and cryptographic primitive operations to produce round keys with better pseudo‐random sequences. Comparative security analysis and performance evaluation of the enhanced RC5 block cipher (ERC5) with RC5, RC6 and chaotic block cipher algorithm (CBCA) are addressed. Several test images are used for inspecting the validity of the encryption and decryption algorithms. The experimental results show the superiority of the suggested enhanced RC5 (ERC5) block cipher to image encryption algorithms such as RC5, RC6 and CBCA from the security analysis and performance evaluation points of view.