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 $y_{i}$ consists of 16 × 32-bit words: $m_{0},\ldots ,m_{15}$

A block is processed in 4 consecutive passes, each modifying the MD5 buffer (dijest) $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 $2^{6}4$

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

Digest is 160 bits long, 5 × 32-bit words $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 $M_{1}$ and a secret key $k$, one can easily concatenate and compute the hash $a=H(k\mid M_{1}\mid padding)$ and use $a$ as the message authentication code.

Given $M_{1}$, $M_{2}$, and $H(k\mid M1\mid padding)$, it's easy to compute $H(k\mid M_{1}\mid padding\mid M_{2}\mid newpadding)$ for some new mesage $M_{2}$:

Just use $H(k\mid M_{1}\mid padding)$ as the IV for computing the hash of $M_{2}\mid newpadding$ (does not require us to know $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.