4003-482-01/4005-705-01 Cryptography
Chapter 11. Hash Functions
Lecture Notes

One-Way Hash Functions

• A one-way hash function maps an arbitrary-length input message M to a fixed-length output hash H(M) such that the following properties hold:

• One-way, or preimage resistant: Given a hash H(M), it is difficult to find the message M.

• Second preimage resistant, or weakly collision resistant: Given a message M₁, it is difficult to find another message M₂ such that H(M₁) = H(M₂).

• Collision resistant, or strongly collision resistant: It is difficult to find two messages M₁ and M₂ such that H(M₁) = H(M₂).

• Examples of one-way hash functions:

  Hash Algorithm		Output Hash Length (bits)		Security
  Message Digest 4 (MD4)		128		Broken
  Message Digest 5 (MD5)		128		Broken
  Secure Hash Algorithm 0 (SHA-0)		160		Broken
  Secure Hash Algorithm 1 (SHA-1)		160		Theoretically broken
  SHA-224 (part of SHA-2)		224		Questionable
  SHA-256 (part of SHA-2)		256		Questionable
  SHA-384 (part of SHA-2)		384		Questionable
  SHA-512 (part of SHA-2)		512		Questionable

Generic Attacks on Hash Functions

• n = output hash length

• Can find a preimage with 2ⁿ operations using brute force search

• Can find a second preimage with 2ⁿ operations using brute force search

• Can find a collision with sqrt(2ⁿ) = 2^n/2 operations using brute force search
  • Birthday attack

• Birthday problem 1
  • An urn with M balls labeled 1 .. M
  • N balls are drawn at random, with replacement
  • Pr[collision] = Probability that two or more balls drawn have the same label
  • Pr[collision] = 1 − M! / ((M − N)! M^N)
  • If M is large and N is about sqrt(M), then an approximate formula is:
  • Pr[collision] = 1 − exp (−N² / (2M))

• Birthday problem 2
  • An urn with M white balls labeled 1 .. M
  • Another urn with M red balls labeled 1 .. M
  • N white balls are drawn at random, with replacement
  • N red balls are drawn at random, with replacement
  • Pr[collision] = Probability that one or more white balls drawn have the same label as one or more red balls drawn
  • If M is large and N is about sqrt(M), then an approximate formula is:
  • Pr[collision] = 1 − exp (−N² / M)

• See Handbook of Applied Cryptography, Section 2.1.5

The Merkle-Damgård Construction

• Invented by Ralph Merkle and Ivan Damgård working independently
  • R. Merkle. A certified digital signature. In Advances in Cryptology -- CRYPTO '89, pages 218-238, August 1989.
  • I. Damgård. A design principle for hash functions. In Advances in Cryptology -- CRYPTO '89, pages 416-427, August 1989.

• Wikipedia article: http://en.wikipedia.org/wiki/Merkle-Damgard

  
  David Göthberg, http://en.wikipedia.org/wiki/Image:Merkle-Damgard_hash_big.svg

• Message extended with padding bits (100000...) plus message length
  • Merkle-Damgård strengthening

• Padded message fed through an iterated compression function

• In 1989, Merkle and Damgård proved that if the compression function is collision-resistant, then the whole hash function will be collision resistant

• Because of this proof, most hash functions proposed since then use the Merkle-Damgård construction or a variation

MD5

• Invented by Ron Rivest in 1992

• Official specification: Internet RFC 1321, http://www.ietf.org/rfc/rfc1321.txt

• Wikipedia article: http://en.wikipedia.org/wiki/Md5

• Uses the Merkle-Damgård construction

• MD5 is broken!
  • It is possible to find collisions far more quickly than 2⁶⁴ operations
  • In fact, it is possible to find collisions in seconds

• HashClash Project
  • Main web site -- http://www.win.tue.nl/hashclash/
  • Predicting the winner of the 2008 U.S. presidential elections using a Sony PlayStation 3 (November 30, 2007) -- http://www.win.tue.nl/hashclash/Nostradamus/
  • MD5 considered harmful today: Creating a rogue CA certificate (December 30, 2008) -- http://www.win.tue.nl/hashclash/rogue-ca/

SHA-1 and SHA-2

• Standardized by NIST in 2002

• Official specification: Federal Information Processing Standards Publication 180-4. Secure Hash Standard (SHS). March 2012. http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf

• Cryptographic One-Way Hash Functions

• Wikipedia article: http://en.wikipedia.org/wiki/Sha-1

• Uses the Merkle-Damgård construction

• SHA-1 is theoretically broken
  • One attack finds collisions with 2⁶³ operations
    • Far less time than brute force 2⁸⁰ operations
    • Far more time than most people are willing to wait for an actual collision
  • Another attack finds collisions with an estimated 2⁵¹ operations
    • Unknown whether the estimate is correct

• SHA-2's security is "questionable"
  • But watch out -- they use algorithms similar to SHA-1

Block Cipher Based Hash Functions

• The Merkle-Damgård construction, using a block cipher as the compression function

• See Handbook of Applied Cryptography, Section 9.4

  
  A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997), page 340.

• V. Rijmen and P. Barreto. The Whirlpool hash function. http://paginas.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html, October 28, 2006.
  • Based on a block cipher, W, similar to AES but with a 512-bit block size and a 512-bit key size

