2
$\begingroup$

I have a question in mind. Suppose we have a collision-resistant unkeyed-hash function $H(·)$ which outputs a 128-bit digest, and a semantic secure symmetric encryption $E(·,·)$ in the following way, we can design a Message Authentication Code (MAC) in this manner, so given a message $m$ and the secret key $k$, the mac is the encrypted digest, $t=E(k, H(m))$.

Is it susceptible to forgery if the encryption is in CBC mode or CTR mode? My intuition tells me that it is possible, but I have no idea of constructing the forgery for them. Any suggestion is welcome, thanks!

$\endgroup$
  • $\begingroup$ What should run in CTR / CBC mode? The $E$ function? $\endgroup$ – SEJPM Sep 28 '16 at 14:02
  • $\begingroup$ @SEJPM: Yes you are right. $\endgroup$ – freak_warrior Sep 28 '16 at 14:03
  • $\begingroup$ Trivial attack against CTR: Modify the message as you wish, calculate the XOR of the old and the new hash and XOR that into the encrypted hash. Voila, you have a forgery. $\endgroup$ – SEJPM Sep 28 '16 at 14:04
  • $\begingroup$ @SEJPM: Sorry, but can you explain it further? Equations/diagrams are better. $\endgroup$ – freak_warrior Sep 28 '16 at 14:07
  • $\begingroup$ What is the block size of the underlying cipher? 128-bit? Is the IV (for the modes) always prepended to the cipher text? (I need this info to see how hard it is to attack CBC in this scenario and then I'll write a full answer). $\endgroup$ – SEJPM Sep 28 '16 at 14:09
5
$\begingroup$

An attacker can trivial forge the MAC of any message, given one valid MAC of a known message, in either CBC mode or CTR mode.

Let us assume that the attacker knows a message $m$ and its MAC $E(k, H(m)) = IV, E(k, IV, H(m))$; he has a message $m'$ he wants to form the message to. He computes $\delta = H(m) \oplus H(m')$, then:

  • For CTR mode, he computes $IV, E(k, IV, H(m)) \oplus \delta$, when this is decrypted, this results in $H(m) \oplus \delta = H(m')$

  • For CBC mode, we computes $IV \oplus \delta, E(k, IV, H(m))$; because of how CBC mode works, the first block (128 bits for AES) are the first 128 bits of $H(m) \oplus \delta = H(m')$; because $H$ generates only 128 bits, that's the entire message (nit: depending on CBC mode is padded, that may also be an issue; I'm assuming no padding).

Also, there is no such thing as a "collision resistant hash function with 128 bits output"; assuming that the hash function takes an arbitrary bitstring, we can find a collision in $O(2^{64})$ time, and that's generally considered feasible.

$\endgroup$
  • $\begingroup$ When reading this answer please note: The second attack doesn't apply if the IV isn't available for modification. $\endgroup$ – SEJPM Sep 28 '16 at 14:17
  • 1
    $\begingroup$ @SEJPM: on the other hand, freak_warrior stated that $E$ was a semantically secure mechanism, and so $E$ must be randomized somehow. It could be done by, say, passing an encoding of the IV, however that's starting to get away from standard CBC mode... $\endgroup$ – poncho Sep 28 '16 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.