Mixmaster Security Issues

Apart from thwarting traffic analysis attacks, how does the security
of a Mixmaster Type II remailer packet compare to that of a
PGP-chained Type I message?

For example, is each remailer in the path limited to knowing only
the next remailer in the path?  Is there any way for a remailer
(except for the first and last in the chain) to know how many hops
have already occurred or how many remain?  Is there a session key
chosen via an RNG?  If so, how random is the RNG?  Is it seeded from
a pseudo-random source that's at least as secure as measuring
keystroke latencies, as PGP does?

Lance Cottrell's original "remailer essay" which proposed the Type
II concept envisioned, if I'm not mistaken, the use of PGP
technology to do the actual encryptions.  Now it seems that another,
seemingly proprietary, implementation of RSAREF was used, instead.
What was the reason for this change?

Would any security be lost if Type I and II technology were combined
and a PGP-chained Type I packet were initially sent via Mixmaster?
This would would seem to provide the necessary protection against
traffic analysis while bypassing any *POSSIBLE* hidden weaknesses in
Mixmaster.  IOW, if the outer Mixmaster "envelope" were "steamed
open", perhasps based on some hidden weakness in Mixmaster, the
inner, nested PGP envelope(s) would remain intact.

BTW, what volume of message traffic is the Mixmaster network of
remailers currently handling?  Is much cover traffic necessary to
minimize delays while providing enough reordering to thwart traffic
analysis?  (IOW, so a remailer with a reordering pool size of five
messages, and averaging one REAL message a day, wouldn't have to
keep a message for an average of five days before sending it on its
next hop, as a worst-case scenario).

Is my math correct in surmising that chaining a message through five
remailers, each with a reordering pool of five messages, could mean
that the message eventually leaves the chain as one of 5^5 (3125)
possible messages?  (My math is a bit weak, so please feel free to
correct my methodology, if necessary.)  If so, does that work in
reverse?  Could a given output message that finally surfaced in the
clear be narrowed down to one of 3125 Mixmaster input messages
through traffic analysis?  Or would the fact that the attacker
didn't know the exact number of hops utilized significantly increase
the odds against identifying the sender?  What effect, if any, would
increasing the number of available remailers have on traffic
analysis?

Date: Wed, 30 Aug 1995 18:17:02 -0700

Can't answer all of your questions, but I'll answer the ones I can,
which will save time for someone else to answer the rest of them.

   Apart from thwarting traffic analysis attacks, how does the security
   of a Mixmaster Type II remailer packet compare to that of a
   PGP-chained Type I message?

Well, on the one hand, PGP uses IDEA, which is arguably better than
triple-DES, but PGP also only uses the key length(s) of choice, which
is to say that if you use the minimum length, you have very little
security.  Also, Mixmaster packets remain the same length from hop to
hop, so they are harder to track.

Not every PGP remailer reorders.

   For example, is each remailer in the path limited to knowing only
   the next remailer in the path?

And the previous one.  For PGP-chaining, that tells you a lot, because
you can observe the message length getting smaller.

   Is there any way for a remailer (except for the first and last in
   the chain) to know how many hops have already occurred or how many
   remain?

No.  The hop list is a constant length, and the list is back-encrypted
through the chain, so that all you can ever know is the next hop,
which the previous remailer couldn't know because it couldn't decrypt
it.

And not even the first or last necessarily!  Both the source and
destination are running Mixmaster (by definition).  There's no reason
why mixmaster must remail -- eventually it delivers.  And someone
sourced the mail using Mixmaster.  If the source or destination is not
on an advertised remailer, or the destination was non-local to the
destination remailerthen it's pretty obvious that someone on that host
is an endpoint.  But that's one of the beauties of Mixmaster --
there's a large security increase in setting it up as a remailer and
advertising it.

   Would any security be lost if Type I and II technology were combined
   and a PGP-chained Type I packet were initially sent via Mixmaster?

Security is increased.

   Is my math correct in surmising that chaining a message through five
   remailers, each with a reordering pool of five messages, could mean
   that the message eventually leaves the chain as one of 5^5 (3125)
   possible messages?

You're ignoring the case where it is to/from a machine that runs a
public remailer.

-- 
-russ <nelson@crynwr.com>    http://www.crynwr.com/~nelson
Crynwr Software   | Crynwr Software sells packet driver support | PGP ok
11 Grant St.      | +1 315 268 1925 (9201 FAX)  | America neither a Christian,
Potsdam, NY 13676 |  Jewish, Islamic, nor atheist (etc&) nation.  This is good.