J. Cent. South Univ. Technol. (2007)03-0380-06

DOI: 10.1007/s11771-007-0075-3               

Design and analysis of two-layer anonymous communication system

WANG Wei-ping(王伟平), WANG Jian-xin(王建新)

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Key words:

scalability; anonymity; performance analysis; communication system；

1 Introduction

With rapid growth and public acceptance of the Internet as a means of communication and information dissemination, concerns about privacy and security on the Internet have grown. Anonymity becomes an essential requirement for many on-line Internet applications. Anonymity protects the identity of a participant in a networked application.

Many researches address strong anonymity. Technologies such as rerouting, padding and encryption are wildly used in anonymous communication prototypes^[1-5], which increases the complication of the system and largely restricts the scalability of system.

Crowds^[6] developed by AT&T implements sender anonymity based on P2P architecture, in which payload on each member is virtually constant as a function of the size of the crowd. This suggests that Crowds should be able to grow quite large. But central blender mechanism makes large management cost.

Other systems also suffer from lower efficiency. Herbivore maps each member into several sub DC-nets^[7], which has well scalability but poor efficiency as Dinner Cryptographer mechanism^[1] being used. In P5^[8], scalability is achieved by setting up multiple layers of broadcasting channel. But low channel efficiency is the main disadvantage in broadcasting system. In Tarzan^[9], each member can find other members in O(n) connectionsby running chatting protocol^[10]. There is no need of central management node, so the system can scale well. But chatting operations should always run and a lot of information should be exchanged among members, which reduces the efficiency of the system.

Some other researches focus on improving quality of anonymous service such as rerouting path length and delay^[11-14], not considering the scalability.

In this study, a new architecture of scalable anonymous communication system(SACS) was proposed based on Crowds.

2 Architecture of SACS

2.1 Introduction of Crowds

Crowds implements sender anonymity based on P2P architecture. P(I|H₁₊), which is the probability that the path initiator is the first collaborator’s immediate predecessor if there is at least one collaborator on the path, can be used to indicate the failure probability of sender anonymity in Crowds:

      (1)

where  n is the number of total members; c is the number of compromised members; p is the probability of non-collaborator in all members and P_f denotes forwarding probability. Obviously, the larger the P(I|H₁₊), the worse the anonymous performance.

In Crowds, membership is controlled and reported to crowd members by a server called blender. A new user firstly communicates with the blender. After authentication, the blender adds the new user (i.e., its IP address, port number, and account name) to its member list, and generates shared keys for each pair of the new one and others, then reports the member list and shared keys back to the new user and informs the other members the participation of the new one and their shared key.

In Crowds, each member should keep the members list, which is received from the blender when the member joins. The list should be updated when a new one joins or a member leaves.

So in Crowds, with increasing of the members, a large member list should be maintained in each member and a large of exchanged messages will be transported between the blender and members.

2.2 Basic idea of SACS

SACS tries to actualize sender anonymity just like Crowds. We still call the user agent jondo. When a user has joined in, it will take on the role of both sender and forwarder. All anonymous requests from a user’s application will be first sent to its own jondo. 

Fig.1 shows the logic management structure in SACS. The management area of the system consists of a main-blender and several sub-blenders, which are in charge of member’s joining and leaving. Each sub-blender manages one subgroup, in which some members are mapped in.

When a new user joins in, it firstly contacts with the main-blender. The main-blender authenticates it and maps it to at most s subgroups using some hash function, and then informs the sub-blenders that are in charge of these subgroups. The sub-blenders register the new user, send the subgroup’s member list and inform other users in the same subgroup of this update.

The joining process is described as follows. J_n is a

new user, is the shared key between i₁ and i₂. i₁ and

i₂ can be user or sub-blender.

1) J_n->main-blender: (IP, port, account)

2)main-blender->J_n: (IP of sub-blender_i, port of

sub-blender_i, )

/*sub-blender_i is the management server of subgroup that the new user is mapped to*/

3)main-blender-> sub-blender_i:                

4)J_n->sub-blender_i:  (IP, port)

5)sub-blender_i->J_n:  (IP of J_i, port of J_i, ) 

6)sub-blender_i-> J_i:  (IP of J_n, port of J_n, )

 /*J_i denotes all members in the subgroup managed by sub-blender_i*/

Fig.1 Logic architecture of SACS

In SACS, rerouting path will be setup as follows. First the user’s jondo randomly picks one jondo in its own subgroups as the next one and forwards the setup message to it. Any jondo who receives the forwarding message will forward it to any one jondo of its own subgroups with the probability P_f, otherwise will send it to the destination directly. Instead of from the whole system, any jondo in SACS only chooses his forwarder from his own subgroups.

2.3    Management mechanism in SACS

