安全定位协议的UC模型

张俊伟，马建峰，杨超

（西安电子科技大学 计算机学院，陕西 西安 710071）

1 引言

与传统的密码学不同，基于位置的密码学[1]将用户的物理位置信息作为该用户的唯一一个凭证信息。典型应用如基于位置的秘密通信、基于位置的认证/签名、基于位置的接入控制等。

目前，针对基于位置密码学的研究主要集中在安全定位方面。在无线安全领域，定位技术已经有了相当多的研究成果。定位技术的主要目标是测量并获得某个设备的物理地址。著名的全球定位系统（GPS）就是一种定位技术，雷达也是一种定位技术。除此之外，还有很多其他的定位技术，它们进行定位的实际方法是基于消息响应时间的技术。然而，之前的安全定位协议都不能抵御多个敌手的共谋攻击（collusion attack）。换句话说，这些定位方法都不是可证明安全的。文献[1]研究了安全定位中共谋攻击的问题，并在Vanilla Model下提出了一个安全定位协议，但该协议仅仅能够抵御2个敌手的共谋攻击，并不能抵御3个或者更多敌手的共谋攻击。

文献[2]首次在BRM（bounded retrieval model）模型[3]下研究了安全定位和基于位置的密钥交换协议。设计的2个密钥交换协议中，一个是计算条件下安全的，另一个是信息论安全的。文献[4]研究了基于位置的量子密码学，利用量子密码学构造了基于位置的安全定位、密钥交换以及认证协议。然而，这些研究并没有给出基于位置密码协议的组合安全模型，因此，设计的协议无法保证在组合环境下协议的安全性。

由Canetti提出的通用可组合框架（UC框架，universally composable framework）[5]可以保证协议的通用可组合安全，即在UC框架下证明安全的协议，在与其他协议并发运行的情况下，或者作为一个系统的组件时，仍能保证协议的安全性。

理想函数是UC框架中非常重要的概念，它扮演着一个不可攻陷的可信第三方的角色，能够完成协议所执行的特定功能。目前，已经定义了多个最基本的理想函数，如认证消息传输 FAUTH、密钥交换FKE、公钥加解密FPKE、签名FSIG、承诺FCOM、零知识证明FZK、不经意传输FOT[6]、基于一次签名（FOTS）的广播认证（FBAUTH）[7]和可信网络连接FTNC[8]等。

在UC框架下设计协议的困难所在和核心内容就在于形式化和抽象一个完美的并且可以安全实现的理想函数。然而，现有的UC框架没有基于位置密码学的理想函数，缺乏对基于位置密码学的支持，无法直接用于基于位置密码协议的分析与设计。

本文在UC框架下提出了安全定位协议的可证明安全模型。针对安全定位的安全需求，设计了安全定位的理想函数 FSP。同时，针对基于位置密码学的前提假设模型——BRM 模型，提出了满足BRM模型性质的理想函数FBRM。针对安全定位理想函数的实现问题，以 Chandran等设计的 1-维空间的安全定位协议为例，证明了该协议在 FBRM-混合模型下能安全实现安全定位的理想函数FSP。

2 预备知识

2.1 UC框架

UC框架如图1所示。首先，UC框架定义了现实环境。现实环境描述协议的真实运行情况，其中所有参与方在真实敌手攻击A存在的环境下运行真实协议。其次，UC框架定义了理想环境用来描述密码协议的理想运行。在理想环境下，存在虚拟参与方，理想敌手S和理想函数F。参与方之间以及敌手S与参与方不直接通信；所有参与方和敌手S均与理想函数交互。理想函数本质上是一个不可攻陷的可信角色，用来完成协议所需的理想运行和功能。在UC的安全框架中，环境Z模拟协议运行的整个外部环境（包括其他并行的协议、攻击者等等），Z可以与所有的参与者以及攻击者A和S直接通信，Z不允许直接访问理想函数F。

图1 UC框架

定义1 UC仿真[5]:协议π能够UC仿真理想函数F当且仅当对于任意真实敌手A，存在理想敌手 S，使得任意环境 Z，至多以一个可忽略的概率来区分:存在A及协议π的现实环境和存在S及理想函数F的理想环境。如果协议π能够UC仿真理想函数F，就称协议π在UC框架下安全实现了理想函数F，也称协议π是UC安全的。

