MAC & Authenticated Encryption
Cryptographic hashes
hash functions are a building block for confidentiality and integrity
H(M) input: arbitrary length message M Output: fixed length, n-bit hash.
properties:
- correctness: deterministic
- hashing same input always produces same output
- efficient to compute
- one way
- collision resistant
- random / unpredictable
hash function provides a fixed length fingerprint over a sequence of bits
ex: document comparison, you take 2 files, and hash both, and then can compare hashes, to see if the files are different.
informal: given an output y, it is infeasible to find any input x such that H(x) = y intuition: here’s an output: can you find an input that hashes to this output?
is H(x) = 1 one-way
do not want collision: if you have 2 documents and they give same hash, defeats point of hash
can we design a hash function with NO collisions?
collision resisstance; it is infeasible for an attacker to find a collision, but NOT impossible. cannot make a hash function w no collision that takes arbitrary inputs and gets them down to 512bit output
birthday attack: finding a collision on an n bit output required only 2n/2 in a random group of 23 people there is about a 50 percent change that two people have the same birthday
Md5: output 128 bit security: completely broken
sha-1: 160 bits completely broken in 2017
sha 2: output 256 384 or 512 bits
length extension attack: given H(x) and the length of x, but nox, an attacker can create H(x || m) for any m of the attacker’s choosing this doesnt violate any property of hash functions but is undesirable.
Alice and bob both have a A in itis 3200 alice is sending a message M and H(M) to Bob M = “Alice’s grade is A” H(M) = 1234567 Mallory can perform length extension attack to create a new message M’ and H(M’) M’ = Alice’s grade is A! Bob’s grade is D! H(M’) = 12345678
do hash functions provide integrity? depends on your threat model scenario: mozilla publishes new version of firefox on some download servers alice downloads the program binary she can use cryptographic hashes mozilla hashes the binary and publishes hash on the site alice hashes the binary and checks that it matches the hash on the website if alice downloaded a malicious program, the hash would not match an attacker cant create a malicious program with the same hash if someone can fake the hash, it’s cooked
if mallory can moify the message AND the hash, hashing fails to provide integrity
if mallory can ONLY modify the message, but not he hash, hashing provides integrity.
main issue: most hashes are unkeyed functions
we produce some piece of information that can only be produced with the key
MAC takes 2 inputs Key, and M generates T ( tag ) inputs: secret key, arbitrary length message output: a fixed length tag on the message
correctness: deterministic efficiency: very efficient Security: EU-CPA ( unforgeable without the key )
Mallory cant generate a MAC without the key K
can we use secure cryptograhic hashes to build a secure MAC? NMAC does 2 runs of hashing so we can defend against length extension intuition: using 2 hashes prevents a length extension attack.
HMAC is a simplified version of NMAC NMAC needs 2 keys HMAC produces 2 keys from 1 key
HMAC(K,M) Computes K’ as a version of K that is the length of the hash output output: H((K’ xor opad) || H((K’ xor ipad) || M))
opad is the hard coded byte 0x5c repeated until it is the same length as K’ ipad is the hard coded byte 0x36 repeated until it’s the same length as K’ as long as opad and ipad are different, you get different keys.
if underlying hash is secure, hmac doesn’t reveal M, but it is still deterministic
you can’t verify a tag T if you don’t have K.
MACs provide integrity
MACs do not provide authenticity. You can be sure that the message came from someone with the secret key but you cannot narrow it down to one person
Combining schemes
If alice sends Enc(K1, M) and MAC(K2, M) this provides integrity but does not provide confidentiality