MAC & MDC

Question 1

What are the main categories of modification check values?

Answer 1

Modification Detection Code (MDC) and Message Authentication Code (MAC)

Question 2

What does MDC stands for?

Answer 2

It stands for Modification Detection Code

Question 3

What does MAC stands for?

Answer 3

It stands for Message Authentication Code

Question 4

Why not use traditional methods (as CRC; Parity; etc) to check if a message was modified?

Answer 4

Messages modified on purpose cannot be detected using those tecniches - intentional modification can’t be detected.

Question 5

What are hash functions?

Answer 5

Hash functions are functions which compress input to a shorter output.

Question 6

What are the main requirements for hash functions?

Answer 6

Easy computation - compression level - collision resistance - locality-sensitivity

Question 7

What are cryptographic hash functions?

Answer 7

Cryptographic hash functions are a special class of hash functions which have certain properties which make them suitable for security applications and can be used to compute modification detection codes.

Question 8

What are the extra propreties which a cryptographic hash function have to additionally satisfy?

Answer 8

Pre-image resistance; 2nd pré-image resistance and collision resistance

Question 9

What is pre-image resistance?

Answer 9

It is computionally infeasible to find an x such that h(x) = y for essentially all pre-specified outputs y.

Question 10

What is second pre-image resistance?

Answer 10

Given x it is computionally infeasible to find any second input x’ with x not equal to x’ such that h(x) = h(x’)

Question 11

What is collision resistance?

Answer 11

It is computationally infeasible to find any pair (x;x’) with x different from x’ such that h(x)=h(x’)

Question 12

Why messages authentication codes are important?

Answer 12

It is not only important to know that data changed because it is as important to know where it is from.

Question 13

What is Message authentication code?

Answer 13

A message authentication code algorithm is a familly of functions hk parameterized by a secret key k with the following properties: compression; ease of computation; and computation-resistance.

Question 14

What is compression in the scope of MAC algorithms?

Answer 14

Is the property which says that hk maps an input x of arbitrary finite bitlength to an output hk(x) of fixed bitlength - called MAC

Question 15

What is Ease of computation in the MAC scope?

Answer 15

is the property that given k and x and a known function family hk the value hk(x) is easy to compute

Question 16

What is Computation-resistance in the MAC scope?

Answer 16

it is a property that says that for every fixed allowed but unknown value of K; given zero or more text-MAC pairs (xi;hk(xi)) it is computationally infeasible to compute a text-mac pair (x;hk(x)) for any new input x different from xi

Question 17

Does computational-resistance implies the property of key non-recovery?

Answer 17

Yes since k cannot be recovered from pairs (xi;hk(xi)

Question 18

Does key non-recovery implies computational-resistance?

Answer 18

No as the key k need not always to be recovered to forge message authentication code.

Question 19

Is XOR of 64-bit values a secure message authentication code?

Answer 19

No since it requires only the brute force effort of 2^(55) operations to obtain the key. Also if an attacker can get a pair (m;Ck(m)) it can compute a valid message computing yn = [y1 xor y2 xor … xor x(n-1) xor delta(m) ] and m’ = (y1…yn) and sending (m’;Ck(m)) and the receiver will accept this as a valid MAC

Question 20

What is the main application of modification detection code?

Answer 20

Modification detection code (MDC) represents a digital fingerprint [which can be signed with a private key e.g. RSA or ElGamal algorithm] and it is not possible to construct two messages with the same fingerprint so that given signed fingerprint cannot be reused by an attacker

Question 21

What is the mais application os message authentication code?

Answer 21

A message authentication code over a message m directly certifies that the sender of the message possesses the secret key k and the message could not have been modified without knowledge of that key.

Question 22

Depending on the application which further requirement have to be met despite pre-image resistance and second image resistance and collision resistance?

Answer 22

partial pre-image resistance.

Question 23

What is partial pre-image resistance?

Answer 23

Even if only a part of the input (say t bits) is unknown it should take on the avarage 2^(t-1) operations to find these bits

Question 24

What does the birthday phenomenon have to do with modification detection codes (MDCs)?

Answer 24

the number k of values one needs to randomly choose in order to obtain at least one pair of identical values is on the order of sqr(n) if there are n possible different values.

Question 25

Explain how can one attack a modification detection codes (MDCs) if he/she know a pair m1 and mdc(m1).

Answer 25

He/she can calculate the mdc(m2) of a message m2 and then start to change the message m2 and m1 to m2’ and m1’ (adding spaces or non-important signals) and once he or she could find the same mdc it ask to sign m1’ and then use it to sign m2’ [this would need an effort of sqr(number of possible values).