hash functions (w5)

Question 1

what is the definition of a hash function?

Answer 1

an N-bit (cryptographic) hash function is an efficiently computable function:
H: {0, 1}^* –> {0, 1}^N
mapping an arbitrary length input string to a fixed-length hash value (sometimes called message digest)

hash functions are not a keyed primitive

Question 2

what are the applications of hash functions?

Answer 2

Applications of Hash Functions
* message fingerprinting
* * file integrity checking, file sharing
* signature schemes (hash-then-sign paradigm)
* message authentication codes (e.g., HMAC)
* key derivation
* * e.g., to derive keys from ‘raw data’ in Die-Hellman key exchange
* password hashing
* commitment schemes
* pseudorandom number generators
* Bitcoin (proof-of-work schemes)
* post-quantum signature schemes.

Question 3

to what extent does password hashing improve security?

Answer 3

• Security depends on one-wayness of hash function H used: if H can be reversed, then passwords can be found from hashes.
• Use of password crackers: build dictionary, try to hash all passwords in dictionary, check for matches.
• Sophistication of password crackers: tuning, site-specific,
  number-letter substitutions, etc.
• Use of GPUs and special-purpose hardware to speed-up password cracking.
• Use of common passwords: makes cracking many accounts easy.

Question 4

what is salting passwords?

Answer 4

• Add a random, account-specific value, called a salt, in each hash calculation.
• This means that each account has to be attacked individually (via password hashing).
• Store the salt values as a field in the database of usernames and password hashes.
• 64 bits of salt is typical: enough to prevent collisions in random choices of salt values (birthday bound again) and to devalue pre-computation by an attacker.

Question 5

how does hash iteration improve security?

Answer 5

• Slow down password cracking via dictionaries by iterating the hashing.
• Choose an iteration method that makes parallelisation of
  attacks/time-memory trade o↵s hard to do.
  https://password-hashing.net).
• Obtain a trade-off between security and performance of
  authentication system.
• Think about Facebook scale operations.
• Typical iteration count: 10,000

Question 6

what are the primary security goals of hashing?

Answer 6

• pre-image resistance (one-wayness): given h, is it infeasible to find m ∈ {0, 1}^* such that H(m) = h
• second pre-image resistance: given m₁, is it infeasible to find m₁ != m₂ such that H(m₁) = H(m₂)
• collision resistance: is it infeasible to find collisions, i.e. a pair of messages m₁ != m₂ such that H(m₁) = H(m₂)

Question 7

what are the secondary security goals of hashing?

Answer 7

• Near-Collision Resistance: it is infeasible to find m₁ != m₂ such that
  H(m₁1) ≈ H(m2) (e.g. “≈” might mean hashes agree on most
  output bits).
• • Public-key verification in Signal.
• Partial Pre-Image Resistance 1: given H(m), it is infeasible to recover any partial information about m.
• • Key Derivation.
• Partial Pre-Image Resistance 2: given a target string t of bit-length l, it is infeasible to find m ∈ {0, 1}^* such that H(m) = t||z in time
  significantly faster than 2l hash evaluations.
• • Proof-of-Work in Bitcoin.

Question 8

what is the pigeonhole principle?

Answer 8

collisions must exist, because the input space of the hash function is much larger than the output space

Question 9

what is the birthday bound implication?

Answer 9

• an N-bit hash function offers only N/2 bits of security* againts the generic collision attack
• so we need hash functions with 256-bit outputs to achieve 128-bit security level etc.
• SHA-1, still in widespread use, has an output size of 160 bits, so can only reach 80-bit security level against generic collision attack

*Meaning attack cost is 2^N/2 “operations” + memory in some cost model

Question 10

how to achieve post-quantum security with a Merkle-Damgard-based hash?

Answer 10

use 512-bit or larger hash outputs fo 256-bit post-quantum security

impement quantum-secure compression functionc such as those based on lattice assumptions or modular arithmetic

Question 11

define the shortest vector problem (SVP)

Answer 11

given a lattice L(B), find a (nonzero) lattice vector Bx (with x ∈ ℤ^k) of length (at most) ||Bx|| <= λ₁

Question 12

define shortest integer solutions (SIS) problem

Answer 12

SIS(n, m, q, B)
Given A ∈_R ℤ^{n x m}, find z ∈ ℤ_q^m such taht Az = 0 (mod q), where z != 0 and z ∈ [-B, B]^m (and B «q/2)

ℤ_q = {0, 1, 2, … , q - 1}
x ∈_R S means x is selected uniformly (and independantly) at random from S
all vectors are column vectors