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.

Given that we know that nonce + message + hash(nonce + message + mac-key) all inside the encryption makes it possible to detect if any bits of the message have been changed by the attacker (in essence converting a malleable cipher into a non-malleable one), why do they still say encrypt then MAC?

Furthermore, doesn't adding the mac-key that is split into pairs like the symmetric cipher authenticate the attacker by proving the rest of the material not subject to attack on the cipher is known (assuming adequate length)?

Of course if we had full asymmetric we'd sign then encrypt but that's not the question being asked.

EDIT: The encryption algorithms I prefer all have the property of not having invalid inputs, in that any ciphertext + any key -> some "plaintext", usually garbage. There cannot exist an attack on the algorithm that would crash the implementation.

EDIT: OK I get the part about HMAC not being hash(a + b) due to most hash functions being unsuitable. I prefer to replace a hash function as unsuitable for any use once it reaches the state of unsuitable for that use but no matter. I don't get the part about why we care if the ciphertext has been altered. The way my stuff is set up it is not faster to MAC before attempting decryption due to rewinding streams.

share|improve this question
3  
Hint –  e-sushi Jul 22 at 20:36
1  
I was going to fix the grammar on the second paragraph, but I find myself wondering what it's supposed to mean. What I first though can't be it. –  otus Jul 22 at 21:17
    
We "care if the ciphertext has been altered" because it might be easy to modify a single ciphertext so that whether or not the decryptor rejects depends in a predictable-and-useful way on what the message was. $\;$ –  Ricky Demer Jul 22 at 22:18
    
And if the decryptor can't reject? –  Joshua Jul 23 at 15:54
    
If the decryptor can't reject, then we "care if the ciphertext has been altered" because it might be easy to modify a single ciphertext so that whether or not it is detected that "any bits of the message have been changed by the attacker" depends in a predictable-and-useful way on what the message was. $\hspace{.68 in}$ –  Ricky Demer Jul 23 at 17:11

2 Answers 2

up vote 3 down vote accepted

If there exists an encryption scheme, then there exists an encryption schemes such that
one can easily modify a single ciphertext so that whether or not that modifies the decryption
result depends in a predictable-and-useful way on what the plaintext message was, such as:

The modified encryption operation outputs a zero concatenated with the original encryption algorithm's output. $\:$ If the input ciphertext is empty then the modified decryption operation gives the same output as the original decryption algorithm. $\:$ If the input ciphertext begins with a zero then the modified decryption operation outputs the original decryption algorithm's output when given the rest of the ciphertext.
If the input ciphertext begins with a one followed by a prefix-free encoding of a natural number,
then the modified decryption operation takes the output of the original decryption algorithm on the
rest of the ciphertext, appends however many (possibly zero) zeros are needed to make it longer
than the natural number, makes the [natural number]-th bit a one, and outputs that result of that.
Otherwise, the modified decryption operation outputs the original
decryption algorithm's output when given the empty ciphertext.


If MAC-then-encrypt is used with an encryption scheme which allows such ciphertext modifications
that depend in a predictable-and-useful way on the actual message component of the plaintext,
then the resulting scheme will still be malleable.

share|improve this answer
    
I can come up with some examples like this, but can't actually come up with anything that would work with the nonce there. (Assuming the nonce is large, random and private.) –  otus Jul 23 at 20:08
    
It's a "just do it" construction that I'll describe later. $\;$ –  Ricky Demer Jul 23 at 20:15
    
otus: It's a matter of the ciphertext change didn't change the plaintext only if the plaintext is a certain value at some point. –  Joshua Jul 23 at 20:39
    
@otus : $\:$ I just edited in an example. $\;\;\;\;$ –  Ricky Demer Jul 23 at 21:26
    
HUH what? If you insert the plaintext MAC is completely different due to being decrypted at a different offset than encrypted. –  Joshua Jul 23 at 23:08

It has the disadvantages of any MAC-then-encrypt scheme, which I'm quoting from the linked answer below. In addition:

  • It has the property that you need both a nonce and a hash, so for equivalent security it requires more message space.

  • The nonce has to be random, so it requires strong random numbers for each message, unlike e.g. AES CTR + HMAC.

  • Doesn't work if you need deterministic encryption, for some reason.


From the link:

Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.

This means that it may allow some chosen-ciphertext attacks that encrypt-then-MAC would protect from. It also means more time is wasted on incorrect messages, which could e.g. help with denial-of-service attacks.

If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC code. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.

In your scheme the nonce and ID take the place of the MAC secret, which could be weaker if the encryption is weak and the hash function isn't a strong MAC in that mode, but can't be any stronger. Still theoretical, as long as you choose a strong, unknown nonce.

share|improve this answer
    
My scheme has both nonce and MAC secret (identifier) –  Joshua Jul 22 at 21:01
    
@Joshua, right, but "hash(m|k)" is not a secure MAC with all hash functions. I've updated the answer to clarify. –  otus Jul 22 at 21:17
1  
In addition to possibly allowing chosen-ciphertext attacks, it may even be malleable. $\hspace{1.3 in}$ –  Ricky Demer Jul 22 at 21:38
    
@RickyDemer, could you explain what you mean? Beyond what MAC-then-encrypt in general allows? –  otus Jul 22 at 21:58
1  
I mean that it might be easy to modify a single ciphertext so that whether or not the decryptor rejects depends in a predictable-and-useful way on what the message was. $\:$ (That is not beyond "what MAC-then-encrypt in general allows".) $\;\;\;\;$ –  Ricky Demer Jul 22 at 22:18

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.