共查询到20条相似文献,搜索用时 31 毫秒
1.
Luby and Rackoff [26] showed a method for constructing a pseudorandom permutation from a pseudorandom function. The method
is based on composing four (or three for weakened security) so-called Feistel permutations, each of which requires the evaluation
of a pseudorandom function. We reduce somewhat the complexity of the construction and simplify its proof of security by showing
that two Feistel permutations are sufficient together with initial and final pairwise independent permutations. The revised
construction and proof provide a framework in which similar constructions may be brought up and their security can be easily
proved. We demonstrate this by presenting some additional adjustments of the construction that achieve the following:
• Reduce the success probability of the adversary.
• Provide a construction of pseudorandom permutations with large input-length using pseudorandom functions with small input-length.
Received 2 August 1996 and revised 26 July 1997 相似文献
2.
为了优化Luby和Rackoff给出的DES型置换的构造,我们给出了一种基于循环移位置换的超伪随机置换的构造方法。新构造简化了构造的复杂性和基于随机预言模型的安全性证明,并指出:首末两轮循环移位置换和中间两轮DES-型的随机置换的组合构造是超伪随机置换。新构造降低了区分优势的上界和敌手攻击成功的概率并降低了对首末轮函数的要求。 相似文献
3.
Jean-Sébastien Coron Thomas Holenstein Robin Künzler Jacques Patarin Yannick Seurin Stefano Tessaro 《Journal of Cryptology》2016,29(1):61-114
This paper provides the first provably secure construction of an invertible random permutation (and of an ideal cipher) from a public random function that can be evaluated by all parties in the system, including the adversary. The associated security goal was formalized via the notion of indifferentiability by Maurer et al. (TCC 2004). The problem is the natural extension of that of building (invertible) random permutations from (private) random functions, first solved by Luby and Rackoff (SIAM J Comput 17(2):373–386, 1988) via the four-round Feistel construction. As our main result, we prove that the Feistel construction with fourteen rounds is indifferentiable from an invertible random permutation. We also provide a new lower bound showing that five rounds are not sufficient to achieve indifferentiability. A major corollary of our result is the equivalence (in a well-defined sense) of the random oracle model and the ideal cipher model. 相似文献
4.
On the Security of a Practical Identification Scheme 总被引:3,自引:0,他引:3
Victor Shoup 《Journal of Cryptology》1999,12(4):247-260
We analyze the security of an interactive identification scheme. The scheme is the obvious extension of the original square
root scheme of Goldwasser, Micali, and Rackoff to 2
m
th roots. This scheme is quite practical, especially in terms of storage and communication complexity. Although this scheme
is certainly not new, its security was apparently not fully understood. We prove that this scheme is secure if factoring integers
is hard, even against active attacks where the adversary is first allowed to pose as a verifier before attempting impersonation.
Received 29 July 1996 and revised 30 June 1998 相似文献
5.
Feistel-PG structure is a new specific Gen-eralized Feistel structure (GFS) adopted in DBlock and LHash. Its main feature is adding a sbox-size permutation before the round function. Different choices of the per-mutation may aff ect the security property of ciphers with Feistel-PG structure but how it eff ects is not clear. We evaluate the values of diffusion round for all possible pa-rameters and summarize the characteristics of optimum shuffles. The results show that one special kind of Feistel-PG achieves full diffusion in less cost than the improved GFS. This advantage may attract the designers' interests and this kind of Feistel-PG ciphers are suggested to de-signers. We also evaluate the security of suggested ciphers against various byte-oriented attacks, including differential cryptanalysis, linear cryptanalysis, impossible differential attack and integral attack. Some permutations with opti-mum diffusion but relatively weaker security are filtered out and these permutations should be avoided by design-ers. 相似文献
6.
Parallel Collision Search with Cryptanalytic Applications 总被引:16,自引:0,他引:16
A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is
presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions.
General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding
meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double
encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known
to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic
curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple
encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines
which could be built with current technology: one finds elliptic curve logarithms in GF(2155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected
time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders
of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers
only 17 more bits of security than single-DES.
Received 21 December 1995 and revised 24 September 1996 相似文献
7.
We introduce the black-box model for cryptographic primitives. In this model cryptographic primitives are given by a computation graph, where the computation
boxes sitting on the vertices of the graph act as random oracles. We formalize and study a family of generic attacks which
generalize exhaustive search and the birthday paradox. We establish complexity lower bounds for these attacks and we apply
it to compression functions based on the FFT network.
Received 25 October 1995 and revised 15 September 1997 相似文献
8.
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. 相似文献
9.
An almost k -wise independent sample space is a small subset of m bit sequences in which any k bits are ``almost independent'. We show that this idea has close relationships with useful cryptologic notions such as
multiple authentication codes (multiple A -codes), almost strongly universal hash families, almost k -resilient functions, almost correlation-immune functions, indistinguishable random variables and k -wise decorrelation bias of block ciphers.
We use almost k -wise independent sample spaces to construct new efficient multiple A -codes such that the number of key bits grows linearly as a function of k (where k is the number of messages to be authenticated with a single key). This improves on the construction of Atici and Stinson
\cite{AS96}, in which the number of key bits is Ω (k
2
) .
We introduce the concepts of ɛ -almost k -resilient functions and almost correlation-immune functions, and give a construction for almost k -resilient functions that has parameters superior to k -resilient functions. We also point out the connection between almost k -wise independent sample spaces and pseudorandom functions that can be distinguished from truly random functions, by a distinguisher
limited to k oracle queries, with only a small probability. Vaudenay \cite{Vaudenay99} has shown that such functions can be used to construct
block ciphers with a small decorrelation bias.
Finally, new bounds (necessary conditions) are derived for almost k -wise independent sample spaces, multiple A -codes and balanced ɛ -almost k -resilient functions.
Received September 1999 and revised January 2001 Online publication 29 August 2001 相似文献
10.
11.
Attacks on Fast Double Block Length Hash Functions 总被引:5,自引:0,他引:5
The security of hash functions based on a block cipher with a block length of m bits and a key length of k bits, where , is considered. New attacks are presented on a large class of iterated hash functions with a 2m -bit hash result which processes in each iteration two message blocks using two encryptions. In particular, the attacks break
three proposed schemes: Parallel-DM, the PBGV hash function, and the LOKI DBH mode.
Received 1 March 1996 and revised 16 December 1996 相似文献
12.
线性密码分析已成为分组密码最主要的密码分析方法之一.基于此,本文深入研究了一类非平衡Feistel网络的线性可证明安全性.设LP为该非平衡Feistel网络的轮函数F的线性偏差的最大值,本文从非平衡Feistel网络的线性偏差的结构形式入手,在轮子密钥是相互独立且均匀分布的假设下,证明了当轮数不少于m轮时,该非平衡Feistel网络的线性偏差关于密钥的平方均值的上界为LP的平方;当轮数不少于2m轮时,证明了该非平衡Feistel网络的线性偏差关于密钥的平方均值的上界为LP四次方的2倍. 相似文献
13.
The Data Encryption Standard (DES) defines an indexed set of permutations acting on the message space ={0,1}64. If this set of permutations were closed under functional composition, then the two most popular proposals for strengthening DES through multiple encryption would be equivalent to single encryption. Moreover, DES would be vulnerable to a known-plaintext attack that runs in 228 steps on the average. It is unknown in the open literature whether or not DES has this weakness.Two statistical tests are presented for determining if an indexed set of permutations acting on a finite message space forms a group under functional composition. The first test is a meet-in-the-middle algorithm which uses O(K) time and space, where K is the size of the key space. The second test, a novel cycling algorithm, uses the same amount of time but only a small constant amount of space. Each test yields a known-plaintext attack against any finite, deterministic cryptosystem that generates a small group.The cycling closure test takes a pseudorandom walk in the message space until a cycle is detected. For each step of the pseudorandom walk, the previous ciphertext is encrypted under a key chosen by a pseudorandom function of the previous ciphertext. Results of the test are asymmetrical: long cycles are overwhelming evidence that the set of permutations is not a group; short cycles are strong evidence that the set of permutations has a structure different from that expected from a set of randomly chosen permutations.Using a combination of software and special-purpose hardware, the cycling closure test was applied to DES. Experiments show, with overwhelming confidence, that DES is not a group. Additional tests confirm that DES is free of certain other gross algebraic weaknesses. But one experiment discovered fixed points of the so-called weak-key transformations, thereby revealing a previously unpublished additional weakness of the weak keys.Support for this research was provided in part by the National Science Foundation under contract number MCS-8006938 and by the International Business Machines Corporation. 相似文献
14.
Decorrelation: A Theory for Block Cipher Security 总被引:2,自引:0,他引:2
Pseudorandomness is a classical model for the security of block ciphers.
In this paper we propose convenient tools in order to study it in connection
with the Shannon Theory, the Carter–Wegman universal hash functions paradigm,
and the Luby–Rackoff approach.
This enables the construction of new ciphers with security proofs under
specific models.
We show how to ensure security against basic differential and linear
cryptanalysis and even more general attacks.
We propose practical construction schemes. 相似文献
15.
Provable security against a differential attack 总被引:4,自引:0,他引:4
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 23–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. 相似文献
16.
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). 相似文献
17.
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, 226 data, 230 bytes of memory, and 232 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. 相似文献
18.
Lindell 《Journal of Cryptology》2008,16(3):143-184
In this paper we show that any two-party functionality can be securely computed in a constant number of rounds , where security is obtained against (polynomial-time) malicious adversaries that may arbitrarily deviate from the protocol
specification. This is in contrast to Yao's constant-round protocol that ensures security only in the face of semi-honest
adversaries, and to its malicious adversary version that requires a polynomial number of rounds.
In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in
parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain
a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present
a constant-round almost perfect coin-tossing protocol, where by ``almost perfect' we mean that the resulting coins are guaranteed to be statistically close
to uniform (and not just pseudorandom). 相似文献
19.
Fast correlation attacks on certain stream ciphers 总被引:13,自引:0,他引:13
Suppose that the output of a running key generator employed in a stream cipher is correlated to a linear feedback shift register sequence (LFSR sequence) a with correlation probabilityp>0.5. Then two new correlation attacks (Algorithms A and B) are presented to determine the initial digits of a, provided that the numbert of feedback taps is small (t<10 ifp0.75). The computational complexity of Algorithm A is of orderO(2ck), wherek denotes the length of the LFSR andc<1 depends on the input parameters of the attack, and Algorithm B is polynomial (in fact, even linear) in the lengthk of the LFSR. These algorithms are much faster than an exhaustive search over all phases of the LFSR, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000). On the other hand, for correlation probabilitiesp0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk100 andt10).This work was supported in part by GRETAG Ltd., Regensdorf, Switzerland. 相似文献
20.
For the published block cipher algorithm, two kinds of round functions have been researched. Block ciphers in network environments are taking more risks than ever before because of their initialization key's distribution in the internet. The security of block cipher algorithm is affected by linear bias and nonlinear bias which are restricted by confusion layer and diffusion layer. This article takes an approach on how block cipher's two round structures are initially transformed when they fuse into LFSR. The SP structure can be considered two F functions in one Feistel round function which combines both right and left of origin data transformation. Furthermore, the round number linear function and nonlinear function of Feistel and SP structure are compared. The merit of SP structure is that it can fuse in LFSR as a nonlinear filter without memory. 相似文献