ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.213-221



ȫЭ֤߼
˶ӱ桡ҡׯ
ժҪһ֤ȫЭ֮ȫʵķǵ̬߼.ϢȫضҪ,һܡܡǩ֤ԿѧйصĹ,˵һ߼֤ȫЭ鷽Ӧ,Ҫһ.
ؼʣϢȫ,Э֤,̬߼,ǵ߼.
ţTP309
The Verification Logic for Secure Protocols
BAI ShuoSUI Li-yingCHEN Qing-fengFU YanZHUANG Chao
(National Research Center for Intelligent Computing Systems,Beijing,100080)
AbstractIn this paper,a non-monotonic dynamic logic that verifies properties of security protocols is introduced.In accordance with the specific requirement of information security,it provides axioms and inference rules about various cryptographic operations such as encryption,decryption,signature,authentication and key assignment.Several instances are given to illustrate its applications in security protocol verification.Open problems for further study are also discussed.
Key wordsInformation security,protocol verification,dynamic logic,non-monotonic logic.
ǰ,Ϣһ緶ΧĴ.InternetΪĹȳÿһ͸.һ,ϢȫΪѧ͹ҵ繲ͬעĹؼ.һ˵,ϢȫʿơͨŰȫϢ.ڷʿƺͨŰȫ,ԷǽΪҪֶΡԾΪIntranetԼͨΪҪֶΡԹ˽ΪExtranetѾʵ.ϵĸ,ΪϼͨŶƶİȫЭϢȫе򷢻Ҫ.
һȫЭڳ̨Ժ,ҪӶ෽䰲ȫʽ֤.ֶ֤ж,,ֱ۵ķʵʹֶεĲ,ʽ߼.,ֶεܺͶԵձü,ѧһ,ҲԹҵһӰ.
֪,ȫЭɲͨŵĸȷĲһͨŶɵ.ЩͨŶʵͨű,һЩѧ任㷨ʵʩ.Щѧ任㷨,ѧṩ˴ﵽһ̶ȵͨŰȫĻ.׿㷨ѧݲ̸,ԴﵽͨŰȫĻ߼ĲϽ,Ͳ˰ȫЭ֤ʽ.ʽ㷨İȫǿȵǰ,Ժ㷨ѧϸЭİȫ,ͨʽ߼ѰҰȫЭ©.,Ϣȫһܵӵо.
Ϊ˶԰ȫЭʽ߼,ȱ԰ȫЭ漰ĸֶ״̬͹ϵ,ʵ塢Ϣ֪ʶ״̬ιϵȽ߼.һʮֹؼ.ͬʽ֮ĲҲ߼Ĳͬ.߼ʹڰȫʵܹ㷨ѧϸ޹صĲϽ,Աֱⰲȫĺ,չ߼.
ǰڰȫЭ֤߼ҪĹ,Burrows,AbadiNeedhamBAN߼1ڷȫЭ߼.BAN߼и򵥡⡢Ӧõص,ӦԷְȫЭĳЩײ©.BAN߼ޣĳЩЭ,BAN߼ķǴģ,ûпߵĴ.BAN߼軷ܶʧϢӰ,ڷֲʽ,Ǻ׷,BAN߼Ĳ֮,߼޷ȷܵĶջǱܵ.߼,GNY2,UEPS3ݵͼץסÿϸ,˷,Щ߼̫ӶҲӦ.Ϊһ,AUTLOG4߼Ӧ˶.BAN߼Ļ֮һЩ򵥵,ˡrecognizeν,ˡseeĺ,ģһߵ.Щ䲢δʹ߼ӻ,ͬʱܷһЩBAN߼ܴЭ.AUTLOGδӸϽ,Ȼֻѡ:GNYȸ߼еЭ,ΪÿһЭӦļ߼з.
KaliarڡAccountability in Electronic Commerce Protocols5ֱԵһڷҪԡİȫЭ¿.˷߼ֻڷԿЭһЩ֤Э,漰еĸ,ǿ˽е˫ԶԷ,ԼϢĲɷ.KailarķBAN߼Ȼ.
Ϊ,߼Ͽ,ͨŰȫж̬Ժͷǵ.νָ̬,ȫЭ鱾һ,,Ӧ붯̬߼Ļ,ͨԶǰͺбʾհȫЭΪе.νǵָ,ЩȫΪڽеǰĿǰɵĶ֤Ĭ,һǰ߶,Щʵĳǻı仯仯,,Ӧǵ߼Ļ,ͨʧܼ񶨡ԭΪĲ,֤ȫЭķǵ.,Ҫһְͨһ߼Ͷ̬߼ǵ߼ۺ߼.
ĵĵ1ڽİȫ߼.2ڽĹͱݵı׼ʽ.3ڸ3ȫЭ֤ʾ.4ڶԱܽᲢдһо.
1 ȫ߼
ڴ߼Ƕ۰ȫʱ,ҪǶ漰߼,㷨ѧϸйصķ,ӳȫ߼ʵʵķ.,¸֪ʶ״̬ιϵ氲ȫЭִвչĸֱ仯ȵ.ڶ԰ȫ߼,ǻ漰һЩ.
ʵ ʵǲμͨŵ,շϢмܡܡǩ֤ͷԿ,ҲǶϢ֪Ͷʵε.,һЩʵԿĹռҪĵλ,ν֤Ȩ֣certificate authorities,CA.֤ȨͨǩϽͨŷΧȷϲμͨŵʵĹԿ,Ӷȷ乫ԿĺϷ.Ȼ,һ걸ĹԿṹ,CAĺϷԻҪ߲Ȩֵȷ.Ľṹ,ǽ,ֻΨһCA.
Ϣ ϢͨŻĶ,ҲѧĶ.ȫͨŵȫʹĳЩϢø֪֪,֪˲֪.Կѧĺ,߼Ĺ۵㿴,ԿҲϢ,ҲԱԿܲ.ضʵϵԿ硰AǩԿ,Bݽ˽Կȣ,߼ϿԿصԿڸʵıʽ.˵,ҪЭִ,ʵԿ仯.֤,ʵҲϢ̬.ѧĽģҲΪϢ.ʵΪϢʵͬʽʾ,ޱҪö߼Զ߽.
 ͨŻĹɵλ.ǹĵĻֻ:ɣgenerateͷͣsend.Դϳɶ.ȫЭһЩضĶУԿܡԿܡǩѧǰһЩϢӳΪһЩϢѧ任,߼һЩĺʾ,ڡķ룩.еǸı䵱µʵ֪ʶ״̬Լʵ֮ιϵ.
