Catálogo de publicaciones - libros

The need of true random number generators for many purposes (ranging from applications in cryptography and stochastic simulation, to search heuristics and game playing) is increasing every day. Many sources of randomness possess the property of stationarity. However, while a biased die may be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. In this paper, we present a new technique for simulating fair coin flips using a biased, stationary source of randomness. Moreover, the same technique can also be used to improve some of the properties of pseudo random number generators. In particular, an improved pseudo random number generator has almost unmeasurable period, uniform distribution of the letters, pairs of letters, triples of letters, and so on, and passes many statistical tests of randomness. Our algorithm for simulating fair coin flips using a biased, stationary source of randomness (or for improving the properties of pseudo random number generators) is designed by using quasigroup string transformations and its properties are mathematically provable. It is very flexible, the input/output strings can be of 2-bits letters, 4-bits letters, bytes, 2-bytes letters, and so on. It is of linear complexity and it needs less than 1Kb memory space in its 2-bits and 4-bits implementations, hence it is suitable for embedded systems as well.

In this paper we present a distinguisher targeting towards irregularly clocked filter generators. The attack is applied on the irregularly clocked stream cipher called LILI-II. LILI-II is the successor of the cipher LILI-128 and its design was published in [1]. There have been no known attacks better than exhaustive key search on LILI-II. Our attack is the first of this kind that distinguishes the cipher output from a random source using 2 bits of keystream using computational complexity of approximately 2 operations.

Algebraic attacks on stream ciphers apply (at least theoretically) to all LFSR-based stream ciphers that are clocked in a simple and/or easily predictable way. One interesting approach to help resist such attacks is to add a component that de-synchronizes the output bits of the cipher from the clock of the LFSR. The Bit-search generator, recently proposed by Gouget and Sibert, is inspired by the so-called Self-Shrinking Generator which is known for its simplicity (conception and implementation-wise) linked with some interesting properties. In this paper, we introduce two modified versions of the BSG, called MBSG and ABSG, and some of their properties are studied. We apply a range of cryptanalytic techniques in order to compare the security of the BSGs.

The bit-search generator (BSG) was proposed in 2004 and can be seen as a variant of the shrinking and self-shrinking generators. It has the advantage that it works at rate 1/3 using only one LFSR and some selection logic. We present various attacks on the BSG based on the fact that the output sequence can be uniquely defined by the differential of the input sequence. By knowing only a small part of the output sequence we can reconstruct the key with complexity (2). This complexity can be significantly reduced in a data/time tradeoff manner to achieve a complexity of (2) if we have (2) of keystream. We also propose a distinguishing attack that can be very efficient if the feedback polynomial is not carefully chosen.

This paper presents a new hash function design, which is different from the popular designs of the MD4-family. Seen in the light of recent attacks on MD4, MD5, SHA-0, SHA-1, and on RIPEMD, there is a need to consider other hash function design strategies. The paper presents also a concrete hash function design named SMASH. One version has a hash code of 256 bits and appears to be at least as fast as SHA-256.

In this paper, we propose a 2/3-rate double length compression function and study its security in the black-box model. We prove that to get a collision attack for the compression function requires Ω(2) queries, where is the single length output size. Thus, it has better security than a most secure single length compression function. This construction is more efficient than the construction given in [8]. Also the three computations of underlying compression functions can be done in parallel. The proof idea uses a concept of computable message which can be helpful to study security of other constructions like [8],[14],[16] etc.

This paper contains several attacks on the hash function MD2 which has a hash code size of 128 bits. At Asiacrypt 2004 Muller presents the first known preimage attack on MD2. The time complexity of the attack is about 2 and the preimages consist always of 128 blocks. We present a preimage attack of complexity about 2 with the further advantage that the preimages are of variable lengths. Moreover we are always able to find many preimages for one given hash value. Also we introduce many new collisions for the MD2 compression function, which lead to the first known (pseudo) collisions for the full MD2 (including the checksum), but where the initial values differ. Finally we present a pseudo preimage attack of complexity 2 but where the preimages can have any desired lengths.

We consider the 3GPP confidentiality and integrity schemes that were adopted by Universal Mobile Telecommunication System, an emerging standard for third generation wireless communications. The schemes, known as 8 and 9, are based on the block cipher KASUMI. Although previous works claim security proofs for 8 and 9′, where 9′ is a generalized version of 9, it was shown that these proofs are incorrect; it is to prove 8 and 9′ secure under the standard PRP assumption on the underlying block cipher. Following the results, it was shown that it is to prove 8′ and 9′ secure if we make the assumption that the underlying block cipher is a secure PRP-RKA against a certain class of related-key attacks; here 8′ is a generalized version of 8. Needless to say, the assumptions here are stronger than the standard PRP assumptions, and it is natural to seek a way to modify 8′ and 9′ to establish security proofs under the standard PRP assumption. In this paper, we propose 8 and 9, slightly modified versions of 8′ and 9′, but they allow proofs of security under the standard PRP assumption. Our results are practical in the sense that we insist on the minimal modifications; 8 is obtained from 8′ by setting the key modifier to all-zero, and 9 is obtained from 9′ by setting the key modifier to all-zero, and using the encryptions of two constants in the CBC MAC computation.

This paper introduces CCFB and CCFB+H, two patent-free authenticated encryption schemes. CCFB+H also supports the authentication of associated data. Our schemes can employ any block cipher and are provably secure under standard assumptions. The schemes and their proofs of security are simple and straightforward. CCFB and CCFB+H restrict the sizes of nonce and authentication tags and can, depending on these sizes, perform significantly better than both generic composition and other two-pass schemes for authenticated encryption, such as the EAX mode.

In [8], Paterson and Yau presented padding oracle attacks against a committee draft version of a revision of the ISO CBC-mode encryption standard [3]. Some of the attacks in [8] require knowledge and manipulation of the initialisation vector (IV). The latest draft of the revision of the standard [4] recommends the use of IVs that are secret and random. This obviates most of the attacks of [8]. In this paper we consider the security of CBC-mode encryption against padding oracle attacks in this secret, random IV setting. We present new attacks showing that several ISO padding methods are still weak in this situation.