. Démonstration, Cette propriété découle de la propriété 8. Soit (A, B) un noeud ayant un chemin utile µ dans G, différent de x 0 Au moment de l'insertion de

. Testatypique, µ) est vrai, alors Echec b se produit et le simulateur s'arrête

. Démonstration and . Soit, une requête reçue par S 5 Si x a un chemin utile µ dans G(q) et si µ||M est un chemin utile, la propriété 10 montre qu'aucun (?, ? )-relatif de x ne peut avoir de chemin utile dans G. S émet la seule requête (M, x) à F et ajoute l

. Dans-le-cas-contraire, M ) telles que?xque? que?x a un chemin utile?µutile? utile?µ dans G et?µ||?Met? et?µ||et?µ||? et?µ||?M est un chemin utile et que S 5 soumet à F. Ces entrées ont toutes (M, x) comme relatif commun, et la propriété 10 garantit qu'aucune paire d'éléments de T n'est composée d'entrées relatives l'une de l'autre. Par définition de R indep, nous avons donc |T | ? R indep . En ajoutant la requête pour F M (x), nous avons E(q + 1) ? E(q) + (R indep + 1)

. Comme-avant-la-première-requête, ) = 0, nous en déduisons |E(q)| ? (q ? 1)

.. La-cryptanalyse-conditionnelle-algébrique, 168 8.1.1 Préimages pour la fonction de compression, p.170

.. Description-de-la-fonction-hamsi-256, 171 8.2.1 Schéma général de la fonction, p.172

.. Recherche-de-secondes-préimages-pour-hamsi, 182 8.6.1 Préimages d'un ensemble d'éléments, p.183

M. Abe, Advances in Cryptology -ASIACRYPT 2010, 16th International Conference on the Theory and Application of Cryptology and Information Security Proceedings, 2010.
DOI : 10.1007/978-3-642-17373-8

E. Jean-philippe-aumasson, L. R. Käsper, K. Knudsen, R. Matusiewicz, and . Ødegaard, Thomas Peyrin et Martin Schläffer : Distinguishers for the compression function and output transformation of Hamsi-256, LNCS, vol.6168, pp.87-103, 2010.

J. Aumasson and W. Meier, Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. NIST mailing list, pp.173-182, 2009.

J. Aumasson, A. Mashatan, and W. Meier, More on Shabal's permutation. OF- FICIAL COMMENT, p.75, 2009.

A. Van-assche, A rotational distinguisher on Shabal's keyed permutation and its impact on the security proofs, Available online, p.79, 2010.

J. Aumasson, On the pseudorandomness of Hamsi, NIST mailing list, p.173, 2009.

E. Biham-et-rafi-chen-matthew and K. Franklin, éditeur : CRYPTO, volume 3152 de Lecture Notes in Computer Science Christina Boura et Anne Canteaut : Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-and Hamsi-256, Biryukov et al. [BGS11], pp.290-305, 2004.

C. Boura, A. Canteaut, and C. De-cannière, Higher Order Differential Properties on Keccak and Luffa Keying Hash Functions for Message Authentication, éditeur : CRYPTO, volume 1109 de Lecture Notes in Computer Science, pp.1-15, 1996.

E. Biham and O. Dunkelman, A Framework for Iterative Hash Functions : HAIFA. Dans Proceedings of Second NIST Cryptographic Hash Workshop, p.54, 2006.

G. Bertoni and J. Daemen, Michaël Peeters et Gilles Van Assche : Radiogatun, a belt-andmill hash function. Presented at Second Cryptographic Hash Workshop, pp.156-166

G. Bertoni and J. Daemen, Michaël Peeters et Gilles Van Assche : Sponge Functions, p.152, 2007.

G. Bertoni, J. Daemen, M. Peeters, and G. , Van Assche : Keccak specifications. Submission to NIST, p.54, 2008.

G. Bertoni and J. Daemen, On the Indifferentiability of the Sponge Construction, Lecture Notes in Computer Science, vol.4965, issue.68, pp.181-197, 2008.
DOI : 10.1007/978-3-540-78967-3_11

G. Bertoni and J. Daemen, Michaël Peeters et Gilles Van Assche : Duplexing the sponge : single-pass authenticated encryption and other applications

S. Conference and . Barbara, 23-24 août 2010

J. Daniel and . Bernstein, ChaCha, a variant of Salsa20, 2008.

J. Daniel and . Bernstein, Second preimages for 6 (7 ? (8 ? ?)) rounds of Keccak ? NIST Hash Forum, 2011.

