The Gnosis-Anon algorithmic pseudonym generator

Document Revision Date: Sat 06-14-2003

Gnosis-Anon generates "anonyms" for email addresses, and forwards any mail sent to those anonyms on to the corresponding real addresses. In other words, this is a protocol that allows anonymous recipients to get email.

So far, the implementation is fairly crude--consider this an early alpha. Nonetheless, it does what it claims to do; I welcome feedback or ideas at: mertz@gnosis.cx. I published an article on ONLamp.com that discusses Gnosis-Anon: see Prvacy and Anonymity in Email

Read the FAQ below for more information. There is also a TODO list at bottom. Or find an anonym right now

*A bug was found 6/14 that caused null bytes in the keys to break the forwarding. Unfortunately, fixing this invalidates all the old anonyms.


Find Gnosis-Anon anonym

Permanent Month Week Day
True Address:
[VALUE]
Anonym:
[VALUE]
Verify:
[VALUE]
Duration:
[VALUE]

Frequently Asked Questions

(at least they should be)

How does Gnosis-Anon work?

You can download the code for youself at http://gnosis.cx/download/anon/. That provides a more detailed answer.
Here's a short explanation. The protocol maintains several keys, each of which has a deletion schedule. Someone---you, your friend, your enemy, the NSA, etc.--submits an address to the pseudonym generator (this page). Gnosis-Anon first applies some compression to email address, then encrypts the result using a symmetrical encryption algorithm. The interface lets a user choose which duration key to lookup. Any time Gnosis-Anon receives email at the generated anonym, it forwards the message to a corresponding "original" address.
There are a couple caveats here, as well as a few special features. Once its encrypting key is deleted, mail received for a pseudonym cannot be forwarded to an original address. That's a primary feature. Gnosis-Anon quietly discards any received email that cannot be delivered. The internal criteria for deliverability is simply that an anonym decrypts to something that looks a little bit like an email address, using some available key; the message can still bounce for other reasons, of course. Moreover, the protocol deliberately has no way of distinguishing what duration key an anonym might have been generated with--nor, for that matter, whether a received message was genuinely encrypted with a key at all rather than merely invented.
A message forwarded by Gnosis-Anon has its original pseudonym stripped out of the headers. An anonym and its original address should never be contained in the same message, so no correlation can be established based on an archived message alone. A little blurb is added to the top of each message to provide context to a recipient. Also, Gnosis keeps no log or records of what pseudonyms have been used, nor of what original address have received forwards.

What is the difference between an anonym and a pseudonym?

Nothing, really. I just cannot decide which word I like better. However, calling it a pseudonym speaks more to the raw algorithm; while describing the address as an anonym speaks more to its purpose.

What is the point of all this encryption and key schedule mumbo jumbo?

Basically, the amount of information that a Gnosis-Anon server ever has available to reveal is very limited. Unlike in early systems like anon.penet.fi, no database mapping addresses to pseudonyms exists anywhere. A maintainer cannot reveal such utilized mappings under a court order, nor to a hacker who breaks into the server--it just doesn't exist.
Of course, the server must be able to perform a transformation between addresses and pseudonyms, so a mapping exists in a sense. But this mapping is purely subjunctive. I can reveal the fact that if Gnois-Anon were to receive a message addressed to the pseudonym <.zFPuTG+2P6Gm/Lp8@gnosis.cx>, it would forward it to <someone@somewhere.org>. Normally--if not subpoena'd or hacked--I would not disclose that. But even under a compromised situation, I have no knowledge of whether such a pseudonym was ever actually used.
The reverse mapping is perfectly public. Anyone in the word if free to lookup what pseudonym is assigned to <someone@somewhere.org>--even the "bad guys". But just looking up the fact that this mapping exists only lets someone send email to the anonym of an address they already know perfectly well (or else they would not know what to lookup). No information is disclosed by the availability of this lookup.
Notice also that once a particular key has been deleted, a mapping that was based on that key is wholly unrecoverable. All that can be revealed at a given moment is the collection of keys that are still current.

What about an identity guessing attack?

