On Sun, 23 Nov 2003 [EMAIL PROTECTED] wrote: > > > > His analysis applies to any large-scale p2p network. There are at least > > > > two defenses: either create some sort of certification authority (perhaps > > > > a supervisory p2p network) or allow/encourage fragmentation of the target > > > > network. > > > > > > Come now, This is not impossible. GNUnet does it. And does it well. I posted a > > > way to adapt this to Freenet's architecture a while back. It can be done. It > > > just requires a big code over hall. > > > > You might be disagreeing with the conclusions of the paper on Sybil. If > > so, have you read the paper? If so, which conclusion are you disagreeing > > with? > > I am disagreeing with the paper. Not in it's conclusions but in it's premises.
This is a bit hard to decipher. Its premises include a belief in arithmetic, that sort of thing. It might be helpful to quote from the paper: "Abstract - Large-scale peer-to-peer systems face security threats from faulty or hostile remote computing elements. To resist these threats, many such systems employ redundancy. However, if a single faulty entity can present multiple identities, it can control a substantial fraction of the system, thereby undermining this redundancy. One approach to preventing these 'Sybil attacks' is to have a trusted agency certify identities. This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities. "Introduction "We argue that it is practically impossible, in a distributed computing environment, for initially unknown remote computing elements to present convincingly distinct identities." I suppose you might say that everything from "Large-scale peer-to-peer" to "have a trusted agency certify identities" are the paper's premises and everything after "shows that" is its conclusions. If you agree with this, then your disagreeing with the premises is unfathomable. Certainly you and I both know that any computer can present more than one identity. For example, I am working at the moment on a machine behind a firewall. It has one IP address inside the local network, and quite a different IP address to the outside world. > > Or you might be saying that Freenet could create a CA. If so, can you be > > more specific? > > Not create a CA, but act as one. They state that a CA is necessary to > prevent cancer nodes from making multiple identity's What the author actually says is very carefully worded. He certainly makes no reference to cancer nodes. "The system must ensure that distinct identities refer to distinct entities, otherwise, when the local entity selects a subset of identities to redundantly perform a remote operation, it can be duped into selecting a single remote entity multiple times, thereby defeating the redundancy. We term the forging of multiple identities a Sybil attack ... on the system." > to insure privacy > and prevent a group of nodes from attacking the network. I'll think > you'll agree with me when I say that in terms of data storage Freenet > does an excellent job insuring security despite not trusting the node > with the data. If they think they could brute force a CHK I welcome > them to try. In terms of responsibility for storing data, nobody is > responsible in Freenet. They could pretend to be 100000 nodes and then > collect lots of data and delete it and nobody would care. The only way > they got the data was to cache it in the first place. With respect, this is nonsense. The usual reasons for using Freenet are anonymity in publication and anonymity in reading. If Freenet is flooded with dummy nodes, both types of anonymity will be thoroughly compromised. If the publishing node, for example, is surrounded by compromised nodes, then it will be known to be the source of document X. If a reader is surrounded by compromised nodes, the document being read will pass through one of them and so the node will be known to be a reader of document X. Furthermore, all inserts from a given node can be discarded and/or all requests treated the same way. That is, by flooding the network with compromised nodes, you can deny all service to any particular node or just compromise anonymity is both publishing and reading. In other words, while you may be happy with this situation, any user expecting Freenet to function as specified would be distinctly unhappy. > > Or you might be saying that Freenet could allow or encourage network > > fragmentation. Are you? > > No I am not. > > There are still two other arias where cancer nodes can be a problem. > First is flooding. This is what the GNUnet model solves. Here's the > short version: If you give each node credit proportional to the amount > of time they saved you by processing a request through them as opposed > to someone else, and then allow them to use that credit towards your > spending time processing their requests, then you don't need any > outside authority. Both nodes know they are not being cheated. If they > are then they don't process the requests. Node A is surrounded by compromised nodes X, Y, Z. Whenever A tries to insert data, X, Y, or Z as appropriate certifies that the data has been inserted. They may or may not be lying. Whenever A tries to retrieve data, the relevant compromised node either returns the data reliably (running traffic analysis at all times) or discards the request but simulates good reason for doing so. X, Y, and Z can build huge credit, but they are in no sense trustworthy. The credit mechanism works, sort of, but doesn't address the problem of trust at all. Mild variation: A inserts a document, and then retrieves it to confirm that it is there. Any of X, Y, or Z will return the document. They may claim that is stored in node Q (also compromised). It may even be actually there, but anyone else requesting it will be told that it isn't. If the adversary is large, it will have correspondingly large resources, say a server farm with the fastest commercially available CPUs, GBs of memory, lots of fast disk drives, huge pipes into the Internet, many blocks of IP addresses. It can impersonate an arbitrarily large number of nodes. > Simple as that. Now how does > one build up credit in the first place? Simple. If CPU, network > bandwidth or hardDrive space are not being used at any particular > time, they go to waste. So even if a node has 0 credit you'll still > process their request if you have idle resources. Thus you gain credit > with them. This way no node can do more damage than The Amount of > Benefit they have previously provided to the network + the slack > resources in the network + the CPU required to check and then drop N > requests. That's as good as it gets anywhere. In its idle moments, the server farm described above can casually flood the remnants of Freenet with fake requests and junk inserts. These can be easily made indistinguishable from real requests and real inserts. Just imitate the typical user browsing the Web, flicking from one site to another. The fetches will flood Freenet with trash. If node A lies between compromised nodes X and Y, X can request material known to be on Y from A, and then Y can return the favor. The effect is to load A with meaningless data and use up all of its bandwidth. Between them, the compromised nodes around A can cause it to specialize in junk. In the 1950s, the Communist Party of the USA (CPUSA) was infiltrated by the FBI in just this fashion. The infiltrators were extremely reliable, much more so than real party members. They volunteered for odd jobs, including dull clerical positions in local cells, where they managed the membership list ;-) After some time anyone who paid their dues regularly was suspected of being an agent. But by then the damage had been done: the FBI owned CPUSA. > The only problem this does not solve is if a node does a good job of > processing requests over all, but always drops a single key. Freenet > cannot truly solve this problem, because there is no way to know that > they really should have had the data. BUT a central authority cannot > solve this problem ether! By 'central authority' I assume that you mean certificate authority. The CA does not address this problem at all. What it does do (among other things) is make it difficult and/or expensive to forge identities, and it should force the forged identities to be scattered around the network, so that if f% of the network is compromised, then on average f% of the neighbors of any particular node are compromised. _This_ is in fact the best that you can do: limit to a degree the number of compromised nodes and randomize their distribution. In this situation, "always drops a single key" is just a fault. This happens in real networks: at any given time, some proportion of the machines on a network are faulty in one way or another. I submit that accident is more common than malice. But whatever the source of the errors, you have to be able to deal with them. The usual means is redundancy of one sort or another. > The only way to do so would be for it to > know where all the data on the network was stored. AND have all the > requests routed and returned through it. The Internet operates in the presence of a large number of errors without the central authority you refer to. What it has is what amounts to a certificate authority, the IANA, which doles out identities, autonomous system (AS) numbers. The operators of the Internet set up voluntary peering arrangements under which ASs exchange routing information using BGP4, the "border gateway protocol". The operators continuously monitor inter-network traffic looking for errors. Some of the mechanisms are automatic: for example, some ASs "route flap", meaning that some of the routing information they advertise changes very frequently. Routers detect these route flaps and dampen them, ignoring them entirely when they occur too frequently. If people misconfigure their equipment too often, other networks drop peering with them. Smaller errors are ignored; if you subscribe to lists like NANOG, you will periodically see reports of known misconfigurations. People just tolerate the noise - up to a certain point. In other words, we have in the Internet a huge real-world example of a network that relies upon a CA (the IANA) to provide verifiable identities (AS numbers) which are used to build a reliable service despite continuous faults, some malicious, but most just operator errors and equipment failures. There is no central authority that has to see all data to keep the Internet running; in fact it is inconceivable, to me at least, that anyone could build a central authority to manage the Internet in real time. It takes a highly distributed peer-to-peer network to do the job, the p2p network formed by backbone routers talking BGP4 to one another. To me, the paper on the Sybil attack is convincing. The author argues from first principles that you cannot prevent identity forgery in a simple peer-to-peer system. A p2p system without a mechanism for detecting identity forgery is wide open to attacks. On the other hand, the Internet is a convincing practical demonstration that a reliable global network can be built IF the participating entities have reliable identities issued by a trusted CA. > Otherwise a node could claim > it did not receive the data when it did. I don't think I need to > explain why this is not a viable solution. -- Jim Dixon [EMAIL PROTECTED] tel +44 117 982 0786 mobile +44 797 373 7881 _______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
