基于循环移位置换的超伪随机置换的构造

为了优化Luby和Rackoff给出的DES型置换的构造,我们给出了一种基于循环移位置换的超伪随机置换的构造方法。新构造简化了构造的复杂性和基于随机预言模型的安全性证明,并指出：首末两轮循环移位置换和中间两轮DES-型的随机置换的组合构造是超伪随机置换。新构造降低了区分优势的上界和敌手攻击成功的概率并降低了对首末轮函数的要求。     

Enhancements of Trapdoor Permutations

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich, Foundation of Cryptography: Basic Applications, 2004) and doubly enhanced trapdoor permutation (Goldreich, Computational Complexity: A Conceptual Perspective, 2011) as well as intermediate notions (Rothblum, A Taxonomy of Enhanced Trapdoor Permutations, 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, but they address natural concerns that may arise also in other applications of trapdoor permutations. We clarify why these enhancements are needed in such applications, and show that they actually suffice for these needs.     

DNA与密码分析

论文首先介绍了Weng-LongChang等人[1]用DNA方法分解整数(2k比特长)的算法,并与Beaver[2]的算法相比较。针对文献[1]中的算法,其瓶颈问题是所需溶液的体积随整数的规模而指数地增加,可改进文献[1]中的算法,使体积减少一半,但体积仍是指数级的。用DNA破解AES等分组密码面临同样的问题,因此,体积问题是破译RSA、AES等公钥(分组)密码共同面临的问题,而对这一问题,作者认为很难解决。     

Acoustic Cryptanalysis

Many computers emit a high-pitched noise during operation, due to vibration in some of their electronic components. These acoustic emanations are more than a nuisance: They can convey information about the software running on the computer and, in particular, leak sensitive information about security-related computations. In a preliminary presentation (Eurocrypt’04 rump session), we have shown that different RSA keys induce different sound patterns, but it was not clear how to extract individual key bits. The main problem was the very low bandwidth of the acoustic side channel (under 20  kHz using common microphones, and a few hundred kHz using ultrasound microphones), and several orders of magnitude below the GHz-scale clock rates of the attacked computers. In this paper, we describe a new acoustic cryptanalysis key extraction attack, applicable to GnuPG’s implementation of RSA. The attack can extract full 4096-bit RSA decryption keys from laptop computers (of various models), within an hour, using the sound generated by the computer during the decryption of some chosen ciphertexts. We experimentally demonstrate such attacks, using a plain mobile phone placed next to the computer, or a more sensitive microphone placed 10 meters away.     

Cryptanalysis of MD4

In 1990 Rivest introduced the hash function MD4. Two years later RIPEMD, a European proposal, was designed as a stronger mode of MD4. In 1995 the author found an attack against two of three rounds of RIPEMD. As we show in the present note, the methods developed to attack RIPEMD can be modified and supplemented such that it is possible to break the full MD4, while previously only partial attacks were known. An implementation of our attack allows us to find collisions for MD4 in a few seconds on a PC. An example of a collision is given demonstrating that our attack is of practical relevance. Received 23 October 1995 and revised 31 August 1997     

Cryptanalysis of self-shrinking generator

A simple cryptanalysis of the self-shrinking generator with very short keystream for the case of unknown connection polynomial is provided. The expected complexity of this cryptanalysis is 2/sup 1.5L/ when the length of the LFSR of the generator is L.     

Cryptanalysis of dragon scheme

Patarin proposed the dragon scheme,pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function.This paper presents an algebraic method to attack the candidate dragon signature algorithm.The attack borrows the basic idea of the attack due to Kipnis and Shamir,and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value.The attack recovers the private keys efficiently when the parameters are n≤25 and D=「logqd」≤3.     

对八阵图算法的不可能差分密码分析和线性密码分析

该文对八阵图(ESF)算法抵抗不可能差分密码分析和线性密码分析的能力进行了研究。ESF算法是一种具有Feistel结构的轻量级分组密码算法,它的轮函数为代换置换(SP)结构。该文首先用新的不可能差分区分器分析了12轮ESF算法,随后用线性密码分析的方法分析了9轮ESF算法。计算得出12轮不可能差分分析的数据复杂度大约为O(2⁶⁷),时间复杂度约为O(2^110.7),而9轮线性密码分析的数据复杂度仅为O(2³⁵),时间复杂度不大于O(2^15.6)。结果表明ESF算法足够抵抗不可能差分密码分析,而抵抗线性密码分析的能力相对较弱。     

Cryptanalysis of AEGIS-128

AEGIS, an authenticated encryption(AE) algorithm designed by H. J. Wu and B. Preneel, is one of the six winners of the Competition for Authenticated Encryption: Security, Applicability, and Robustness,which was launched by the National Institute of Standards and Technology. In this paper, we comprehensively investigate the existence of collision in the initialization of AEGIS-128 and evaluate the number of advanced encryption standard(AES) round functions involved in initialization, which reflec...     

Cryptanalysis of MD2

This paper considers the hash function MD2 which was developed by Ron Rivest in 1989. Despite its age, MD2 has withstood cryptanalytic attacks until recently. This paper contains the state-of-the-art cryptanalytic results on MD2, in particular collision and preimage attacks on the full hash function, the latter having complexity 2⁷³, which should be compared to a brute-force attack of complexity 2¹²⁸.     

Cryptanalysis of Polly Cracker

An attack on the public key cryptosystem Polly Cracker is described, that reveals the complete secret key σ ∈ F_q ⁿ by means of n (nonadaptively) chosen "fake" ciphertexts     

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.     

Slender-Set Differential Cryptanalysis

This paper considers PRESENT-like ciphers with key-dependent S-boxes. We focus on the setting where the same selection of S-boxes is used in every round. One particular variant with 16 rounds, proposed in 2009, is broken in practice in a chosen plaintext/chosen ciphertext scenario. Extrapolating these results suggests that up to 28 rounds of such ciphers can be broken. Furthermore, we outline how our attack strategy can be applied to an extreme case where the S-boxes are chosen uniformly at random for each round, and where the bit permutation is key-dependent as well.     

Differential-Linear Cryptanalysis Revisited

The two main classes of statistical cryptanalysis are the linear and differential attacks. They have many variants and enhancements such as the multidimensional linear attacks and the truncated differential attacks. The idea of differential-linear cryptanalysis is to apply first a truncated differential attack and then a linear attack on different parts of the cipher and then combine them to a single distinguisher over the cipher. This method is known since 1994 when Langford and Hellman presented the first differential-linear cryptanalysis of the DES. Recently, in 2014, Blondeau and Nyberg presented a general link between differential and linear attacks. In this paper, we apply this link to develop a concise theory of the differential-linear cryptanalysis. The differential-linear attack can be, in the theoretical sense, considered either as a multidimensional linear or a truncated differential attack, but is for both types an extreme case, which is best measured by the differential-linear bias. We give an exact expression of the bias in a closed form under the sole assumption that the two parts of the cipher are independent. Unlike in the case of ordinary differentials and linear approximations, it is not granted that restricting to a subset of characteristics of a differential-linear hull will give a lower bound on the absolute value of the bias. Given this, we revisit the previous treatments of differential-linear bias by Biham et al. in 2002–2003, Liu et al. in 2009, and Lu in 2012, and formulate assumptions under which a single differential-linear characteristic gives a close estimate of the bias. These results are then generalized by considering a subspace of linear approximations over the second part of the cipher. To verify the assumptions made, we present several experiments on a toy-cipher.     

Cryptanalysis of tree-structured ciphers

Tree structures have been proposed for both the construction of block ciphers by Kam and Davida (1979), and self-synchronous stream ciphers by Kuhn (1988). Attacks on these ciphers have been given by Anderson (1991), and Heys and Tavares (1993). Here the authors demonstrate that a more efficient attack can be conducted when the underlying Boolean functions for the cells are known. It is shown that this attack requires less than one third of the chosen ciphertext of Anderson's original attack on the Kuhn cipher     

Cryptanalysis of Full RIPEMD-128

In this article we propose a new cryptanalysis method for double-branch hash functions and we apply it on the standard RIPEMD-128, greatly improving over previously known results on this algorithm. Namely, we are able to build a very good differential path by placing one nonlinear differential part in each computation branch of the RIPEMD-128 compression function, but not necessarily in the early steps. In order to handle the low differential probability induced by the nonlinear part located in later steps, we propose a new method for using the available freedom degrees, by attacking each branch separately and then merging them with free message blocks. Overall, we present the first collision attack on the full RIPEMD-128 compression function as well as the first distinguisher on the full RIPEMD-128 hash function. Experiments on reduced number of rounds were conducted, confirming our reasoning and complexity analysis. Our results show that 16-year-old RIPEMD-128, one of the last unbroken primitives belonging to the MD-SHA family, might not be as secure as originally thought.     

基于遗传算法的密码分析方法

论文基于遗传算法的基本思想,给出了一个运用遗传算法进行密码分析的一种方法和算法,并验证了该方法的有效性。     

差分-双线性密码分析研究

差分密码分析和线性密码分析是分组密码分析中应用最广泛的技术.随着差分-线性密码分析的出现,一大批派生出来的密码分析方法表现出了很好的攻击效果.文中首先介绍了这两种密码分析方法的原理,然后推广到双线性密码分析.由于双线性密码分析攻击Feistel结构的密码特别有效,所以在某些场合,由差分密码分析和双线性密码分析结合成的差分-双线性密码分析具有比差分-线性密码分析更好的攻击效果.     

两种多重签名方案的密码分析

对两种多重签名方案进行了深入的研究,提出了一种伪造攻击方法。在第一种方案中,该攻击使得群体中任一成员都能在不经其他成员同意的条件下代表整个群体生成有效签名,这说明该方案是不安全的。在第二种方案中,这种攻击使得指定的合成者能获取任何签名者的秘密密钥,从而可以生成有效门限签名,因此这个方案也是不安全的。分析了攻击成功的原因,为同行设计安全的新方案提供了有效借鉴。     

构造正形置换的一种递归方法

首先给出了构造置换的一种递归方法。其次,借助这种方法给出了构造正形置换的一种递归方法。