All papers in 2007 (482 results)

Leonardo B. Oliveira, Michael Scott, Julio López, Ricardo Dahab
Show abstract
Key distribution in Wireless Sensor Networks (WSNs) is challenging. Symmetric cryptosystems can perform it efficiently, but they often do not provide a perfect trade-off between resilience and storage. Further, even though conventional public key and elliptic curve cryptosystem are computationally feasible on sensor nodes, protocols based on them are not. They require exchange and storage of large keys and certificates, which is expensive. Using Pairing-based Cryptography (PBC) protocols, conversely, parties can agree on keys without any interaction. In this work, we (i) show how security in WSNs can be bootstrapped using an authenticated identity-based non-interactive protocol and (ii) present TinyPBC, to our knowledge, the most efficient implementation of PBC primitives for an 8-bit processor. TinyPBC is an open source code able to compute pairings as well as binary multiplication in about 5.5s and 4019.46$\mu$s, respectively, on the ATmega128L 7.3828-MHz/4KB SRAM/128KB ROM processor -- the MICA2 and MICAZ node processor.
Last updated:  2008-01-07
Uncategorized
(withdrawn)
Xianhui Lu, Xuejia Lai, Dake He
Last updated:  2008-05-06
Uncategorized
Junko Takahashi, Toshinori Fukunaga
Show abstract
This letter proposes a differential fault analysis on the AES key schedule and shows how an entire 128-bit AES key can be retrieved. In the workshop at FDTC 2007, we presented the DFA mechanism on the AES key schedule and proposed general attack rules. Using our proposed rules, we showed an efficient attack that can retrieve 80 bits of the 128-bit key. Recently, we have found a new attack that can obtain an additional 8 bits compared with our previous attack. As a result, we present most efficient attack for retrieving 88 bits of the 128-bit key using approximately two pairs of correct and faulty ciphertexts.
Last updated:  2007-12-28
J. Wu, D. R. Stinson
Show abstract
In this paper, we propose an extremely simple identification protocol and prove its security using the Knowledge-of-Exponent Assumption (KEA). We discuss the applicability of KEA in various protocol settings as well. Recently, doubts have been raised about applying KEA in some protocols where an adversary has auxiliary inputs. However, we suggest that KEA is applicable in these cases. We present two variants of KEA, Generalized KEA (GKEA) and Auxiliary-Input KEA (AI-KEA), to clarify the proper use of KEA.
Last updated:  2008-05-15
Dafna Kidron, Yehuda Lindell
Show abstract
Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the key-registration public-key infrastructure of Barak et al.~in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the {\em plain model}\/ where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.
Last updated:  2010-06-06
Andrey Bogdanov, Andrey Pyshkin
Show abstract
This paper presents a new powerful side-channel cryptanalytic method - algebraic collision attacks - representing an efficient class of power analysis being based on both the power consumption information leakage and specific structure of the attacked cryptographic algorithm. This can result in an extremely low measurement count needed for a key recovery. The algebraic collision attacks are well applicable to AES, if one-byte collisions are detectable. For the recovery of the complete AES key, one needs 3 measurements with a probability of 0.42 and 4.24 PC hours post-processing, 4 measurements with a probability of 0.82 and several seconds of offline computations or 5 measurements with success probability close to 1 and several seconds of post-processing.
Last updated:  2007-12-28
Xu Zijie
Show abstract
In this paper I describe the construction of Dynamic SHA family of cryptographic hash functions. They are built with design components from the SHA-2 family, but there is function R in the new hash functionh. It enabled us to achieve a novel design principle: When message is changed, different rotate right operation maybe done. It make the system can resistant against all extant attacks.
Last updated:  2008-11-20
Uncategorized
Ran Canetti
Show abstract
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, ``plain'' model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system's components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.
Last updated:  2007-12-19
Martin Cochran
Show abstract
Although advances in SHA-1 cryptanalysis have been made since the 2005 announcement of a $2^{63}$ attack by Wang et al., the details of the attack have not yet been vetted; this note does just that. Working from Adi Shamir's 2005 CRYPTO rump session presentation of Wang et al.'s work, this note corroborates and presents the differential path and associated conditions for the two-block attack. Although the error analysis for the advanced condition correction technique is not verified, a method is given which yields a two-block collision attack on SHA-1 requiring an estimated $2^{62}$ SHA-1 computations if the original error analysis by Wang et al. is correct.
Last updated:  2008-08-25
Tatsuaki Okamoto
Show abstract
This paper presents a new paradigm to realize cryptographic primitives such as authenticated key exchange and key encapsulation without random oracles under three assumptions: the decisional Diffie-Hellman (DDH) assumption, target collision resistant (TCR) hash functions and a class of pseudo-random functions (PRFs), $\pi$PRFs, PRFs with pairwise-independent random sources. We propose a (PKI-based) two-pass authenticated key exchange (AKE) protocol that is comparably as efficient as the existing most efficient protocols like MQV and that is secure without random oracles (under these assumptions). Our protocol is shown to be secure in the (currently) strongest security definition, the extended Canetti-Krawczyk (eCK) security definition introduced by LaMacchia, Lauter and Mityagin. We also show that a variant of the Kurosawa-Desmedt key encapsulation mechanism (KEM) using a $\pi$PRF is CCA-secure under the three assumptions. This scheme is secure in a stronger security notion, the chosen public-key and ciphertext attack (CPCA) security, with using a generalized TCR (GTCR) hash function in place of a TCR hash function. The proposed schemes in this paper are validity-check-free and the implication is that combining them with validity-check-free symmetric encryption (DEM) will yield validity-check-free (e.g., MAC-free) CCA-secure hybrid encryption.
Last updated:  2007-12-26
Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, Christian Rechberger
Show abstract
The stream cipher Salsa20 was introduced by Bernstein in 2005 as a candidate in the eSTREAM project, accompanied by the reduced versions Salsa20/8 and Salsa20/12. ChaCha is a variant of Salsa20 aiming at bringing better diffusion for similar performance. Variants of Salsa20 with up to 7 rounds (instead of 20) have been broken by differential cryptanalysis, while ChaCha has not been analyzed yet. We introduce a novel method for differential cryptanalysis of Salsa20 and ChaCha, inspired by correlation attacks and related to the notion of neutral bits. This is the first application of neutral bits in stream cipher cryptanalysis. It allows us to break the 256-bit version of Salsa20/8, to bring faster attacks on the 7-round variant, and to break 6- and 7-round ChaCha. In a second part, we analyze the compression function Rumba, built as the XOR of four Salsa20 instances and returning a 512-bit output. We find collision and preimage attacks for two simplified variants, then we discuss differential attacks on the original version, and exploit a high-probability differential to reduce complexity of collision search from 2^256 to 2^79 for 3-round Rumba. To prove the correctness of our approach we provide examples of collisions and near-collisions on simplified versions.
Last updated:  2008-03-14
Uncategorized
Erik Tews
Show abstract
WEP is a protocol for securing wireless networks. In the past years, many attacks on WEP have been published, totally breaking WEP’s security. This thesis summarizes all major attacks on WEP. Additionally a new attack, the PTW attack, is introduced, which was partially developed by the author of this document. Some advanced versions of the PTW attack which are more suiteable in certain environments are described as well. Currently, the PTW attack is fastest publicly known key recovery attack against WEP protected networks.
Last updated:  2007-12-19
Bodo Möller, Andy Rupp
Show abstract
We consider the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements $g_2, ..., g_k$ are fixed while $g_1$ is variable between multi-exponentiations but may repeat, and where the exponents are bounded (e.g., in a finite group). We present a new technique that entails two different ways of computing such a result. The first way applies to the first occurrence of any $g_1$ where, besides obtaining the actual result, we create a cache entry based on $g_1$, investing very little memory or time overhead. The second way applies to any multi-exponentiation once such a cache entry exists for the $g_1$ in question: the cache entry provides for a significant speed-up. Our technique is useful for ECDSA or DSA signature verification with common domain parameters and recurring signers.
Last updated:  2007-12-19
Xun Yi, Raylin Tso, Eiji Okamoto
Show abstract
Password-authenticated key exchange (PAKE) protocols are designed to be secure even when the secret key used for authentication is a human-memorable password. In this paper, we consider PAKE protocols in the group scenario, in which a group of clients, each of them shares a password with an ``honest but curious'' server, intend to establish a common secret key (i.e., a group key) with the help of the server. In this setting, the key established is known to the clients only and no one else, including the server. Each client needs to remember passwords only while the server keeps passwords in addition to private keys related to his identity. Towards our goal, we present a compiler that transforms any group key exchange (KE) protocol secure against a passive eavesdropping to a group PAKE which is secure against an active adversary who controls all communication in the network. This compiler is built on any group KE protocol (e.g., the Burmester-Desmedt protocol), any identity-based encryption (IBE) scheme (e.g., Gentry's scheme), and any identity-based signature (IBS) scheme (e.g., Paterson-Schuldt scheme). It adds only two rounds and $O(1)$ communication (per client) to the original group KE protocol. As long as the underlying group KE protocol, IBE scheme and an IBS scheme have provably security without random oracles, a group PAKE constructed by our compiler can be proven to be secure without random oracles.
Last updated:  2008-12-04
Uncategorized
(withdrawn)
Xianhui Lu, Xuejia Lai, Dake He, Guomin Li
Last updated:  2009-10-24
Uncategorized
André Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, Salil Vadhan
Show abstract
We show that interactive and noninteractive zero-knowledge are equivalent in the `help model' of Ben-Or and Gutfreund ({\em J. Cryptology}, 2003). In this model, the shared reference string is generated by a probabilistic polynomial-time dealer who is given access to the statement to be proven. Our results do not rely on any unproven complexity assumptions and hold for statistical zero knowledge, for computational zero knowledge restricted to AM, and for quantum zero knowledge when the help is a pure quantum state.
Last updated:  2007-12-19
Uncategorized
Wei Wang, Xiaoyun Wang
Show abstract
This paper presents an improved impossible differential attack on the new block cipher CLEFIA which is proposed by Sony Corporation at FSE 2007. Combining some observations with new tricks, we can filter out the wrong keys more efficiently, and improve the impossible differential attack on 11-round CLEFIA-192/256, which also firstly works for CLEFIA-128. The complexity is about $2^{103.1}$ encryptions and $2^{103.1}$ chosen plaintexts. By putting more constraint conditions on plaintext pairs, we give the first attack on 12-round CLEFIA for all three key lengths with $2^{119.1}$ encryptions and $2^{119.1}$ chosen plaintexts. For CLEFIA-192/256, our attack is applicable to 13-round variant, of which the time complexity is about $2^{181}$, and the data complexity is $2^{120}$. We also extend our attack to 14-round CLEFIA-256, with about $2^{245.4}$ encryptions and $2^{120.4}$ chosen plaintexts. Moreover, a birthday sieve method is introduced to decrease the complexity of the core precomputation.
Last updated:  2008-03-06
Zheng Gong, Xuejia Lai, Kefei Chen
Show abstract
At ASIACRYPT 2006, Chang et al. analyzed the indifferentiability of some popular hash functions based on block ciphers, namely, the twenty collision resistant PGV, the MDC2 and the PBGV hash functions, etc. In particular, two indifferentiable attacks were presented on the four of the twenty collision resistant PGV and the PBGV hash functions with the prefix-free padding. In this article, a synthetic indifferentiability analysis of some block-cipher-based hash functions is considered. First, a more precise definition is proposed on the indifferentiability adversary in block-cipher-based hash functions. Next, the advantage of indifferentiability is separately analyzed by considering whether the hash function is keyed or not. Finally, a limitation is observed in Chang et al.'s indifferentiable attacks on the four PGV and the PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-free padding, the NMAC/HMAC and the chop construction.
Last updated:  2009-08-12
Uncategorized
Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, Tal Rabin
Show abstract
Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where {\em all} messages sent by the parties may be tampered with and modified by the adversary without the uncorrupted parties being able to detect this fact. In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees {\em can} be provided: Essentially, all the adversary can do is to partition the network into disjoint sets, where in each set the computation is secure in of itself, and also {\em independent} of the computation in the other sets. In this setting we provide, for the first time, non-trivial security guarantees in a model with {\em no setup assumptions whatsoever.} We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including password-based authenticated key exchange and non-malleable commitments. As an application of our results, we study the question of constructing secure protocols in partially-authenticated networks, where some of the links are authenticated and some are not (as is the case in most networks today).
Last updated:  2010-08-20
Gen Takahashi, Fumitaka Hoshino, Tetsutaro Kobayashi
Show abstract
The computation speed of pairing based cryptosystems is slow compared with the other public key cryptosystems even though several efficient computation algorithms have been proposed. Thus more efficient computation of the Tate pairing is an important research goal. GF(3m) multiplication in GF(36m) in the pairing algorithm is the greatest consumer of time. Past research concentrated on reducing the number of GF(3m) multiplications, for instance the Karatsuba method. In this article, we propose a new method to reduce the number of online precomputations( precomputations) in GF(3m) multiplications for the eta T pairing. The proposed algorithm reduces 18 online precomputations in GF(36m) in the eta T pairing to 4 online precomputations by reusing the intermediate products obtained in precomputation.We implement the proposed algorithm and compare the time taken by the proposed algorithm with that of the previous work. Our algorithm offers a 40% performance increase for GF(3m) multiplications in GF(36m) on an AMD 64-bit processor. Additionally, a completely new finding is obtained. The results show that the reducing the number of the multiplications in GF(36m) does not necessarily lead to a speed-up of the eta T pairing calculation.
Last updated:  2008-02-07
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.