Hash functions, MACs and authenticated encryption Flashcards
What are hash functions?
Cryptographic functions used as building block for authentication
A public function H, such that:
- Simple and fast to compute
- H takes a message m input of arbitrary length, and computes a fixed length hash output H(m)
What are MACs?
symmetric key cryptographic mechanisms providing authentication and integrity services
What does authenticated encryption combine?
Confidentiality and authentication
Name 3 security properties of hash functions
Collision resistant
One-way (preimage resistant)
Second-preimage resistant
What does it mean to be collision resistant?
It should be infeasible (impractical) to find 2 different messages x1 and x2, with H(x1)=H(x2)
What does it mean to be preimage resistant (one-way)?
Given a value y, it should be infeasible to find any input x that gives H(x)=y
What does it mean to be second-preimage resistant?
Given a value x1, it should be infeasible to find a different x2 such that H(X1)=H(X2)
What can also be broken, if an attacker manages to break second-preimage resistance?
Collision resistance
What is the birthday paradox?
If we choose sqrt(M) values from a set of size M, the probability of getting 2 equal values are around 0.5
If H has the output size of 2^k, then 2^(k/2) trials are enough to find a collision with the probability of 0.5
Today, how many trials are considered infeasible, and because of this, how large should hash-outputs be to satisfy collision resistance?
2^128
This means that hash outputs should be 256 bits.
What are iterated hash functions?
Split input into fixed sized blocks
Operates on each block sequentially using the same function with fixed size inputs (as done with block ciphers)
What is the Merkle-Damgård construction?
Use a fixed-size compression function applied to multiple blocks of the message.
- Breaks message m into n-bit blocks m1 || m2 || … || mr
- Add padding and an encoding of the length of m. This may, or may not, add one block.
- Input each block into the compression function h along with chained output; use IV to get started
h(IV, m1) = n1
h(n1, m2) = n2
…
Produces in the end H(m)
How does a compression function h work?
Takes to input strings x1 and x2, and produces an n bit output string y
h(x1, x2) = n
What is the security of Merkle-Damgård construction?
If compression-function h is collision-resistant, then hash-function H is collision resistant
What are some weaknesses of Merkle-Damgård construction?
Length-extension attack: Once you have one collision, easy to find more
Sencond-preimage attacks are not as hard as they should be
What are the members of the MDx family?
MD2, MD4, MD5
All 128-bit output
All broken
What is SHA-0 and SHA-1
Secure Hash Algorithm
Based on MDx family
Both 160-bit output
Both are broke, have found collisions
What is the SHA-2 family?
Developed in response to (real or theoretical) attacks on MD5 and SHA-1
Different variations with different Hash- and block sizes
Describe the SHA-2 family
Block length: 512, 1024
Message length field: 64, 128
At least one bit of padding. After the first 1 in the padding, ‘0’ bits are added to achieve a exact number of blocks.
What is SHA-3?
Use of sponge construction instead of Merkle-Damgård
What are some properties that shows that hash is not encryption?
Hash computation aren’t dependent on a key
Not generally possible to go backwards to find the input
How can hash functions help with providing data authentication?
Authenticate the hash of a message to authenticate the message
Building blocks for message authentication codes (HMAC)
Building blocks for signatures.
How can the use of keys be combined with hash fnctions?
Can write hash functions that take a key s as an input:
H^s(x) = H(s, x)
It must be hard to find collision for a randomly generated key s
Key is NOT secret
Collision resistance must hold even if the adversary has the key
How can hashes be used to store passwords?
Store salted hashes of passwords
- pick random salt
- compute h = H(pass, salt)
- store (salt, h)
Can check if password is valid by:
h == H(password_input, salt)
If H is preimage resistant, pass is hard to retreive from H(pass)
What are MACs and what are they used for?
Message Authentication Code
Mechanisms that provides integrity and authentication
Describe how MACs work
key K and message M, MAC algorithm outputs a fixed-length tag:
T = MAC(K, M)
Symmetric key algorithm, send and recv have K
Sender sends (M, T), M may- or may not be encrypted.
Receiver computes T’ = MAC(M’, K)
Then compares the tags T’ = T
What is MAC unforgeability?
It is not feasible to producee a M and a T such that:
T = MAC(M, K) without knowing the K
What is unforgeability under chosen message attack?
Attacker is given access to a forging oracle
Attacker can input M and the MAC tag is returned:
T = MAC(M, K)
The unforgeability property says that it is not feasible for the attacker to produce a (M, T) pair that was not already asked to the Oracle
What is HMAC?
Built from iterated hash functions
Standardized, used in applications including TLS and IPsec
How is HMAC calculated?
HMAC(M, K) = H ((K xor opad) || H((K xor ipad) || M))
M: Message
K: Key, padded with zeroes to be the block size of H
opad: fixed string (0x5c5c5c…5c)
ipad: fixed string (0x363636…36)
||: denotes concatination of bit strings
When is HMAC unforgeable (secure)?
If H is collision resistant or H is a pseudorandom function
Name one type of attack that HMAC is designed to resist
Length extension attacks, even when H is a Merkle-Damgård hash function
What is a common usage of HMACs?
pseudorandom function for deriving keys in cryptographic protocols
What is authenticated encryption?
Dedicated algorithms that provide both confidentiality, and authenticity and integrity
For a shared key K between two parts, how can a message be sent with confidentiality, authentication and integrity?
Split key into 2 parts, K1 and K2
Encrypt with K1 (confidentiality)
Use K2 with a MAC (authenticity and integrity)
How can encryption and message authentication be combined?
3 ways:
Encrypt and MAC
MAC then encrypt
Encrypt then MAC
What is Encrypt and MAC?
encrypt M, apply MAC to M, send the two results
What is MAC then encrypt?
Apply MAC to M to get tag,
Encrypt M||T
Send ciphertext
What is encrypt then MAC?
Encrypt M to get ciphertext C
Then MAC C
Send 2 result
C = Enc(M, K1)
T = MAC(C, K2)
Send C||T
This is the safest approach
What are some weaknesses with encrypt and MAC?
May not achieve the most basic level of secrecy
Even strongly secure MAC does not guarantee secrecy
A MAC can leak information about m in the tag
What are some weaknesses with MAC then Encrypt?
Padding the message with the tag can cause 2 decryption errors:
- Incorrect padding
- Tag may not verify
An attacker can be able to distinguish between these two errors, and exploit this information
What is AEAD?
An AEAD algorithm is a symmetric key cryptosystem
What are the inputs and outputs of an AEAD?
Input:
M: Message (AEAD provides configentiality and authentication for M)
A: Associated data (provides authentication)
K: Shared key
Output:
Can contain different elements, such as ciphertext and tag
When using an AEAD algorithm, what is sent from the sender to the recipient?
O and A
When a receiver receives an AEAD message, what do they then do?
Either accept M and A, or report failure
What is Galois Counter Mode (GCM)
Block cipher mode providing AEAD
Combines CTR mode on a block cipher, with a keyed hash function GHASH
How does the GCM algorithm work?
GHASH Uses multiplication in the field GF(2^128)
Input: P, A (authenticated data), N (nonce)
u and v: values that are the minimum number 0s to expand A and C to complete number of blocks
output: C, T (tag), len_A, len_C (64 bit values)
What does Inc_32 do in GCM?
Increment the right-most 32-bit of the input string by 1 mod 2^32
How does GHASH work in GCM?
output = GHASH(X1, …, Xm)
operation *: multiplication in finite field GF(2^128)
HK = E(0^128, K) is the hash subkey
How is GCM decrypted?
Elements transmitted to receiver: C, N, T, A
Receiver compute tag T, with a shared key
Computed tag is checked with received tag
If tag is correct, plaintext can be recomputed by generating the same key stream, from CTR mode
What is key derivation?
User remembers a password that will be used to derive a key for encryption
What are dictionary attacks?
Attacker have access to a dictionary of passwords, sorted by approximate frequency of use.
Attacker iterates from most to least frequent passwords
What are a problem with storing encrypted passwords?
Where to store the key safely. If database/storage is compromised, key can be found and passwords retreived
What is the safest way to store passwords?
Hashes: h = H(password)
Easy to check if an entered password is the correct:
H(input) == H(password)
Hard to recover password from H(password), assuming H is preimage resistant
con: Attacker can store dictionary of pw and H(pw), and compare with stolen input_password
How can salted hashes be used to store passwords?
Pick random salt,
Store H(password, salt) and salt
What are some pros and cons of using salted hashes to store passwords?
Pro:
- Easy to validate entered password
- Hard to recover password from H
- attacker needs to store different dictionary for each salt
con:
- doesn’t slow down per-password attacks
What is PBKDF2?
Password Based Key Derivation Function 2
Uses hash, MAC or cipher
Combines pass + salt
Uses multiple iterations to slow down attacks
Can output key of arbitrary length
How is PBKDF2 constructed?
PBKDF2(P, pass, salt, c) = U1 xor U2 xor…xor Uc
U1 = F(pw, salt || 1)
Uj = F(pw, U_j-1) for j >= 2
F: Pseudorandom function (e.g. HMAC with SHA256)
What should any AEAD algorithm provide?
Confidentiality for M
Authentication for M and A
