analysis of RemailerNet

[Wei Dai <weidai@eskimo.com>]

-----BEGIN PGP SIGNED MESSAGE-----

I've been reading through T.C. May's FAQ, and came upon this 
section about analyzing the RemailerNet.

>            + What's needed:
>              - aggreement on some terminology (this doesn't require
>                 consensus, just a clearly written paper to de facto
>                 establish the terminology)
>              - a formula relating degree of untraceability to the major
>                 factors that go into remailers: packet size and
>                 quantization, latency (# of messages), remailer policies,
>                 timing, etc.
>              - Also, analysis of how deliberate probes or attacks might
>                 be mounted to deduce remailer patterns (e.g., Fred always
>                 remails to Josh and Suzy and rarely to Zeke).
>            - I think this combinatorial analysis would be a nice little
>               monograph for someone to write.
>    8.10.2. A much-needed thing. Hal Finney has posted some calculations
>             (circa 1994-08-08), but more work is sorely needed.

I think one of the most difficult aspects of analyzing remailers is 
the large number of variables you have to deal with.  In 
contrast, when analyzing ciphers things are pretty much 
static.  The only thing variable you have to worry about is 
key length.  But think of the factors you have to include in 
a complete analysis of the RemailerNet:

1.  different methods of attack
        - passive traffic analysis (i.e., packet sniffing)
        - active attacks: including physical attacks, subverting 
          remailer security, flooding, denial-of-service,
          starting "trap" remailers, etc.

2.  differences at the user level
        - fixed vs random chains vs something in between
        - length of chains
        - numbers of real messages sent
        - numbers of fake (cover) messages sent
        - concerns about latency, bandwidth, and monetary costs
        - acceptibility of risk, and benifits of anonymity

3.  differences at the individual remailer level
        - the mixing mechanism: does batched mailing occur by time or by the
          number of messages in the queue, and is there a rollover pool?
        - security: including vulnerabilities to political, 
          physical, and electronic attacks
        - usage level
        - price

4.  differences at the RemailerNet level
        - total numbers of remailers
        - average security (or the number of compromised remailers)
        - total number of users

... and I'm sure there are more.  The number of variables and the 
complex way they're all interrelated make the analysis 
difficult.  Perhaps a good way to go about this is to construct 
simplified models which focus on different aspects.  For 
example, someone pointed out that if you didn't have to worry 
about active attacks, and the attacker can monitor all the 
remailers, then you can treat the entire RemailerNet as a 
single large remailer.  I'm not sure how well this approach 
would work, since I don't know how easy it would be to 
integrate the different simplified models into a realistic one.

Anyhow, this might at least give us some insights, so I'll 
make some attempts in this direction, and post my results.

Just to start things off though, let me try an *extremely*
simple model.

Assume there is just one remailer, it's perfectly secure, and it 
does 4 batches of remailing at equal intervals each day.  There are 
one million users, each of whom receives a mail from the remailer 
once per day.  Alice is sending anonymous mail to Bob through this 
system, also once per day.  But just to be extra careful, she 
also sends a cover mail to the remailer at some other time 
each day, which gets redirected to its /dev/null.

So the situation looks like this on day 1:

            Alice sends     Bob receives     some random user receives
Batch #1:       0                0                   0
Batch #2:       1                1                   0
Batch #3:       0                0                   1
Batch #4:       1                0                   0

Suppose Eve, the traffic analyst, is trying to figure out who 
Alice is sending mail to.  After the first day, she can 
eliminate about half of the remailer users from the list of possible 
targets, because they, like the the random user above,
received a mail even though Alice didn't send one out during the 
collection period of that batch.  Now, since Eve can eliminate 
on average half of the list every day, Bob will be the only person left on 
that list after about (log base 2 of one million) = 20 days.

Suppose Alice sent out some different numbers of cover e-mail:

        # of cover mail     # of days to discover Bob
               0               log base 4 of 1,000,000 = 10
               1               log base 2 of 1,000,000 = 20
               2               log base 4/3 of 1,000,000 = 48
               3               log base 1 of 1,000,000 = infinity!

Hopefully that makes sense...  Comments?

Wei Dai


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBLxU0QTl0sXKgdnV5AQFkoAP/SSyqbbDw+zoh+q5aL0+xr5BcLzaEoS4h
NASocZvKHGLe8/sfefDj4J2zPINKhmQzbKdD4oHirPEVbnWZC+7Us3giCKl80t2V
bKx6QPB1hJWi6n3cFme6NCuTjmHCsgrQ/bI2j524O43FhW6BIQAAxQ6GGN10t1V8
3nv3SzUC6jE=
=Y2qv
-----END PGP SIGNATURE-----