Anubis Working Notes, Plain
	ANUBIS:    ANonymity via Unix-Based Information Services

			Some concerns about anonymous services

Some important remailers have already been compromised, thuough this is
not widely publicized as yet.

People should check their names with anonymous remailers; one hacker was
recently surprised to find a bounce message indicating regarding the
status of their new anonymous remailer account, one they hadn't actually
applied for.  Further investigation revealed that someone had cracked
their system and applied for the remailer account under their name.
Only the fortuitous email bounce revealed the attack on the hacker's
digital reputation-- it is entirely legitimate to consider this a direct
attack, it is difficult to come up with plausible benign motives for
this series of actions.

			Design Goals of Project

The compromise of any portion of the anonymous remailing system should
result in as little intrusion as possible.  Compromise of an individual
user should not put others at risk through known-content-encryption
attacks and similar methods.  Compromise of a remailer host should not
affect the security of recipients identity, transactional data, message
content, or keys.

			Implementation Goals of Project

Design of a complex system always involves a series of trade-offs
between conflicting goals.  In the case of ANUBIS, the primary goals are
anonymity and scalability.  Some of the methods presented in this paper
protect an individual's privacy in an exemplary manner but do not scale
well.  Other methods scale much more gracefully but are more subject to
determined traffic analysis attacks.  And of course, ultimately even the
best security is worthless if it is too difficult to install, maintain,
and use.  Ultimately, the end-user must choose the level of trade-off
with which he or she is comfortable.

The ANUBIS method is to make available a range of preconfigured choices
which represent a design space delimited by three axis: anonymity,
scalability, and usability.  By reliance on already available Unix tools
and protocols, much of the burden of installation is removed from the
site administrator and the learning curve required to maintain the
package is substantially flattened.  While moderately sophisticated
agents must be packaged for end-use, this can be easily done via
supplied scripts which will run on a wide variety of systems.  The
scripts can be implemented in MetaShell, a public domain "compiler"
which produces highly portable Bourne shell code.

We need to make truly anonymous remailer services, something which may
be much more difficult than many people currently believe.  One-way
outbound mail is fairly easy, although precautions should still be taken
to prevent timing analysis methods of determining identity

Two-way anonymous email requires internal recordkeeping to allow mapping
of anonymous identities with email addresses to send replies and
messages to.  This approach is, of course, inherently dangerous, and I
would like to propose a different approach using public-key cryptography
and digital signature technology to validate identity.

			Some Methods for Anonymity

First the simple technique, for a remailer not much different than those
in use today:

	* you request an anonymous ID

	* the mailer processes your request 

	* the mailer queries some arbitrary number of public key servers
and DNS sites (not just one or the default one!)  to get consensus on
your info and your public key

	* the mailer mails you the information encrypted in your public
key; thus if someone is spoofing you, they still don't have the info
necessary to read your mail from the remailer, though they can still
compromise the data tables of the remailer or do traffic/timing analysis
to find out who you are

Variants on the existing technology; multiple variants can be combined.

	Variant 1: the mailer mails you all correspondence encrypted in
your public key

	Variant 2: the mailer only accepts outbound anonymous mail
encrypted with the combo of your key and the mailers (I handwave, not
knowing details but knowing you can create something that authenticates
you in your own key); basically only accepts outgoing mail digitally
signed by you

	Variant 3: your initial request is digitally signed by you and
one of the things the mailer checks when processing your application is
the keysig equiv of DNS reverse IP lookups, ie that the info you give
matches with the info on the key server(s).

	Variant 4: your original encrypted request specifies a method of
acknowledgement delivery from a limited arbitrary subset, which the
mailer service is authorized to carry out.  All acknowledgements are
encrypted in your public key, of course.  Some examples:

		* ftp a file to a public incoming drop box

		* post a GIF file of a particular name from a particular
ID to; GIF file has SAAR/Stego encoding of the info in
your key

		* create an object on a particular MOO that the remailer
