Catálogo de publicaciones - libros

The most efficient collision attacks on members of the SHA family presented so far all use complex characteristics which were manually constructed by Wang et al . In this report, we describe a method to search for characteristics in an automatic way. This is particularly useful for multi-block attacks, and as a proof of concept, we give a two-block collision for 64-step SHA-1 based on a new characteristic. The highest number of steps for which a SHA-1 collision was published so far was 58. We also give a unified view on the expected work factor of a collision search and the needed degrees of freedom for the search, which facilitates optimization.

At CRYPTO2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed a collision attack on SHA-0 that could generate a collision with complexity 2^39 SHA-0 hash operations. Although the method of Wang et al. can find messages that satisfy the sufficient conditions in steps 1 to 20 by using message modification, it makes no mention of the message modifications needed to yield satisfaction of the sufficient conditions in steps 21 and onwards. In this paper, first, we give sufficient conditions for the steps from step 21, and propose submarine modification as the message modification technique that will ensure satisfaction of the sufficient conditions from steps 21 to 24. Submarine modification is an extension of the multi-message modification used in collision attacks on the MD-family. Next, we point out that the sufficient conditions given by Wang et al. are not enough to generate a collision with high probability; we rectify this shortfall by introducing two new sufficient conditions. The combination of our newly found sufficient conditions and submarine modification allows us to generate a collision with complexity 2^36 SHA-0 hash operations. At the end of this paper, we show the example of a collision generated by applying our proposals.

In this paper, we analyze the security of HMAC and NMAC, both of which are hash-based message authentication codes. We present distinguishing, forgery, and partial key recovery attacks on HMAC and NMAC using collisions of MD4, MD5, SHA-0, and reduced SHA-1. Our results demonstrate that the strength of a cryptographic scheme can be greatly weakened by the insecurity of the underlying hash function.

We propose a new type of guess-and-determine attack on the self-shrinking generator (SSG). The inherent flexibility of the new attack enables us to deal with different attack conditions and requirements smoothly. For the SSG with a length L LFSR of arbitrary form, our attack can reliably restore the initial state with time complexity O (2^0.556 L), memory complexity O ( L ^2) from O (2^0.161L)-bit keystream for L ≥100 and time complexity O (2^0.571 L), memory complexity O ( L ^2) from O (2^0.194 L)-bit keystream for L < 100. Therefore, our attack is better than all the previously known attacks on the SSG and especially, it compares favorably with the time/memory/data tradeoff attack which typically has time complexity O (2^0.5 L), memory complexity O (2^0.5 L) and data complexity O (2^0.25 L)-bit keystream after a pre-computation phase of complexity O (2^0.75 L). It is well-known that one of the open research problems in stream ciphers specified by the European STORK (Strategic Roadmap for Crypto) project is to find an attack on the self-shrinking generator with complexity lower than that of a generic time/memory/data tradeoff attack. Our result is the best answer to this problem known so far.

Stream ciphers play an important role in symmetric cryptology because of their suitability in high speed applications where block ciphers fall short. A large number of fast stream ciphers or pseudorandom bit generators (PRBG’s) can be found in the literature that are based on arrays and simple operations such as modular additions, rotations and memory accesses (e.g. RC4, RC4A, Py, Py6, ISAAC etc.). This paper investigates the security of array-based stream ciphers (or PRBG’s) against certain types of distinguishing attacks in a unified way. We argue, counter-intuitively, that the most useful characteristic of an array, namely, the association of array-elements with unique indices, may turn out to be the origins of distinguishing attacks if adequate caution is not maintained. In short, an adversary may attack a cipher simply exploiting the dependence of array-elements on the corresponding indices. Most importantly, the weaknesses are not eliminated even if the indices and the array-elements are made to follow uniform distributions separately. Exploiting these weaknesses we build distinguishing attacks with reasonable advantage on five recent stream ciphers (or PRBG’s), namely, Py6 (2005, Biham et al. ), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong et al. ) with data complexities 2^68.61, 2^32.89, 2^16.89, 2^32.89 and 2^32.89 respectively. In all the cases we worked under the assumption that the key-setup algorithms of the ciphers produced uniformly distributed internal states. We only investigated the mixing of bits in the keystream generation algorithms. In hindsight, we also observe that the previous attacks on the other array-based stream ciphers (e.g. Py, etc.), can also be explained in the general framework developed in this paper. We hope that our analyses will be useful in the evaluation of the security of stream ciphers based on arrays and modular addition.

