刘青  龙士工

（贵州大学 计算机科学与技术学院，贵州 贵阳550025）

 

    摘  要  本文设计了一个新颖的基于数据挖掘的模型，通过它可以探测安全协议中的共谋攻击，探测过程中使用了Prolog语言的内部推理机制。通过对实例的分析表明该方法是有效的，并且可以用于发现及预防安全协议中的共谋攻击。

    关键词  共谋攻击；安全协议；Prolog语言

  

    在安全的电子商务中安全协议已经扮演着非常重要的角色。因此，很多方法已经被运用在探测潜在的缺陷以保证交易的安全。尽管广泛的运用了形式化分析方法，但是共谋攻击，隐藏的危险的安全问题仍然被人们所忽视。在传统的分析方法中不合理的假设任何主体都不可以通过非法的手段获得秘密，然而，用户可以串通多个参与主体分享他们彼此的秘密，从而获得更多的保密信息。为了更加可靠的分析安全协议，探测勾结攻击是非常必要的。

    假设A表示原子公式，L为命题公式，是由多个原子符号及逻辑连接词，例如像等所组成的。X，Y∈A代表参与主体，像发送者，接受者，可信第三方。令 α，β，γ和m为可靠消息， ф，φ，ψ为公式集合。CA代表认证中心，Z为攻击者团体，k为密钥，Cert（X） 表示主体A的一个被CA认证的证书。K_p（X）和 K^-1（X）分别代表主体X的一对公开，私有密钥；S(m,K^-1(X))表示用K^-1(X)对消息m的签名；E（make）是用密钥k对消息m的加密密文。

    在电子商务系统中处理可靠消息的过程通常有4个步骤分别为：生成消息、发送消息、接收消息、消息认证。中间是密文和明文的传输。一些规则以及对消息的基本操作在文献[1，4]中已经阐述。

    一个共谋攻击通常包括攻击者Z，主体集合P={P₁，……，P_n}，共谋攻击的门限限制k，1≤k≤n 。图像1表示了主体A，B，C如何合作透露秘密给Z的。值得注意的是，并非任意k个主体的联合都可以获得秘密。各个参与主体的责任分工如下：

    参与者P：在参与交易中使用电子交易协议。

    攻击着Z：运用从各个参与者那里收集的信息发起攻击。

    门限k：要达到共谋攻击，所需要的参与主体的最小值。

    定义1  攻击结构 的集合是由以下元素组成的：P={P₁，……P_n}是参与主体集合（他们通过交换各自的秘密获得秘密集合S）。M_X表示主体X的消息集合。A（k，n）是门限设置，即如果当前的行为主体AP，并且k≤n，则允许该秘密被恢复。

    这里α_i代表M_Xi中的消息集合。

    根据以上定义一个共谋攻击必须满足三个条件：

    （1）；

    （2）1≤k≤n；

    （3） ，α_i至少属于2个参与主体。

    由上面可知，被用来发起攻击的每一个 都必须至少属于两个参与主体。因此，找出被多于一个的主体所拥有的 是非常必要的。从参与主体中获得的可靠消息集合被称作是交易数据库。因此，被探测到的 被修改定义为多次出现的消息集合，称之为——frequent k-itemsets（以下用FI表示）（2≤k≤n）。探测共谋攻击可以按照以下三个步骤进行：

    （1）确定多次出现的消息集合—frequent k-itemsets。

    （2）建立基于所获知识库的推理法则。

    （3）通过将所获得frequent k-itemsets与知识库相匹配来探测共谋攻击。

    令I={i₁,i₂,...,i_n}为一消息集合，D为交易事务的集合，称为交易数据库。每一项交易T∈D。令AI是消息集合I的子集，如果AT，我们就可以说交易T包含A。一个消息集合A在交易数据库D中有一个支持者，用supp（A）表示。因此，有 

               （1）

    这里T_A表示在交易数据库中包含的消息A。

    一个消息集合A在D中被叫做一个frequent itemset，如果它的支持者大于等于最小的支持者数量（minsupp）^[2]。在本文中，Frequent Patterns（FP）的树状运算法则被用于从交易数据库中确定FI。

    从分析来看，只有当minsupp指定之后，FI才可以被确定。根据上面所提到的共谋攻击所需要的必备条件，每一个消息子集 必须属于至少两个主体。假设在交易中有n（n≥3）个主体。于是有：

