Security Properties of Domain Extenders for Cryptographic Hash Functions
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Cryptographic hash functions reduce inputs of arbitrary or very large length to a short string of fixed length. All hash function designs start from a compression function with fixed length inputs. The compression function itself is designed from scratch, or derived from a block cipher or a permutation. The most common procedure to extend the domain of a compression function in order to obtain a hash function is a simple linear iteration; however, some variants use multiple iterations or a tree structure that allows for parallelism. This paper presents a survey of 17 extenders in the literature. It considers the natural question whether these preserve the security properties of the compression function, and more in particular collision resistance, second preimage resistance, preimage resistance and the pseudo-random oracle property.
Abstract
Cryptographic hash functions reduce inputs of arbitrary or very large length to a short string of fixed length. All hash function designs start from a compression function with fixed length inputs. The compression function itself is designed from scratch, or derived from a block cipher or a permutation. The most common procedure to extend the domain of a compression function in order to obtain a hash function is a simple linear iteration; however, some variants use multiple iterations or a tree structure that allows for parallelism. This paper presents a survey of 17 extenders in the literature. It considers the natural question whether these preserve the security properties of the compression function, and more in particular collision resistance, second preimage resistance, preimage resistance and the pseudo-random oracle property.
참고문헌 (82)
- Whitfield Diffie, "New Directions in Cryptography", IEEE Transactions on Information Theory, 22(6), pp.644~654 (1976)
- Ralph Merkle, "Secrecy, Authentication, and Public Key Systems" (1979), UMI Research Press
- Michael O. Rabin, "Digitalized signatures. Foundations of Secure Computation", pp.155~166 (1978), Academic Press
- Ivan Damgård, "A Design Principle for Hash Functions", Advances in Cryptology - CRYPTO '89 of Lecture Notes in Computer Science, 435, pp.416~427 (1990), Springer-Verlag
- Ralph Merkle, "One way hash functions and DES. Advances in Cryptology - CRYPTO '89 of Lecture Notes in Computer Science", 435, pp.428~446 (1990), Springer-Verlag
- Xuejia Lai, "Hash Function Based on Block Ciphers", Advances in Cryptology - EUROCRYPT '92 of Lecture Notes in Computer Science, 658, pp.55~70 (1992), Springer-Verlag
- Bert den Boer, "Collisions for the compression function of MD5", Advances in Cryptology - EUROCRYPT '93 of Lecture Notes in Computer Science, 765, pp.293~304 (1994), Springer-Verlag
- Hans Dobbertin, "The status of MD5 after a recent attack", CryptoBytes, 2006(2), pp.1~6 (1996)
- Xiaoyun Wang, "How to Break MD5 and Other Hash Functions", Advances in Cryp-tology - EUROCRYPT '05 of Lecture Notes in Computer Science, 3494, pp.19~35 (2005), Springer-Verlag
- Xiaoyun Wang, "Finding Collisions in the Full SHA-1", Advances in Cryptology - CRYPTO '05 of Lecture Notes in Computer Science, 3621, pp.17~36 (2005), Springer-Verlag
- Jean-Sébastien Coron, "Merkle-Damgård Revisited: How to Construct a Hash Function", Advances in Cryptology - CRYPTO '05 of Lecture Notes in Computer Science, 3621, pp.430~448 (2005), Springer-Verlag
- Antoine Joux, "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions", Advances in Cryptology - CRYPTO '04 Lecture Notes in Computer Science, 3152, pp.306~316 (2004), Springer-Verlag
- John Kelsey, "Herding Hash Functions and the Nostradamus Attack", Advances in Cryptology - EUROCRYPT'06 of Lecture Notes in Computer Science, 4004, pp.183~200 (2006), Springer-Verlag
- John Kelsey, "Second Preimages on n-Bit Hash Functions for Much Less than Work", Advances in Cryptology - EUROCRYPT '05 Lecture Notes in Computer Sci-ence, 3494, pp.474~490 (2005), Springer-Verlag
- Phillip Rogaway, "Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance", Fast Software Encryption '04 of Lecture Notes in Computer Science, 3017, pp.371~388 (2004), Springer-Verlag
- "National Institute for Standards and Technology. Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family"[URL]
- Douglas Stinson, "Some Observations on the Theory of Cryptographic Hash Functions", Des. Codes Cryptography, 38(2), pp.259~277 (2006)
- Phillip Rogaway, "Formalizing Human Ignorance", VIETCRYPT '92 of Lecture Notes in Computer Science, 4341, pp.211~228 (2006), Springer-Verlag
- Amos Fiat, "How to Prove Yourself: Practical Solutions to Identification and Signa-ture Problems", Advances in Cryptology - CRYPTO '86 of Lecture Notes in Computer Science, 263, pp.186~194 (1987), Springer-Verlag
- Mihir Bellare, "Random Oracles are Practical: A Paradigm for Designing Effi-cient Protocols", ACM Conference on Computer and Communications Security, pp.62~73 (1993), ACM
- Ueli Maurer, "Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology", Theory of Cryptography Conference '04 of Lecture Notes in Computer Science, 2951, pp.21~39 (2004), Springer-Verlag
- Elena Andreeva, "Seven-Property-Preserving Iterated Hashing: ROX", Advances in Cryptology - ASIACRYPT '07 of Lecture Notes in Computer Science, 4833, pp.130~146 (2007), Springer-Verlag
- Richard Dean, "Formal Aspects of Mobile Code Security", 박사, pp.1999
- Stefan Lucks, "A Failure-Friendly Design Principle for Hash Functions", Advances in Cryptology - ASIACRYPT '05, Vol.3788 of Lecture Notes in Computer Science, pp.474~494 (2005), Springer-Verlag
- Hans Danilo Gligoroski, "Cryptographic Hash Function BLUE MIDNIGHT WISH", ~ (2009)
- Dan Bernstein, "CubeHash specification", ~ (2009)
- Ryad Benadjila, "SHA-3 Proposal: ECHO", ~ (2009)
- Shai Halevi, "Fugue", The Hash Function, ~ (2009)
- Praveen Gauravaram, "Grøstl - a SHA-3 candidate", ~ (2009)
- Hongjun Wu, "The Hash Function JH", ~ (2009)
- Guido Bertoni, "The KECCAK sponge function family", ~ (2009)
- Christophe De Cannière, "Hash Function Luffa", ~ (2009)
- Gaëtan Leurent, "SIMD is a Message Digest", ~ (2009)
- Emmanuel Bresson, "Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition", ~ (2009)
- Jean-Philippe Aumasson, "SHA-3 proposal BLAKE", ~ (2009)
- Özgül Küçük, "The Hash Function Hamsi", ~ (2009)
- Eli Biham, "The SHAvite-3 Hash Function", ~ (2009)
- Shai Niels Ferguson, "The Skein Hash Function Family", ~ (2008)
- Elena Andreeva, "Security Reductions of the Second Round SHA-3 Candidates", Information Security Conference - ISC '10 in Lecture Notes in Computer Science (2010)
- Mihir Bellare, "Multi-Property-Preserving Hash Domain Extension and the EMD Transform", Advances in Cryptology - ASIACRYPT '06, Vol.4284 of Lecture Notes in Com-puter Science, 통권 : 4284, pp.299~314 (2006)
- Elena Andreeva, "A Three-Property-Secure Hash Function", Selected Areas in Cryp-tography '08, Vol.5381 of Lecture Notes in Computer Science, 통권 : 5381, pp.228~244 (2009)
- Donghoon Chang, "Indifferentiable Security Analysis of Popular Hash Functions with Prefix-Free Padding", Advances in Cryptology - ASIACRYPT '06, Vol.4284 of Lecture Notes in Computer Science, pp.283~298 (2006)
- Donghoon Chang, "Improved Indifferentiability Security Analysis of chopMD Hash Function", Fast Software Encryption '08, Vol.5086 of Lecture Notes in Computer Science, pp.429~443 (2008)
- Ewan Fleischmann, "Some Observations on Indifferentiability", Australasian Conference on Information Security and Privacy - ACISP '10, Vol.6168 of Lecture Notes in Computer Science, pp.117~134 (2010)
- Yevgeniy Dodis, "Salvaging Merkle-Damgård for Practical Applications", Advances in Cryptology - EUROCRYPT '09, Vol.5479 of Lecture Notes in Computer Science, pp.371~388 (2009)
- Mihir Bellare, "Keying Hash Functions for Message Authentication", Advances in Cryptology - CRYPTO '96, Vol.1109 of Lecture Notes in Computer Science, pp.1~15 (1996)
- Shoichi Hirose, "A Simple Variant of the Merkle-Damgård Scheme with a Permutation", Advances in Cryptology - ASIACRYPT '07, Vol.4833 of Lecture Notes in Computer Science, pp.113~129 (2007)
- Mihir Bellare, "Collision-Resistant Hashing: Towards Making UOWHFs Prac-tical", Advances in Cryptology - CRYPTO '97, Vol.1294 of Lecture Notes in Computer Science, pp.470~484 (1997)
- Mihir Bellare, "Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms", International Colloquium on Automata, Languages and Pro-gramming - ICALP '07, Vol.4596 of Lecture Notes in Computer Science, pp.399~410 (2007)
- Victor Shoup, "A Composition Theorem for Universal One-Way Hash Functions", Advances in Cryp-tology - EUROCRYPT '00, Vol.1807 of Lecture Notes in Computer Science, pp.445~452 (2000)
- Mohammad Reza Reyhanitabar, "Analysis of Property-Preservation Capabilities of the ROX and ESh Hash Domain Extenders", Australasian Conference on Information Security and Privacy - ACISP '09, Vol.5594 of Lecture Notes in Computer Science, pp.153~170 (2009)
- A Framework for Iterative Hash Functions - HAIFA, "Eli Biham", Cryptology ePrint Archive, ~, pp.Report 2007 (2007), 278
- Second Prei-mage Attacks on Dithered Hash Functions, "Charles Bouillaguet", Cryptology ePrint Archive, ~, pp.Report 2007 (2007), 395
- Ronald Rivest, "Abelian Square-Free Dithering for Iterated Hash Functions", ECRYPT Hash Function Workshop 2005.
- Shai Halevi, "Strengthening Digital Signatures Via Randomized Hashing", Ad-vances in Cryptology - CRYPTO '06, Vol.4117 of Lecture Notes in Computer Science, pp.41~59 (2006)
- Praveen Gauravaram, "On Randomizing Hash Functions to Strengthen the Security of Digital Signatures", Advances in Cryptology - EUROCRYPT '09, Vol.5479 of Lecture Notes in Computer Science, pp.88~105 (2009)
- Ralph Merkle, "Protocols for Public Key Cryptosystems", pp.122~134 (1980), IEEE Computer Society Press
- Wonil Lee, "New Parallel Domain Extenders for UOWHF", Advances in Cryptology - ASIACRYPT '03, Vol.2894 of Lecture Notes in Computer Science, pp.208~227 (2003)
- Wonil Lee, "Construction of UOWHF: Two New Parallel Methods", IEICE Transactions, 88-A(1), pp.49~58 (2005)
- Palash Sarkar, "Construction of Universal One-Way Hash Functions: Tree Hashing Revisited", Discrete Applied Mathematics, 155(16), pp.2174~2180 (2007)
- Yevgeniy Dodis, "Indifferentiability of Permutation-Based Compression Functions and Tree-Based Modes of Operation, with Applications to MD6", Fast Software Encryption '09, Vol.5665 of Lecture Notes in Computer Science, pp.104~121 (2009)
- Sufficient Conditions for Sound Tree and Sequential Hashing Modes, "Guido Bertoni", Cryptology ePrint Archive, ~, pp.Report 2009 (2009), 210
- Elena Andreeva, "Three-Property-Preserving Iterations of Keyless Compression Functions", ECRYPT Hash Function Workshop 2007
- Jonathan Hoch, "On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak", International Colloquium on Automata, Languages and Programming - ICALP '08, Vol.5126 of Lecture Notes in Computer Science, pp.616~630 (2008)
- Moses Liskov, "Constructing an Ideal Hash Function from Weak Ideal Compression Functions", Selected Areas in Cryptography '06, Vol.4356 of Lecture Notes in Computer Science, pp.358~375 (2007)
- Bart Preneel, "Hash Functions Based on Block Ciphers: A Synthetic Approach", Advances in Cryptology - CRYPTO '93, Vol.773 of Lecture Notes in Computer Science,, pp.368~378 (1993)
- John Black, "Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV", Advances in Cryptology - CRYPTO '02, Vol.2442 of Lecture Notes in Computer Science, pp.320~335 (2002)
- Hidenori Kuwakado, "Indifferentiability of Single-Block-Length and Rate-1 Compression Functions", IEICE Transactions, 90(A(10)), pp.2301~2308 (2007)
- Martijn Stam, "Blockcipher-Based Hashing Revisited", Fast Software Encryption '09, Vol.5665 of Lecture Notes in Computer Science, pp.67~83 (2009)
- Improved Collision and Preimage Resistance Bounds on PGV Schemes, "Lei Duo", Cryptology ePrint Archive, ~, pp.Report 2006 (2006), 462
- Zheng Gong, "A Synthetic Indifferentiability Analysis of Some Block-Cipher-Based Hash Functions", es. Codes Cryptography, 48(3), pp.293~305 (2008)
- Revisiting the Indifferen-tiability of PGV Hash Functions, "Yiyuan Luo", Cryptology ePrint Archive, ~, pp.Report 2009 (2009), 265
- John Black, "On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions", Advances in Cryptology - EUROCRYPT '05, Vol.3494 of Lec-ture Notes in Computer Science, pp.526~541 (2005)
- Phillip Rogaway, "Security", Efficiency Tradeoffs for Permutation-Based Hashing, 2008, 220~236
- Martijn Stam, "Beyond Uniformity: Better Security", Efficiency Tradeoffs for Compression Functions, 2008, 397~412
- Phillip Rogaway, "Constructing Cryptographic Hash Functions from Fixed-Key Blockciphers", Advances in Cryptology - CRYPTO '08, Vol.5157 of Lecture Notes in Computer Science,, pp.433~450 (2008)
- Thomas Shrimpton, "Building a Collision-Resistant Compression Function from Non-compressing Primitives", International Colloquium on Automata, Languages and Programming - ICALP '08, Vol.5126 of Lecture Notes in Computer Science, pp.643~654 (2008)
- Guido Bertoni, "Sponge Functions", ECRYPT Hash Function Workshop 2007
- Guido Bertoni, "On the Indifferentiability of the Sponge Construction", Advances in Cryptology - EUROCRYPT '08, Vol.4965 of Lecture Notes in Computer Science, pp.181~197 (2008)
- Lars Knudsen, "The Grindahl Hash Functions", Fast Software Encryption '07, Vol.4593 of Lecture Notes in Computer Science, pp.39~57 (2007)
- Yevgeniy Dodis, "Getting the Best Out of Existing Hash Functions; or What if We Are Stuck with SHA?", Applied Cryptography and Network Security '08, Vol.5037 of Lecture Notes in Computer Science,, pp.156~173 (2008)
- Mridul Nandi, "Characterizing Padding Rules of MD Hash Functions Preserving Collision Security", Australasian Conference on Information Security and Privacy '09, Vol.5594 of Lecture Notes in Computer Science, pp.171~184 (2009)
