Novel analysis and improvement of Yahalom protocol

Available online at www.sciencedirect.com“ScienceDirectThe Journal of ChinaUniversities of Posts andTelecommunicationsEL SEVIERApril 2009, 16(2): 80- 83www.sciencedirect.com/science/jouma/10058885www.buptjournal.cn/xbenNovel analysis and improvement of Yahalom protocolCHEN Chun-ling' (囚), YU Han', LU Heng shan', WANG Ru- chuan'1.College of Sofware, Najing University of Posts and Telecomunications, Nanjing 200030, China2. Department of Mahematics, Cllege of An and Science, University of Wyorming, Laramie, Wyoming 82072. USA3. Ollege of Computer, Nanjing University of Posts and Tecommunications, Nanjing 200030, ChinaAbstractThe modified version of Yahalom protocol improved by Burrows, Abradi, and Needham (BAN) still has security drawbacks.This study analyzed such flaws in a detailed way from the point of strand spaces, which is a novel method of analyzing protocol'ssecurity. First, a mathematical model of BAN-Yahalom protocol is constnucted. Second, pentators' abilities are restricted with arigorous and formalized definition. Moreover, to increase the security of this protocol against potential atackers in practice, afurther improvement is made to the protocol. Future application of this re improved protocol is also discussed.Keywords strand spaces, BAN-Yahalom protocol, ideal, minimal element1 IntroductionStep4 A→B:{A.KpINb}xr{N.}kaSince Dolev and Yao proposed to study security protocolindependent of the research of cryptography [1], research that↓centers on the protocol itself stats to draw much attention.Especially after the emergence of BAN logic [2], research inthis field has rapidly progressed. However, the technique offormalized analysis did not acquire substantial advancementFig. 1 BAN.Yahalom protocoluntil Strand Spaces emerged [3- 4]. This article is organized asfollows: Sect. 2 provides the algebraic model of the BAN-This protocol aims to enable only two principals A andYahalom protocol based on strand spaces. Sect. 3 analyzes3 to eventually share one common key Kp generated anddrawbacks of the BAN Yahalom protocol from the point ofdstributed by the authentication server s, which is trusted bystrand spaces and reviews the secrecy from the notion ofboth principals.'Ideals' proposed in Refs. [5- -6]. Sect. 4 discusses improvementof the BAN-Yahalom protocol in its Intemet security guarantee2.1 Specialization of term algebraand electronic business (E-business).1) Building strand spaces2 Strand space model of the BAN-Yahalom protocolAccording to the theory and methods proposed by strandspaces, it is necessary to give notions as follows;A complete bout of the BAN-Yahalom protocol is shown inDefinition 1 A set of principal identifiers Tonne sT;A,Fig. 1, with its prototype as follows:B, ... are generally used to identify the principals' name. AnStep1 A→B:A,N.injective mapping K:T→K，which means that ifStep2 B→S:B,N,{A,N.)xwK. =K,, there must exist a=b , that is, different principalsStep3 s→A:N.{B,K.N.Jhx.1IA.K.IN.hxaDer中国煤化工3AN-Yahalom strandReceived date: 05-04 2008space,YHCNMHGspaceand 5 istheCorresponding author. CHEN Chun- ling, E mail: clchen@njupt.du.cnunion of four kinds ot strands:DOL: 10.1016/S1005- 88(0806020701Issue 2CHEN Chun-ling, et al. 1 Novel analysis and improvement of Yahalom protocol81①Penetrtor'strand s∈ P.originated in 5, it must originate from . The②Initiator's strand s∈Sga[A,B,S,N,N,K.p] , with tracereason is obvious since A is an initiator of the whole bundle C,< +AN,- N。{B,Kp,N,)xw{A, Kp, NJ}xa,+{A, Kp, N,)xan*nd Definition 3 (M,T,C,S) indicates that any atacker{N}xa>, where A,BeTm，N,Ng∈T ,but N.ET ;cannot generate the term N, by himself. As a result, a③Responder's strand s∈SR [A,B,S,N, ,N,K.], withminimal relationship [9] in the bundle of partial order can betrace<-AN,+BN.{A,.N,)on.H{A,K.N.J}x~{N.}xw >, whereobtained:= {M :N, C term(m)}Kc-mita. (1)A,B∈Tw，N,N.∈T, N。eT,but N,≠N,;④Authentication server's strand s∈ Ssuw[A,B.S,N,N。K_], with trace <-BN[{A,N,}xa.+N,{B,KpIN.,}xw,-{A,Kp,N.la>，where A,BeT，N,N∈T, and Kp∈(K \Kp)N(K\K,),where i=a,b .2) Boundares of atacker.Definition 3 A penetrator trace is one type of the fllowing:;M. Text messages: <+1> , where teTF. Flushing: <-g>T.Tee: <-g.+8g.+g>Fig. 2 The Iitiator's Strand with regular nodes and N, isG. Concatenation: <-g,-h,+gh>the minimal in Sns. Separating into components: < -gh,+g,+h>K.Key: <+K>, where K∈KpNow, check whether the term N.(B,Km,N,ku{A,K.,E. Encryption: <-K,- -h,+{h}r >N,}xm received by can be sent from an attacker'sD. Decryption: <~K-', -{h}x,+h >node located in a penetrator strand, which is the main aim ofIn Ref. [7], F. and T. are ignored, which are crucial for thethis article.closure of the whole penetrator's strand space.1) Temm divisionterm(< S,2>)= -N.{B,Kxp,N,J}xm{A.Kx,.N}xan(23 Protocol analysisA penetrator can receive and send nonce's in a strand withtrace C:<-g," h,+gh> andS:<- gh,+g,+h> in Definition 3,3.1 Authentication securitywhich limits a penetrator's capability. Repeated application ofthis plus M and F can help a potential penetrator to divide oneAlthough BAN-Yahalom protocol improved the last step ofterm into three subtems [3], that is N,{B,KoIN,)w , andthe original Yahalom protocol proposed in Ref. [1] because of{A,Kp,NJ}ox. Hence, it is reasonable to study these threeits defection in old key replay atacks [8], this problem is nottoo serious since BAN logic has the fundamental hypothesissubterms respectively.2) Term interceptionthat both initiator A and responder B are honest. However,By K..KKp∈Kp, it can be deduced that each of the twothis improvement brings new problems. The study explains anew proof of such problems from the perspective of strandsets {m:(B,Ko,N,}x C term(m)} and {m:{A,Km,NJ}xn Cspaces. .term(m)} defined by {B,Kp,N.}kw and {A,Ky,NJ)xnProposition 1 Ifrespectively, has a Sc- = aim member [3] that uniquely1) 5 isa BAN-Yahalom strand space, C is a bundle oforiginates from the node in the authentication server's strand.2[3-4]，S。is an initiator's strand with traceSince:Sma[A,B,S,N,N,K_], and C-height(S)=3.①By the Proposition1, Kg,Kpe Kp in the proposition2) K_,Kg,KgeKp.and the boundary of the penetrator's behavior with trace K:3) N, is uniquely originatedin 5.<+K> (where K∈Kp) defined by Definition 3, anyThen C does not necessarily contain a real responder'spotential atacker cannot send or receive the keys that encryptstrand withrace Sen 。[A,B,S,N,N,K.小.two su中国煤化工.,-(n),.+h>Proof First, the hypotheses of this proposition can be②briefly constructed, as shown in Fig. 2. If N. is uniquelyItis |MYHCNMHGihoutheocrncee，82The Journal of China Universities of Posts and Telecommunications2009of K stated in①. It is also necessary to mention that thereceives this term with trace F so that a complete bout of thiscryptographic system in the protocol is perfect just aprotocol terminates. A real responder strand with traceindicated by Proposition 1. In that case, any potentialSeap[A,B,S,N,N,Kg] doesn't necessarily appear in thepenetrator cannot naturally generate{B,Kp,N,}km anbundle C.{A,Kb,NJ)ko. As a result, it is only possible to deceiveauthentication server into intercepting these subterms.3.2 Consistency guarantee3) The attackIf the real responder B participates in the protocol, then byThe proof above indicates that the BAN-Yahalom protocolN.≠N。of ③in Definition 2, B will generate termhas security problems because of non-injective consistencyBN.{A,N,Ixn and send it. Thus, it is impossible for thethat may be used to cheat authentication server. Its drawbacksare analyzed in terms of the following:attackers to intercept any useful nonce s that may threaten the1) Public exposition of information like N。 withoutsecurity of the protocol. If a penetrator smoothly carries ouencryption in steps 2) and 3) of the protocol.the atack, then the following formula should be satisfied.2) No nigorous guarantee that N, ≠N。by authentication{m:{A,N,)xm c term(m)}Sc.iu c0(3Since the initiator and authentication server do not considerserver or initiator.whether N.=N。 or not, they are easily deceived by an3) Inberent defection of authentication server because itnly receives and sends messages without checking thattacker to generate certain terms as long as the atacker sendsource and the destination of messages.them mesages by imitating initiator A, responder B, o4) Lack of necessary information exchange between initiatorauthentication server s.However, {m:{A,N.}ks C term(m)|Sc. caoia C 0 indicatesand responder.that no one generates {A,N.}xw. It is significant for the3.3 Secrecy guaranteeauthentication server to treat the status of A and B equally if itis noted the symmetry of {B,Kp,N,)xu and {A,Kg,N,)on .The atack above does not lead to key K。being leakedIn that case, it is logic that {B,N,}kw may also be used byout to any penetrator. It just prevents the key from beingan atacker to reach his purpose. And the minimal element ofshared by two principals. The is because the penetrator has nothe set {m:{B,N.}xm c term(m)} uniquely originates fromknowledge of Kp and thus its boundaries are limited andthe strand of a responder acted by A. Therefore, an attackernot able to decrypt terms that include Kp as a subterm. Thismay use this property with N.=N。 to enable theis further explained by the next thcorem.authentication server to encrypt for him.Theorem 1 Suppose that C is a bundle in EThus, the initiator A can be deceived by several potentialA,BET.me，Kp is uniquely originated, Kg,Kw e Kp, andattackers as follows:Sg_v e Sw[A,B,N,IN,K.]. Let s={Kg,Kp,Kx}, whereA→P(B):A,N, I1 F in Definition 3k=K\S. Then for any node m∈C, term(m)E lx[K.].P(B) -→A:B,N。I1 atacker imitates B to initialize anotherProof In Ref. [4], it is indicated that term(m)∈ l[Kg]bout of protocol withAif and onlyif Kp C ,term(m).A→P(S):A,N",{B,N.}xa 11 A generates {B,N,}xHowever, because K..KneK, ，any long-term keyalong with another temporary nonce N，cannot be applied to encrypt Kg.P(A)→S:A,N,{B,N,}kw /since N. =N。is alowed,First, the assumption k= K \S ensures that the smallestN. can be replaced by N。by atacker with M,F,T,C,S .k-Ideal containing K。cannot be encrypted by regular nodeS→P():N,1A.K.m.N.Jx.{B,K.o.Nx.of non-participants even with the help of long-term keys K.,Then, P(B) is able to send the message shown in Fig. 2Ku,or Kp iself.to node by concatenation and separation of messageSecond, the assumption that Kw is uniquely originatedN,{A.Ks,NJao(B.Km.N.)x。indicates that K。should only be encrypted by Suev， thatTherefore, 1), 2), and 3) have basically described theis, the. authentication server strand with trace Sgv[A,B,N,process of the attack against BAN- Y ahalom protocol.中国煤化工The last step can be expressed as follows:N,Kterm(<. S,3>)= +{A,Kp,NJ}x{N,hkw. The attacker P(B)YHCNMHGIssue 2CHEN Chun-ling, et al.1 Novel analysis and improvement of Yahalom protocol834 Improvementmessage in step 1. This symmetry makes impossible that anoutdated key is used by attackers. This improvement4.1 Principles for improvement of the BAN-Yahalom protocolconsiders the requirement of consistency guarantee as well asmaintaining the inherent secrecyof K。.With the development of security protocol in E-business [10],protocol itsef becomes more vital for the security of different5 Discussionprincipals. Considering this, some rules are proposed to makefurther improvement on the BAN-Yahalom protocol thatIn this study, the drawbacks of the BAN-Yahalom protocolrefers to the principles stated in Ref. [10], which is expectedare analyzed based on a new method- Strand Spaces. Theto be more adaptable to applications in information exchangeBAN-Yahalom protocol is proposed in Ref. [2] under theon the Internet.idealistic condition that each principal, including every1) Keep the framework of this protocol without encryptingattacker', is honest. Nevertheless, Ref. [1] indicates thatany nonce, including session keys or temporary messages thatattackers should never be underestimated. Hence, furtherneed protection.improvements to the protocol against potential attackers are2) Add new terms to bundle C to enhance the authenticationmade. Strand spaces make it convenient to improve securitycapabilities of the protocol.protocols to be more adaptable to practical environment.3) Add response of the responder to the initiator's message,Further research of this protocol can be applied in E-business.which leaves very few chances to replay atacks.4) Initiator and responder can be better simulated for futureAcknowledgementsapplication in E-business on the Internet.This work was supported by the National Naturnl Science4.2 Measures of imnprovementFoundation of China (6057314. 60773041).Step1 A→ B:A,N.ReferencesStep2 B→S:B,{N,A,N,)ox1. Dolev D, Yao A. On the security of public key protocols. EEEStep3 s →A:{B.Kx,N.N,}w.I{A.K.,N.xanTransactions on Information Theory, 1983, 29(2): 198 -2082. Burrows M, Abradi M. Needham R. A Logic of authentication.Step4 A→B:{A.Kp.NJhxw,{N,.N}x.Proceedings of the Royal Society: Series A, 1989, 426: 233 -271Step5 B →A:{A,N,}u3. Thayer Fabrega F J, Herzog J C, Gutman J D. Strand space: why is ascurity protocol orrect? Proceedings of 1998 IEEE Symposium onFeatures of this improvement:Security and Privacy, May 3 6, 1998, Oakland, CA, USA: EEEComputer Society, 1998: 160-1711) Step 1 retains the framework of the original protocol,Thayer Fabrega F J, Herzog I C Guttman J D. Strand spaces. Technicalwhich makes initiator send messages to authentication serverReport. The MITRE Corporation, 1997indirectly.s. Thayer J, Herzog J, Gutman 」. Honest ideals om strand speces,Proceedings of the 11th IEEE Computer Security Foundations Workshop,2) Steps 2 and 3 shield more information from potentialJun9-11, 1998, Rockport, MA, USA. Los Alamitos, CA, USA: IEEEattackers with the help of K\Kp using the oniginalComputer Society,1998: 66-776. ThayerFJ, Herog J C, Gutman J D. Mixed strand spaces. ProceedingsYahalom protocol.of the 12th IEEE Computer Security Foundations Workshop, Jun 28 -30,3) Steps 4 and 5 guarantee necessary message exchangeMordano, ltaly. Los Alamitos, CA, USA: TEEE Computer Society, 1999;between A and B, which makes their common key7. Qin S H. Security prolocol. Beiing, China: Tsinghua University Press,acknowledged by both sides explcitly. The subterm2005: 78 -149, 306 -334 (in Chinese)3. WangGL, QinS H, Zhou z F. Some new atacks upon authentication{N,N,} not only ensures responder B to reply in step 5procols. Journal of Software, 2001, 12(6);: 907-913 (in Chinese)but more importantly helps identify attackers earlier before9. ZuoXL,L W J, Liu Y C. Discrete mathemaics. Shanghai, China:Shanghai Science and Technology Literature Press, 1982: 81-139 (inthe termination of the protocol even if N, = N。is allowed,which is highly probable under circumstances of probability10. Zhou L x. Summarization of electronic commerce protocols rescarch.Journal of Software, 2001, 12(7): 1015- -1032 (io Chinese)model or practical application. Moreover, the message{A,N.)k in step 5 keeps certain symmetry with the(Editor: ZHANG Ying)中国煤化工MYHCNMHG