On unbalanced Feistel networks with contracting MDS diffusion

Though unbalanced Feistel networks (UFN) are widely considered as an alternative to balanced Feistel networks (BFN) and substitution?Cpermutation networks (SPN) in symmetric cryptography, little has been known yet about their resistance against differential and linear cryptanalysis. In this work, we tackle the problem at the example of d-branch SP-type UFNs with contracting MDS diffusion (dCUFN-SP). Under some restrictions on the contracting MDS matrices over multiple rounds, we prove lower bounds on the number of differentially active S-boxes for dCUFN-SP with ${d\in\{3,4\}}$ and on the number of linearly active S-boxes for dCUFN-SP with d ?? 3. As opposed to SPNs and BFNs, the number of differentially active S-boxes for such constructions does not directly translate to an upper bound on the probability of differential trails. So we provide a thorough analysis of single-round differentials that yields an upper bound on the probability of a differential trail. It is also shown that the efficiency level of dCUFN-SP is comparable to that of BFNs and SPNs with respect to differential and linear cryptanalysis.     

Conditional cube attack on round-reduced River Keyak

This paper evaluates the security level of the River Keyak against the cube-like attack. River Keyak is the only lightweight scheme of the Keccak-permutation-based authenticated encryption cipher Keyak, which is one of the 16 survivors of the third round CAESAR competition. Dinur et al. gave the seven-round cube-like attack on Lake Keyak (1600-bit) using the divide-and-conquer method at EUROCRYPT 2015, then Huang et al. improved the result to eight-round using a new conditional cube attack at EUROCRYPT 2017. While for River Keyak, the 800-bit state is so small that the equivalent key (256-bit capacity) occupy double lanes, the attacks can not be applied to the River Keyak trivially. In this paper, we comprehensively explore the conditional cube attack on the small state (800-bit) River Keyak. Firstly, we find a new conditional cube variable which has a much weaker diffusion than Huang et al.’s, this makes the conditional cube attack possible for small state (800-bit) River Keyak. Then we find enough cube variables for six/seven-round River Keyak and successfully launch the key recovery attacks on six/seven-round River Keyak with the time complexity \(2^{33}\) and \(2^{49},\) respectively. We also verify the six and seven-round attack on a laptop. Finally, by using linear structure technique with our new conditional cube variable, we greatly increase the freedom degree to find more cube variables for conditional cube attacks as it is complex for 800-bit state to find enough cube variables for eight-round attack. And then we use the new variables by this new method to launch eight-round conditional cube attack with the time complexity \(2^{81}.\) These are the first cryptanalysis results on round-reduced River Keyak. Our attacks do not threaten the full-round (12) River Keyak.     

Generalization of Matsui’s Algorithm 1 to linear hull for key-alternating block ciphers

We consider linear approximations of an iterated block cipher in the presence of several strong linear approximation trails. While the effect of such trails in Matsui’s Algorithm 2, also called the linear hull effect, has been previously studied by a number of authors, their effect on Matsui’s Algorithm 1 has not been investigated until now. The goal of this paper is to fill this gap and examine how to generalize Matsui’s Algorithm 1 to work also on linear hulls. We restrict to key-alternating ciphers and develop a mathematical framework for this kind of attacks. The complexity of the attack increases with the number of linear trails that have significant contribution to the correlation. We show how to reduce the number of trails and thus the complexity using related keys. Further, we illustrate our theory by experimental results on a reduced round version of the block cipher PRESENT.     

Improved distinguishers for HC-128

HC-128 is an eSTREAM final portfolio stream cipher. Several authors have investigated its security and, in particular, distinguishing attacks have been considered. Still, no one has been able to provide a distinguisher stronger than the one presented by Wu in the original HC-128 paper. In this paper we first argue that the keystream requirement in Wu’s original attack is underestimated by a factor of almost 2⁸. Our revised analysis shows that the keystream complexity of Wu’s original attack is 2^160.471 32-bit keystream blocks. We then go on to investigate two new types of distinguishers on HC-128. One of them, a distinguisher counting the number of zeros in created blocks of bits, gives a biased distribution that requires 2^143.537 such constructed block samples (2^152.537 32-bit keystream blocks). For fairness, the same metric is used to compare our attack to Wu’s, and our improvement is significant compared to Wu’s original result. Furthermore, the vector-based methodology used is general and can be applied to any cryptographic primitive that reveals a suitable probability distribution.     

Improving algebraic attacks on stream ciphers based on linear feedback shift register over $$\mathbb {F}_{2^k}$$