[. Bouillaguet and P. Fouque, Analysis of RadioGatun using Algebraic Techniques, p.152, 2008.
URL : https://hal.archives-ouvertes.fr/inria-00417797

[. Bouillaguet, . Pierre-alain-fouque-et-gaëtan-leurent, and . Biryukov, Security Analysis of SIMD, BGS11], vol.119, issue.BGS11, pp.351-368
DOI : 10.1007/11535218_2
URL : https://hal.archives-ouvertes.fr/inria-00556680

A. Biryukov, G. Gong, D. R. Stinson, S. Barak, and . Halevi, Selected Areas in Cryptography - 17th International Workshop Revised Selected Papers, volume 6544 de Lecture Notes in Computer Science A model and architecture for pseudo-random generation with applications to /dev/random, éditeurs : ACM Conference on Computer and Communications Security, pp.190-203, 2005.

A. Biryukov, D. Khovratovich, and I. Nikolic, Distinguisher and Related-Key Attack on the Full AES-256. Dans Shai Halevi, éditeur : CRYPTO, volume 5677 de Lecture Notes in Computer Science, BR93] Mihir Bellare et Phillip Rogaway : Random Oracles are Practical : A Paradigm for Designing Efficient Protocols. Dans ACM Conference on Computer and Communications Security, pp.231-249, 1993.

S. L. Paulo, V. Barreto, and . Rijmen, The WHIRLPOOL hashing function Analysis of the Block-Cipher- Based Hash-Function Constructions from PGV, Bra90] Gilles Brassard, éditeur. Advances in Cryptology -CRYPTO '89, 9th Annual International Cryptology Conference Proceedings, volume 435 de Lecture Notes in Computer Science Moti Yung, éditeur : CRYPTO, volume 2442 de Lecture Notes in Computer Science, pp.191-320, 1989.

E. Biham and A. Shamir, Differential Cryptanalysis of the Full 16-round DES, Dans Ernest F. Brickell Lecture Notes in Computer Science, vol.740, pp.487-496, 1992.
DOI : 10.1007/3-540-48071-4_34

J. M. Luc, J. Claesen, M. Daemen, G. Genoe, and . Peeters, Subterranean : A 600 Mbit/Sec Cryptographic VLSI Chip, pp.610-613, 1993.

Y. Jean-sébastien-coron, C. Dodis, . Malinaud-et-prashant-puniya-merkle-damgård-revisited-]-donghoon, M. Chang, and . Nandi, How to Construct a Hash Function Differential Collisions in SHA-0. Dans Hugo Krawczyk, éditeur : CRYPTO, volume 1462 de Lecture Notes in Computer Science Improved Indifferentiability Security Analysis of chopMD Hash Function, [Cra05] Ronald Cramer, éditeur. Advances in Cryptology -EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques Proceedings, volume 3494 de Lecture Notes in Computer ScienceCT10] Cagdas Calik et Meltem Sonmez Turan : Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256. Cryptology ePrint Archive, pp.430-448, 1998.

J. Daemen, Ivan Damgård : A Design Principle for Hash Functions, Bert den Boer et Antoon Bosselaers : Collisions for the Compression Function of MD5. Dans EUROCRYPT, pp.153-416, 1991.

J. Daemen and S. K. Craig, Clapp : Fast Hashing and Stream Encryption with PANAMA, Serge Vaudenay, éditeur : FSE, volume 1372 de Lecture Notes in Computer Science, pp.60-74, 1998.

]. R. Dea99 and . Dean, Formal aspects of mobile code security, p.33, 1999.

J. Detrey, P. Gaudry, and K. Biryukov, A Low-Area Yet Performant FPGA Implementation of Shabal, BGS11], pp.99-113
DOI : 10.1109/DSD.2009.162
URL : https://hal.archives-ouvertes.fr/inria-00498705

W. Diffie and E. Martin, Hellman : New Directions in Cryptography, IEEE Transactions on Information Theory, issue.6, pp.22644-654, 1976.

M. Duan and X. Lai, Improved zero-sum distinguisher for full round Keccak-f permutation, Dieter Gollmann, éditeur : FSE, volume 1039 de Lecture Notes in Computer Science, pp.53-69, 1996.
DOI : 10.1007/s11434-011-4909-x

J. Daemen and V. Rijmen, The Block Cipher Rijndael, éditeurs : CARDIS, volume 1820 de Lecture Notes in Computer Science, pp.277-284, 1998.
DOI : 10.1007/10721064_26

