Subject: [Cfrg] PGP and non-malleability

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 12 Dec 2002 21:48:51 +0200 (IST)

This note is in response to the the request made by Jon Callas during the
Atlanta CFRG meeting for feedback on their PGP "message integrity"
mechanism. It serves also as a clarification of the problem which I (and
possibly others) misunderstood when Jon described it at the meeting.  
Specifically, this relates to the following excerpt from the cfrg minutes:

> Jon Callas gave an overview of the PGP message integrity problem, which
> resulted in a lively discussion.  Earlier message formats didn't have
> any message integrity. The proposed method of adding message integrity
> involves adding a "modification detection code" (an unkeyed hash) to
> end of the plaintext. However, the encryption mode used is CFB. CFB has
> the property that bytes can be lopped of the end of the message without
> detection. David Wagner has pointed out that this simple addition of an
> unkeyed hash is not sufficient as it can theoretically be broken. The
> question was posed by Jon as to whether the problem was sufficiently
> bad that a fire alarm should be pulled? Hugo Krawczyk pointed out that
> the problem was not merely theoretical, since any attacker which can
> successfully decrypt the message can change the message, re-compute
> the unkeyed hash to place at the end of the modified data, and then
> re-encrypt the message making it appear to be the original message. There
> seemed to be a consensus of attendees that this method was worse than
> no integrity at all, and should be dropped in favor of a more secure
> message integrity method.

When Jon talked about this "message integrity" problem during the meeting
I thought that he meant this term in the traditional sense of a MAC
functionality and therefore I referred to the mechanism that they use
(compute a SHA1 value on the message, append this value to the message,
encrypt message and hash using a symmetric cipher in CFB mode, and finally
encrypt the symmetric key under the recipient's PK) as obviously broken.  
However, after talking to Jon after the meeting I understood that the
problem that they are trying to solve is not that of authentication but
rather to avoid the "malleability" of encrypted messages.

Let me explain the problem as I understood it (I hope that Jon sees this
and will correct me if I did not get it right.) First, they are talking
about situations where cryptographic authentication is NOT performed at
all. Even though PGP allows to sign email messages for authentication,
there are situations in which they want to avoid the use of such
authentication.  This is mainly related to some side-effects of the use of
digital signatures, such as liability, non-repudiation, privacy concerns,
etc that are seen as bugs rather than features in some scenarios
(especially given the ongoing legislation on digital signatures).

Note that in this case, where no authentication is applied, there is no
point in preventing Eve from changing a message that A sent to B to a
completely new message that Eve chooses.  Indeed, Eve can send that
message to B directly (she just chooses the message, encrypts it, and
sends to B; and she may well choose to have a header with A's name on it
or whatever). What they want to prevent are attacks of the following form
(the example is mine, I hope that it represents Jon's problem correctly):
Assume that I send an encrypted email message which contains my billing
information (say a credit card number). In this case, an attacker that
does not know this information, may be interested to change some part of
the message (e.g the shipping address) but leave the credit card number
intact.

The general question then is how to prevent that an attacker that sees an
encrypted message E(m) can create a second encrypted message E(m') such
that m is somehow related to m' (beyond the trivial relation m=m').  This
reflects exactly the notion of non-malleability that we know to be
equivalent to chosen-ciphertext security (CCA).

Thus, the question Jon asked should be restated as: does their current
mechanism (with the appended SHA1 value) provide non-malleability (or,
equivalently, CCA security)?  The answer is not. Jon mentioned the
possible truncation attack (in which the attacker can cut a suffix of the
message).  This is indeed possible. Moreover, not only attacks against
malleability are possible but against secrecy too.  This is the case even
if the PK encryption of the key is CCA too.

I'd suggest as a solution to this problem simply moving the SHA1 value of
the message from the symmetric encryption to the PK encryption. Namely, I
propose to encrypt a message M under the pair
(RSA-OAEP(K,SHA1(M)),CFB_K(M)) rather than the current
(RSA(K),CFB_K(M,SHA1(M)).  If the PK encryption is CCA secure (e.g. OAEP)
nad SHA1 collision resistant then the whole thing is CCA-secure and in
particular non-malleable.

This method of using a collision-resistant hash of the message under the
PK encryption (let's call the method EKH) has been used in the design of
the iKP protocols in 1995, and included in the SET protocol, and a version
of it was used even earlier in IBM in the context of key management (see
the paper "enhanced OAEP" by Johnson and Matyas in CryptoBytes spring
1996).

I tried to find a formal proof of the security of EKH in the published
literature but couldn't find one.  So I went over the exercise of proving
its CCA security before I offered it as a solution here.  But if any one
knows of a published proof, please let me know,

AN alternative solution for achieving non-maleability is to apply a MAC to
the (symmetric) ciphertext. The MAC key can be added to the information
included under the PK encryption (or the single PK-encrypted key can be
used to derive an encryption key and a MAC key via a prf). The advantage
of the "hash under the PK encryption" is that it is closer to what is done
now; the advantage of the encrypt-then-mac solution is that the PK
encryption can be computed independently from the specific message.

Comments (in particular from Jon whose email address I do not have) are
welcome.

Hugo

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 12 Dec 2002 13:04:36 -0800

> -----Original Message-----
> From: Hugo Krawczyk [mailto:[email-masked]]
>
> the (symmetric) ciphertext. [...] the single PK-encrypted key can be
> used to derive an encryption key and a MAC key via a prf).

An earlier discussion involved doing the above, but with the MAC applied to
the plaintext instead of ciphertext, i.e. AtE (authenticate-then-encrypt)
instead of EtA.  

AtE might be a simpler change, but I think EtA is better here - besides
being generically secure, PGP's encryption layer has some redundancy which
it checks ("The repetition of 16 bits in the random data prefixed to the
message allows the receiver to immediately check whether the session key was
incorrect").  This may allow an attack similar to Vaudenay's attack on TLS's
CBC padding, where the attacker learns something through differentiating
between a failed decryption and failed MAC through some sidechannel, even
one so subtle as timing differences.

Alternatively, I suppose PGP could switch to a combined mode like CCM for
symmetric encryption?

Trevor