In this paper we investigate univariate algebraic attacks on filter generators over extension fields \(\mathbb {F}_q=\mathbb {F}_{2^n}\) with focus on the Welch–Gong (WG) family of stream ciphers. Our main contribution is to reduce the general algebraic attack complexity on such cipher by proving new and lower bounds for the spectral immunity of such ciphers. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the minimum number of nonzero coefficients of a multiple of a univariate polynomial. In particular, there is an algebraic degeneracy in these constructions, which, when combined with attacks based on low-weight multiples over \(\mathbb {F}_q\), provides much more efficient attacks than over \(\mathbb {F}_2\). With negligible computational complexity, our best attack breaks the primitive WG-5 if given access to 4 kilobytes of keystream, break WG-7 if given access to 16 kilobytes of keystream and break WG-8 if given access to half a megabyte of keystream. Our best attack on WG-16 targeted at 4G-LTE is less practical, and requires \(2^{103}\) computational complexity and \(2^{61}\) bits of keystream. In all instances, we significantly lower both keystream and computational complexity in comparison to previous estimates. On a side note, we resolve an open problem regarding the rank of a type of equation systems used in algebraic attacks.     

On non-negligible bias of the first output byte of RC4 towards the first three bytes of the secret key

In this paper, we show that the first byte of the keystream output of RC4 has non-negligible bias towards the sum of the first three bytes of the secret key. This result is based on our observation that the index, where the first byte of the keystream output is chosen from, is approximately twice more likely to be 2 than any other value. Our technique is further used to theoretically prove Roos’s experimental observation (A class of weak keys in the RC4 stream cipher, 1995) related to weak keys.     

Cryptanalysis of a chaos block cipher for wireless sensor network

Based on the analysis of a chaos block cipher for wireless sensor network (WSN), it is found that there is a fatal flaw in its security because the number of rounds is too small and the calculation precision of round function is too short. The scheme could be cryptanalyzed by utilizing differential cryptanalysis theory. First, the third round key is recovered by chosen plaintext attack according to the characteristics of the round function. Then, the second round key can be deduced from the relationship of the sub-keys between the second and the third rounds. Based on the above successful attacks, the first round key could also be broken by brute-force attack. Finally, by employing the characteristics of Feistel structure, the fourth round key could also be obtained. Since all round keys have been cryptanalyzed, the plaintext can then be decrypted. The encryption scheme is proven to be insecure consequently.     

Resistance of a CAST-Like Encryption Algorithm to Linear and Differential Cryptanalysis

Linear cryptanalysis and differential cryptanalysis are two recently introduced, powerful methodologies for attacking private-key block ciphers. In this paper, we examine the application of these two cryptanalysis techniques to a CAST-like encryption algorithm. It is shown that, when randomly generated substitution boxes (s-boxes) are used in a CAST-like encryption algorithm, the resulting cipher is resistant to both the linear attack and the differential attack.     

Zero-correlation linear cryptanalysis of reduced-round LBlock

Zero-correlation linear attack is a new method developed by Bogdanov et al. (ASIACRYPT 2012. LNCS, Springer, Berlin, 2012) for the cryptanalysis of block ciphers. In this paper we adapt the matrix method to find zero-correlation linear approximations. Then we present several zero-correlation linear approximations for 14 rounds of LBlock and describe a cryptanalysis for a reduced 22-round version of LBlock. After biclique attacks on LBlock revealed weaknesses in its key schedule, its designers presented a new version of the cipher with a revised key schedule. The attack presented in this paper does not exploit the structure of the key schedule or S-boxes used in the cipher. As a result, it is applicable to both variants of the LBlock as well as the block ciphers with analogous structures like TWINE. Moreover, we performed simulations on a small variant LBlock and present the first experimental results on the theoretical model of the multidimensional zero-correlation linear cryptanalysis method.     

Truncated differential based known-key attacks on round-reduced SIMON

At Crypto 2015, Blondeau, Peyrin and Wang proposed a truncated-differential-based known-key attack on full PRESENT, a nibble oriented lightweight block cipher with an SPN structure. The truncated difference they used is derived from the existing multidimensional linear characteristics. An innovative technique of their work is the design of a MITM layer added before the characteristic that covers extra rounds with a complexity lower than that of a generic construction. We notice that there are good linear hulls for bit-oriented block cipher SIMON corresponding to highly qualified truncated differential characteristics. Based on these characteristics, we propose known-key distinguishers on round-reduced SIMON block cipher family, which is bit oriented and has a Feistel structure. Similar to the MITM layer, we design a specific start-from-the-middle method for pre-adding extra rounds with complexities lower than generic bounds. With these techniques, we launch basic known-key attacks on round-reduced SIMON. We also involve some key guessing technique and further extend the basic attacks to more rounds. Our known-key attacks can reach as many as 29/32/38/48/63-rounds of SIMON32/48/64/96/128, which comes quite close to the full number of rounds. To the best of our knowledge, these are the first known-key results on the block cipher SIMON.     

