Applied Cryptography & Authentication PDF

Applied Cryptography & Authentication Keyed Hash Functions & MACs M. Jason Hinek COMP 2108 Last time... Unkeyed Hash Functions A hash function h is an easily computable function h : {0, 1}∗ → {0, 1}n. All hash functions have two bas...

Applied Cryptography & Authentication Keyed Hash Functions & MACs M. Jason Hinek COMP 2108 Last time... Unkeyed Hash Functions A hash function h is an easily computable function h : {0, 1}∗ → {0, 1}n. All hash functions have two basic properties · compression : h maps binary strings of arbitrary (but finite) length to binary strings of fixed length · ease of computation : can compute h(x) in time polynomial in log x A cryptographic hash function has some additional properties · preimage resistance: given y it is hard to find an x such that h(x) = y. (one way) · second preimage resistance: given x it is hard to find x 0 6= x such that h(x) = h(x 0 ) (weak collision resistance) · collision resistance: it is hard to find x, x 0 such that x 6= x 0 and h(x) = h(x 0 ) (strong collision resistance) 2 Data Integrity An unkeyed hash function can provide data integrity (and many other things) Note that anyone can compute the hash of a given message since everything is public. So, it allows anyone to verify the integrity of some data. (As long as the hash you comparing to is also unchanged.) 3 Keyed Hash Functions A keyed hash function is a hash function that uses a secret key (symmetric key crypto) in addition to a message as input. For a given key k, calling hk (m) will always return the same hash value each time it is called (for every message m). Given two different keys k1 and k2 , however, it should be the case that hk1 (m) 6= hk2 (m) except for a small number of messages m. Two important cryptographic algorithms that are constructed with keyed hash functions MACs Message Authentication Codes PRFs Pseudorandom Functions We’ll talk about MACs here. 4 Message Authentication Codes a message authentication code, or MAC, is a triple of efficient algorithms (G, S, V), where · G(1n ) generates a key k with security parameter n. G is the key generation algorithm. · S(k, m) generates a tag t for message m and key k. S is the signing algorithm. · V(k, m, t) outputs either accept or reject. V is the verification algorithm. For all messages m and all keys k, S and V must satisfy V(k, m, S(k, m)) → accept This is the correctness property. 5 Message Authentication Codes a message authentication code (MAC) · provides data integrity and data origin authentication in the private key setting · can also be considered as a family of functions (parametrized by k) Hk : {0, 1}∗ → {0, 1}n where k is an `-bit key · Hk (m) is call the MAC or tag of the message m We may use the notation MAC (m), MACk (m), MAC (k, m) for Hk (m) 6 Message Authentication Codes a message authentication code (MAC) · Alice and Bob share a secret key k · Alice computes t = Hk (m) and send (m, t) to Bob · Bob receives (m0 , t 0 ) and checks that t 0 = Hk (m0 ) if t 0 = Hk (m0 ), · Bob has confidence that m0 = m (and t 0 = t) · Bob has confidence that (m, t) was sent by Alice 7 Message Authentication Codes a message authentication code (MAC) 8 Message Authentication Codes security of MACs · Alice and Bob know k · Eve does not know k · Eve is allowed (polynomially many) tags for messages of her choice · oracle access to Hk () (polynomially many calls) · chosen-message attack · Eve tries to generate a valid message-tag pair (m0 , t 0 ) for any m0 (provided she did not ask for the tag of m0 already) 9 Message Authentication Codes security of MACs a MAC is secure if, given polynomially many message-tag pairs (mi , Hk (mi )), it is computationally infeasible to generate a new message-tag pair (m, Hk (m)) for any new message with non-negligible probability such a MAC is said to be existentially unforgeable against chosen-message attacks 10 Message Authentication Codes security of MACs existential forgery: an adversary can create a valid message-tag pair for some message m (doesn’t matter what m is) selective forgery: an adversary can create a valid message-tag pair for a chosen message m (selected by the adversary before the attack) universal forgery: an adversary can create a valid message-tag pair for any message m 11 Message Authentication Codes generic attacks on MACs 1. choose y ∈ {0, 1}n and guess that Hk (m) = y · probability of success 2−n assuming Hk () is random function · n must be large enough to make this infeasible · (we cannot directly check if guess is correct!) 2. exhaustive search for key k · given r message-tag pairs · test each key k by trying to verify each of the r known pairs with k · assuming Hk () is random function the expected number of keys such that all r pairs are verified is 2`−nr 12 Message Authentication Codes we can try and make a MAC from an unkeyed hash function Hk (m) = h(k||m) · secret prefix MAC 13 Message Authentication Codes we can try and make a MAC from an unkeyed hash function Hk (m) = h(k||m) · secret prefix MAC · if underlying hash function has Merkle-Damgård construction · given (m, Hk (m)) and the length of k (but not k itself) we can compute Hk (m||y ) for (almost) arbitrary y and (m||y , Hk (m||y )) is selective forgery 13 Message Authentication Codes we can try and make a MAC from an unkeyed hash function Hk (m) = h(k||m) · secret prefix MAC · if underlying hash function has Merkle-Damgård construction · given (m, Hk (m)) and the length of k (but not k itself) we can compute Hk (m||y ) for (almost) arbitrary y and (m||y , Hk (m||y )) is selective forgery · sha-3 does not admit extension attacks 13 Message Authentication Codes we can try and make a MAC from an unkeyed hash function Hk (m) = h(m||k) · secret suffix MAC 14 Message Authentication Codes we can try and make a MAC from an unkeyed hash function Hk (m) = h(m||k) · secret suffix MAC · if underlying hash function has Merkle-Damgård construction and k is one block in length · first find a collision x1 ,x2 of the hash function · mount chosen-message attack by asking for MAC of x1 which will also be the MAC for x2 14 Message Authentication Codes we can try and make a MAC from an unkeyed hash function Hk (m) = h(m||k) · secret suffix MAC · if underlying hash function has Merkle-Damgård construction and k is one block in length · first find a collision x1 ,x2 of the hash function · mount chosen-message attack by asking for MAC of x1 which will also be the MAC for x2 Hk (m) = h(k||m||k) · envelope (or sandwich) method · secure? attacks exist See the paper by Preneel and van Oorschot https://cr.yp.to/bib/1999/preneel.pdf 14 Message Authentication Codes keyed-hash message authentication code (HMAC) 
 HMAC (k, m) = h (k ⊕ opad) || h (k ⊕ ipad)||m 15 Message Authentication Codes keyed-hash message authentication code (HMAC) 
 HMAC (k, m) = h (k ⊕ opad) || h (k ⊕ ipad)||m · security is based on security of hash function used · can forge MACs using MD4 (because MD4 is too weak) · used in TLS (transport layer security) · used in IPsec (internet protocol security) · RFC 2104 (https://tools.ietf.org/html/rfc2104) · FIPS 198-1 (http://csrc.nist.gov/publications/fips/fips198-1/FIPS-198-1_final.pdf) 16 Message Authentication Codes block cipher MACs · CBC mode of encryption 17 Message Authentication Codes block cipher MACs · CBC-MAC 17 Message Authentication Codes block cipher MACs · CBC-MAC 17 Message Authentication Codes block cipher MACs · EMAC 17 Message Authentication Codes block cipher MACs · EMAC 17 Message Authentication Codes block cipher MACs · EMAC 17 Message Authentication Codes there are other MACs that can built up using a block cipher · XCBC-MAC · CMAC · OMAC 18 Message Authentication Codes Most MACs used in practice have been based on either hash functions or block ciphers. Another kind of MAC is poly1305-AES. · message m is a sequence of bytes m, m,... · key (k, r ) consists of 16-byte AES key k, 16-byte secret number r · each tag uses a 16-byte nonce n · message is converted ci ← fi (m) to coefficients of a polynomial · MAC tag is created as follows (((c1 r q + c2 r q−1 + · · · + cq r 1 ) mod 2130 − 5) + AESk (n)) mod 2128 https://cr.yp.to/mac/poly1305-20050329.pdf https://tools.ietf.org/html/rfc7905 19 Authenticated Encryption provides confidentiality, data integrity and data origin authentication three generic ways to do this with a symmetric-key cipher and MAC · encrypt-then-mac (preferred) · authenticate the encryption · send hEk1 (m), MACk2 (Ek1 (m))i · provably secure if MAC is secure · recent addition to TLS (and DTLS) also found in SSHv2 · encrypt-and-mac · encrypt plaintext and authenticate plaintext · send hEk1 (m), MACk2 (m)i · used in SSH · mac-then-encrypt · encrypt plaintext and mac of plaintext · sends Ek1 (m||MACk2 (m)) · used in SSL/TLS See the doom principle (READ THIS) https://moxie.org/2011/12/13/the-cryptographic-doom-principle.html 20 Authenticated Encryption provides confidentiality, data integrity and data origin authentication there are sevaral AE modes for block ciphers · CCM, CWC, OCB, EAX, GCM http://cseweb.ucsd.edu/~mihir/papers/oem.pdf 21 Authenticated Encryption provides confidentiality, data integrity and data origin authentication · Galois/Counter mode for authenticated encryption http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm- spec.pdf 22 Authenticated Encryption provides confidentiality, data integrity and data origin authentication · Galois/Counter mode for authenticated encryption http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm- spec.pdf 22 Authenticated Encryption provides confidentiality, data integrity and data origin authentication · ChaCha20-Poly1305 algorithm as described in RFC 8439 · uses 256-bit key and a 96-bit nonce to encrypt a plaintext · ChaCha20 is used in counter mode to derive a key stream that is ⊕’d with the plaintext. 23 AEAD Authenticated Encryption with Associated Data · Allows authentication of both encrypted data and associated (plaintext) data · TLS 1.3 allows (there is another that is insecure) · AES-GCM · AES-CCM · Ghost R 34.12 2015 · ChaCha20-Poly1305 24