Interoperability, one-use remailer tickets

The remailers need a one-time reply mechanism.

This would enable many other things, including "persistent" anonymous
entities, without using broadcast techniques. The current remailers
encourage hit-and-run anonymity, like the recent burst of anonymous
nastiness, and discourage conversational anonymity and persistent
anonymous entities. Sending a one-way message is easy and fairly secure.

Creating a reply ticket is not very secure. The ticket can be replayed
through the net to trace the path taken, and since the text following
the ticket it sent in clear, it is easy to trace. The ticket can also
be decrypted by coercion or hacking of the remailer machines. In general,
there is enough persistent information available to trace any reply ticket.
This is a bad thing.

A one-shot reply ticket would be designed so that, after the ticket was used
or a set time had passed, the ticket was no longer valid and the information
needed to trace the path, partially stored in the remailers, was gone.

One way to do this: each remailer has a list of secret (symmetric) keys.
Each secret may have an expiration date. By some method (problem discussed
later) the user and the remailer establish a shared secret, adding it to the
list, while the remailer does not find out who the user is. The reply ticket
contains a series of nested hops, each encrypted with that remailer's secret
plus all the others after it.

When the ticket is used, the remailer decrypts one layer of the ticket to
obtain the next hop. It then encrypts the message with that secret key. Now
it forgets the secret key (poof!) and passes the message and remainder of
the ticket on to the next remailer.

The ticket is getting decrypted at each hop, and the message is getting
encrypted. Thus there is nothing recognizable between hops, and the trail is
burning up as the message propagates. At the terminal end, the recipient
applies all of the secret keys in the proper order to decrypt the message.
Of course, an additional end-to-end public-key encryption is also an option.

The catch: how do we establish a shared secret with the remailer, without
identifying ourselves to it? If the first remailer (the one the replyer
sends the ticket to) is corrupt, and it knows who established the secret
contained in the ticket, it knows the end-to-end path of the message.

Solution 1: each remailer has a public key. To establish shared secrets with
a series of remailers, you send a normally-chained and nested message, using
each remailer's public key. Each remailer decrypts a layer, stores the
secret contained for it, and passes the message on. The first few remailers
may not get secrets; they are just there to anonymize the message.

  Problem: secret-establishing message is replayed, setting trail back up,
  then reply ticket is replayed. Solution: when a secret is used, it is
  one-way hashed, the hash stored, the secret forgotten. Secrets which have
  already been used will not be accepted the second time. When the used
  secrets list gets full, a new public/secret pair is generated and the old
  one is forgotten, preventing any more replays. 

    Problem: remailers are coerced or hacked to decrypt a captured secret-
    establishing message, before the secret key is expired. Trail of a reply
    ticket can then be followed. Solution: no good one that I can think of.

Solution 2: establish a shared secret by a simple, direct Diffie-Hellman
exchange with the remailer. You send a public-piece in a message, remailer
sends you a public-piece, both sides compute the secret. If the remailer is
corrupt, it now knows who you are. This is a level-1 secret.

Use the level-1 secret as a reply ticket to establish a secret with another
remailer. Message goes through a remailer, to the target you want to
establish a secret with. Target replies using the level-1 secret. This is a
level-2 secret; two remailers have to be corrupt to trace this secret to
you. If you want, use the level-2 secret for another exchange to create a
level-3 secret, and so on until your comfort zone is reached. An automatic
program sits around stockpiling secrets for you. Problem: high bandwidth.

Does anyone know of a better way to establish a shared secret in an
untraceable way? Both of these methods have their problems.

Given a secure two-way messaging mechanism, persistent anonymous identities
are established using a "pigeonhole service". This is a service, with a
publicized address, that will accept public-key encrypted mail and store it
in a "pigeonhole". The owner of the pigeonhole anonymously sends a request
(with authentication) and a reply ticket. The pigeonhole service sends the
owner his mail using the ticket.