[. Dodis, T. Ristenpart, and T. Shrimpton, Salvaging Merkle-Damg??rd for Practical Applications, Joux [Jou09], pp.371-388
DOI : 10.1007/BFb0054137

I. Dinur and A. Shamir, Cube Attacks on Tweakable Black Box Polynomials, pp.278-299, 2009.
DOI : 10.1007/978-3-540-68164-9_16

N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare et al., The Skein Hash Function Family, Octobre 2010. Cf

[. Fuhr and T. Peyrin, Cryptanalysis of RadioGat??n, Lecture Notes in Computer Science, vol.5665, pp.122-138, 2009.
DOI : 10.1007/978-3-642-03317-9_8

A. Fiat, A. Shamir-andrew, and M. Odlyzko, How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Lecture Notes in Computer Science, vol.263, pp.186-194, 1986.
DOI : 10.1007/3-540-47721-7_12

J. Francq and C. Thuillet, Unfolding Method for Shabal on Virtex-5 FPGAs : Concrete Results. Second SHA-3 conference [Fuh10] Thomas Fuhr : Finding Second Preimages of Short Messages for Hamsi-256, pp.67-87, 2010.

X. Guo, S. Huang, L. Nazhandali, and P. Schaumont, Fair and comprehensive evaluation of 14 second round SHA-3 ASIC implementations, p.67, 2010.

[. Gaj, Ekawat Homsirikamol et Marcin Rogawski : Fair and Comprehensive Methodology for Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates Using FPGAs, Mangard et Standaert [MS10], pp.264-278

. Gkm-+-11-]-praveen, L. R. Gauravaram, K. Knudsen, F. Matusiewicz, C. Mendel et al., Thomsen : grøstl-a sha-3 candidate, Mars 2011. Cf

M. Gorski, S. Lucks, and T. Peyrin, Slide Attacks on a Class of Hash Functions, Lecture Notes in Computer Science, vol.7, issue.4, pp.143-160, 2008.
DOI : 10.1007/978-3-540-68164-9_20

J. Guo, S. Søren, . Thomsen, and . Biryukov, Deterministic Differential Properties of the Compression Function of BMW, BGS11], pp.338-350
DOI : 10.1007/978-3-642-13858-4_17

J. J. Hoch and A. Shamir, On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak, Lecture Notes in Computer Science, vol.5126, issue.2, pp.616-630, 2008.
DOI : 10.1007/978-3-540-70583-3_50

T. Isobe and T. Shirai, Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512, Cryptology ePrint Archive, p.77, 2010.

L. Ji and X. Liangyu, Attacks on Round-Reduced BLAKE. Cryptology ePrint Archive, Report, vol.238, p.54, 2009.

A. Joux, Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions, pp.306-316, 2004.
DOI : 10.1007/978-3-540-28628-8_19

A. Joux, Advances in Cryptology -EUROCRYPT, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques Proceedings, volume 5479 de Lecture Notes in Computer Science, pp.189-193, 2009.

A. Joux and T. Peyrin, Hash Functions and the (Amplified) Boomerang Attack, Lecture Notes in Computer Science, vol.4622, pp.244-263, 2007.
DOI : 10.1007/978-3-540-74143-5_14

]. B. Kal92 and . Kaliski, RFC 1319 : The MD2 Message Digest Algorithm, 1992.

L. R. Knudsen and J. E. Mathiassen, Preimage and Collision Attacks on MD2, Lecture Notes in Computer Science, vol.3557, pp.255-267, 2005.
DOI : 10.1007/11502760_17

L. R. Knudsen, J. E. Mathiassen, F. Muller-et-søren, and S. Thomsen, Cryptanalysis of MD2, Journal of Cryptology, vol.12, issue.1, pp.72-90, 2010.
DOI : 10.1007/s00145-009-9054-1

S. Knellwolf, W. Meier, and M. Naya-plasencia, Conditional Differential Cryptanalysis of NLFSR-Based Cryptosystems, Abe [Abe10], pp.130-145
DOI : 10.1007/978-3-642-17373-8_8

L. R. Knudsen, K. Matusiewicz-et-søren, and S. Thomsen, Observations on the Shabal keyed permutation, OFFICIAL COMMENT, vol.118, pp.78-121, 2009.

[. Khovratovich and I. Nikolic, Rotational Cryptanalysis of ARX, Hong et Iwata [HI10]KNR10] Dmitry Khovratovich, Ivica Nikolic et Christian Rechberger : Rotational Rebound Attacks on Reduced Skein. Dans Abe [Abe10], pp.333-346
DOI : 10.1007/978-3-642-13858-4_19

J. Kelsey and B. Schneier, Second Preimages on n-Bit Hash Functions for Much Less than Work 32 [Küç09] Özgül Küçük : The Hash Function Hamsi, Cramer [Cra05]Leu08] Gaëtan Leurent : MD4 is Not One-Way. Dans Nyberg [Nyb08]Leu09] Gaëtan Leurent : Communication personnelleLis06] Moses Liskov : Constructing an Ideal Hash Function from Weak Ideal Compression Functions, pp.474-490, 2009.

E. Dans, . Biham, M. Amr, J. L. Lai, and . Massey, éditeurs : Selected Areas in Cryptography Hash Function Based on Block Ciphers Lucks : A Failure-Friendly Design Principle for Hash Functions, ASIACRYPT, volume 3788 de Lecture Notes in Computer Science, pp.358-375, 2006.

