Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Cryptography > Hash functions, MACs and authenticated encryption > Flashcards

Hash functions, MACs and authenticated encryption Flashcards

1
Q

What are hash functions?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are MACs?

A

symmetric key cryptographic mechanisms providing authentication and integrity services

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does authenticated encryption combine?

A

Confidentiality and authentication

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Name 3 security properties of hash functions

A

Collision resistant
One-way (preimage resistant)
Second-preimage resistant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does it mean to be collision resistant?

A

It should be infeasible (impractical) to find 2 different messages x1 and x2, with H(x1)=H(x2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does it mean to be preimage resistant (one-way)?

A

Given a value y, it should be infeasible to find any input x that gives H(x)=y

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What does it mean to be second-preimage resistant?

A

Given a value x1, it should be infeasible to find a different x2 such that H(X1)=H(X2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What can also be broken, if an attacker manages to break second-preimage resistance?

A

Collision resistance

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the birthday paradox?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Today, how many trials are considered infeasible, and because of this, how large should hash-outputs be to satisfy collision resistance?

A

2^128

This means that hash outputs should be 256 bits.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are iterated hash functions?

A

Split input into fixed sized blocks

Operates on each block sequentially using the same function with fixed size inputs (as done with block ciphers)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the Merkle-Damgård construction?

A

Use a fixed-size compression function applied to multiple blocks of the message.

  1. Breaks message m into n-bit blocks m1 || m2 || … || mr
  2. Add padding and an encoding of the length of m. This may, or may not, add one block.
  3. 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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How does a compression function h work?

A

Takes to input strings x1 and x2, and produces an n bit output string y

h(x1, x2) = n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the security of Merkle-Damgård construction?

A

If compression-function h is collision-resistant, then hash-function H is collision resistant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are some weaknesses of Merkle-Damgård construction?

A

Length-extension attack: Once you have one collision, easy to find more

Sencond-preimage attacks are not as hard as they should be

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the members of the MDx family?

A

MD2, MD4, MD5

All 128-bit output

All broken

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is SHA-0 and SHA-1

A

Secure Hash Algorithm

Based on MDx family

Both 160-bit output

Both are broke, have found collisions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the SHA-2 family?

A

Developed in response to (real or theoretical) attacks on MD5 and SHA-1

Different variations with different Hash- and block sizes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Describe the SHA-2 family

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is SHA-3?

A

Use of sponge construction instead of Merkle-Damgård

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are some properties that shows that hash is not encryption?

A

Hash computation aren’t dependent on a key

Not generally possible to go backwards to find the input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

How can hash functions help with providing data authentication?

A

Authenticate the hash of a message to authenticate the message

Building blocks for message authentication codes (HMAC)

Building blocks for signatures.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How can the use of keys be combined with hash fnctions?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

How can hashes be used to store passwords?

A

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)

25
What are MACs and what are they used for?
Message Authentication Code Mechanisms that provides integrity and authentication
26
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
27
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
28
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
29
What is HMAC?
Built from iterated hash functions Standardized, used in applications including TLS and IPsec
30
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
31
When is HMAC unforgeable (secure)?
If H is collision resistant or H is a pseudorandom function
32
Name one type of attack that HMAC is designed to resist
Length extension attacks, even when H is a Merkle-Damgård hash function
33
What is a common usage of HMACs?
pseudorandom function for deriving keys in cryptographic protocols
34
What is authenticated encryption?
Dedicated algorithms that provide both confidentiality, and authenticity and integrity
35
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)
36
How can encryption and message authentication be combined?
3 ways: Encrypt and MAC MAC then encrypt Encrypt then MAC
37
What is Encrypt and MAC?
encrypt M, apply MAC to M, send the two results
38
What is MAC then encrypt?
Apply MAC to M to get tag, Encrypt M||T Send ciphertext
39
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
40
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
41
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
42
What is AEAD?
An AEAD algorithm is a symmetric key cryptosystem
43
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
44
When using an AEAD algorithm, what is sent from the sender to the recipient?
O and A
45
When a receiver receives an AEAD message, what do they then do?
Either accept M and A, or report failure
46
What is Galois Counter Mode (GCM)
Block cipher mode providing AEAD Combines CTR mode on a block cipher, with a keyed hash function GHASH
47
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)
48
What does Inc_32 do in GCM?
Increment the right-most 32-bit of the input string by 1 mod 2^32
49
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
50
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
51
What is key derivation?
User remembers a password that will be used to derive a key for encryption
52
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
53
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
54
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
55
How can salted hashes be used to store passwords?
Pick random salt, Store H(password, salt) and salt
56
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
57
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
58
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)
59
What should any AEAD algorithm provide?
Confidentiality for M Authentication for M and A

Cryptography (15 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions