Catálogo de publicaciones - libros

We analyze all the cases and propose the corresponding explicit formulae for computing 2 +  in one step from given divisor classes and on genus 2 hyperelliptic curves defined over prime fields. Compared with naive method, the improved formula can save two field multiplications and one field squaring each time when the arithmetic is performed in the most frequent case. Furthermore, we present a variant which trades one field inversion for fourteen field multiplications and two field squarings by using Montgomery’s trick to combine the two inversions. Experimental results show that our algorithms can save up to 13% of the time to perform a scalar multiplication on a general genus 2 hyperelliptic curve over a prime field, when compared with the best known general methods.

Efficient computation of the Tate pairing is an important part of pairing-based cryptography. Recently with the introduction of the Duursma-Lee method special attention has been given to the fields of characteristic 3. Especially multiplication in , where is prime, is an important operation in the above method. In this paper we propose a new method to reduce the number of -multiplications for multiplication in from 18 in recent implementations to 15. The method is based on the fast Fourier transform and its explicit formulas are given. The execution times of our software implementations for show the efficiency of our results.

In this paper we re-visit distinguishing attacks. We show how to generalize the notion of linear distinguisher to arbitrary sets. Our thesis is that our generalization is the most natural one. We compare it with the one by Granboulan et al. from FSE’06 by showing that we can get sharp estimates of the data complexity and cumulate characteristics in linear hulls. As a proof of concept, we propose a better attack on their toy cipher TOY100 than the one that was originally suggested and we propose the best known plaintext attack on SAFERK/SK so far. This provides new directions to block cipher cryptanalysis even in the binary case. On the constructive side, we introduce DEAN18, a toy cipher which encrypts blocks of 18 decimal digits and we study its security.

In this paper we analyze the previous attacks on the block cipher SHACAL-1 and show that all the differential-based attacks fail due to mistreatment of XOR differences through addition. We show that the previously published differential and rectangle attacks on SHACAL-1 fail as some of the underlying differentials are impossible. The related-key rectangle attacks on the cipher generally fail, but if some conditions are imposed on the key (i.e., for a weak key class) they work. After identifying the flaws in previous attacks, we present possible fixes to these attacks. We then present some modified differentials which lead to a related-key rectangle attack which can be applied to 2 weak keys. Our observations are then used to improve a related-key rectangle attack on IDEA by a factor of 2.

We show how to represent a non-linear equation over (2) using linear systems with multiple right hand sides. We argue that this representation is particularly useful for constructing equation systems describing ciphers using an S-box as the only means for non-linearity. Several techniques for solving systems of such equations were proposed in earlier work, and are also explained here. Results from experiments with DES are reported. Finally we use our representation to link a particular problem concerning vector spaces to the security of ciphers with S-boxes as the only non-linear operation.

Recent personal computers have high-spec CPUs and plenty of memory. The motivation of this study is to take these advantages in designing a tough and fast key-stream generator. Natural controversies on using a large state space for a generator are (1) effectiveness is unclear, (2) slower generation speed, (3) expensive initialization, and (4) costs in a hardware implementation.

Our proposal is to combine a linear feedback shift register (LFSR) and a uniform quasigroup filter with memory of wordsize. We prove theorems which assure the period and the distribution property of such generators, answering to (1). As for (2), the generation speed of a LFSR is independent of the state size. In addition, we propose a filter based on integer multiplication, which is rather fast in modern CPUs. We analyze the algebraic degree of such filters. We answer to (3) by a simple trick to use another small generator to initialize LFSR while outputting. We have no answer to (4), but comment that recent hardwares tend to have larger memory and sophisticated instructions.

As a concrete example, we propose CryptMT stream generator with period (no less than) 2− 1, 1241-dimensional equidistribution property, which is sometimes faster than SNOW2.0 in modern CPUs.

At DRM 2002, Chow  [4] presented a method for implementing the DES block cipher such that it becomes hard to extract the embedded secret key in a white-box attack context. In such a context, an attacker has full access to the implementation and its execution environment. In order to provide an extra level of security, an implementation shielded with external encodings was introduced by Chow and improved by Link and Neumann [10]. In this paper, we present an algorithm to extract the secret key from such white-box DES implementations. The cryptanalysis is a differential attack on obfuscated rounds, and works regardless of the shielding external encodings that are applied. The cryptanalysis has a average time complexity of 2 and a negligible space complexity.

Obfuscation is a method consisting in hiding information of some parts of a computer program. According to the Kerckhoffs principle, a cryptographical algorithm should be kept public while the whole security should rely on the secrecy of the key. In some contexts, source codes are publicly available, while the key should be kept secret; this is the challenge of code obfuscation. This paper deals with the cryptanalysis of such methods of obfuscation applied to the DES. Such methods, called the “naked-DES” and “nonstandard-DES”, were proposed by Chow [5] in 2002. Some methods for the cryptanalysis of the “naked-DES” were proposed by Chow [5], Jacob [6], and Link and Neuman [7]. In their paper, Link and Neuman [7] proposed another method for the obfuscation of the DES.

In this paper, we propose a general method that applies to all schemes. Moreover, we provide a theoretical analysis. We implemented our method with a C code and applied it successfully to thousands of obfuscated implementations of DES (both “naked” and “non-standard” DES). In each case, we recovered enough information to be able to invert the function.

The ESA-PSS-04-151 Authentication Layer of the European Space Agency is a MAC mechanism for authenticating telecommands transmitted to spacecrafts. We show that in spite of the very large key length of 2940 bits there are (under certain circumstances) feasible known message attacks. In particular, we show that an attacker who is given about  ≈80-100 message/MAC pairs and 60 special bits of the key can forge the MAC of any further message with high probability (> 5% for  = 100) by a single LLL lattice reduction modulo 2 of a matrix of size approximately ( − 60)×. Most of the 2880 remaining key bits can also be recovered. Furthermore, we show that the attacker can find the 60 special key bits as well if he is given, in addition, another set of about 40-50 message/MAC pairs of a special kind with a workload of less than 2 LLL lattice reductions modulo 2 of the same size.

The XCB mode of operation was outlined in 2004 as a contribution to the IEEE Security in Storage effort, but no security analysis was provided. In this paper, we provide a proof of security for XCB, and show that it is a secure tweakable (super) pseudorandom permutation. Our analysis makes several new contributions: it uses an algebraic property of XCB’s internal universal hash function to simplify the proof, and it defines a in which XCB can be securely used even when the plaintext is shorter than twice the width of the underlying block cipher. We also show minor modifications that improve the performance of XCB and make it easier to analyze. XCB is interesting because it is highly efficient in both hardware and software, it has no alignment restrictions on input lengths, it can be used in nonce mode, and it uses the internal functions of the Galois/Counter Mode (GCM) of operation, which facilitates design re-use and admits multi-purpose implementations.