[freehaven-dev] comments on proposed mixmaster v3 protocol

[Adam Back <adam@cypherspace.org>]

http://www.eskimo.com/~rowdenw/crypt/Mix/draft-moeller-v3-01.txt

Some comments on the proposed mixmaster 3 protocol (see above).

- Section 3.2 describes using Elgamal.  Two problems with this 1) I'm
not sure Elgamal is a good idea.  RSA patent expires RSN, probably
before mix3 is likely to get implemented, and Elgamal suffers from
message expansion which will exacerbate the overhead.  2) The rest of
the document and packet format descriptions don't mention Elgamal but
seem to assume RSA.

- Section 3.3 describes a packet format of:

>      Length of asymmetrically encrypted data  [       1 byte ]
>      Asymmetrically encrypted session key     [ key-dependant]
>      Initialization vector                    [       8 bytes]
>      Symmetrically encrypted data             [fill to 20 kiB]
> 
> The symmetrically encrypted part of the packet has the following
> format:
> 
>      Message digest                      [ 16 bytes]
>      Packet ID                           [ 16 bytes]
>      Timestamp                           [  2 bytes]
>      Packet type identifier              [  1 byte ]

It would be more secure (marginal value) and more importantly more
compact to make use of the asymmetric encryption to transfer data
other than a session key.  There's plenty of space in a 1024 bit RSA
encrypted message to include everything you need for 1 hop.

You could generalise it to decrypt the asymmetric encryption, extract
the session key and IV, and continue decrypting the rest of the
symmetric encrypted data; the resulting plaintext is the asymmetric
decrypted data starting after the symmetric key and iv concatenated
with the symmetrically decrypted data.

ie.

asymmetric = length || RSA( session-key || iv || plaintext1 )
symmetric = 3DES_iv,session-key( plaintext2 )
plaintext = plaintext1 || plaintext2

That way you don't suffer message expansion by going to larger keys.

We could also use the RSA padding for the padding seed value, saving
16 bytes per intermediate hop.

The overall message size is fixed to 20k, and the payload is fixed at
10k, so the max number of hops you get depends on the public key
sizes, and the size of the symmetric encryption.

So if we use for example 1024 bit RSA keys, and assuming average
remailer address lengths of 25 chars that's:

(1+128+8+16+16+2+1+16+2+25)*n+2

So we could have a 47 hop remailer chain in the allotted 10k

Using my suggestion of transferring plaintext as well as session-keys
in the RSA packet, if we assume 20 bytes of RSA padding, and we reuse
the RSA padding as the padding seed, we get:

(20+16+2+1+2+25)*n

which would give a max chaing length of 155 hops.

I suspect that's a little long, and it might be better to make the
thing more efficient by having a 18k payload and 2k header and have a
max of 30 or so hops (depending on remailer address lengths).

- might also want to investigate using the non-interactive forward
secrecy protocol [1] based on the identity crypto construct of a
composite modulus diffie-hellman key with parameters chosen to be
smooth enough to make computing discrete logs feasible, but retaining
reasonable security against factoring.  Need to investigate how large
parameters are feasible and what the safety margin is as a result.  As
we're already relying on a valid clock to some extent (the timestamp
field will eat messages with wildly out clocks as suspected replays),
we could then use an "identity" of the current day (+- 3 days), and
the remailer could delete day "identity" keys after the expire.

Adam

[1] http://www.inet-one.com/cypherpunks/dir.1998.05.25-1998.05.31/msg00171.html

Minor stuff:

- it's not explained what the Timestamp is for.  

The mix implementation caches packet-IDs for 5days or more, and by
discarding messages with expired Timestamps outside of this range, it
prevents replay with a relatively small packet-ID cache.  At least
this is what I presume it's for.

- section 3.3 "fill to 20 kiB" should be "fill to 20 kB"

- section 3.3 "XXX" is presumably a place holder for a description of
what the padding seed value is for

- Is a remailer address size of 2 bytes really necessary?  Do we
expect remailers with email addresses > 256 chars?