Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

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
Q

What are MACs and what are they used for?

A

Message Authentication Code

Mechanisms that provides integrity and authentication

26
Q

Describe how MACs work

A

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
Q

What is MAC unforgeability?

A

It is not feasible to producee a M and a T such that:

T = MAC(M, K) without knowing the K

28
Q

What is unforgeability under chosen message attack?

A

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
Q

What is HMAC?

A

Built from iterated hash functions

Standardized, used in applications including TLS and IPsec

30
Q

How is HMAC calculated?

A

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
Q

When is HMAC unforgeable (secure)?

A

If H is collision resistant or H is a pseudorandom function

32
Q

Name one type of attack that HMAC is designed to resist

A

Length extension attacks, even when H is a Merkle-Damgård hash function

33
Q

What is a common usage of HMACs?

A

pseudorandom function for deriving keys in cryptographic protocols

34
Q

What is authenticated encryption?

A

Dedicated algorithms that provide both confidentiality, and authenticity and integrity

35
Q

For a shared key K between two parts, how can a message be sent with confidentiality, authentication and integrity?

A

Split key into 2 parts, K1 and K2

Encrypt with K1 (confidentiality)
Use K2 with a MAC (authenticity and integrity)

36
Q

How can encryption and message authentication be combined?

A

3 ways:

Encrypt and MAC
MAC then encrypt
Encrypt then MAC

37
Q

What is Encrypt and MAC?

A

encrypt M, apply MAC to M, send the two results

38
Q

What is MAC then encrypt?

A

Apply MAC to M to get tag,
Encrypt M||T
Send ciphertext

39
Q

What is encrypt then MAC?

A

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
Q

What are some weaknesses with encrypt and MAC?

A

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
Q

What are some weaknesses with MAC then Encrypt?

A

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
Q

What is AEAD?

A

An AEAD algorithm is a symmetric key cryptosystem

43
Q

What are the inputs and outputs of an AEAD?

A

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
Q

When using an AEAD algorithm, what is sent from the sender to the recipient?

A

O and A

45
Q

When a receiver receives an AEAD message, what do they then do?

A

Either accept M and A, or report failure

46
Q

What is Galois Counter Mode (GCM)

A

Block cipher mode providing AEAD

Combines CTR mode on a block cipher, with a keyed hash function GHASH

47
Q

How does the GCM algorithm work?

A

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
Q

What does Inc_32 do in GCM?

A

Increment the right-most 32-bit of the input string by 1 mod 2^32

49
Q

How does GHASH work in GCM?

A

output = GHASH(X1, …, Xm)

operation *: multiplication in finite field GF(2^128)

HK = E(0^128, K) is the hash subkey

50
Q

How is GCM decrypted?

A

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
Q

What is key derivation?

A

User remembers a password that will be used to derive a key for encryption

52
Q

What are dictionary attacks?

A

Attacker have access to a dictionary of passwords, sorted by approximate frequency of use.

Attacker iterates from most to least frequent passwords

53
Q

What are a problem with storing encrypted passwords?

A

Where to store the key safely. If database/storage is compromised, key can be found and passwords retreived

54
Q

What is the safest way to store passwords?

A

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
Q

How can salted hashes be used to store passwords?

A

Pick random salt,
Store H(password, salt) and salt

56
Q

What are some pros and cons of using salted hashes to store passwords?

A

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
Q

What is PBKDF2?

A

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
Q

How is PBKDF2 constructed?

A

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
Q

What should any AEAD algorithm provide?

A

Confidentiality for M

Authentication for M and A

Cryptography (15 decks)

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