安全定位協議的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.