֪ʶ״̬ ֪ʶ״̬ʵϢ֮һֹϵ,֪ϵ.ڱдһֻԵġ֪ϵ.˵,ΪЭִ,һʵ塰֪Ϣκζķϳ,Ϊ֪.
ιϵ ˵ιϵָǩ֤ιϵ,һǩϢ֤ԱΪ:1 ȷϵǩ;2 յϢȷ緢ʱһ,ûоκδ۸.
,ʽʾ,͹ǵ߼NDLnon-monotonic dynamic logic﷨.
NDLԹɰ峣ԪʡνʡԺԱʾ6ֳɷ.
峣Ԫ ôдĸ±꣩ʾ.CAһĸ峣Ԫ,ʾ֤Ȩ.
 NDLĺŰЩʾܡǩѧ͹Կӳϵ:
E(m,k)kΪԿmܵĽ;
S(m,k)kΪĹԿԿ֮һmܵĽ;
H(m)mϢժ;
Kpb(x)xݽԿ;
Kpv(x)xݽ˽Կ;
Spb(x)xǩԿ;
Spv(x)xǩ˽Կ;
m1,...,mnϢm1,...,mnɵġΪһϢ.
ν ,ֱʾص֪ʶ״̬ιϵ:
Know(x,m)x֪m;
Auth(x,y,m)xȷmΪyҷδ޸.
 :
