Catálogo de publicaciones - libros

In this paper, we present some reduced complexity attacks on the Alternating Step Generator (ASG). The attacks are based on a quite general framework and mostly benefit from the low sampling resistance of the ASG, and of an abnormal behavior related to the distribution of the initial states of the stop/go LFSR’s which produce a given segment of the output sequence. Our results compare well with previous results as they show a greater flexibility with regard to known output of the ASG, which amounts in reduced complexity. We will also give a closed form for the complexity of attacks on ASG (and SG) as presented in [13].

The main application of stream ciphers is online-encryption of arbitrarily long data. Many practically used and intensively discussed stream ciphers consist of a small number of linear feedback shift registers (LFSRs) and a compression function that transforms the bitstreams produced by the LFSRs into the output keystream. In 2002, Krause proposed a Binary Decision Diagram (BDD) based attack on this type of ciphers, which ranges among the best generic short-keystream attacks on practically used ciphers such as the A5/1 generator used in GSM and the generator from the Bluetooth standard. In this paper we show how to extend the BDD-technique to nonlinear feedback shift registers (NFSRs), feedback shift registers with carry (FCSRs), and arbitrary compression functions. We apply our findings to the eSTREAM focus ciphers , Grain and F-FCSR. In the case of Grain, we obtain the first nontrivial cryptanalytic result besides generic time-memory-data tradeoffs.

is a stream cipher designed in 2005 by C. De Cannière and B. Preneel for the European project eSTREAM. It has an internal state of 288 bits and the key of length 80 bits. Although the design has a simple and elegant structure, no attack on it has been found yet.

In this paper a family of -like designs is studied. We propose a set of techniques for methodological cryptanalysis of these structures in general, including state recovering and linear distinguishing attacks. In particular, we study the original and present a state recovering attack with time complexity around 2, which is 2 faster than the best previous result. Our attack clearly shows that has a very thin safety margin and that in its current form it can not be used with longer 128-bit keys.

Finally, we identify interesting open problems and propose a new design , which resists all of our attacks proposed in this paper. It also accepts a 128 bit secret key due to the improved security level.

The diversity of methods for fast collision search in SHA-1 and similar hash functions makes a comparison of them difficult. The literature is at times very vague on this issue, which makes comparison even harder. In situations where differences in estimates of attack complexity of a small factor might influence short-term recommendations of standardization bodies, uncertainties and ambiguities in the literature amounting to a similar order of magnitude are unhelpful. We survey different techniques and propose a simple but effective method to facilitate comparison. In a case study, we consider a newly developed attack on 70-step SHA-1, and give complexity estimates and performance measurements of this new and improved collision search method.

Iterated Halving has been suggested as a replacement to the Merkle-Damgård construction following attacks on the MDx family of hash functions. The core of the scheme is an iterated block cipher that provides keying and input material for future rounds. The CRUSH hash function provides a specific instantiation of the block cipher for Iterated Halving. In this paper, we identify structural problems with the scheme, and show that by using a bijective function, such as the block cipher used in CRUSH or the AES, we can trivially identify collisions and second preimages on many equal-length messages of length ten blocks or more. The cost is ten decryptions of the block cipher, this being less than the generation of a single digest. We show that even if Iterated Halving is repaired, the construction has practical issues that means it is not suitable for general deployment. We conclude this paper with the somewhat obvious statement that CRUSH, and more generally Iterated Halving, should not be used.

Side-channel collision attacks were proposed in [1] and applied to AES in [2]. These are based on detecting collisions in certain positions of the internal state after the first AES round for different executions of the algorithm. The attack needs about 40 measurements and 512 MB precomputed values as well as requires the chosen-plaintext possibility.

In this paper we show how to mount a collision attack on AES using only 6 measurements and about 2 offline computational steps working with a probability of about 0.85. Another attack uses only 7 measurements and finds the full encryption key with an offline complexity of about 2 with a probability of 0.99. All our attacks require a negligible amount of memory only and work in the known-plaintext model. This becomes possible by considering collisions in the S-box layers both for different AES executions and within the same AES run. All the attacks work under the assumption that one-byte collisions are detectable.

Cache based attacks (CBA) exploit the different access times of main memory and cache memory to determine information about internal states of cryptographic algorithms. CBAs turn out to be very powerful attacks even in practice. In this paper we present a general and strong model to analyze the security against CBAs. We introduce the notions of and to analyze the security of several implementations of AES. Furthermore, we analyze how to use random permutations to protect against CBAs. By providing a successful attack on an AES implementation protected by random permutations we show that random permutations used in a straightforward manner are not enough to protect against CBAs. Hence, to improve upon the security provided by random permutations, we describe the property a permutation must have in order to prevent the leakage of some key bits through CBAs.

Power Analysis has been deeply studied since 1998 in order to improve the security of tamper resistant products such as Trusted Platform Module (TPM). The study has evolved from initial basic techniques like simple and differential power analysis to more complex models such as correlation. However, works on correlation techniques have essentially been focused on symmetric cryptography. We analyze here the interests of this technique when applied to different smartcard coprocessors dedicated to asymmetric cryptography implementations. This study leads us to discover and realize new attacks on RSA and ECC type algorithms with fewer curves than classical attacks. We also present how correlation analysis is a powerful tool to reverse engineer asymmetric implementations.

Scalar multiplication on Koblitz curves can be very efficient due to the elimination of point doublings. Modular reduction of scalars is commonly performed to reduce the length of expansions, and -adic Non-Adjacent Form (NAF) can be used to reduce the density. However, such modular reduction can be costly. An alternative to this approach is to use a random -adic NAF, but some cryptosystems (e.g. ECDSA) require both the integer and the scalar multiple. This paper presents an efficient method for computing integer equivalents of random -adic expansions. The hardware implications are explored, and an efficient hardware implementation is presented. The results suggest significant computational efficiency gains over previously documented methods.

We discuss a family of irreducible polynomials that can be used to speed up square root extraction in fields of characteristic two. They generalize trinomials discussed by Fong et al. [20]. We call such polynomials .

The main application is to point halving methods for elliptic curves (and to a lesser extent also divisor halving methods for hyperelliptic curves and pairing computations).

We note the existence of square root friendly trinomials of a given degree when we already know that an irreducible trinomial of the same degree exists, and formulate a conjecture on the degrees of the terms of square root friendly polynomials. Following similar results by Bluher, we also give a partial result that goes in the direction of the conjecture.

We also discuss how to improve the speed of solving quadratic equations. The increase in the time required to perform modular reduction is marginal and does not affect performance adversely. Estimates confirm that the new polynomials mantain their promises. Point halving gets a speed-up of 20% and scalar multiplication is improved by at least 11%.