Public Anonymity (Re: FIPR Release 16/10/2001: EMERGENCY POWERS ALLOW MASS-SURVEILLANCE FOR NON-TERRORIST INVESTIGATIONS

[Peter Fairbrother]

> Richard Clayton wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
> 
> In article <005f01c1572f$060bca80$742b4ed5 at fleetfoot>, Paul R. Pettitt
> <prpettitt at onetel.net.uk> writes
> 
>> All you need do is use a free service like that at http://www.anonymisers.com
>> and nobody is able to monitor or log what you read or post.
>> 
> "nobody" is too strong ... the people who run that web site are in a position
> to log what you do -- they may well not choose to do so, but that's not quite
> the same thing.
> 
> They seem to have a clear understanding of what they are offering, and their
> FAQ is quite sensible, starting as it does with the sentence:
> 
> The answer to the big question quite simply is - no. It is not possible to
> ever be totally anonymous on the Internet despite what anyone else may try and
> tell you.
> 

This is simply wrong. There are several techniques which can provide public
anonymity, ie anonymity when _all_ parts of the communication system are
compromised. Some are well-known.

I have been working on this for some time, for possible inclusion in
m-o-o-t. I'm thinking of publishing a paper on this soon, and I have
attached part of an early draft of the introduction, which gives an
overview. It's just notes, I haven't finished it, so don't expect total
accuracy 
(or clarity).

-- Peter Fairbrother


.............................

Public Anonymity.

Public anonymity is anonymity when all the inner workings of the
transmission system are public, so anyone can see what is transmitted,
stored, manipulated, see who did it, but still can't detect if a message is
sent, or who the sender or recipient are *.

To set a scene, Alice wants to send Bob an email. Alice's comms with her ISP
are tapped, so are Bob's, and all the mail servers and anonymous remailers
in the world are secretly run/compromisable by the FB!/NSA/GCHQ. Also, Alice
and Bob are potentially subject to Court orders to reveal keys to encrypted
data.

There are several ways that this can be accomplished. Steganography (sending
hidden messages in eg pictures on the web that are accessed by many people)
is an obvious example, but it suffers from the disadvantage that if a
receiver is compromised than the sender can potentially be identified. So,
to a lesser extent, do simple broadcast systems or just-a-bunch-of-files
systems (I just stole/made up those terms). (Also, most stego software
writers don't know what they are doing, which I can quite understand as it
is usually theoretically impossible for them to do so **.)

A simple broadcast system works like this: eg 1 million users (including
Alice) each contribute on average 10 (some random, some signal) bytes/sec to
a 10MB/s broadcast signal. It's fairly easy to arrange for only intended
recipients (or a subset of them) to be able to determine which bytes of the
broadcast are meant for them, and to be able to decode only those bytes.
This system requires Bob to be online all the time.

A just-a-bunch-of-files system works like this: Sid (the server) makes a lot
of files and fills them with random data. Alice (and everyone else)
overwrites some of them with either encrypted or random data (and perhaps a
time). Bob reads _all_ the files from Sid's public database, and decrypts
those files intended for him, including Alice's message, with covertraffic
from the other users for anonymity. This requires Bob to read a lot of data,
but allows him to do it not in real time, ie Alice and Bob don't have to be
online at the same time. It also requires that Bob collects his messages
within a short time, otherwise they will be overwritten.

Anonymity in both these systems comes from Bob receiving lots of data, only
some of which is meant for him. The senders of data meant for him can't be
identified. Another twist, to foil traffic analysis and provide plausible
deniability against Court orders to reveal keys, is the sending of
meaningless data as a part of the system, eg: whenever Alice logs on,
whether or nor she has a message to send, she sends data. With good crypto
it is impossible to tell if she actually sent a message.


The difficulty with both these systems is the large amount of data Bob has
to read. It is possible to put this large transfer requirement on Alice
instead of Bob, but not much is gained overall by doing so. Simple
techniques to reduce transfer in these systems, eg Bob connecting at a set
time of day in the first case, or reading only a subset of the files in the
second, only reduce anonymity.

-----------------------------

(the paper itself will describe two methods for reducing this transfer
requirement, without decreasing anonymity, They're based on SFS-like
technology, undetectably moving hidden data around a too-big-to-transfer
SFS, actually doing it as part of other user's writes) (I hope, it's not
finished yet!)

----------------------------

* (There is another potential qualification, that the very existence of
Alice and Bob's comms can't be detected, but I won't fully address that
here, because in the present situation it isn't relevant. If Governments
impose requirements for key escrow, or mandate encryption software control,
it may become relevant. This attack can be defeated, though the useable
bandwith may become very low, and users may be required to generate lots of
plausible covertext and/or (shared) key material.)

** I'd love to argue this with you, but I will only do so once (unless you
are really interesting).