Journées Codage et Cryptographie 2009

Journées Codage et Cryptographie 2009

-

Documents
55 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

  • exposé - matière potentielle : en deux parties
  • exposé
  • exposé - matière potentielle : courts
  • exposé - matière potentielle : longs
Journées Codage et Cryptographie 2009 Du 4 au 9 Octobre 2009 Présentation L'objet de ces journées nationales est de réunir la communauté scientifique française s'impliquant dans le codage, la cryptographie, et plus généralement la théorie de l'information. Ces journées sont organisées par le groupe de travail C2 (Codage et Cryptographie) du GDR IM (Informatique Mathématique) . Dates et lieu • Du dimanche 4 Octobre au vendredi 9 Octobre 2009.
  • candidate hashing algorithm
  • h25 complexité en données
  • h45 amélioration de la probabilité
  • teurs candidats
  • sha
  • pause
  • collision
  • collisions
  • h20
  • complexité
  • h45

Sujets

Informations

Publié par
Nombre de lectures 40
Langue Français
Signaler un problème

Journées "Codage et Cryptographie" 2009
Du 4 au 9 Octobre 2009

Présentation
L'objet de ces journées nationales est de réunir la communauté scientifique française
s'impliquant dans le codage, la cryptographie, et plus généralement la théorie de l'information.
Ces journées sont organisées par le groupe de travail C2 (Codage et Cryptographie) du GDR
IM (Informatique Mathématique) .
Dates et lieu
• Du dimanche 4 Octobre au vendredi 9 Octobre 2009.
• Au village de vacances Villa Clythia (CAES CNRS) à Fréjus.
• Des navettes assureront la liaison entre la gare TGV de St Raphaël Valescure et la
villa.
o Dimanche 4 Octobre : départ de la gare de St Raphaël à 19h.
o Vendredi 9 Octobre : retour depuis la villa à 13h45.
Déroulement
Le programme comporte à la fois des exposés courts sur des sujets pointus, et des exposés
longs plus généralistes, effectués par des chercheurs confirmés. Les doctorants sont vivement
encouragés à soumettre des propositions d'exposés.
Thématiques
Codes, cryptologie et sécurité de l'information.
Organisateurs
Luk Bettale, Jean-Charles Faugère, Ludovic Perret, Guénaël Renault

Lundi 5
Octobre
Exposé invité : Rehashing Cryptographic
9h00-10h00 B. Preneel
Hash Functions: the SHA-3 Competition
10h00-
Attaques par Collision contre SHA-1 S. Manuel
10h25
Pause

J.-P. Aumasson, Y. Laigle-
10h55- Cryptanalyse de la fonction de hachage Chapuy, G. Leurent, W. Meier,
11h20 ESSENCE M. Naya Plasencia, T. Peyrin
et A. Röck
11h20- Approximating addition by XOR: how to
D. Alquié
11h45 go (a little) further than P. Sarkar
11h45- Algebraic-Differential Cryptanalysis of
P.-J. Spaenlehauer
12h10 DES
Pause

16h00-
Exposé invité : Hachage et multicollisions A. Joux
17h00
17h00- Complexité en données et probabilité de
C. Blondeau et B. Gerard
17h25 succès des cryptanalyses statistiques
Pause

17h55-
Nouvelle approche des automates FCSR B. Pousse
18h20
18h20- Solving Multivariate Polynomial Systems
L. Bettale
18h45 over big Finite Fields
18h45- Etude du generateur d'alea du noyau A. Röck, V. Strubely et M.
19h10 Linux Videau
Mardi 6 Octobre
Exposé invité : Codes et graphes
9h00-10h00 G. Zémor
extenseurs 10h00-
On linear error-block codes R. Dariti et El M. Souidi
10h25
Pause

