Internet Security - Hashing Algorithms

Internet Security - Hashing Algorithms

• Hashing algorithms are used for data integrity assurance
• They are based on one-way mathematical functions
• Input data produces a fixed-length digest (fingerprint) of output data
• Digests are cryptographically strong; recovering original data from the digest is impossible
• Well-known hash functions include:
  • Message Digest 5 (MD5) – 128 bits digest
  • Secure Hash Algorithm 1 (SHA-1) – 160 bits digest

Key Hash Functions

• MD5 (Message Digest 5):

  • Computes a 128-bit hash value
  • Widely used for file integrity checking
  • Based on MD4, addressing vulnerabilities in MD4
  • Generates 128-bit hash values over 512-bit blocks in 4 rounds of 16 steps each

• SHA-1 (Secure Hash Algorithm 1):

  • Computes a 160-bit hash value
  • An NIST approved message digest algorithm
  • Operates on 512-bit blocks, producing a 160-bit hash value in 4 rounds of 20 steps each

Popular Hashing Implementations

• MD5:
  • Designed by Ron Rivest in 1991
  • 128-bit output (considered too short for current use)
  • Developed in 2005
  • Can be broken on a single notebook within minutes
• SHA:
  • Designed by the NSA, published in 1993
  • Family of functions: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512
  • SHA-256 is the current recommendation

Birthday Attack

• Collisions: Two messages with the same hash value
• Based on the birthday paradox
• Hash algorithms should resist this attack
• Each input generates a unique digest

Hash Collision

• Hash functions map arbitrary amounts of data into fixed-length strings
• Due to the nature of fixed output lengths, some inputs inevitably hash into the same string
• Cryptographic hash functions are designed to make these collisions difficult to find

Password Hashing

• Account creation and password hashing involves hashing the password to store it in the database
• Never store cleartext passwords
• The attempted password is hashed and compared to the hash of the original password (stored in the password file).
• Users gain access only if the hashes match.
• Never give user password/username error specific messages.

How to crack Hashed Passwords

• Dictionary attacks: Uses a file containing common passwords (words, phrases). A file of potential words/phrases is hashed. Its hash is compared to the victim's credential hash
• Brute force attacks: Tries every possible combination of characters up to a given length
• Hash table lookup: Precomputing the hashes of the passwords (in a dictionary). Store hashes and associated passwords. Faster than rainbow tables but needs significant storage
• Reverse-lookup table: Obtaining a user's password and hash. Determine the algorithm and apply the lookup to all other accounts
• Rainbow table: Pre-computed table for reversing cryptographic hash functions (usually for cracking passwords). Efficient way to store a pre-computed hash but is slower than lookup

Adding Salt

• Lookup tables and rainbow tables work when a password is hashed exactly the same way
• Randomize hashes by appending or prepending a random string (salt) to the password before hashing

Encryption vs Hashing

Purpose of Hashing

• Non-repudiation: Cannot deny what has been sent
• Detect doctored messages: Original messages are compared to their digests
• Messages and their digests are sent together for verification
• Salt can decrease the risk of hash collision

Terminology

• Message encryption: Ciphertext of entire message serves as authenticator
• Message authentication code (MAC): Public function of message and secret key that produces a fixed length value that serves as authenticator
• Hash function: A public function that maps a message of any length into a fixed length hash value that serves as authenticator
• Hash-based Message Authentication Code (HMAC): Combination of hash function and MAC using a shared secret

Message Integrity

• Allows verification of received messages' authenticity
• Ensures message content hasn't been altered
• Checks source of message and its temporal integrity
• Maintains sequence of messages

Formal Requirements of Hash Function

• H() can be applied to any block of data of any size
• H() produces a fixed-length output
• H(x) is relatively easy to compute for any given x
• One-way property: Very difficult to find another input (X') on which H(X) = H(X')
• Weak collision resistance: Given an input X and a hashing function H(), it is very difficult to find another input X' on which H(X) = H(X')
• Strong collision resistance: H() and two arbitrary inputs (X & Y), a low probability of H(X) being equal to H(Y)

Other Important Details

• Hash is used in digital signatures with analogous techniques to handwritten signatures for verifiability and non-forgeability.
• HMAC is a popular MAC standard addressing subtle security flaws in MAC calculation.