BACK
Francais
PIPS
Perso
Poly
Publications
Swsusp
Tricks
ZEN

Publications

Reference Abstract ps pdf
Differential collisions in SHA-0,
F. Chabaud, and A. Joux,
extended abstract published in
CRYPTO'98, H. Krawczyk ed., LNCS 1462, pp 56--71, 1998.
In this paper we present a method for finding collisions in SHA-0 which is related to differential cryptanalysis of block ciphers. Using this method, we obtain a theoretical attack on the compression function SHA-0 with complexity 261, which is thus better than the birthday paradox attack. In the case of SHA-1, this method is unable to find collisions faster than the birthday paradox. This is a strong evidence that the transition to version 1 indeed raised the level of security of SHA. .PS .PDF
Contrôle d'intégrité de la séquence de démarrage d'un ordinateur,
F. Chabaud, and N. Cuillandre,
extended abstract published in
SECI'02, 2002.
The boot sequence of a computer begins at the power on of the machine and ends when the operationg system is completely charged. One can see this boot procedure as a sequence of steps that lead the computer from a shut down state to a usable state with an active operating system ready to execute the user applications.

This article presents an integrity control method of the end of the boot sequence. It has been developed on a mono-processor PC running Windows 95 and linux but can be generalized to all operating systems and can be adapted to other hardware.

   
Secured and Practical Voting Machines,
E. Bresson, F. Chabaud, X. Chassagneux, and M. Videau,
abstract published in
C&ESAR'08, 2008.
Voting machines are used in France in political elections since 2004. Other examples, notably in the USA, have raised a lot of concerns and some criticisms against their use. The purpose of this paper is to propose new conception rules for voting machines, in order to improve their security to achieve the sincerity of the ballot, to obtain transparency of the voting and counting procedures, so as to raise the confidence of citizens. One way to reach this final goal, is to give to the citizens the ability to participate into control operations, which is easier to do in paper voting than in the case of voting machines.    
Recherche de performance dans l'algorithmique des corps finis. Applications à la cryptographie.,
Thèse de doctorat, École Polytechnique, Oct. 1996.
(in french)

We present in this thesis ZEN, a programming library for computing in every finite extension over a finite ring. This library gives an easy and efficient way to implement such computations in C.

We then introduce some applications that were implemented using this library. These applications are related to the cryptanalysis of some cryptosystems based on error-correcting codes. Mainly, we present two algorithms for the general decoding of linear error-correcting codes, using Hamming's metric on one hand, and Gabidulin's rank metric on the other one.

We derive a few results

  • the true minimum distance of some BCH codes of length 511,
  • a bound on the minimum distance of linear codes using Gabidulin's metric,
  • the underestimation of some parameters in an identification scheme proposed by Véron,
  • a realist cryptanalysis of another identification scheme proposed by Chen.
We also note that, to our knowledge, our algorithms seems to be the best attacks against a large variety of cryptosystems including the well-known McEliece's, Niederreiter's and Stern's SD cryptosystems.

.PS .PDF

A new algorithm for finding minimum-weight words in a linear code: Application to primitive narrow-sense BCH codes of length 511.,
A. Canteaut, and F. Chabaud
published in
IEEE Trans. Inform. Theory, 44(1):367--378, jan 1998.

Preliminary version: Rapport de recherche 2685, INRIA, oct 1995.

An algorithm for finding small-weight words in large linear codes is developed. We determine with it the minimum distance of some binary BCH codes of length 511, which were not known.

Keywords: error-correcting codes, decoding algorithm, minimum weight, random linear codes, BCH codes

   
The cryptographic security of the syndrome decoding problem for rank distance codes,
F. Chabaud, and J. Stern,
extended abstract published in
Advances in Cryptology: ASIACRYPT '96, volume 1163 of LNCS, pages 368--381. Springer-Verlag, 1996.
An algorithm that achieves general syndrome decoding of linear rank distance code is proposed. As a consequence, the cryptographical schemes as proposed by K. Chen are not secure. We also derive a bound on the minimal rank distance of a linear code. .PS .PDF
On the security of some cryptosystems based on error-correcting codes,
F. Chabaud,
extended abstract published in
A. de Santis, editor, Advances in Cryptology: Proceedings of EUROCRYPT'94, volume 950 of LNCS, pages 131--139. Springer-Verlag, 1995.
A certain number of public-key cryptosystems based on error-correcting codes have been proposed as an alternative to algorithms based on number theory. In this paper, we analyze algorithms that can be used to attack such cryptosystems in a very precise way. .PS .PDF
Links between differential and linear cryptanalysis,
F. Chabaud, and S. Vaudenay,
extended abstract published in
A. de Santis, editor, Advances in Cryptology: Proceedings of EUROCRYPT'94, volume 950 of LNCS, pages 356--365. Springer-Verlag, 1995.
Preliminary version: Report LIENS-94-3
This paper exhibits new relations between linear and differential cryptanalysis and presents new classes of functions which are optimally resistant to these attacks.    
Asymptotic analysis of probabilistic algorithms for finding short codewords,
F. Chabaud,
extended abstract published in
In P. Camion, P. Charpin, and S. Harari, editors, EUROCODE'92, volume 339 of CISM Courses and Lectures, pages 175--183. Springer-Verlag, 1993.
We present the asymptotic analysis of two previously known algorithms for finding short codewords in linear binary codes. The results are confirmed by implementation, and this allows extrapolation for larger codes.    
BACK
Francais
PIPS
Perso
Poly
Publications
Swsusp
Tricks
ZEN

Florent Chabaud
E-mail: florent.chabaud@m4x.org
GPG key: KEY