minsup P=m/n              （2）

    这里n必须大于等于3，因为在只有两个参与主体的交易中发生共谋攻击是不现实的。另一方面，根据不同的安全要求，m≥3是可以被改变的。M的值越大，所获得的frequent itemsets越多。

    本部分内容介绍在交易数据库中如何构建知识库，如何处理所获得的事实。为简单起见，这里假定通信信道和公钥是安全并可靠的，并且，在交易过程中的消息是新鲜的。因此，对于消息的新鲜性规则及主体公钥的验证规则不再讨论。

    事实用来说明一个问题中已知的对象和它们之间的关系。在Prolog程序中，事实由谓词名及用括号括起来的一个或几个对象组成。谓词和对象可由用户自己定义。

    知识库（包含事实和推理规则）是程序根据环境和所给的输入信息以及所要解决的问题来决定自己的行动，所以它是在环境模式的指导下的推理过程。知识库中的推理法则是由安全协议中对可靠消息的基本操作构成的。

    在安全协议中，建立知识库和获得FI是探测潜在共谋攻击的基础。在本文中，Prolog语言的内部演绎推理机制被用于处理知识库和FI。不过，FI需要转化为Prolog语言的谓词形式。另外，为了核实参与共谋攻击的主体，弄清楚可靠消息的主体名字是非常必要的。

    定义2假设

    表示交易集合T中的一个frequent k-itemsets集合。令P={P₁，……P_n}为参与本次交易的主体集合。于是有

    是属于主体P_j的FI    （3）

    在上面的定义中断言know P_j={α₁，……α_k}表示主体 P_j知道消息{α₁，……α_k}。依据公式（2），至少应该有两个主体知道消息{α₁，……α_k}。

    对于FI的转化可以通过用户信息形式的相互交换获得。另外，事实数据库在收集之前是被清空的，一旦用户递交了探测请求，我们需要一个推理程序以便有效的处理知识库以及获得的FI。至于if-then规则我们有两个基本的推理方法^[8]：

    ——后向链接（backward chaining）

    ——前向链接（forward chaining）

    所谓后向链接是以一个假设开始，根据已知条件依据知识库中的规则进行推理，最终证实结论。前向链接是一个相反的方向。在我们的探测模型中，所使用的推理方法就是后向链接，以达到核实数据的目的。该探测用一个之前的假设，猜想可能遭受共谋攻击的消息作为起点开始分析，如果最终达到目的，则说明发现了这种共谋攻击。否则，如果在现有信息的基础上我们没有发现共谋攻击，就说明在当前的交易中没有共谋攻击发生。

    为了举例说明新方法的正确性，下面我们用在线支付协议—SET协议^[5]的其中一部分作为例子进行分析。当然，通过对知识库不同的扩展，分析其他的安全协议对我们的新方法来说也是很容易的。

该例子描述的持卡人C发起一个注册表请求，其目的是获得认证中心CA的一个合法有效地认证。换句话说，持卡人C想成为被认证中心CA承认的持卡帐户的合法使用者。

    其中设计到的消息包含：持卡人的初始账号（PAN）、注册表请求（RegFormReq）、对称密钥 k₁和CA的公开交换密钥（K_pb（CA））。只有CA、C和发行者（Issuer）知道PAN，在该交易过程中假设有四个主体，每个参与主体所拥有的消息集合组成交易数据库，可以描述为如同和的形式。表1即是对交易数据库中消息的描述。

    根据表1来确定FI，令m = 2，根据公式（2）可得，minsupp = 2/4=0.5.结果，运用FP法则 可以得到以下的FI：

    Frequent1-itemsets：{ PAN }，{ RegFormReq }，{ k1 }，{ Kpb（CA）}；

    Frequent2-itemsets： { PAN，RegFormReq }，{ PAN，k1 }，{ PAN，Kpb（CA） }，{ RegFormReq，k1 }，{ RegFormReq，Kpb（CA） }，{ k1，Kpb（CA） }；

    Frequent 3-itemsets： { PAN，RegFormReq，k1 }，{ PAN，RegFormReq，Kpb（CA） }，{ RegFormReq，k1，Kpb（CA） }，{ PAN，k1，Kpb（CA） }；

    Frequent4-itemsets： { PAN，RegFormReq，k1，Kpb（CA） }.

    获得以上这些frequent itemsets后，接下来就要将其转化为Prolog断言的形式。例如可将{ PAN }转化为：know（P ，PAN），knpw（P ，PAN），know（P ，PAN），know （P ，PAN）。在本文第三部分提出，知识库包含推理规则和事实，一旦以上程序已经完成，用户就可以递交探测请求：

    ？-Detection（E（RegFormReq，k ））

    后向链接的搜索在这里要被使用。探测模型试图在知识库中找到匹配规则以达到验证目标。只要{RegFormReq，k }在集合requent itemset中并且满足知识库中推理规则的加密规则，对Detection（E（RegFormReq，k }的探测模型最终就返回“真”值。最后，对共谋攻击的预警就会发送给用户。使用同样的方法，用户还可以发送另一个请求：

    ？- Detection（S （<k ，PAN>，Kpb （CA）））

    在该请求中，探测模型需要处理包含{ k ，PAN}和 {Kpb（CA）}的两个FI中的匹配。根据分析得出{ k ，PAN}和 {Kpb（CA）}都在集合frequent itemsets中，并且满足知识库中的公开密钥规则，从而可以断定此项交易隐含着共谋攻击。

    本文给出了一种新颖的数据挖掘模型来探测安全协议中的共谋攻击。特别是每一个参与主体所拥有的消息集合被看作是该模型的交易数据库。从而该探测过程就可以转化为在交易数据库中确定frequent itemsets。通过对实例SET协议中持卡人C证书发起请求协议的分析表明，我们的新方法在分析安全协议中是非常有效的。

    [1]Burrows M.，Abadi M.，Needham R.，“A logic for Authentication”，ACM Transactions on Computer Systems，8（1），pp 18-36，February 1990

    [2]Chengqi Zhang，and Shichao Zhang，“Association Rule Mining： Models and Algorithms”，LNAI 2307，Springer-Verlag，Germany，2002

    [3]Qingfeng Chen，Chengqi Zhang and Shichao Zhang，“ENDL： A Logical Framework for Verifying Secure Transaction Protocols”，Knowledge and Information Systems，7（1），pp 84-109，2005

    [4]Bratko I.，“Prolog Programming for Artificial Intelligence”，Addison-Wesley，1990

    [5]SET Secure Electronic Transaction Specification，Book 1： Business Description，Version1.0，May 31，1997

    收稿日期：1 月 6 日   修改日期：1 月 26 日

    作者简介：刘青（1986－），女，山东聊城人，在读研究生，主要研究领域为密码学与信息安全；龙士工（1967－），男，湖南人，副教授，博士，硕士生导师，主要研究领域为密码学与信息安全。