4005-800-70 Theory of Computer Algorithms
Cryptographic One-Way Hash Algorithms

One-Way Hash Functions
The Secure Hash Algorithm Family
Double Hashing
Message Authentication Codes
Digital Signatures
Encryption and Decryption

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: Given a hash H(M), it is difficult to find the message M.
   
• Second preimage resistant: Given a message M₁, it is difficult to find another message M₂ such that H(M₁) = H(M₂).
   
• 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)
Message Digest (MD4) -- insecure		128
MD5		128
Secure Hash Algorithm 1 (SHA-1)		160
SHA-256		256
SHA-384		384
SHA-512		512

Specification: "Secure Hash Standard," Federal Information Processing Standards Publication 180-2, August 1, 2002.
http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf

An example implementation of SHA-256 in the Computer Science Course Library:
Class edu.rit.crypto.hash.OneWayHash -- Source code
Class edu.rit.crypto.hash.SHA256Hash -- Source code

SHA-256 is a typical iterated hash function. The following diagrams show how it works.
 
 

Top-Level Function

Iterated Hash Function Structure

Compression Function

Message Expansion Function

Round Function

The Little Functions

σ₀(X) = (X right-rotate 7) xor (X right-rotate 18) xor (X right-shift 3)

σ₁(X) = (X right-rotate 17) xor (X right-rotate 19) xor (X right-shift 10)

Σ₀(X) = (X right-rotate 2) xor (X right-rotate 13) xor (X right-rotate 22)

Σ₁(X) = (X right-rotate 6) xor (X right-rotate 11) xor (X right-rotate 25)

Ch(X,Y,Z) = (X and Y) xor ((not X) and Z)

Maj(X,Y,Z) = (X and Y) xor (X and Z) xor (Y and Z)
 
 

To foil the length extension attack on an iterated hash function:

A message authentication code (MAC) is like a one-way hash function, except you need a secret authentication key to compute the MAC:

You can build a MAC using a one-way hash function as a building block. Here is the Hash-MAC (HMAC) as defined in Internet RFC 2104 (http://www.ietf.org/rfc/rfc2104.txt):

It is just as secure, and usually faster, to compute a digital signature on the hash of a message instead of the message itself:

You can use a hash function in "counter mode" to generate a keystream to do encryption and decryption:

Theory of Computer Algorithms 4005-800-70 Winter Quarter 2003

Course Page

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

Home Page

Copyright © 2004 Alan Kaminsky. All rights reserved. Last updated 17-Feb-2004. Please send comments to ark­@­cs.rit.edu.