Cryptographic Hash Functions

Lecturer:

Prof. Dr. Michael Eichberg

Version:

2023-10-19

Based on:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Hash Function

• A hash function H accepts a variable-length block of data \(M\) as input and produces a fixed-size result \(h = H(M)\).

• A good hash function will produce outputs that are evenly distributed and apparently random.

• Often used to ensure data integrity. A change to any bit in M should result with a high probability in a change of the hash value.

• Cryptographic hash functions are nedded for security applications.

• Applications:

  • Message Authentication

  • Digitial Signatures

  • One-way Password Files

Security Requirements for a Cryptographic Hash Function H

Variable Input Size:

H can be applied to a block of data of any size.

Fixed Output Size:

H produces a fixed-length output

Efficiency:

When used for message authentication and digital signatures \(H(x)\) is relatively easy to compute for any given \(x\), making both hardware and software implementations practical.

vs.

When used for password hashing it is hard to efficiently compute the hash even on specialized hardware (GPUs, ASICs) to thwart attackers.

Security Requirements for a Cryptographic Hash Function H

Preimage resistant (one-way property):

For any given hash value \(h\), it is computationally infeasible to find \(y\) such that \(H(y) = h\)

Second preimage resistant (weak collision resistant):

For any given block x, it is computationally infeasible to find \(y \neq x\) with \(H(x) = H(y)\)

Collision resistant (strong collision resistant):

It is computationally infeasible to find any pair \((x,y)\) with \(x \neq y\), such that \(H(x) = H(y)\)

Pseudorandomness:

Output of H meets standard tests for pseudorandomness.

Hash Function Resistance Properties Required

Relationship Among Hash Function Properties

Structure of Secure Hash Code

Password Recovery

Passwords are often stored using hashes.

Example using the md5 hash function:

md5 ("Hello") = 8b1a9953c4611296a827abf8c47804d7
md5 ("hello") = 5d41402abc4b2a76b9719d911017c592
md5 ("Dieses Passwort ist wirklich total sicher
      und falls Du es mir nicht glaubst, dann
      tippe es zweimal hintereinander blind
      fehlerfrei ein.")
              = 8fcf22b1f8327e3a005f0cba48dd44c8

Usage of Cryptographic Hash Functions

• Known cryptographic hash functions: MD4, MD5, SHA-256, SHA-512, RIPE-MD, PBKDF2, …

• When used for password hashing the algorithms are usually applied many times to increase the runtime to make it harder for adversaries.

• Several hash algorithms were explicitly designed for passwort hashing to withstand common attacks. E.g., bcrypt, scrypt, Argon2

• Some of these algorithms are so computationally involved that they are not suitable for web applications/situations where have to authorize many users at a time. These algorithms are typically used to protect local harddisks or containers.

Passwords are not always explicitly stored

Encryption of Containers (e.g., Veracrypt)

Passwords are not always explicitly stored

Generic File Encryption

Password Recovery

1. know where to “find” the hash to recovery

2. extract the hash

3. recover the hash

Example - recovery of a linux login password

~% sudo cat /etc/shadow
[...]
john:$6$zElzjLsMqi36JXWG$FX2Br1/[...]. ↩︎
RxAHnNCBsqiouWUz751crHodXxs0iqZfBt9j40l3G0:19425:0:99999:7:::
[...]

% echo -n '$6$zElzjLsMqi36JXWG$FX2Br1/[...]. ↩︎
RxAHnNCBsqiouWUz751crHodXxs0iqZfBt9j40l3G0' > hash.txt

% hashcat -m 1800 hash.txt -a 3 ‘?d?d?d?d?d?d'

Sources of Passwords

Passwords are often created using one or more of the following sources:

• Pins (e.g., 1111, 1234, 123456, …)

• Keyboard Walks (e.g., asdfg, q2w3e4r5t)

• Patterns (e.g., aaaaa, ababab, abcabcabc)

• Dictionaries (e.g., Duden, Webster, …)

• Context Information

• Password Generators

A good source for studying the construction of passwords are so-called leaks and lists with common password.

Common Password Lists

Source: Becker's Health IT

• The lists typically don't change much year-over-year.

• The methodology is often questionable.

Challenges When Recovering Passwords (Hashrates)

Challenges When Recovering Passwords - (Hashrates)

Challenges When Recovering Passwords - (Hashrates)

Attacking LUKS2 with Argon2

[…] The choice of Argon2 as a KDF makes GPU acceleration impossible. As a result, you’ll be restricted to CPU-only attacks, which may be very slow or extremely slow depending on your CPU. To give an idea, you can try 2 (that’s right, two) passwords per second on a single Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz. Modern CPUs will deliver a slightly better performance, but don’t expect a miracle: LUKS2 default KDF is deliberately made to resist attacks. […]

https://blog.elcomsoft.com/2022/08/probing-linux-disk-encryption-luks2-argon-2-and-gpu-acceleration

Challenges When Recovering Passwords - (Password Policies)

Modern password policies make it impossible to directly use older leaks.

Examples:

• minimum number of characters (maximum number of characters)

• requirements on the number of digits, special chars, upper and lower case letters

• requirements on the diversity of the used characters

• some passwords (e.g., from known leaks and dictionaries) are forbidden

• ...

Understanding the Nature of Passwords

Here, we mapped every lowercase letter to l, upper case letters to u, digits to d and special chars to s.

Analysis based on the “famous” rockyou leak.

Understanding the Nature of Passwords

Analysis based on the “famous” rockyou leak.

Understanding the Nature of Passwords

Understanding the Nature of Passwords

• Passwords that need to be entered frequently are in the vast majority of cases based on “real” words.

• Real words are often not used as is, but are transformed using simple rules; e.g., by appending a number or by appending a special character, …

Password Cracking Using Probabilistic Context-Free Grammars

• Generate password patterns in order of decreasing probability.

  • Directly useable as guesses

  • Used as word-mangling templates that are to be filled using dictionaries(E.g., pre-terminal structure: S → D1L3S2 → 1L3!! → 1luv!! )

• Learn the patterns, words, special chars and digits based on real-world leaks

• Process:

  1. Pre-processing to identify base structures and probabilities(e.g. 2 numbers followed by special char by 8 letters)

  2. Password guess generation taking the probabilities of the rules and the digits/special chars into account; the probability of the alpha strings is not considered.

SePass: Semantic Password Guessing Using k-nn Similarity Search in Word Embeddings

Extension of PCFG where additional candidate words are identified using Word Embeddings. Enables to automatically find related words.

Example

SePass: Semantic Password Guessing Using k-nn Similarity Search in Word Embeddings

Avoids human bias.

Example

SePass: Semantic Password Guessing Using k-nn Similarity Search in Word Embeddings

Avoids human bias.

Example

SePass: Conceptual