Re: How secure is SSL emails?

From: Nick Mathewson (QnickQm_at_freehaven.net)
Date: 06/30/04 

Date: Wed, 30 Jun 2004 20:04:23 GMT

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

In article <cbn96u$1s9g$1@calcite.rhyolite.com>, Vernon Schryver wrote:
 [...]
> Assume:
>
> - Your remailer generates no traffic eventually delivered to mailboxes
> at other systems except except as the result of real incoming
> traffic. This prevents your box from using the classic babbling
> defense against traffic analysis.
> This assumption is reasonable because of the practical problems
> in babbling without being seen as a spammer or mailbomber. To
> solve that problem in theory, all possible recipients of remailed
> messages could subscribe to a remailer network, and each output
> system in the network could continually send messages, using
> random garbage when there is no real message to send.
 [...]

This is so. There is a largeish category of theoretical anonymity
designs that _do_ use constant-volume padding to try to defeat traffic
analysis, but these systems are not suitable for remailer-like
applications on the Internet-as-it-exists-today.

Some researchers have proposed applications where (they say)
constant-volume padding might be practical. These tend to involve
smallish, closed sets of participants doing some limited-duration
operation.

(But naturally, if you have strong connectivity and can afford
constant-volume padding, then you might as well use Chaum's DC-nets.
They're sort of like the OTP of anonymity: provably secure under the
right assumptions, but almost never practical.)

> - There are only Guy Macon's "hundreds or thousands" of users.

This is a problem, of course. If there aren't enough users, then
all the attacks are easier.

> - There is enough traffic to analyze. You'll be encouraged to send
> more messages with the standard tactics, such as information about
> broken Pacific island fresh water systems. If you still send too
> few messages, then you probably don't need a high bandwidth system
> like SMTP remailers but can use old fashioned systems.

This point ("enough traffic") is critical, but it is, I think, more
subtle than you discuss here. I'll elaborate below.

> In this context, the goal for George is not discovering that you sent
> a message of X bits to Ted at a particular time, but only that you
> have a habit of sending messages to Ted. The purpose is not decoding
> your messages, but knowing where to dispatch agents to plant bugs or
> whom to round up when the time times.
>
> steps
 [...]
You present a special case of the long-term intersection attack. I'll
summarize the general case. The necessary assumptions are:

  A1. There is some variation in how much volume you send over time,
      and in how much volume some people receive over time.

  A2. George (the attacker) can get a good estimate of how much you're
      sending, and how much some people are receiving, at various
      points in time.

  A3. The communications medium (a single mix, or an entire mix-net,
      or something else) may introduce a random delay in messages, but
      the variance in this delay is finite, and George can get a good
      estimate of the probability distribution of this delay.

  A4. You send messages regularly, to certain recipients, for "long
      enough".

The steps are:

  1. George watches you sending messages over time, and watches
     everyone else receiving messages over time. (A2 says he can do
     this.)

  2. George notices that certain recipients are likelier to receive
     messages at about the time your messages might be expected to
     arrive than they are to receive messages when your messages are
     less likely to arrive. (A3 says that he can guess when your
     messages are likely to arrive; A1 says that there is a
     difference in sending and receiving volume.)

  3. George does some elementary statistics, and eventually guesses
     that the recipients in step 2 above are those with whom you
     frequently correspond. (A4 says that he gets enough traffic to
     get the required statistical confidence.)

These (passive) attacks have long been known, but the research
community has only recently started to examine their effectiveness.
Personally, I think that the key insight is that "enough traffic"
and "eventually guesses" cover up details that make a practical
difference. After all, if "eventually" means "after a dozen
messages", then you're screwed. On the other hand, if "eventually"
is long enough (say, a million days), then maybe this anonymity
could be good enough for some realistic users.

This approach is not wholly unlike what we use for cipher designs.
After all, a brute-force attack against a symmetrical with "enough"
computing power will "eventually" break the cipher--we just choose
ciphers with keys long enough that 'enough' and 'eventually' become
physically impossible. [Before anybody objects to the comparison, I
freely admit that we do not currently know how to make remailer-like
networks that are "physically" impossible to break.]

