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 correspondence. 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 identity. 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: 5.2.4.1 ftp a file to a public incoming drop box 5.2.4.2 post a GIF file of a particular name from a particular ID to rec.foo.binaries; GIF file has SAAR encoding of the info in your key 5.2.4.3 create an object on a particular MOO that the remailer has privs on, said object containing the data in question 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 anonymity. 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) 6.1.1.1 user can specify padding level at which anubis mailers connect to user's mailer 6.1.1.2 anubis mailer specifies padding type in encrypted body of message 6.1.1.3 padding types vary; never pad with nulls, always pad with random text, padding method indicates how to unravel message 6.1.1.4 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 6.1.2.1 constant, at arbitrary volumes 6.1.2.2 variable, deterministic 6.1.2.3 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 6.1.6.1 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* 6.1.6.2 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 6.1.6.3 also requires a mechanism to make message delivery suitably atomic, above and beyond sendmail's already lossy per-message mechanisms 6.1.6.3.1 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. 6.1.6.3.2 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. 6.1.6.3.3 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. 6.1.6.3.4 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. 6.1.6.3.5 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. 6.1.6.3.6 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). 6.1.6.3.7 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. 6.2.2.1 "black hats" who know as much as we do 6.2.2.2 random feds/law enforcement 6.2.2.3 the terminally nosy 6.2.2.4 the wholeNSA (bleah) 6.2.2.4.1 start out assuming complete packet replay for some arbitrary and implausibly large amount of time (months, possibly years) 6.2.2.4.2 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. 6.2.2.4.2.1 [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 replies 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 process. 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 key 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 generated.) 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. 7.13.6.1 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 fucked. 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.13.11.1 [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 strata@virtual.net; it is helpful to include the word "Anubis" in the subject.