Subject: Return to MDC packet discussion

From: [email-masked]
Date: Thu, 10 Feb 2000 17:41:15 -0800

Greetings to Open-PGPers.  I would like to take up the topic we discussed
in May of 1999 without coming to a resolution, the MDC packet.  The
proposal I advanced at that time is appended below.  In this message
I discuss some of the motivation for that proposal, and suggest a way
of doing the change which many people wanted, to allow variation in the
MDC algorithm.

Several comments and changes were suggested, but as I have expressed
in the past, my concern is that they will weaken the security we want
to provide with the MDC packet.  Due to the nature of CFB encryption,
an attacker can do any XOR that he wants into any one block of
encrypted data, at the cost of totally corrupting the following block.
This means that suggestions to protect against modifications by
putting fields into the encrypted data will not work.

In particular, it is dangerous to have a field which allows specifying
which algorithm to use for the MDC.  The danger is that an attacker
can change the value of this field to some other algorithm.  Of course
the attacker cannot actually compute a valid MDC packet for that new
algorithm.  That is not the attack.  Rather he can change the
algorithm field to be an unknown/unsupported algorithm, one not yet
assigned.  The receiver then has no way of knowing whether this is the
result of such an attack, or whether it is receiving a message from a
newer OpenPGP version which uses a newer hash algorithm.

It was suggested that this attack could be prevented by putting other
data into the encrypted data, like a checksum for the MDC algorithm.
I think the idea was to include the prefix block of random data in the
checksum, along with the MDC alg value, all of which would be
encrypted.  However some checksum algorithms are transparent to XOR,
for example bytewise sum is transparent to XOR of the high bit
(meaning, checksum correctness is preserved if an input byte and the
checksum byte both have their high bit toggled).  Even with a 16 bit
arithmetic checksum as used in PGP secret keys, the attacker has a 50%
chance of successfully toggling the high bit.  I am unconvinced that
we can come up with a guaranteed safe checksum algorithm.

It was also suggested to put the packet version byte (1, for this
version) into the encrypted data to help prevent rollback attacks, but
for the reasons just mentioned the attacker can change this value in
the encrypted packet, so it does not work.

On further thought though I can see a way that we could safely allow
an MDC algorithm specification bit.

We would specify that the reciever MUST NOT attempt to process any MDC
message with an unknown MDC algorithm (or unknown version, although
that is already implied).  It must treat the message as an error and
not process it further, not display it to the user.

This would prevent the attacker from getting a modified message seen
by the receiver.  If all receivers follow this rule, then an attacker
knows that meddling with the version or MDC alg bytes will only cause
the message not to be seen, possibly with an error message that would
alert the user to the attack.  So this is no better for the attacker
than simply deleting the message, which he can presumably do if he is
able to alter bits.

I would be willing to accept an MDC algorithm specifier if we added
this rule.  My main worry is that an implementation might choose to
disregard this rule on the theory that it should show all possible
data to the user and let him decide how much to trust it.  I suppose
we can't protect people from themselves.

If we do this, though, I don't see any advantage to putting the MDC
algorithm (or packet version) into the encrypted data, for the reasons
discussed above.  I would propose to add the algorithm specifier in
the unencrypted packet header, just after the packet version described
below.

Comments?

Hal Finney
PGP Security, Inc.

=====

