Re: [freehaven-dev] sketching accountability requirements/solutionsin FH

[dmolnar@belegost.mit.edu]

On Sun, 19 Nov 2000, Roger Dingledine wrote:

> 
> But even if we solve that, we have the same problem at the higher level:
> the requestor doing the FH document query needs to pay not only to get
> his request to the first server, but he also has to pay that server to
> contact all the other servers. Is there a way to tunnel payment like
> that? (Or rather, what's the best way.)

In the case of "paying mix-net nodes in a reply block without revealing
identity of the nodes," there seems to be a partial solution based on an
idea of "blinded public-key encryption" which I've been discussing with
David Hopwood. He actually has some very nice work on this, but I'll let
him decide whether to post a pointer to it, since this is the public
mailing list (don't want to publish it accidentally!). This note will by
and large *not* follow the notation of that work.

A "blinded public-key cryptosystem" is a public-key cryptosystem in which
given a public key E_A for Alice, there is an efficient algorithm blind() 
to create a "blinded" public key E'_A = blind(E_A), such that

	* E'_A = blind(E_A) can be computed without knowledge of A's 
	private key. 

	* E'_A is a valid public key -- i.e. D_A(E'_A(M)) = M 

	* It is impractical for any (probabilistic polytime) adversary
	to determine given only E'_A and E_A that the two public keys are
	equivalent. i.e. given E'_delta, E_0, and E_1, the adversary has
	negligible chance of correctly identifying delta. 

Anna Lysyanskaya and independently David Wagner pointed out that Elgamal
seems to have a key blinding property. We can actually build such things.

Now for the partial solution to the "how do we tunnel payments?" problem.
I'll give it in terms of remailer reply blocks, because I haven't 
carefully considered the Freehaven case. 

Given a blinded-key public key cryptosystem, we can construct a remailer
reply block as follows:

1. Pick a remailer chain  C_1, C_2, ... C_n  where C_i is a remailer's 
   public key. 

2. Create the blinded public keys C'_1, C'_2, ... C'_n .

3. Create the remailer reply block as "usual" (by the way, we want this
   to be a "recipient-hiding" cryptosystem as well, but that's not so hard
   with Elgamal -- fix a common p). Call this block B. 

4. Output (B, C'_1, C'_2, .... C'_n) as the reply block. 

If the public-key cryptosystem is secure, only the first hop can be
determined from inspecting B. If the public-key cryptosystem has the
blinded key property, then by themselves the C'_i give no useful
information about the identities of the remailer hops. 

To send a message with equal payments for each hop, do the following:

1. Look at B, obtain the public key and e-mail address of first remailer
   C_1. Create E_(C_1)(B concat M)

2. Create n payment values P_1...P_n. Encrypt each P_i with one and only
   one C'_i.  NOTE that at this point you do _not_ know which C'_i 
   corresponds to the first hop, the second hop, etc. You don't even
   know if they all correspond to distinct machines.  
   But you do know that you have n distinct strings representing valid 
   public keys, and you can map one string to one payment value. 

3. Send ( E_(C_1)(B concat M), concat for all i C'_i(P_i) ) to C_1. 

This works because:

1. At the first hop C_1, the message E_(C_1)(B concat M) is decrypted.
   Inspecting B tells C_1 the name and e-mail address of C_2. 

2. There are n different encrypted payment packets appended to 
   E_(C_1)(B concat M). Actually, it's probably best that they
   be placed inside E_(C1)()...but C_1 has access to them anyway. 


   One of them is encrypted with E_(C_1). 
   C_1 just tries to decrypt them all until it finds which one. 
   Then it checks to see whether adequate payment was enclosed. 
   If none of the payment packets decrypt or if the payment is
   not sufficient, C_1 "fails" the packet. That could be dropping
   the packet, trying to notify the author, whatever. 


This seems to produce a way by which we can incorporate payments for each
hop of a reply block *without* revealing the identity of a hop and
*without* trusting the first server to be basically good. 

A couple of problems, though:

	* What if you want to pay some of the hops more than others?	
	Currently only the first hop can be paid more. With the others,
	you can guess which key goes with which hop and then modify
	payments accordingly. 
	(Does this lead to an attack in which an adversary pays 0 
	for a packet at one C_i and 100 for the others, then tries
	to follow the message and see where it drops?)

	* The blinded key property cannot conceal the fact that Hop i
	can decrypt messages encrypted with C'_i. So the adversary can
	take a particular C'_i from a reply block, guess a mix node,
	and then try its damndest to get the mix node to respond to
	messages encrypted with C'_i. Dealing with this will take
	care in the protocol -- and if we screw up, we just identified
	a mix node in the middle of the reply block! 
	Is this more trouble than it's worth? 

	* In the reply block case, we know the number of hops n in
	advance. It's fixed at reply block construction. What about
	situations, as Roger pointed out, where n is not fixed in
	advance? e.g. searching Free Haven?

	You could try to hack around this by posting a directory of
	blinded public keys of Free Haven nodes. Then everyone
	encrypts payment with every key and appends to the message.
	This yields a trivial DoS attack if the directory can be
	updated by just anyone, though -- add so many public keys
	that encrypting with them is impractical. 


Despite these problems, this seems like a nice idea because it allows you
to target a particular MIX node directly. No trusting spurious first
parties necessary. 

-David