Abstract
Re-encryption Mix Nets are used to provide anonymity by passing encrypted messages through a collection of servers which each permute and re-encrypt messages. They are used in secure electronic voting protocols because they provide a combination of anonymity and verifiability. The use of several peers also provides for robustness, since a Mix Net can run even in the presence of a minority of dishonest or incorrectly behaving peers. However, in practice the protocols for peers to decide when to exclude a peer are complex distributed algorithms, and it is non-trivial to gain confidence that the Mix Net will be robust and live in the presence of faulty or malicious peers. In this paper we model and analyse the algorithm used by Ximix, a particular Mix Net implementation, using the CSP process algebra and the FDR model checker. We model and analyse the protocol in the presence of a realistic intruder based on Roscoe and Goldsmith’s perfect Spy. We show that in the current implementation the protocol does not satisfy the robustness requirement. Finally, we propose a method of making it robust, and verify in FDR that the proposed solution is sound and provides this robustness. Along the way, we highlight the omissions and deviations from the original RPC proposal; Mix Net protocols are extremely fragile, and small and seemingly benign changes may result in security flaws. Our experimental results show that, with our modification, Ximix guarantees termination and produces a correct output in the presence of an intruder who can corrupt a minority of mix servers.