In this paper, we study the construction of (2 t +1)-variable Boolean functions with maximum algebraic immunity, and we also analyze some other cryptographic properties of this kind of functions, such as nonlinearity, resilience. We first identify several classes of this kind of functions. Further, some necessary conditions of this kind of functions which also have higher nonlinearity are obtained. In this way, a modified construction method is proposed to possibly obtain (2 t +1)-variable Boolean functions which have maximum algebraic immunity and higher nonlinearity, and a class of such functions is also obtained. Finally, we present a sufficient and necessary condition of (2 t +1)-variable Boolean functions with maximum algebraic immunity which are also 1-resilient.

There have been active discussions on how to derive a consistent cryptographic key from noisy data such as biometric templates, with the help of some extra information called a sketch . It is desirable that the sketch reveals little information about the biometric templates even in the worst case (i.e., the entropy loss should be low). The main difficulty is that many biometric templates are represented as points in continuous domains with unknown distributions, whereas known results either work only in discrete domains, or lack rigorous analysis on the entropy loss. A general approach to handle points in continuous domains is to quantize (discretize) the points and apply a known sketch scheme in the discrete domain. However, it can be difficult to analyze the entropy loss due to quantization and to find the “optimal” quantizer. In this paper, instead of trying to solve these problems directly, we propose to examine the relative entropy loss of any given scheme, which bounds the number of additional bits we could have extracted if we used the optimal parameters. We give a general scheme and show that the relative entropy loss due to suboptimal discretization is at most ( n log3), where n is the number of points, and the bound is tight. We further illustrate how our scheme can be applied to real biometric data by giving a concrete scheme for face biometrics.

The complex multiplication (CM) method for genus 2 is currently the most efficient way of generating genus 2 hyperelliptic curves defined over large prime fields and suitable for cryptography. Since low class number might be seen as a potential threat, it is of interest to push the method as far as possible. We have thus designed a new algorithm for the construction of CM invariants of genus 2 curves, using 2-adic lifting of an input curve over a small finite field. This provides a numerically stable alternative to the complex analytic method in the first phase of the CM method for genus 2. As an example we compute an irreducible factor of the Igusa class polynomial system for the quartic CM field ℚ $(i\sqrt{75 + 12\sqrt{17}})$ , whose class number is 50. We also introduce a new representation to describe the CM curves: a set of polynomials in ( j _1, j _2, j _3) which vanish on the precise set of triples which are the Igusa invariants of curves whose Jacobians have CM by a prescribed field. The new representation provides a speedup in the second phase, which uses Mestre’s algorithm to construct a genus 2 Jacobian of prime order over a large prime field for use in cryptography.

It has been recently acknowledged [4,6,9] that the use of double bases representations of scalars n , that is an expression of the form n = ∑_ e , s , t (–1)^ e A ^ s B ^ t can speed up significantly scalar multiplication on those elliptic curves where multiplication by one base (say B ) is fast. This is the case in particular of Koblitz curves and supersingular curves, where scalar multiplication can now be achieved in o (log n ) curve additions. Previous literature dealt basically with supersingular curves (in characteristic 3, although the methods can be easily extended to arbitrary characteristic), where A , B ∈ℕ. Only [4] attempted to provide a similar method for Koblitz curves, where at least one base must be non-real, although their method does not seem practical for cryptographic sizes (it is only asymptotic), since the constants involved are too large. We provide here a unifying theory by proposing an alternate recoding algorithm which works in all cases with optimal constants. Furthermore, it can also solve the until now untreatable case where both A and B are non-real. The resulting scalar multiplication method is then compared to standard methods for Koblitz curves. It runs in less than log n /loglog n elliptic curve additions, and is faster than any given method with similar storage requirements already on the curve K-163, with larger improvements as the size of the curve increases, surpassing 50% with respect to the τ -NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require O (log( n )/loglog( n )) precomputations for optimal parameters, we offer the advantage of a fixed, small memory footprint, as we need storage for at most two additional points.

At Eurocrypt 2005, Waters presented an identity based encryption (IBE) protocol which is secure in the full model without random oracle. In this paper, we extend Waters’ IBE protocol to a hierarchical IBE (HIBE) protocol which is secure in the full model without random oracle. The only previous construction in the same setting is due to Waters. Our construction improves upon Waters’ HIBE by significantly reducing the number of public parameters.