Catálogo de publicaciones - libros

is a new stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like ’s, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast — it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size ≤ 256 bits.

SHACAL-1 is a 160-bit block cipher with variable key length of up to 512-bit key based on the hash function SHA-1. It was submitted to the NESSIE project and was accepted as a finalist for the 2nd phase of evaluation. Since its introduction, SHACAL-1 withstood extensive cryptanalytic efforts. The best known key recovery attack on the full cipher up to this paper has a time complexity of about 2 encryptions.

In this paper we use an observation due to Saarinen to present an elegant related-key attack on SHACAL-1. The attack can be mounted using two to eight unknown related keys, where each additional key reduces the time complexity of retrieving the actual values of the keys by a factor of 2. When all eight related-keys are used, the attack requires 2 related-key chosen plaintexts and has a running time of 2 encryptions. This is the first successful related-key key recovery attack on a cipher with varying round constants.

It is well-known that RSA signatures such as FDH, PSS or PSS-R are as secure as RSA is hard to invert in the random oracle (RO) model. Such proofs, however, have never been discovered in the standard model. This paper provides an explanation of this gap by pointing out a strong of equivalence between inverting RSA and any form of unforgeability for a wide class of RSA signatures. In particular, our impossibility results explicitly assume that the public key is made of a single RSA instance, that hash functions involved in the signature padding are unkeyed and that key generation fulfils a natural property which we call instance-non-malleability. Beyond showing that any RSA-based signature scheme of that type black-box separates the RO model from the standard model in a strong sense, our work leaves the real-life security of well-known signatures in a state of uncertainty.

We mathematically explore a model for the shortness and security for passwords that are stored in hashed form. The model is implicitly in the NIST publication [8] and is based on conditions of the Shannon, Guessing and Min Entropy. We establish various new relations between these three notions of entropy, providing strong improvements on existing bounds such as the McEliece-Yu bound from [7] and the Min entropy lowerbound on Shannon entropy [3]. As an application we present an algorithm generating near optimally short passwords given certain security restrictions. Such passwords are specifically applicable in the context of one time passwords (e.g. initial passwords, activation codes).

The task of developing protocols for humans to securely authenticate themselves to a remote server has been an interesting topic in cryptography as a replacement for the traditional, less secure, password based systems. The protocols proposed in literature are based on some underlying difficult mathematical problem, which are tuned so as to make them easily computable by humans. As a result these protocols are easily broken when desired to be efficiently executable. We present a Human Identification Protocol based on the ability of humans to efficiently process an image given a secret predicate. It is a challenge-response protocol in which a subset of images presented satisfies a secret predicate shared by the challenger and the user. We conjecture that it is hard to guess this secret predicate for adversaries, both humans and programs. It can be efficiently executed by humans with the knowledge of the secret which in turn is easily memorable and replaceable. We prove the security of the protocol separately for human adversaries and programs based on two separate assumptions and justify these assumptions with the help of an example implementation.

FORK-256 is a hash function presented at FSE 2006. Whereas SHA-like designs process messages in one stream, FORK-256 uses four parallel streams for hashing. In this article, we present the first cryptanalytic results on this design strategy. First, we study a linearized variant of FORK-256, and show several unusual properties of this linearized variant. We also explain why the linearized model can not be used to mount attacks similar to the recent attacks by Wang on SHA-like hash functions. Second, we show how collision attacks, exploiting the non-bijectiveness of the nonlinear functions of FORK-256, can be mounted on reduced variants of FORK-256. We show an efficient attack on FORK-256 reduced to 2 streams and present actual colliding pairs. We expect that our attack can also be extended to FORK-256 reduced to 3 streams. For the moment our approach does not appear to be applicable to the full FORK-256 hash function.

This article presents a rare case of a deterministic second preimage attack on a cryptographic hash function. Using the notion of controllable output differences, we show how to construct second preimages for the SMASH hash functions. If the given preimage contains at least  + 1 blocks, where is the output length of the hash function in bits, then the attack is deterministic and requires only to solve a set of linear equations. For shorter preimages, the attack is probabilistic.

A digital signature scheme that achieves an optimal bandwidth (generating signatures as short as possible) is called an optimal signature scheme. The previous optimal signature schemes all need the random permutations (or the ideal ciphers) with large block size as building blocks. However, the practical cipher with large block size such as Halevi and Rogaway’s CMC-mode should call the underlying secure block cipher with small block size many times each time. This makes the previous optimal signature schemes which use the large domain permutation (or the ideal cipher) less efficient in the real world, even if there exist the methods that can encipher the messages with larger domain. On the other hand, all the practical signature schemes are not optimal in bandwidth including PSS-R, FDH, DSA, etc. Hence, the problem on how to design a practical, efficient and optimal signature scheme remains open.

This paper uses two random oracles and an ideal cipher with a smaller block size to design an optimal padding for signature schemes. The ideal cipher in our scheme can be implemented with a truly real block cipher (e.g. AES). Therefore, we provide a perfect solution to the open problem. More precisely, we design a practical, efficient and optimal signature scheme. Particularly, in the case of RSA, the padding leads the signature scheme to achieve not only optimality in bandwidth but also a tight security.

In 2002, Micali and Rivest raised an open problem as to whether directed transitive signatures exist or not. In 2003, Hohenberger formalized the necessary mathematical criteria for generic directed transitive signature scheme, showing that the edge signatures in such a scheme form a special (and powerful) mathematical group, called Abelian trapdoor group with infeasible inversion, which is not known to exist. In this paper, we consider a directed graph whose transitive reduction is a directed tree, on which we propose a natural RSA-based directed transitive signature scheme . In this particular case, we have answered the open problem raised by Micali and Rivest. We have proved that , associated to a standard digital signature scheme, is transitively unforgeable under adaptive chosen-message attack if the RSA inversion problem over a cyclic group is hard and the standard digital signature is secure. Furthermore, has even better performance than -1 in certain circumstance.

Multi-signatures allow multiple signers to jointly authenticate a message using a single compact signature. Many applications however require the public keys of the signers to be sent along with the signature, partly defeating the effect of the compact signature. Since identity strings are likely to be much shorter than randomly generated public keys, the identity-based paradigm is particularly appealing for the case of multi-signatures. In this paper, we present and prove secure an identity-based multi-signature (IBMS) scheme based on RSA, which in particular does not rely on (the rather new and untested) assumptions related to bilinear maps. We define an appropriate security notion for interactive IBMS schemes and prove the security of our scheme under the one-wayness of RSA in the random oracle model.