- Yes, there is the problem that the randomly chosen reference value may not be close enough to the keys the different Bob's usually get requests for to attract any requests from them, though the level of this risk isn't entirely clear (it depends on how well sorted a Freenet is in reality). I did simulate this protocol, and though I did not do a good analysis of the results it looked like the new nodes where indeed getting requests to them. Their is a scalability issue there of course, as the simulation was doing 25 hop announcements on only 600 nodes.
I would be hard pressed to think of an announcement protocol that was not random however, since any key routed announcement (including the backwards references used currently) do open up avenues for malicious parties to easily plant references to themselves at chosen key values. - I don't see why all the Bob's can collude to control the value, since Alice also has a value XORed into the result. Of course, they can decide as they wish what key value they actually reference Alice from, so it doesn't matter. I think better stated the goal is that for any honest party in the process, the value they will know as the final result is random. - I had a long defense written, but I had to remove it upon realizing that it didn't make much sense. I was well aware that the protocol only needed one set of commits for the the resulting value to be random, the reason I added the second, and the encrypt for Alice, was what you called R2 - to make sure that if a node wanted to fuck with BobN's address on the way to Alice, he would also screw up BobN's selected random value. I must admit that simply having Alice sign both values together seems a lot more logical atm. One small advantage is that all the Bob's addresses are not revealed to everyone in chain. Though, I guess a malicious node looking to fish for addresses could just do his own Announcements to find them (a thought - maybe the addresses of the Bob's should never be sent back, and all the references simply requested from Bob1 (to start with, once a reply comes back one can use the datasource for that)). - I believe that Scott is already doing encryption in the node connection process, and that he would use ElGamal using the same primitives as we have for DSA. On Mon, Feb 26, 2001 at 03:24:48PM -0800, hal at finney.org wrote: > I've looked some more at Oskar's announcement protocol, > http://cvs.sourceforge.net/cgi-bin/cvsweb.cgi/~checkout~/docs/announcement.txt?rev=1.1&content-type=text/plain&cvsroot=freenet > > As far as I can see, the protocol is cryptographically sound. I have > two concerns, which don't deal with any cryptographic problems. > > The first is whether this protocol will "work" in the context > of Freenet routing. The problem is that a new node gets an initial > keyspace assignment, but this is announced to a _random_ set of nodes. > This is unlike the usual Freenet situation where nodes tend to be known > to other nodes which are similar in keyspace. > > The difference is that in the present protocol, the nodes to which Alice > is announced (by doing an insert) are close to hers in keyspace, and > in the proposed protocol they are randomly chosen. Notifying a random > set of nodes about a new one doesn't exploit Freenet's data locality. > Without this it seems that you will need grossly large HTL on the > announcement for people to find Alice's node. > > The second issue relates to a possible simplification of the announcement > protocol. It is difficult to analyze whether this works because the > conditions for "success" of the protocol are somewhat vague. As I > see it, we have several conditions C which must be met, and then we > have certain results R: > > If > C1: There are at least some honest Bobm nodes who complete the protocol > C2: There is really a node Alice which is announcing herself > C3: The Bobm nodes end up with Alice's true address and public key > then > R1: Alice's assigned keyspace value x is random and uninfluenced > R2: Alice knows Bobm's true address and public key > > As Oskar describes, there are a lot of ways for nodes to cheat, which > violate some of these conditions. All the Bobm's can collude to give > Alice a specific key space, but all they succeed in doing is notifying > themselves. What good is that? It's hard to say, which is related to > the point above about the value of even a successful completion when it > is a bunch of random nodes that got the info. > > One aspect of the protocol that looks complex to me is that it uses both > encryption and signatures. I don't think we necessarily were planning > on having long-term encryption keys in Freenet, but rather having only > long-term signature keys and doing signed DH exchanges for encryption. > Granted with RSA keys you can use the same key for encryption as for > signature, but this is generally frowned upon and is impossible with > some other key types. So you might have to introduce a second public > key per node to allow the protocol to work. > > I decided to see if I could eliminate the encryption, and here is what > I came up with. > > The initial AnnouncementRequest is the same; it chains the commitments > forward. > > However the AnnouncementReply does not do any encryption or signatures > or hashing. It simply reveals the xi values backwards, along with the > Bob's addresses (including public keys). > > Data > xN, Address(BobN) > xN-1, Address(BobN-1) > ... > > Obviously this opens up some cheating possibilities. To fix this, we make > the next message, AnnouncementExecute, be signed in its entirety by Alice: > > Data > Sign[Alice] (x, x1, x2, x3, ..., xN, > Address(Bob1), Address(Bob2), ... ) > > This is then sent up the chain and allows each BobM to see that no cheating > was done in the AnnouncementReply phase. > > The last phase, AnnouncementComplete, is then the same. > > By having Alice sign what she got back at the end of the second phase > and send it back up, we assure that any BobM who actually got Alice's > correct key (condition C3 above) can verify that his x value was used > in the calculation, and that Alice got his address right. > > When doing a commit-and-reveal protocol to choose an unbiased value, > it is not necessary for all parties to commit. What each party wants > is to get the effect that he reveals LAST. This can be done by having > everyone else commit before he reveals, or it can be done by having > everyone else reveal before he does. Or it can be a mixture of those, > as in this protocol. BobM reveals after seeing commitments for Bob1 - > BobM-1, and after seeing reveals for BobM+1 - BobN. He therefore gets > the effect of revealing last, which allows him to be sure that he is not > cheated. Then when Alice sends the signed x and x1 - xN values, he can > confirm that these values match what he saw, sent, and was committed to. > > I haven't given a lot of thought to the issue of making sure Alice knows > all the Bob's addresses. But in general if we assume again that the > Bobs have Alice's true key, then seeing her signature on their addresses > should assure them that she got the addresses okay. > > So this protocol accomplishes the requirements above, without using > encryption, which should simplify the implementation. It may be that > there are some stronger requirements which the original announcement > protocol met, which my variant does not. As I mentioned, the requirements > are not completely clear. But I think it is worthwhile to try to come > up with alternatives to encryption even at some cost in efficiency of > the announcement protocol. > > Hal > > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://www.uprizer.com/mailman/listinfo/devl -- 'DeCSS would be fine. Where is it?' 'Here,' Montag touched his head. 'Ah,' Granger smiled and nodded. Oskar Sandberg md98-osa at nada.kth.se _______________________________________________ Devl mailing list Devl at freenetproject.org http://www.uprizer.com/mailman/listinfo/devl
