Bit flipping attack in hash function for message authentication

Allexj

5/31/24, 12:28 PM

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:

You have plaintext message and the encrypted hash.

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

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:

Why if I xor between plaintext hash and encrypted hash I get stuff that if decrypted gives 0?
What should I xor? Why doing this now the hash will be what I want?

1 + 2

xor

chosen-plaintext-attack

hash-signature

attack

fgrieu

6/1/24, 9:53 AM

The attack in the quote assumes E is a [stream cipher](https://en.wikipedia.org/wiki/Stream_cipher), e.g. a [block cipher](https://en.wikipedia.org/wiki/Block_cipher) in [CTR](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Counter_(CTR)) or [OFB](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Output_feedback_(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](https://en.wikipedia.org/wiki/Keystream), excluding the [IV](https://en.wikipedia.org/wiki/Initialization_vector).

Allexj

6/1/24, 11:13 AM

you are right @fgrieu

Score:4

Crypto

Sacha Servan-Schreiber

6/1/24, 7:31 AM

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})).$$

This is one explanation for steps 2 and 3, and can possibly generalize to other symmetric encryption schemes (beyond one-time pad). For a great exposition of generic authentication techniques, I recommend reading Chapter 9.4 of Boneh-Shoup.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Bit flipping attack in hash function for message authentication

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.