基于攻击方的网络匿名性概率分析

虎 勇，李镔剑，陈紫煜，苟俊卿，陈瑞东

(1.官地水力发电厂,四川 西昌 615000；2.北京信息科技大学 自动化学院,北京 100192；3.电子科技大学 网络空间与安全研究院，四川 成都 611731)

0 引言

随着网络的快速发展，人们越来越注重在互联网上的个人隐私，一些具有严格隐私要求的应用程序需求(如网页浏览、即时消息传递和电子投票等)，迅速增加了研究人员和从业人员对开发可靠隐私增强技术 (例如匿名通信网络) 的兴趣。设计此类网络的主要目的是通过在公开网络上建立匿名通信来隐藏通信方(即消息的发送方或接收方)的真实身份。自1981年Chaum[1]提出不可追踪邮件问题和Mix解决方法,设计了匿名传输的新概念。对匿名系统提供的匿名性进行量化，从概念提出开始一直就是重要挑战，Chaum[2]提出利用匿名集大小来度量匿名性。Reiter和Rubin[3]从用户角度单独考虑匿名性，从绝对隐私到可证明暴露，提出6级匿名。Sarjantov[4]和Diaz[5]利用熵的方法来度量匿名性。关永等[6]利用攻击方角度对匿名性进行度量，提供了匿名性度量的新角度[7]。迄今为止，此类网络所提供最重要的匿名属性是消息发送方的匿名性，它们通过重路由机制利用多个中间节点来隐藏消息发送方的真实身份，但要实现完全匿名的交流很难[8]。针对匿名通信问题，提出了不同解决方案，这些方案可为用户提供多少匿名性？为了评判匿名通信网络给用户带来了多少安全性，有必要通过一些定量指标来评测此类网络所提供的匿名度，即希望可以通过一些指标区分可靠的匿名通信网络和不可靠的匿名通信网络[9]。为评估重路由机制匿名通信网络的匿名度，本文提出一种用于匿名通信网络安全性分析的概率模型。

1 建模

在建模过程之前，需要声明潜在的假设，以便能够基于这些假设构建模型。因为并不希望该度量方法仅局限于特定网络，其应该适用于各类匿名通信网络，故假设时考虑更一般化的条件。而从攻击方来评估匿名网络，必须同时考虑匿名通信网络和攻击者两方面。

1.1 匿名通信网络子模型

一个典型的匿名通信网络由多个节点组成，这些节点之间彼此协作形成从源到目的地的随机路径，以便向用户提供匿名属性。在本文设置中，匿名通信网络的主要任务是隐藏消息发送者的身份。这项研究处理的是“多跳”匿名通信网络，而不是“单跳” 网络。从匿名的角度来看，单跳网络只有一个中继节点，重路由路径没有不确定性，达不到匿名通信的需求。

为研究“多跳”网络[10-12]，假设有一组潜在发送者、一组中继节点和一个特定的接受者，其中S代表发送者，I代表中继节点，R代表接受者。由于本文只对量化发送者的匿名感兴趣，同时又不失一般性，假定接收方已被攻击者所控制。在许多重要的应用中，这是一个现实的假设[13]。例如，考虑诸如匿名电子邮件和网页浏览等应用程序,大多数访问特殊网页的人都希望对网页服务器(即接收者)隐藏他们的身份(即IP地址)。在这种情况下，网络服务器被假定为受到威胁[14]。

将匿名通信网络建模为无向图G=(V,E)，其中V=S∪I∪R，是潜在发送者、中间节点和接收者的顶点集，E⊆V×V是这些顶点对的边集，代表顶点之间的直接联系[15]。本文更倾向通过邻接矩阵来表示的相应图G(为方便起见，假设S∩I=φ)。假设有n个中间节点和m个潜在发送者，并且匿名通信网络的中间节点被标记为1,2,…,n,并且潜在发送者被标记为n+1,n+2,…,n+m。I和S的集合定义如下:I={I1，I2，…，In}，S={sn+1，sn+2，…，sn+m}。

图1展示了一个无向图，表示由5个中间节点、3个潜在发送者和1个接收机组成的匿名通信网络。假设在任何2个顶点之间都有一条边，为简单起见，在图中未示出边缘。

