Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

It seems that even in MAC-then-encrypt systems like SSL, something like HMAC is used rather than a plain hash. Why?

Suppose we use some stream cipher; then why can't we use $Encrypt(m | H(m))$ as the MAC-then-encrypted version of the message? Assuming no bad relations between $Encrypt$ and $H$, what are the possible weaknesses? It seems that in this case we are encrypting the hash with part of a secretly keyed stream cipher keystream, and the hash is secure; does this not fulfil an approximation of the ideal MAC?

This must be somehow bad, since no secure protocol seems to use it. Why?

share|improve this question
1  
possible duplicate of Does CBC encryption of a hash provide authenticity? –  D.W. May 31 at 2:15
    
@e-sushi, this question asks whether $\text{Encrypt}(M || H(m))$ is secure, where $H$ is a hash (not a MAC). The question I linked to asks whether $E_k(M || H(M))$ is secure. It's the same question. OK, the latter question focuses on CBC encryption, but the answers there show an attack when $\text{Encrypt}$ is CBC mode encryption, which already answers this question and shows that this question's scheme is not secure in general. And the case of stream ciphers is already handled by crypto.stackexchange.com/q/6069/351. So this question is completely subsumed by existing questions. –  D.W. May 31 at 18:10
2  
@D.W.: I agree that these questions have substantial overlap, but it's not obvious which one(s) of them should be deemed canonical. In particular, given that this question seems to have the most thorough and highly voted answer (not that the others don't have good answers too), there's an argument to be made for closing both of the earlier questions as duplicates of this one. –  Ilmari Karonen May 31 at 19:39
    
@IlmariKaronen, Good point! This is worth considering and discussing. Looks like there are many possibilities. Another possibility that might make even more sense would be to close this question as a dup of crypto.stackexchange.com/q/6069/351, since they are both specifically about stream ciphers. (I do not suggest closing Gilles' older question as a dup of this one; I think Gilles' older question is better-written and better-researched, whereas I find this question a bit confusing and hard to follow.) –  D.W. Jun 2 at 5:21

4 Answers 4

up vote 13 down vote accepted

$Encrypt(m|H(m))$ is not an operating mode providing authentication; forgeries are possible in some very real scenarios. Depending on the encryption used, that can be assuming only known plaintext.

Here is a simple example with $Encrypt$ a stream cipher, including any block cipher in CTR or OFB mode. Mallory wants to sign some message $m$ of his choice.

  1. Mallory intercepts a cryptogram $Encrypt(m_0|H(m_0))$ of the form $IV|C_0$, with $m_0$ known and at least the size of $m$; $C_0$ is the size of $m_0|H(m_0)$ and the eXclusive-OR of the later with keystream $K$ function of $IV$.
  2. Mallory computes $K$ as $C_0\oplus(m_0|H(m_0))$, truncated to the size of $m|H(m)$ if $m$ is shorter than $m_0$.
  3. Mallory computes $C=(m|H(m))\oplus K$.
  4. Mallory replaces the cryptogram by $IV|C$, which will pass the authentication check of the receiver and decipher as $m$.

Another example: assume $Encrypt$ is AES in CBC, CFB, or OFB mode with random $IV$; and $H$ is SHA-256. Mallory wants to sign some message $m$ of his choice, with size $s$ blocks of 16 bytes (the block size of AES).

  1. Mallory computes $m_1=m|H(m)$, of $s+2$ blocks.
  2. Mallory manages to inserts $m_1$ into some message $m_0|m_1|m_2$ sent by a legitimate holder of the AES key, who chooses $m_0$ and $m_2$, with $m_0$ non-empty and of size multiple of the block size known by Mallory.
  3. Mallory intercepts the cryptogram $IV|C$.
  4. From $C$ Mallory removes one less block than in $m_0$; keeps the next block, forming $\widetilde{IV}$; then the next $s+2$ blocks, forming $\widetilde{C}$.
  5. Mallory replaces the cryptogram with $\widetilde{IV}|\widetilde{C}$, which will pass the authentication check of the receiver and decipher as $m$.

That scenario is not far fetched: if Mallory is in a position to choose some file in a CD-ROM image, like a movie he pretends will be a promotion, then he can make a fake enciphered-and-authenticated CD-ROM image, which will appear as an authentic CD-ROM image and decipher to something Mallory chooses arbitrarily.

If $m_0$ can be empty (which is less realistic), an even simpler attack works: $\widetilde{IV}$ is $IV$, $\widetilde{C}$ is the first $s+2$ blocks of $C$.


The title of the question asks if $Encrypt(m|H(m))$ is a secure MAC, which strictly speaking means that $Encrypt(m|H(m))$ is appended to $m$ sent in clear. This is not secure either, and succumbs to trivial variants of the above.

share|improve this answer
    
The first attack is the type of horribly devastating attack I was expecting! Thanks! –  user54609 May 28 at 10:41
    
Certainly CTR mode encryption offers no authentication, but when using OFB, wouldn't it be impossible for anyone without the encryption key to change any block other than the last without garbling the succeeding block [and thus changing the hash value in unknowable fashion]? –  supercat May 28 at 22:56
    
@supercat Do you not mean CFB? –  user54609 May 29 at 1:19
    
@supercat: neither of OFB, CFB, CBC has the property that you state. Rather, changes in plaintext propagate indefinitely, but changes in ciphertext propagate to 1 block (OFB) or 2 blocks (CFB,CBC). PCBC has the property that you state; however the second attack with $m_0$ empty still works. –  fgrieu May 29 at 13:21
    
