Catálogo de publicaciones - libros

In this paper, we present new techniques for collision search in the hash function SHA-0. Using the new techniques, we can find collisions of the full 80-step SHA-0 with complexity less than 2^39 hash operations.

In this paper, we present new collision search attacks on the hash function SHA-1. We show that collisions of SHA-1 can be found with complexity less than 2^69 hash operations. This is the first attack on the full 80-step SHA-1 with complexity less than the 2^80 theoretical bound.

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed. We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.

We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of F $(\centerdot)$ and G $(\centerdot)$ is the function G ( F ( $\centerdot$ )), the parallel composition is F $(\centerdot) \bigstar$ G $(\centerdot)$ where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case. In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions F and G which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.

Using a recent idea of Gaudry and exploiting rational representations of algebraic tori, we present an index calculus type algorithm for solving the discrete logarithm problem that works directly in these groups. Using a prototype implementation, we obtain practical upper bounds for the difficulty of solving the DLP in the tori $T_2(\mathbb{F}_{p^m})$ and $T_6(\mathbb{F}_{p^m})$ for various p and m . Our results do not affect the security of the cryptosystems LUC, XTR, or CEILIDH over prime fields. However, the practical efficiency of our method against other methods needs further examining, for certain choices of p and m in regions of cryptographic interest.

In this paper we present a practical heuristic attack on the Ko, Lee et al. key exchange protocol introduced at Crypto 2000 [11]. Using this attack, we were able to break the protocol in about 150 minutes with over 95% success rate for typical parameters. One of the ideas behind our attack is using Dehornoy’s handle reduction method as a counter measure to diffusion provided by the Garside normal form, and as a tool for simplifying braid words. Another idea employed in our attack is solving the decomposition problem in a braid group rather than the conjugacy search problem .

Motivated by the security of the nonlinear filter generator, the concept of correlation was previously extended to the conditional correlation, that studied the linear correlation of the inputs conditioned on a given (short) output pattern of some specific nonlinear function. Based on the conditional correlations, conditional correlation attacks were shown to be successful and efficient against the nonlinear filter generator. In this paper, we further generalize the concept of conditional correlations by assigning it with a different meaning, i.e. the correlation of the output of an arbitrary function conditioned on the unknown (partial) input which is uniformly distributed. Based on this generalized conditional correlation, a general statistical model is studied for dedicated key-recovery distinguishers. It is shown that the generalized conditional correlation is no smaller than the unconditional correlation. Consequently, our distinguisher improves on the traditional one (in the worst case it degrades into the traditional one). In particular, the distinguisher may be successful even if no ordinary correlation exists. As an application, a conditional correlation attack is developed and optimized against Bluetooth two-level E0. The attack is based on a recently detected flaw in the resynchronization of E0, as well as the investigation of conditional correlations in the Finite State Machine (FSM) governing the keystream output of E0. Our best attack finds the original encryption key for two-level E0 using the first 24 bits of 2^23.8 frames and with 2^38 computations. This is clearly the fastest and only practical known-plaintext attack on Bluetooth encryption compared with all existing attacks. Current experiments confirm our analysis.

Non-interactive zero-knowledge (NIZK) proofs have been investigated in two models: the Public Parameter model and the Secret Parameter model . In the former, a public string is “ideally” chosen according to some efficiently samplable distribution and made available to both the Prover and Verifier. In the latter, the parties instead obtain correlated (possibly different) private strings. To add further choice, the definition of zero-knowledge in these settings can either be non-adaptive or adaptive . In this paper, we obtain several unconditional characterizations of computational, statistical and perfect NIZK for all combinations of these settings. Specifically, we show: In the secret parameter model, NIZK = NISZK = NIPZK = AM . In the public parameter model, – for the non-adaptive definition, NISZK ⊆ AM ∩ coAM , – for the adaptive one, it also holds that NISZK ⊂ BPP , – for computational NIZK for “hard” languages, one-way functions are both necessary and sufficient . From our last result, we arrive at the following unconditional characterization of computational NIZK in the public parameter model (which complements well-known results for interactive zero-knowledge): Either NIZK proofs exist only for “easy” languages (i.e., languages that are not hard-on-average), or they exist for all of AM (i.e., all languages which admit non-interactive proofs).

In this paper, we continue the study of the round complexity of black-box zero knowledge in the bare public-key ( BPK , for short) model previously started by Micali and Reyzin in [11]. Specifically we show the impossibility of 3-round concurrent (and thus resettable) black-box zero-knowledge argument systems with sequential soundness for non-trivial languages. In light of the previous state-of-the-art, our result completes the analysis of the round complexity of black-box zero knowledge in the BPK model with respect to the notions of soundness and black-box zero knowledge. Further we give sufficient conditions for the existence of a 3-round resettable zero-knowledge proof (in contrast to argument) system with concurrent soundness for $\mathcal{NP}$ in the upperbounded public-key model introduced in [14].

We show how to turn three-move proofs of knowledge into non-interactive ones in the random oracle model. Unlike the classical Fiat-Shamir transformation our solution supports an online extractor which outputs the witness from such a non-interactive proof instantaneously, without having to rewind or fork. Additionally, the communication complexity of our solution is significantly lower than for previous proofs with online extractors. We furthermore give a superlogarithmic lower bound on the number of hash function evaluations for such online extractable proofs, matching the number in our construction, and we also show how to enhance security of the group signature scheme suggested recently by Boneh, Boyen and Shacham with our construction.