(FWD) Re: Comparing mixminion's repadding with your RSA talk?

[Roger Dingledine <arma@mit.edu>]

----- Forwarded message from owner-mixminion-dev@freehaven.net -----

Date: Sat, 1 Mar 2003 16:11:02 +0100
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: Roger Dingledine <arma@mit.edu>
Cc: mixminion-dev@freehaven.net
Subject: Re: Comparing mixminion's repadding with your RSA talk?

On Sat, Mar 01, 2003 at 01:37:03AM -0500, Roger Dingledine wrote:
> On Thu, Feb 27, 2003 at 04:30:23AM -0500, Roger Dingledine wrote:
>> On Thu, Feb 27, 2003 at 09:26:24AM +0100, Bodo Moeller wrote:

>>> I don't use an explicit padding seed (although that was my original
>>> idea a couple of years ago), instead I use a stream cipher to decrypt
>>> the ciphertext with an appropriate number of zero bits appended.
>>> I.e., decryption and deterministic pseudo-random padding are combined
>>> into a single operation.

>> This is a really good point. It's not really that different when it comes
>> down to it (the prng is just encrypting a stream of zeros, after all),
>> but we're deriving an extra key when we don't need to.

> Hrm. On more thought, this seems tricky again. You see, we're repadding
> just the header, not the whole message. And if we append the 0's to the
> header before, then we don't know how many 0's we should add. (Another
> complexity to our design is that a given hop can use 1 or more 128 byte
> chunks from the header -- say, if we need to include more details for
> a given processing step. And you don't know how many chunks a hop will
> use until you've decrypted it.)
> 
> So we could:
> 
> a) decrypt the header 128 bytes at a time until we know how much we'll
> use for this hop, then append the correct number of zero's to the header,
> then continue to decrypt
> b) decrypt the whole thing, then decrypt an appropriate number of 0's
> *after* we've decrypted the whole thing, and stick them into place at
> the end of the header
> c) stay with our current
> derive-padding-seed-then-add-sufficient-padding-afterwards approach.
> d) other options?

b) looks OK.  This is equivalent to decrypting the header concatenated
with a large amount of zeros and finally throwing away the unused
postfix.

> Below is a potential diff on the current paper, using approach b
> (closest to what we do right now), to help clarify things. Bodo --
> are we stretching your paper too far to say this?

> +Each subheader contains a hash of the remainder of its header as seen
> +by that mix, so we can do integrity-checking of the path (but not the
> +payload) within each leg. Each subheader also contains a master secret,
> +which is used to derive a symmetric key for decrypting the rest of the
> +message. The mix appends an appropriate number of zero bits to the header
> +after message decryption, and decrypts those also --

I think this description of the decryption process is not necessarily
clear to a reader who is not aware of the previous discussion ...

>                                                       the decryption of
> +the padding is predictable, and so the hash can match even though each
> +hop must repad the header to maintain constant length. A proof for the
> +security of this approach is given in \cite{BM:mixencrypt}.

I don't know all of your paper, so I can't really comment on what may
be provable for your protocol.  My paper does not cover
variable-length padding, so the final statement is not exactly true,
although the security result should carry over to variants where the
length of padding can only be determined after decryption (the main
reason for not including this into the paper is that it adds some
complication to formally describing the protocol).  But you appear to
be saying that integrity-checking does not cover the payload, so the
protocol would be quite different from mine.


-- 
Bodo Möller <moeller@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036

----- End forwarded message -----