定理 1 组合定理[5]:如果协议 ρ安全实现理想函数F且π是F-混合模型[5]下的协议，那么协议πρ/F（用协议ρ替换协议π中的理想函数F所得到的组合协议）UC仿真F-混合模型下的协议π。特别地，如果协议π在F-混合模型下安全实现理想函数G，那么协议πρ/F也安全实现理想函数G。

通常，复杂的协议由多个子协议构成，每个子协议都可以实现某个安全任务。根据组合定理，利用UC安全的协议可以安全构建一个更为复杂的协议，从而实现指定的任务，并保证相应的安全属性。

2.2 BSM模型和BRM模型

BSM模型[9]（bounded storage model）假设参与方（包括敌手）能存储信息量存在一个上限。假设存在一个具有很高的最小熵（min-entropy）的信息串，那么敌手可以存储这个信息串的一个任意函数，只要这个函数输出的长度不超过敌手存储的上限。

BRM 模型[3]假设参与方可以存取具有很高最小熵的信息串，而敌手仅仅能提取这个信息串的一部分。在基于位置密码学中，假定验证者(verifiers)可以广播具有高的最小熵的信息串，那么当这些信息高速通过敌手的时候，敌手只能提取这些信息中有限的一部分。假设敌人不能提取全部信息主要从下面两方面考虑:1) 信息都是高速传输的(接近光速)；2) 验证者可以有多个具有不同频率的消息源广播信息。

BRM模型具有如下性质。

1) 验证者拥有一个可以生成具有高最小熵信息串的 reverse block entropy source。令最小熵为(δ+β)n, 其中n为信息串的长度。拥有reverse block entropy source，意味着验证者自身可以生成并发送具有高最小熵的信息串。

2) 当这些信息串高速经过敌手时，敌手能够提取的信息量存在一个上限 βn。敌手可以提取这个信息串的任意函数，只要这个函数的输出长度≤βn。提取上限 βn可以是最小熵(δ+β)n的任意部分。

2.3 BSM熵生成器

定义2 令存储率为β，最小熵率为α。EG:{0,1}n×{0, 1}r→ {0, 1}t是 (ε, ψ)-安全的BSM 熵生成器（BSM entropy generators），当且仅当, 对于{0,1}n上任意的αn-source的X，对于任意A:{0, 1}n→{0, 1}βn，随机变量(EG(X, K), A(X), K) 对(W, A(X), K)是ε-close的，其中KR→{0, 1}r且W是ψ-source的。

根据(ε, ψ)-安全的 BSM EG 的定义[2]可得，对于任意算法F，给定A(X)和K，算法F(A(X), K)能正确计算出EG(X, K)的最大概率为ε+2-ψ。在安全参数为 κ的情况下，如果 r≥(2/δ)κlogn，那么 ε+2-ψ是可忽略的。

关于BSM模型、BRM模型、BSM EG以及其中的ψ-source和ε-close等概念的详细内容，请参阅文献[2]。

3 理想函数

3.1 安全定位理想函数FSP

假设存在一个位于位置 p证明者（prover）声称其位于p’，当验证者（verifier）需要对证明者安全定位时，安全定位理想函数能够保证，证明者正确通过验证者的安全定位验证当且仅当p = p’。理想函数FSP如下所示。

理想函数FSP

d-维空间。

验证者 Ver = {V1,V2,…,Vn}分别在位置 pos1,pos2,…, posn，其中 posi= Pos (Vi)。

敌手 Adv={A1,A2,…,Ak}分别在位置 apos1,apos2,…, aposk，其中 aposi= Pos(Ai)。

Initial

当从Prov 收到(Position Initialize, sid, Prov):

令Pos(sid, Prov) = ⊥, 发送(Position Initialize,sid, Prov) 给敌手。

当从敌手收到(Position Initialize, sid, Prov, p):

如果 p = posi(1≤i≤n) 或者 p = aposj(1≤j≤k) 或者 p不在 Ver所构成的封闭空间内，发送POSITION_INVALID给敌手。

否则，令p = Pos(sid, Prov)，并输出(Position Initialized, sid, Prov, p)。

Secure Positioning

当从 Ver 收到(Secure Position, sid, Ver, Prov, p):

如果p = Pos(sid, Prov), 发送(Secure Position,sid, Ver, Prov, p)给敌手。

