On Sun, 23 Nov 2003 [EMAIL PROTECTED] wrote: > > > 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.
True. > To resist these threats, > many such systems employ redundancy. True. > However, if a single faulty entity > can present multiple identities, it can control a substantial fraction of > the system, thereby undermining this redundancy. Sometimes. > One approach to > preventing these 'Sybil attacks' is to have a trusted agency certify > identities. OK. > 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. Alright, how do they make that case ... > "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 argue that it is totally unnecessary, 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. I'm saying that what the paper proves means nothing to Freenet because it is addressing a problem that we do not face, or have the ability to avoid completely. > 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. Yup. > > > 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." Yes. And if we had that problem it would be relevant. The system must ensure that distinct identities refer to distinct entities, ONLY IF, when the local entity selects a subset of identities to redundantly perform a remote operation, WE CARE IF it can be duped into selecting a single remote entity multiple times, thereby defeating the redundancy. I don't care if they can be duped. This is because A: there is no motivation to do that, as there are MUCH MUCH better attacks on the network and B: There is not anything we can do about it in a distributed newtwork. This paper really amounts to proving point B. > > 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. No. Plausible denyability is preserved so long as they cannot PROVE that you were not connected to ANY other nodes. > If the publishing node, for example, is surrounded by compromised nodes, > then it will be known to be the source of document X. 1. There are ways to prevent this. 2. It only works if they KNOW that they make up every node that connects to you. Which means they control your ISP too. 3. Premix routing makes this much loss of an issue, even if all of those nodes are compromised as well, your level of deniableity is the same as it is now. > 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. See above. > Furthermore, all inserts from a given node can be discarded and/or all > requests treated the same way. Yup. > 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. Any node can drop any request. If someone is trying to DOS the network like this they are stupid. Nodes will drop them as soon as they start to fail. Or if they wait and act normal for a while, and surround a few nodes so they drop off, they will reseed. It would be much easier and much more effective to launch a simple ping attack. > > > 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. I'm not going to argue over every point of GNUnet's implementation. They have written over a dozen whitepapers and docs describing their protocol. If you want to argue with their papers then go for it. But they have a lot of smart people who have spent a lot of time thinking about this and describing attacks. The fact that they have a working implementation, to me says that this CAN work. > 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. What makes you think that such an adversary could not get multiple identities even with a CA. > > 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. A simple ping attack and a node harvester, would be much more destructive. > 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. Read the white papers they address this sort of thing if I remember correctly. > 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. But this is not acceptable. The network cannot function without the CA. I would like to remind you that a few years back, many of the largest and highest bandwidth sites on the internet with some of the best security out there, were all brought to their knees by a DDoS attack, orchestrated by a single teenager. What makes you think that any single computer or installation of computers can withstand a planned attack by a rouge government. Whats more in the real world many groups do not limit them selves to sending 'digital' bombs. > 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. Always drops a single key == Always censors a particular website. > > 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. Yes, there are central DNS servers. The IANA / ICAN are single entities. If these go down the WWW is going to face problems for a while. > 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. I don't necessarily agree, they say it hinges upon "Unrealistic assumptions". However in the CP routing days Freenet had a distributed means of selecting a initial key value. If we were willing to go the fixed routing route, then more options open up. Read the Grapevine whitepapers. (sorry I don't have the link) They list 3 ways for nodes to be assigned an identity in a distributed way and not have control over the out come and still have it verifiable. They implement one of these. This at least insures that any cancer nodes will be located randomly, or only recognized by the existing cancer nodes. A CA could do better, but that's not bad. > 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. I don't think any non-distributed from of CAing can work in a Freenet context. > > 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. _______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
