Untitled
CM30173: Example sheet 5
27th February
All questions relate to cryptographic hashes. Remember to have a look at the description of
MD5 in RFC 1321, it isn’t long and you don’t need to learn it in any way — just have a look
so you can see the detail of the process. If you are feeling keen you might try implementing
the algorithm in a language of your choice.
1. Let g be a collision resistant MDC which produces message digests of bitlength n. Define
a new MDC h which produces message digests of length n + 1:
h(x) =
{
1 || x if x has bitlength n
0 || g(x) otherwise.
Argue that h is collision resistant but not preimage resistant.
2. [Question 4.11 p. 158 from Stinson:]
A message authentication code can be produced by using a block cipher in CFB mode
instead of CBC mode. Given a sequence of plaintext blocks, x1, . . . , xn, suppose we define
the initialization vector IV to be x1. Then encrypt the sequence x2, . . . , xn using key k in
CFB mode, obtaining the ciphertext sequence y1 · · · yn−1 (note that there are only n − 1
ciphertext blocks). Finally, define the MAC to be ek(yn−1). Prove that this MAC is
identical to CBC-MAC, which was presented in Section 4.4.2.
3. In lecture 8 it was explained that to achieve data integrity of encrypted communication
we compute
y = ek(x‖h(x)).
In lecture 9 I mentioned that we could replace the MDC in the above equation with a
MAC:
y = ek1(x‖hk2(x)) (1)
I noted that there were downsides to doing this.
In equation (1) take encryption to be CBC encryption with key k and IV v. Let the keyed
hash be CBC-MAC using the same block cipher, key and IV.
(a) Show that the encryption and MAC calculation can take place simultaneously
(b) Show that this combination of encryption mode and MAC provides no assurance of
data integrity