否则，忽略这个消息。

当从敌手收到(Secure Positioned, sid, Ver, Prov,p’, f)，其中 f ∈{Accept, Reject}:

如果 Pos (sid, Prov)≠p’，那么输出(Secure Positioned, sid, Ver, Prov, p’, Reject) 给 Ver；

否则, 输出(Secure Positioned, sid, Ver, Prov, p’,Accept) 给 Ver。

证明者位置的无关性:在理想函数FSP初始化时，证明者的位置由敌手决定。这说明，安全定位协议的安全性不依赖证明者所处位置。

证明者位置的非机密性:由于证明者的位置在初始化时由敌手决定，因此，理想函数FSP不能保证证明者位置信息的机密性。

敌手攻击行为:敌手可以得到无线信道中的消息，并伪装成合法用户发送虚假消息。但敌手不能完全阻止无线信道中的信息。

抗敌手共谋攻击:敌手 Adv是多个敌手{A1,A2,…, Ak}组成的集合，即理想函数FSP是在多个敌手共谋情况下的运行。因此，理想函数FSP能够抵御多个敌手共谋攻击。

定位的安全性:只有当p’ = p = Pos(sid, Prov)时，理想函数 FSP才会输出(Secure Positioned, sid,Ver, Prov, p’, Accept) 给 Ver。

3.2 BRM理想函数FBRM

理想函数FBRM保证:如果验证者（verifier）发送具有高的最小熵的信息串，那么当这些信息高速通过敌手的时候，敌手只能提取这些信息中有限的一部分。理想函数FBRM如下所示。

理想函数FBRM

当从P收到(Broadcast BRMessage, sid, X)，如果 X 的最小熵为(δ + β) n, 则

1) 令 Xi= X，i = i +1；

2) 发送(Broadcasted BRMessage, sid, P, X)给所有参与方（除了敌手）；

3) 发送(Broadcasted BRMessage, sid, P, i)给敌手。

当从P收到(Send BRMessage, sid, Q, X)，如果X 的最小熵为(δ + β) n, 则

1) 令 Xi= X，i = i +1；

2) 发送(Sent BRMessage, sid, P, Q, X)给 Q；

3) 发送(Sent BRMessage, sid, P, Q, i)给敌手。

当从敌手收到(Retrieve BRMessage, sid, i, F):

1) 计算 F(Xi)；

2) 如果F(Xi)的信息量没有超过上限(i.e.≤βn)，则令f = F(Xi)；否则，将F(Xi)截短到适当的长度并将其设为f；

3) 发送(Retrieved BRMessage, sid, i, f)给敌手。

消息序号i:FBRM对每个要发送的最小熵为(δ +β) n的信息串用i进行编号。敌手也可以通过编号使用(Retrieve BRMessage, sid, i, F)来提取该信息串的相关信息。

单播:FBRM使用(Send BRMessage, sid, Q, X)来发送信息串X。

广播:FBRM使用(Broadcast BRMessage, sid, X)来广播信息串X。

BRM:当敌手发送请求(Retrieve BRMessage,sid, i, F)来提取第i个信息串的信息时，仅能够提取出上限为βn的信息量。

4 实现理想函数FSP

本节以 1-维空间下的安全定位协议（记为πSP1d）[2]为例，证明协议 πSP1d在 FBRM-混合模型下可以安全实现理想函数 FSP。首先，给出在 FBRM-混合模型下协议πSP1d的形式化描述。其次，证明协议πSP1d在FBRM-混合模型下满足UC安全性。

4.1 安全定位协议πSP1d

在 FBRM-混合模型下，1-维空间的安全定位协议πSP1d如下所示。

协议πSP1d

令βn为敌手提取信息的上限。验证者V1拥有最小熵为(δ+β)n 的信息串 X1, X2, …, 其中 Xi∈{0,1}n。(ε, ψ)-安全的 BSM 熵生成器 EG:{0, 1}n× {0,1}l→ {0, 1}m。令 l≥(2/δ)κlog(n)，则 ε+2-ψ在安全参数κ下是可忽略的。

Initial

当从Prov收到(Position Initialize, sid, Prov):

1) 令 p = Pos(sid, Prov)；

2) 如果 p = posi(1≤i≤n) 或者 p = aposj(1≤j≤k), 那么令 p = POSITION_INVALID；

