ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



CCSļЭ 
һǿ

ժҪЭķҪʽķ͹.Ķ˼ЭPEP (principals+environment=protocol),˵һЭ,PEPתΪĻCCS,ɴ˿ڻCCSCWB(concurrency workbench)зЭ.˷ŵʽؿ̻ߵΪ,ͼͨģͼ(model checking)ЭǱڵİȫ©,ҵЭ;.
ؼʡЭ,Э,ʽ,CCS,ģͼ.
ͼšTP309

CCS-based Cryptographic Protocol Analysis
DING Yi-qiang
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100080)
Abstract Formal methods and tools are key aspects for the analysis of cryptographic protocols. In this paper, a formal language PEP (principals+environment=protocol) for the specification of cryptographic protocols is proposed. For some cryptographic protocols, their PEP specifications can be translated into finite basic CCS processes, so it is possible to analyze the security properties using CCS-based tools such as CWB (concurrency workbench). The advantage of the mothod proposed in this paper is that the actions of the attacker can be implicitly specified, and if the potential back door of the protocol analyzed exists, the attacking action trace can be explicitly found out by model checker.
Key words Cryptographic protocols, protocol analysis, formal methods, CCS, model checking.
1Э鼰ʽ
ЭĿüܼ֤İȫ.ڼЭ,ܼǷǳҪ,һ,Э߼Ʋ,ڼ̵ı˸,߸÷ȥܾͿԴﵽĿ.Ϊ˱֤ЭƵȷ,ⷢǱڵĴ,ҪʽĹȷЭΪԼЭҪﵽĿ,ЭܷﵽԤĿ.ʵѾ֤,ʽЧ.
ĶЭPEP(principals+environment=protocol),˵һЭ,PEPתΪĻCCS[1],ɴ˿ڻCCSCWB(concurrency workbench)[2]зЭ.ķŵʽؿ̻ߵΪ,ͨģͼ(model checking)[3]ЭǱڵİȫ©,ӶҵЭ;.
ĵ2ڽܼЭҪ.3ڶЭPEP﷨.4ھNeedham-SchroederԿЭ.5ǽ.
2Эģ
2.1  Ϣ
֮䷢ͺͽյϢ¼:ʶġ(nonce)ԿϢ͸Ϣ.
ʶΨһ,ڿ绷,ʶһǹ.һִ.,޷ͨ²õ.ڼЭ,ϢҪ͵Ϣм,Ժ,յϢʱ,ͿԶ϶Ϣ½ɵ.,ȷԷֹط(replay).
ǰԿƷΪ.һԿ,ҲƶԳԿ,ԿԿͬһԿ,ԿƱ,һԿܵϢֻôԿܽ.ڱ֤Ϣı֮,ͨϼϢ,жϴϢԴ,ΪôԿϢȷ.һǹԿ,ԿɶԴ,һǹԿ,һ˽Կ,Ϣ߿ýߵĹԿϢ,ֻӵжӦ˽ԿĽ߲ܴܽϢ.
ϢϢĸ,װѸϢֽΪɲ.
2.2  
Эˡ.ΪͺͽϢԼڲ(ܡܡ߼жϵ).֮ǲе.
ǼָϢ,ҶԲЭϢܾ.,Э,AӦôBԿk,ôʱA;ܾճԿϢ.,ҲܱͬϢĲֵͬ.,ԱյǷǸղŲ.
2.3 
ڿŵ绷,ǱڵĹ߿ܿ,ϴ͵Ϣ۸ĺز.ڱ,ǿ԰ѻߵ֪ʶ.һ,Э,֪ʶ;һ,ЭΪҲɵǰĻ.
2.4 Э
ּЭҪﵽĿĲͬ,ҪҲͬ.֤(authentication)Э,ķ֤Э.
֤ЭǼЭкҪһ.MITŵȼƻKerberosЭʹùԿ֤Э.֤ЭĿȷЭ,ֹ߼ðԴ.
WooLam[4]֤ЭҪ:Ӧ(correspondence)ͱ(secrecy).ķӦ.ʽ˵,Ӧָ֤ЭеĶŶӦϵ.,ЭӦBЭʱ,ӦЭ鷢AѿʼдЭ.
T authenticate R
ʾT֮ǰһжR,
end_response authenticate begin_init
ͷӳӦϵ.
3ЭPEP
CCSһͷͨϵͳʽϵ[1].ͨϵͳͨΪCCS,ϵͳģ̬߼̻.һCCSǷģ̬ʳΪģͼ(model checking).CCS(basic CCS)кܳ۽ԼӦĹ,Concurrency WorkBench[2].ЭгĴֵʱ,ᵼ״̬Ǩͼֲ,߶޷.
ڿλCCSͷЭ.
һڵЭģ,Э֮ԴݸϢ,ЭǴֵ,ֵϢռ,Ȼ.Эķ.,ڼЭĻҲʵĿ̻.ϣʽؿ̻()Ϊ,Эʱ,Эаȫ©,ǵķӦƵ·.
ЭͻΪԷ,Эɻݵ(ǹ)͵Ϣɿѡؽܵ.,Э˵(аNeedham-SchroederԿЭ),κ״̬,Ķ޵,һCCSЭ˷.һ,ΪҲܻӰ.Э,֮䴫͵ϢԽ,ܹĿԾԽ.,ͬЭڵ2ʱ״ֲ̬ͱȵ1ʱҪ.
Эģ͵ص,׼CCS޷ֱӿ̻.,ĻCCSPEP,ԴﵽͷЭĿ.
3.1 Ϣռ
Ͻ,ϢʶġԿϢ͸Ϣ.ڱ,uval(a)ʾʶֵ,uvar(x)ʾʶ;nval(n)ʾֵ,nvar(x)ʾ;kpub(a),kpvt(a),kshd(a)ֱʾԿ˽Կ͹Կ;text(t)ʾ;enc(k,m)ʾܵϢ;(m1,m2)ʾϢĸ.
Ϊ˱״̬Ǩͼֲ,ϢռвϢ,ֻʶ.ηſ,ʹñķӦø㷺ǽŬ.ʹд,Ȼ̻һļЭ.
3.2 Ϣ
()ϢµĶԪϵ̻.
R1: mS,Sm.
R2: Sm,Sk,Senc(k,m) .
R3: Senc(k,m),Sk,Sm.,(kpub(a))=kpvt(a),(kshd(a))=kshd(a).
R4: Sm1,Sm2,S(m1,m2) .
R5: S(m1,m2),Sm1,Sm2.
3.3 ЭPEP
3.31  
ЭĶsend(m)recv(m).Эеκ״̬,ֻܷͷյϢ,Ϣڲޱ.ڽն,ɽյϢһϢģʽ,пԳֱ.ֻģʽϢŽ. 
3.32 +=Э
PRINCIPALS = stop ; ֹ
| ACTION. PRINCIPALS ;ǰ׺
| PRINCIPALS + PRINCIPALS ; ѡ
| PRINCIPALS | PRINCIPALS ; 
ENVIRONMENT = {MESSAGE,,MESSAGE} ; Ϣ
PROTOCOL = PRINCIPALS in ENVIRONMENT
PEP,̵CCSĽ̷ǳ,ֻΪ뻷໥.ǶЭĲ:




P[/]ָ滻PеĵõĽ.
ЭĲ,ǿЭPEPõ״̬Ǩͼ,ȻתΪCCS.,recvеϢֻʶ,˼{M()|SM()},ӦCCSתֲ.,Ҳ̵ĵݹ鶨,,Эģ͵CCSתĽ.
3.4 Ӧ
ģ̬߼ʽ[3]:
T authenticate R=X.([T]false[R]X)
̻Э嶯ĶӦ,⼴̿ʼT,ҶκγR֮õĽ,ҲT,ԺκγR֮õĽ,ҲT,ȵ.
3.5 ģͼЭ
,Ƕ˼ЭPEP,˵PEPתΪCCS.,ģ̬߼еĦ͹ʽ̻嶯ĶӦ.
CCS,һģǷģ̬ʽ,ģͼ㷨.˾Ϳ֤ЭǷӦ.Ŀǰ,๤߶֤,ҵ֤ʧʱ,ԸʲĶ,ǷļЭ˵,˶ǶӦ˹߽·.
4Needham-SchroederԿЭķ
ھ˵ӦñķЭ.ǵЭǼ򻯵Needham-SchroederԿЭ[5].
(1)AB:A,B,{Na,A}kb
(2)BA:B,A,{Na,Nb}ka
(3)AB:A,B,{Nb}kb
ڴЭ,,Э鷢AѡһNaʶһӦBĹԿkbܺ͸B;BյϢܺ,͵õNa,֮ҲһNb,NaһAĹԿkaܺ͸A;AӽܺõNaͼжͨŵB,ͬ,ANbܺ󷵻ظB;BܺͼжͨŵA.
,Э鷢AЭӦBͨ.Ϊ,ǿAB,Cͨŵ.
PEP,Э:
A1= send(uval a,uval b,enc(kpub b,nval na1,uval a)).
recv(uval a,uval b,enc(kpub a,nval na1,nvar x)).
send(uval a,uval b,enc(kpub b,nvar x)).
stop
A2= send(uval a,uval c,enc(kpub c,nval na2,uval a)).
recv(uval a,uval c,enc(kpub a,nval na2,nvar x)).
send(uval a,uval c,enc(kpub c,nvar x)).
stop
B = recv(uval b,uval a,enc(kpub b,nvar y,uval a)).
send(uval b,uval a,enc(kpub a,nvar y,nval nb)).
ecv(uval b,uval a,enc(kpub b,nval nb)).
stop
,A1,A2ֱʾAB,ACľֲͨЭ.
ʼΪ
S0={uval a,uval b,uval c,kpub a,kpub b,kpub c,kpvt c}.
ʼаC˽Կkpvt c,ӦCΪ߻C˽Կй¶.
Э˵дΪ
Spec=(A1+A2)|B in S0.
BͨŶA,˵һ:
recv(uval b,uval a,enc(kpub b,nval nb)) (1)
ʱ,ȷŴЭA,A
send(uval a,uval b,enc(kpub b,nval na1,uval a)) (2)
.öӦʾΪ
(1) authenticate (2).
MLʵPEPCWBCCSԵת.ȻCWB,ģͼЭǷӦ,Ƿ񶨵,Һ׾͵õ˹;:
send(uval a,uval c,enc(kpub c,nval na2,uval a))
recv(uval b,uval a,enc(kpub b,nval na2,uval a))
send(uval b,uval a,enc(kpub a,nval na2,nval nb))
recv(uval a,uval c,enc(kpub a,nval na2,nval nb))
send(uval a,uval c,enc(kpub c,nval nb))
recv(uval b,uval a,enc(kpub b,nval nb))
5 
Ƕ˼ЭPEPڿ̻һ಻ϢļЭ,״̬Ǩͼֲ.,ЭPEPͿתΪĻCCS,ҿڻCCSCWBзЭ.ķͬ๤,ŵʽؿ̻ߵΪ,ͨģͼ鷢ЭǱڵİȫ©,ҵЭ;.
עͣоõȻѧ͹ҽѧعԱ
߼飺һǿ1970,ʿ,ҪоΪʽ簲ȫЭ
ߵλ:йѧԺоѧоʵ  100080
ο
1Milner R. Communication and Concurrency. New York: Prentice Hall, Inc., 1989
2Bruns G. Distributed Systems Analysis with CCS. London: Prentice Hall, Inc., 1997
3Stirling C. Modal and temporal logics for processes. Technical Report, ECS-LFCS-
92-221, Department of Computer Science, University of Edinburgh, 1992
4Woo T Y C,Lam S S. A semantic model for authentication protocols. In: Proceedings
of IEEE Symposium on Research in Security and Privacy. Oakland, CA:IEEE Computer
Society Press, 1993
5Lowe G. Breaking and fixing the Needham-Schroeder public-key protocol using FDR. 
In: Margaria T, Steffen B eds. Tools and Algorithms for the Construction and 
Analysis of Systems, vol 1055. Lecture Notes in Computer Science. 
Springer-Verlag, 1996. 147166
ոڣ1998-04-30޸ڣ1998-10-22
