comp527

All of the four papers, i.e., SybilGuard, SybilLimit, SybilInfer and SumUp try to address the Sybil problem, where a malicious user takes on multiple identities and pretends to be multiple, distinct nodes in the distributed systems. Sybil nodes behave in many forms: a common node can obtain many different system identities by registration; several nodes collude with each other to do evil things; and even nodes in botnets may work together, and launch distributed denial-of-service (DDoS) attacks. In my view, the latter two can not be considered as Sybil attack; however, all of three may behave similarly, and even a botnet can register many Sybil nodes in a website.

On the other hand, various Internet services, especially the services which rely on the common customers to vote their quality,  such as digital commercial sites and online social networks are very vulnerable to Sybil attack. Li Jinyang lists two Sybil examples in SumUp, one of which is that students deploy automatic scripts to vote for their schools in Slashdot poll, and the other one is that Sybil accounts work together and vote on the content in Youtube. Yu Haifeng lists a lot of threshold values for the avoidance of Sybil attacks in different systems. In Byzantine fault tolerance system, the value for the ratio of malicious nodes is 1/3; for the security routing in Peer-to-Peer systems, the value is 1/4; for the voting system in Youtube-like systems, the value should be much smaller, depending on the feedback willingness of honest users.

Certainly, if we bind the system identities with the actual social identities, such as the social security numbers or driver license, then the problem should be easily addressed. Lack of widely accepted authorities in the world and the existence of single point of failure make this mechanism not good. Even people may not like to leak their privacy information to all such kinds of Internet services. Puzzles, including computation puzzle, memory puzzle, and even haman-intelligence-related puzzles (CAPTCHAs) are the actual ways to deal with the problem. However, they are proved to be vulnerable in SybilGuard.

The third way to address this problem is though the use of social networks, including the above four paper together, all of which are based on the same assumption that a Sybil nodes can not easily create the trust edges between themselves and the general honest nodes. Certainly, in the real social networks, this assumption works; however, in the Internet social networks, this assumption sometimes is questionable, since there are lots of cases that a general user accept a stranger as their friend. Even some users in the Youtube have thousands of friends, and even they never have a interactions with such friends. As a result, I think the interaction histories should be considered in such mechanisms, and SumUp is good towards this trend.

For SybilGuard and SybilLimit, I should admit that the underling idea is very novel. That is, to find the minimum cut between the Sybil area and the remaining graph. In my view, it is not that the number of attack edges is limited; on the contrary, it is that the number of victim nodes that connects the Sybil nodes are limited.  (1) However, in many systems, their may not exist such a social network, then the problem still be serious. (2)Another thing is that, even there exists some social networks in such system, the graph made of system nodes may not meet the requirements of SybilGuard, i.e., the main honest area should be a large strongly connected components and the number of nodes dominate the at least 80 percentage of the total nodes. To my knowledge, there are some online social networks, who have a number of strongly connected components, and the size of the largest one only dominate 30~40% percent of the total nodes. As a result, if we apply SybilGuard/Sybil Limit to such graph, then the false positive should be very large. Admittedly, the quantity of interactions among nodes in the largest component should be much large than that of the remaining nodes. However, a system also should provide such Sybil-resist service to such isolated nodes, especially considering many of such nodes are just newcomers.  (3) Because the deterministic algorithm of finding the minimum cut that connects the honest area and malicious area is NP-Complete, the author tries to use the “random walk” algorithm to test if a potential node is Sybil node. However, the “random walk” is deterministic, and should be updated if some nodes leave the system. Thus, the overhead due to the “churn” should be considered.  If a node leave the system, then all the random walks along though this node should be rebuilt. Facebook once states that all the content of a user who left the system would be saved in Facebook, and the such routing can not be changed if a node check out. However, we should give some random walks for new registered users. In sum, SybilGuad / SybilLimit can only apply to the snapshot of the graph.

Under the same assumption, George Danezis introduces SybilInfer to address the Sybil problem. The background of SybilInfer is totally the same with SybilGuard/SybilLimit; however, SybilInfer use the statistical way instead of deterministic algorithm to address this problem. There are several differences between SybilInfer and SybilGuard/SybilLimit: (1) the random walk is different. SybilGuad/SybilLimit create the “routing table” for each node, and then the routing is fixed. In addition, the probabilities of walking along all of the outing edges of a node are the same; however, in SybilInfer, this probability of walking an edge is related with the out degrees of an edge’s adjacent nodes.  (2) the algorithms on how to use the random walk path are different. SybilGuard/ SybilLimit uses the the fraction of cross points to make estimation. SubilInfer uses the Bayesian algorithm to compute the probability of a set of nodes being honest. The latter needs a sampling method. (3) Performance: it is stated in the original paper that SybilInfer works much better than SybilGuard/SybilLimit. You can refer the data in the original paper.

SumUp tries to reduce the quantity of votes from Sybil identities in the voting problem in social networks based on the same assumption. SumUp tries to use the “adaptive vote flow aggregation” algorithm to limit the bogus votes to no more than the number of attack edges in the trust network. In fact, SumUp tries to create a tree like the tree created by breadth-first-search algorithm  for each node by pruning some edges in social networks, and then assign the capacity to each edge, which means that the number of votes through the edge can not bigger than that capacity. Then if the distance from the Sybil nodes to this source node is far enough, then all the votes within the distance can be honest not considering the honest nodes’ fake votes. In addition, because the near the edges from the source node, the more capacity that the votes can get through the edge, then the attack edges in the minimum cut between the honest area and the malicious area can get only a small capacity. In addition to that, SumUp uses the vote history to adjust the pruned tree above. The problems with SumUp is that: (1) it can not apply to separated components (2) the overhead for each node can be large enough. (3) the algorithm is very complicated.

