[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: freehaven-dev@freehaven.net*Subject*: Re: [freehaven-dev] sketching accountability requirements/solutionsin FH*From*: dmolnar@belegost.mit.edu*Date*: Sun, 19 Nov 2000 01:34:37 -0500 (EST)*Delivery-Date*: Sun, 19 Nov 2000 01:34:43 -0500*In-Reply-To*: <20001119004551.Q1022@belegost.mit.edu>*Reply-To*: freehaven-dev@freehaven.net*Sender*: owner-freehaven-dev@freehaven.net

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

**Follow-Ups**:**Re: [freehaven-dev] sketching accountability requirements/solutionsin FH***From:*dmolnar@belegost.mit.edu

**References**:**[freehaven-dev] sketching accountability requirements/solutions in FH***From:*Roger Dingledine <arma@mit.edu>

- Prev by Date:
**[freehaven-dev] sketching accountability requirements/solutions in FH** - Next by Date:
**Re: [freehaven-dev] Opening example** - Prev by thread:
**[freehaven-dev] sketching accountability requirements/solutions in FH** - Next by thread:
**Re: [freehaven-dev] sketching accountability requirements/solutionsin FH** - Index(es):