Generate(x,m)xϢm;
Send(x,y,m)xym.
пɵݹض:1 Ƕ;2 ,Ƕ,ҲǶ.Эһֶ.
 ԵһʽΪ
PQ,
P,QΪʽ,Ϊ.Աʾ,P,ִжЦ,ҶִϺ,Q.
Աʾ һЩҪĹ̶ڰȫЭжظ,ȷĸ.Щ̶ĺ,һЩԱʾд.ڱĵ߼ϵͳ,Ƕ4Աʾ:
Sign(x,m)=m,S(H(m),Spv(x)),xϢmĴǩ;
So(x,m)=S(H(m),Spv(x)),xϢmǩ;
CertK(x)=Sign(CA,x,Kpb(x)),xݽԿ֤;
CertS(x)=Sign(CA,x,Spb(x)),xǩԿ֤.
,ԿǵľӦ.
2  
ɹʽ.Сһ.
2.1  
(1) ܹ
1-1 Know(x,m)Know(x,k)Know(x,E(m,k))
1-2 Know(x,m)Know(x,Kpb(y))Know(x,S(m,Kpb(y)))
(2) Կ乫
2-1 Know(x,Kpb(CA))
2-2 Know(x,Spb(CA))
2-3 Know(x,Kpv(x))
2-4 Know(x,Spv(x))
(3) ܹ
3-1 Know(x,k)Know(x,E(m,k))Know(x,m)
3-2 Know(x,Kpv(y))Know(x,S(m,Kpb(y)))Know(x,m)
(4) ǩ
4-1 Know(x,m)Know(x,H(m))
4-2 Know(x,m)Know(x,Spv(y))Know(x,S(H(m),Spv(y)))
(5) ֤
5-1 Know(x,m)Know(x,S(H(m),Spv(y)))Know(x,Spb(y))Auth(x,y,m)
5-2 Know(x,m)Auth(x,y,H(m))Auth(x,y,m)
(6) ֺϹ
6-1 Know(x,m1,...,mn)Know(x,m1)...Know(x,mn)
6-2 Auth(x,y,m1,...,mn)Auth(x,y,m1)...Auth(x,y,mn)
ϹԱʾĺSo()Sign()Ķ,֤ԺõıȽʵõĶ.
1.Know(x,m)Know(x,So(y,m))Know(x,Spb(y))Auth(x,y,m).
֤:
(1)Know(x,m)ǰ
(2)Know(x,So(y,m))ǰ
(3)Know(x,Spb(y))ǰ
(4)Know(x,S(H(m),Spv(y)))(2)۶
(5)Auth(x,y,m)(1)(3)(4)5-1
(6) Know(x,m)Know(x,So(y,m))Know(x,Spb(y))Auth(x,y,m)(1)(2)(3)(5)ۡ+

1ʵǹ5-1һȼ۵д,ʮȻ.
2.Know(x,Sign(y,m))Know(x,Spb(y))Auth(x,y,m).
֤:
(1)Know(x,Sign(y,m))ǰ
(2)Know(x,Spb(y))ǰ
(3)Know(x,m,S(H(m),Spv(y)))۶
(4)Know(x,m)(3)6-1
(5)Know(x,S(H(m),Spv(y)))(3)6-1
(6)Know(x,So(y,m))(5)۶
(7)Auth(x,y,m)(2)(4)(6)۶1
(8)Know(x,Sign(y,m))Know(x,Kpb(y))Auth(x,y,m)(1)(2)(7)ۡ+

2ӳ֤ĸ͵ʽ.
2.2  
(R-1) Ϣй¶
Know(x,m)Send(x,y,m)Know(z,m).
˼,ĵϢܿɱ.ʵ,й¶,Ϊģκμṩ˷߼ʾ.
(R-2) Բ֪
Generate(x,m)Know(x,m).
˼,ԼɵϢԼһ֪.
(R-3) ۹

