CSCE 465 Lecture 20

« previous | Thursday, April 4, 2013 | next »

Hash Functions

• Commitment verification
• Message authentication
• Encryption (OFB-like) scheme (after first collision, pad sequence repeats)
• Message Integrity verification
• Digital Signatures (public key signing a hash/digest) instead of the whole message.

Is encryption a good hash function? No

• Block size might be too small
• Easy to construct message with same hash (meet-in-middle)

Modern Hash Functions

MD5

Also previous (broken) versions (MD2, MD4, etc.)

Multiple rounds produces 128-bit digest

Operation:

1. Input: 128-bit input message digest (IV or output from prev chain)
2. Input: 512-bit message block
3. Output: 128-bit digest (input to next chain)
4. (continues for length of message (mod 2⁶⁴))

Block processing

Every message block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i} consists of 16 × 32-bit words: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_0, \ldots, m_{15}}

A block is processed in 4 consecutive passes, each modifying the MD5 buffer (dijest) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_0, \ldots, d_3} ; each pass labeled ${\mathcal {F}},{\mathcal {G}},{\mathcal {H}},{\mathcal {I}}$

Insecurity

• a few collisions published in August 2004
• In 2005, two X.509 certificates with different public keys and the same MD5 hash were constructed
  • based on differential analysis
  • 8 hrs on 1.6 GHz processor
  • much faster than birthay attack
• Too weak to be used for serious applications

SHA

• Developed by NIST in 1993, specified in Secure Hash Standard
• Revised to SHA-1 in 1995

Assumption: Input size must be ideally less than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^64}

Input message broken into 512-bit blocks, same padding as MD5

Digest is 160 bits long, 5 × 32-bit words Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A, B, C, D, E}

Block Processing

80 steps (c.f. 64 for MD5)

Very similar to MD5: only one added step

Comparison with MD5

• SHA-1 is stronger than MD5 (simply because it has more steps)
• Also takes twice as long to compute, but "much" faster than DES

Insecurity

• Original SHA: Weaknesses were found
• SHA-1 is broken, but not yet cracked:
  • Collisions in 2⁶⁹ hash operations, less than brute force 2⁸⁰ operations
  • Results published in 2005
• other (more secure versions) in family: SHA-256, SHA-384, etc. (based on digest output size)

Extension Attack

Given message Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1} and a secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , one can easily concatenate and compute the hash Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = H(k\mid M_1 \mid padding)} and use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} as the message authentication code.

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_2} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(k\mid M1\mid padding)} , it's easy to compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(k\mid M_1\mid padding\mid M_2\mid newpadding)} for some new mesage Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_2} :

Just use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(k \mid M_1 \mid padding)} as the IV for computing the hash of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_2 \mid newpadding} (does not require us to know Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} )

Hashed Message Authentication Code (HMAC)

Provably secure against Extension attack

1. P = pad \( k \) on right with 0s to 512 bits in length
2. compute P ⊕ 0x36363636...36
3. ...
4. Concatenate P ⊕ 0x5c5c5c5c...5c

Summary

• Hashing is fast to compute
• Has many applications
• Images must be at least 128 bits long, but longer is better
• Hash function details are tedious
• HMAC protects message digests from extension attacks.