# Bit flipping attack in hash function for message authentication

In this picture we have a use of a hash function for message authentication.

M is plaintext message. H is hash function. E is encryption block with K symmetric key. || is concatenation of plaintext M with the output of E.

Is it true that this is vulnerable to bit flipping attack? I'm not sure how though.

This is what they said to me:

You do the bit flipping on the encrypted hash in such a way that it is as you want the hash to be

In a nutshell:

1. You have plaintext message and the encrypted hash.

2. If you xor between the plaintext hash and the encrypted hash you get "X" that if decrypted gives you all bytes to 0

3. So to flip the bits you just xor with the correct hash first and then xor with the malicious hash

But the 2 and 3 are absolutely unclear to me:

1. Why if I xor between plaintext hash and encrypted hash I get stuff that if decrypted gives 0?

2. What should I xor? Why doing this now the hash will be what I want?

• The attack in the quote assumes E is a stream cipher, e.g. a block cipher in CTR or OFB mode. Also it names "encrypted hash" the subpart of that stream cipher's ciphertext that's the XOR of the hash and the keystream, excluding the IV.
– fgrieu
Commented Jun 1, 2023 at 9:53
• you are right @fgrieu Commented Jun 1, 2023 at 11:13

I believe a counter example could be derived as follows: Suppose that your encryption scheme is a one-time pad, then you have $$E(K, M) = K \oplus M$$. In your scheme, the output is $$(M, E(K, H(M))) = (M, K \oplus H(M))$$. Then, observe that an adversary can authenticate a message $$\hat{M} \neq M$$ as:
$$(\hat{M}, \underbrace{(K \oplus H(M))}_{\text{original tag}} \oplus H(M) \oplus H(\hat{M})) = (\hat{M}, K \oplus H(\hat{M}))= (\hat{M}, E(K, H(\hat{M})).$$