˼,Ѿ֤Ľκζֳ.
ָ,۹ĳЩȫЭǲõ.ط:(1) Эִй̵;Կ,ʵԭԿ֪ʶѾϡ,˲㡰ۡ;(2) ڶĳЩϢûС䡱ܵ,ԭЩϢ֪ʶܱ,Ҳ㡰ۡ.,߼ϵͳ,ֻİȫЭ:(1) Эִ;ɸԿ;(2) ʵйᴩЭִйʼյļ书.ڲЭ,Ĺ۹,ԴǽĲ.
(R-4) ϳɹ

˼,еĺϳЧ൱ڰǰһеĺΪһеǰᡢѺһеĽ۵ϳɶеĽʹ.
ںϳɹĳ,԰ѶеĺϳɿһнԵĴ.еλԪ,С.
(R-5) ǵ

˼,ƳǰPx֪m,ôͿԷǵؼٶx֪m.ǵ˼:֪Pͦ,ǡƲx֪mͼٶx֪mǺ;Pߦļӳ,ҲͿƳx֪m,ʱԭķǵҪµ.÷ӳϢȫеһ:Ǻѿ϶ءض϶˭֪ʲô,Ĭ֪;ĳֵĻ,ЩӦò֪ĳЩϢ.
2.3 ʽ
Ķл,ʽ:
(նУ

ʽʾµϵ:

ڷǵ۵Ƶ,֪һ߼¿֤ϵĲж,ܰڡƲʲôֶԵһ߼Χʽ.ڻڴһ߼ķǵ߼,ǹһֵʹǰͷǵ۹ͬΪ.ĸֵܹɹ,ǵۼϿ;ֹ̲޽.ڻڶ̬߼ķǵ߼,ҪԸڡƲʲôֶ,һҲ,ֻܲȡʧܼ񶨡ֱ۵İ취.Ȼ,һ־л۹ķǵ̬߼,˿ͨѶתдνһġڴһ߼ķǵ߼.߼ϵͳԽPrologԱĴСʧܼ񶨡ʵ䲢ӵķǵ.
3 ȫЭƵ֤ʾ
3ʵ˵NDLƵȫЭ.
1:֪:
P={Know(Alice,Kpb(Bob))},
=Generate(Alice,m)Generate(Alice,k)Send(Alice,Bob,E(m,k),S(k,Kpb(Bob))),
Q={Know(Bob,m)}.
֤:PQ
֤:
(1)Know(Alice,Kpb(Bob))ǰ
(2) Generate(Alice,m)۶
(3)Know(Alice,m)(2)R-2
(4) Generate(Alice,k)۶
(5)Know(Alice,k)(2)R-2
(6)Know(Alice,E(m,k))(3)(4)1-1
(7)Know(Alice,S(k,Kpb(Bob)))(5)(1)1-2
(8)Know(Alice,E(m,k),S(k,Kpb(Bob)))(6)(7)6-1
(9) Send(Alice,Bob,E(m,k),S(k,Kpb(Bob)))۶
(10)Know(Bob,E(m,k),S(k,Kpb(Bob)))(9)R-1
(11)Know(Bob,E(m,k))(10)6-1
(12)Know(Bob,S(k,Kpb(Bob)))(10)6-1
(13)Know(Bob,Kpv(Bob))2-3
(14)Know(Bob,k)(12)(13)(14)3-2
(15)Know(Bob,m)(11)(15)3-1
ʽ(15)֤Ľ.
1ͨźѧ任ƿͼ1ʾ.

Fig.1
ͼ1
2:֪:
P={Know(A,CertS(A)),Know(A,Kpb(B))},
=Generate(A,m)Generate(A,k)Send(A,B,E(m,k),S(k,So(A,m),CertS(A),Kpb(B))),
Q={Know(B,m),Auth(B,A,m),Auth(B,CA,A,Spb(A))}.
֤:PQ
֤:
(1)Know(A,CertS(A))ǰ
(2)Know(A,Kpb(B))ǰ
(3)Generate(A,m)۶
(4)Know(A,m)(3)R-2
(5)Generate(A,k)۶
(6)Know(A,k)(5)R-2
(7)Know(A,E(m,k))(4)(6)1-1
(8)Know(A,Spv(A))2-3
(9)Know(A,So(A,m))(4)(8)4-2
(10)Know(A,k,So(A,m),CertS(A))(6)(9)(1)6-1
(11)Know(A,S(k,So(A,m),CertS(A),Kpb(B)))(10)(2)1-2
(12)Know(A,E(m,k),S(k,So(A,m),CertS(A),Kpb(B)))(7)(11)6-1
(13)Send(A,B,E(m,k),S(k,So(A,m),CertS(A),Kpb(B)))۶
(14)Know(B,E(m,k),S(k,So(A,m),CertS(A),Kpb(B)))(13)R-1
(15)Know(B,E(m,k))(14)6-1
(16)Know(B,S(k,So(A,m),CertS(A),Kpb(B))(14)6-1
(17)Know(B,Kpv(B))2-3
(18)Know(B,k,So(A,m),CertS(A))(15)(16)(17)3-2
(19)Know(B,k)(18)6-1
(20)Know(B,So(A,m))(18)6-1
(21)Know(B,CertS(A))(18)6-1
(22)Know(B,m)(15)(19)3-1
(23)Know(B,A,Spb(A))(21)۶,6-1
(24)Know(B,Spb(A))(23)6-1
(25)Auth(B,A,m)(20)(22)(24)۶1
(26)Know(B,Sign(CA,A,Spb(A)))(21)۶
(27)Know(B,Spb(CA))2-2
(28)Auth(B,CA,A,Spb(A))۶2
ʽ(22)(25)(28)֤֮.
ۺӦõԿܽܡԿܽܡǩ֤Կֶ֤εһȫЭ֤.,(25)(28)ʽ,кԵ֤Ч:mAԼǩԿǩ,AǩԿͬA˵CAǩԿǩ.,ֻҪBCA,BSpb(A)ȷϵAǩԿ,ӶȷAm.
3:˫ǩ.
һ漰3İȫЭ,ǴӰȫӽSET(secure electronic transactions)ЭнȡƬβһļ.֪:
P={Know(B,Spb(A)),Know(C,Spb(A))},
=Generate(A,m1)Generate(A,m2)
Send(A,B,m1,H(m2),So(A,H(m1),H(m2)))
Send(A,C,m2,H(m1),So(A,H(m1),H(m2))),
Q={Auth(B,A,m1),Auth(C,A,m2),Auth(B,A,H(m2)),Auth(C,A,H(m1))}.
֤:PQ
֤:
(1)Know(B,Spb(A))ǰ
(2)Know(C,Spb(A))ǰ
(3)Generate(A,m1)۶
(4)Know(A,m1)(3)R-2
(5)Generate(A,m2)۶
(6)Know(A,m2)(5)R-2
(7)Know(A,H(m1))(4)4-1
(8)know(A,H(m2))(6)4-1
(9)Know(A,H(m1),H(m2))(7)(8)4-1
(10)Know(A,So(A,H(m1),H(m2)))(9)4-2
(11)Know(A,m1,H(m2),So(A,H(m1),H(m2)))(4)(8)(10)4-1
(12)Send(A,B,m1,H(m2),So(A,H(m1),H(m2)))(11)۶
(13)Know(A,m2,H(m1),So(A,H(m1),H(m2)))(6)(7)(10)4-1
(14)Send(A,C,m2,H(m2),So(A,H(m1),H(m2)))(13)۶
(15)Know(B,m1,H(m2),So(A,H(m1),H(m2)))(12)R-1
(16)Know(C,m2,H(m1),So(A,H(m1),H(m2)))(14)R-1
(17)Know(B,m1)(15)6-1
(18)Know(B,H(m1))(17)4-1
(19)Know(B,H(m2))(15)6-1
(20)Know(B,H(m1),H(m2))(18)(19)6-1
(21)Know(B,So(A,H(m1),H(m2)))(15)6-1
(22)Auth(B,A,H(m1),H(m2))(20)(21)۶1
(23)Auth(B,A,H(m1))(22)6-2
(24)Auth(B,A,H(m2))(22)6-2
(25)Auth(B,A,m1)(17)(23)5-2
(26)Know(C,m2)(16)6-1
(27)Know(C,H(m2))(26)4-1
(28)Know(C,H(m1))(16)6-1
(29)Know(C,H(m1),H(m2))(28)(27)6-1
(30)Know(C,So(A,H(m1),H(m2))(16)6-1
(31)Auth(C,A,H(m1),H(m2))(29)(30)۶1
(32)Auth(C,A,H(m1))(31)6-2
(33)Auth(C,A,H(m2))(31)6-2
(34)Auth(C,A,m2)(27)(33)5-2
ʽ(24)(25)(33)(34)֤֮.
˫ǩǿԿ,ǵ֤Ĳͬ.5-1Ķ1Ͷ2Ǵǩֱӽ֤.5-2ͨժ֤ԭγɶԭĵļ֤.һּ֤ķʽȫ.ͨ׵˵,:㲻ܵĳԭĵժϽйǩ,ֻ˸ԭ,ҾΪ㲻ܵ㷢˸ԭ.һõĸԭժѾȷ޸Ķժ,ҾΪԭҲûиĶ.Կ,ûڹ5-2Ĺ,Ҫ֤˫ǩŵİȫкܴѵ.˵ֱ۷ϸ΢֮ܲװ,ȷġĹ,֤ͷ.
4  
Ͻķǵ̬߼ϵͳNDL.ϵͳͨһ׻ڡһ߼+̬߼+ǵ߼Ĺ,綨ƵȫЭʵһµʽ.ͨЭ֤ʵ,ǿ,ķȷʵܹԺܴһలȫЭŵİȫʽ֤.رڻ۹õ,֤̿Prologʵֳ,еķǵ.
Ȼ,۹򲢲ǶаȫЭ鶼.ȷʵһЩ漰Эִе;ԿĺҪӵ߼.ԴҪбķΧרо.
Ĺص߼Ӧ.߼ϵͳʽʣȣ,ҲҪбķΧרо.
ձĵķ,ϵӽױһЩ֪ʶ,ԶһЩģȽϴĵӽЭ,˵SET6,ȫġϸ֤.ѾSETһҵ̳ɹؽ֤,ƹ㵽ֵĹڽ֮.
Ŀоõ863߿ƼĿ(No.863-306-ZD10-02).
߼飺˶,1956,ʿ,оԱ,ʿʦ,ҪоΪ˹,
ѧ,Internet/IntranetӦ.
ӱ,Ů,1973,˶ʿ,ҪоΪInternet/IntranetӦ,
.
,1971,ʦ,ҪоΪϢȫ,.
,1974,ʿ,ҪоΪϵͳ,InternetӦ.
ׯ,1968,ʿ,ҪоΪInternetݰȨ,ȫЭ.
ߵλ˶(ܼоġ100080)
ӱ(ܼоġ100080)
(ܼоġ100080)
(ܼоġ100080)
ׯ(ܼоġ100080)
οף
1Michael B,Martin Abadi,Roger Needham.A logic of authentication.ACM Transactions on Computer System,1990,8(1):1836
2Abadi M,Tuttle M.A semantics for a logic of authentication.In:Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing.Montreal:ACM Press,1991.201216
3Kailar R,Gligor V.On belief evolution in authentication protocols.In:Catherine Harris,Madallum A C eds.Proceedings of 4th IEEE Computer Security Foundations Workshop.Los Alamitors,CA:IEEE Computer Society Press,1991.103116
4Volker Kessler,Cabriele Wedel.AUTLOGan advanced logic of authentication.In:Bob Wernered ed.Proceedings of the 7th IEEE Computer Security Foundations Workshop.Los Alamitors,CA:IEEE Computer Society Press,1994.9099
5Kailar R.Accountability in electronic commerce protocols.Proceedings of IEEE Transactions on Software Engineering,1996,22(5):313328
6SET Secure Electronic Transaction Specification.Book 1:Business Description,Version 1.0.1997
ոڣ1998-04-03
޸ڣ1999-03-22
