Hashing Flashcards
Easy to compute H(m)
Performance of hash function
Given H(m), but not m, it’s computationally infeasible to find m
One-way property of hash function
Given H(m), it’s computationally infeasible to find m’ such that H(m’) = H(m)
Pre-image resistance
Computationally infeasible to find any pair m1, m2 such that H(m1) = H(m2)
Collision resistance
Too long of a hash
Unnecessary overhead
Too short of a hash
Birthday paradox
Broken, collisions published in August 2004
MD5
Too weak for serious applications
MD5
Weaknesses were found, but still in use
SHA
Collisions in 2^69 hash operations
SHA-1 birthday attack
128-bit input digest of four 32-bit words
MD5 input
512-bit message block (sixteen 32-bit words)
MD5 input
128-bit output (four 32-bit words)
MD5 output
Each pass uses a table of constants to update output digest
MD5 operation
Developed by NIST, specified in 1993
SHA
Input processed in 512 bit blocks, with same padding as MD5
SHA1
Input message must be < 2^64
SHA1
Message digest output is 160 bits, five 32-bit words
SHA1 output
Consists of 80 steps
Block processing in SHA
Output of last step is added to input of first step
Block processing in SHA
Slower to compute than MD5
Speed of SHA1
Only works if set of valid messages is limited by some structure
Authentication via encryption
Unsuitable for message authentication
CRC
Used to detected random errors, not malicious attacks
CRC
Attacker can easily modify message and recompute CRC
CRC can only be used to detect random, not malicious errors
Attack where additional information is appended onto hash
Length extension attack
Build MAC out of a hash function
Hash MAC (HMAC)
S(K,m) = H(k xor opad, H(k xor ipad || m))
HMAC
opad and ipad are ____ ciphers
stream
pad messages with 0x36 and 0x5c
HMAC processing