An idea for refining penet-style anonymous servers

-----BEGIN PGP SIGNED MESSAGE-----

Does the world need to have the anon.penet.fi model of anonymous email
and news posting refined, given the existence of Cypherpunks remailers
and Mixmaster digital mixes, not to mention nymservers?

I will listen respectfully to the arguments of the people who say "no",
and they're very likely right.  But penet *is* the most widely used
means of anonymous communication on the Internet - largely because of
its ease of use compared to genuinely secure remailers and mixes.

The other night, while sick and feverish with the flu, a scheme popped
into my head that would seem to make penet-style anonymous servers less
vulnerable to compromise through seizure of the remailer equipment or of
the address database.  In the cold light of day and normal temperature,
it still seems like a sound idea to me, and I wondered what other people
would think of it.

My scheme is the design of the address database.  It consists of two
hash tables, one for sending messages (which maps anonymous IDs onto
sender's addresses), and one for receiving them (mapping recipient's
addresses onto anonymous IDs).  A cryptographically secure hash (say,
MD5) is used for the index of both tables.

The index of the sending message table is the MD5 hash of the sender's
address.  The table entry the index points to is the sender's anonymous
ID, encrypted by a symmetric algorithm (maybe IDEA).  The encryption key
would be a different hash, by another algorithm (let's suppose it's
SHA), of that same address.

In forwarding a message, the server MD5-hashes the sender's address and
looks at the table.  If it doesn't find a corresponding entry, it
creates one.  If it *does* find an entry, it SHA-hashes the sender's
address and uses this key to decrypt the anonymous ID.  In the unlikely
event of collision the decrypted ID will be gibberish and the server
does something sensible (like appending padding to the address and
trying again).  The header information is filtered and the anonymous ID
inserted in the From: line. 

The receiving message hash table is designed similarly, in reverse.  The
index of the hash table is the MD5 hash of the anonymous ID; the entry
in the table is the recipient's email address, encrypted with the SHA
hash of the anonymous ID.  When a message comes in, the anon ID is
hashed and looked up in the table.  If  nothing is found, the message is
bounced. If an entry is found, the anon ID is SHA hashed and the table
entry decrypted.  If it is gibberish, a collision has taken place and
handled appropriately.  The message is then forwarded to its intended
recipient. 

What all this accomplishes is to obscure more information from attackers
and from honest operators.  In the event of abuse it is a simple matter
to find out who the abusers are and block them out.  If the operator is
subject to subpoena, anyone named in the subpoena can be easily
identified . . . *but nobody else can!*  Authorities cannot use a search
for one identity as an excuse for a fishing expedition in the address
database. 

(Obscuring information from honest operators can protect the operator
when questions of liability or even conspiracy come up.)

There is a way that attackers who have seized or copied the database can
search it - by trying it out on anonymous IDs, or user addresses, until
they hit paydirt.  And of course such an anonymous server can be no more
trustworthy than its operator; and the fundamental security limitations of
the penet-style anonymous server are well-understood.

So what do people think of this scheme of mine?  Are there drawbacks or
weaknesses that I'm not seeing?  Is it a good idea?  I'd really like it
if *something* good came out of being laid up with the flu. 

- -- 
Alan Bostick               | They say in online country there is no middle way
mailto:abostick@netcom.com | You'll either be a Usenet man or a thug for the CDA
news:alt.grelb             |    Simon Spero (after Tom Glazer)
http://www.alumni.caltech.edu/~abostick

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQB1AwUBMX+n0OVevBgtmhnpAQFkrwL+N+CklsLNsqHXNPnCOs1mogNydNnCtvGs
cUqK9rG3xpTYFsPMH6lhWq8wfPfKtQ88xs3RC/JE8ypcDZBugifNDf7hTuGeLZ8n
Q8RDvnAq0qNz9rxqHiMuyOQ3kf6YEVys
=g5SU
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "Alan" == Alan Bostick <abostick@netcom.com> writes:

[.....]

Alan> There is a way that attackers who have seized or copied the
Alan> database can search it - by trying it out on anonymous IDs, or
Alan> user addresses, until they hit paydirt.

I think that's exactly where the problem lies.  The advantage of your
proposal is, that for an honest SysOp your system makes it easier not
to look on the database, but I assume that Julf isn't interested in
the contents of the database anyways..

But for a real attacker it's just a small inconvinience, nothing more.


Alan> So what do people think of this scheme of mine?  Are there
Alan> drawbacks or weaknesses that I'm not seeing?

I think it's similar to a postmaster running a script to automatically
removing the actual message from a bounced mail, before she looks at
it.  But I don't think it's really making penet-style servers more
secure.


Have a nice day, and hope your flu cured now!