Correlation Analysis of the Alternating Step Generator

The alternating step generator is a well-known keystream generator consisting of two stop/go clocked LFSRs, LFSR₁ and LFSR₂, whose clocks are controlled by another LFSR, LFSR₃, which is clocked regularly. A probabilistic analysis of this generator is conducted which shows that the posterior probabilites of individual bits of the first derivatives of the regularly clocked LFSR₁ and LFSR₂ sequences, when conditioned on a given segment of the first derivative of the keystream sequence, can be computed efficiently in a number of probabilistic models of interest. The expected values of these probabilities, for a random keystream sequence, are derived by an approximate theoretical analysis and are also verified by systematic computer experiments. It is pointed out that these posterior probabilities can be enhanced in a resynchronization scenario and thus used for a low-complexity fast correlation attack on the two LFSRs. More generally, it is argued that even without resynchronization these probabilities may be significantly different from one half for fast correlation attacks based on iterative decoding algorithms to be successful, although with incresead complexity. A related method for computing the posterior probabilities of individual bits of the LFSR₃ sequence, when conditioned on both the keystream sequence and the LFSR₁ and LFSR₂ sequences, is also developed. As these posterior probabilities are much more different from one half, they can be used for a low-complexity fast correlation attack on LFSR₃, provided that the initial states of LFSR₁ and LFSR₂ are previously reconstructed.     

一种基于后验概率判决的one-by-one快速相关攻击算法(英文)

本文描述了一种基于后验概率判决的 one by one快速相关攻击算法.本文试图通过概率的观点来看待和分析快速相关攻击问题.该算法的优点有以下三点.首先,和文献[5]相比 one by one算法减少了对存储空间的需求.其次,提出了攻击失败概率的概念,并利用中心极限定理给出了它和密钥流序列长度的关系.最后,和文献[4]相比,该算法只需要更少的密钥流序列就可以达到几乎相同的攻击效果.     

The (related-key) impossible boomerang attack and its application to the AES block cipher

The Advanced Encryption Standard (AES) is a 128-bit block cipher with a user key of 128, 192 or 256 bits, released by NIST in 2001 as the next-generation data encryption standard for use in the USA. It was adopted as an ISO international standard in 2005. Impossible differential cryptanalysis and the boomerang attack are powerful variants of differential cryptanalysis for analysing the security of a block cipher. In this paper, building on the notions of impossible differential cryptanalysis and the boomerang attack, we propose a new cryptanalytic technique, which we call the impossible boomerang attack, and then describe an extension of this attack which applies in a related-key attack scenario. Finally, we apply the impossible boomerang attack to break 6-round AES with 128 key bits and 7-round AES with 192/256 key bits, and using two related keys we apply the related-key impossible boomerang attack to break 8-round AES with 192 key bits and 9-round AES with 256 key bits. In the two-key related-key attack scenario, our results, which were the first to achieve this amount of attacked rounds, match the best currently known results for AES with 192/256 key bits in terms of the numbers of attacked rounds. The (related-key) impossible boomerang attack is a general cryptanalytic technique, and can potentially be used to cryptanalyse other block ciphers.     

Cryptanalysis of multilinear maps from ideal lattices: revisited

Multilinear map is a central primitive in cryptography and Garg, Gentry and Halevi proposed the first approximate multilinear maps over ideal lattices (GGH13 map) at EUROCRYPT 2013. Ever since then, multilinear maps has caused the extensive concern and has found too numerous applications to name. Very recently, Hu and Jia put forward an efficient attack on the multipartite key exchange and witness encryption based on GGH13 map. In this paper, we describe another efficient cryptanalysis of GGH13 map, an augmented version of Hu and Jia’s attack on it. More specifically, we improve their attacking tools and propose a “downgrading” method, which enable us to get a low level encoding from a higher level encoding. As a result, we can break the multilinear computational Diffie–Hellman assumption in the GGH13 setting with great ease while Hu and Jia only dealt with the decisional version. Furthermore, by applying our augmented cryptanalysis straightforwardly, we break two schemes from GGH13 map published at CRYPTO 2013: attribute-based encryption for general circuits and identity-based aggregate signatures.     

Finite Subsequences of Shift Register Sequences

