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

[Roger Dingledine <arma@mit.edu>]

(Moving the thread to mixminion-dev so I can get some feedback on design
implications to mixminion.)

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?

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?
--Roger

 Messages are composed of a header section and a payload. We divide
 a message's path into two \emph{legs}, and split the header section
 correspondingly into a main header and a secondary header. Each header
 is composed of up to 16 subheaders, one for each hop along the path.
-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 also
-derives a padding seed from this master key. It uses this padding seed
-to place predictable padding at the end of the header, so the hash will
-match even though each hop must repad the header to maintain constant
-length.
+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 -- 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}.