Olmur
- --
"If privacy is outlawed, only outlaws will have privacy" --- P. Zimmermann
      Please encipher your mail!  Contact me, if you need assistance.

finger -l mdeindl@eisbaer.bb.bawue.de for PGP-key
         Key-fingerprint: 51 EC A5 D2 13 93 8F 91  CB F7 6C C4 F8 B5 B6 7C



-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: latin1
Comment: Processed by Mailcrypt 3.3, an Emacs/PGP interface

iQCVAwUBMYEyKA9NARnYm1I1AQFZaQP/Q6jt+o1oDLysFTcxkitZF5aaQbwNa0Z6
Ud/oJqeTZvVtbltbJ7CIAIQCHydYLnBcxbeAw3EJDPpMYXaVz0Lsd00cdggD8Uh4
nY6dc4MaWvU0Kv1QUsdBlsIzpPwqvB9+WnXFQxcu/DONQT5pNkkzJWRGoHNj6+f4
kr31q2gniis=
=M/jY
-----END PGP SIGNATURE-----

In article <Uc5fx8m9LojB085yn@netcom.com>,
Alan Bostick <abostick@netcom.com> wrote:
>My scheme is the design of the address database.  It consists of two
>hash tables, one for sending messages (which maps anonymous IDs onto
>sender's addresses), and one for receiving them (mapping recipient's
>addresses onto anonymous IDs).  A cryptographically secure hash (say,
>MD5) is used for the index of both tables.
>
>The index of the sending message table is the MD5 hash of the sender's
>address.  The table entry the index points to is the sender's anonymous
>ID, encrypted by a symmetric algorithm (maybe IDEA).  The encryption key
>would be a different hash, by another algorithm (let's suppose it's
>SHA), of that same address.
>
>In forwarding a message, the server MD5-hashes the sender's address and
>looks at the table.  If it doesn't find a corresponding entry, it
>creates one.  If it *does* find an entry, it SHA-hashes the sender's
>address and uses this key to decrypt the anonymous ID.  In the unlikely
>event of collision the decrypted ID will be gibberish and the server
>does something sensible (like appending padding to the address and
>trying again).  The header information is filtered and the anonymous ID
>inserted in the From: line. 
>
>The receiving message hash table is designed similarly, in reverse.  The
>index of the hash table is the MD5 hash of the anonymous ID; the entry
>in the table is the recipient's email address, encrypted with the SHA
>hash of the anonymous ID.  When a message comes in, the anon ID is
>hashed and looked up in the table.  If  nothing is found, the message is
>bounced. If an entry is found, the anon ID is SHA hashed and the table
>entry decrypted.  If it is gibberish, a collision has taken place and
>handled appropriately.  The message is then forwarded to its intended
>recipient. 
>
>What all this accomplishes is to obscure more information from attackers
>and from honest operators.  In the event of abuse it is a simple matter
>to find out who the abusers are and block them out.  If the operator is
>subject to subpoena, anyone named in the subpoena can be easily
>identified . . . *but nobody else can!*  Authorities cannot use a search
>for one identity as an excuse for a fishing expedition in the address
>database. 
>
>(Obscuring information from honest operators can protect the operator
>when questions of liability or even conspiracy come up.)
>
>There is a way that attackers who have seized or copied the database can
>search it - by trying it out on anonymous IDs, or user addresses, until
>they hit paydirt.  And of course such an anonymous server can be no more
>trustworthy than its operator; and the fundamental security limitations of
>the penet-style anonymous server are well-understood.
>
>So what do people think of this scheme of mine?  Are there drawbacks or
>weaknesses that I'm not seeing?  Is it a good idea?  I'd really like it
>if *something* good came out of being laid up with the flu. 

This sounds a bit like the scheme mentioned in AC2, pp73-74.
Check it out (and its reference, if you have time...).

   - Ian

In article <Uc5fx8m9LojB085yn@netcom.com>,
Alan Bostick <abostick@netcom.com> wrote:
>                                          Authorities cannot use a search
> for one identity as an excuse for a fishing expedition in the address
> database.   [...]
> There is a way that attackers who have seized or copied the database can
> search it - by trying it out on anonymous IDs, or user addresses, until
> they hit paydirt.

So maybe this is an incremental improvement over the penet model,
but I'm not yet convinced that it's really a gigantic advance.

The threat model I'm most worried about is this: I post a Co$
document about clams & volcanos, under a nym.  The Co$ has enough
lawyers to subvert any justice system; they might be pissed off
enough to target me.  I don't want them to recover my name.

As you point out, your improvement can't protect against this scenario.