C. Ralph and . Merkle, One Way Hash Functions and DES, pp.428-446

S. Miyaguchi, M. Iwata, and K. Ohta, New 128-bit hash function, 4th International Joint Workshop on Computer Communications, pp.279-288, 1942.

C. [. Matyas, J. Meyer, and . Oseas, Generating Strong One-Way Functions With Cryptographic Algorithm, p.42, 1985.

S. Manuel and T. Peyrin, Collisions on SHA-0 in One Hour, pp.16-35
DOI : 10.1007/978-3-540-71039-4_2

M. Ueli, R. Maurer, C. Renner, and . Holenstein, Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology, Moni Naor, éditeur : TCC, volume 2951 de Lecture Notes in Computer Science, pp.21-39, 2004.

[. Mangard and F. Standaert, Frédéric Muller : The MD2 Hash Function Is Not One-Way, Proceedings, volume 6225 de Lecture Notes in Computer Science Pil Joong Lee, éditeur : ASIACRYPT, volume 3329 de Lecture Notes in Computer ScienceNik09] Ivica Nikolic : Near collisions for the compression function of hamsi-256. CRYPTO rump session, pp.193-214, 1996.

U. Thèse-de-doctorat, M. Pierre, and . Curie, María Naya-Plasencia : How to Improve Rebound Attacks Cf, Nyb08] Kaisa Nyberg, éditeur. Fast Software Encryption, 15th International WorkshopOsv00] Dag Arne Osvik : Speeding up Serpent. Dans AES Candidate Conference, pp.75-64, 2000.

[. Peyrin, Cryptanalysis of Grindahl 163 [Pey10] Thomas Peyrin : Improved Differential Attacks for ECHO and Grøstl, Dans Tal Rabin Lecture Notes in Computer Science, vol.6223, issue.54, pp.551-567, 2007.

[. Preneel, R. Govaerts-et-joos-vandewalle-douglas, and R. Stinson, Hash functions based on block ciphers: a synthetic approach, Lecture Notes in Computer Science, vol.773, issue.42, pp.368-378, 1993.
DOI : 10.1007/3-540-48329-2_31

P. [. Rogier and . Chauvaud, MD2 is not Secure Without the Checksum Byte, Des. Codes Cryptography, vol.12, issue.3, pp.245-251, 1997.
DOI : 10.1007/978-1-4615-5489-9_3

]. R. Riv92a and . Rivest, RFC 1320 : The MD4 Message Digest Algorithm, Avril 1992. Cf. http://www.ietf. org. 43 [Riv92b] R. Rivest : RFC 1321 : The MD5 Message Digest Algorithm, Cf, 1992.

B. Vincent-rijmen, B. Van-rompay, J. Preneel, and . Vandewalle, Producing Collisions for PANAMA, pp.37-51, 2001.

R. L. Rivest, A. Shamir, and M. Leonard, Adleman : A Method for Obtaining Digital Signatures and Public-Key Cryptosystems Hovav Shacham et Thomas Shrimpton : Careful with Composition : Limitations of the Indifferentiability Framework, RSA02] PKCS# 1 v2.1 : RSA Cryptography Standard, pp.120-126, 1978.

Y. Sasaki and K. Aoki, Finding Preimages in Full MD5 Faster Than Exhaustive Search, Joux [Jou09], pp.134-152
DOI : 10.1007/11426639_2

M. Schläffer, Updated Differential Analysis of grøstl, p.54, 2011.

A. Shamir and I. Dinur, Sequences of games : a tool for taming complexity in security proofs, 2004. shoup@cs.nyu Advances in Cryptology, CRYPTO 2005 : 25th Annual International Cryptology Conference Proceedings, volume 3621 de Lecture Notes in Computer Science Michael Vielhaber : AIDA Algebraic IV Differential Attack Breaking One.Fivium by AIDA an Algebraic IV Differential AttackBenner et Jens Gräf : XBX : eXternal Benchmarking eXtension for the SUPER- COP Crypto Benchmarking Framework. Dans Mangard et Standaert [MS10], pp.185-193, 2004.

[. Wu, The Hash Function JH, Janvier 2011. Cf

[. Wang and H. Yu, How to Break MD5 and Other Hash Functions, Cramer [Cra05], pp.19-35
DOI : 10.1007/11426639_2
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.6718

X. Wang, Y. Lisa-yin, and H. Yu, Finding Collisions in the Full SHA-1, Shoup [Sho05], pp.17-36
DOI : 10.1007/11535218_2

X. Wang and H. Yu-et-yiqun-lisa-yin, Efficient Collision Search Attacks on SHA-0, Shoup [Sho05], pp.1-16
DOI : 10.1007/11535218_1

[. Yu and X. Wang, Cryptanalysis of the Compression Function of SIMD. Cryptology ePrint Archive, Report, vol.304, p.64, 2010.