Subject: Re: Agree with PRZs MDC suggestion

From: [email-masked]
Date: Sun, 9 May 1999 18:08:17 -0700

An attacker can modify encrypted messages to a limited extent.  In CFB
mode, if he xors one bit of the ciphertext, it has two effects.  It xors
the corresponding bit of the plaintext, and it also turns the following
block of plaintext into complete garbage.  The remainder of the message
is unchained.

Attackers can also delete entire blocks of messages.  If they do it at
the end, this has no obvious effect.  If they do it at the beginning,
they can supply an IV so that everything decrypts OK (but missing the
first blocks of the encrypted messages).  If they do it in the middle,
there will be one block of garbage after the spot where the deleted
blocks would go.

Attackers can also rearrange blocks of messages, or moving groups of
blocks from one point to another, or duplicating groups of blocks in
various ways.  This will normally put a block of garbage at the join
points when the messages are decrypted.

It is important to realize that these blocks of garbage or noise will
not necessarily expose the attacker's actions.  They may be overlooked
by the receiver.  They may be located in a part of the message which
he does not study closely (like mail headers or data tables).  They may
be at the very beginning or end of the message where the important data
is in the middle, or vice versa.  We can't assume that blocks of noise
will always be detected.  (And of course the truncation attack leaves
no noise blocks.)

Our goal with the MDC feature is to detect these kinds of transformations.
As we have been discussing, including a hash of the message within the
encrypted data should accomplish this.

One possible attack we need to then consider is whether a message sent
in this form can be transformed by an attacker so that the receiver does
not attempt to do the MDC verification.  The attacker might be able to
change the format of the message so that it looks like a non-MDC message,
using some of the tools above.

As a simple example, if we include a bit in the message header that
tells whether the message has MDC protection, and the attacker guessed
that that bit was on, he could turn it off by xoring the right place in
the ciphertext.  This would introduce a burst of noise in the following
block of the message, but depending on the block size and the message
format, this might still allow the message to decrypt successfully.

The receiver would not be fooled into thinking that he had an
MDC-protected message which was untouched, but he would be fooled into
thinking that the message had been sent without MDC protection when in
fact the sender had intended to protect it.

I believe it is possible to provide for this level of protection, but it
will put some constraints on the design.  Anything in the headers which
the attacker could tweak to disable the MDC checking (like changing a hash
algorithm value) would have to be such that the change will be detected.
There could be another checksum in the headers itself, or the headers
could be structured so that the block of noise is guaranteed to corrupt
crucial data, or the data structures could be such that MDC checking
can't be disabled.

I suggest that we should design the packets, if possible, to prevent
this attack.  What do others feel?  Do we care about this kind of attack?
Should we take steps to prevent it, or should we allow it to happen?

Hal Finney
Network Associates

---

From: Werner Koch <[email-masked]>
Date: Mon, 10 May 1999 09:35:30 +0200

[email-masked] writes:

[ About attacks flipping some bits in the headers to 
  make the receiver think the message has no MDC ]

> Should we take steps to prevent it, or should we allow it to happen?

I think the easiest solution and the one we did at other places too
is to say:

"Implementations SHOULD use the MDC for ciphers with a blocksize of 64
bit.  Implementations MUST use the MDC for ciphers with a blocksize
other than 64.  If an implemenations detects a violation of the above
it SHOULD notify the user about this.  It MUST do this for messages
encrypted with non-64 bit blocksize cipher."

Or something similar.

-- 
Werner Koch at guug.de           www.gnupg.org           keyid 621CC013