图1 匿名通信网络示意图Fig.1 Diagram of anonymous communication network

对其进行概率分析，有必要描述匿名通信网络如何根据某些概率分布随机选择重路由路径的中间节点。由于匿名通信网络在逐个节点的基础上构建重路由路径，因此“选择概率”是分配给它们相应图形的边。因此，将图G=(V,E)的邻接矩阵P=(pij)称为重路由矩阵。当两节点为同一节点时，pij=0；当两节点不同且都为两节点连线属于边集E时，pij为边集中选定该连线的概率；当两节点连线不属于边集E时，pij=∞，即为:

(1)

任何匿名通信网络的核心都是其重路由路径选择策略，只能根据特定的网络路径选择策略来选择特定的网络，即如果攻击者可以识别传输过程中所选路径，则通过此路径进行的所有通信都将暴露给攻击者。同时，任何路径选择策略都必须满足一些约束条件。本文从匿名的角度来看问题，可以对策略施加许多约束，最关键的约束条件是“网络拓扑”“路径拓扑”“路径长度”，通过过去对匿名通信网络的研究可知，这些约束条件可以被识别和确定[16]。

网络拓扑匿名通信网络的拓扑结构与标准计算机网络的拓扑结构有很大不同，对网络匿名级别具有重要影响。对于匿名通信网络的拓扑结构，需要各节点之间链接更密集，避免攻击者轻易识别各节点通信状态。

路径拓扑路径的拓扑结构可以反映路径的复杂程度,最重要的是确定预定路径是否有重复。将不经过同一节点的路径认定为简单路径，即一条简单路径上的所有节点必须是不同的；将多次经过同一节点的路径认定为自由路径，即该路径不止一次地遍历某些节点。相比简单路径，访问者更倾向于使用自由路径的拓扑方式，因其更难被攻击者所识别，匿名性更高。

路径长度路径长度定义为路径顶点序列中的顶点总数减去1，在未确定完整路径时，路径长度可变。设L是一条均匀分布的可变路径的长度，并假设M和m分别是L的上界和下界，其概率质量函数为：

(2)

1.2 攻击者子模型

为了对匿名通信网络进行安全性分析，决定用潜在攻击者的视角来分析匿名通信网络，并尽可能真实地描述攻击者的能力。攻击者的主要任务是预测重路由路径，从而识别消息的真正发送者。因此，“匿名集”被定义为所有可能发送者的集合。潜在的攻击者可以通过各种方式获得大量有效信息来缩小该集合[17]。因此，希望拥有一个强大的匿名通信网络，这里“强大”是指攻击者知道该网络的路径选择策略，并且破坏了它的一个或多个中间节点，却不能精准地确定它的实际重路由路径。

设计的初衷是希望该网络可以广泛部署并使用，因此，假设攻击者能够利用现有的方法和工具推断出路径选择策略(即网络拓扑、路径拓扑和路径长度)。同时，假设攻击者将能够控制部分中间节点和潜在发送者，并利用已破坏的中间节点和潜在发送者所捕获的信息来揭示真正发送者身份。已知在通信网络中，每个路由节点都知道它在该路径上的前一节点和后一节点。因此，如果某一被控节点是路径的一部分，攻击者至少可以识别该路径上的3个节点。但此时，攻击者只能捕获通信通道上的流量，却无法更改这些信息，故该攻击者模型只考虑被动攻击。如果在进行某一信息传输时多次遍历被破坏节点，攻击者可以利用节点的相对顺序创建一个遍历节点的排序列表，并实时更新该匿名通信网络的初始信息。

攻击者的最终目标是利用所捕获到的信息，重构从发送方到接收方的消息重路由的实际路径。例如，考虑图2中的重路由路径(6,5,3,R)，由于接收方已经被攻击，攻击者只知道路径上的节点3。假设攻击者已经破坏了节点3，攻击者可以根据节点3所得到的信息知道节点5也在该传输路径上。另一个例子，考虑重路由路径(7,1,2,3,1,4,R)，假设攻击者已经破坏了节点1，他知道节点2、3、4和7也在该路径上。根据消息到达和离开的时间，可以得到路径上节点的正确顺序，即7、1、2、3、1、4。