3) 输出(Position Initialized, sid, Prov, p)。

Secure Positioning

当Ver收到(Secure Position, sid, Ver, Prov, p):

1) V1从{0, 1}l中随机选择K并通过秘密信道发送(Send, sid, V1, V2, K)给 V2；

2) 令 t和 t’是无线电波分别从 V1和 V2到达 p的时间，V1利用reverse block entropy source生成并在(T−t)时刻发送(Send, sid, V1, Prov, X)给 FBRM, 其中，T为X到达位置p的时刻，X的最小熵为(α+β)n。同时，V1计算EG(X, K)；

3) 在(T−t’)时刻，V2发送(Send, sid, V2, Prov, K)给Prov，使得K在T时刻在位置p与X相遇；

4) 在T时刻, Prov收到(Sent, sid, V2, Prov, K)，并从FBRM收到(Sent, sid, V1, Prov, X)，计算y = EG(X,K)，并发送(Send, sid, Prov, V1, y)给 V1；

5) 当 V1从 p 收到(Send, sid, Prov, V1, y’)时，V1验证是否在(T+t)时刻收到y’，且y’是否等于EG(X,K)。如果是，输出(Secure Positioned, sid, Ver, Prov, p,Accept)；否则，输出(Secure Positioned, sid, Ver, Prov,p, Reject)。

4.2 协议πSP1d的安全性分析

定理 2 如果 X 的最小熵为(δ + β)n，βn 为敌手提取信息的上限，EG是(ε, ψ)-安全的BSM熵生成器，那么，协议πSP1d在FBRM-混合模型下安全实现理想函数FSP。

证明 令A 为现实敌手。构造理想敌手S，使得对于任意环境Z只能以可忽略的概率区分:协议πSP1d及A交互的现实环境（记为REAL）和理想函数FSP及S交互的理想环境（记为IDEAL），记为IDEAL≈REAL（表示REAL和IDEAL不可区分）。

1）构造S

敌手S运行一个敌手A的仿真副本。因此，S通常被称为仿真器（simulator）。S将Z的所有输入发送给A。A 的所有输出都作为S的输出。

敌手S运行如下。

①当从FSP收到(Position Initialize, sid, Prov), S将(Position Initialize, sid, Prov)作为输入为A运行πSP1d的一个副本。然后将从A收到的响应(Position Initialized, sid, Prov, p)发送给 FSP。

②当 S从 FSP收到(Secure Position, sid, Ver,Prov, p), S 以(Secure Position, sid, Ver, Prov, p)为输入运行πSP1d的副本。

③当V1通过秘密信道发送(Send, sid, V1, V2, K)给V2时，S仿真从V1到V2通过秘密信道发送的消息(Send, sid, V1, V2, K)。

④当V1在(T-t)时刻利用FBRM发送(Send, sid, V1,Prov, X)给Prov，S在(T-t)时刻利用FBRM仿真从V1到Prov的消息(Send, sid, V1, Prov, X)。

⑤当 V2在(T-t’) 时刻发送(Send, sid, V2, Prov, K)给 Prov，S在(T-t’)时刻仿真从 V2到 Prov的消息(Send, sid, V2, Prov, K)。

⑥当Prov在T时刻发送(Send, sid, Prov, V1, y)给V1，S在T时刻仿真从Prov到V1的消息(Send, sid,Prov, V1, y)。

⑦当 πSP1d的副本输出(Secure Positioned, sid,Ver, Prov, p’, f)，其中 f ∈{Accept, Reject}，S 发送(Secure Positioned, sid, Ver, Prov, p’, f)给 FSP。

2) IDEAL和REAL不可区分

事件E1:πSP1d的副本输出(Secure Positioned, sid,Ver, Prov, p’, Accept), 其中 Pos (sid, Prov) ≠ p’。

事件E2:πSP1d的副本输出(Secure Positioned, sid,Ver, Prov, p’, Reject), 其中 Pos (sid, Prov) = p’。

根据事件 E1和 E2，按照下列 3种情况分别讨论。

1) E1和E2均不发生。当E1和E2事件都不发生的情况下，上述仿真是完美的，即IDEAL ≈ REAL；