In SACS, the main-blender manages all sub- blenders. A sub-blender list, recording the index number, managing area and member amount of each sub-blender is kept in the main-blender. Each sub-blender should keep the identity information of the users who are mapped in his area, such as ( IP, Port, Account ). Each member also should keep the subgroup member lists.

In our scheme, the members in each area are limited between n₁ and n₂ considering the balance between anonymity and overhead. Too fewer members in a subgroup cannot support available anonymity while too much members will increase the management overhead. In our scheme, when the members of a subgroup are less than n₁ or greater than n₂, the merging or splitting process will work.

3 Performance analysis

3.1 Anonymity analysis

We assume that attacker has ability to compromise some members in the system and all compromised members can cooperate to guess the initiator of a session.

For comparing fairly, we use the same analysis method as in Crowds. Suppose some compromised member can cooperate together, firstly they can confirm which of them is the first one on the session’s forwarding path, and then guess its predecessor being the initiator. P(I|H₁₊) denotes the probability that the path initiator is the first compromised member’s immediate predecessor when there is at least one compromised member on the forwarding path. Obviously the smaller the P(I|H₁₊), the lower probability to tell the initiator, and the better the sender anonymity.

we suppose that there are totally n members and g subgroups in the system, each member can join s subgroups, each subgroup has m members, compromised members are evenly distributed in subgroups, p is the proportion of non-compromised member in the system. So, there are average mp non-compromised members in each subgroup and g=sn/m.

Obviously, when s=1, a member will join only one subgroup. The members on the forwarding path will be in the same subgroup. In this situation, we can get the P(I|H₁₊) just as the P(I|H₁₊) in Crowds, where the number of members is m instead of n:

But if s=1, forwarding will be in only one subgroup, which makes it possible to take concentrative attack. That is to say, if attacker can compromise many members in sender’s subgroup, the anonymity will be decreased dramatically. Supposing a scene that an attacker had controlled the members in sender’s subgroup over 50%. P(I|H₁₊) will be more than 50% in this subgroup. That is to say, there is more than half chance for the attacker to successfully destroy the anonymity in this subgroup.

When s＞1, a member will join more than one subgroups and the forwarding path will be over several subgroups, which can effectively avoid the bad anonymity when too many compromised members join in the same subgroup.

We deduce P(I|H₁₊) when s is not equal to 1 as follows.

Supposing P(H_i) denotes the probability of that the first compromised member is at ith position on the forwarding path, P(H₁₊) denotes the probability of that there is at least one compromised member on the forwarding path, we have

Assume P(v_i) is the probability that a member is the path initiator given that the member is not compromised and is on the ith position of the forwarding path.

When the first compromised member is on the first position of the path, its former must be the path initiator, so, P (I|H₁) =P (v₀) =1.

When the first compromised member is on the second position, we can get P(I|H₂) =P(v₁) =1/(mp). As the first compromised member on the path occupies the second position, we can confirm the first one on the path is not compromised one, which means the initiator (on the zero position) selects one of non-compromised members in its subgroup. As the initiator is just the one of non-compromised members, the probability of the first one being the initiator is 1/(mp).

When the first compromised member is on the third position of the path, there will be two circumstances. Firstly, if the first position on the path is the initiator, the initiator will be in the subgroup of itself, so the probability of the initiator being on the second position is 1/(mp). Secondly, circumstance is that if the first position not occupied by the initiator, it can be assured that the initiator is at least in one subgroup of the first member being located. If the subgroup of the initiator is chosen (the probability is 1/s), the probability of the initiator being on the second position is 1/(mp), else (probability is (s-1)/s) the probability of the initiator being on the second position is (s-1)/((g-1)mp). On the second circumstance, the probability of the initiator being on the second position is

   (2)

So, when the first compromised member is on the third position of the path, the probability of the initiator being on the second position is

   (3)

When the first compromised member occupies the fourth position of the path, there are also two circumstances. First, if the initiator is on the second position, the probability of the initiator being on the third position is 1/(mp). Second, when the initiator is not on the second position, the probability of the initiator being on the third position is s/(gmp).

So when the first compromised member is on the fourth position of the path, the probability of the initiator being on the third position is

   (4)

So we can deduce

(5)

Then we can also get the following formula:

  ₍₆₎

3.2 Analysis of management overhead

Subgroup management scheme was used in SACS to decrease the management overhead. The following is the analysis of management overhead in SACS comparing with Crowds.

In Crowds, the blender and each joined member must record the information of all the members. The number of the records is n.

In SACS, the main-blender must record the ID, area and number of members for each subgroup. So, there are g records in the main-blender. Each sub-blender should keep the members’ information in its subgroup. The average number of the records in each sub-blender is m. Also, each member should keep the member list in its subgroup, which has IP, port, and session key. As each member belongs to s subgroups, the record number is sm.