Anonymous users would need a client that could set up trails, create
tickets, request mail from the pigeonhole, etc. One nice feature of the
system is that non-anonymous users could talk to anonymous users without
having a client. The anonymous message would be of the form:

--- BEGIN REPLY TICKET (LEAVE AT HEAD OF REPLY) ---
(Reply ticket ciphertext)
--- END REPLY TICKET ---
Message text

The non-anonymous user could reply with any mail reader, send the message
back to the remailer that sent it to him, and the message would be
transported securely back to the anonymous user that sent it.

For something complex like this, we need a language with a little more
leverage than C provides. For this and other complex protocols, I've ported
RSAREF 2.0 to Perl. The interface does not require you to recompile Perl.
It uses a C daemon and pipes. It provides symmetric encryption, public-key
encryption, digital signatures, hashing, DH exchange, and ASCII armor.
The algorithms used are MD5, MD2, DES, DESX, triple-DES, RSA, and DH.
It has a good (eval/die) exception handling mechanism, and a very thorough
regression testing script.

For reliability in a large remailer network, end-to-end reliability is
better than point-to-point reliability. Messages should be m-of-n secret
shared before transmission, and reassembled at the terminal end. For
clientless reception, the terminal node remailer could do the reassembly
and splitting of replies.

Code for secret sharing is available, but most secret-sharing algorithms
create shadows each the size of the message. This can be avoided: use an
error correcting code to add enough information to the original so the
message can be recreated with any m of n pieces. Break into pieces, encrypt
each piece, and secret-share the key. Where can I get an error correction
algorithm that can do this? You should be able to increase a file's size by
50% and then have any two of three pieces recreate it, for example.