图2 路径拓扑Fig.2 Path topology

2 模型的概率分析

到目前为止，已经给出了该模型的基本假设。该模型由一个匿名通信网络子模型和一个攻击者子模型组成。对于该模型，将演示匿名通信网络的概率分析及其匿名损失的量化过程。通过以下几个步骤进行评估：

第一步，定义匿名指标，来量化匿名通信网络提供的发送者匿名级别。为了计算度量，需要计算潜在发送者的概率分布。

第二步，构造一种寻径树。寻径树表示满足匿名通信网络路径选择策略约束的所有重路由路径，它可以系统地生成所有感兴趣的路径。

第三步，用重路由概率参数化寻径树，并利用其计算潜在发送者的概率分布，再利用概率分布计算其他指标。

2.1 定义匿名指标

设S为消息M的潜在发送者的离散随机变量，对其进行评估，主要定量匿名度量定义是潜在发送者为真正发送者的概率。首先，在没有任何信息的情况下，考虑潜在发送者为离散均匀分布：

(3)

通过分析匿名网络的行为，攻击者可以得到更准确的潜在发送者分布。这个分布将描述每个候选者成为真正的发送者的概率[18]：

p′(S=si)=p′i，

其中，

(4)

首先计算随机变量S的初始熵：

(5)

攻击者通过捕获信息后得到新的分布：

(6)

为了表示初始分布和通过利用先验知识得到的新分布之间的区别，利用“相对熵”来量化。

(7)

对于该问题：

(8)

这种度量是一种描述偏差的度量，表明攻击者的估计与事实的差距。一些研究已引入了这种度量方法[19]。本文的主要新颖之处在于建模方法的基本假设和度量标准的过程评估。

假设消息M从潜在的发送方发送到特定的接收方。为了识别消息真正的发送方，攻击者尝试重建从源到目的地的路径，将概率地选择潜在的路径。攻击者的成功主要取决于两个因素：被攻击者攻击节点的数量和节点之间的链路信息的数量。假定基础图是完整的，攻击者必须考虑所有可能的路径。事实上，攻击者需要解决两个主要问题：表示一个匿名通信网络的两个指定节点之间有多少条路径?如何系统地生成这些路径?

2.2 寻径树

攻击者将猜测消息的潜在发送者并通过执行穷举搜索得到概率分布，再考虑其中满足所有约束条件的路径，然后确定潜在发送者的理想分布。如果要计算路径的数量，将面临两个严重的障碍：① 路径的数量可能会随着图的大小呈指数增长；② 生成所有路径并非易事。本文通过使用一种类型的状态空间树来克服，将其称为寻径树。

推导概率分布的思想是基于构造状态空间树的变体，其节点反映了重路由路径的节点所做的特定选择，它可以系统地生成所有感兴趣的路径。因此没有必要生成一个完整的寻径树，只要保证考虑节点的后续节点不可能存在完整路径，便进行“剪枝”，不再考虑其后续节点的情况以减小任务量。寻径树的根代表在开始搜索可能路径之前被破坏的消息接收方，从根到叶的任何路径都是候选路径；树中第一级节点代表路径第二个中间节点的选择(由于攻击者是要揭露发送方的身份，从接收方反向溯源，故节点选择为反向选择)。将以宽度优先搜索的方式构建树，如果当前节点是有希望的，则将路径的下一跳备选节点作为其子节点。如果当前节点被证明是没有希望的，算法回溯到节点的父节点，为它的父节点考虑下一个可能的选项;如果没有这样的选项，它将回溯到树的上一级，以此类推。最后，算法在获得从源到目标的完整路径后，继续搜索其他可能的路径。预计路径搜索方法将能够根据网络拓扑和路径的信息，修剪足够多的路径查找树的分支。

2.3 概率分布计算

利用寻径树可以得到潜在发送者的概率分布。由于路径是基于概率分布构造的，所以攻击者可以为任意给定的一对顶点之间的网络链路分配选择概率。也就是说，通信链路的选择是基于这些概率的，这些概率可以根据一些观察得到，例如利用一些指标，如中间节点的地理位置和网络链路的带宽来确定这些值。这些转移概率可以简单地表示为(m+n) × (m+n)转移概率矩阵S:

(9)

式中，m和n分别为潜在发送者和中间节点的数量。对于所有i,j∈V，在这个矩阵的第i行和第j列中，元素0≤sij≤1表示节点i在重路由路径上是节点j的“直接后继”的概率。由于图是完整的，因此在图的任意一对顶点之间均存在一条边。设随机变量Yn是从目的地到源的“反向”路径上的第n个节点。因此，sij可以表示为:

sij=P(Yn=j|Yn-1=i)。

(10)

在这样的矩阵中，有些行和列是统一的。也就是说，矩阵S的元素满足以下约束条件:

(11)

显然，被破坏的顶点的存在改变了矩阵的某些元素。设C为被妥协的潜在发送者和中间节点的集合，有C⊆V，设j∈C为妥协顶点。如果j不在路径上，矩阵S对应的元素保持不变。如果j在路径上，相应的元素被更新，这意味着顶点j不再有不确定性了。寻径树用重路由概率参数化，概率值被分配到树的边缘。从根到叶的路径是满足约束的重路由路径，且重路由路径计算的所有概率值加起来为1。对于一般情况下的寻径树，设X和Y为两个离散随机变量，分别表征在寻径树的第1层和第2层中所做的选择。根据定义，在树的第1层，有:

(12)

设P(x,y)为这些随机变量的联合概率质量函数。根据定义，在树的第2层，Y(X)的条件概率质量函数为：

且

(13)

将其推广到整个树，则在树的最底层(叶节点)可得：

(14)

假设路径L=(si,nj,…,nr,ns,R)，长度为L的路径是从发送方si到接收方R的路径。为了计算该算法溯源找到路径L的概率,可以将条件概率P(A∩B)=P(B)P(A|B)推广得到路径选择的概率:

P(Yl=R,Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)=

P(Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)×

P(Yl=R|Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)=

P(Yl-1=ns,Yl-2=nr,…,Y1=nj,Y0=si)×pRs=

P(Yl-2=nr,…,Y1=nj,Y0=si)×psr×pRs=

⋮

pji×…×psr×pRs。

(15)

树的每个分支都被标记为特定的选择概率，这样从根到任何叶的所有分支概率的乘积就等于选择相应路径的概率。因此，可以为每条可能的路径L分配一个选择概率，其组成边的概率的乘积为：

(16)

对于寻径树的定义，网络的中间节点和潜在发送者分别是树的内部节点和叶节点。由于树的叶子部分代表消息的潜在发送者，所以在使用寻径树指定新的分布时，需要将潜在发送者分成两组，属于树叶的发送者顶点和不属于树叶的发送者顶点(即被妥协的发送者)。假设i是一个潜在的发送端顶点，它是树的叶子，可能出现多次。为了得到该节点为真正发送者的相应概率，需要考虑该节点从根到该叶的所有对应路径。设L(i)={L1(i),L2(i),…,Lt(i)}为发送端顶点i对应的路径集合，其中t为这样路径的个数，故有:

(17)

最后，利用了全概率定理的一种形式。设L(T)=[L(1),L(2),…,L(k)]为发送者的“路径向量”，其中T为寻径树。所有叶节点对应的概率之和必须是1，因为它们覆盖了选择路径的所有可能性：

(18)

式中，k为所有潜在发送者的数量。

至此，攻击方可得到任意路径被选择的概率，并可以通过此概率计算潜在发送者的概率，定量分析该网络的匿名性。

3 结论

本文引入一个概率模型来测量匿名通信网络提供的匿名性水平,其主要目的是提出一种用于评估匿名度量的建模方法，而不是对模型进行精确的参数化。换句话说，主要关注的是发展一种定量分析匿名通信网络匿名性的理论方法，而不是精确分析模型的评估。该模型可以简单地进行扩展，用于量化匿名通信网络的其他匿名属性(如接收者匿名)。寻径树可以系统地搜索所有可能的重路由路径，故肯定能找到感兴趣的路径,从而保证分析方法的正确性。