安全協(xié)議的新邏輯

安全協(xié)議的新邏輯

1新邏輯與串空間模型1.1新邏輯及其應(yīng)用假設(shè)p、q和r是協(xié)議的對象，并且是所有參與協(xié)議的元素的集合。c是一條信道，k是密鑰，x是消息。w（c）是c視道c的集合，r（c）是讀取信道c的主體的集合，c（x）是信道c中的消息x，f表示公式。P|≡X:表示協(xié)議從開始到結(jié)束的整個運(yùn)行過程中P一直相信X.P|～X:表示P在某時發(fā)送了一個包含X的消息,但不能確定它是何時發(fā)送的.P||～X:表示P在本輪協(xié)議中發(fā)送了X.P|?X:表示P對X有仲裁權(quán).P<X:表示P可見X.P<C(X):表示有主體通過信道C發(fā)送了消息X,P可以看到.如果P不能讀信道C,那么P不能識別和理解此消息.P<X|C:表示P通過信道C接收了消息X,只有當(dāng)有某個主體(不是P)通過信道C發(fā)送了消息X,并且P可讀信道C.#(X):表示X是新鮮的.X在當(dāng)前協(xié)議輪之前未被說過.ΡΚ?QP?KQ:表示密鑰K只為P和Q所知.ΚαΡαKP:表示K是P的公鑰,K-1是P的私鑰,K-1只能是P擁有或者P相信的實體擁有.{X}K:表示用K加密X.〈X〉Y:表示X和秘密Y的組合,Y的出現(xiàn)證明了誰發(fā)送了〈X〉Y.P∩x∩Q:表示秘密X只為P和Q所知.(X,Y):表示消息X和消息Y的組合消息.如果φ是一個公式,那么下列表示也是一個公式,P|≡φ:P相信φ為真,并不意味著φ為真.如果φ1和φ2是公式,那么φ1∨φ2、φ1∨φ2和φ1→φ2都是公式.在新邏輯中給出了25條推理規(guī)則用于安全協(xié)議的分析,31條合成規(guī)則用于安全協(xié)議的設(shè)計,使安全協(xié)議的設(shè)計和分析可以在同一中邏輯框架中進(jìn)行.消除了用一種方法來設(shè)計安全協(xié)議而用另一種方法來分析協(xié)議的不一致性.通過這種新邏輯的運(yùn)用,可以將安全協(xié)議的初始條件直接運(yùn)用到安全協(xié)議的分析和設(shè)計中,減少了初始條件的形式化過程,提高了工作效率.有關(guān)新邏輯的推理規(guī)則和合成規(guī)則見文獻(xiàn).1.2randmap安全串(strand)是協(xié)議中的主體可以執(zhí)行的事件序列.對于誠實的主體,該事件序列是由協(xié)議定義好的,由發(fā)送消息的事件和接收消息的事件所組成;對于攻擊者,該事件序列由攻擊者的行為來確定.串空間(strandspace)是誠實的主體串和攻擊者串所組成的集合.束(bundle)是串空間的一個子集,用來表示一個完整的協(xié)議.束是一個有限無環(huán)圖,每個結(jié)點(diǎn)由兩部分組成,即<串名,位置>,其中串名指出該結(jié)點(diǎn)所屬的串的名稱,位置指出該結(jié)點(diǎn)在串中的位置編號.束中有兩種邊,這兩種邊表示了結(jié)點(diǎn)間的因果依賴關(guān)系.第一種邊:〈s,i〉→〈s1,i1〉,表示串s中的第i個結(jié)點(diǎn)發(fā)送消息給串s1中第i1個結(jié)點(diǎn);第二種邊:〈s,i〉?〈s,i+1〉,表示結(jié)點(diǎn)〈s,i〉是結(jié)點(diǎn)〈s,i+1〉的直接前驅(qū).在串空間模型中,協(xié)議的正確性問題可以表示為不同串之間的因果連接關(guān)系.有關(guān)串空間模型的詳細(xì)資料,見文獻(xiàn).2基于principal的s/s轉(zhuǎn)換設(shè)〈B,s,i〉表示束B中的點(diǎn),也就是束B中串s上的第i個結(jié)點(diǎn),則公式j(luò)在〈B,s,i〉為真表示為〈B,s,i〉|=φ.公式φ蘊(yùn)涵公式Ψ表示為φ→Ψ,φ→Ψ在〈B,s,i〉為真表示為〈B,s,i〉|=(φ→Ψ).用principal(s)表示執(zhí)行串s的主體.用r(C)表示可讀信道C的主體集合,用w(C)表示可寫信道C的主體集合.2.1基本句子的含義2.1.1p.dx〈B,s,i〉|=P|≡X當(dāng)且僅當(dāng)在束B的結(jié)點(diǎn)〈s,i〉滿足:(a)principal(s)=P;(b)〈B,s,i〉|=X.2.1.2principalt,l〈B,s,i〉|=P|～X為真當(dāng)且僅當(dāng)束B中或者束B′(B′表示當(dāng)前協(xié)議輪B的前面的某個輪)中存在一個結(jié)點(diǎn)〈t,j〉,滿足:(a)principal(t)≠P,principal(s)=P;(b)〈s,i〉≤〈t,j〉;(c)term(〈t,j〉)=+X,term(〈s,i〉)=-X.2.1.3principal/s計算p〈B,s,i〉|=P||～X為真當(dāng)且僅當(dāng)束B中存在一個結(jié)點(diǎn)〈t,j〉,滿足:(a)principal(t)≠P,principal(s)=P;(b)〈s,i〉≤〈t,j〉;(c)term(〈t,j〉)=+X,term(〈s,i〉)=-X.2.1.4束b中多個結(jié)論〈B,s,i〉|=P|?X為真當(dāng)且僅當(dāng)束B中存在一個結(jié)點(diǎn)〈s,j〉,滿足:(a)principal(s)=P;(b)〈B,s,j〉|=X.2.1.5principalt驅(qū)動〈B,s,i〉|=P□X為真當(dāng)且僅當(dāng)束B中存在一個結(jié)點(diǎn)〈t,j〉,滿足:(a)principal(t)≠P,principal(s)=P;(b)〈t,j〉≤〈s,i〉;(c)term(〈t,j〉)=+M,X?term(〈s,i〉)=-M(也就是X是M的子術(shù)語).2.1.6principal/t〈B,s,i〉|=P□C(X)為真當(dāng)且僅當(dāng)束B中存在一個結(jié)點(diǎn)〈t,j〉,滿足:(a)principal(t)≠P,principal(s)=P;(b)〈t,j〉≤〈s,i〉;(c)term(〈t,j〉)=+X.2.1.7principalt驅(qū)動〈B,s,i〉|=P□X|C為真當(dāng)且僅當(dāng)束B中存在一個結(jié)點(diǎn)〈t,j〉,滿足:(a)principal(t)≠P,principal(s)=P;(b)〈t,j〉≤〈s,i〉;(c)term(〈t,j〉)=+X,P□r(C),term(〈s,i〉)=-X.2.1.8elyoringingintitat3.3.4和4.33.3.35.35.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.555.55.55.55.55.55.55.55.55.555.55.55.55.55.55.55.55.55.55.55.55.55.55.555555555555555.555.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.55.〈B,s,i〉|=#(X)為真當(dāng)且僅當(dāng)束B中存在一個結(jié)點(diǎn)〈t,j〉,滿足:(a)〈t,j〉≤〈s,i〉;(b)X唯一源發(fā)(uniquelyoriginating)于結(jié)點(diǎn)?t,j?.2.1.9ΡΚ?Q?B,s,i?|=ΡΚ?Q?t,j?.2.1.9P?KQ?B,s,i?|=P?KQ為真當(dāng)且僅當(dāng)束B中存在兩個結(jié)點(diǎn)〈t1,j1〉、〈t2,j2〉,滿足:(a)principal(t1)=P,principal(t2)=Q;(b)〈t1,j1〉≤〈s,i〉,〈t2,j2〉≤〈s,i〉;(c)r(CPQ)=w(CPQ)={P,Q}.2.2個表示公式以下這些公理可以從謂詞邏輯和串空間模型中直接得到,證明從略.公理1設(shè)〈B,s,i〉為束B中的一個點(diǎn),φ公式,〈B,s,i〉|=φ,對于束B中的任意一個結(jié)點(diǎn)〈t,j〉,如果〈s,i〉≤〈t,j〉,那么〈B,t,j〉|=φ.公理2設(shè)〈B,s,i〉為束B中的一個點(diǎn),φ、Ψ為公式,如果〈B,s,i〉|=φ并且〈B,s,i〉|=(φ→Ψ),那么〈B,s,i〉|=Ψ.公理3設(shè)〈B,s,i〉為束B中的一個點(diǎn),φ、Ψ為公式,〈B,s,i〉|=(φ∧Ψ)充要條件是〈B,s,i〉|=φ并且〈B,s,i〉|=Ψ.公理4設(shè)〈B,s,i〉為束B中的一個點(diǎn),φ、Ψ為公式,〈B,s,i〉|=(φ∨Ψ)充要條件是〈B,s,i〉|=φ或者〈B,s,i〉|=Ψ.公理5設(shè)〈B,s,i〉為束B中的一個點(diǎn),φ為公式,〈B,s,i〉|=φ和〈B,s,i〉|=(?φ)只有一個成立(?表示公式的否定).2.3在新邏輯中有25條推理規(guī)則,由于篇幅的限制,我們只證明一部分規(guī)則,其它推理規(guī)則可進(jìn)行類似的證明.另外,用于安全協(xié)議設(shè)計的合成規(guī)則是由推理規(guī)則構(gòu)造出來的,所以只要證明了推理規(guī)則即可,相應(yīng)的合成規(guī)則不需要進(jìn)行額外的證明.定理1(接收規(guī)則1)Ρ＜C(X)?Ρ∈r(C)Ρ|≡(Ρ＜X|C),Ρ＜XP＜C(X)?P∈r(C)P|≡(P＜X|C),P＜X證明:由P□C(X)知束B中存在一個結(jié)點(diǎn)〈s,i〉,使得〈B,s,i〉|=P□C(X),也就是在束B中存在一個節(jié)點(diǎn)〈t,j〉,滿足:principal(t)≠P,principal(s)=P(1.1)〈t,j〉≤〈s,i〉(1.2)term(〈t,j〉)=+X(1.3)又因為P∈r(C)(1.4)所以term(〈s,i〉)=-X(1.5)由(1.1)(1.2)(1.3)(1.4)(1.5)得到:〈B,s,i〉|=P|≡P□X|C(1.6)由X?X(也就是X是X的子術(shù)語)和(1.6)得到:〈B,s,i〉|=P□X(1.7)由公理3和(1.6)(1.7)可得:〈B,s,i〉|=(P|≡P□X|C)∧(P□X)所以Ρ＜C(X)?Ρ∈r(C)Ρ|≡(Ρ＜X|C),Ρ＜XP＜C(X)?P∈r(C)P|≡(P＜X|C),P＜X成立.定理2(接收規(guī)則2)Ρ＜(X,Y)Ρ＜X,Ρ＜Y證明:由P□(X,Y)知束B中存在一個節(jié)點(diǎn)〈s,i〉,使得〈B,s,i〉|=P□(X,Y)也就是在束B中存在一個節(jié)點(diǎn)〈t,j〉,滿足:principal(t)≠P,principal(s)=P(2.1)〈t,j〉≤〈s,i〉(2.2)term(〈t,j〉)=+M,term(〈s,i〉)=-M,(X,Y)?M(2.3)因為X?(X,Y)?M,所以term(〈s,i〉)=-X(2.4)因為X?X和(2.1)(2.2)(2.3)(2.4),所以〈B,s,i〉|=P□X(2.5)因為Y?(X,Y)?M,所以term(〈s,i〉)=-Y(2.6)因為Y?Y和(2.1)(2.2)(2.3)(2.6),所以〈B,s,i〉|=P□Y(2.7)由(2.5)(2.7)和公理3得到:〈B,s,i〉|=(P□X)∧(P□Y)所以Ρ＜(X,Y)Ρ＜X,Ρ＜Y成立.定理3(發(fā)送規(guī)則1)Ρ|≡(w(C)=W)Ρ|≡((Ρ＜X|C)→∨?Qi(Qi∈W\{Ρ})(Qi|∶x))證明:可以把該規(guī)則進(jìn)行等價變換為:(P|≡(w(C)=W)∧(P□X|C))→P|≡(∨(“Qi(Qi∈W\P)(Qi|～X))),只要證明該公式成立即可.由P□X|C可知,在束B中存在一個節(jié)點(diǎn)〈s,i〉使得,〈B,s,i〉|=P□X|C,也就是在束B中存在一個節(jié)點(diǎn)〈t,j〉,滿足:principal(t)≠P,principal(s)=P(3.1)〈t,j〉≤〈s,i〉(3.2)term(〈t,j〉)=+X,P∈r(C),term(〈s,i〉)=-X(3.3)由w(C)=W和(3.1)(3.2)(3.3)得到:principal(t)=W\P(3.4)由(3.4)可知Qk∈W\P,k=1,2,…,使得principal(t)=Qk(3.5)由(3.3)(3.5)可得:〈B,s,i〉|=∨(“Qk(Qk∈W\P)(Qk|～X))(3.6)由(3.6)和(3.1)可得:〈B,s,i〉|=(P|≡∨(“Qk(Qk∈W\P)(Qk|～X)))(3.7)所以(P|≡(w(C)=W)∧(P□X|C))→P|≡(∨(?Qi(Qi∈W\P)(Qi|～X)))成立,也就是Ρ|≡(w(C)=W)Ρ|≡((Ρ＜X|C)→∨?Qi(Qi∈W\{Ρ})(Qi|∶X))成立.定理4(發(fā)送規(guī)則2)Ρ|≡(Q|∶(X,Y))Ρ|≡(Q|∶X),Ρ|≡(Q|∶Y))證明:由P|≡Q|～(X,Y)可知在束B中存在一個節(jié)點(diǎn)〈s,i〉,滿足principal(s)=P(4.1)〈B,s,i〉|=(Q|～(X,Y))(4.2)因為X?(X,Y),所以〈B,s,i〉|=(Q|～X)(4.3)又因為Y?(X,Y),所以〈B,s,i〉|=(Q|～Y)(4.4)由(4.3)(4.4)和公理3可得:〈B,s,i〉|=(Q|～X)∧(Q|～Y)(4.5)由(4.1)(4.5)可得:〈B,s,i〉|=(P|≡(Q|～X))∧(P|≡(Q|～Y))所以Ρ|≡(Q|∶(X,Y))Ρ|≡(Q|∶X,Ρ|≡(Q|∶Y))成立.定理5(新鮮性規(guī)則1)Ρ|≡(Q|∶X),Ρ|≡#(X)Ρ|≡(Q||∶X)證明:由P|≡(Q|～X)可知在束B中存在一個節(jié)點(diǎn)〈s,i〉,滿足〈B,s,i〉|=(Q|～X),或者在束B′中存在一個結(jié)點(diǎn)〈t,j〉,滿足〈B,t,j〉|=(Q|～X),這里〈t,j〉≤〈s,i〉.因為P|≡#(X),所以只可能是〈B,s,i〉|=(Q|～X)成立,由#(X)馬上可得〈B,s,i〉|=(Q||～X),因為principal(s)=P,所以〈B,s,i〉|=P|≡(Q||～X)成立.因此Ρ|≡(Q|∶X),Ρ|≡#(X)Ρ|≡(Q||∶X)成立.定理6(新鮮性規(guī)則2)Ρ|≡#(X)Ρ|≡#(X,Y)證明:由P|≡#(X)可知在束B中存在一個節(jié)點(diǎn)〈s,i〉,滿足〈B,s,i〉|=#(X),也就是束B中存在一個結(jié)點(diǎn)〈t,j〉,滿足:〈t,j〉≤〈s,i〉(6.1)X唯一源發(fā)(uniquelyoriginating)于結(jié)點(diǎn)〈t,j〉(6.2)由X?(X,Y)和(6.2)得到〈B,s,i〉|=#(X,Y)