So compared with Crowds, the number of storage records has changed from O(n) in blender to O(m) in every sub-blender. In each member, the storage records number has changed from n to sm. And there are also g records restored in the main-blender, usually g<

In the following, we will discuss the transmission overhead of management in SACS. Suppose that every subgroup has m members, and each member joins in s subgroups. When there are n members having joined, each sub-blender will generate the session keys between every two members in its subgroup. The total number of session key is C_m². As each session key will be sent to two members, the overhead of session keys distribution is 2C_m²l_key1, where l_key1 is the length of the session key. Also, each sub-blender will transmit the member list to all the members in its subgroup, the transmission overhead is m(m-1)l_record, where l_record is the information length of the member record. 

When a member joins system, the main-blender will send the account key to it. So, the transmission overhead is nl_key2, where l_key2 is the length of account key. Considering the effect of the packet head, we must take the amount of transmission times into account. For each subgroup, the times of transmission is m(m-1)/2. So, there is total gm(m-1)/2 transmission times and the overhead of the transmission head is (gm(m-1)/2)l_h, where l_h is the length of the transmission head.

At the same time, we assume that the main-blender and all sub-blenders are in the same management region, which are connected with high bandwidth line, so the transmission overhead among them can be neglected.

Therefore, when the amount of joining members changes from 0 to n, the total transmission overhead is  gm(m-1)( l_key1+ l_record + l_h /2)+n l_key2.

Corresponding, in Crowds, the blender will generate the session keys between every two members, so the amount of session keys transmission is n(n-1) l_key1. The blender also needs to send the member list to every member, the overhead of which is n(n-1)l_record. As the

total times amount of transmitting is ,

the overhead of packet head is n(n-1)/2l_h. Therefore, the total transmitting overhead is n(n-1)(l_key1+ l_record+l_h/2).

Supposing Ψ represents the ratio of the transmitting overhead in Crowds to that in SACS, we can get

         (7)

When g/s²>1, the transmitting overhead for management in SACS is less than Crowds.

The leaving of members will also bring the management overhead. In SACS, the overhead of a member’ leaving is O(sm). While that in Crowds is O(n). So we can assure that the cost of member’s leaving in SACS is less than that in Crowds when sm

Moreover, the merging and splitting of subgroup will also bring additional cost in SACS. But if appropriate mapping scheme is used, the new joining member will be prior mapped into those subgroups with less members, which can decrease times of splitting. When the system runs steadily, the amount of members’ joining and leaving for the same subgroup is almost equivalent, thus the merging and splitting will not be frequent.

3.3 Member’s load and path length expectation

In the anonymous communication system based on probability forwarding, it has been proved^{[6, 13, 15]} that the expectation of the times that a member appears in all the forwarding paths is the same with the expectation of the forwarding path length 1+1/(1-P_f), which means that whether the path length or load on members has nothing to do with the amount of members in the system, only corresponding to the forwarding probability P_f. The larger the P_f, the larger the expectation of path length and the load on members. In SACS, as the forwarding scheme is the same as that in Crowds, we can also get the same conclusion.

4 Simulation and performance analysis

In the simulation, the group is generated randomly according to relative parameters and the requests are created randomly. The compromised nodes are randomly selected from n nodes with probability 1-p, which are not allowed to create requests. In our simulation, n=   10 000.

We test P(I|H₁₊) with different P_f,1-p and s, and also compare the simulation results with the theoretical values. At the same time, we test the payload with different P_f and s.

Fig.2 shows the P(I|H₁₊) with different P_f and s when m=200 and 1-p=10% in simulation and theoretical computation respectively. As shown in Fig.2, the simulation results are very close to the theoretical values. P(I|H₁₊) is decreased with increasing of P_f . Also s does not influence P(I|H₁₊) markedly. According to the analytical results in section 3.2, the ratio of overhead in Crowds to that in SACS is Ψ=g/s². The smaller the s, the larger the Ψ. But as the analysis in section 3.1, the value of s should be larger than 1 to avoid concentrative attack. So considering the network overload and security, we propose that s=2. Assume s=2, m=200 and n=10 000, the ratio of the management cost in SACS to that in Crowds is about 1?25.

It is noted that the number of members in the subgroups is not static. Fig.3 shows the simulation results when m is a random number between 400 and 600. Also curve of P(I|H₁₊) at m=500 is given for comparing.  It can be seen that the result at m=500 is very close to that at m being a random number between 400 and 600.

Fig.4 shows the value of P(I|H₁₊) in SACS is little higher than that in Crowds and the increased value is only 0.001-0.020, which indicates that SACS can keep

