All papers (Page 184 of 21762 results)

Last updated:  2009-08-10
A Registration Scheme to Allocate a Unique Identification Number
Uncategorized
Manoj Kumar
Show abstract
Uncategorized
Identification is always a necessity of human life. Currently, our government has decided to allocate a unique identity to every Indian. This paper proposed a registration scheme, in which a controlling agency can generate a unique identification number in such a way that registration number cannot be forged and misused. In the proposed scheme, only the number holder can use his number and he/she can prove its validity to any third party, whenever necessary.
Last updated:  2009-09-03
Linearization Framework for Collision Attacks: Application to CubeHash and MD6
Uncategorized
Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin
Show abstract
Uncategorized
In this paper, an improved differential cryptanalysis framework for finding collisions in hash functions is provided. Its principle is based on linearization of compression functions in order to find low weight differential characteristics as initiated by Chabaud and Joux. This is formalized and refined however in several ways: for the problem of finding a conforming message pair whose differential trail follows a linear trail, a condition function is introduced so that finding a collision is equivalent to finding a preimage of the zero vector under the condition function. Then, the dependency table concept shows how much influence every input bit of the condition function has on each output bit. Careful analysis of the dependency table reveals degrees of freedom that can be exploited in accelerated preimage reconstruction under the condition function. These concepts are applied to an in-depth collision analysis of reduced-round versions of the two SHA-3 candidates CubeHash and MD6, and are demonstrated to give by far the best currently known collision attacks on these SHA-3 candidates.
Last updated:  2021-02-07
A short Note on Discrete Log Problem in $\mathbbF_p$
Habeeb Syed
Consider finite prime fields $\mathbb{F}_p$ for which $2$ is primitive element. In this short we propose a new algorithm to compute discrete log in such finite fields. Our algorithm is based on elementary properties of finite fields and is purely theoretical in nature. Further, complexity of the algorithm is exponential in nature and as such it is not being suggested for any computational purposes.
Last updated:  2009-08-03
Untraceable Tags based on Mild Assumptions
Carlo Blundo, Angelo De Caro, Giuseppe Persiano
Radio frequency identification (RFID) chips have been widely deployed in large-scale systems such as inventory control and supply chain management. While RFID technology has much advantage, however it may create new problems to privacy. Tag untraceability is a significant concern that needs to be addressed in deploying RFID-based system. In this paper we propose a new construction for untraceable tags. Our construction is the first construction in the symmetric bilinear setting based on a mild assumption. That is our assumption is tautological in the generic group model and is ``efficiently falsifiable'' in the sense that its problem instances are stated non-interactively and concisely (i.e., independently of the number of adversarial queries and other large quantities).
Last updated:  2014-07-01
Protecting Circuits from Computationally Bounded and Noisy Leakage
Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, Vinod Vaikuntanathan
Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage. Our construction requires a small, stateless and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component. Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component), and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited in the amount of output bits per iteration and the ability to decode certain linear encodings. While our results apply in general to such leakage classes, in particular, we obtain security against: - Constant-depth circuits leakage, where the leakage function is computed by an AC^0 circuit (composed of NOT gates and unbounded fan-in AND and OR gates). - Noisy leakage, where the leakage function reveals all the bits of the internal state of the circuit, perturbed by independent binomial noise. Namely, for some number p \in (0,1/2], each bit of the computation is flipped with probability p, and remains unchanged with probability 1-p.
Last updated:  2009-08-03
Detectable correlations in Edon-R
Peter Novotney, Niels Ferguson
The Edon-R compression function has a large set of useful differentials that produce easily detectable output bit biases. We show how to construct such differentials, and use them to create a distinguisher for Edon-R-512 that requires around $2^{54}$ compression function evaluations (or $2^{28}$ evaluations after a pre-computation of $2^{66}$ evaluations). The differentials can also be used to attack a variety of MAC and KDF constructions when they use Edon-R-512.
Last updated:  2009-08-19
Chosen-Ciphertext Secure RSA-type Cryptosystems
Uncategorized
Benoit Chevallier-Mames, Marc Joye
Show abstract
Uncategorized
This paper explains how to design fully secure RSA-type cryptosystems from schemes only secure against passive attacks, in the standard model. We rely on instance-independence assumptions, which, roughly speaking, conjecture that for certain problems, an interactive access to a solver for another problem does not help the challenger. Previously, instance-independence assumptions were used in a "negative" way, to prove that certain schemes proven in the random oracle model were not provable in the standard model. Our paradigm applies virtually to all (weakly secure) RSA-type encryption schemes for which public-key RSA exponent can be arbitrarily chosen. As an illustration, we present a chosen-ciphertext secure variant of the Naccache-Stern encryption scheme.
Last updated:  2009-08-03
Cryptanalysis of the Tillich-Zémor hash function
Markus Grassl, Ivana Ilic, Spyros Magliveras, Rainer Steinwandt
At CRYPTO ’94, Tillich and Zémor proposed a family of hash functions, based on computing a suitable matrix product in groups of the form SL_2(F_{2^n}).We show how to construct collisions between palindromic bit strings of length 2n + 2 for Tillich and Zémor’s construction. The approach also yields collisions for related proposals by Petit et al. from ICECS ’08 and CT-RSA ’09. It seems fair to consider our attack as practical: for parameters of interest, the colliding bit strings have a length of a few hundred bits and can be found on a standard PC within seconds.
Last updated:  2009-08-03
Forgotten Secret Recovering Scheme and Fuzzy Vault Scheme Constructed Based on Systematic Error-Correcting Codes
Masao KASAHARA
In this paper, we revisit the Forgotten Secret Recovering Scheme for $k$ users, referred to as FSRS($k$) previously proposed by the present author. FSRS($k$) takes advantage of the fact that Reed-Solomon code used in FSRS($k$) is constructed in a form of systematic code. We show that a particular class of FSRS($k$), FSRS($1$), can be successfully applied to the various cryptoscheme including Fuzzy Vault Scheme (FVS).
Last updated:  2009-08-19
Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds
Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, Adi Shamir
AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the $2^{128}$ complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require $2^{176}$ and $2^{119}$ time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems. In this paper we describe several attacks which can break {\it with practical complexity} variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and $2^{39}$ time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and $2^{120}$ time). Another attack can break a 10 round version of AES-256 in $2^{45}$ time, but it uses a stronger type of {\it related subkey attack} (the best previous attack on this variant required 64 related keys and $2^{172}$ time). While neither AES-128 nor AES-256 can be directly broken by these attacks, the fact that their hybrid (which combines the smaller number of rounds from AES-128 along with the larger key size from AES-256) can be broken with such a low complexity raises serious concern about the remaining safety margin offered by the AES family of cryptosystems.
Last updated:  2010-03-05
Utility Dependence in Correct and Fair Rational Secret Sharing
Gilad Asharov, Yehuda Lindell
The problem of carrying out cryptographic computations when the participating parties are \emph{rational} in a game-theoretic sense has recently gained much attention. One problem that has been studied considerably is that of rational secret sharing. In this setting, the aim is to construct a mechanism (protocol) so that parties behaving rationally have incentive to cooperate and provide their shares in the reconstruction phase, even if each party prefers to be the only one to learn the secret. Although this question was only recently asked by Halpern and Teague (STOC 2004), a number of works with beautiful ideas have been presented to solve this problem. However, they all have the property that the protocols constructed need to know the actual utility values of the parties (or at least a bound on them). This assumption is very problematic because the utilities of parties are not public knowledge. We ask whether this \emph{dependence on the actual utility values} is really necessary and prove that in the case of two parties, rational secret sharing cannot be achieved without it. On the positive side, we show that in the multiparty case it is possible to construct a single mechanism that works for all (polynomial) utility functions. Our protocol has an expected number of rounds that is constant, and is optimally resilient to coalitions. In addition to the above, we observe that the known protocols for rational secret sharing that do not assume simultaneous channels all suffer from the problem that one of the parties can cause the others to output an incorrect value. (This problem arises when a party gains higher utility by having another output an incorrect value than by learning the secret itself; we argue that such a scenario needs to be considered.) We show that this problem is inherent in the non-simultaneous channels model, unless the actual values of the parties' utilities from this attack is known, in which case it is possible to prevent this from happening.
Last updated:  2009-07-31
More on Key Wrapping
Rosario Gennaro, Shai Halevi
We address the practice of key-wrapping, where one symmetric cryptographic key is used to encrypt another. This practice is used extensively in key-management architectures, often to create an ``adapter layer'' between incompatible legacy systems. Although in principle any secure encryption scheme can be used for key wrapping, practical constraints (which are commonplace when dealing with legacy systems) may severely limit the possible implementations, sometimes to the point of ruling out any ``secure general-purpose encryption.'' It is therefore desirable to identify the security requirements that are ``really needed'' for the key-wrapping application, and have a large variety of implementations that satisfy these requirements. This approach was developed in a work by Rogaway and Shrimpton at EUROCRYPT 2006. They focused on allowing deterministic encryption, and defined a notion of deterministic authenticated encryption (DAE), which roughly formalizes ``the strongest security that one can get without randomness.'' Although DAE is weaker than full blown authenticated encryption, it seems to suffice for the case of key wrapping (since keys are random and therefore the encryption itself can be deterministic). Rogaway and Shrimpton also described a mode of operation for block ciphers (called SIV) that realizes this notion. We continue in the direction initiated by Rogaway and Shirmpton. We first observe that the notion of DAE still rules out many practical and ``seemingly secure'' implementations. We thus look for even weaker notions of security that may still suffice. Specifically we consider notions that mirror the usual security requirements for symmetric encryption, except that the inputs to be encrypted are random rather than adversarially chosen. These notions are all strictly weaker than DAE, yet we argue that they suffice for most applications of key wrapping. As for implementations, we begin by observing that many standard encryption modes satisfy the key-warpping notion that mirrors CPA-security, even when used with a fixed IV (with the notable exception of CTR mode). To achieve the notion that mirrors authenticated encryption, we investigate a template of Hash-then-Encrypt (HtE), which seems practically appealing: In this method the key is first ``hashed'' into a short nonce, and then the nonce and key are encrypted using some standard encryption mode. We consider a wide array of ``hash functions'', ranging from a simple XOR to collision-resistant hashing, and examine what ``hash function'' can be used with what encryption mode.
Last updated:  2009-07-31
Attribute-Sets: A Practically Motivated Enhancement to Attribute-Based Encryption
Rakesh Bobba, Himanshu Khurana, Manoj Prabhakaran
In distributed systems users need to share sensitive objects with others based on the recipients’ ability to satisfy a policy. Attribute-Based Encryption (ABE) is a new paradigm where such policies are specified and cryptographically enforced in the encryption algorithm itself. Ciphertext-Policy ABE (CP-ABE) is a form of ABE where policies are associated with encrypted data and attributes are associated with keys. In this work we focus on improving the flexibility of representing user attributes in keys. Specifically, we propose Ciphertext Policy Attribute Set Based Encryption (CP-ASBE) - a new form of CP-ABE - which, unlike existing CP-ABE schemes that represent user attributes as a monolithic set in keys, organizes user attributes into a recursive set based structure and allows users to impose dynamic constraints on how those attributes may be combined to satisfy a policy. We show that the proposed scheme is more versatile and supports many practical scenarios more naturally and efficiently. We provide a prototype implementation of our scheme and evaluate its performance overhead.
Last updated:  2009-07-31
A study of pairing computation for elliptic curves with embedding degree 15
Nadia El Mrabet, Nicolas Guillermin, Sorina Ionica
This paper presents the first study of pairing computation on curves with embedding degree $15$. We compute the Ate and the twisted Ate pairing for a family of curves with parameter $\rho~1.5$ and embedding degree $15$. We use a twist of degree 3 to perform most of the operations in $\F_p$ or $\F_{p^5}$. Furthermore, we present a new arithmetic for extension fields of degree $5$. Our computations show that these curves give very efficient implementations for pairing-based cryptography at high security levels.
Last updated:  2013-03-04
Quantum readout of Physical Unclonable Functions: Remote authentication without trusted readers and authenticated Quantum Key Exchange without initial shared secrets
Uncategorized
Boris Skoric
Show abstract
Uncategorized
Physical Unclonable Functions (PUFs) are physical structures that are hard to clone and have a unique challenge-response behaviour. The term PUF was coined by Pappu et al. in 2001. That work triggered a lot of interest, and since then a substantial number of papers has been written about the use of a wide variety of physical structures for different security purposes such as identification, authentication, read-proof key storage, key distribution, tamper evidence, anti-counterfeiting, software-to-hardware binding and trusted computing. In this paper we propose a new security primitive: the quantum-readout PUF (QR-PUF). This is a classical PUF which is challenged using a quantum state, e.g. a single-photon state, and whose response is also a quantum state. By the no-cloning property of unknown quantum states, attackers cannot intercept challenges or responses without noticeably disturbing the readout process. Thus, a verifier who sends quantum states as challenges and receives the correct quantum states back can be certain that he is probing a specific QR-PUF without disturbances, even in the QR-PUF is far away `in the field' and under hostile control. For PUFs whose information content is not exceedingly large, all currently known PUF-based authentication and anti-counterfeiting schemes require trusted readout devices in the field. Our quantum readout scheme has no such requirement. Furthermore, we show how the QR-PUF authentication scheme can be interwoven with Quantum Key Exchange (QKE), leading to an authenticated QKE protocol between two parties. This protocol has the special property that it requires no a priori secret, or entangled state, shared by the two parties.
Last updated:  2009-07-30
A Simulation-Based Treatment of Authenticated Message Exchange
Klaas Ole Kuertz, Henning Schnoor, Thomas Wilke
Simulation-based security notions for cryptographic protocols are regarded as highly desirable, primarily because they admit strong composability and, consequently, a modular design. In this paper, we give a simulation-based security definition for two-round authenticated message exchange and show that a concrete protocol, 2AMEX-1, satisfies our security property, that is, we provide an ideal functionality for two-round authenticated message exchange and show that 2AMEX-1 realizes it securely. To model the involved public-key infrastructure adequately, we use a joint-state approach.
Last updated:  2010-01-25
Non-delegatable Identity-based Designated Verifier Signature
Uncategorized
Qiong Huang, Willy Susilo, Duncan S. Wong
Show abstract
Uncategorized
Designated verifier signature is a cryptographic primitive which allows a signer to convince a designated verifier of the validity of a statement but in the meanwhile prevents the verifier from transferring this conviction to any third party. In this work we present the \emph{first} identity-based designated verifier signature scheme that supports non-delegatability, and prove its security in the random oracle model, based on computational Diffie-Hellman assumption. Our scheme is perfectly non-transferable, and its non-delegatability follows the original definition proposed by Lipmaa et al. \cite{LipmaaWaBa05}.
Last updated:  2009-07-28
Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer
Yehuda Lindell, Hila Zarosim
In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this paper, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems: 1) Adaptive zero-knowledge proofs: We ask whether it is possible to construct adaptive zero-knowledge proofs (with unconditional soundness). Beaver (STOC 1996) showed that known zero-knowledge proofs are not adaptively secure, and in addition showed how to construct zero-knowledge arguments (with computational soundness). 2) Adaptively secure oblivious transfer: All known protocols for adaptively secure oblivious transfer rely on seemingly stronger hardness assumptions than for the case of static adversaries. We ask whether this is inherent, and in particular, whether it is possible to construct adaptively secure oblivious transfer from enhanced trapdoor permutations alone. We provide surprising answers to the above questions, showing that achieving adaptive security is sometimes harder than achieving static security, and sometimes not. First, we show that assuming the existence of one-way functions only, there exist adaptive zero-knowledge proofs for all languages in NP. In order to prove this, we overcome the problem that all adaptive zero-knowledge protocols known until now used equivocal commitments (which would enable an all-powerful prover to cheat). Second, we prove a black-box separation between adaptively secure oblivious transfer and enhanced trapdoor permutations. As a corollary, we derive a black-box separation between adaptively and statically securely oblivious transfer. This is the first black-box separation to relate to adaptive security and thus the first evidence that it is indeed harder to achieve security in the presence of adaptive adversaries than in the presence of static adversaries.
Last updated:  2009-07-27
Space Efficient Secret Sharing: A Recursive Approach
Uncategorized
Abhishek Parakh, Subhash Kak
Show abstract
Uncategorized
This paper presents a k-threshold secret sharing technique that distributes a secret S into shares of size |S|/(k-1), where |S| denotes the secret size. This bound is close to the optimal bound of |S|/k, if the secret is to be recovered from k shares. The proposed scheme makes use of repeated polynomial interpolation. Our technique has potential applications in secure and reliable storage of information on the Web and in sensor networks.
Last updated:  2009-07-27
Position Based Cryptography
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
We consider what constitutes {\em identities\/} in cryptography. Typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your address, or your (non-revoked) public-key coming from some trusted public-key infrastructure. In many situations, however, {\bf where you are} defines your identity. For example, we know the role of a bank-teller behind a bullet-proof bank window not because she shows us her credentials but by merely knowing her location. In this paper, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party are derived from its \emph{geographic location}. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve. In light of the above impossibility result, we then turn to the Bounded Retrieval Model (a variant of the Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: \begin{itemize} \item Secure Positioning; and \item Position Based Key Exchange. \end{itemize} We then show that these tasks are in fact {\em universal\/} in this setting -- we show how we can use them to realize Secure Multi-Party Computation. Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results by showing that the bounded-retrieval framework is, in fact, one of the ``right" frameworks (there may be others) to study the foundations of position-based cryptography.
Last updated:  2010-11-10
Some Lattices Attacks on DSA and ECDSA
Uncategorized
Dimitrios Poulakis
Show abstract
Uncategorized
In this paper, using the LLL reduction method and computing the integral points of two classes of conics, we develop attacks on DSA and ECDSA in case where the secret and the ephemeral key and their modular inverse are quite small or quite large.
Last updated:  2009-07-24
Toward a Generic Construction of Convertible Undeniable Signatures from Pairing-Based Signatures
Laila El Aimani
Undeniable signatures were proposed to limit the verification property of ordinary digital signatures. In fact, the verification of such signatures cannot be attained without the help of the signer, via the confirmation/denial protocols. Later, the concept was refined to give the possibility of converting a \emph{selected} signature into an ordinary one, or publishing a \emph{universal} receipt that turns all undeniable signatures publicly verifiable. In this paper, we present the first generic construction for convertible undeniable signatures from certain weakly secure cryptosystems and any secure digital signature scheme. Next, we give two specific approaches for building convertible undeniable signatures from a large class of pairing-based signatures. These methods find a nice and practical instantiation with known encryption and signature schemes. For instance, we achieve the most efficient undeniable signatures with regard to the signature length and cost, the underlying assumption and the security model. We believe these constructions could be an interesting starting point to develop more efficient schemes or give better security analyses of the existing ones.
Last updated:  2009-07-22
On the Security of a Proxy Blind Signature Scheme over Braid Groups
Manoj Kumar
A proxy blind signature scheme is the combination of proxy signature and blind signature scheme. In 2009,Verma proposed a proxy blind signature scheme over braid groups. Verma claimed that the proposed scheme is secure against all possible security lapses and also satisfy all essential security attributes.This paper analyzes Verma’s proposed scheme and found that this scheme suffers with the serious security vulnerabilities. This paper show that the proposed scheme does not satisfy unforgeability and unlinkability, which are two essential security requirement of a secure proxy blind signature scheme.
Last updated:  2012-06-20
Cryptanalysis of a Generalized Unbalanced Feistel Network Structure
Ruilin Li, Bing Sun, Chao Li, Longjiang Qu
This paper reevaluates the security of GF-NLFSR, a new kind of generalized unbalanced Feistel network structure that was proposed at ACISP 2009. We show that GF-NLFSR itself reveals a very slow diffusion rate, which could lead to several distinguishing attacks. For GF-NLFSR containing $n$ sub-blocks, we find an $n^2$-round integral distinguisher by algebraic methods and further use this integral to construct an $(n^2+n-2)$-round impossible differential distinguisher. Compared with the original $(3n-1)$-round integral and $(2n-1)$-round impossible differential, ours are significantly better. Another contribution of this paper is to introduce a kind of non-surjective attack by analyzing a variant structure of GF-NLFSR, whose provable security against differential and linear cryptanalysis can also be provided. The advantage of the proposed non-surjective attack is that traditional non-surjective attack is only applicable to Feistel ciphers with non-surjective (non-uniform) round functions, while ours could be applied to block ciphers with bijective ones. Moreover, its data complexity is $\mathcal{O}(l)$ with $l$ the block length.
Last updated:  2010-12-02
Bonsai Trees (or, Arboriculture in Lattice-Based Cryptography)
Chris Peikert
We introduce *bonsai trees*, a lattice-based cryptographic primitive that we apply to resolve some important open problems in the area. Applications of bonsai trees include: 1. An efficient, stateless `hash-and-sign' signature scheme in the *standard model* (i.e., no random oracles), and 2. The first *hierarchical* identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.
Last updated:  2015-09-08
MAC Precomputation with Applications to Secure Memory
Juan A. Garay, Vladimir Kolesnikov, Rae McLellan
We present ShMAC (Shallow MAC), a fixed input length message authentication code that performs most of the computation prior to the availability of the message. Specifically, ShMAC's message-dependent computation is much faster and smaller in hardware than the evaluation of a pseudorandom permutation (PRP), and can be implemented by a small shallow circuit, while its precomputation consists of one PRP evaluation. A main building block for ShMAC is the notion of strong differential uniformity (SDU), which we introduce, and which may be of independent interest. We present an efficient SDU construction built from previously considered differentially uniform functions. Our motivating application is a system architecture where a hardware-secured processor uses memory controlled by an adversary. We present in technical detail a novel, more efficient approach to encrypting and authenticating memory and discuss the associated trade-offs, while paying special attention to minimizing hardware costs and the reduction of DRAM latency.
Last updated:  2009-07-22
Impossible Differential Cryptanalysis of FOX
Zhongming Wu, Xuejia Lai, Bo Zhu, Yiyuan Luo
Block ciphers are the very foundation of computer and information security. FOX, also known as IDEA NXT, is a family of block ciphers published in 2004 and is famous for its provable security to cryptanalysis. In this paper, we apply impossible differential cryptanalysis on FOX cipher. We find a 4-round impossible difference, by using which adversaries can attack 5, 6 and 7-round FOX64 with $2^{71}$, $2^{135}$ and $2^{199}$ one-round encryptions respectively. Compared to the previous best attack with $2^{109.4}$, $2^{173.4}$ and $2^{237.4}$ full-round encryptions to 5, 6 and 7-round FOX64, the method in this paper is the best attack to FOX cipher. This attack can also be applied to 5-round FOX128 with $2^{135}$ one-round encryptions.
Last updated:  2009-07-21
A Domain Extender for the Ideal Cipher
Uncategorized
Jean-Sebastien Coron, Yevgeniy Dodis, Avradip Mandal, Yannick Seurin
Show abstract
Uncategorized
We describe the first domain extender for ideal ciphers, {\sl i.e.} we show a construction that is indifferentiable from a $2n$-bit ideal cipher, given a $n$-bit ideal cipher. Our construction is based on a $3$-round Feistel, and is more efficient than first building a $n$-bit random oracle from a $n$-bit ideal cipher and then a $2n$-bit ideal cipher from a $n$-bit random oracle (using a $6$-round Feistel). We also show that $2$ rounds are not enough for indifferentiability by exhibiting a simple attack. We also consider our construction in the standard model: we show that $2$ rounds are enough to get a $2n$-bit tweakable block-cipher from a $n$-bit tweakable block-cipher and we show that with $3$ rounds we can get beyond the birthday security bound.
Last updated:  2010-07-23
Asynchronous Distributed Private-Key Generators for Identity-Based Cryptography
Aniket Kate, Ian Goldberg
An identity-based encryption (IBE) scheme can greatly reduce the complexity of sending encrypted messages over the Internet. However, an IBE scheme necessarily requires a private-key generator (PKG), which can create private keys for clients, and so can passively eavesdrop on all encrypted communications. Although a distributed PKG has been suggested as a way to mitigate this problem for Boneh and Franklin's IBE scheme, the security of this distributed protocol has not been proven and the proposed solution does not work over the asynchronous Internet. Further, a distributed PKG has not been considered for any other IBE scheme. In this paper, we design distributed PKG setup and private key extraction protocols in an asynchronous communication model for three important IBE schemes; namely, Boneh and Franklin's IBE, Sakai and Kasahara's IBE, and Boneh and Boyen's BB1-IBE. We give special attention to the applicability of our protocols to all possible types of bilinear pairings and prove their IND-ID-CCA security in the random oracle model. Finally, we also perform a comparative analysis of these protocols and present recommendations for their use.
Last updated:  2009-09-14
Cache Timing Attacks on Camellia Block Cipher
Uncategorized
ZHAO Xin-jie, WANG Tao, ZHENG Yuan-yuan
Show abstract
Uncategorized
Camellia, as the final winner of 128-bit block cipher in NESSIE, is the most secure block cipher of the world. In 2003, Tsunoo proposed a Cache Attack using a timing of CPU cache, successfully recovered Camellia-128 key within 228 plaintexts and 35 minutes. In 2004, IKEDA YOSHITAKA made some further improvements on Tsunoo’s attacks, recovered Camellia-128 key within 221.4 plaintexts and 22 minutes. All of their attacks are belonged to timing driven Cache attacks, our research shows that, due to its frequent S-box lookup operations, Camellia is also quite vulnerable to access driven Cache timing attacks, and it is much more effective than timing driven Cache attacks. Firstly, we provide a general analysis model for symmetric ciphers using S-box based on access driven Cache timing attacks, point out that the F function of the Camellia can leak information about the result of encryption key XORed with expand-key, and the left circular rotating operation of the key schedule in Camellia has serious designing problem. Next, we present several attacks on Camellia-128/192/256 with and without FL/FL-1. Experiment results demonstrate: 500 random plaintexts are enough to recover full Camellia-128 key; 900 random plaintexts are enough to recover full Camellia-192/256 key; also, our attacks can be expanded to known ciphertext conditions by attacking the Camellia decryption procedure; besides, our attacks are quite easy to be expanded to remote scenarios, 3000 random plaintexts are enough to recover full encryption key of Camellia-128/192/256 in both local and campus networks. Finally, we discuss the reason why Camellia is weak in this type of attack, and provide some advices to cipher designers for hardening ciphers against cache timing attacks.
Last updated:  2009-07-21
Comparing SessionStateReveal and EphemeralKeyReveal for Diffie-Hellman protocols (extended version)
Berkant Ustaoglu
Both the ``eCK'' model, by LaMacchia, Lauter and Mityagin, and the ``CK01'' model, by Canetti and Krawczyk, address the effect of leaking session specific ephemeral data on the security of key establishment schemes. The CK01-adversary is given a \SessionStateReveal{} query to learn session specific private data defined by the protocol specification, whereas the eCK-adversary is equipped with an \RevealEphemeralKey{} query to access all ephemeral private input required to carry session computations. \SessionStateReveal{} \emph{cannot} be issued against the test session; by contrast \RevealEphemeralKey{} \emph{can} be used against the test session under certain conditions. On the other hand, it is not obvious how \RevealEphemeralKey{} compares to \SessionStateReveal{}. Thus it is natural to ask which model is more useful and practically relevant. While formally the models are not comparable, we show that recent analysis utilizing \SessionStateReveal{} and \RevealEphemeralKey{} have a similar approach to ephemeral data leakage. First we pinpoint the features that determine the approach. Then by examining common motives for ephemeral data leakage we conclude that the approach is meaningful, but does not take into account timing, which turns out to be critical for security. Lastly, for Diffie-Hellman protocols we argue that it is important to consider security when discrete logarithm values of the outgoing ephemeral public keys are leaked and offer a method to achieve security even if the values are exposed.
Last updated:  2009-07-21
On the Duality of Probing and Fault Attacks
Berndt M. Gammel, Stefan Mangard
In this work we investigate the problem of simultaneous privacy and integrity protection in cryptographic circuits. We consider a white-box scenario with a powerful, yet limited attacker. A concise metric for the level of probing and fault security is introduced, which is directly related to the capabilities of a realistic attacker. In order to investigate the interrelation of probing and fault security we introduce a common mathematical framework based on the formalism of information and coding theory. The framework unifies the known linear masking schemes. We proof a central theorem about the properties of linear codes which leads to optimal secret sharing schemes. These schemes provide the lower bound for the number of masks needed to counteract an attacker with a given strength. The new formalism reveals an intriguing duality principle between the problems of probing and fault security, and provides a unified view on privacy and integrity protection using error detecting codes. Finally, we introduce a new class of linear tamper-resistant codes. These are eligible to preserve security against an attacker mounting simultaneous probing and fault attacks.
Last updated:  2009-07-24
How to Delegate a Lattice Basis
David Cash, Dennis Hofheinz, Eike Kiltz
We present a technique, which we call basis delegation, that allows one to use a short basis of a given lattice to derive a new short basis of a related lattice in a secure way. And since short bases for lattices essentially function like cryptographic trapdoors, basis delegation turns out to be a very powerful primitive. As the main application of our technique, we show how to construct hierarchical identity-based encryption (HIBE) that is secure, without random oracles, under the assumption that certain standard lattice problems are hard in the worst case. This construction and its variants constitute the first HIBE schemes from lattices, as well as the first lattice-based constructions of stateless signatures and identity-based encryption without random oracles.
Last updated:  2009-07-21
Game Theoretic Resistance to Denial of Service Attacks Using Hidden Difficulty Puzzles
Harikrishna Narasimhan, Venkatanathan Varadarajan, C. Pandu Rangan
Denial of Service (DoS) vulnerabilities are one of the major concerns in today’s Internet. Client-puzzles offer a good mechanism to defend servers against DoS attacks. In this paper, we introduce the notion of hidden puzzle difficulty, where the attacker cannot determine the difficulty of the puzzle without expending a minimal amount of computational resource. Game theory is used to develop defense mechanisms, which make use of such puzzles. New puzzles that satisfy the requirements of the defense mechanisms have been proposed. We also show that our defense mechanisms are more effective than the ones proposed in the earlier work by Fallah.
Last updated:  2009-07-18
Compact Hardware Implementations of the SHA-3 Candidates ARIRANG, BLAKE, Grøstl, and Skein
Stefan Tillich, Martin Feldhofer, Wolfgang Issovits, Thomas Kern, Hermann Kureck, Michael Mühlberghuber, Georg Neubauer, Andreas Reiter, Armin Köfler, Mathias Mayrhofer
The weakening of the widely used SHA-1 hash function has also cast doubts on the strength of the related algorithms of the SHA-2 family. The US NIST has therefore initiated the SHA-3 competition in order to select a modern hash function algorithm as a ``backup'' for SHA-2. This algorithm should be efficiently implementable both in software and hardware under different constraints. In this paper, we present hardware implementations of the four SHA-3 candidates ARIRANG, BLAKE, Grøstl, and Skein with the primary constraint of minimizing chip area.
Last updated:  2009-07-20
A provably secure really source hiding designated verifier signature scheme based on random oracle model
Uncategorized
Huang-Ta Huang, Jue-Sam Chou
Show abstract
Uncategorized
A lot of designated verifier signature (DVS) schemes have been proposed. However, all of them only provide the basic security requirement that only the designated verifier can check the validity of the signature. They are either not secure enough or lacking source hiding. Hence, in this article, we design a provably secure DVS scheme. It not only can attain the basic security requirement but also hide the original signer’s identity which makes our scheme more suitable for the applications in an electronic voting system.
Last updated:  2009-07-18
An Efficient Concurrent Repetition Theorem
Douglas Wikström
Håstad et al. (2008) prove, using Raz's lemma (STOC '95) thefirst efficient parallel repetition theorem for protocols with anon-constant number of rounds, for a natural generalization ofpublic-coin protocols. They show that a parallel prover thatconvinces a fraction $1-\gamma$ of the embedded verifiers of a$\reps$-wise repeated $\exchanges$-message verifier can be turnedinto a prover with error probability$1-\gamma-O(\exchanges\sqrt{-\logg{\epsilon}/\reps})$. This improvesprevious results of Impagliazzo et al. (Crypto 2007) and Pass andVenkitasubramaniam (STOC 2007) that studies the constant round case. We prove a generalization of Raz's Lemma to random processes thatallows us to improve the analysis of the reduction of Håstad etal. in the public-coin case to$1-\gamma-O(\sqrt{-\logg{\epsilon}/\reps})$, i.e., we remove thedependence on the number rounds completely, and thus the restrictionto settings where $\reps>\exchanges^2$. An important implication of the strengthened parallel repetitiontheorem is the first efficient \emph{concurrent} repetition theoremfor protocols with a non-constant number of rounds. In concurrentrepetition, the verifiers execute completely independently and onlyreport their final decision, i.e., the prover chooses arbitrarily inwhich order it interacts with the individual verifiers. This shouldbe contrasted with parallel repetition where the verifiers aresynchronized in each round.
Last updated:  2009-07-18
Security Analysis of the GF-NLFSR Structure and Four-Cell Block Cipher
Wenling Wu, Lei Zhang, Liting Zhang, Wentao Zhang
The overall structure is one of the most important properties of block ciphers. At present, the most common structures include Feistel structure, SP structure, MISTY structure, L-M structure and Generalized Feistel structure. In \cite{29}, Choy et al. proposed a new structure called GF-NLFSR (Generalized Feistel-NonLinear Feedback Shift Register), and designed a new block cipher called Four-Cell which is based on the 4-cell GF-NLFSR. In this paper, we first study properties of the $n$-cell GF-NLFSR structure, and prove that for an $n$-cell GF-NLFSR, there exists an $(n^2+n-2)$ rounds impossible differential. Then we present an impossible differential attack on the full 25-round Four-Cell using this kind of 18-round impossible differential distinguisher together with differential cryptanalysis technique. The data complexity of our attack is $2^{111.5}$ and the time complexity is less than $2^{123.5}$ encryptions. In addition, we expect the attack to be more efficient when the relations between different round subkeys can be exploited by taking the key schedule algorithm into consideration.
Last updated:  2009-07-16
Anonymous ID Based Signcryption Scheme for Multiple Receivers
Sunder Lal, Prashant Kushwah
Anonymous signcryption is synonyms of ring signcryption which provides anonymity of the sender along with the advantages of signcryption. Multi receiver signcryption is suited for situation where a sender wants to send a message to multiple receivers in the confidential and authenticated way. This paper proposes an identity based anonymous signcryption scheme in multi-receiver setting. It also provides proofs of provable security of the proposed scheme under some computationally difficult problems.
Last updated:  2009-07-16
Comments on Shao-Cao's Unidirectional Proxy Re-Encryption Scheme from PKC 2009
Xi Zhang, Min-Rong Chen, Xia Li
In Eurocrypt'98, Blaze, Bleumer and Strauss [4] introduced a primitive named proxy re-encryption (PRE), in which a semi-trusted proxy can convert - without seeing the plaintext - a ciphertext originally intended for Alice into an encryption of the same message intended for Bob. PRE systems can be categorized into bidirectional PRE, in which the proxy can transform from Alice to Bob and vice versa, and unidirectional PRE, in which the proxy cannot transforms ciphertexts in the opposite direction. How to construct a PRE scheme secure against chosen-ciphertext attack (CCA) without pairings is left as an open problem in ACM CCS'07 by Canetti and Hohenberger [7]. In CANS'08, Deng et al. [8] successfully proposed a CCA-secure bidirectional PRE scheme without pairings. In PKC'09, Shao and Cao [10] proposed a unidirectional PRE without pairings, and claimed that their scheme is CCA-secure. They compared their scheme with Libert-Vergnaud's pairing-based unidirectional PRE scheme from PKC'08, and wanted to indicate that their scheme gains advantages over Libert-Vergnaud's scheme. However, Weng et al. [13] recently pointed out that Shao-Cao's scheme is not CCA-secure by giving a concrete chosen-ciphertext attack, and they also presented a more efficient CCA-secure unidirectional PRE scheme without parings. In this paper, we further point out that, Shao-Cao's comparison between their scheme and Libert-Vergnaud's scheme is unfair, since Shao-Cao's scheme is even not secure against chosen-plaintext attack (CPA) in Libert-Vergnaud's security model.
Last updated:  2009-07-14
Partitioning Multivariate Polynomial Equations via Vertex Separators for Algebraic Cryptanalysis and Mathematical Applications
Uncategorized
Kenneth Koon-Ho Wong, Gregory V. Bard, Robert H. Lewis
Show abstract
Uncategorized
We present a novel approach for solving systems of polynomial equations via graph partitioning. The concept of a variable-sharing graph of a system of polynomial equations is defined. If such graph is disconnected, then the system of equations is actually two separate systems that can be solved individually. This can provide a significant speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting a small number of vertices on the graph, the variable-sharing graph could be disconnected in a balanced fashion, and in turn the system of polynomial equations are separated into smaller ones of similar sizes. In graph theory terms, this process is equivalent to finding balanced vertex partitions with minimum-weight vertex separators. The techniques of finding these vertex partitions are discussed, and experiments are performed to evaluate its practicality for general graphs and systems of polynomial equations. Applications of this approach to the QUAD family of stream ciphers, algebraic cryptanalysis of the stream cipher Trivium and its variants, as well as some mathematical problems in game theory and computational algebraic geometry are presented. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method, and constructive results are discussed.
Last updated:  2009-07-31
FPGA Implementations of SHA-3 Candidates:CubeHash, Grøstl, L{\sc ane}, Shabal and Spectral Hash
Uncategorized
Brian Baldwin, Andrew Byrne, Mark Hamilton, Neil Hanley, Robert P. McEvoy, Weibo Pan, William P. Marnane
Show abstract
Uncategorized
Abstract: Hash functions are widely used in, and form an important part of many cryptographic protocols. Currently, a public competition is underway to find a new hash algorithm(s) for inclusion in the NIST Secure Hash Standard (SHA-3). Computational efficiency of the algorithms in hardware will form one of the evaluation criteria. In this paper, we focus on five of these candidate algorithms, namely CubeHash, Grøstl, L{\sc ane}, Shabal and Spectral Hash. Using Xilinx Spartan-3 and Virtex-5 FPGAs, we present architectures for each of these hash functions, and explore area-speed trade-offs in each design. The efficiency of various architectures for the five hash functions is compared in terms of throughput per unit area. To the best of the authors' knowledge, this is the first such comparison of these SHA-3 candidates in the literature.
Last updated:  2010-03-13
Leakage Resilient Cryptography in Practice
Uncategorized
Francois-Xavier Standaert, Olivier Pereira, Yu Yu, Jean-Jacques Quisquater, Moti Yung, Elisabeth Oswald
Show abstract
Uncategorized
In this report, we are concerned with models to analyze the security of cryptographic algorithms against side-channel attacks. Our objectives are threefold. In a first part of the paper, we aim to survey a number of well known intuitions related to physical security and to connect them with more formal results in this area. For this purpose, we study the definition of leakage function introduced by Micali and Reyzin in 2004 and its relation to practical power consumption traces. Then, we discuss the non equivalence between the unpredictability and indistinguishability of pseudorandom generators in physically observable cryptography. Eventually, we examine the assumption of bounded leakage per iteration that has been used recently to prove the security of different constructions against side-channel attacks. We show that approximated leakage bounds can be obtained using the framework for the analysis of side-channel key recovery attacks published at Eurocrypt 2009. In a second part of the paper, we aim to investigate two recent leakage resilient pseudorandom generators, both from a theoretical and practical point of view. On the one hand, we consider a forward secure generator from ASIACCS 2008 and its similarities with a previous construction by Bellare and Yee. On the other hand, we analyze Pietrzak's block cipher based construction from Eurocrypt 2009. Doing this, we put forward the difficulty of meaningfully restricting the physical leakages and show that this difficulty leads to different drawbacks. It allows us to emphasize the differences between these two designs. First, one construction that we analyze requires strong black box assumptions (i.e. random oracles) - the other one considers unrealistic leakages leading to (possibly useless) performance overheads. Second, one construction considers an adversary able to adaptively choose a leakage function while the second one does not permit this adaptivity. Third, the security proof of the Eurocrypt 2009 construction relies on the assumption that ``only computation leaks'' (or relaxed but related hypotheses) while this assumption is not necessary for the ASIACCS construction. We then discuss the impact of these hypotheses with respect to recent technological advances. In the third part of the paper, we show that Pietrzak's leakage resilient mode of operation from Eurocrypt 2009 can be broken with a standard DPA if it is re-initialized without sharing new keys. Then, we propose solutions to fix this issue and extend the initial proposal from ASIACCS 2008 in order to rely on more standard cryptographic constructions. We use these alternative designs to illustrate the incompatibility between a fully adaptive selection of the leakage function and the secure initialization of a pseudorandom generator. We also argue that simple pseudorandom functions (e.g. the one of Goldreich, Goldwasser, Micali) can be shown leakage resilient, using the random oracle methodology. We additionally discuss the security vs. performance tradeoff that is inherent to these different schemes. Eventually, we show that the security of the forward secure pseudorandom number generator of Bellare and Yee against side-channel attacks cannot be directly generalized in the standard model. It is an open problem to determine the minimum black box assumptions and restrictions of the leakage function for this purpose.
Last updated:  2014-06-03
Efficient Indifferentiable Hashing into Ordinary Elliptic Curves
Eric Brier, Jean-Sebastien Coron, Thomas Icart, David Madore, Hugues Randriam, Mehdi Tibouchi
We provide the first construction of a hash function into ordinary elliptic curves that is indifferentiable from a random oracle, based on Icart's deterministic encoding from Crypto 2009. While almost as efficient as Icart's encoding, this hash function can be plugged into any cryptosystem that requires hashing into elliptic curves, while not compromising proofs of security in the random oracle model. We also describe a more general (but less efficient) construction that works for a large class of encodings into elliptic curves, for example the Shallue-Woestijne-Ulas (SWU) algorithm. Finally we describe the first deterministic encoding algorithm into elliptic curves in characteristic 3.
Last updated:  2009-07-13
A Novel ID-based Electronic Cash System from Pairings
Jue-Sam Chou, Yalin Chen, Ming-Hsun Cho, Hung-Min Sun
Recently, Chen et al. and Juang et al. each proposed one and two e-cash payment systems respectively. They claimed that their schemes are secure. However, in this paper, we will present the shortcomings of their schemes and then propose a novel one from pairings. After security analysis and comparison, we conclude that our scheme not only is more secure but also possesses more functions that a secure electronic cash system should encompass than all of the proposed protocols.
Last updated:  2009-07-13
Security weaknesses in two multi-server password based authentication protocols
Uncategorized
Jue-Sam Chou, Chun-Hui Huang, Cheng-Chung Ding
Show abstract
Uncategorized
In 2004 and 2005, Tsaur et al. proposed a smart card based password authentication schemes for multi-server environments, respectively. They claimed that their protocols are safe and can withstand various kinds of attacks. However, after analysis, we found their schemes each have some secure loopholes. In this article, we will show the security flaws in these two protocols.
Last updated:  2009-07-13
A New Lattice-Based Cryptosystem Mixed with a Knapsack
Yanbin Pan, Yingpu Deng, Yupeng Jiang, Ziran Tu
In this paper, we present a new lattice-based public-key cryptosystem mixed with a knapsack, which has reasonable key size and quick encryption and decryption. The module strategy in our cryptosystem can also be used to construct a framework for some GGH-type cryptosystems to improve their security.
Last updated:  2011-08-28
Partial Signatures and their Applications
Uncategorized
Mihir Bellare, Shanshan Duan
Show abstract
Uncategorized
We introduce Partial Signatures, where a signer, given a message, can compute a ``stub'' which preserves her anonymity, yet later she, but nobody else, can complete the stub to a full and verifiable signature under her public key. We provide a formal definition requiring three properties, namely anonymity, unambiguity and unforgeability. We provide schemes meeting our definition both with and without random oracles. Our schemes are surprisingly cheap in both bandwidth and computation. We describe applications including anonymous bidding and betting.
Last updated:  2009-12-26
Related-Key Rectangle Attack of the Full 80-Round HAS-160 Encryption Mode
Ewan Fleischmann, Michael Gorski, Stefan Lucks
In this paper we investigate the security of the encryption mode of the HAS-160 hash function. HAS-160 is a Korean hash standard which is widely used in Korea's industry. The structure of HAS-160 is similar to SHA-1 but includes some improvements. The encryption mode of HAS-160 is defined similarly as the encryption mode of SHA-1 that is called SHACAL-1. In 2006, Dunkelman et. al. successfully broke the full 80-round SHACAL-1. In this paper, we present the first cryptographic attack that breaks the encryption mode of the full 80-round HAS-160. SHACAL-1 and the encryption mode of HAS-160 are both blockciphers with key size 512 bits and plain-/ciphertext size of 160 bits. We will apply a key recovery attack that needs about 2^{155} chosen plaintexts and 2^{375.98} 80-round HAS-160 encryptions. The attack does not aim for a collision, preimage or 2nd-preimage attack, but it shows that HAS-160 used as a block cipher can be differentiated from an ideal cipher faster than exhaustive search.
Last updated:  2009-07-09
Attacking Reduced Rounds of the ARIA Block Cipher
Ewan Fleischmann, Michael Gorski, Stefan Lucks
ARIA is a block cipher proposed at ICISC'03. Its design is very similar to the advanced encryption standard (AES). The authors propose that on 32-bit processors, the encryption speed is at least 70% of that of the AES. They claim to offer a higher security level than AES. In this paper we present two attacks of reduced round ARIA which shows some weaknesses of the cipher. Moreover, our attacks have the lowest memory requirements compared to existing attacks on ARIA with an increase in the time complexity.
Last updated:  2009-07-09
Hard Fault Analysis of Trivium
Yupu Hu, Fengrong Zhang, Yiwei Zhang
Fault analysis is a powerful attack to stream ciphers. Up to now, the major idea of fault analysis is to simplify the cipher system by injecting some soft faults. We call it soft fault analysis. As a hardware--oriented stream cipher, Trivium is weak under soft fault analysis. In this paper we consider another type of fault analysis of stream cipher, which is to simplify the cipher system by injecting some hard faults. We call it hard fault analysis. We present the following results about such attack to Trivium. In Case 1 with the probability not smaller than 0.2396, the attacker can obtain 69 bits of 80--bits--key. In Case 2 with the probability not smaller than 0.2291, the attacker can obtain all of 80--bits--key. In Case 3 with the probability not smaller than 0.2291, the attacker can partially solve the key. In Case 4 with non--neglectable probability, the attacker can obtain a simplified cipher, with smaller number of state bits and slower non--linearization procedure. In Case 5 with non--neglectable probability, the attacker can obtain another simplified cipher. Besides, these 5 cases can be checked out by observing the key--stream.
Last updated:  2009-07-08
Untraceable RFID protocols are not trivially composable: Attacks on the revision of EC-RAC
Ton van Deursen, Sasa Radomirovic
It is well-known that protocols that satisfy a security property when executed in isolation do not necessarily satisfy the same security property when they are executed in an environment containing other protocols. We demonstrate this fact on a family of recently proposed RFID protocols by Lee, Batina, and Verbauwhede. We invalidate the authentication and untraceability claims made for several of the family's protocols. We also present man-in-the-middle attacks on untraceability in all of the protocols in the family. Similar attacks can be carried out on some other protocols in the literature, as well. We briefly indicate how to repair the protocols.
Last updated:  2009-07-07
Security Notions and Generic Constructions for Client Puzzles
Uncategorized
L. Chen, P. Morrissey, N. P. Smart, B. Warinschi
Show abstract
Uncategorized
Computational puzzles are mildly difficult computational problems that require resources (processor cycles, memory, or both) to solve. Puzzles have found a variety of uses in security. In this paper we are concerned with {\em client puzzles}: a type of puzzle used as a defense against Denial of Service (DoS) attacks. Before engaging in a resource consuming protocol with a client, a server demands that the client solves a freshly generated client puzzle. Despite their widespread use, the lack of formal models for security of client puzzles prevents a full analysis of proposed puzzles and, more importantly, prevents rigorous proofs for the effectiveness of puzzles as a DoS defense. The main contribution of this paper is a formal model for the security of client puzzles as a stepping stone towards solving the above problems. We clarify the interface that client puzzles should offer and give two security notions for puzzles. Both functionality and security are inspired by, and tailored to, the use of puzzles as a defense against DoS attacks. The first notion -- puzzle unforgeability -- requires that an adversary is unable to produce valid looking puzzles on its own. The second notion -- puzzle-difficulty -- requires that an adversary spends at least an appropriate amount of resources solving puzzles. Our definitions fill an important gap: breaking either of the two properties immediately leads to successful DoS attacks. We illustrate this point with an attack against a previously proposed puzzle construction. We show that a subtle flaw renders the construction forgeable and we explain how to exploit this flaw to mount a DoS attack on certain protocols that use this puzzle. We also provide a generic construction of a client puzzle. Our construction uses a pseudorandom function family to provide unforgeability and a one way function for the difficulty. We prove our generic construction meets our definitions of unforgeability and difficulty for client puzzles. Finally, we discuss and analyze (in the random oracle model) a practical instantiation of our construction based on hash functions.
Last updated:  2009-08-04
NTRU, quaternion algebra, public key cryptography
Uncategorized
Ehsan Malekian, Ali Zakerolhosseini, Atefeh
Uncategorized
We propose QTRU, a probabilistic and multi-dimensional public key cryptosystem based on the NTRU public key cryptosystem using quaternion algebra. QTRU encrypts four data vectors in each encryption session and the only other major difference between NTRU and QTRU is that the underlying algebraic structure has been changed to a non-commutative algebraic structure. As a result, QTRU inherits the strength of NTRU and its positive points. In addition, the non-commutativity of the underlying structure of QTRU makes it much more resistant to some lattice-based attacks. After a brief description of NRTU, we begin by describing the algebraic structure used in QTRU. Further, we present the details of the key generation, encryption and decryption algorithms of QTRU and discuss the issues regarding key security, message security, and probability of successful decryption. Last but not least, QTRU’s resistance against lattice-based attacks is investigated.
Last updated:  2009-10-05
Efficient Approximation of Higher Order Boolean function in a Low Order Function
Uncategorized
Mehreen Afzal, Ashraf Masood
Uncategorized
A few of non-linear approximation methods for Boolean functions have been developed but they are not of practical application. However, if a low order Boolean function can be found that can nearly approximate a higher order Boolean function of an encryption technique then the low order Boolean function can be used to exploit the cipher. Such a technique can become a strong cryptanalytic tool and can sneak in a cipher. In this article, an efficient method has been devised to find non-linear low degree approximation of the Boolean function. The algorithm is based on non-linear filter generator followed by solving Galois field 2 equations. To find best approximations execution time of the proposed algorithm is tremendously low as compared the brute force search. Suggested method is very efficient and of practical nature.
Last updated:  2009-07-07
Flowchart description of security primitives for Controlled Physical Unclonable Functions
Boris Skoric, Marc X. Makkes
Physical Unclonable Functions (PUFs) are physical objects that are unique, practically unclonable and that behave like a random function when subjected to a challenge. Their use has been proposed for authentication tokens and anti-counterfeiting. A Controlled PUF (CPUF) consists of a PUF and a control layer that restricts a user's access to the PUF input and output. CPUFs can be used for secure key storage, authentication, certified execution of programs, and certified measurements. In this paper we modify a number of protocols involving CPUFs in order to improve their security. Our modifications mainly consist of encrypting a larger portion of the message traffic, and additional restrictions on the CPUF accessibility. We simplify the description of CPUF protocols by using flowchart notation. Furthermore we explicitly show how the helper data for the PUFs is handled.
Last updated:  2009-07-07
Simple Adaptive Oblivious Transfer Without Random Oracle
Kaoru Kurosawa, Ryo Nojima
Adaptive oblivious transfer (adaptive OT) schemes have wide applications such as oblivious database searches, secure multiparty computation and etc. It is a two-party protocol which simulates an ideal world such that the sender sends $M_1, \cdots, M_n$ to the trusted third party (TTP) first, and then the receiver receives $M_{\sigma_i}$ from TTP adaptively for $i=1,2,\cdots k$. In the standard model, however, the fully simulatable schemes known so far had to rely on dynamic assumptions such as $q$-strong DH assumption, $q$-PDDH assumption and $q$-hidden LRSW assumption. This paper shows two fully simulatable adaptive OT schemes which do not rely on dynamic assumptions in the standard model. Our first scheme holds under the DDH assumption and our second scheme holds under the Paillier's decisional $N$th residuosity assumption, respectively.
Last updated:  2009-08-19
The Application of Polynomials over the Field of Two Elements to a Problem in Intellectual Property
Gregory V. Bard
It is a routine task to convert a digital circuit to a system of polynomial equations over GF(2). A very well-studied set of tools called ``SAT-solvers'', which solve Conjunctive Normal Form logical satisfiability problems, can be used to determine if two circuits are equivalent, as is commonly done in computer engineering. An interesting problem in intellectual property is to determine if two circuits are identical but subject to an unknown permutation of the inputs and outputs. This could be of interest if a manufacturer suspects his encryption circuit has been stolen. While this is easily shown to be a sub-problem of the famously hard “isomorphism of polynomials” problem, we show that in fact it can be easily solved via conversion to a polynomial system of equations over GF(2), and is only slightly harder than if the permutations were in fact known.
Last updated:  2009-07-08
Characterizing Padding Rules of MD Hash Functions Preserving Collision Security
Mridul Nandi
This paper characterizes collision preserving padding rules and provides variants of \MD (MD) which are having less or no overhead costs due to length. We first show that suffix-free property of padding rule is necessary as well as sufficient to preserve the collision security of MD hash function for an arbitrary domain $\s^*$. Knowing this, we propose a simple suffix-free padding rule padding only $\log |M|$ bits for a message $M$, which is less than that of Damg\aa rd's and Sarkar's padding rules. We also prove that the length-padding is not absolutely necessary. We show that a simple variant of MD with $10^d$-padding (or any injective padding) is collision resistant provided that the underlying compression function is collision resistant after chopping the last-bit. Finally, we design another variant of MD hash function preserving all three basic security notions of hash functions, namely collision and (2nd) preimage. This is an improvement over a recently designed (SAC-08) three-property preserving hash function in terms of both salt size and efficiency.
Last updated:  2009-10-08
Group-Oriented Fair Exchange of Signatures
Uncategorized
Qiong Huang, Duncan S. Wong, Willy Susilo
Show abstract
Uncategorized
In an Optimistic Fair Exchange (OFE) for digital signatures, two parties exchange their signatures fairly without requiring any online trusted third party. The third party is only involved when a dispute occurs. In all the previous work, OFE has been considered only in a setting where both of the communicating parties are individuals. There is little work discussing about the fair exchange between two \emph{groups} of users, though we can see that this is actually a common scenario in actual OFE applications. In this paper, we introduce a new variant of OFE, called \emph{Group-Oriented Optimistic Fair Exchange} (GOFE). A GOFE allows two users from two different groups to exchange signatures on behalf of their groups in a fair and anonymous manner. Although GOFE may be considered as a fair exchange for group signatures, it might be inefficient if it is constructed generically from a group signature scheme. Instead, we show that GOFE is \emph{backward compatible} to the Ambiguous OFE (AOFE). Also, we propose an efficient and concrete construction of GOFE, and prove its security under the security models we propose in this model. The security of the scheme relies on the decision linear assumption and strong Diffie-Hellman assumption under the random oracle model.
Last updated:  2009-07-01
Factoring Unbalanced Moduli with Known Bits
Eric Brier, David Naccache, Mehdi Tibouchi
Let $n = pq > q^3$ be an RSA modulus. This note describes a LLL-based method allowing to factor $n$ given $2log_2q$ contiguous bits of $p$, irrespective to their position. A second method is presented, which needs fewer bits but whose length depends on the position of the known bit pattern. Finally, we introduce a somewhat surprising ad hoc method where two different known bit chunks, totalling $\frac32 log_2 q$ bits suffice to factor $n$.
Last updated:  2010-05-13
Certifying Assembly with Formal Cryptographic Proofs: the Case of BBS
Reynald Affeldt, David Nowak, Kiyoshi Yamada
With today's dissemination of embedded systems manipulating sensitive data, it has become important to equip low-level programs with strong security guarantees. Unfortunately, security proofs as done by cryptographers are about algorithms, not about concrete implementations running on hardware. In this paper, we show how to extend security proofs to guarantee the security of assembly implementations of cryptographic primitives. Our approach is based on a framework in the Coq proof-assistant that integrates correctness proofs of assembly programs with game-playing proofs of provable security. We demonstrate the usability of our approach using the Blum-Blum-Shub (BBS) pseudorandom number generator, for which a MIPS implementation for smartcards is shown cryptographically secure.
Last updated:  2012-12-19
Tweakable Enciphering Schemes From Stream Ciphers With IV
Palash Sarkar
We present the first construction of a tweakable enciphering scheme from a stream cipher supporting an initialization vector. This construction can take advantage of the recent advances in hardware efficient stream ciphers to yield disk encryption systems with a very small hardware footprint. Such systems will be attractive for resource constrained devices.
Last updated:  2010-03-17
Automorphic Signatures in Bilinear Groups and an Application to Round-Optimal Blind Signatures
Georg Fuchsbauer
We introduce the notion of automorphic signatures, which satisfy the following properties: the verification keys lie in the message space, messages and signatures consist of elements of a bilinear group, and verification is done by evaluating a set of pairing-product equations. These signatures make a perfect counterpart to the powerful proof system by Groth and Sahai (Eurocrypt 2008). We provide practical instantiations of automorphic signatures under appropriate assumptions and use them to construct the first efficient round-optimal blind signatures. By combining them with Groth-Sahai proofs, we moreover give practical instantiations of various other cryptographic primitives, such as fully-secure group signatures, non-interactive anonymous credentials and anonymous proxy signatures. To do so, we show how to transform signature schemes whose message space is a group to a scheme that signs arbitrarily many messages at once.
Last updated:  2009-07-01
Comments and Improvements on Chameleon Hashing Without Key Exposure Based on Factoring
Xiaofeng Chen, Haibo Tian, Fangguo Zhang
In this paper, we present some security flaws of the key-exposure free chameleon hash scheme based on factoring \cite{GWX07}. Besides, we propose an improved chameleon hash scheme without key exposure based on factoring which enjoys all the desired security notions of chameleon hashing.
Last updated:  2009-07-24
The Fermat factorization method revisited
Robert ERRA, Christophe GRENIER
We consider the well known Fermat factorization method ({\it FFM}) when it is applied on a balanced RSA modulus $N=p\, q>0$, with primes $p$ and $q$ supposed of equal length. We call the {\it Fermat factorization equation} the equation (and all the possible variants) solved by the FFM like ${\cal P}(x,y)=(x+2R)^2-y^2-4N=0$ (where $R=\lceil N^{1/2} \rceil$). These equations are bivariate integer polynomial equations and we propose to solve them directly using Coppersmith's methods for bivariate integer polynomials. As we use them as a black box, our proofs will be brief. We show first that, using Coppersmith's methods, we can factor $N$ in a polynomial time if $|p-q|<N^{3/14}$, with $3/14 \approx 0.214\cdots$ and, using the fact that the Newton polygon of ${\cal P}(x,y)$ is a lower triangle we show a better result: we can indeed factor $N$ in a polynomial time if $|p-q|<N^{1/4}$. Unfortunately this shows that using Coppersmith's methods for bivariate integer polynomials is no better than the FFM, because in that case the FFM is immediate. This is confirmed by numerical experiments. We then propose another method: solving the {\it modular} Fermat factorization equation $ (x+2R)^2-y^2=0 \mod 4N $. Since Coppersmith's methods for {\it modular} multivariate integer polynomial equations are {\it empirical}, there relies on the the famous {\it "resultant heuristic"}, we get only an empirical method that can factor $N$ in a polynomial time if $|p-q|<N^{1/3}$. We conclude with proposals for future works.
Last updated:  2009-12-05
Related-key Cryptanalysis of the Full AES-192 and AES-256
Alex Biryukov, Dmitry Khovratovich
In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has $2^{99.5}$ time and data complexity, while the recent attack by Biryukov-Khovratovich-Nikolic works for a weak key class and has much higher complexity. The second attack is the first cryptanalysis of the full AES-192. Both our attacks are boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers and enhanced with the boomerang switching techniques to gain free rounds in the middle.
Last updated:  2009-09-15
An Efficient Password Security of Key Exchange Protocol based on ECDLP
Uncategorized
Jayaprakash Kar, Banshidhar Majhi
Show abstract
Uncategorized
In this paper we have proposed an efficient password security of Three-Party and Multiparty Key Exchange Protocol based on Elliptic Curve Discrete Logarithm Problem. In three party Key exchange protocols allow two clients with a trusted Server where they registered their password and communicate over a public network to establish a common secret key called session key. Similary multiparty key exchange protocol allow a group of parties communicating over a public network to establish the session key. Due to their significance by in building a secure communication channel, a number of key exchange protocols have been suggested over the years for a variety of settings.Here we have taken two one-way hash functions to built the level of security high.
Last updated:  2009-07-01
Breaking RSA-based PIN Encryption with thirty ciphertext validity queries
Uncategorized
N. P. Smart
Show abstract
Uncategorized
We show that one can recover the PIN from a standardised RSA-based PIN encryption algorithm from a small number of queries to a ciphertext validity checking oracle. The validity checking oracle required is rather special and we discuss whether such oracles could be obtained in the real world. Our method works using a minor extension to the ideas of Bleichenbacher and Manger, in particular we obtain information from negative, as well as positive, responses from the validity checking oracle.
Last updated:  2023-04-11
Secure Two-Party Computation is Practical
B. Pinkas, T. Schneider, N. P. Smart, S. Williams
Secure multi-party computation has been considered by the cryptographic community for a number of years. Until recently it has been a purely theoretical area, with few implementations with which to test various ideas. This has led to a number of optimisations being proposed which are quite restricted in their application. In this paper we describe an implementation of the two-party case, using Yao’s garbled circuits, and present various algorithmic protocol improvements. These optimisations are analysed both theoretically and empirically, using experiments of various adversarial situations. Our experimental data is provided for reasonably large circuits, including one which performs an AES encryption, a problem which we discuss in the context of various possible applications.
Last updated:  2009-07-01
Identity Based Group Signatures from Hierarchical Identity-Based Encryption
Uncategorized
Nigel P. Smart, Bogdan Warinschi
Show abstract
Uncategorized
A number of previous papers explored the notion of identity-based group signature. We present a generic construction of identity-based group signatures. Our construction is based on the Naor transformation of a identity-based signature out of an identity-based encryption, adjusted to hierarchical identity-based encryption. We identify sufficient conditions on the underlying HIBE so that the scheme that results from our transformation meets our security definitions. Finally, we suggest a couple of extensions enabled by our construction, one of which is to hierarchical identity-based group signatures.
Last updated:  2009-11-06
Jacobi Quartic Curves Revisited
Uncategorized
Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson
Show abstract
Uncategorized
This paper provides new results about efficient arithmetic on Jacobi quartic form elliptic curves, $y^2 = d x^4 + 2 a x^2 + 1$. With recent proposals, the arithmetic on Jacobi quartic curves became solidly faster than that of Weierstrass curves. These proposals use up to 7 coordinates to represent a single point. However, fast scalar multiplication algorithms based on windowing techniques, precompute and store several points which require more space than what it takes with 3 coordinates. Also note that some of these proposals require $d = 1$ for full speed. Unfortunately, elliptic curves having 2-times-a-prime number of points, cannot be written in Jacobi quartic form if $d = 1$. Even worse the contemporary formulae may fail to output correct coordinates for some inputs. This paper provides improved speeds using fewer coordinates without causing the above mentioned problems. For instance, our proposed point doubling algorithm takes only 2 multiplications, 5 squarings, and no multiplication with curve constants when $d$ is arbitrary and $a = \pm1/2$.
Last updated:  2009-07-01
Multi Party Distributed Private Matching, Set Disjointness and Cardinality Set Intersection with Information Theoretic Security
Sathya Narayanan G, Aishwarya T, Anugrah Agrawal, Arpita Patra, Ashish Choudhary, Pandu Rangan C
In this paper, we focus on the specific problems of Private Matching, Set Disjointness and Cardinality Set Intersection in information theoretic settings. Specifically, we give perfectly secure protocols for the above problems in n party settings, tolerating a computational ly unbounded semi-honest adversary, who can passively corrupt at most t < n/2 parties. To the best of our knowledge, these are the first such information theoretically secure protocols in a multi-party setting for all three problems. Previous solutions for Distributed Private Matching and Cardinality Set Intersection were cryptographical ly secure and the previous Set Disjointness solution, though information theoretically secure, is in a two party setting. We also propose a new model for Distributed Private matching which is relevant in a multi-party setting.
Last updated:  2012-01-23
RFID distance bounding protocol with mixed challenges to prevent relay attacks
Chong Hee Kim, Gildas Avoine
RFID systems suffer from different location-based attacks such as distance fraud, mafia fraud and terrorist fraud attacks. Among them mafia fraud attack is the most serious since this attack can be mounted without the notice of both the reader and the tag. An adversary performs a kind of man-in-the-middle attack between the reader and the tag. It is very difficult to prevent this attack since the adversary does not change any data between the reader and the tag. Recently distance bounding protocols measuring the round-trip time between the reader and the tag have been researched to prevent this attack. All the existing distance bounding protocols based on binary challenges, without final signature, provide an adversary success probability equal to (3/4)^n where n is the number of rounds in the protocol. In this paper, we introduce a new protocol based on binary mixed challenges that converges toward the expected and optimal (1/2)^n bound. We prove its security in case of both noisy and non-noisy channels.
Last updated:  2009-07-01
Fault Attacks on RSA Signatures with Partially Unknown Messages
Jean-Sebastien Coron, Antoine Joux, Ilya Kizhvatov, David Naccache, Pascal Paillier
Fault attacks exploit hardware malfunctions to recover secrets from embedded electronic devices. In the late 90's, Boneh, DeMillo and Lipton introduced fault-based attacks on {\sc crt-rsa}. These attacks factor the signer's modulus when the message padding function is deterministic. However, the attack does not apply when the message is partially unknown, for example when messages contain some randomness which is recovered only when verifying a {\sl correct} signature. In this paper we successfully extends RSA fault attacks to a large class of partially known message configurations. The new attacks rely on Coppersmith's algorithm for finding small roots of multivariate polynomial equations. We illustrate the approach by successfully attacking several randomized versions of the ISO 9796-2 encoding standard. Practical experiments show that a $2048$-bit modulus can be factored in less than a minute given one faulty signature containing $160$ random bits and an unknown $160$-bit message digest.
Last updated:  2012-05-02
A note on the Certificateless Multi-receiver Signcryption Scheme
S. Sharmila Deva Selvi, S. Sree Vivek, C. Pandu Rangan
Certificateless cryptography aims at combining the advantages of identity based and public key cryptography, so as to avoid the key escrow problem inherent in the identity based system and cumbersome certificate management in public key infrastructure. Signcryption achieves confidentiality and authentication simultaneously in an e
Last updated:  2009-10-12
Anonymous Signatures Revisited
Vishal Saraswat, Aaram Yun
We revisit the notion of the anonymous signature, first formalized by Yang, Wong, Deng and Wang, and then further developed by Fischlin, and Zhang and Imai. We present a new formalism of anonymous signature, where instead of the message, a part of the signature is withheld to maintain anonymity. We introduce the notion unpretendability to guarantee infeasibility for someone other than the correct signer to pretend authorship of the message and signature. Our definition retains applicability for all previous applications of the anonymous signature, provides stronger security, and is conceptually simpler. We give a generic construction from any ordinary signature scheme, and also show that the short signature scheme by Boneh and Boyen can be naturally regarded as such a secure anonymous signature scheme according to our formalism.
Last updated:  2009-07-01
Authentic Time-Stamps for Archival Storage
Alina Oprea, Kevin D. Bowers
We study the problem of authenticating the content and creation time of documents generated by an organization and retained in archival storage. Recent regulations (e.g., the Sarbanes-Oxley act and the Securities and Exchange Commission rule) mandate secure retention of important business records for several years. We provide a mechanism to authenticate bulk repositories of archived documents. In our approach, a space efficient local data structure encapsulates a full document repository in a short (e.g., 32-byte) digest. Periodically registered with a trusted party, these commitments enable compact proofs of both document creation time and content integrity. The data structure, an append-only persistent authenticated dictionary, allows for efficient proofs of existence and non-existence, improving on state-of-the-art techniques. We give a rigorous security analysis of our solution and confirm through an experimental evaluation with the Enron email corpus its feasibility in practice.
Last updated:  2009-06-24
Improved generic algorithms for 3-collisions
Antoine Joux, Stefan Lucks
An $r$-collision for a function is a set of $r$ distinct inputs with identical outputs. Actually finding $r$-collisions for a random map over a finite set of cardinality $N$ requires at least about $N^{(r-1)/r} $ units of time on a sequential machine. For $r$=2, memoryless and well-parallelisable algorithms are known. The current paper describes memory-efficient and parallelisable algorithms for $r \ge 3$. The main results are: (1)~A sequential algorithm for 3-collisions, roughly using memory $N^\alpha$ and time $N^{1-\alpha}$ for $\alpha\le1/3$. I.e., given $N^{1/3}$ units of storage, on can find 3-collisions in time $N^{2/3}$. Note that there is a time-memory tradeoff which allows to reduce the memory consumption. (2)~A parallelisation of this algorithm using $N^{1/3}$ processors running in time $N^{1/3}$. Each single processor only needs a constant amount of memory. (3)~An generalisation of this second approach to $r$-collisions for $r \ge3$: given $N^s$ parallel processors, on can generate $r$-collisions roughly in time $N^{((r-1)/r)-s}$, using memory $N^{((r-2)/r)-s}$ on every processor.
Last updated:  2010-04-27
Factor-4 and 6 Compression of Cyclotomic Subgroups
Uncategorized
Koray Karabina
Show abstract
Uncategorized
Bilinear pairings derived from supersingular elliptic curves of embedding degrees 4 and 6 over finite fields of characteristic two and three, respectively, have been used to implement pairing-based cryptographic protocols. The pairing values lie in certain prime-order subgroups of certain cyclotomic subgroups. It was previously known how to compress the pairing values over characteristic two fields by a factor of 2, and the pairing values over characteristic three fields by a factor of 6. In this paper, we show how the pairing values over characteristic two fields can be compressed by a factor of 4. Moreover, we present and compare several algorithms for performing exponentiation in the prime-order subgroups using the compressed representations. In particular, in the case where the base is fixed, we expect to gain at least a 54% speed up over the fastest previously known exponentiation algorithm that uses factor-6 compressed representations.
Last updated:  2009-06-24
Key extraction from general non-discrete signals
Uncategorized
E. Verbitskiy, P. Tuyls, C. Obi, B. Schoenmakers, B. Skoric
Show abstract
Uncategorized
We address the problem of designing optimal schemes for the generation of secure cryptographic keys from continuous noisy data. We argue that, contrary to the discrete case, a universal fuzzy extractor does not exist. This implies that in the continuous case, key extraction schemes have to be designed for particular probability distributions. We extend the known definitions of the correctness and security properties of fuzzy extractors. Our definitions apply to continuous as well as discrete variables. We propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretisation, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise. Finally, we study the security implications of incomplete knowledge of the source's probability distribution P. We derive a bound on the min-entropy of the extracted key under the worst case assumption, where the attacker knows P exactly.
Last updated:  2010-01-27
Cryptanalysis of ESSENCE
Maria Naya-Plasencia, Andrea Röck, Jean-Philippe Aumasson, Yann Laigle-Chapuy, Gaëtan Leurent, Willi Meier, Thomas Peyrin
ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities 2^67.4 and 2^134.7. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.
Last updated:  2009-06-24
A Probabilistic Secret Sharing Scheme for a Compartmented Access Structure
Uncategorized
Yuyin Yu, Mingsheng Wang
Show abstract
Uncategorized
In a compartmented access structure, there are disjoint participants C1, . . . ,Cm. The access structure consists of subsets of participants containing at least ti from Ci for i = 1, . . . ,m, and a total of at least t0 participants. Tassa [2] asked: whether there exists an efficient ideal secret sharing scheme for such an access structure? Tassa and Dyn [5] presented a solution using the idea of bivariate interpolation and the concept of dual program [9, 10]. For the purpose of practical applications, it is advantageous to have a simple scheme solving the problem. In this paper a simple scheme is given for this problem using the similar idea from [5].
Last updated:  2009-06-24
Universally Composable Contributory Group Key Exchange
M. Choudary Gorantla, Colin Boyd, Juan Manuel Gonzàlez Nieto
We treat the security of group key exchange (GKE) in the universal composability (UC) framework. Analyzing GKE protocols in the UC framework naturally addresses attacks by malicious insiders. We define an ideal functionality for GKE that captures contributiveness in addition to other desired security goals. We show that an efficient two-round protocol securely realizes the proposed functionality in the random oracle model. As a result, we obtain the most efficient UC-secure contributory GKE protocol known.
Last updated:  2009-10-15
On the security of oscillator-based random number generators
Mathieu Baudet, David Lubicz, Julien Micolod, André Tassiaux
Physical random number generators (a.k.a. TRNGs) appear to be critical components of many cryptographic systems. Yet, such building blocks are still too seldom provided with a formal assessment of security, in comparison to what is achieved for conventional cryptography. In this work, we present a comprehensive statistical study of TRNGs based on the sampling of an oscillator subject to phase noise (a.k.a. phase jitters). This classical layout, typically instantiated with a ring oscillator, provides a simple and attractive way to implement a TRNG on a chip. Our mathematical study allows one to evaluate and control the main security parameters of such a random source, including its entropy rate and the biases of certain bit patterns, provided that a small number of physical parameters of the oscillator are known. In order to evaluate these parameters in a secure way, we also provide an experimental method for filtering out the global perturbations affecting a chip and possibly visible to an attacker. Finally, from our mathematical model, we deduce specific statistical tests applicable to the bit stream of a TRNG. In particular, in the case of an insecure configuration, we show how to recover the parameters of the underlying oscillator.
Last updated:  2010-06-15
Cryptanalysis of Certificateless Signcryption Schemes and an Efficient Construction Without Pairing
Uncategorized
S. Sharmila Deva Selvi, S. Sree Vivek, C. Pandu Rangan
Show abstract
Uncategorized
Certificateless cryptography introduced by Al-Riyami and Paterson eliminates the key escrow problem inherent in identity based cryptosystems. Even though building practical identity based signcryption schemes without bilinear pairing are considered to be almost impossible, it will be interesting to explore possibilities of constructing such systems in other settings like certificateless cryptography. Often for practical systems, bilinear pairings are considered to induce computational overhead. Signcryption is a powerful primitive that offers both confidentiality and authenticity to noteworthy messages. Though some prior attempts were made for designing certificateless signcryption schemes, almost all the known ones have security weaknesses. Specifically, in this paper we demonstrate the security weakness of the schemes in \cite{BF08}, \cite{DRJR08} and \cite{CZ08}. We also present the first provably secure certificateless signcryption scheme without bilinear pairing and prove it in the random oracle model.
Last updated:  2009-08-04
A New Improved Distinguisher for HC-128
Subhabrata Sen, Rudradev Sengupta, Subhamoy Maitra, Goutam Paul, Shashwat Raizada
In this paper, we present a new distinguisher for HC-128 which is the best known so far. The distinguisher requires approximately $2^{138}$ keystream words with success probability 0.9772.
Last updated:  2009-09-07
Perfectly Balanced Functions in Symbolic Dynamics
O. A. Logachev, A. A. Salnikov, S. V. Smyshlyaev, V. V. Yashchenko
In the present paper we study properties of perfectly balanced Boolean functions. Based on the concept of Boolean function barrier, we propose a novel approach to construct large classes of perfectly balanced Boolean functions.
Last updated:  2009-07-01
Defending Against Key Abuse Attacks in KP-ABE Enabled Broadcast Systems
Shucheng Yu, Kui Ren, Wenjing Lou, Jin Li
Key-Policy Attribute-Based Encryption (KP-ABE) is a promising cryptographic primitive which enables fine-grained access control over sensitive data. However, key abuse attacks in KP-ABE may impede its wide application especially in copyright-sensitive systems. To defend against this kind of attacks, this paper proposes a novel KP-ABE scheme which is able to disclose any illegal key distributor’s ID when key abuse is detected. In our scheme, each bit of user ID is defined as an attribute and the user secret key is associated with his unique ID. The tracing algorithm fulfills its task by tricking the pirate device into decrypting the ciphertext associated with the corresponding bits of his ID. Our proposed scheme has the salient property of black box tracing, i.e., it traces back to the illegal key distributor’s ID only by observing the pirate device’s outputs on certain inputs. In addition, it does not require the pirate device’s secret keys to be well-formed as compared to some previous work. Our proposed scheme is provably secure under the Decisional Bilinear Diffie-Hellman (DBDH) assumption and the Decisional Linear (DL) assumption.
Last updated:  2009-06-24
Low Latency High Bandwidth Anonymous Overlay Network with Anonymous Routing
Uncategorized
Roman Schlegel, Duncan S. Wong
Show abstract
Uncategorized
Most existing anonymous networks focus on providing strong anonymity for the price of having lower bandwidth, higher latency and degraded usability when compared with the conventional use of the Internet. They also often anonymize only a few specific applications. In this paper, we propose a new approach of constructing an anonymous network. The network consists of an overlay network, which provides anonymity to all applications running on top of it, and a routing protocol, which can be considered as an anonymized version of path vector routing. The protocol preserves the high performance characteristics of the path vector routing and also has the added advantage of hiding the overlay network topology. Our simulation results show that the expected latency of our approach is 50% better than that of existing systems. Besides the new anonymous routing protocol, this paper aims to provide the general overview of this new anonymous overlay network which may serve as the input for further research.
Last updated:  2009-06-24
Enhancing Attribute-based Encryption with Attribute Hierarchy
Jin Li, Qian Wang, Cong Wang, Kui Ren
Attribute-based encryption (ABE) has been envisioned as a promising cryptographic primitive for realizing secure and flexible access control. However, ABE is being criticized for its high scheme overhead as extensive pairing operations are usually required. In this paper, we focus on improving the efficiency of ABE by leveraging a previously overlooked fact, i.e., the often-found hierarchical relationships among the attributes that are inherent to many access control scenarios. As the first research effort along this direction, we coin the notion of hierarchical ABE (\textsf{HABE}), which can be viewed as the generalization of traditional ABE in the sense that both definitions are equal when all attributes are independent. We further give a concrete \textsf{HABE} construction considering a tree hierarchy among the attributes, which is provably secure. More importantly, our construction exhibits significant improvements over the traditional ABE when attribute hierarchies exist.
Last updated:  2011-09-27
Implementing Wagner's generalized birthday attack against the SHA-3 round-1 candidate FSB
Daniel J. Bernstein, Tanja Lange, Ruben Niederhagen, Christiane Peters, Peter Schwabe
This paper applies generalized birthday attacks to the FSB compression function, and shows how to adapt the attacks so that they run in far less memory. In particular, this paper presents details of a parallel implementation attacking FSB48 , a scaled-down version of FSB proposed by the FSB submitters. The implementation runs on a cluster of 8 PCs, each with only 8GB of RAM and 700GB of disk. This situation is very interesting for estimating the security of systems against distributed attacks using contributed off-the-shelf PCs.
Last updated:  2009-06-17
Modeling Key Compromise Impersonation Attacks on Group Key Exchange Protocols
M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto
A key exchange protocol allows a set of parties to agree upon a secret session key over a public network. Two-party key exchange (2PKE) protocols have been rigorously analyzed under various models considering different adversarial actions. However, the analysis of group key exchange (GKE) protocols has not been as extensive as that of 2PKE protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for the case of GKE protocols. We first model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure even against outsider KCI attacks. The attacks on these protocols demonstrate the necessity of considering KCI resilience for GKE protocols. Finally, we give a new proof of security for an existing GKE protocol under the revised model assuming random oracles.
Last updated:  2009-06-19
Security Analysis of Aggregate signature and Batch verification signature schemes
Uncategorized
S. Sharmila Deva Selvi, S. Sree Vivek, J. Shriram, S. Kalaivani, C. Pandu Rangan
Show abstract
Uncategorized
An identity based signature scheme allows any pair of users to communicate securely and to verify each others signatures without exchanging public key certificates. An aggregate signature scheme is a digital signature scheme which supports aggregation of signatures. Batch verification is a method to verify multiple signatures at once. Aggregate signature is useful in reducing both communication and computation cost. In this paper, we describe the breaks possible in some of the aggregate signature schemes and batch verification scheme.
Last updated:  2009-06-17
Analysis of the End-by-Hop Protocol for Secure Aggregation in Sensor Networks
Erik Zenner
In order to save bandwidth and thus battery power, sensor network measurements are sometimes aggregated en-route while being reported back to the querying server. Authentication of the measurements then becomes a challenge if message integrity is important for the application. At ESAS 2007, the End-by-Hop protocol for securing in-network aggregation for sensor nodes was presented. The solution was claimed to be secure and efficient and to provide the possibility of trading off bandwidth against computation time on the server. In this paper, we disprove these claims. We describe several attacks against the proposed solution and point out shortcomings in the original complexity analysis. In particular, we show that the proposed solution is inferior to a naive solution without in-network aggregation both in security and in efficiency.
Last updated:  2009-06-16
Efficient Key Exchange with Tight Security Reduction
Jiang Wu, Berkant Ustaoglu
In this paper, we propose two authenticated key exchange (AKE) protocols, SMEN and SMEN&#8722;, which have efficient online computation and tight security proof in the extended Canetti-Krawczyk (eCK) model. SMEN takes 1.25 exponentiations in online computation, close to that (1.17 exponentiations) of the most efficient AKEs MQV and its variants HMQV and CMQV. SMEN has a security reduction as tight as that of NAXOS, which is the first AKE having a tight security reduction in the eCK model. As a comparison, MQV does not have a security proof; both HMQV and CMQV have a highly non-tight security reduction, and HMQV needs a non-standard assumption; NAXOS takes 2.17 exponentiations in online computation; NETS, a NAXOS variant, takes two online exponentiations in online computation. SMEN simultaneously achieves online efficiency and a tight security proof at a cost of 0.17 more exponentiations in offline computation and the restriction that one party is not allowed to establish a key with itself. SMEN&#8722; takes 1.29 exponentiations in online computation, but SMEN&#8722; does not use the static private key to compute the ephemeral public key (as does in SMEN, NAXOS, CMQV, and NETS), and hence reduces the risk of leaking the static private key.
Last updated:  2009-06-16
Generic Attacks on Alternating Unbalanced Feistel Schemes
Valerie Nachef
\begin{abstract} Generic attacks against classical (balanced) Feistel schemes, unbalanced Feistel schemes with contracting functions and unbalanced Feistel schemes with expanding functions have been studied in \cite {P01}, \cite{Jut}, \cite{PNB06}, \cite{PNB07}. In this paper we study schemes where we use alternatively contracting random functions and expanding random functions. We name these schemes ``Alternating Unbalanced Feistel Schemes''. They allow constructing pseudo-random permutations from $kn$ bits to $kn$ bits where $k \geq 3$. At each round, we use either a random function from $n$ bits to $(k-1)n$ bits or a random function from $(k-1)n$ bits to $n$ bits. We describe the best generic attacks we have found. We present``known plaintext attacks'' (KPA) and ``non-adaptive chosen plaintext attacks'' (CPA-1). Let $d$ be the number of rounds. We show that if $d \leq k$, there are CPA-1 with 2 messages and KPA with $m$ the number of messages about $2^{\frac {(d-1)n}{4}}$. For $d \geq k+1$ we have to distinguish $k$ even and $k$ odd. For $k$ even, we have $m=2$ in CPA-1 and $m \simeq 2^{\frac {kn}{4}}$ in KPA. When $k$ is odd, we show that there exist CPA-1 for $d \leq 2k-1$ and KPA for $d \leq 2k+3$ with less than $2^{kn}$ messages and computations. Beyond these values, we give KPA against generators of permutations. \end{abstract}
Last updated:  2009-06-16
On Privacy Losses in the Trusted Agent Model (Abstract)
Paulo Mateus, Serge Vaudenay
Tamper-proof devices are pretty powerful. They typically make security applications simpler (provided that the tamper-proof assumption is not violated). For application requiring privacy, we observe that some properties may become harder (if possible at all) to achieve when devices are maliciously used. We take the example of deniability, receipt-freeness, and anonymity. We formalize the trusted agent model which assumes tamper-proof hardware in a way which captures the notion of programmable secure hardware. This model defines a functionality relative to which deniability requires provers to use a tamper proof hardware. Otherwise, any asymmetric situation in which the malicious verifiers have more powerful tamper-proof devices than the honest ones makes deniability impossible. We conclude by observing that the ability to put boundaries in computing devices prevents from providing full control on how private information spreads: the concept of sealing a device is in some sense incompatible with some privacy notions.
Last updated:  2009-06-16
Efficient Public Key Encryption Based on Ideal Lattices
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa
The potential high efficiency of public-key encryption based on structured lattices was first indicated by the NTRU cryptosystem, which was proposed about 10 years ago. Unfortunately, the security of NTRU is only heuristic. Thus, it remained an important research challenge to construct an efficient encryption scheme based on structured lattices which admits a proof of security relative to a well established cryptographic assumption. We make progress in addressing the above challenge. We show how to construct a CPA-secure public-key encryption scheme with security provably based on the worst case hardness of the approximate Shortest Vector Problem in structured ideal lattices. Under the assumption that the latter is exponentially hard to solve even with a quantum computer, our scheme resists any subexponential attack and offers (quasi-)optimal asymptotic performance: if $n$ is the security parameter, both keys are of bit-length $\softO(n)$ and the amortized costs of both encryption and decryption are $\softO(1)$ per message bit. Our construction adapts the trapdoor one-way function of Gentry, Peikert and Vaikuntanathan (STOC 2008), based on the Learning With Errors problem, to structured lattices. Our main technical tools are an adaptation of Ajtai's trapdoor key generation algorithm (ICALP 1999) to structured ideal lattices, and a re-interpretation of Regev's quantum reduction between the Closest Vector Problem and sampling short lattice vectors. We think these techniques are very likely to find further applications in the future.
Last updated:  2009-07-06
Privacy-aware Attribute-based Encryption with User Accountability
Jin Li, Kui Ren, Bo Zhu, Zhiguo Wan
As a new public key primitive, attribute-based encryption (ABE) is envisioned to be a promising tool for implementing fine-grained access control. To further address the concern of user access privacy, privacy-aware ABE schemes are being developed to achieve hidden access policy recently. For the purpose of secure access control, there is, however, still one critical functionality missing in the existing ABE schemes, which is user accountability. Currently, no ABE scheme can completely prevent the problem of illegal key sharing among users. In this paper, we tackle this problem by firstly proposing the notion of accountable, anonymous, and ciphertext-policy ABE (CP-A$^3$BE, in short) and then giving out a concrete construction. We start by improving the state-of-the-art of anonymous CP-ABE to obtain shorter public parameters and ciphertext length. In the proposed CP-A$^3$BE construction, user accountability can be achieved in black-box model by embedding additional user-specific information into the attribute private key issued to that user, while still maintaining hidden access policy. The proposed constructions are provably secure.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.