Description
0 CBC-MAC
Write the basic construction of CBC-MAC.
-
Merkle-Damgard
Let h : f0; 1gn+t ! f0; 1gn be a xed-length compression function. Suppose we forgot a few features of Merkle-Damgard and construct H as follows:
Value x is input.
Split x into y0; x1; : : : ; xk. Where y0 is n bits and xi (for i = 1; : : : ; k) is t bits.. The last piece xk may be padded with zeroes.
For i = 1; : : : ; k, set yi = h(yi 1jjxi). Output yk.
It’s similar to Merkle-Damgard except no IV and the nal padding block is missing.
-
Describe an easy way to nd two messages that are broken up into the same number of pieces, which have the same hash value under H.
-
Describe an easy way to nd two messages that are broken up into a di erent number of pieces, which have the same hash value under H. Hint: Pick any string of length n + 2t, and nd a shorter string that collides with it.
Neither of your collisions above should involve nding a collision in h!
-
Hash Functions
I designed H : f0; 1g ! f0; 1gn. I make H(x) = x if x is n-bit string { but assume H’s behavior is more complicated on strings of other lengths. This way we know there are no collisions among n-bit strings. Is this a good design decision?
-
MAC
Prove that the following modi cations of basic CBC-MAC do not yield a secure MAC (even for xed-length messages).
1
-
Mac outputs all blocks t1; : : : ; t‘ rather than just t‘. Veri cation only checks if t‘ is correct.
-
A random initial block is used each time a message is authenticated. That is, choose a uniform t0 2 f0; 1gn, run basic CBC-MAC over the \message” t0; m1; : : : ; m‘ and output tag ht0; t‘i. Veri cation is done in a natural way.
-
Digital Signature
|
Let ( |
G;S;V |
) be a secure signature scheme with |
message space |
f |
0; 1 |
g |
n, and security parameter |
||
|
. Let (pk0; sk0) $ G(1 ) and (pk1; sk1) $ G(1 |
) be two pairs of signing/veri cation keys. |
||||||||
Which of the following are secure signature schemes? Show an attack or prove security.
-
(S1; V1):
Sign. S1((sk0; sk1); m) : Output (S(sk0; m); S(sk1; m)).
Verify. V1((pk0; pk1); m; ( 0; 1)): Output 1 if (V (pk0; m; 0) _ V (pk1; m; 1)), 0 otherwise.
I.e., the veri cation accepts if one of the two signatures accepts.
-
(S2; V2)
Sign. S2((sk0; sk1); (mL; mR)): Output (S(sk0; mL); S(sk1; mR)).
Verify. V2((pk0; pk1); (mL; mR); ( 0; 1)): Output 1 if (V (pk0; mL; 0)^V (pk1; mR; 1)), 0 otherwise. I.e., both veri cations must accept.
2
