4

I was reading the chosen answer to the following question -

"MAC vs Encryption"

They say that just using encryption, "an attacker could alter the ciphertext to make it say something else when decrypted", and then say by hashing the message, adding onto the end and encrypting the entire thing, this provides integrity.

My question is, if the attacker can alter the ciphertext even when it's encyrpted, can't the attacker also alter the hash attached to the end of the message so that it matches the modified text?

Thanks in advance.

Community
  • 1
RJSmith92
  • 311
  • 2
  • 9

3 Answers3

3

The attacker can modify certain bits of the plaintext (by modifying the ciphertext), but the attacker does not know what the entire plaintext originally was. Therefore, the attacker doesn't know what bits of the hash will change due to their alterations of the plaintext. To successfully modify the hash and the plaintext, the attacker would need to know the difference between the original hash and the hash of the modified plaintext. The attacker doesn't know this difference, which prevents the attacker from changing the hash to match the modified plaintext.

Now, all of this is based on the idea that the recipient is supposed to decrypt the data, then verify its authenticity. While this can be done, it's also possible to protect the integrity of the ciphertext, allowing the recipient to verify that the message hasn't been tampered with before even attempting decryption. Obviously, just hashing the ciphertext and appending it to the end doesn't work, because the attacker could modify that hash. Instead, there are two ways of doing this, based on the kind of crypto in use. They are both hash-based but have extra security beyond simply hashing:

  • If using asymmetric cryptography, such as the usual way to use HTTPS or SSH, then you digitally sign the hash. Without getting into the mathematics of how digital signature schemes work, the basic idea is that you have two keys: a private key that only you know, and a public key that everybody can get a copy of. The private key is used to sign the hash, and the public key is used to verify the signature. Because the attacker doesn't have your private key, if they modify the message and re-compute the hash, they won't be able to re-create a signature that can be verified using your public key. Therefore, anybody will be able to use your public key to tell that the message they received is not the message that you signed.
  • If using symmetric cryptography only, like an encrypted .ZIP file or most other forms of password encryption, you create a keyed Hash-based Message Authentication Code (or HMAC). Again, without going into the details, the idea of an HMAC is that when you compute the hash of the message, you also stick in some additional data that is based on a key (which might be the key used to encrypt the message, or might be another one) that the intended recipient of the encrypted message also has. This additional data added to the hash function input modifies the output (the digest) in such a way that if an attacker modifies the message, the attacker won't be able to figure out what the new HMAC should be because the attacker doesn't know the key and therefore, when the recipient uses the key to compute the HMAC of the modified message, it won't match and the recipient will know the message was tampered with.