Recherche efficace des racines de
10h55-
polynômes dans les corps de V. Herbert
11h20
caractéristique 2
Amélioration de la probabilité de tricher
11h20- C. Aguilar, P. Gaborit, F.
de 2/3 à 1/2 pour le schéma
11h45 Laguillaumie et A. Otmani
d'authentification de Stern
11h45- Signatures de cercle à seuil prouvees
L. Dallot et D. Vergnaud
12h10 sûres
Pause

Discussion ouverte à tous sur le GDR IM
14h-15h55 C. Carlet
et le groupe de travail C2
15h55-
Cryptographie en métrique rang P. Loidreau
16h30
16h30- Codes sur des anneaux de Öre à plusieurs
L. Chaussade
16h55 variables
16h55- Un protocole de signatures de groupe à
O. Blazy
17h20 seuil tracables
Pause

17h50-
Efficient Anonymous Proxy Signatures G. Fuchsbauer
18h15
18h15-
Signatures Déléguées et Application A. Jambert
18h40
18h40- Condentialité et intégrité des grandes
Y. Guo et S. Jacob
19h05 bases de données
Mercredi 7 Octobre
Exposé invité : Extracting Sensitive
9h00-10h00 Information from Leakage Measurements E. Prouff
in Various Contexts 10h00- Multi-Linear cryptanalysis in Power
T. Roche et C. Tavernier
10h25 Analysis MLPA
Pause

10h55- Information Leakage From Public Key A. Berzati, C. Canovas, J.-G.
11h20 Perturbation Dumas et L. Goubin
11h20- Etude des notions d'immunité algébrique
B. Merabet
11h45 des fonctions vectorielles
11h45- Nonlinéarité d'une classe de fonctions
Z. Jadda et P. Parraud
12h10 quaternaires
Sécurité des Calculs Distribués Multi-
12h10-
parties, Application : Sécuriser le Calcul B. Ait-salem
12h35
Distribué des Confiances
Jeudi 8 Octobre
Exposé invité : Construction et utilisation
9h00-10h00 de codes pour le canal à effacement de J. Lacan
paquets
10h00- Décodage EM du code de Tardos pour le A. Charpentier, C. Fontaine et
10h25 fingerprinting T. Furon
Pause

10h55- M. Marazin, R. Gautier et G.
Reconnaissance aveugle de turbocodes
11h20 Burel
11h20-
Stego-Codes de Reed-Muller H. Jouhari et El M. Souidi
11h45
11h45- Codes quasi-cycliques sur des anneaux de
C. Chabot
12h10 matrices
Pause

Exposé invité : Utilisation des bases de
16h00- Gröbner dans les méthodes de
A. Bauer
Coppersmith pour la recherche de petites 17h00
racines de polynômes
17h00- Implicit Factoring with Shared Most J.-C. Faugère, R. Marinier et G.
17h25 Significant Bits Renault Pause

17h55- Distribution de la non-linéarité des
S. Dib
18h20 fonctions booléennes
18h20- C. Bouillaguet, P.-A. Fouque,
Problèmes d'Isomorphisme de Polynômes
18h45 J.-C. Faugère et L. Perret
18h45- SAT Solvers in the Context of Stream
M. Soos
19h10 Ciphers
Vendredi 9 Octobre
Exposé invité : Quelques applications des
9h00-10h00 fonctions thêta en arithmétique et en D. Lubicz
cryptographie
10h00- Atomicity Improvement for Elliptic Curve
V. Verneuil et C. Giraud
10h25 Scalar Multiplication
Pause