You noted this in your original message when you said:
> Thousands of users differ qualitatively from zillions just as
> encryption systems with 10 bit keys differ qualitatively from
> systems with 128 bit keys.
But number of users isn't the only variable. The key security
parameters are:
{I'm hand-waving here, see the papers below for better exposition.)
  1. How regularly and consistently you send traffic.
  2. How much traffic you send at a time.
  3. How much traffic there is besides yours.
  4. How much the traffic other than yours blends with yours.
     4a. How many regular recipients there are.
     4b. How your traffic is distributed among the recipients.
     4c. How other traffic is distributed among the recipients.
  5. Whether you send any padding messages (dropped _inside_ the
     network, typically); and if so, what strategy you use to send
     them; and how often you are offline and unable to send padding.
  6. The probability distribution of message delays through the
     network.
  7. The probability that the attacker sees messages leaving you or
     reaching each given recipient.
  8*. How your behavior changes over time.
  9*. How the behavior of the other users changes over time.

Current research has not, AFAIK, examined points 8 and 9 in any
detail.

Some papers that have looked at this are:
 1. http://freehaven.net/anonbib/author.html#statistical-disclosure
 2. http://freehaven.net/anonbib/author.html#DanSer04
 3. http://freehaven.net/anonbib/author.html#e2e-traffic

The first two papers are more mathematically rigorous than the
third; the third paper examines more "realistic" networks, but does
so by simulation rather than analytically. (Full disclosure: I am a
co-author on the third paper.)

Anyway, after all this build-up, the answer about the security of
mix-nets is still a big "maybe". Research on statistical attacks on
quasi-realistic mix-nets has as yet (again, AFAIK) examined
long-term security against end-to-end passive traffic analysis. You
should read the future work section of the third paper to see how
far we have to go before this research turns into a useful answer.

But hey, we're trying to answer these questions, and give people as
honest an answer as we can about the security of what they're using.
It isn't simply a matter of waving dead snakes, sacrificing a
chicken to David Chaum, and shouting "The Gods Of Anonymity Will
Protect Thee!" ;)

 [...]
> Remailer systems are based on this reasoning:
>
> 1. tracing email or at least packets through the internet is impractical.
> "No one can know if you're a dog on the Internet."
>
> 2. oops, #1 is false in the real Internet, so let's build a new
> overlay network where it will be true. Never mind why #1 is false
> in the real Internet. We'll design the remailer network like a
> classic bad random number generator or snake oil cypher with lots
> of hand waving and apparent complexity.

Heh. If you restrict your view of the field to the level of
technical discussion that usually happens on Usenet, I can see how
you'd get that impression. I agree that plenty of people have made
incorrectly grandiose claims for their systems. Also, for most of
the history of anonymity research, contact between the research
community and the deployed-remailer community has been tenuous and
sketchy.

But there's a growing research field in the area that really, really
wants to be rigorous, even if they can't agree on a research
program. Here's how I think the anonymity field works today:

  One day, Alice, Bob, and Carol wake up and decide to work on
  anonymous (that is, untraceable and unlinkable) communication for
  a while. It seems like a neat field. So they go out and read
  all the papers they can find, and spend a while thinking and
  talking about the issues involved.

  After a while, they read about (or reinvents) long-term
  intersection attacks; other long-term traffic analysis; active
  blending (flooding, trickling, n-1); blending-assisted traffic
  analysis; insider attacks; and so on. They realize that
  categorical defenses against these attacks are pretty much
  incompatible with having an open set of senders, an open set of
  receivers, a mostly-untrusted infrastructure, untrusted users,
  unreliable hardware, unreliable network connections, and so on.

  At this point, they part ways.

  Alice decides to work on designs that *can* offer categorical
  protection against the attacks above. In this case, she winds up
  designing systems that can't be deployed in practice on the
  Internet-as-we-know-it, or that can't be used for email-like
  applications. There's no shame in this. Alice stays in academia,
  and writes neat security proofs that the cryptographers like. She
  works on ways to relax her security assumptions without losing
  provably categorical security.

  Bob decides to work on the designs that can be built, and see how
  far their security can be improved against the attacks above. In
  this case, he spends his time designing systems (and sometimes
  building) systems which are "less" insecure against the above
  attacks, but not categorically strong. Bob might work in
  academia, or might just work on this stuff in his spare time. He
  spends his time trying to analyze which of the "eventually"
  successful attacks are most effective, and which proposed defenses
  work best against them.

  And in a completely different sub-community, Carol decides to set
  her research agenda by changing her threat model. (To heck with
  global adversaries!) She builds a low-latency network to
  anonymize web traffic, and writes a couple of papers discussing
  who can break it and who can't. Carol might work anyplace from
  academia to industry. (Because Carol's weak designs handle web
  browsing, she gets enough users to consider charging.) She spends
  her time trying to formulate slightly stronger attackers which she
  might frustrate for just a little while.

  Alice thinks Bob is misguided for not working on anything provably
  secure for all time. Bob thinks that Alice is impractical for
  never having designed anything that could be built tomorrow and do
  what he wants. Alice and Bob both think that Carol is perverse
  for not even trying to resist the adversaries they consider
  reasonable. Carol thinks that Alice and Bob are impractical for
  working on systems which apparently nobody is willing to use.

  Nonetheless, they still follow one another's research, each
  secretly hoping that this year, one of their others will have
  finally solved the hard problems.

That's an insider take on the field, sure. From the look of things,
you've got more hope for Alice's work. Personally, I'm with Bob,
but I'd be just as happy to see Alice succeed. In the end, I think
that this is really a question of research programs: making the
secure less impractical, versus making the practical less insecure.

yrs,
- --
 Nick Mathewson <Q nick Q m at freehaven dot net>
                      Remove Q's to respond.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA4xyUzgimHDtOLu4RAsMKAJ9uG+Ct5GzCzT59t94hC5MAgpJYiACeK76g
KViaPYQuPEBU3cIrWmx+kd8=
=wF5M
-----END PGP SIGNATURE-----