# Why do we need Hash by key?

(i'm just trying to find what am I missing...)

Assuming John have a clear text message , he can create a regular hash ( like md5 , or sha256) and then encrypt the message.

John can now send Paul the message + its (clear text)hash and Paul can know if the message was altered. ( decrypt and then compare hashes).

Even if an attacker can change the encrpyted data ( without decrypt) - - when paul will open the message - and recalc the hash - it wont generate the same hash as the one john sent him.

so why do we need hash by key ?  • You say that "John encrypts the message", but you skate over how he does this. Do they have a pre-shared secret, or are you assuming some kind of asymmetric cryptosystem, where John encrypts to Paul's public key? I ask because it makes a difference to the answer. – MadHatter Nov 10 '12 at 8:10
• One thing that hasn't been mentioned yet is a padding oracle attack. The easiest remedy is to verify the authenticity of the ciphertext before passing it to your decryption function, which can't be done by a hash of the plaintext. – Stephen Touset Nov 11 '12 at 2:05

The question is about an attempt to augment an encryption scheme with an integrity-protection measure, by additionally transferring the hash $H=\mathtt{Hash}(P)$ of the plaintext $P$ together with the ciphertext $C=\mathtt{ENC}(P)$ of the original encryption scheme; and having the recipient of an alleged $(C,H)$ obtain the alleged $P=\mathtt{DEC}(C)$, and accept that $P$ as genuine if $\mathtt{Hash}(P)=H$.

This attempt fails disastrously:

1. The original encryption scheme is greatly weakened, for $\mathtt{Hash}(P)$ reveals information about the plaintext $P$. An attacker Eve can test with high confidence if a guess of $P$ is correct! If $P$ legitimately sent by Alice is the result of a yes-or-no vote, or otherwise is one in a moderate list of possibilities (e.g. a password), Eve can now recover $P$ without attacking the original encryption scheme at all.

2. The change provides no integrity protection when used with a public-key encryption scheme, where Alice enciphers a message to Bob using Bob's public key. Eve can choose any message she desires, hash it, and encipher it using Bob's public key, just like Alice.

3. Even considering symmetric encryption schemes, in many important use cases, the change fails to provide integrity protection against an Eve able to guess/obtain/choose the plaintext, or part of it; these are standard hypothesis, and we have seen with 1 that guesses have been made verifiable by the attempted strengthening. Examples, among many:

a. Many schemes, including the One Time Pad, all Stream Ciphers, and all Block Ciphers employed in the OFB or CTR mode of operation, have the property that $\mathtt{ENC}(P\oplus X)=\mathtt{ENC}(P)\oplus X$ (where $\oplus$ is bitwise Exclusive-OR). In these cases, Eve is able to change the message $P$ to $P'$ of the same length: Eve uses $\mathtt{Hash}(P)$ to confirm her guess of $P$, chooses $P'$ she want to substitute, computes $\mathtt{Hash}(P')$, and computes $C'=\mathtt{ENC}(P')$ as $C'=\mathtt{ENC}(P)\oplus P\oplus P'$.

b. Most schemes have the property that truncating the ciphertext correspondingly truncates the plaintext (often, with restriction to truncation at block boundaries). An adversary unable to guess the end of a message, but knowing the start (because that is conventional, or transmitted in clear alongside) can truncate the ciphertext, and compute the corresponding plaintext's hash. Thus Eve can make a forgery that deciphers to the truncated original plaintext, and passes the hash check.

c. Many symmetric encryption schemes, including all Block Ciphers employed in the ECB, CBC or CFB mode of operation, have the property that decryption of a segment of the ciphertext leads to the corresponding fragment of the plaintext (often, with restriction to segmenting at block boundaries, and need to adjust the IV). If Eve can persuade Alice to encipher some message $P||P'$ of Eve's choice (a standard assumption; say, $P$ is a nice image that a viewing program will show when fed with the file $P||P'$), Eve now has $C'=\mathtt{ENC}(P')$ for $P'$ of her choice, and can compute the matching $\mathtt{Hash}(P')$.

4. Many common hashes (including MD5, SHA-1, and all SHA-2 hashes) have the length-extension property, which is that from knowledge of the length of $P$ and $\mathtt{Hash}(P)$, it is easy to determine a short $F$ such that for any $X$, it is easy to compute $\mathtt{Hash}(P||F||X)$. For some symmetric encryption schemes and plausible assumptions (similar to 3c), it might be possible to extend an unknown $P$ with some $F||X$, deduce $\mathtt{ENC}(P||F||X)$ from intercepts, and compute $\mathtt{Hash}(P||F||X)$ from the length-extension property.

5. The scheme is not protected at all against replay of earlier messages.

A Message Authentication Code (or keyed hash, which includes HMAC) can be used instead of the hash to fix 1/2/3/4 (but something extra is needed for 5). The key used for the MAC should be different from the key used for the encryption scheme, in particular if the MAC has building blocks in common with the encryption scheme.

If the attacker was hypothetically capable of meaningfully altering ciphertext, then he probably also has the ability to just compute the hash of the modified data (since the hash does not use any secret information), and replace the existing hash by this one, which would defeat your integrity system.

This is easy with encryption modes of operation which are based on a keystream, because if some existing data is known - which is very often the case - it can trivially be changed via the well-known property that $((P_1 \oplus K) \oplus (P_2 \oplus K)) = P_1 \oplus P2$. A robust integrity system is paramount in these situations.

With a keyed hash (also called a hash-based message authentication code, or HMAC for short), the encryption key itself (which is not known to the attacker) is used within the hash function, which makes it impossible for the attacker to forge a valid fingerprint of any data he tries to alter, therefore if he tries to mess with your ciphertext, you will be able to detect it and take the necessary measures (disconnect, etc...)

• But if John sends paul the encrypted message and the Devil change the encryprted message - but the devil can't create a valid hash because he dont see the clear text. so paul can detect if the message was altered....no ????( when he will create a new hash , he will see that it is not as the same as john sent him) – Royi Namir Nov 10 '12 at 8:57
• can you please answer my last comment ? – Royi Namir Nov 10 '12 at 9:06
• @RoyiNamir Believe it or not, it is sometimes possible for the Devil to completely change the clear text to exactly what he wants, without knowing the key. He can then calculate the valid hash for this new, forged clear text and send that to Paul instead of the old hash. In cryptography, we don't actually mind if the Devil can change the messages to whatever he wants - all that matters is that we can detect these changes reliably, and make sure he can't actually read the old messages. – Thomas Nov 10 '12 at 9:08
• So If paul gets a message +hash. how can he know if it is from the Devil or from John ? both have valid hashes ...? – Royi Namir Nov 10 '12 at 9:12
• @RoyiNamir: Often the Devil has a good guess as what the original message was, and with your plaintext hash, she can even verify this guess. Of course, if your message contains an unguessable random number, this will not work, but does really every message contain such one? – Paŭlo Ebermann Nov 12 '12 at 19:12