10h55- F. Herbaut, N. Meloni et P.
Chaînes d'addition et logarithme discret
11h20 Veron
11h20- Générateur Pseudo-Aléatoire À Base De
A. Landolsi et B. Martin
11h45 Courbes Elliptiques
Une amélioration des bornes de la
11h45-
complexité bilinéaire de la multiplication J. Pieltant
12h10
dans les corps finis
Rehashing Cryptographic Hash Functions:
?The SHA-3 Competition
Bart Preneel
Katholieke Universiteit Leuven and IBBT
Dept. Electrical Engineering-ESAT/COSIC,
Kasteelpark Arenberg 10 Bus 2446, B-3001 Leuven, Belgium
bart.preneel@esat.kuleuven.be
Cryptographic hash functions play a central role in applications of cryptog-
raphy. In spite of this, there has been only limited interest for theoretical work
on the de nitions and foundations. Until recently, there were about hundred
practical designs, of which more than three quarter are broken, and the most
widely used hash functions were MD5 and SHA-1. Cryptanalysis during the
1990s showed that these functions o ered only a very limited security margin,
and in 2004 Wang et al. managed to enhance di erential cryptanalysis to a point
that nding collisions for MD5 became very easy; for SHA-1 a substantial reduc-
tion of the security margin was obtained. This breakthrough has resulted in a
urry of research, resulting in both more theoretical research and new construc-
tions. NIST has announced in November 2007 that it would organize the SHA-3
competition [3], with as goal to select a new hash function family by 2012. On
October 31, 2008, 64 submissions were received, 51 of which have been selected
for the rst round; on July 24, 2009 NIST announced that 14 hash functions were
selected for the second round, namely: BLAKE, Blue Midnight Wish, CubeHash,
ECHO, Fugue, Gr stl, Hamsi, JH, Keccak, Lu a, Shabal, SHAvite-3, SIMD, and
Skein. An overview of security and performance results on the candidates can
be found at [2] and [1] respectively.
This talk presents a brief outline of the state of the art of hash functions at
the beginning of the second round of the SHA-3 competition and tries to clarify
the context in which this competition is developing.
References
1. eBASH, ECRYPT Benchmarking of All Submitted Hashes, http://bench.cr.yp.
to/ebash.html
2. ECRYPT II, The SHA-3 Zoo, http://ehash.iaik.tugraz.at/wiki/The_SHA-3_
Zoo.
3. NIST SHA-3 Competition, http://csrc.nist.gov/groups/ST/hash/.
? Supported in part by the IAP Programme P6/26 BCRYPT of the Belgian State
(Belgian Science Policy) and by the European Commission through the IST
Programme under contract number ICT-2007-216676 ECRYPT II.e
la
non
des
osons
nouv
2005
le
rev
r
b
on
teurs
ur
la
hag
collision
la
oie
fonction
caractéristique
et
1
Joux
h
[ePrin
une
t
rev
toine
l
al.
ecteurs.
longueur
deux
de
t
e
tèren
ne
une
fonction
a
rec
l'ob
dénommé
.
herc
hib
doit
s
algo
in
SHA-1.
collision
l'ob
eau
ion
h
par
x
on
quan
leur
o
deux
à
rec
é
la
tro
faire
cquencourt
t
hes
La
par
à
e
par
r
ang
rep
décriv
1993,
c
une
de
uel
de
tec
o
fonction
at-
messages.
o
de
complexité
la
2007,
rapidemen
YPT'06,
ecteurs
collisions
ge
SHA-1
ecaces.
70
v
P
our
la
érier
pro
v
tours.
cryptanalyses
prop
[W
p
une
diéren
SHA-1
aux
l
et
al.
bre
une
d'év
ce
Cha
complexité
l'ecacité
des
haîne
un
cet
partie
Puis
nouv
ang
v
caractères
e
YPTO'05]
p
don
con
t
l'état
Stéphane
térature
appro
seulemen
aux
diéren
tec
de
arbitraire
SHA-1
Le
t
seconde
comme
attaques
NIST.
uel@inria.fr
YPTO'05],
tre
al.
collision.
un
sur
n
n
attaque
tique
ision
NIST
ersion
qu
a
con
une
et
e
standard
u
d'optimisation
de
emprein
compression.
he
a
hac
d'une
construction
non
hac
t
passe
tr
qui
2006
e
Ca
xée.
[ASIA
de
C'07]
remplacé
t
p
o
e
ersions
t
uit
par
64
nouv
An
plus
t
ithme
[CR
te
duisiren
rec
hnique
prend
omerangs
de
t
début
our
a
Man
c
2008]
d'une
un
SHA
ecteur
Cet
p
conduire
un
par
remon
tr
des
v
n
théorique
existan
de
v
McDonald
comme
t
une
exhib
ne
ique
Floren
p
p
ecteur
p
ndiqué
ie
ou
et
de
v
Nous
P
our
L'utilisation
osé
[CR
La
a
tro
é
u
W
algorithme
t
he
et
t
aris-Ro
de
[CR
turbations
s
elle
in
ces
de
seconde
duisiren
istera
t
bilan
de
dans
Collision
lit
elles
fonction
résistance
à
c
t
nie
classes
et
tes.
attaques
fonction
hniques
hac
stephane.man
e
cryptanalyse.
est
préimage,
présen
princip
ociellemen
et
considérée
des
cassée
préimage
le
par
En
Man
[CR
con
W
t
et
SHA-1
présen
e
t
ose
article
En
a
u
t
Une
première
caractéris-
par
le
oll
linéaire,
sur
v
v
caractéristi
complète
publia
SHA-1,
e
v
aques
c
linéaire
complexité
premier
la
des
év
une
l
hniques
ati
de
ns
de
la
de
de
herc
Cette
de
taque
de
fait
te
jet
La
améliorati
hage
n
d'une
publiée
Équip
endiquan
linéaire
une
SHA-0,
de
par
con
taille
En
r
puis
fut
De
c
nnière
ha
al.
he
CR
t
SA
v
ex-
Elle
èren
de
des
en
p
e
ur
t
v
turba
de
995
réd
ions
e
de
à
Un
et
une
tours.
el
toine
cryptographique
e
r
Thomas
arian
eyrin
p
YPTO'07]
v
tro
la
t
baptisée
tec
herc
des
SECRET
o
e
et
Le
duisiren
ces
une
un
p
ecteurs
70
des
Stéphane
fait
uel
comme
t
jet
a
de
osé
publication
nouv
ert
v
CC'09].
de
-0
erturbations
algorithme
ouv
t
ise
à
SHA-1
attaque
compromis
collis
i
con
t
e
te
a
algorit
ec
t
complexité
mes
de
tra
'ordre
ts
collision
nom
.
prend
et
au
[ePrin
argumen
2009]
CRI
t
u
é
de
caractérist
fonction
n
de
linéaire
aluation
our
t
v
our
et
c
e
t
une
baud
p
r
r
r
attaque
des
attaques
An
.
ec-
prop
SHA-1
p
candidats.
C2
Joux
exp
de
en
pri
parties.
algorithme
première
YPTO'98].
in
conduit
duira
de
e
el
tt
par
re
-
argumen
a
et
util
an
ne
de
classication
herc
des
de
v
ec
ecteurs
e
de
s
p
p
erturbations
r
et
et
a
nouv
p
classication
ermis
our
de
v
mon
La
trer
partie
que
s
les
à
v
un
ecteurs
de
présen
actuel
ts
SHA-1.
appartiennen
A
692
632
512
522Cryptanalyse de la fonction de hachage
ESSENCE
y zMar a Naya-Plasencia , Andrea R ock . Jean-Philippe Aumasson,
x zYann Laigle-Chapuy, Gaetan Leurent, Willi Meier,
{et Thomas Peyrin
Journees \Codage et Cryptographie" 2009
ESSENCE [1, 2] est un candidat au concours du NIST pour designer un
nouveau standard de fonction de hachage [3]. Ce concours a re cu 64 soumissions
dont 51 ont ete acceptees au premier tour, notamment ESSENCE. ESSENCE
a ete developpee pour une implementation e cace en hardware et est facile a
paralleliser. Elle utilise du hachage en arbre et a deux instances principales,
travaillant sur des mots de 32 bits et 64 bits respectivement : ESSENCE-256 et
ESSENCE-512.
Nous presentons une attaque par collision sur la version complete d’ES-
67:4 134:7SENCE qui a une complexite de 2 et 2 respectivement pour les deux
versions ESSENCE-256 et ESSENCE-512. Dans un premier temps, cette at-
taque cherche une paire de messages qui satisfait un chemin di erentiel. Cette
62:2 116:1partie a une complexite de 2 et 2 respectivement pour ESSENCE-256 et
ESSENCE-512. Ensuite, nous testons plusieurs valeurs de cha^ nage pour trouver
une collision. La deuxieme partie est la partie la plus couteuse^ dans l’attaque.
Une recherche na ve d’une paire de messages satisfaisant le chemin di erentiel a
une complexite plus grande que le paradoxe des anniversaires. Pour diminuer le
cout,^ nous calculons au debut un ensemble de paires de messages qui veri ent
9 des 32 tours du chemin di erentiel. Apres quoi, nous veri ons le reste du che-
min. Cette demarche nous permet de reduire la complexite bien en dessous de
la complexite du paradoxe des anniversaires.
References
[1] J. W. Martin. ESSENCE : A candidate hashing algorithm for the NIST
competition. Submission to NIST, 2008.
[2] J. W. Martin. ESSENCE : A family of cryptographic hashing algorithms.
Submission to NIST, 2008.
INRIA project-team SECRET, France
yHelsinki University of Technology, Department of Information and Computer Science,
Finland.
zFHNW, Windisch, Switzerland
x Ecole Normale Superieure, Paris, France
{Ingenico, France
1[3] National Institute of Standards and Technology (NIST). Cryptographic hash
algorithm competition. http://csrc.nist.gov/groups/ST/hash/sha-3/
index.html.
2Approximating addition by XOR: how to go (a
little) further than P. Sarkar
Didier Alqui´e
DGA, CELAR
didier.alquie@laposte.net
July 7, 2009
Cryptographic algorithm designers are particularly interested in non linear
function that are easy to compute. Arithmetic addition is a good candidate
for them. For example its algebraic degree grows rapidly with respect to the
bits of inputs. Famous algorithms, such as SHA-1 or SHA-2 involve arithmetic
addition of more than 2 terms (up to 7 terms actually).
General analysis of hash functions use approximation of addition by XOR,
setting that the probability that both results are equal is 1/2. P. Sarkar’s work,
for which we give some further result, essentially says that this approximation
is asymptotically the right one. More precisely:
• when the number n of summands is fixed, the probability that the i-th bit
of addition and XOR are equal has a limit when i→ +∞, equal to 1/2 if
(n−1)/2n is even, and to 1/2+(−1) ε for odd n;n
• ε → 0 as n→ +∞.n
Inotherwords, replacingadditionbyXOR,youaredoingagoodapproximation
unless there are “few” odd summands.
Inthispaper,westudyapproximationofadditionbyXOR,takingP.Sarkar’s
eprint publication 2009/047 as the reference work and starting point. In this
work, among various results, it was claimed that explicit formulas seemed dif-
ficult to obtain when the number n of summands is more than 5. In the first
part of our work, we show a systematic way to find explicit formulas: the com-
3plexity to compute them is O(n ), which allows large values of n. We present
some numerical computation and point out a - conjectural - observation on the
coefficients.
In the second part, we study a generalisation of P. Sarkar’s work to q-ary
addition, insteadofbinary. Weshowthatthemechanicsoftheadditionisessen-
tially the same as in the binary case. In particular, sequence of carries behaves
very similarly: it is a Markov chain whose transition matrix can be computed.
Running some experiments on small values of n leads us to a conjecture, the
first part of which is intuitive and the second part of which reveals an amazing
coincidence (and is probably not!).
1