@fgrieu: I sometimes get the different chaining modes confused. Still, would it be fair to say that the value of encryption for authentication depends upon the chaining method used? Certainly there are chaining approaches where the only way to exploit a known plaintext/ciphertext pair to create a different valid ciphertext would be to use that pair to find the key [which is presumed to be difficult]. –  supercat May 29 at 14:59

Two things going on that together may make plain-hash-then-encrypt insecure.

First, the distinction between secure MACs and hashes, which is that a hash function may allow you to derive $H(m')$ from $H(m)$ even if you only know how $m'$ and $m$ differ. Length extension attacks on SHA-1 and SHA-2 are a practical way that can happen, but there could be others if the hash function doesn't specifically guarantee that there isn't.

Second, stream ciphers allow you to make deterministic changes to the plaintext. Specifically, you can flip any bits you like in the ciphertext and they'll be flipped in the decrypted plaintext as well (assuming the cipher uses XOR as most do).

Put those together and it could be possible to e.g. flip the last message bit, determine which bits that would flip in the hash, then flip those.

Additionally, even if you chose a secure MAC as $H$, having the hash inside encryption means you need to decrypt and hash before deciding whether the ciphertext has been corrupted, increasing retransmission latency on a noisy channel compared to encrypt-then-hash.

share|improve this answer

…something like HMAC is used rather than a plain hash.

HMAC is a keyed hash… which means it additionally provides unforgeability.

A “plain hash” (which I assume to include cryptographic hashes) merely provides collision resistance, while a HMAC provides both collision resistance and unforgeability… because an attacker is unable to calculate a new, valid HMAC of a modified/forged message ($m$), unless that attacker also has the needed key to produce a new, valid, and verifiable HMAC.

If you would use a (let’s just call it) “unkeyed” hash, an attacker would be able to modify/change the message ($m$) if that attacker would have (for example) guessed or intercepted your encryption key, or if that attacker would be able to break your encryption in any way. The problem (better: security issue) in this case is that you would potentially be accepting and decrypting ciphertext from the attacker instead of the expected sender, and you would never learn about the fact that the message $m$ has been messed with. Your simple hash would be useless… as all it provides is collision resistance and that’s it.

When you use a HMAC, that same attacker would additionally have to successfully guess/intercept the key for your HMAC (that is, unless you use the same key for both the encryption and the HMAC… which certainly isn’t the smartest idea because that would make it easier for an attacker to forge-it-all). So, the use of a keyed hash does not only provide collision resistance like an unkeyed hash, it also lets you verify if $m$ is authentic (unforgeability).

Keeping it short and simple: creating a “simple hash” of some plaintext is a piece of cake for an attacker; but trying to create a valid and verifiable “keyed hash” is a completely different and more complicated beast. So, compared to the use of a regular hash function, HMAC practically adds an additional layer of security. That is one of the main reasons to prefer HMACs over “unkeyed” hashes.

Note that I’m not saying your Encrypt(m | H(m)) method would be insecure (that mainly depends on the encryption… better: the used algorithm and key choice). All I’m explaining is why it’s logic to prefer a MAC over a simple hash, and that a simple hash would give you nothing if your encryption fails/breaks.

…does this not fulfill an approximation of the ideal MAC?

No.

…no secure protocol seems to use it. Why?

If you can get an additional, well-vetted security layer for free, why would you want to avoid or ignore it?

You once said “HMAC seems a bit complicated”, but if you look at it you will notice that it also gives you a good chunk of “unforgeability” in return. See, sometimes, things are “a bit complicated” for a good reason… and people prefer to use it for exactly that reason. In this case, to gain unforgeability.

share|improve this answer
    
But I'm talking about MAC-THEN-encrypt. So unless the encryption is forgeable, the MAC should be unforgeable? –  user54609 May 28 at 3:59
    
@user54609 I edited my answer to explain it a bit more. I essence, your plain hash might be protected by the encryption… but it does not provide unforgeability in any way – which somewhat renders it useless from a security point of view. Maybe a rhetorical question can help explain it a bit better: if you’ld jump out of a plane at an altitude of 10.000 feet… would you rather rely on one parachute (= encryption), or would you feel safer having an additional parachute “just in case” (= encryption & HMAC)? That’s why you’ld want to prefer using a keyed hash instead of a plain, unkeyed hash. ;) –  e-sushi May 28 at 4:42

Why?

We want to be able to build off of more basic encryption schemes.

Suppose we use some stream cipher; then why can't we use Encrypt(m|H(m)) as the MAC-then-encrypted version of the message?

For "traditional" non-authenticated encryption schemes, encrypting plaintexts with the same length always produces ciphertexts with the same length and for all messages $m_0$, one can easily find a string $p$ such that for all messages $m_1\hspace{-0.0 in}$, truncating $Encrypt(m_0|H(m_0)|p|m_1|H(m_0|H(m_0)|p|m_1))$ to the appropriate length will produce an encryption of $m_0|H(m_0)$.

Assuming no bad relations between $Encrypt$ and $H$, what are the possible weaknesses?

The possible weakness is an adversary's ability to choose a "ciphertext" that will decrypt to a highly non-random "plaintext".

It seems that in this case we are encrypting the hash with part of a secretly keyed stream cipher keystream, and the hash is secure; does this not fulfil an approximation of the ideal MAC?

Yes; as I explained earlier in this answer, that does not fulfill an approximation of the ideal MAC.

This must be somehow bad, since no secure protocol seems to use it. Why?

It only works when the underlying encryption scheme already has some resistance to active attacks.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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