I read the above four papers several months ago, and I forgot some details about them. Maybe my description includes some mistakes.

A serious “protocol level” vulnerability is reported to be found in SSL. (see here)

According to the website of the company who discovered the vulnerability (link), which they call SSL authentication gap  : “Because this is a protocol vulnerability, and not merely an implementation flaw, the impacts are far-reaching. All SSL libraries will need to be patched.”

It is surprising to know that such a widely used protocol can be vulnerable.

I found an interesting website, when I was seaching for “Google Chrome”. It consists of 40 comics, which describe the ideas behind creating a multi-process browser. Like all Google products, Google Chrome is simple, efficient and minimalist. I highly recommend trying it, if you haven’t used it before.

I think we can all be inspired by these comics while designing our Quiltwork browser.

According to a report from Anti-Phishing Alliance of China (APAC), up to Oct. 22nd, APAC has handled accumulated up to 8342 phishing site domain in China. The top three targets of phishing sites are TengXun(famous for their IM client QQ), TaoBao(biggest online shopping site in China), and ICBC (Industrial and Commercial Bank of China).

Another astonishing figure shows that out of 338 million of internet users in China, there are about 110 million of them have ever encountered a problem of account or password stolen in recent half a year!

It is really a tough task to protect accounts and passwords for general users.

News source: http://www.chinanews.com.cn/it/it-itxw/news/2009/10-26/1931366.shtml

As most of you know, Windows 7 RTM is officially out as of yesterday. According to Gregg Keizer’s article, we do not need to buy full versions of Windows 7, instead we can just use the upgrade versions (which are considerably cheaper) for a clean install.

The hack is actually quite simple:

1. First we need to install Windows 7 from the upgrade DVD without entering a key.
2. After installing, we just need to change one registry key (1 to 0) and enter “slmgr /rearm” to command prompt.
3. After rebooting,  we can activate Windows with our upgrade key (before the hack, the key was not valid)

Actual details can be found in this blog. There was a similar (but more tedious) “install twice” hack for vista, now with Windows 7, it is even simpler.

Thank you again, Microsoft!

Tor is a system for users to communicate anonymously on the Internet, but in China, it is also a tool to break the restrictions provided by Great Firewall of China, a powerful censorship system which block lots of websites in and out of China.

There are some reports said that at the end of last month, most part of tor’s service was also blocked by GFC. Also on tor’s web page you can find the corresponding blog and data.

It was said that GFC blocked most of the directory servers of tor, thus a tor user cannot accesses them to get a list of available and trusted onion routers. The user can add bridges manually to avoid being blocked as long as he/she can get a list of them by other means.

“An election integrity advocacy group has found extensive voting machine source code in election databases that were provided in response to public records requests. The code, which powers Sequoia voting machines, is said to be a possible a violation of Federal Election Commission rules.”

It seems more evidence comes forward for not using the Sequoia voting machines.

For more info check  this out.

BitBucket, a major host of Mercurial repositories, experienced a major outage on October 2nd, preventing many users from accessing their online code repositories (thank goodness for DVCS). The situation has drawn the interest of many on the web because BitBucket is hosted on Amazon’s cloud computing services, EC2 and EBS. Indeed, this highlights one of the significant drawbacks of cloud computing services in that when things go wrong, direct access to your systems infrastructure simply isn’t possible. BitBucket wrangled with Amazon sales representatives and engineers to get them to admit there was a problem on Amazon’s side, which turned out to be a flood of UDP packets consuming all available bandwidth.

More can be read about the story in a BitBucket blog post found here.

Now gmail is attacked!, more than 30000 usernames and passwords have been posted online.
it was hotmail and now gmail.

source BBC

Facebook on Thursday fended off an attack in which multiple identical profiles were created to spread malware.

Antivirus provider AVG Technologies said users of its LinkScanner service detected numerous profiles that were identical except with different names and each included a link to what was represented as a home video but which instead displayed a fake antivirus alert when clicked. The scams are designed to trick people into paying for software they don’t need, to get credit card information from victims for identity fraud purposes, and often to install spyware on the computer.

“Clearly, the Data Snatchers have found a way to automate the creation of Facebook accounts, which means they’ve found a way to bypass the Facebook Captcha,” Roger Thompson, chief of research at AVG, wrote in a blog post. Successfully translating a Captcha, a hard-to-read image of letters supposed to ensure that a human is involved, is required for a new account .

The malicious link was blacklisted by the major Web browsers and Facebook was blocking the URL from being shared on its site, said Facebook spokesman Simon Axten. Meanwhile, the company was working to identify all the fake accounts and disable them, he added.

Axten disagreed with the AVG speculation that the Captcha system had been broken.

“We’re looking into how these accounts were created, but it’s very likely that the sign-up process was manual, or that the person behind the attack farmed out the Captchas to be solved by humans for a price,” Axten wrote in an e-mail.

For its Captcha system Facebook uses ReCaptcha, “which was recently acquired by Google and is about as well-regarded a Captcha provider as there is,” he said.

From http://news.cnet.com/security/?tag=bc