Fig.2 P(I|H₁₊) different P_f and s (m=200, 1-p=10%)

Fig.3 P(I|H₁₊) with different P_f , m and 1-p at s=3

Fig.4 P(I|H₁₊) in Crowds and SACS with  different P_f (1-p=10%)

almost equivalent anonymity with Crowds.

Fig.5 shows the average payload of each member with different P_f. The curve of 1+1/(1-P_f) is the theoretical value. As shown in Fig.5, the simulation results are corresponding with theoretical results, and the payload depends on the value of P_f and increases quickly with increasing of P_f.

Fig.5 Payload with different P_f at m=200

5 Conclusions

1) A new architecture of anonymous communi- cation system-SACS based on forwarding mechanism was proposed.

2) By two-layer management scheme, the manage- ment overhead decreases efficiently, which also makes the system well scalable.

3) The results of theoretic analysis and simulation indicate that SACS can keep equivalent anonymity with Crowds, while having lower management cost and good scalability.

References

[1] CHAUM D. The dining cryptographers problem: Unconditional sender and recipient untraceability[J]. Journal of Cryptology, 1988, 1 (1): 65-75.

[2] BERTHOLD O, FEDERRATH H, K OPSELL S. Web MIXes: A system for anonymous and unobservable internet access[C]// Workshop on Design Issues in Anonymity and Unobservability. Heidelberg: Springer-Verlag Press, 2001: 115-129.

[3] DINGLEDINE R, MATHEWSON N, SYVERSON P. Tor: The second-generation onion router[C]// Proceeding of the 13th USENIX Security Symposium. San Diego: ACM Press, 2004: 303-320.

[4] MURDOCH S J. DANEZIS G. Low-cost traffic analysis of tor[C]// IEEE Symposium on Security and Privacy. Oakland: IEEE Computer Soc, 2005: 183-195.

[5] GOLDSCHLAG D, REED M,SYVERSON P. Onion routing for anonymous and private Internet connections[J]. Communications of the ACM, 1999, 42(2): 39-41.

[6] REITER M, RUBIN A. Crowds: Anonymity for web transactions[J]. ACM Transactions on Information and System Security, 1998, 1(1): 62-92.

[7] GOEL S, ROBSON M, POLTE M, et al. Herbivore: A scalable and efficient protocol for anonymous communication[R]. Computing and Information Science Technical Report TR2003-1890, Cornell University, 2003-04.

[8] SHERWOOD R, BHATTACHARJEE B, SRINIVASAN A. P5: A protocol for scalable anonymous communication[C]//IEEE Symposium on Security and Privacy. Oakland: IEEE Computer Society Press, 2002: 58-70.

[9] FREEDMAN M, MORRIS R. Tarzan: A peer-to-peer anonymizing network layer[C]// The 9th ACM Conference on Computer and Communications Security. Washington, DC: ACM Press, 2002: 193-206.

[10] HARCHOL-BALTER M, LEUGHTON T, LEWIN D. Resource discovery in distributed networks[C]// ACM Symposium on Principles of Distributed Computing. Atlanta: ACM Press, 1999: 229-237.

[11] WANG Wei-ping, CHEN Jian-er, CHEN Song-qiao, et al. Research on a short distance-prior rerouting scheme in anonymous communication[J]. Journal of Software, 2004, 15(4): 561-570. (in Chinese)

[12] WANG Wei-ping, CHEN Jian-er, WANG Jian-xin. An anonymous communication protocol based on groups with definite route length[J]. Journal of Computer Research and Development, 2003, 40(4): 609-614. (in Chinese)

[13] SUI Hong-fei, WANG Jian-xin, CHEN Jian-er, et al. The cost of becoming anonymous: on the participant payload in Crowds[J]. Information Processing Letters, 2004, 90(4): 81-86.

[14] SUI Hong-fei, CHEN Song-qiao, CHEN Jian-er. Decreased forwarding probability based length control strategy of crowds[J]. Mini-micro Systems, 2005, 26(3): 387-391.

[15] SUI H F, WANG J X, CHEN J E, et al. An analysis of Forwarding Mechanism in Crowds[C]//IEEE International Conference on Communications. Anchorage: Institute of Electrical and Electronics Engineers Computer Society, 2003: 261-265.

(Edited by LI Xiang-qun) 

Foundation item: Projects(60403032) supported by the National Natural Science Foundation of China; Project (NCET-05-0683) supported by the New Century Excellent Talents in University, China; Project(IRT0661) supported by Changjiang Scholars and Innovative Research Team in University, China

Received date: 2006-07-24; Accepted date: 2006-10-27

Corresponding author: WANG Wei-ping, PhD; Tel:+86-731-8830212; E-mail:wpwang@mail.csu.edu.cn