You got me. Having publicly available lookups does reveal something. If an attacker can easily guess a likely email identity of an anonym, she can carry out a dictionary/guessing attack. For example the address <mertz@gnosis.cx> is a really bad choice for an email address to use to generate an anonym--anyone who sees an anonym can come to this website, and enter my official address to check if the anonym belongs to me (an obvious thought that the creator might use an anonym). However, the hard-to-guess address <GnojlrdX@gnosis.cx> is a pretty good choice (or would be if I didn't just write it here :-))--I control the domain, and that address also comes back to me. For users who don't have their own domain, a single-purpose account at a free email service works too (but don't make the username anything obvious).

What is the actual key schedule?

The day key is refreshed at 4:00 a.m. each day; the week key is refreshed at 4:01 a.m. each Thursday; the month key is refreshed the 5th day of the third week of each month, at 4:02 a.m. I think my host is on Central Standard Time.
An obvious consequence of the key schedule is that a "day key," for example, will last a maximum period of 24 hours. If you lookup an anonym using a day key, at 3:59 a.m., it will only be usable for one minute (which is probably not what you want). Other key schedules could obviously be implemented, but this is what the current system does.

If you want an anonymous address, why not just set one up at Yahoo or Hotmail?

The anonymity provided by free commercial email services is only as good as the promise of those services. In my mind, that's not much. Under a court order--or even just at the monetary enticement of spammers--they will probably happily reveal everything they know or can find out about your true identity.

Why should I trust Gnosis more than I do Yahoo and Microsoft?

You shouldn't. You should download the code yourself, and run it on a server you trust. Or find someone else you trust more than Gnosis. Nonetheless, it is worth noting that the whole point of Gnosis-Anon is to avoid the need to retain any permanent records about its users.
Moreover, you can chain trust. If a number of servers support the Gnosis-Anon protocol, you can find the anonym-of-an-anonym-of-an-anonym. If one server actually logs all the messages passing through it, all it finds out is that some anonym maps to some other anonym. As long as there is at least one trustworthy server in the chain, recipient anonymity is protected.

Why is the chaining description in that last question not really true?

OK, I fudged things a bit. In order to aid compression, Gnosis-Anon currently canonicalizes email addresses to uppercase. But the actual anonyms Gnosis-Anon decrypts are case-sensitive. So chaining doesn't really work. For that matter, anybody who has a case-sensitive destination email network will probably have problems with Gnosis-Anon. Sorry.
It is simple to fix this limitation. But the cost of it is that anonyms grow quite verbose. An encryption step forces the email string into 8-bit, but that has to be downgraded back to 7-bit to pass through most email systems. Add that to the fact that the domain has to be encoded as well as the username, and anonyms can grow quite large if you don't use the compression and normalization.

Why not use the much better analyzed and refined Mixmaster (Type II) remailer protocol rather than Gnosis-Anon?

Mixmaster is extremely well thought out. Mixminion (Type III) is even better--or it will be when it is implemented in practice. These remailers combine public key encryption between jumps with complex "mixing" of message streams to resist traffic analysis. Many people far smarter than me have developed Type II & III remailers.
There's just one problem with Mixmaster: it has nothing to do with enabling anonymous recipients. The purpose of Mixmaster is to allow anonymous senders--which may have more uses even, but is not what Gnosis-Anon does. There is no need to choose between Mixmaster and Gnosis-Anon: you can perfectly well use Mixmaster to send a message to a Gnosis-Anon pseudonym, thereby enabling anonymity of both sender and recipient. Mixminion, by the way, will offer only "single use" anonymous replies, not persistent anonyms.
It is probably true that being to send messages anonymously has more uses than does being able to maintain a recipient anonym. Still, it is not hard to imagine scenarios where a limited group of people is trusted to distribute contact information for a recipient who must remain anonymous. And grafitti on a wall, or a post to a weblog (for example), provide possible distribution mechanisms for anonyms (walking up to someone and introducing yourself as "anonymous" misses the point).

How much protection does Gnosis-Anon offer against traffic analysis?

None at all. If someone can sniff the incoming and outgoing packets (or even sizes) of a Gnosis-Anon server, they can pierce the anonymity. There are extra steps a protocol could take; but they all involve more work, and many would require less transparency for users.

Does Gnosis-Anon offer encrypted messages to avoid interception of plaintext content?

Nope. If you want your messages encrypted, that's great. Do it!

What is the threat model Gnosis-Anon addresses?

The protocol is intended to be secure against a passive subpoena attacks. That is to say, that if someone can only obtain access to secret key information (and/or raw traffic) at time T, forwarded traffic prior to T has a degree of anonymity protection. Such an attack may reveal its existence, in which case future forwarding could be categorically refused as a partial defense.
The degree of anonymity protection at time T depends on users' utilized key duration. For users whose encrypting key has already expired, the attacker is unable to determine any additional identity information based on the revelation of secret keys. Obviously, that does not mean the attacker cannot establish an identity by means outside Gnosis-Anon itself (e.g. subpoena the logs of sender and receiver, whom they identify as part of a larger operation). For encryption keys that remain current, the attacker can determine that an anonym is mapped to an identity; but this does not establish that the anonym was ever actually utilized, or even looked up, before.
While it is reasonable to assume that the NSA or FBI already logs all my traffic, there are a range of attackers who do not have this degree of access. For example, a large company, normal "hacker", or even ordinary police department, will not be able to mount an "active subpoena attack" (one that involves a priori logging of traffic). For the latter class of atacks, the attacker generally only become interested in piercing anonymity (or even aware of the server) at and after time T.
An eavesdropper can gain different degrees of information based on what she observes and where she observers it. Consider the path:
Alice (M,<anon>)--> MTA1 --> Gnosis-Anon (M,<bob>)--> MTA2 --> Bob
  
MTA1 knows that Alice sent a message to some anonym, but not the corresponding identity. MTA2 knows that Bob received a message from Gnosis-Anon, but not that it was a forward from the headers alone. If MTA2 scans the payload for the forwarding blurb, it can make a good guess that it was a forwarded anonym; but the anonym itself is not contained in the message. An eavesdropper on MTA2 can do a lookup on Bob only if the encrypting key has not expired when the lookup is attempted. The only eavesdropper who directly correlates an anonym with an identity is one who can observe the incoming and outgoing traffic for Gnosis-Anon itself (or of an upstream provider who carries both; e.g. an ISP).

Can you guarantee that messages will be forwarded correctly, and that keys will be deleted on the mandated schedule?

Nope! If you use Gnosis-Anon now, it is quite likely your messages will be randomly deleted when I make changes to the code. There's a slight chance I could forward something to the wrong recipient. I will almost certainly regenerate keys on a erratic and random-seeming schedule for the forceable future. If I change encoding or encryption algorithms, that will break any existing anonyms.
Then again, you can download the code, and run it without changes midstream, if you like. Or you can implement the same general ideas in even better code. I encourage either.

Things to Do

(maybe)

Fix the case issue with anonyms!

Relayed forwards do not work with the current ALLCAP addresses and case-sensitive anonyms. That is bad. The question is whether it is better to stop canonicalizing addresses or to use allcap anonyms. I lean towards the latter, since it probably allows for less expansion of anonyms (and case-sensitive MTAs are rare).

Use a better encryption algorithm.

There is something to this. The current algorithm is not particularly strong; then again, the strongest attack almost certainly involves obtaining the key material (by warrant or by hacking), rather than breaking the cipher. The current algorithm has two advantages: (1) It can be done (easily) in pure Python; (2) It does not pad anonym to a block size.

Create a POP3, IMAP, and/or SMTPd version of the forwarder.

There is not conceptual requirement for shell access, or for the particular Unix-style mailbox format anon-forward currently assumes. At the other end of things, building the protocol into an SMTP server also make sense

Allow encryption of messages and/or destinations by senders

From a technical perspective, it would not be hard to have Gnosis-Anon publish a PGP public key. Mail received that contained encrypted information could be automatically decrypted by Gnosis-Anon. It is not clear whether it would make more sense to allow encryption of just message bodies or of complete messages (including destinations). Or if either makes any sense. In the latter case, messages might be sent to a generic address like <anon@gnosis.cx>, and the anonym would need to be contained within the encrypted block (in a special format maybe, or just as the first line).
Traffic leaving Gnosis-Anon would nonetheless be unencrypted--or at least no longer encrypted with Gnos-Anon's public key--since we have no knowledge of whether recipients have their own (public) keys, or if recipients know how to use encryption tools. This could add some extra security for a sender who worried that her own host was monitored by an attacker, but the attacker was not presumed able to eavesdrop on Gnosis-Anon also. Moreover, if the anonym was included in the encrypted block, it would be hidden from attackers (especially since no logs are kept). An attacker might only have access to header information, which would only show a message to <anon@gnosis.cx>, not to a specific anonym.
Despite some possible benefits, use of a Gnosis-Anon public key would overlap closely in purpose with the job that Cypherpunk and Mixmaster remailers already do better. It might be wise to deliberately eschew such capabilities, and direct users instead to pass their messages through Type I & II remailers prior to reaching a Gnosis-Anon anonym.