5.X. Symmetrically Encrypted Integrity Protected Data Packet (Tag 15)

   The Symmetrically Encrypted Integrity Protected Data packet contains
   data encrypted with a symmetric-key algorithm and protected against
   modification by the SHA-1 hash algorithm. When it has been decrypted,
   it will typically contain other packets (often literal data packets
   or compressed data packets).  The last such decrypted packet must be
   a Modification Detection Code packet.

   The body of this packet consists of:

     - A one-octet version number.  The only currently defined value is 1.

     - Encrypted data, the output of the selected symmetric-key cipher
       operating in Cipher Feedback mode with shift amount equal to the
       block size of the cipher (CFB-n where n is the block size).

   The symmetric cipher used MUST be specified in a Public-Key or
   Symmetric-Key Encrypted Session Key packet that precedes the
   Symmetrically Encrypted Data Packet.  In either case, the cipher
   algorithm octet is prefixed to the session key before it is
   encrypted.

   The data is encrypted in CFB mode, with a CFB shift size equal to
   the cipher's block size.  The Initial Vector (IV) is specified as
   all zeros.  Instead of using an IV, OpenPGP prefixes an octet string
   to the data before it is encrypted.  The length of the octet string
   equals the block size of the cipher in octets, plus two.  The first
   octets in the group, of length equal to the block size of the cipher,
   are random; the last two octets are each copies of their 2nd preceding
   octet.  For example, with a cipher whose block size is 128 bits or 16
   octets, the prefix data will contain 16 random octets, then two more
   octets, which are copies of the 15th and 16th octets, respectivelly.
   Unlike the Symmetrically Encrypted Data Packet, no special CFB
   resynchronization is done after encrypting this prefix data.

   The repetition of 16 bits in the random data prefixed to the message
   allows the receiver to immediately check whether the session key
   is incorrect.

   The plaintext of the data to be encrypted is passed through the SHA-1
   hash function, and the result of the hash is appended to the plaintext
   in a Modification Detection Code packet.  Specifically, the input to
   the hash function does not include the prefix data described above;
   it includes all of the plaintext, and then also includes two octets
   of values 0xD0, 0x14.  These represent the encoding of a Modification
   Detection Code packet tag and length field of 20 octets.

   The resulting hash value is stored in a Modification Detection Code
   packet which MUST use the two octet encoding just given to represent
   its tag and length field.  The body of the MDC packet is the 20 octet
   output of the SHA-1 hash.

   The Modification Detection Code packet is appended to the plaintext and
   encrypted along with the plaintext using the same CFB context.

   During decryption, the plaintext data should be hashed with SHA-1,
   not including the prefix data but including the packet tag and length
   field of the Modification Detection Code packet.  The body of the
   MDC packet, upon decryption, should be compared with the result of
   the SHA-1 hash.  Any difference in hash values is an indication that
   the message has been modified and SHOULD be reported to the user.
   Likewise, the absence of an MDC packet, or an MDC packet in any
   position other than the end of the plaintext, also represent message
   modifications and SHOULD also be reported.

   Note: future designs of new versions of this packet should consider
   rollback attacks since it will be possible for an attacker to change
   the version back to 1.

5.Y Modification Detection Code Packet (Tag 16)

   The Modification Detection Code packet contains a SHA-1 hash of
   plaintext data which is used to detect message modification.  It is
   only used in the context of a Symmetrically Encrypted Integrity
   Protected Data packet.  The Modification Detection Code packet MUST
   be the last packet in the plaintext data which is encrypted in the
   Symmetrically Encrypted Integrity Protected Data packet, and MUST
   appear in no other place.

   A Modification Detection Code packet MUST have a length of 20 octets.

   The body of this packet consists of:

     - A 20-octet SHA-1 hash of the preceding plaintext data of the
       Symmetrically Encrypted Integrity Protected Data packet, not
       including prefix data but including the tag and length byte of
       the Modification Detection Code packet.

   Note that the Modification Detection Code packet MUST always use a
   new-format encoding of the packet tag, and a one-octet encoding of
   the packet length.  (These requirements are already imposed by the
   rules for tag and length encoding.)

---

From: Werner Koch <[email-masked]>
Date: Fri, 11 Feb 2000 11:25:12 +0100

> not process it further, not display it to the user.

Okay.

>    resynchronization is done after encrypting this prefix data.

Good.

This proposal is fine with me.  To implement this we have to add
feature flags to the public keys or choose an implicit way to decide
when a tag-15 packet should be used or is expected.  Using cipher
algorithms with a blocklength other the 64 bit should still work 
as an implicit criteria.

   Werner