Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Introduction to Cryptography • CSCI 462-01 • Spring Semester 2018
Course Page

## CSCI 462—Introduction to Cryptography Chapter 11. Hash Functions Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### One-Way Hash Functions

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

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

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

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

• The above properties imply that:
• The output of a hash function looks like an n-bit random number
• Two different messages will almost certainly (with probability 1 − 2n) have completely different digests
• A message's digest serves as a unique "fingerprint" for the message

• Examples of one-way hash functions:

 Hash Algorithm Date Output Digest Length (bits) Security Message Digest 4 (MD4) 1990 128 Broken Message Digest 5 (MD5) 1991 128 Broken Secure Hash Algorithm 0 (SHA-0) 1993 160 Broken Secure Hash Algorithm 1 (SHA-1) 1995 160 Broken Secure Hash Algorithm 2 (SHA-2) 2002 224, 256, 384, 512 Questionable Secure Hash Algorithm 3 (SHA-3) 2015 224, 256, 384, 512 Secure

### Generic Attacks on Hash Functions

• n = output digest length

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

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

• Can find a collision with sqrt(2n) = 2n/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)! MN)
• If M is large and N is about sqrt(M), then an approximate formula is:
• Pr[collision] = 1 − exp (−N2 / (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 (−N2 / 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

### SHA-1 and SHA-2

• SHA-1 Standardized by NIST in 1995

• SHA-2 Standardized by NIST in 2002

• Official specification: Federal Information Processing Standards Publication 180-4. Secure Hash Standard (SHS). August 2015.
http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

• Cryptographic One-Way Hash Functions

• Wikipedia articles:

• Uses the Merkle-Damgård construction

• SHA-1 was theoretically broken years ago
• Brute force search finds collisions with 280 operations
• Attack by Wang et al. (2005) finds collisions with 269 operations
• Attack by Stevens (2013) finds collisions with 261 operations

• A variant of SHA-1 was practically broken in 2016
• M. Stevens, P. Karpman, and T. Peyrin. Freestart collision on full SHA-1. Cryptology ePrint Archive, Report 2015/967, February 22, 2016. http://eprint.iacr.org/2015/967
• By picking a different initialization vector (a "freestart" attack) . . .
• A collision in SHA-1 can be found with 257 operations
• The attack was actually carried out on a GPU cluster in 2015
• A practical attack on SHA-1 with the correct IV is not too far off

• The actual SHA-1 was practically broken in 2017!
• M. Stevens, E. Bursztein, P. Karpman, A. Albertini, and Y. Markov. The first collision for full SHA-1. 2017. https://shattered.io/static/shattered.pdf
• The attack required 6500 single-CPU years and 110 single-GPU years
• Computational effort equivalent to 263.1 SHA-1 compressions

• The SHA-2 hash functions are as yet unbroken
• But watch out—they use algorithms similar to SHA-1
• Concerns about SHA-2's security led to the SHA-3 Competition

### 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

### Attacks on Merkle-Damgård

• Random oracle
• A theoretical function that acts as an "ideal" hash function
• Maps each possible input message to an n-bit digest chosen uniformly at random from 0 to 2n−1
• Requires an infinitely large table—impossible to implement in practice

• Indistinguishability
• Suppose I give you a black box that is a hash function
• The black box is either a random oracle or some real hash function, but you don't know which
• You do some computations where you can evaluate the black box as many times as you please on whatever inputs you want
• Then you tell me whether the black box is a random oracle or a real hash function
• If on the average you get the right answer only 50% of the time, then the real hash function is indistinguishable from a random oracle
• When designing a hash algorithm, this is what you want
• If on the average you get the right answer more than 50% of the time, then the real hash function is distinguishable from a random oracle, and the computation is a distinguishing attack

• Length extension attack
• Suppose the digest of message abc is X
• For a Merkle-Damgård hash function, the digest of message abcd is C(X,d)
• C is the compression function
• For a random oracle, hash(abcd) ≠ C(X,d) almost certainly (with probability 1 − 1/2n)
• So this is a distinguishing attack
• I can compute the digest of the longer message without even knowing the content of the shorter message
• This poses a problem when we try to use a hash function in a message authentication code (MAC)

• Partial-message collision attack
• Suppose I find a collision in the compression function
• Given chaining input H1, find two message blocks a and b such that C(H1,a) = C(H1,b)
• For an n-bit digest (chaining value), this takes 2n/2 work
• Then I append another message block c to each message
• For a Merkle-Damgård hash function, hash(ac) = hash(bc)
• For a random oracle, hash(ac) ≠ hash(bc) almost certainly (with probability 1 − 1/2n)
• So this is a distinguishing attack
• This poses a problem when we try to use a hash function in a MAC

• Fixed-point attack
• R. Dean. Formal Aspects of Mobile Code Security. Ph.D. dissertation, Princeton University, 1999.
• Suppose message abc yields a chaining value of H1
• Suppose I find a fixed point in the compression function
• Given chaining input H1, find message block f such that C(H1,f) = H1
• For an n-bit digest (chaining value), this takes 2n work
• Then I can construct an infinite number of messages, all of which have the same digest
• abcfxyz
• abcffxyz
• abcfffxyz
• . . .
• But it should not be possible to construct an infinite number of collisions with a finite amount of work

• Multicollision attack
• A. Joux. Multicollisions in iterated hash functions. Application to cascaded constructions. In Advances in Cryptology—CRYPTO 2004, pages 306-316, 2004.
• Suppose I find three collisions in the compression function
• Given chaining input H1 = initialization vector, find two message blocks a and b such that C(H1,a) = C(H1,b) = H2
• Given chaining input H2, find two message blocks c and d such that C(H2,c) = C(H2,d) = H3
• Given chaining input H3, find two message blocks e and f such that C(H3,e) = C(H3,f) = H4
• For an n-bit digest (chaining value), each collision takes 2n/2 work
• Then I can construct 8 messages, all of which have the same digest
• ace
• acf
• bce
• bcf
• bde
• bdf
• But it should not be possible to construct 8 collisions with only 3⋅2n/2 work—it's supposed to take 8⋅2n/2 work
• This scheme can be extended to construct k collisions with only (log2 k) collision searches

• Expandable message attack
• J. Kelsey and B. Schneier. Second preimages on n-bit hash functions for much less than 2n 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.

• All of these are weaknesses in the Merkle-Damgård construction, not in any particular hash algorithm's compression function

### Alternatives to Merkle-Damgård

• To avert the preceding attacks on Merkle-Damgård hash functions

• 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 digest 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 bijective function P is indistinguishable from a random oracle, then the whole hash function is indistinguishable from a random oracle
• Can produce a digest of any size with the same algorithm

• 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

• 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:

• 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

• On May 28, 2014, NIST published a draft standard for SHA-3

• On August 5, 2015, NIST published the official SHA-3 standard

• SHA-3 cryptographic hash functions
• SHA3-224
• SHA3-256
• SHA3-384
• SHA3-512
• Arbitrary input size, fixed output size (224 to 512 bits)
• Intended for hashing

• SHA-3 extendable output functions
• SHAKE128
• SHAKE256
• "SHAKE" = "Secure Hash Algorithm" + "KEccak"
• Arbitrary input size, arbitrary output size
• Intended primarily for hashing, but also possibly for other applications
• Stream ciphers
• Pseudorandom number generators
• The 128 or 256 refers to the security level: 2128 or 2256 operations to find a collision

• Solution: Store a database of (username, password) entries on the server
• Server looks up username in database
• Server verifies that the passwords match

• Problem: If a hacker steals the database, the hacker obtains all the users' passwords

• Solution: Store a database of (username, password-digest) entries on the server
• Server looks up username in database
• Server computes digest of user-supplied password
• Server verifies that the password digests match

• Now if a hacker steals the database, the hacker has to compute hash function preimages to obtain the users' passwords

• Problem: The hacker can do a dictionary attack
• Most humans choose passwords that can be found in a dictionary
• One claims to have a list of nearly 1.5 billion words
• Hacker precomputes the digest of every password in the dictionary
• Hacker also precomputes the digest for variations like alternate capitalization, additional digits, punctuation, etc.
• Hacker looks for password-digest matches

• Time-memory trade-off (TMTO) algorithms can reduce the hacker's storage requirement
• Hash chains
• Rainbow tables

• Solution: Store a database of (username, salt, password-digest) entries on the server
• Salt = a large random number (e.g. 64 bits) unique to each user
• Server looks up username and salt in database
• Server computes digest of user-supplied password concatenated with salt
• Server verifies that the password digests match

• Now to do a dictionary attack . . .
• The hacker must compute the hash of every dictionary word/salt value combination
• This increases the hacker's work factor by the number of possible salt values
• If the hacker computes the dictionary hashes before stealing the server's database, the work factor increases by the total possible number of salt values (e.g. 264)
• If the hacker computes the dictionary hashes after stealing the server's database, the work factor increases by the actual number of salt values in the database

• Problem: Standard cryptographic hash functions can be computed very quickly — especially when computed in parallel
• Multicore CPUs
• Graphics processing unit (GPU) accelerators
• Field programmable gate array (FPGA) accelerators
• Application specific integrated circuits (ASICs)

• Bitcoin mining ASICs
• Bitcoin mining requires computing double-SHA-256
• Bitcoin mining ASICs and boards are readily available — try a Google search
• One claims a computation rate of 800 billion hashes per second
• This board could hash a 1.5-billion-word dictionary in 2 milliseconds
• This board could hash all combinations of a 1.5-billion-word dictionary with 1 million salt values in half an hour
• Despite a lot of hype and inflated claims around Bitcoin ASIC performance, it's clear that ASICs can compute hashes at enormous speed

• Solution: Use a CPU-hard hash function
• A hash function that takes a long time to compute
• For example, iterate SHA-256 n times; e.g., n = 1000
• Make n large enough to deter hackers . . .
• But not so large that user login processing is too slow
• As time goes on and computer speeds increase, just increase n to keep pace

• Problem: GPUs, FPGAs, ASICs, etc. are still too fast

• Solution: Use a memory-hard hash function
• A hash function that takes a long time and lots of memory to compute
• Standard hash functions (including iterated standard hash functions) require very little memory
• So a GPU/FPGA/ASIC only needs a small amount of memory per processor core
• So a single chip can have a lot of parallel processor cores
• But a single chip or board can only have a certain total amount of memory
• So if computing a hash function required, say, a gigabyte of memory, that would drastically reduce the achievable parallelism

• Inaugurated in February 2013
• 24 first-round candidate password hashing algorithms announced on April 1, 2014

 AntCrypt Argon battcrypt Catena Catfish Centrifuge EARWORM Gambit Lanarea Lyra2 M3lcrypt Makwa MCS_PHS Omega Crypt Parallel PolyPassHash POMELO Pufferfish RIG Schvrch Tortuga TwoCats Yarn yescrypt

• 9 finalist candidate password hashing algorithms announced on December 8, 2014

 Argon battcrypt Catena Lyra2 Makwa Parallel POMELO Pufferfish yescrypt

• Winner announced July 20, 2015: Argon2 (a variant of the original Argon)

• "Special recognitions" for Catena, Lyra2, Makwa, and yescrypt were also announced

• Catena
• C. Forler, S. Lucks, and J. Wenzel. Catena: a memory-consuming password scrambler. Cryptology ePrint Archive, Report 2013/525, January 5, 2014. http://eprint.iacr.org/2013/525

Forler et. al, op. cit.

• Each black dot is a hash computation — they recommend using SHA2-512, Keccak-512, or BLAKE2b
• 2g hashes wide — they recommend 217 for password hashing
• λ levels deep — they recommend 2 levels for password hashing
• They recommend using a 128-bit salt for password hashing

• Lyra
• L. Almeida, E. Andrade, P. Barreto, and M. Simplicio. Lyra: password-based key derivation with tunable memory and processing costs. Cryptology ePrint Archive, Report 2014/030, April 1, 2014. http://eprint.iacr.org/2014/030

Almeida et. al, op. cit.

• Uses a sponge construction hash function
• Absorb the password and salt
• Fill in an R×C matrix with random values computed by the sponge bijection function
• Do T passes over the entire matrix, updating elements with random values computed by the sponge bijection function
• The rows are visited in a random order determined by the matrix elements themselves
• Thus, the entire matrix needs to stay in memory throughout the computation
• At the end, absorb the salt again, then squeeze out the password digest
• R and C tune memory usage
• T tunes processing time

• Argon2

Biryukov et. al, op. cit.

• Argon2 uses m kilobytes of memory, organized into a matrix B with p rows (lanes) and m/p columns of 1-KB blocks
• Memory is typically hundreds of megabytes to several gigabytes
• The message (password), nonce (salt), and other parameters are fed through a conventional hash function (Blake2b)
• The hash function's output is used to initialize the first two blocks in each lane
• Each remaining block in each lane is filled in by running two blocks through a compression function:
• The previous block in the lane
• Some other block elsewhere in the matrix, chosen by a quasirandom indexing function
• Compression function based on the Blake2b round function
• The above is repeated for t passes over the memory
• This forces the entire matrix to remain in memory while computing the hash function
• The last blocks in the lanes are XORed together
• The result is run through one or more iterations of the conventional hash function to generate the final digest
• Memory and time required to compute the hash function are independently tunable with the m and t parameters

• Late breaking PHC news flash!
• On April 1, 2015, it was announced that all the above algorithms were rejected . . .
• And that the Microsoft legacy algorithm LM Hash was the winner
• Wikipedia article on LM Hash: http://en.wikipedia.org/wiki/LM_hash
• Rationale for the choice of LM Hash

http://www.joyoftech.com/joyoftech/joyarchives/2252.html

 Introduction to Cryptography • CSCI 462-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005