CBHacking
  • 42,359
  • 3
  • 76
  • 107
  • Thanks @CBHacking, the two methods you mentioned I understand why they're secure, it's mainly the method in the answer that I find confusing, where the text and hash are together and then encrypted. When the attacker modifies the ciphertext, do they know what it will be once decrypted? if so can't they just produce a new hash of the modified clear text and then change the ciphertext to that of the new hash, or is that infeasble/impossible? – RJSmith92 Oct 18 '15 at 07:36
  • 1
    The attacker only knows part of the modified plaintext. Manipulating ciphertext doesn't *set* plaintext to a desired value; it flips bits in the plaintext. In order to change the entire plaintext, you would need to know the entire original plaintext in order to know which bits to flip to reach your desired outcome. If you know the original plaintext, you've already defeated the confidentiality that encryption is supposed to provide. So no, the attacker doesn't know what the (whole) new plaintext will be, nor what the original hast was, so they can't update the hash accurately. – CBHacking Oct 18 '15 at 08:28
  • Thanks. When you say 'an attacker only knows part of the modified plaintext', why can they only know part of the ciphertext, and which parts is it? I would have thought once it's encrypted they can't understand any of it. User fr00tyl00p above has said that an attacker doesn't know any of the ciphertext, and can only randomly flip bits to produce gibberish once decrypted? Thanks again. – RJSmith92 Oct 21 '15 at 13:47
  • 1
    Often, the attacker knows part of the plaintext but not all of it. For example, in HTTPS traffic, an attacker might not actually know the authentication cookie, but (if they know the URL) they probably know the headers up to the `Cookie: ` part, just not what comes next. Blindly garbling encrypted data is certainly possible (if you don't have a MAC protecting the ciphertext) but usually when this is a threat, it's because the attacker is specifically trying to change a bit of data that they know about to some other value. – CBHacking Oct 21 '15 at 20:34
  • Thanks really appreciate it. Still not getting it to be honest, if the HTTPS traffic is all encrypted, how can an attacker know any of it, isn't this defeating the purpose of encrypting it? ...and when you say 'the attacker is specifically trying to change a bit of data that they know about to some other value' how can they do this if it's encrypted, how can they alter the ciphertext and know what the value will be once decrypted? if they could do that couldn't they alter the entire message? Thanks again, I'll not ask any more questions after this! – RJSmith92 Oct 21 '15 at 20:52
  • 1
    That last question is worth doing some research on - semi-blind modification of plaintext by manipulating ciphertext is not new - but I can summarize it a bit. To take the example of HTTPS (assuming TLS didn't have integrity checks, which it does have), if I know somebody has requested https://example.org/ but not what value their `session` cookie has, I know that the first part of their request will look like `GET / HTTP/1.1\r\nHost: example.org\r\n...\r\nCookie: session=` but not the actual cookie value. I could change the Host header to something else by flipping bits, though. – CBHacking Oct 22 '15 at 11:31
  • 1
    Doing so may corrupt the rest of the message (depending on the cipher; in a stream cipher like RC4 you can usually alter bits without preventing the rest for decrypting correctly), and I could never learn what the original session cookie value was. However, if I took some of the less-critical headers whose values I *could* predict (like the user-agent string, which varies by browser but is one of a few options) and turn it into a Cookie header, then terminate the headers with `\r\n\r\n`. The server gets a strangely short request with some garbage after it, but with a cookie value I control. – CBHacking Oct 22 '15 at 11:36
  • Right sort of getting it now, so they know parts of what the ciphertext is due to the 'structure' of the protocol and how it works. Last question, promise. When the attackers wants to terminate headers with \r\n\r\n for example, how do they know which bits and how to flip them so that it produces the desired result once decrypted? Do they know 'where' to flip them due to the structure of the protocol as I said before, but how do they how to flip them to produce \r\n\r\n once decrypted? Do they look at other places where they know \r and \n are encrypted and use that? Thanks. – RJSmith92 Oct 22 '15 at 12:16
  • 1
    Assuming a stream cipher (like RC4, which really shouldn't be used anymore for TLS but for reasons not related to this problem), producing the modifications is easy. Start with the plaintext that you will modify (you must know every byte of this plaintext, and its offset from the message start). XOR the to-modify text with the new value you want to change it into. This produces the bitwise difference between the texts. XOR that into the ciphertext at the correct offset. When decrypted , the bits you flipped (via XOR) in the ciphertext will be flipped in the plaintext, changing the message. – CBHacking Oct 22 '15 at 17:50
  • 1
    For a block cipher using CBC mode - probably the most common mode of operation - this is a lot harder. Unlike stream ciphers, which just produce a bitstream that is (supposedly; RC4 has biases) indistinguishable from random noise and XOR the plaintext with the bitstream to get ciphertext (encrypt) or the ciphertext with the bitstream to get plaintext (decrypt), block ciphers in CBC mode perform complicated operations on "blocks" of ciphertext (during decryption). You can flip bits in one block, but it will corrupt other decrypted data. This is mostly useful in binary formats. – CBHacking Oct 22 '15 at 17:55
  • Thanks @CBHacking for all that, much appreciated. Really interesting to see you can change the encrypted text without knowing the key, with my limited knowledge I always presumed once it was encrypted it was impossible to do anything with without the key. – RJSmith92 Oct 22 '15 at 18:28
  • Yeah, depending on the cipher, it's not even difficult to manipulate the plaintext as long as you know a bit of what it was initially. That's why providing integrity - which most ciphers do **NOT** provide intrinsically - is essential in cryptography. – CBHacking Oct 22 '15 at 20:08
2

Maybe a not-so-technical view helps understanding the problem... Just think of an envelope that contains the message and the hashsum. You can punch the envelope and flip certain bits of the message. You can also punch where the hashsum is and change bits of it. However, as you cannot look inside the envelope you have (almost) no chance to flip the hashsum in a way that yields the correct value for the modified message.

When the receiver opens the envelope they see a message and a hashsum that do not match - a clear indication that something was modified, the message, the checksum or both.

Edit:

Ok, more technical... :-)

Consider the following message M, which I transfer plain-text.

Please transfer 100$ to my account.

its (SHA1) hashsum is 5f7e22d270ca9da68543e3f97f30f1859e20a88a. The resulting MAC is

f56c10e4264a5173aa97660f7438fc0e12618d1e

This MAC is the hashsum that I encrypted with a secret password. You can freely modify the message and the MAC, but you cannot figure out how to modify the MAC so that, when I decrypt it, it delivers the correct hashsum, that matches your modified message. Consequently when I decrypt, I will notice that the hashsum does not match the message and something was modified.

That is what a MAC is all about, detecting modifications.

fr00tyl00p
  • 2,339
  • 1
  • 15
  • 17
  • Thanks @fr00tyl00p, the analogy you used is how I initially understood it, but the part about being able to modify the ciphertext has me confused. I understand an attacker can randomly flip bits and therefore the hash and original text won't match when decrypted, but their answer seemed to suggest an attacker could modify the ciphertext to something they choose? or have I misunderstood. If an attacker can only randomly flip bits in the ciphertext to ruin the integrity of the message then that makes sense. – RJSmith92 Oct 18 '15 at 13:33
  • Sorry to bother you @fr00tyl00p can you just confirm something for me? When the attacker 'punches the envelope' do they have any idea of 'what' they have flipped or 'what' they have flipped it to? or can they just flip bits of the ciphertext at random without knowing what they have changed and what it will be changed to? – RJSmith92 Oct 20 '15 at 12:02
  • 1
    You can change the ciphertext to anything you want. But you (usually) cannot know what the cleartext after decryption will be then. This holds for both the message and the hashsum. – fr00tyl00p Oct 20 '15 at 12:25
  • Thanks @fr00tyl00p. I was being an idiot, I thought when they said 'an attacker could alter the ciphertext to make it say something else when decrypted', they knew what they were changing. For example they could edit the ciphertext so it said 1000$ instead of 100$, then could change the encrypted hash to match the new text, but if they could do all that it would completely defeat the purpose of encrypting the plain text in the first place. So am I right in thinking the only thing an attacker can do with ciphertext is randomly change it to produce gibberish once decrypted? – RJSmith92 Oct 20 '15 at 14:15
  • 1
    Yes, that's it. You only know *that* the decrypted text will change when you change the ciphertext, but you don't know into *what* it changes. – fr00tyl00p Oct 21 '15 at 12:26
1

When creating an HMAC (Hashed Message Authentication Code), the message is only part of the hash. There needs to be a key as well. This key is known only to the server.

In python:

import hmac
from hashlib import sha256

msg = "The cow jumped over the moon."
key = "My key."

print hmac.HMAC(key, msg, sha256).hexdigest()

Without the key, anyone could modify the hash. So it is important to have a strong key. Once the key is leaked or guessed, the HMAC becomes useless.