Data Integrity

Question 1

Hash Functions

Answer 1

Condenses message to fixed size has value (digest)
Multiple input can map to one (collision)
Outputs evenly distributed for all inputs
Used to detect changes to message
Used for data integrity, digital signatures, hashed password files, file system intrusion detection, psuedorandom number generation

Question 2

Message Authentication

Answer 2

Protecting integrity of message, verifying identity of sender, and non-repudiation of origin
Hash value called “message digest” when used for message authentication

Question 3

Message Authentication Code (MAC)

Answer 3

Keyed Hash Function
Used by sides that share a secret key to authenticate themselves to each other
M and k = H
Check MAC of received message with associated MAC value
Attacker can’t alter MAC value without secret key

Question 4

Message Authentication Code (MAC) - Other Uses

Answer 4

Passwords-Store hash of password
Intrusion/virus detection-Attacker must somehow change file, but not MAC
Pseudorandom number generator

Question 5

Hash Function - Requirements

Answer 5

Variable input length
Fixed output length
Efficiency
Preimage resistant (one-way property)-infeasible to find x that H(x) == h
Second preimage resistant (weak collision resistant)-infeasible to find y that x != y & H(x) == H(y)
Collision resistant (strong collision resistant)-infeasible to find any message pair x, y where H(x) == H(y)
Pseudorandomness-Output of H meets pseudorandomness tests

Question 6

Hash Functions - Attacks - Brute Force

Answer 6

Find 1st or 2nd preimage-Probability of success = over 50% after 2^(m-1) attempts
Collision Resistance-Probabilty of success = over 50% after 2^(m/2) attempts

Question 7

Hash Functions - Attacks - Birthday Attack

Answer 7

Opponent makes 2^(m/2) fraudulent messages and 2^(m/2) valid messages victim will sign
Find two that have the same hash (birthday paradox says he/she has over 50%)
Victim signs real one, but opponent concatenates fake one
Use larger (more bits) hash values

Question 8

Hash Functions - Types - XOR

Answer 8

M || E(K, H(M))
Based on XOR
Very weak, can change message before/after encryption (can permute 1, N-1 blocks before changing MAC value)

Question 9

Hash Functions - Types - Block Cipher

Answer 9

Encrypt last hash value + current message block to get next hash value
Continue until you get to last message block-that is your hash value
Too small (DES 64 bits)
Vulnerable to birthday and meet-in-the-middle attacks

Question 10

Hash Functions - Attacks - Meet-in-the-Middle

Answer 10

Create fraudulent message from Q0 to Qn-2 to create H1 to Hn-2
Create 2^(m/2) random blocks Xi and 2^(m/2) random blocks Yj
Create EXi(Hn-2) and DYj(g)
>= 50% probability that EXi(Hn-2) == DYj(g) for some X and Y; concatenate X and Y to end of fraudulent message

Question 11

Symmetric Encryption Authentication

Answer 11

Message must have standardized structure and/or checksum function used before/after encryption/decryption

Question 12

Message Authentication Code (MAC) - Discover Authentication Key

Answer 12

Given M1 and T1 = C(K, M1), try all 2^k keys and get Ti for each one
T1 == Ti will happen about 2^k-n times
Keep doing this until you get one match-authentication key
Effort needed is O(2^k)

Question 13

Message Authentication Code (MAC) - Requirements

Answer 13

Infeasible to find message with same MAC (2nd image protection)
Output should be uniformly distributed
Should depend on all parts of the message
Can’t create same MAC with same key with NEW message

Question 14

HMAC

Answer 14

(K+ XOR opad) || Hash[ (K+ XOR ipad) || M ]

K+ is K padded on right side with 0s to make it to bit size b, where b > Length(K) > n