In the standard message passing models it is assumed that the identity of a sender is known to the receiver. In practice, this often is not the case, due to impersonation attacks by malicious adversaries. Various impersonation attack schemes have been extensively investigated in the context of network security or cryptography, in particular for peep-to-peer and sensor networks [4,5]. Here, we study this problem in the context of distributed computing theory.Consider a set of n processors, p_1,...,p_n, communicating by means of point-to-point message passing between every pair of processors. Assume that the message sender is identified by including its id in the message. For simplicity the communication is assumed to be synchronous. The adversary is an external entity capable of injecting messages with arbitrary content into the network (but it is incapable of preventing the processors from receiving each other's messages). The ids of the processors are assumed to be fixed and known a priori, thus injecting messages that impersonate the real processors is the only way by which the adversary can interfere with the computation. Adversarial behavior of this kind is known as stolen identities Sybil attack [4,5]. For the purpose of formal analysis, the strength of the adversary is quantified by the number of messages it is able to send to each processor in every round. A k-adversary can generate up to k messages for every processor, so that a processor can receive up to n + k messages in a round, instead of just n correct messages. This formulation includes the particular cases of an adversary that in every round can impersonate some specific k processors, or of a system with n + k processors, k of which are Byzantine, capable of sending messages with arbitrary ids and content.
展开▼