In a stream cipher a cryptogram is produced from a binary datastream by modulo-2-adding it to a keystream sequence. The securityof the system relies on the inability of an interceptor to determinethis keystream sequence. One obvious requirement for such asystem is that there should be sufficiently many possibilitiesfor the keystream sequence that the interceptor cannot possiblytry them all. In this paper we consider the likelihood of an interceptor beingable to decipher the cryptogram correctly even though he maybe trying the wrong keystream sequence. This possibility arisesbecause the length of any particular message is likely to beconsiderably shorter than the period of the keystream sequence,and thus only a comparatively small section of the keystreamsequence is used. Hence, if the interceptor tries a sequencewhich intersects (i.e. agrees) with the keystream sequence inthe appropriate positions, he will deduce the message correctly. A number of the standard methods for generating keystream sequencesuse shift registers as ‘building blocks’. So welook in considerable detail at the number of intersections (ofvarious lengths) for sequences generated by two different shiftregisters. We also show that if a keystream sequence has linearequivalence n, then the local linear equivalence of any subsequenceof length at least 2n is n. This means that if the message haslength at least 2n and the keystream sequence has linear equivalencen, then there is no other sequence of linear equivalence lessthan n+1 which can be used to decipher correctly.     

Linear hulls with correlation zero and linear cryptanalysis of block ciphers

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on n bits, an algorithm of complexity 2 ^n-1 is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.     

Impossible differential cryptanalysis using matrix method

The general strategy of impossible differential cryptanalysis is to first find impossible differentials and then exploit them for retrieving subkey material from the outer rounds of block ciphers. Thus, impossible differentials are one of the crucial factors to see how much the underlying block ciphers are resistant to impossible differential cryptanalysis. In this article, we introduce a widely applicable matrix method to find impossible differentials of block cipher structures whose round functions are bijective. Using this method, we find various impossible differentials of known block cipher structures: Nyberg’s generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, Rijndael structures and generalized Skipjack-like structures. We expect that the matrix method developed in this article will be useful for evaluating the security of block ciphers against impossible differential cryptanalysis, especially when one tries to design a block cipher with a secure structure.     

Index Calculation Attacks on RSA Signature and Encryption

At Crypto ’85, Desmedt and Odlyzko described a chosen-ciphertext attack against plain RSA encryption. The technique can also be applied to RSA signatures and enables an existential forgery under a chosen-message attack. The potential of this attack remained untapped until a twitch in the technique made it effective against two very popular RSA signature standards, namely iso/iec 9796-1 and iso/iec 9796-2. Following these attacks, iso/iec 9796-1 was withdrawn and ISO/IEC 9796-2 amended. In this paper, we explain in detail Desmedt and Odlyzko’s attack as well as its application to the cryptanalysis of iso/iec 9796-2. AMS Classification: 11T71, 14G50, 94A60     

Zero-correlation attacks: statistical models independent of the number of approximations

Multiple and multidimensional zero-correlation linear cryptanalysis have been two of the most powerful cryptanalytic techniques for block ciphers, and it has been shown that the differentiating factor of these two statistical models is whether distinct plaintexts are assumed or not. Nevertheless, questions remain regarding how these analyses can be universalized without any limitations and can be used to accurately estimate the data complexity and the success probability. More concretely, the current models for multiple zero-correlation (MPZC) and multidimensional zero-correlation (MDZC) cryptanalysis are not valid in the setting with a limited number of approximations and the accuracy of the estimation for data complexity can not be guaranteed. Besides, in a lot of cases, using too many approximations may cause an exhaustive search when we want to launch key-recovery attacks. In order to generalize the original models using the normal approximation of the \(\chi ^2\)-distribution, we provide a more accurate approach to estimate the data complexity and the success probability for MPZC and MDZC cryptanalysis without such approximation. Since these new models directly rely on the \(\chi ^{2}\)-distribution, we call them the \(\chi ^{2}\) MPZC and MDZC models. An interesting thing is that the chi-square-multiple zero-correlation (\(\chi ^{2}\)-MPZC) model still works even though we only have a single zero-correlation linear approximation. This fact puts an end to the situation that the basic zero-correlation linear cryptanalysis requires the full codebook under the known-plaintext attack setting. As an illustration, we apply the \(\chi ^{2}\)-MPZC model to analyze TEA and XTEA. These new attacks cover more rounds than the previous MPZC attacks. Moreover, we reconsider the multidimensional zero-correlation (MDZC) attack on 14-round CLEFIA-192 by utilizing less zero-correlation linear approximations. In addition, some other ciphers which already have MDZC analytical results are reevaluated and the data complexities under the new model are all less than or equal to those under the original model. Some experiments are conducted in order to verify the validity of the new models, and the experimental results convince us that the new models provide more precise estimates of the data complexity and the success probability.