1

The question is simple:

Adding a hash to a message and then encrypt it using a stream cipher / block cipher. Why can't this guarantee integrity of the message upon decryption?

2
  • 3
    Is this a homework question? What is the context for this question?
    – schroeder
    Nov 17, 2014 at 20:53
  • It is a homework question that I would like to understand, yes. Nov 17, 2014 at 23:22

2 Answers 2

4

Why it does not guarantee integrity is easier to see in the case of a stream cipher like RC4, where the encryption is a bit-by-bit XOR of the data with a key-dependent stream. Basically, the encryption of message m is: e = m XOR sk, where sk is the RC4 output (a long stream of pseudorandom bits produced from the key k). Suppose that you apply the "append hash then encrypt" method. You start with message m, and you get this:

    e = (m || h(m)) XOR sk

Now an attacker comes by, and he is smart, and he guesses the contents of m (remember: the attacker is after integrity, not confidentiality, so we assume that he already knows the message). Since a hash function has no key, the attacker can recompute m||h(m). From that he gets:

    sk = (m || h(m)) XOR e

Now the attacker has the key-dependent secret stream sk. He then proceeds to encrypt his fake message m' by computing:

    e' = (m' || h(m')) XOR sk

This works as along as m' is not longer than m (it could be shorter). Upon decryption, the hash will match, and integrity is defeated. Fun fact: I know a system for Web-based online banking that was using this construction for integrity, and was widely deployed. Fortunately, it has been fixed more than a decade ago.

2
  • This is the superior answer to mine if confidentiality is not meant to be preserved.
    – schroeder
    Nov 17, 2014 at 21:23
  • It's clear that hashing cannot guarantee integrity if the hashing method and the encryption method are linearly related. Suppose, however, that the methods were not linearly related, even if the hash were something simple like ((sum(d[i] * 13573053) >> 8) & 65535) and the stream used a simple xor. How could an adversary have a much better than 1 in 65536 chance of altering a message undetectably?
    – supercat
    Nov 18, 2014 at 0:26
2

The problem is that hashing provides nothing in terms of integrity in your scenario. You are relying on the encryption alone to assert integrity. If I get a hold of the message and decrypt it, I could alter the message, recalculate the hash, encrypt it again and pass it on.

If you trust encryption alone to provide integrity, then this process works, but then the hashing has no point.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .