Anubis Working Notes, Numbered

1.0 ANUBIS:    ANonymity via Unix-Based Information Services

2.0 Some concerns about anonymous services

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

	2.2 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.

3.0 Design Goals of Project

	3.1 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.

4.0 Implementation Goals of Project

	4.1 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.

	4.2 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.

	4.3 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

	4.4 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 

5.0 Some Methods for Anonymity

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

		5.1.1 you request an anonymous ID

		5.1.2 the mailer processes your request

		5.1.3 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

		5.1.4 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

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

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

		5.2.2 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

		5.2.3 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).

		5.2.4 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 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

	5.3 POP connections to redist sites

		5.3.1 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 monitoring).

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

		5.4.1 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

		5.4.2 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.

	5.5 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.

6.0 Some Issues

	6.1 protect against traffic analysis attacks:

		6.1.1 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

		6.1.2 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)

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

		6.1.4 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.

		6.1.5 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.

		6.1.6 an open question is whether or not we should allow
users to specify that longer messages be broken up and reassembled at
their destination 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 mechanisms 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.

	6.2 Cracking Potential

		6.2.1 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.

		6.2.2 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]

7.0 Sample scenarios

	7.1 Post to netnews anonymously, one way

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

	7.3 Communicate with anonymous user, attributed, one way

	7.4 Communicate with anonymous user, anonymously, one way

	7.5 Post to netnews anonymously, enable replies

	7.6 Post to known mailing list or user anonymously, enable

	7.7 Post to anonymous user anonymously, enable replies

	7.8 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.

	7.9 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 problem.

	7.10 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).

	7.11 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.

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.11.1 [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?]

		7.11.2 [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 people 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]

	7.12 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.

	7.13 But How Do I Get My Mail?

		7.13.1 Anubis mailer connects as scheduled to your site

		7.13.2 You and anubis mailer negotiate a secure session

		7.13.3 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

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

		7.13.5 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

		7.13.6 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.

		7.13.7 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!]

		7.13.8 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 (doubtful, denial of service attack, tcp
monitoring entrapment attack both made easier/enabled by this)?  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?

		7.13.9 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 lookups?

		7.13.10 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

		7.13.11 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 mailer.  [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 *bundled*.]

	7.14 What Can I Find Out by Compromising An Anubis Mailer?

		7.14.1 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.

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

		7.14.3 the NYM any encrypted messages were for

		7.14.4 the encrypted body of messages

		7.14.5 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.

	7.15 How Can I Manage Keys for various NYMs?

		7.15.1 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.

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

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

		7.15.4 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...

		7.15.5 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. 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 Anubis Slides

Back to Anubis Home Page

Copyright 1994 M. Strata Rose, all rights reserved.