Serge Vaudenay
----------------------------------------------------------------------------
[Image] FFT-Hash-II is not yet Collision-free
In Advances in Cryptology CRYPTO'92, Santa Barbara, California, U.S.A.,
Lecture Notes in Computer Science No. 740, pp 587-593, Springer-Verlag,
1993.
In this paper, we show that the FFT-Hash function proposed by Schnorr is not
collision free. Finding a collision requires about 2^24 computations of the
basic function of FFT. This can be done in few hours on a SUN4-workstation.
In fact, it is at most as strong as a one-way hash function which returns a
48 bits length value. Thus, we can invert the proposed FFT hash-function
with 2^48 basic computations. Some simple improvements of the FFT hash
function are also proposed to try to get rid of the weaknesses of FFT.
----------------------------------------------------------------------------
[Image] One-Time Identification with Low Memory
In Proceedings of EUROCODE'92, Udine, Italy, CISM Courses and lectures No.
339, pp. 217-228, Springer-Verlag, 1993.
In this paper, a practical cryptosystem based on an authentication tree is
described. It is an extension of Ralph Merkle's results. The security of the
system depends on assumptions on a one-way function. This cryptosystem
allows to make interactive proofs of knowledge using keys only once. Thus,
it can be used to prove one's identity or to sign some message. Moreover, we
can use it to achieve an electronic cash system. A very efficient
implementation can be done on a low-cost smart card. This cryptosystem is
thus an alternative to the zero-knowledge algorithms.
----------------------------------------------------------------------------
[Image] Attacks on the Birational Permutation Signature
Joint work with Don Coppersmith and Jacques Stern
In Advances in Cryptology CRYPTO'93, Santa Barbara, California, U.S.A.,
Lecture Notes in Computer Science No. 773, pp. 435-443, Springer-Verlag,
1994.
(Click here for the Journal version.)
Shamir presents a family of cryptographic signature schemes based on
birational permutations of the integers modulo a large integer N of unknown
factorization. These schemes are attractive because of the low computational
requirements, both for signature generation and signature verification.
However, the two schemes presented in Shamir's paper are weak. We show here
how to break the first scheme, by first reducing it algebraically to the
earlier Ong-Schnorr-Shamir signature scheme, and then applying the Pollard
solution to that scheme. We then show some attacks on the second scheme.
These attacks give ideas which can be applied to schemes in this general
family.
----------------------------------------------------------------------------
[Image] Links between differential and linear cryptanalysis
Joint work with Florent Chabaud
In Advances in Cryptology EUROCRYPT'94, Perugia, Italy, Lecture Notes in
Computer Science No. 950, pp. 356-365, Springer-Verlag, 1995.
Linear cryptanalysis, introduced last year by Matsui, will most certainly
open-up the way to new attack methods which may be made more efficient when
compared or combined with differential cryptanalysis. This paper exhibits
new relations between linear and differential cryptanalysis and presents new
classes of functions which are optimally resistant to these attacks. In
particular, we prove that linear-resistant functions, which generally
present Bent properties, are differential-resistant as well and thus,
present Perfect Nonlinear properties.
----------------------------------------------------------------------------
[Image] Parallel FFT-hashing
Joint work with Claus Schnorr
In Fast Software Encryption, Cambridge Security Workshop, United Kingdom,
Lecture Notes in Computer Science No. 809, pp 149-156, Springer-Verlag,
1994.
We propose two families of scalable hash functions for collision-resistant
hashing that are highly parallel and based on the generalized fast Fourier
transform (FFT). FFT-hashing is based on multipermutations. This is a basic
cryptographic primitive for perfect generation of diffusion and confusion
which generalizes the boxes of the classic FFT. The slower FFT-hash
functions iterate a compression function. For the faster FFT-hash fonctions
all rounds are alike with the same number of message words entering each
round.
----------------------------------------------------------------------------
[Image] Black box cryptanalysis of hash networks based on multipermutations
Joint work with Claus Schnorr
In Advances in Cryptology EUROCRYPT'94, Perugia, Italy, Lecture Notes in
Computer Science No. 950, pp. 47-57, Springer-Verlag, 1995.
Black box cryptanalysis applies to hash algorithms consisting of many small
boxes, connected by a known graph structure, so that the boxes can be
evaluated forward and backwards by given oracles. We study attacks that work
for any choice of the black boxes, i.e. we scrutinize the given graph
structure. For example we analyze the graph of the fast Fourier transform
(FFT). We present optimal black box inversions of FFT-compression functions
and black box constructions of collisions. This determines the minimal depth
of FFT-compression networks for collision-resistant hashing. We propose the
concept of multipermutation, which is a pair of orthogonal latin squares, as
a new cryptographic primitive that generalizes the boxes of the FFT. Our
examples of multipermutations are based on the operations circular rotation,
bitwise xor, addition and multiplication.
----------------------------------------------------------------------------
[Image] Complexity trade-offs with the Digital Signature Standard
Joint work with David M'Raihi, David Naccache and Dan Raphaeli
In Advances in Cryptology EUROCRYPT'94, Perugia, Italy, Lecture Notes in
Computer Science No. 950, pp. 77-85, Springer-Verlag, 1995.
The Digital Signature Algorithm (DSA) was proposed in 1991 by the US
National Institute of Standards and Technology to provide an appropriate
core for applications requiring digital signatures. Undoubtelly, many
applications will include this standard in the future and thus, the foreseen
domination of DSA as legal certification tool is sufficiently important to
focus research endeavours on the suitability of this scheme to various
situations. In this paper, we present six new DSA-based protocols for:
performing a quick batch-verification of n signatures; avoiding the
cumbersome calculation of 1/k mod q by the signer; compressing sets of DSA
transactions into shorter archive signatures; generating signatures from
pre-calculated "Use & Throw" 224-bit signature-coupons; self-certifying the
moduli and bit-patterning directly q on p. All our schemes combine in a
natural way full DSA compatibility and flexible trade-offs between
computational complexity, transmission overheads and key sizes.
----------------------------------------------------------------------------
[Image] On the need for multipermutations: Cryptanalysis of MD4 and SAFER
In Fast Software Encryption, Leuven, Belgium, Lecture Notes in Computer
Science No. 1008, pp. 286-297, Springer-Verlag, 1995.
Cryptographic primitives are usually based on a network with some gates. In
[SV94], it is claimed that all gates should be multipermutations. In this
paper, we investigate a few combinatorial properties of multipermutations.
We argue that gates which fail to be multipermutations can open the way to
unsuspected attacks. We illustrate this statement with two examples.
Firstly, we show how to construct collisions to MD4 restricted to its first
two rounds. This allows to forge digests close to each other using the full
compression function of MD4. Secondly, we show that some generalizations of
SAFER are subject to attack faster than exhaustive search in 6.1% cases.
This attack can be implemented if we decrease the number of rounds from 6 to
4.
----------------------------------------------------------------------------
[Image] The Security of Cryptographic Primitives
Thesis report. (Available in French only). Technical Report LIENS-95-10 of
the Laboratoire d'Informatique de l'Ecole Normale Supérieure, 1995.
In the early fifties, Claude Shannon initiated the theory of cryptographic
primitives. He defined the notion of diffusion and confusion. However, this
theory did not developed very much until nowadays. Recently, the
differential cryptanalysis and the linear cryptanalysis gave a significant
advance in the analysis of the primitives. Security criteria for confusion,
essentially nonlinearity criteria, has been proposed.
In this thesis, we show how to define a notion of complexity on the graph
structure of the primitives and how to study it. This gives security
criteria of the computational network. We propose new criteria for
diffusion. Finally, we unify the two types of cryptanalysis, getting rid of
their linear aspects by a statistical approach.
----------------------------------------------------------------------------
[Image] On the Weak Keys of Blowfish
In Fast Software Encryption, Cambridge, United Kingdom, Lecture Notes in
Computer Science No. 1039, pp. 27-32, Springer-Verlag, 1996.
Blowfish is a sixteen-rounds Feistel cipher in which the F function is a
part of the private key. In this paper, we show that the disclosure of F
allows to perform a differential cryptanalysis which can recover all the
rest of the key with 2^48 chosen plaintexts against a number of rounds
reduced to eight. Moreover, for some weak F function, this attack only needs
2^23 chosen plaintexts against eight rounds, and 3x2^51 chosen plaintexts
against sixteen-rounds. When the F function is safely kept private, one can
detect whether it is weak or not with a differential attack using 2^22
plaintexts against eight rounds.
----------------------------------------------------------------------------
[Image] Black Box Cryptanalysis of Cryptographic Primitives
Joint work with Claus Schnorr.
Submitted to the Journal of Cryptology.
We analyse the security of a cryptographic primitive on the basis of the
geometry of its computation graph. We assume the computation graph of the
primitive to be given whereas the boxes sitting on the vertices of this
graph are unknown and random, i.e. they are black boxes. We formalize and
study a family of attacks which generalize exhaustive search and the
birthday paradox. We establish complexity lower bounds for this family and
we apply it to compression functions based on the FFT network.
----------------------------------------------------------------------------
[Image] An Experiment on DES - Statistical Cryptanalysis
In the Proceedings of the 3rd ACM Conferences on Computer Security, New
Delhi, India, pp. 139-147, ACM Press, 1996. (The proceedings version is (c)
Copyright by the ACM 1995.)
Linear cryptanalysis and differential cryptanalysis are the most important
methods of attack against block ciphers. Their efficiency have been
demonstrated against several ciphers, including the Data Encryption
Standard. We prove that both of them can be considered, improved and joined
in a more general statistical framework. We also show that the very same
results as those obtained in the case of DES can be found without any linear
analysis and we slightly improve them into an attack with theoretical
complexity 2^42.9. We can apply another statistical attack - the
chi^2-cryptanalysis - on the same characteristics without a definite idea of
what happens in the encryption process. It appears to be roughly as
efficient as both differential and linear cryptanalysis. We propose a new
heuristic method to find good characteristics. It has found an attack
against DES absolutely equivalent to Matsui's one by following a distinct
path.
----------------------------------------------------------------------------
[Image] Authenticated Multi-Party Key Agreement
Joint work with Mike Just
In Advances in Cryptology ASIACRYPT'96, Kyongju, Korea, Lecture Notes in
Computer Science No. 1163, pp. 26-35, Springer-Verlag, 1996.
We examine multi-party key agreement protocols that provide (i) key
authentication, (ii) key confirmation and (iii) forward secrecy. Several
minor (repairable) attacks are presented against previous two-party key
agreement schemes and a model for key agreement is presented that provably
provi des the properties listed above. A generalization of the
Burmester-Desmedt model (Eurocrypt '94) for multi-party key agreement is
given, allowing a transformation of any two-party key agreement scheme into
a multi-party scheme. Multi-party schemes (based on the general model and
two specific two-party schem es) are presented that reduce the number of
rounds required for key computation compared to the specific
Burmester-Desmedt scheme. It is also shown how the specific
Burmester-Desmedt scheme fails to provide key authentication.
----------------------------------------------------------------------------
[Image] Cryptography Théorie et Pratique by Douglas Stinson
(c) Copyright by International Thomson Publishing France, 1996
French translation of:
Cryptography Theory and Practice
(c) Copyright by CRC Press, Inc., 1995
----------------------------------------------------------------------------
[Image] Hidden Collisions on DSS
In Advances in Cryptology CRYPTO'96, Santa-Barbara, California, U.S.A,
Lecture Notes in Computer Science No. 1109, pp. 83--88 Springer-Verlag,
1996.
We explain how to forge public parameters for the Digital Signature Standard
with two known messages which always produce the same set of valid
signatures (what we call a collision). This attack is thwarted by using the
generation algorithm suggested in the specifications of the Standard, so it
proves one always need to check proper generation. We also present a similar
attack when using this generation algorithm within a complexity 2^74, which
is better than the birthday attack which seeks for collisions on the
underlying hash function.
----------------------------------------------------------------------------
[Image] Minding your p's and q's
Joint work with Ross Anderson
In Advances in Cryptology ASIACRYPT'96, Kyongju, Korea, Lecture Notes in
Computer Science No. 1163, pp. 26-35, Springer-Verlag, 1996.
Over the last year or two, a large number of attacks have been found by the
authors and others on protocols based on the discrete logarithm problem,
such as ElGamal signature and Diffie Hellman key exchange. These attacks
depend on causing variables to assume values whose discrete logarithms can
be calculated, whether by forcing a protocol exchange into a smooth subgroup
or by choosing degenerate values directly. We survey these attacks and
discuss how to build systems that are robust against them. In the process we
elucidate a number of the design decisions behind the US Digital Signature
Standard.
----------------------------------------------------------------------------
[Image] On Provable Security for Digital Signature Algorithms
Joint work with David Pointcheval
In this paper we consider provable security for ElGamal-like digital
signature schemes. We point out that the good the security criterion on the
underlying hash function is pseudorandomness. We extend Pointcheval-Stern's
results about the use of the random oracle model to prove the security of
two variants of the US Digital Signature Algorithm against adaptive attacks
which issue an existential forgery. We prove that a very practical use of
the random oracle model is possible whith tamper-resistant modules.
----------------------------------------------------------------------------
Serge Vaudenay
----------------------------------------------------------------------------