Journées Codage et Cryptographie 2009
55 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Journées Codage et Cryptographie 2009

-

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

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 42
Langue Français
Poids de l'ouvrage 2 Mo

Exrait

  • candidate hashing algorithm
  • h25 complexité en données
  • h45 amélioration de la probabilité
  • teurs candidats
  • sha
  • pause
  • collision
  • collisions
  • h20
  • complexité
  • h45
  • ' />

    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

    • Accueil Accueil
    • Univers Univers
    • Ebooks Ebooks
    • Livres audio Livres audio
    • Presse Presse
    • BD BD
    • Documents Documents