has privs on, said object containing the data in question

		* POP connections to redist sites

			- This may work if there are several large
redist sites with many legitimate users.  However, the POP connection is
still subject to monitoring by conventional methods (connect

		* publishing digests of stuff encrypted on a newsgroup,
you grab the digests, they're safe as they are encrypted

			- Eric H complains this doesn't scale, and he
doesn't want to invest in any tech which doesn't scale.  But my belief
is that you have to have a broadcast channel or you can't get true

			- One could probably "train" a mailer to get
stuff from newsgroups in encrypted format, then remail it.  Could use
anonymous posting services (hah, I suspect they're as full of holes as
anything else) to put up messages for later remail.

I suggest running modified DNS, "KeyNS" to do dynamic update of keys,
with key authority servers for zones.  Eric H wants to modify DNS to do
forward updating.  I don't know how much he knows about DNS, you can set
TTL's and such so that records for key services are not cached and are
updated in realtime.  Bind 4.9 has forward updating built in but not
often turned on.

			Some Issues 

Protect against traffic analysis attacks:

	* all anubis communiques are of fixed length (padded)

		- user can specify padding level at which anubis mailers
connect to user's mailer

		- anubis mailer specifies padding type in encrypted body
of message

		- padding types vary; never pad with nulls, always pad
with random text, padding method indicates how to unravel message

		- some possible padding types: every nth line, every nth
word, every other paragraph for some value of paragraph, etc; since you
have to use a wrapper to deal with the encryption, it's easy to add a
padding-unraveller as well, to strip padding from text before its
presented but after its encrypted

	* user can specify volume of customary traffic between anubis
mailers and user's mailer
		- constant, at arbitrary volumes
		- variable, deterministic
		- variable, non-deterministic (or best approximation thereof)

	* user can specify list of trusted anubis sites on a per-user
*or* per-site basis

	* Another open question is whether we should build some
mechanism into the anubis mailers which would allow interactive query
via message exchange for authentication by the user.  While facilitating
repeat identification of a trusted host, the mechanism would require
specific data to persist on the host.  This would again violate the
basic paradigm of ANUBIS internal data management: leave only FINWAIT,
take only SYN/ACK.

	* In addition, reliance on an authentication method independent
of hostname/IP/socket tuples increases an intruder's ability to spoof
identity of a mailer once that mailer is compromised.  While there is no
inherent reason why the tuple could not be
"hostname/IP/socket/encrypted-padded-pass-phrase", a naive user
community can quickly degenerate into undue reliance on the pass-phrase
authentication, believing it more flexible and/or easier to administer
than checking the other elements of the tuple.

	* An open question is whether or not we should allow users to
specify that longer messages be broken up and reassembled at their

		- precludes need for excessive user intervention in
traffic patterns/flow: send out lots of text one day, little the next,
it just works *up to a point*
		- need to specify how to handle communiques which
aggregate to more than the customary traffic flow; variable
non-deterministic traffic selection can alleviate this but introduces
the variable which we are trying to explicitly avoid, ie a delta in
traffic which is directly proportional to the amount of information
being exchanged with the mailer

		- also requires a mechanism to make message delivery
suitably atomic, above and beyond sendmail's already lossy per-message

			> If the mailer tracks the sections, we're right
back to where we were earlier, where a mailer being compromised can lead
directly to compromising individual mailer destinations, both on content
and on identity/destination.
			> If the user package tracks sections, it should
be able to autogenerate (probably upon confirmation by user) a query to
the originating package to resend either all or just the missing parts.
			> This implies also that the user package on the
other end can do so, ie that it's keeping some sort of internal tables
on multipart messages and possibly even copies of the message.  However,
not all messages will be files, some will be extemporaneous text or
graphics which for whatever reason will not be saved as files.
			> Furthermore, there will inevitably be
information that will be perceived as too sensitive to file, either in
plaintext or encrypted form.  Or perhaps the user has renamed or moved
the original file.  In either case, the remote user is SOL, though
admittedly no more so than she or he would be with a lost single-part
message.  I would argue that it is demonstrably poor form to provide a
facility which claims to regenerate partial messages that has in fact
severely limited powers to do so.
			> Perhaps an acceptable compromise for those who
insist on multipart messages is for the user package to keep a table
with a filename and optional brief note (for which the user is prompted)
about the contents.  Upon notification of a "lost" multipart message,
the user package could present the user with a notice to regenerate the
message, possibly accompanied by a pre-filled-out template from which to
rebuild the lost message.
			> Note that the multipart message table
represents a substantial security risk, even if encrypted.  It contains
incidental and transactional data that may be subject to informed
analysis, putting the privacy of the user's key potentially at risk.
This makes a "false replay request" style of attack much more
attractive-- note that anyone could spoof a replay request if they
possessed a compromised server to use in the attack.  Once a table has
been cracked, both the user's privacy and the privacy of anyone
receiving the multipart communique are then violated, putting recipients
at greater risk of key compromise due to content analysis (contents of
message sent are now in some part known).
			> Mailer authentication methods are too large a
can of worms to get into here, but suffice it to say that they are in
large part designed to make sure that someone receives the message, and
are often (usually) not designed to handle the case of deliberate and
determined spoofing.  Some of the newer X.500 protocols may address
this, but this is a transport layer specifically outside the scope of
this discussion.

			Cracking Potential

First and foremost, we should assume that anyone who is sufficiently
interested can get a copy of the distribution, alter source code to
compromise the mailer delivery system, and advertise themselves as
"anubis.evil.domain".  Such are the hazards of public domain software.

In considering the security of ANUBIS methods, we should construct cases
involving several levels of motivation and technical skill on the part
of the potential intruders.

	* "black hats" who know as much as we do
	* random feds/law enforcement
	* the terminally nosy
	* the whole  NSA (bleah) 
		- start out assuming complete packet replay for some 
arbitrary and implausibly large amount of time (months, possibly years)

		- have to assume your home system is not compromised,
otherwise what's the point.  Note that part of the design goal of ANUBIS
is to minimize the intrusion's ability to decode intercepted
transmissions once the home system is no longer secure. [7/25/94:
clarification: home system == system you compose and encrypt outgoing
mail on; ie if someone watches you send the mail and/or snags copy of it
at origin point, you lose right there]

			Sample scenarios

* Post to netnews anonymously, one way

* Post to known mailing list or user anonymously, one way

* Communicate with anonymous user, attributed, one way

* Communicate with anonymous user, anonymously, one way

* Post to netnews anonymously, enable replies

* Post to known mailing list or user anonymously, enable replies

* Post to anonymous user anonymously, enable replies

Anubis mailers should store stuff for individual NYMs, dump on
authenticated request.  Problem-- don't want tcp monitoring to pick this
up!  Furthermore, it is undesirable to have someone on the anubis mailer
system monitoring fopens and doing timing analysis, need to incorporate
a delay mechanism and/or routing mechanism similar to nntp.  May be able
to adapt nntp protocol to build anonmailing parallel hierarchy, but
can't put all our eggs in this basket or most hosts will be unable to
run anubis mailers.

A NYM could send a request to various anubis mailers to send his or her
stuff to a particular host.  Would have to be encrypted in that NYMs key
as received via authentication service--- hmm, that's a loophole....can
we hash NYM keys in some fashion so that we can afford to churn through
keys rather than have a correspondence table?  Anubis mailers will have
to have strong ideas about who to trust, and this may be an insoluble

How about a double wrapper key system?  You have to hand the mailer a
key with which to unwrap their encryption of your public key; if the key
you hand them doesn't unwrap your public key, you can't be spoofed.  And
of course, you do secure key negotiation for that session (for each
session with anubis, actually; you need to be able to put these requests
in the normal back-and-forth of the anubis traffic).

Where do I get a NYM's public key?  Let's assume that when I create a
new NYM, I check the key servers to see that the NYM is registered and
that the name field and the public key field match.  I deny the request
if they do not.  If someone has programmed me to be nice, I can register
them with the name and key they hand me if the name is not already
taken.  [7/25/94: clarification: I == the mailer, I am musing in the
first person in this paragraph and a couple below as if I were the
mailer.  Did I mention these were rough stream-of-consciouness notes?]

We may or may not want to search key space as well, and refuse to
register NYMs who are using the same key as a registered user or NYM
under a different name.  This is not to say that the key servers should
disallow this, just that we would not facilitate such a registration

[7/25/94: clarification: I originally envisioned automatic registration
of NYMs being done via the mailer at the point where I wrote the above
paragraphs, and/or using the mailer to autoregister new NYMs that pwople
send it.  I don't know if that is a valid approach; certainly there
needs to be software included in the distribution to register NYMS, and
there needs to be an anonymous way to register them (else what's the
point), but this aspect deserves much more thought. _S]

Okay, so I have received a piece of email that claims to be for a
particular NYM.  I don't care about content, I encrypt it in his key
with a random padding method, carefully enclosing the message in a
wrapper that tells the padding method to use to get the bulk of the
message out.  Hmm, this may be a potential security hole, someone could
send messages requesting a particular padding to study structure.  We
could disallow request overrides for padding messages for internal
storage.  We could also or instead insert the padding instructions
randomly inside the message body with special delimiters, checking to
make sure we don't put it between a pair of quoting characters.  A user
agent receiveing it could then scan the message for body-padding info
once it's unencrypted, edit out the info, then decrypt the message body
(if necessary) and undo the padding from there.

		But How Do I Get My Mail?
[see also slides!]

Anubis mailer connects as scheduled to your site

	* You and anubis mailer negotiate a secure session key

	* You & mailer begin exchanging fixed length text messages
containing randomly padded encrypted stuff (in the session key); some of
these exchanges contain buried control strings

	* You ask mailer if NYM-FOO has any mail.

	* Mailer looks up NYM-FOO's key and encodes a challenge to you,
using the mailer's private key and NYM-FOO's public key of record, then
wraps it in the session key and delivers it.  (Challenges should be
suitably unique and non-deterministically generated.)

	* You respond to the challenge; simply repeating the text of the
challenge back to the mailer is sufficient.  Again, your response (as
all communiques) is encoded in the negotiated session key.

		- At the beginning of each anubis session, you look up
the public key of the anubis mailer; thus it is habitual traffic and not
subject to traffic analysis which might show when you were actually
receiving mail.

	* The mailer delivers mail for NYM-FOO to you, within the guise
of the fixed length padded traffic.  Control sequences that you send to
the mailer in your initial few communiques (or in your challenge
response) indicate the amount of mail you are willing to accept and what
processing options you request or insist on (do/don't break up large
messages, do/don't increase this session's traffic to deliver mail,
do/don't confirm delivery, do/don't automatically schedule larger
sessions over a timeperiod of N to accomodate waiting mail [that one's
dangerous, may be too risky, puts table based info that could be used in
analysis attacks inside the mailer!]

			NYM Management

Should NYM's be allowed to specify that their mail be broken up over
various anubis mailers?

Or that their mail always be sent to a particular anubis mailer?

Should mailers be allowed to send notices to other mailers asking that a
NYM's mail be concentrated in one place?

	* denial of service attack 

	* tcp monitoring entrapment attack 

Should NYMs have a home mailer?  
	* If so, should it default to the one that registered them?  

	* Move home mailer with challenge/response authentication in 
NYM's public key.  

	* Should anubis mailers route stuff to a NYM's designated home mailer?  
	* Should the home mailer info be made public?  

		- If it's in a table in the mailer somewhere we have to 
assume it will be public sooner or later, so should we build such a facility 
into it in the first place?

The anubis mailers should always convert plain text into encrypted text
as quickly as possible.  We need rules for them to do this.
Specifically, we want to convert the text in as speedy a fashion as
possible, yet we don't want to enable tracing attacks based on when the
anubis mailer looked up a recipient's key.  Should mailers cache a key
(from fresh lookup) whenever they make a connection to a particular
person, or must a key server with substantial database live on the same
machine?  How do we prevent timing analysis attacks on key server

Key servers need to be able to do negotiated secure key exchange to talk
to anubis mailers & vice versa.  Batching key requests would help
eliminate the scary overhead this will take, but will still leave the
annoying problem of not having stuff in text too long.  Though basically
we can assume that anything we get in text has been sniffed to death and
perhaps just encrypting it in a mailer-local key will be sufficient
(prevents people less motivated than sniffers from idly browsing, you
must crack root on system, then dig key out from several levels of
mailer indirection).  Of course, if someone compromises the key server
and logs requests internally, you're still fucked.

All of this makes reliance on the post-send encryption feature a poor
idea, and it is an open question as to whether we should support the
feature at all, given that reliance on it can lead people to unwise
actions.  It's arguably better to circumvent the perceived technological
barrier of local encryption and registration by making the user agents
include a programmatic kit for key registration.  This still leaves the
problem of getting and compiling PGP, which will prevent some people
from bothering to do so.  However, I believe that any attempt to include
PGP in the release and have key generation done by the user agent will
make said agents too attractive to potential compromisers.  Perhaps the
best approach is to make ACCEPT_CLEARTEXT a settable option in the

[7/25/94: clarification: after discussing PGP innards & such with Phil Z
at Defcon II, I believe that the right thing to do is to structure the
release such that the latest copy of PGP is always bundled in with the
release; it can be built separately and is not *integrated*, merely

	What Can I Find Out by Compromising An Anubis Mailer?
	[7/25/94: see also slides]

		* the text of any cleartext messages that pass through,
prior to packaging encryption.  See previous notes on the pros and cons
of supporting cleartext -> packaging encryption.

		* which encrypted messages were picked up by a
particular IP address and when

		* the NYM any encrypted messages were for

		* the encrypted body of messages

		* a record of how an encrypted message was salted, who
it was queued for (NYM), what site picked it up: this gives you known
text if the message started out ASCII but only the already encrypted
body if it started out cipher.  If you generate a large volume of test
messages of different known phrases sent to one NYM that could be
trouble, but people can already do that level of key attack analysis on
each other.

		How Can I Manage Keys for various NYMs?

* I Trust My Physical Security: Keep the key ring on a floppy or
something else that you hold securely; load or mount the floppy when key
use is desired.

* I Trust My Data Security: Keep your key ring on your home machine.

* I Don't Trust My Data Security: Keep your key ring on your machine but
encrypt it and keep that key offline.

* I Don't Trust Anybody: Write a simple program that will deposit the
pieces of your key in a matrix of arbitrary size composed of plausible
key pieces.  At this point you can choose an algorithm for the piece
deposit that either requires a computer or a patient human or an
impatient human to decipher (ex., every Nth - 13 * Xth bit is the key)
and leave the matrix online or print it in small font on a card, which
you can laminate and keep in your wallet or some other secure place.  If
the algorithm is complex enough, you have secure key storage provided
that your head is not compromised...

	- Whether or not to write the names of the various NYMs on the
cards is left as an exercise for the reader's paranoia.

I welcome comments on these preliminary specifications for the ANUBIS remailer. An identical version of these notes with section numbers is available for ease in making comments; please refer to the section or subsection number in its entirety. I hope to make comments available as annotations to the text, so please indicate whether your message can be added to the Anubis archive as a public annotation. If you do not explicitly grant permission I will assume that permission is denied. Please mail comments to; it is helpful to include the word "Anubis" in the subject.

View Numbered Notes

Back to Anubis Home Page

View Slides