The (n‐1) attack is the most powerful attack against mix which is the basic building block of many modern anonymous systems. This paper aims to present a strategy that can be implemented in mix networks to detect and counter the active attacks, especially the (n‐1) attack and its variants.
Based on the analysis of the preconditions of a successful (n‐1) attack and the limitations of previous countermeasures, this paper presents Regroup‐And‐Go mix (RG mix) for detecting and foiling the (n‐1) attack. Messages are divided into groups by the sender, regrouped and forwarded at the intermediate mixes, and reordered and sent to the receiver at the last mix. The grouping information for each mix is encrypted with the public key of the corresponding mix. The messages are forwarded only when all the messages in the same group have arrived. When the regrouping of messages triggers a timeout alert, the mix detects the ongoing attack and takes countermeasures.
RG mix can help foil and detect the (n‐1) attacks from both internal and external attackers because the grouping information for the other mixes is unavailable for them. They can only guess which messages can constitute a group and randomly select some messages to have a try. Analysis and experiments show that the probability of successful attack is low.
RG mix uses the hidden correlations between messages for active attack prevention and detection. RG mix does not have unpractical requirements and can be used in the real‐world implementations.
Emerald Group Publishing Limited
Copyright © 2006, Emerald Group Publishing Limited