Public key encrypt-then-sign or sign-then-encrypt?

[Travis H.]

On Wed, Apr 25, 2007 at 03:24:06PM -0300, Mads Rasmussen wrote:
> Hugo Krawczyk [1] showed in the symmetric key setting that the 
> encrypt-then-authenticate was the way to go about securing the integrity 
> of an encrypted message.

Haven't read this yet, but will... and may have comments.

Without reading it, I do have some comments.

At least one authentication protocol failed because it was possible
to strip off a signature then re-use an encrypted blob (e.g. with
one's own signature on it).  So they are malleable.

In _many_ poorly-designed systems it becomes possible to use a system
as a signature oracle to sign arbitrary things.  Smartcards with a
hostile PC are just one of these cases.

One must be very careful what a signature is supposed to attest.

Also there's a semantic issue; am I attesting to the plaintext,
or the ciphertext?  It's possible the difference could be important.

Do we sign letters, or sign envelopes?  If I sign an envelope
containing a letter, I deprive you of much of the evidentiary
value that a signed letter would carry; you cannot easily prove
to someone what I signed without revealing your decryption key(s).

With encrypt-then-authenticate, one can check authentication, and
if it fails, avoid decryption - while in theory this could avoid
DoS, in practice the authentication is more costly than decryption.

In my reading on information-theoretic security, I found that if one
does encryption around the authentication, then one can prevent the
opponent from learning anything about the message.  Specifically, if
Enc(x) is a one-time-pad, then one can use very efficient and
ostensibly unsecure hash functions such as a selection from the
universal hash family ax + b (mod n) for one's integrity and
authentication, and (for certain restrictions on a, b, and n, and
under the assumption of secrecy of a and b) one can have
_information-theoretic security for authentication and integrity_.
That is, no matter how many messages sent, no matter how many CPU
cycles the opponent has available, the opponent can learn nothing new.

I've been discussing and developing a prototype system that aims to
provide information-theoretic security (and at worst, conventional
computational security) for low-bandwidth purposes (i.e. email or IM),
and I will post details here when I have them in a relatively stable
form, for those who are interested.

-- 
Kill dash nine, and its no more CPU time, kill dash nine, and that
process is mine. -><- <URL:http://www.subspacefield.org/~travis/>
For a good time on my UBE blacklist, email john at subspacefield.org.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20070425/a34956a1/attachment.pgp>