Maybe it can help protect others, so that when the Co$ scum steal
the database, they can't compromise everyone who's ever used penet.
But I'm not convinced-- what if the Co$ do a DejaNews search for
'anon*@penet.fi' and use each hit to query the database?  I think
they'll be able to break the anonymity of nearly everyone in the
database.


So I'll make another proposal, to try to be constructive.

Write a program to translate between penet-style remailers and
mixmaster/alpha style remailers.  Set up a service which automatically
creates a chain of nyms for you, with encryption at all the
mixmaster/alpha - to - mixmaster/alpha links.

People seem to (like / be familiar with / be willing to use) the
penet style interface-- so use the penet syntax as the interface
to the user, so the user doesn't have to know anything about what
the remailers are doing behind his back.  (Or use some *simple*
Java/html-forms/... interface.)

Advantages: to figure out the link between a nym and the real person,
you have to compromise a whole chain of remailers (except for the
following drawback).  the nym<->person database is distributed,
so is less susceptible to attack.

Drawbacks: this doesn't encrypt the link between the user and the
first remailer, so if Co$ can sniff on the link between you and
your first remailer, you're screwed.  This is still an improvement
over vanilla penet.fi-- the Co$ has better lawyers than wiretappers,
I suspect-- and you can also make sure your first link is just a
couple of hops away.  One might also contemplate using Hal's java
applet to automatically pgp encrypt the first link (so you only
have to assume that the web server you got the applet from is
trustworthy, and that the Co$ isn't doing active attacks on you).

This is still a compromise between security & usability, unfortunately.

Comments?

-----BEGIN PGP SIGNED MESSAGE-----

On Thu, 25 Apr 1996, Alan Bostick wrote:

> My scheme is the design of the address database.  It consists of two
> hash tables, one for sending messages (which maps anonymous IDs onto
> sender's addresses), and one for receiving them (mapping recipient's
> addresses onto anonymous IDs).  A cryptographically secure hash (say,
> MD5) is used for the index of both tables.

Funny.  I had the *exact* same idea a couple of months ago.  However, I
did find several flaws in it.

>
> The index of the sending message table is the MD5 hash of the sender's
> address.  The table entry the index points to is the sender's anonymous
> ID, encrypted by a symmetric algorithm (maybe IDEA).  The encryption key
> would be a different hash, by another algorithm (let's suppose it's
> SHA), of that same address.

Perhaps the address could be hashed several times for the table look-up and
then the address could be hashed a less number of times for decryption with
the IDEA key.  This reduces the amount of code needed and also eliminates
any problems with only using 128 bits of SHA output.

>
> In forwarding a message, the server MD5-hashes the sender's address and
> looks at the table.  If it doesn't find a corresponding entry, it
> creates one.  If it *does* find an entry, it SHA-hashes the sender's
> address and uses this key to decrypt the anonymous ID.  In the unlikely
> event of collision the decrypted ID will be gibberish and the server
> does something sensible (like appending padding to the address and
> trying again).  The header information is filtered and the anonymous ID
> inserted in the From: line.

In the scheme I thought of, a password would be sent with the message, which
would be hashed, appended to the hash of the address, and then hashed again
to get the decryption key.

> There is a way that attackers who have seized or copied the database can
> search it - by trying it out on anonymous IDs, or user addresses, until
> they hit paydirt.  And of course such an anonymous server can be no more
> trustworthy than its operator; and the fundamental security limitations of
> the penet-style anonymous server are well-understood.

Searching for the real address behind a pseudonym is not hard at all.  Just
hash the anonymous address, look it up in the table, then decrypt the
cooresponding encrypted address.  This was the major flaw that I spotted with
this scheme.

>
> So what do people think of this scheme of mine?  Are there drawbacks or
> weaknesses that I'm not seeing?  Is it a good idea?  I'd really like it
> if *something* good came out of being laid up with the flu.

The only other problem I found is a pretty minor one: the address database
would be twice as large as it would be if it was stored in plaintext.  I
don't think that much security is gained by using this scheme.

- -- Mark

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
markm@voicenet.com              | finger -l for PGP key 0xf9b22ba5
http://www.voicenet.com/~markm/ | bd24d08e3cbb53472054fa56002258d5
"The concept of normalcy is just a conspiracy of the majority" -me

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMX/727Zc+sv5siulAQGbwgP/XfQ2qw4HrzRX/DtFq542EnwnDuE+ACYk
OG3/dlCzqn4mmXNBB1QAh3K7tzNS0Gah46fODI/5lTHRqwyFehFIC96X3L45mEPO
QJWcvu2mqf6KhR5QnanB6jNw+okp1NAvTRJA2QhIZtPBBS3Xm3NfhrtHF8BKdxdu
WqjXM4HMjxs=
=gpZ8
-----END PGP SIGNATURE-----