2) E1发生。E1事件发生的概率是可忽略的:假设事件E1以不可忽略的概率发生，那么，就存在一个敌手（不在位置 p），它能够以不可忽略的概率在(T+t)时刻将正确的y发送给V1。在T时刻，X和K在位置p。假设存在V1和p之间存在g个敌手，这些敌手从 X中能分别提取 S1,S2,…,Sg。令 S=S1∪S2∪…∪Sg，显然，|S|≤βn。由于 S是 V1和 p之间信息的集合，敌手没有在位置p，且在T时刻任何P和V2之间关于X的信息也不能在(t + T)时刻到达V1，因此，如果敌手能够以不可忽略的概率在(T+t)时刻将正确的y发送给V1，那就意味着敌手存在一个算法 A能够以不可忽略的概率正确计算 y=A(S, K)。但是，根据BSM EG的性质，给定S和K，敌手能正确计算 y的最大概率为 ε+2−ψ，其中，ε+2−ψ是可忽略的。因此，这与定义2相矛盾，假设不成立。即事件E1只能以可忽略的概率发生。

3) E2发生。E2事件不会发生:由于敌手在无线环境下不具备阻止消息的能力，根据协议 πSP1d可知，如果Prov在位置p，那么，Prov在T时刻会收到X和K，计算正确的y，并将其发送给V1。V1会在(T+t)时刻收到正确的y并成功通过验证。即E2事件不会发生。

综上，环境Z只能以可忽略的概率区分REAL和IDEAL，即IDEAL ≈ REAL。定理2得证。

5 安全定位协议UC模型的应用

本文提出的安全定位协议UC模型有以下2种应用方法。

1) 定位协议的安全性分析

利用安全定位协议UC模型，可以对定位的安全性进行形式化分析。如果一个定位协议可以安全实现理想函数 FSP，那么该协议就满足 UC安全，具有可组合安全性，即在任意环境下运行该协议，都能确保其安全性。

2) 定位协议的模块化设计

基于安全定位协议 UC模型，结合UC组合安全理论，可以为协议的模块化设计提供理论支持。利用UC框架中混合模型，既可以借助其他子协议或理想函数（如 FBRM），设计满足 UC安全的定位协议，又可以将 UC安全的定位协议作为子协议，与其他协议组合，实现组合协议的UC安全。

6 结束语

本文在 UC框架下提出了安全定位的可组合安全模型。根据安全定位协议的特点，设计了安全定位的理想函数FSP。同时，设计了BRM模型的理想函数FBRM。最后，证明了1-维空间的安全定位协议 πSP1d在 FBRM-混合模型下可以安全实现理想函数FSP。

[1]CHIANG J T, HAAS J J, HU Y C.Secure and precise location verification using distance bounding and simultaneous multilateration[A].WISEC, ACM[C].2009.181-192.

[2]CHANDRAN N, GOYAL V, MORIARTY R, et al.Position-based cryptography[A].Cryptology-CRYPTO 2009[C].2009.391-407.

[3]DZIEMBOWSKI S, PIETRZAK K.Intrusion-resilient secret sharing[A].FOCS '07:Proceedings of the 48th Annual IEEE Foundations of Computer Science[C].2007.

[4]BUHRMAN H, CHANDRAN N, FEHR S, et al.Position-based quantum cryptography:impossibility and constructions[EB/OL].http://eprint.iacr.org/2010/275.pdf,2010.

[5]CANETTI R.Universally composable security:a new paradigm for cryptographic protocols[EB/OL].http://eprint.iacr.org/2000/067,2000.

[6]李凤华, 冯涛, 马建峰.基于 VSPH的UC不经意传输协议[J].通信学报, 2007, 28(7):28-34.LI F H, FENG T, MA J F.Universally composable oblivious transfer protocol based on VSPH[J].Journal on Communications, 2007,28(7):28-34.

[7]张俊伟, 马建峰, 杨力.UC 安全的基于一次签名的广播认证[J].通信学报, 2010, 31(5):31-36.ZHANG J W, MA J F, YANG L.UC secure one-time signature based broadcast authentication[J].Journal on Communications, 2010, 31(5):31-36.

[8]ZHANG J W, MA J F, MOON S J.Universally composable secure TNC model and EAP-TNC protocol in IF-T[J].Science China Information Sciences, 2010,53(3):465-482.

[9]MAURER U M.Conditionally-perfect secrecy and a provebly-secure randomized cipher [J].Journal of Cryptology, 1992, 5(1):53-66.