I want to add other algorithms to the Perl encryption package. The secret
sharing, for one. A one-function call to gzip for compression. A blind
signature if I could get patent permission (not from Chaum; how's Brands?)
or perhaps just do it with a "research purposes only" disclaimer. Someone
with Visual Basic experience could do a DOS/Windows VBX module to enable
easy writing of PC clients for neat net-based servers written with the Perl
encryption package.

As Tim, Eric and others have pointed out, the problem of widespread, usable
crypto is essentially the whole problem of interoperability across a
network. Covering Unix for servers and Windows for clients would be a
large step in the right direction. 

						Mike

Mike Ingle <MIKEINGLE@delphi.com> writes some very nice ideas about
remailers:

>The remailers need a one-time reply mechanism.

>This would enable many other things, including "persistent" anonymous
>entities, without using broadcast techniques. The current remailers
>encourage hit-and-run anonymity, like the recent burst of anonymous
>nastiness, and discourage conversational anonymity and persistent
>anonymous entities. Sending a one-way message is easy and fairly secure.

Bill Stewart pointed out some of the problems with one-shot reply
addresses, although he seemed to be analyzing them as features which the
remailers provided against the users's will.  I think Mike's idea was
that this is something which remailer users would like.  Still, Bill's
comments seem valid.  How useful is a single-use reply address?  If you
posted a message to a mailing list or newsgroup only the first person
would get through to you.  You could post a message with a list of
reply addresses but that would open up some traffic analysis problems.

Two people having a conversation fits this model somewhat well, with
each person sending a new reply address that can reach them with each
message.  But even in this case how often is there a strict alternation
of messages?  Perhaps a "one ahead" approach would work, where each
person at all times has either one or two addresses which will get
through to the other side as long as they are in "alternation mode".
Then when one person needs to get a message to the other out of turn,
he uses up his spare address.  Then he gets sent two new addresses in
the reply message since now he has none, and they are back in the
initial state.

>One way to do this: each remailer has a list of secret (symmetric) keys.
>Each secret may have an expiration date. By some method (problem discussed
>later) the user and the remailer establish a shared secret, adding it to the
>list, while the remailer does not find out who the user is. The reply ticket
>contains a series of nested hops, each encrypted with that remailer's secret
>plus all the others after it.

>When the ticket is used, the remailer decrypts one layer of the ticket to
>obtain the next hop. It then encrypts the message with that secret key. Now
>it forgets the secret key (poof!) and passes the message and remainder of
>the ticket on to the next remailer.

>The ticket is getting decrypted at each hop, and the message is getting
>encrypted. Thus there is nothing recognizable between hops, and the trail is
>burning up as the message propagates. At the terminal end, the recipient
>applies all of the secret keys in the proper order to decrypt the message.
>Of course, an additional end-to-end public-key encryption is also an option.

As you have seen, this model is very similar to Chaum's 1981 paper except
for where the secret keys come from.  This is not to disparage your ideas
but it's just that as long as we have giants around, we might as well
stand on their shoulders.  Chaum's system was considerably simpler as it
used ordinary PK decryption of the address at each stage, with the header
including a secret key that would encrypt the body to maintain
unlinkability.  As you point out this has a certain kind of vulnerability
to coercion that your scheme is less sensitive to.

>The catch: how do we establish a shared secret with the remailer, without
>identifying ourselves to it? If the first remailer (the one the replyer
>sends the ticket to) is corrupt, and it knows who established the secret
>contained in the ticket, it knows the end-to-end path of the message.

>Solution 1: each remailer has a public key. To establish shared secrets with
>a series of remailers, you send a normally-chained and nested message, using
>each remailer's public key. Each remailer decrypts a layer, stores the
>secret contained for it, and passes the message on. The first few remailers
>may not get secrets; they are just there to anonymize the message.

>  Problem: secret-establishing message is replayed, setting trail back up,
>  then reply ticket is replayed. Solution: when a secret is used, it is
>  one-way hashed, the hash stored, the secret forgotten. Secrets which have
>  already been used will not be accepted the second time. When the used
>  secrets list gets full, a new public/secret pair is generated and the old
>  one is forgotten, preventing any more replays. 

Chaum too used a list of message hashes, although his use was to
prevent the reply-replay attack.  I will note that this attack is going
to be pretty difficult to mount on your scheme as it would require
either saving all messages from a suspected target of an anonymous
address, or saving all messages into the remailer network in toto, then
perhaps playing (all of?) them back.  So it is not going to be easy to
set up this chain again.  In addition to your idea of hashes you could
use some time limits to restrict this kind of reply attack.

>    Problem: remailers are coerced or hacked to decrypt a captured secret-
>    establishing message, before the secret key is expired. Trail of a reply
>    ticket can then be followed. Solution: no good one that I can think of.

Yes, this is the kind of coercion that as you point out the Chaum
scheme is vulnerable to.  There we rely on the remailers to not send
two messages to the same one-shot address in order to prevent replay
attacks.  But as long as the remailer key is valid there is the chance
that the remailer could be coerced and forced to decrypt your anonymous
address, allowing it to be traced back to you.

I do think that your scheme is less sensitive to this kind of coercion
because of the difficulty of knowing which message to ask the remailer to
decrypt.  Ironically, your scheme is even stronger than "forward"
messages throught the remailer network.  Those are equally vulnerable to
this kind of coercion.  If a suspect sends a message through the remailer
network, it can be replayed in just the way that we are worried about for
Chaum replies, and the remailers coerced into decrypting it at each step.

We tend not to worry so much about this forward vulnerability as we do
about the reverse one.  Partially this is because our current remailers
don't implement Chaum's scheme, but partially too we sense that an
interesting public pseudonym is a more inviting target than the hopefully
anonymous true name behind it.  I'm not really sure how good an
assumption this is, though.  So I am less inclined to view Chaum's scheme
as broken since the remailer network inherently suffers the same
vulnerabilities.  We hope to develop enough independent remailers that
the coercion issue will not be a major problem.  Tim May has advocated
hardware, tamper-proof circuits to hold the keys so that coercion is
impossible.

Plus, I think an important part of the picture which is not currently
being implemented is remailer key changes.  This can provide forward
secrecy similar to your scheme.  Once last week's key is gone, there is
no longer any danger of your message ever being traced (as long as you
trust the remailer to truly erase it, just as in your scheme).  This
would be useful both for ordinary remailing and for Chaum-style reply
blocks, which as I say are both vulnerable to the reply-with-coercion
attack.

There is one attack on all these schemes which you didn't mention, which is
that the bad guys are the first one to try the return address and coerce
each remailer along the way.  This might be especially dangerous in the
case of your "pigeonhole" described below, where the pigeonhole account
makes for a tempting target for the snoopers, giving them a chance to
intercept the reply message back to you and be the first ones to be using
it.

>Solution 2: establish a shared secret by a simple, direct Diffie-Hellman
>exchange with the remailer. You send a public-piece in a message, remailer
>sends you a public-piece, both sides compute the secret. If the remailer is
>corrupt, it now knows who you are. This is a level-1 secret.

>Use the level-1 secret as a reply ticket to establish a secret with another
>remailer. Message goes through a remailer, to the target you want to
>establish a secret with. Target replies using the level-1 secret. This is a
>level-2 secret; two remailers have to be corrupt to trace this secret to
>you. If you want, use the level-2 secret for another exchange to create a
>level-3 secret, and so on until your comfort zone is reached. An automatic
>program sits around stockpiling secrets for you. Problem: high bandwidth.

>Does anyone know of a better way to establish a shared secret in an
>untraceable way? Both of these methods have their problems.

That is a very nice idea for using DH.  Here is a variant which might use
less bandwidth.  Have each remailer create a lot of DH key halves, values
of hi = g^xi so xi is the secret discrete log of the public DH key half
hi.  All these hi get published.  Now you need to reserve one for
yourself to use in your return ticket, which you do perhaps with an
ordinary remailed message to that remailer as in your first solution.

You create a random y and use hi^y for your secret key for that remailer.
The reply block contains i and g^y which lets the remailer calculate the
same secret.  Then it deletes xi when it gets used so you get the forward
secrecy you desire.  This is not subject to the reply attack you were
worried about because all you told the remailer was i, and xi is gone for
good so they can't re-create the secret.

(Equivalently, have the remailers create lots of public keys and
publicize them, and reserve one in the same way.  Then have the remailer
erase the secret key when it gets used.  This is just another way of
describing the above.)

>Given a secure two-way messaging mechanism, persistent anonymous identities
>are established using a "pigeonhole service". This is a service, with a
>publicized address, that will accept public-key encrypted mail and store it
>in a "pigeonhole". The owner of the pigeonhole anonymously sends a request
>(with authentication) and a reply ticket. The pigeonhole service sends the
>owner his mail using the ticket.

This is a good idea, although there is a tradeoff between frequent polls
of the pigeonhole, which might allow some traffic analysis particularly
if there is a suspected link between persona and true name, and less
frequent checks, which may cause high priority messages to be delayed.

>Anonymous users would need a client that could set up trails, create
>tickets, request mail from the pigeonhole, etc. One nice feature of the
>system is that non-anonymous users could talk to anonymous users without
>having a client. The anonymous message would be of the form:

>--- BEGIN REPLY TICKET (LEAVE AT HEAD OF REPLY) ---
>(Reply ticket ciphertext)
>--- END REPLY TICKET ---
>Message text

>The non-anonymous user could reply with any mail reader, send the message
>back to the remailer that sent it to him, and the message would be
>transported securely back to the anonymous user that sent it.

Yes, well, we do this already with our current remailers.  Many
people have written clients to create these reply blocks, along with
little instructions to the baffled recipient to cut and past the reply
block at the front of the reply message.  Once in a while these even
work, I think.

With your pigeonhole idea you don't need this, you can just have a
Reply-To that points at the pigeonhole, which is one of its biggest
advantages.

>For reliability in a large remailer network, end-to-end reliability is
>better than point-to-point reliability. Messages should be m-of-n secret
>shared before transmission, and reassembled at the terminal end. For
>clientless reception, the terminal node remailer could do the reassembly
>and splitting of replies.

I agree with this.  This also relates to issue of message size
quantization with cryptographically strong padding.  I don't suppose the
RSAREF library could do that...

>Code for secret sharing is available, but most secret-sharing algorithms
>create shadows each the size of the message. This can be avoided: use an
>error correcting code to add enough information to the original so the
>message can be recreated with any m of n pieces. Break into pieces, encrypt
>each piece, and secret-share the key.

Yes, this is a good idea.  I first read about this in the 1993 Crypto
conference proceedings, in a paper called "Secret Sharing Made Short" by
Hugo Krawczyk.  You might find the paper useful although it sounds very
similar to what you have in mind already.


Considering all the pros and cons, I am afraid that even the security of
the one-shot return address is probably insufficient, especially when the
simple "post replies to usenet encrypted with this key" is so easy and
safe.  Granted it will be a problem once everybody starts doing that, but
flooding is going to be hard to beat for safety.

Hal

Mike Ingle <MIKEINGLE@delphi.com> writes:
[Part about remailers deleted]
>For something complex like this, we need a language with a little more
>leverage than C provides. For this and other complex protocols, I've ported
>RSAREF 2.0 to Perl. The interface does not require you to recompile Perl.
>It uses a C daemon and pipes. It provides symmetric encryption, public-key
>encryption, digital signatures, hashing, DH exchange, and ASCII armor.
>The algorithms used are MD5, MD2, DES, DESX, triple-DES, RSA, and DH.
>It has a good (eval/die) exception handling mechanism, and a very thorough
>regression testing script.
>[...]
>I want to add other algorithms to the Perl encryption package. The secret
>sharing, for one. A one-function call to gzip for compression. A blind
>signature if I could get patent permission (not from Chaum; how's Brands?)
>or perhaps just do it with a "research purposes only" disclaimer. Someone
>with Visual Basic experience could do a DOS/Windows VBX module to enable
>easy writing of PC clients for neat net-based servers written with the Perl
>encryption package.

This is very exciting!  Could you show some examples of how your code
would be used with Perl?  Some kind of script that could work with MP
numbers or RSA decrypt a file?  It would be very good to have a
prototyping language like Perl with crypto addons.

>Code for secret sharing is available, but most secret-sharing algorithms
>create shadows each the size of the message. This can be avoided: use an
>error correcting code to add enough information to the original so the
>message can be recreated with any m of n pieces. Break into pieces, encrypt
>each piece, and secret-share the key. Where can I get an error correction
>algorithm that can do this? You should be able to increase a file's size by
>50% and then have any two of three pieces recreate it, for example.

Try looking for a package called Shade using Archie.  Here is an excerpt
from the doc file:

> `shade' is a file splitting and merging utility.  It takes a large
> file and splits it into uniformly sized blocks.  It can also output
> extra blocks (called shadows).  These shadows can be used to recover
> missing sections if they get corrupted or it they are lost.  With a
> single shadow, `shade' can recover ANY single missing block.  As many
> shadows are needed as there are blocks missing.  If too few blocks
> and shadows are available, nothing can be recovered.
> 
> For example, foo.bar (259042 bytes) is split into 5 sections
> of 45000 bytes, 1 section of 34042 bytes and 2 shadows of
> 45000 bytes.  Each of these 8 parts is sent through email.
> Even if any two of these eight parts gets lost, the original
> foo.bar can be reconstructed.
> 
> `shade' is a simple application of the chinese remainder theorem
> for polynomials with coeficients modulo two.  For more information
> see the comments at the beginning of project.c.

As for the remailer return address idea, I would suggest looking at
Chaum's 1981 paper from CACM which has a similar concept.  I believe it
was posted here recently.  Instead of using shared secrets he had the
secret key at each hop get embedded in the return address itself.

Hal