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!

Improve this question
$\endgroup$
6
  • $\begingroup$ What should run in CTR / CBC mode? The $E$ function? $\endgroup$
    – SEJPM
    Commented Sep 28, 2016 at 14:02
  • $\begingroup$ @SEJPM: Yes you are right. $\endgroup$
    – meta_warrior
    Commented Sep 28, 2016 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
    Commented Sep 28, 2016 at 14:04
  • $\begingroup$ @SEJPM: Sorry, but can you explain it further? Equations/diagrams are better. $\endgroup$
    – meta_warrior
    Commented Sep 28, 2016 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
    Commented Sep 28, 2016 at 14:09

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When reading this answer please note: The second attack doesn't apply if the IV isn't available for modification. $\endgroup$
    – SEJPM
    Commented Sep 28, 2016 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
    Commented Sep 28, 2016 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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