• D. Gazzoni Filho, P. Barreto, and V. Rijmen. The Maelstrom-0 hash function. In Proceedings of the 6th Brazilian Symposium on Information and Computer Systems Security (SBSeg 2006), 2006.
  • Based on a block cipher, M, similar to AES (and W) but with a 512-bit block size and a 1024-bit key size

Alternatives to Merkle-Damgård

• To avert various (nongeneric) attacks on Merkle-Damgård hash functions
  • Length extension attack
  • Partial-message collision attack
  • Fixed-point attack
    • R. Dean. Formal Aspects of Mobile Code Security. Ph.D. dissertation, Princeton University, 1999.
  • Multicollision attack
    • A. Joux. Multicollisions in iterated hash functions. Application to cascaded constructions. In Advances in Cryptology -- CRYPTO 2004, pages 306-316, 2004.
  • Expandable message attack
    • J. Kelsey and B. Schneier. Second preimages on n-bit hash functions for much less than 2ⁿ work. In Advances in Cryptology -- EUROCRYPT 2005, pages 474-490, 2005.
  • Herding attack
    • J. Kelsey and T. Kohno. Herding hash functions and the Nostradamus attack. In Advances in Cryptology -- EUROCRYPT 2006, pages 183-200, 2006.

• Wide-pipe construction
  • S. Lucks. Design principles for iterated hash functions. Cryptology ePrint Archive, Report 2004/253, September 29, 2004. http://eprint.iacr.org/2004/253
  • Same as Merkle-Damgård, except chaining value is wider than hash value

    

• HAIFA construction
  • E. Biham and O. Dunkelman. A framework for iterative hash functions -- HAIFA. NIST Second Cryptographic Hash Workshop, 2006. http://csrc.nist.gov/groups/ST/hash/documents/DUNKELMAN_NIST3.pdf
  • Same as Merkle-Damgård, except:
  • A salt is included in each compression function
  • The number of bits hashed so far is included in each compression function

    

• Sponge construction
  • G. Bertoni, J. Daemen, M. Peeters, and G. van Assche. On the indifferentiability of the sponge construction. In Advances in Cryptology -- EUROCRYPT 2008, pages 181-197, 2008.
  • The Sponge Functions Corner. http://sponge.noekeon.org/
  • Completely different from Merkle-Damgård

    

  • They proved that if the permutation is indistinguishable from a random oracle, then the whole hash function is indistinguishable from a random oracle
  • Can produce a hash output of any size with the same algorithm
  • This is a brand new construction -- vulnerabilities not widely studied yet

• Parallel tree mode
  • Merkle-Damgård and sponge must be computed sequentially
  • For large messages, this takes too long
  • Tree mode is a way to compute a hash in parallel

    

  • Example: Damgård's original paper proposed a binary tree of compression functions
  • Not much attention has been paid to tree mode -- vulnerabilities not widely studied yet

SHA-3

• On November 2, 2007, NIST announced a competition to design a new secure hash function to be called SHA-3
  • SHA-3 Competition: http://csrc.nist.gov/groups/ST/hash/sha-3/index.html
  • SHA-3 Zoo: http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo

• On December 9, 2008, NIST announced the 51 first-round candidate hash functions:

  Abacus ARIRANG AURORA BLAKE Blender Blue Midnight Wish BOOLE Cheetah CHI CRUNCH CubeHash

  DCH Dynamic SHA Dynamic SHA2 ECHO ECOH EDON-R EnRUPT ESSENCE FSB Fugue Grøstl

  Hamsi JH Keccak Khichidi-1 LANE Lesamnta Luffa LUX MCSSHA-3 MD6 MeshHash

  NaSHA SANDstorm Sarmal Sgàil Shabal SHAMATA SHAvite-3 SIMD Skein Spectral Hash StreamHash

  SWIFFTX Tangle TIB3 Twister Vortex WaMM Waterfall

• On July 24, 2009, NIST announced the 14 second-round candidate hash functions:

  BLAKE Blue Midnight Wish CubeHash

  ECHO Fugue Grøstl

  Hamsi JH Keccak

  Luffa Shabal SHAvite-3

  SIMD Skein

• Overview of the competition as of September 2009:
  • Message Digests for the Twenty-First Century: An Overview of the NIST SHA-3 Cryptographic Hash Algorithm Competition

• On December 9, 2010, NIST announced the five finalist hash functions:

  BLAKE

  Grøstl

  JH

  Keccak

  Skein

• Characteristics of the five finalists:

  	BLAKE	Grøstl	JH	Keccak	Skein
  Design:
  Merkle-Damgård	X	X			X
  Sponge			X	X
  Compression function:
  Not block cipher based		X
  Block cipher based, Davies-Meyer	X
  Block cipher based, Matyas-Meyer-Oseas					X
  Uses cipher pieces:
  AES		X
  ChaCha	X
  Threefish					X

• On October 2, 2012, NIST announced the winning hash function: Keccak
  • Twelve years to the day after announcing the winner of the AES competition
  • The Keccak Sponge Function Family. http://keccak.noekeon.org/
  • The Sponge Functions Corner. http://sponge.noekeon.org/

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 28-Mar-2013. Please send comments to ark­@­cs.rit.edu.