Subject: Re: [Cfrg] PGP and non-malleability

From: [email-masked] (Peter Gutmann)
Date: Fri, 13 Dec 2002 19:08:56 +1300

Hugo Krawczyk <[email-masked]> writes:

>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.

Unless I'm misinterpreting the notation somehow, this requires two passes over
the data, which would rule out its use with PGP.

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

---

From: Gé Weijers <[email-masked]>
Date: Fri, 13 Dec 2002 10:10:00 -0700

>the data, which would rule out its use with PGP.
Why not append a MAC in stead of encrypting the hash under the PK?

This would work: RSA-OAEP(Ke,Ka), CFB_Ke(M), HMAC-SHA1_Ka(CFB_Ke(M)).

A better single-pass method (given that the best-known security 
reduction for RSA-OAEP is not all that great):
R := random()
Ke := F1(R)
Ka := F2(R)
C := RSA(R),CFB_Ke(M), HMAC-SHA1_Ka(CFB_Ke(M))

F1 and F2 have to be suitable and different PRFs.

Gé

-- 
Gé Weijers
Linux Software Engineering Security       mailto:[email-masked]
Sun Microsystems, Inc.                    Tel:   (877)240-7611
Cobalt Server Appliances Business Unit           x69536
1160 Dublin Road, Suite 100 (UCMH03)      Fax:   (877)240-7611
Columbus OH 43215

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 14 Dec 2002 06:23:34 +0200 (IST)

> the data, which would rule out its use with PGP.

It is possible to do the processing with one pass over the data if you
can wait to produce the PK encryption of the key and hash value AFTER this
pas. That is, you can do:

1) choose a symmetric key K
2) go over the data and compute
   a) the hash value (say SHA1)
   b) the encryption under key K 
   (clearly this processing of hashing and encryption can be done 
    "in parallel")
3) encrypt under the public key the key K and final hash of the message

Yet, since you probably want to send the encrypted key PREpended before 
the message ciphertext then the above method would require buffering the
ciphertext which is probably a reason not to do it.
In any case I'd like you to explain why this buffering or two passes are
prohibitive in PGP. Is it because this changes the current processing
order or is  there a more "essential" reason? (I do not see, in principle,
why PGP couldn't work with buffered data).

In any case, the reason I thought the suggestion may be interesting is
because it showed how by changing the place where you encrypt the hash
(from under the symmetric encryption as done today to the asymmetric
encryption) transforms the currently insecure mechanism into a secure one.
But as I said in my message, you can achieve the same non-malleability by
removing the hash at all and instead MACing the ciphertext. This puts you
back in the one pass processing.

Hugo

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 14 Dec 2002 06:37:34 +0200 (IST)

This is a particular instantiation of the general enc+mac method, and is
especially good in the case that you use RSA as the PK encryption function
(for which we do not know how to achieve CCA security without random
oracles).  As a general method this has the disadvantage that it requires
a "random oracle" assumption even if you use a CCA-secure PK encryption
that does not require this idealized assumption (e.g. if you use
Cramer-Shoup). In this sense the methods I described are better. But
otherwise, and specifically for RSA, this is a perfectly ok method.

Hugo