%!PS-Adobe-2.0 %%Creator: dvips 5.495 Copyright 1986, 1992 Radical Eye Software %%Title: paper.dvi %%CreationDate: Tue Aug 22 13:08:23 1995 %%Pages: 5 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSCommandLine: dvips -o paper.ps paper.dvi %DVIPSSource: TeX output 1995.08.22:1305 %%BeginProcSet: tex.pro %! /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N} B /TR{translate}N /isls false N /vsize 11 72 mul N /@rigin{isls{[0 -1 1 0 0 0] concat}if 72 Resolution div 72 VResolution div neg scale isls{Resolution hsize -72 div mul 0 TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{ CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N} B /I{cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook} if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255 {IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V{}B /RV statusdict begin /product where{ pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{ gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{ p 2 w}B /s{p 2 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 39158280 55380996 1000 300 300 (/amdtmp_mnt/onyx/fs8/c89gl/Security/NSPub/paper.dvi) @start /Fa 1 50 df49 D E /Fb 1 1 df0 D E /Fc 4 116 df97 DI105 D115 D E /Fd 3 104 df33 D102 DI E /Fe 1 50 df49 D E /Ff 1 1 df0 D E /Fg 4 108 df75 D97 DI107 D E /Fh 10 110 df58 DI65 DI73 D75 D78 D83 D107 D109 D E /Fi 31 122 df45 D49 DIII65 D67 D73 D78 D82 DII97 DIIIII104 DI107 DIIIII114 DIII121 D E /Fj 70 125 df14 D16 D19 D34 D39 DII44 DII48 DIIIIIIIIIII65 DIIIIIIII76 DII80 D82 DIII87 D91 DII97 DI IIIIIIIIIIIIIIIIIIIIIII123 DI E /Fk 34 122 df36 D58 D65 D67 D69 D73 D75 DII80 D82 D II97 DIIIIIIII107 DIIIII114 DIII119 D121 D E /Fl 26 122 df45 DI73 D78 D83 DI97 DIIII103 DII107 DIIIII114 DIII119 D121 D E /Fm 7 117 df65 D97 DII114 DII E /Fn 19 120 df44 D49 DI53 D57 D65 D71 D76 D97 D101 D103 D105 D110 DI115 DIIII E /Fo 22 122 df45 D65 D75 D78 D80 D83 D97 DIIII104 DI107 DIIII114 D116 DI121 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 195 405 a Fo(An)28 b(A)n(ttac)n(k)h(on)g(the)g(Needham-Sc)n(hro)r (eder)234 509 y(Public-Key)i(Authen)n(tication)g(Proto)r(col)760 656 y Fn(Ga)n(vin)19 b(Lo)n(w)n(e)703 773 y(August)h(22,)f(1995)815 956 y Fm(Abstract)250 1040 y Fl(In)12 b(this)f(pap)q(er)g(w)o(e)g(presen)o(t) g(an)g(attac)o(k)f(up)q(on)h(the)g(Needham-Sc)o(hro)q(eder)i(public-)182 1097 y(k)o(ey)g(authen)o(tication)h(proto)q(col.)19 b(The)13 b(attac)o(k)f(allo)o(ws)h(an)g(in)o(truder)h(to)f(imp)q(ersonate)182 1153 y(another)i(agen)o(t.)60 1263 y Fk(Keywor)n(ds:)30 b Fj(distributed)18 b(systems;)g(securit)o(y)g(in)h(digital)f(systems;)h(authen)o(tication)f (pro-)60 1324 y(to)q(cols;)e(public-k)o(ey)f(cryptograph)o(y)l(.)60 1490 y Fi(1)83 b(In)n(tro)r(duction)60 1599 y Fj(In)27 b(a)h(distributed)e (computer)g(system,)i(it)f(is)g(necessary)g(to)h(ha)o(v)o(e)e(some)g(mec)o (hanism)60 1660 y(whereb)o(y)20 b(a)h(pair)g(of)g(agen)o(ts)g(can)g(b)q(e)g (assured)h(of)f(eac)o(h)f(other's)h(iden)o(tit)o(y|they)d(should)60 1720 y(b)q(ecome)11 b(sure)i(that)h(they)e(really)g(are)h(talking)f(to)h(eac) o(h)g(other,)g(rather)g(than)g(to)h(an)f(imp)q(oster)60 1780 y(imp)q(ersonating)j(the)g(other)g(agen)o(t.)21 b(This)c(is)f(the)g(role)g (of)g(an)h Fk(authentic)n(ation)i(pr)n(oto)n(c)n(ol)p Fj(.)133 1840 y(In)f(this)g(pap)q(er)h(w)o(e)f(consider)g(the)g(Needham-Sc)o(hro)q (eder)e(public-k)o(ey)g(authen)o(tication)60 1900 y(proto)q(col)d([NS78].)19 b(The)13 b(proto)q(col)g(aims)e(to)h(pro)o(vide)g(m)o(utual)e(authen)o (tication,)j(after)f(whic)o(h)60 1961 y(some)20 b(session)h(in)o(v)o(olving)e (the)h(exc)o(hange)h(of)g(messages)f(can)h(tak)o(e)f(place.)34 b(Ho)o(w)o(ev)o(er,)19 b(w)o(e)60 2021 y(sho)o(w)d(that)h(it)e(fails)h(to)g (ensure)f(authen)o(tication:)21 b(w)o(e)15 b(sho)o(w)i(that)f(an)g(in)o (truder)f(can)h(imp)q(er-)60 2081 y(sonate)21 b(an)f(agen)o(t)g Fh(A)f Fj(during)i(a)f(run)g(of)g(the)g(proto)q(col,)h(to)f(tric)o(k)e (another)j(agen)o(t)f Fh(B)i Fj(in)o(to)60 2141 y(thinking)16 b(that)g(he)g(really)g(is)g(talking)g(to)g Fh(A)p Fj(.)133 2201 y(The)23 b(proto)q(col)g(uses)g Fk(public)h(key)g(crypto)n(gr)n(aphy)g Fj([DH76)q(,)e(RSA78].)39 b(Eac)o(h)23 b(agen)o(t)f Fh(A)60 2262 y Fj(p)q(ossesses)h(a)f Fk(public)i(key)p Fj(,)f(denoted)f Fh(K)802 2269 y Fg(a)823 2262 y Fj(,)h(whic)o(h)e(an)o(y)h(other)g(agen)o(t)g (can)g(obtain)g(from)f(a)60 2322 y(k)o(ey)d(serv)o(er.)28 b(It)18 b(also)h(p)q(ossesses)i(a)e Fk(se)n(cr)n(et)h(key)p Fj(,)f Fh(K)1014 2304 y Ff(\000)p Fe(1)1010 2334 y Fg(a)1061 2322 y Fj(,)g(whic)o(h)g(is)f(the)h(in)o(v)o(erse)e(of)i Fh(K)1638 2329 y Fg(a)1659 2322 y Fj(.)29 b(W)l(e)60 2382 y(will)20 b(write)g Fd(f)p Fh(m)p Fd(g)379 2389 y Fg(k)420 2382 y Fj(for)i(message)e Fh(m)g Fj(encrypted)g(with)g(k)o(ey)g Fh(k)r Fj(.)35 b(An)o(y)20 b(agen)o(t)h(can)g(encrypt)60 2442 y(a)f(message)f Fh(m)h Fj(using)g Fh(A)p Fj('s)f(public)g(k)o(ey)g(to)h(pro)q(duce)g Fd(f)p Fh(m)p Fd(g)1165 2449 y Fg(K)1195 2453 y Fc(a)1215 2442 y Fj(;)h(only)f Fh(A)f Fj(can)h(decrypt)f(this)60 2502 y(message,)d(so)i(this)f(ensures)h (secrecy)l(.)23 b Fh(A)17 b Fj(can)g(sign)h(a)f(message)g Fh(m)g Fj(b)o(y)g(encrypting)f(it)h(with)60 2563 y(its)c(secret)g(k)o(ey)l(,)f(to)i (pro)q(duce)g Fd(f)p Fh(m)p Fd(g)689 2576 y Fg(K)721 2561 y Fb(\000)p Fa(1)719 2582 y Fc(a)764 2563 y Fj(;)g(an)o(y)f(other)h(agen)o(t)g (in)f(p)q(ossession)i(of)f Fh(A)p Fj('s)f(public)f(k)o(ey)60 2623 y(can)j(then)g(decrypt)f(this)h(message;)f(the)h(encryption)f(using)h Fh(A)p Fj('s)f(secret)g(k)o(ey)g(should)h(assure)60 2683 y(other)h(agen)o(ts) h(that)g(the)f(message)f(really)g(did)h(originate)h(from)e Fh(A)p Fj(.)903 2856 y(1)p eop %%Page: 2 2 2 1 bop 133 203 a Fj(The)17 b(proto)q(col)g(also)g(uses)g Fk(nonc)n(es)t Fj(:)23 b(random)16 b(n)o(um)o(b)q(ers)f(generated)h(with)h(the)f(purp)q(ose) 60 264 y(of)i(b)q(eing)g(used)g(in)g(a)g Fk(single)23 b Fj(run)18 b(of)g(the)g(proto)q(col.)26 b(W)l(e)18 b(denote)g(nonces)g(b)o(y)f Fh(N)1565 271 y Fg(a)1604 264 y Fj(and)h Fh(N)1739 271 y Fg(b)1756 264 y Fj(:)60 324 y(the)12 b(subscripts)h(are)g(in)o(tended)f(to)h(denote)f (that)h(the)g(nonces)g(w)o(ere)f(generated)g(b)o(y)g Fh(A)h Fj(and)g Fh(B)s Fj(,)60 384 y(resp)q(ectiv)o(ely)l(.)60 550 y Fi(2)83 b(The)24 b(Needham-Sc)n(hro)r(eder)f(public-k)n(ey)f(authen-)184 642 y(tication)27 b(proto)r(col)60 751 y Fj(The)c(Needham-Sc)o(hro)q(eder)e (public-k)o(ey)f(proto)q(col)k(in)o(v)o(olv)o(es)d(sev)o(en)g(steps,)k(and)e (can)g(b)q(e)60 811 y(describ)q(ed)16 b(as)h(follo)o(ws:)627 858 y(1)p Fh(:)45 b(A)13 b Fd(!)h Fh(S)48 b Fj(:)41 b Fh(A;)8 b(B)627 918 y Fj(2)p Fh(:)45 b(S)17 b Fd(!)c Fh(A)45 b Fj(:)c Fd(f)p Fh(K)1023 925 y Fg(b)1040 918 y Fh(;)8 b(B)s Fd(g)1127 932 y Fg(K)1159 917 y Fb(\000)p Fa(1)1157 938 y Fc(s)627 980 y Fj(3)p Fh(:)42 b(A)13 b Fd(!)h Fh(B)44 b Fj(:)d Fd(f)p Fh(N)1021 987 y Fg(a)1042 980 y Fh(;)8 b(A)p Fd(g)1126 987 y Fg(K)1156 993 y Fc(b)627 1040 y Fj(4)p Fh(:)43 b(B)17 b Fd(!)d Fh(S)46 b Fj(:)41 b Fh(B)s(;)8 b(A)627 1100 y Fj(5)p Fh(:)43 b(S)17 b Fd(!)d Fh(B)46 b Fj(:)41 b Fd(f)p Fh(K)1023 1107 y Fg(a)1044 1100 y Fh(;)8 b(A)p Fd(g)1128 1114 y Fg(K)1160 1099 y Fb(\000)p Fa(1)1158 1120 y Fc(s)627 1162 y Fj(6)p Fh(:)42 b(B)16 b Fd(!)e Fh(A)41 b Fj(:)g Fd(f)p Fh(N)1021 1169 y Fg(a)1042 1162 y Fh(;)8 b(N)1103 1169 y Fg(b)1120 1162 y Fd(g)1145 1169 y Fg(K)1175 1173 y Fc(a)627 1222 y Fj(7)p Fh(:)42 b(A)13 b Fd(!)h Fh(B)44 b Fj(:)d Fd(f)p Fh(N)1021 1229 y Fg(b)1038 1222 y Fd(g)1063 1229 y Fg(K)1093 1235 y Fc(b)1119 1222 y Fh(:)60 1306 y Fj(Here)13 b Fh(A)g Fj(is)h(in)g Fk(initiator)19 b Fj(who)c(seeks)f(to)g(establish)g(a)g (session)h(with)e Fk(r)n(esp)n(onder)19 b Fh(B)s Fj(,)13 b(with)h(the)60 1366 y(help)d(of)i(trusted)f(k)o(ey)f(serv)o(er)f Fh(S)s Fj(.)20 b(In)12 b(step)g(1,)h Fh(A)e Fj(sends)i(a)f(message)f(to)i(the)e(serv)o(er,)h (requesting)60 1426 y Fh(B)s Fj('s)20 b(public)f(k)o(ey)l(.)33 b Fh(S)23 b Fj(resp)q(onds)f(in)e(message)g(2)h(b)o(y)e(returning)i(the)f(k)o (ey)f Fh(K)1488 1433 y Fg(b)1506 1426 y Fj(,)i(along)g(with)60 1487 y Fh(B)s Fj('s)c(iden)o(tit)o(y)e(\(to)j(prev)o(en)o(t)e(attac)o(ks)h (based)h(up)q(on)h(div)o(erting)d(k)o(ey)g(deliv)o(eries\),)f(encrypted)60 1547 y(using)j Fh(S)s Fj('s)g(secret)f(k)o(ey)g(\(to)h(assure)h Fh(A)e Fj(that)i(this)e(message)h(originated)g(from)e Fh(S)s Fj(\).)27 b Fh(A)17 b Fj(then)60 1607 y(seeks)h(to)h(establish)g(a)g (connection)g(with)f Fh(B)k Fj(b)o(y)c(selecting)f(a)j(nonce)e Fh(N)1407 1614 y Fg(a)1428 1607 y Fj(,)h(and)h(sending)e(it)60 1667 y(along)g(with)e(its)h(iden)o(tit)o(y)d(to)k Fh(B)h Fj(\(message)d(3\),) h(encrypted)e(using)j Fh(B)s Fj('s)e(public)g(k)o(ey)l(.)21 b(When)60 1727 y Fh(B)k Fj(receiv)o(es)c(this)h(message,)h(it)f(decrypts)g (the)h(message)e(to)i(obtain)g(the)g(nonce)f Fh(N)1658 1734 y Fg(a)1679 1727 y Fj(.)40 b(It)60 1787 y(requests)14 b(\(message)g(4\))h (and)g(receiv)o(es)e(\(message)h(5\))h Fh(A)p Fj('s)f(public)f(k)o(ey)l(.)20 b(It)14 b(then)h(returns)f(the)60 1848 y(nonce)g Fh(N)235 1855 y Fg(a)256 1848 y Fj(,)h(along)g(with)g(a)f(new)h(nonce)g Fh(N)836 1855 y Fg(b)853 1848 y Fj(,)f(to)h Fh(A)p Fj(,)f(encrypted)g(with)g Fh(A)p Fj('s)g(k)o(ey)f(\(message)h(6\).)60 1908 y(When)23 b Fh(A)g Fj(receiv)o(es)e(this)i(message)f(he)h(should)h(b)q(e)f(assured)h (that)g(he)f(is)g(talking)f(to)i Fh(B)s Fj(,)60 1968 y(since)16 b(only)h Fh(B)j Fj(should)e(b)q(e)f(able)g(to)h(decrypt)e(message)g(3)i(to)g (obtain)f Fh(N)1393 1975 y Fg(a)1414 1968 y Fj(.)24 b Fh(A)17 b Fj(then)g(returns)60 2028 y(the)i(nonce)g Fh(N)327 2035 y Fg(b)364 2028 y Fj(to)g Fh(B)s Fj(,)g(encrypted)g(with)g Fh(B)s Fj('s)f(k)o(ey)l(.)29 b(When)20 b Fh(B)h Fj(receiv)o(es)d(this)h(message)f (he)60 2088 y(should)e(b)q(e)f(assured)g(that)h(he)f(is)g(talking)f(to)i Fh(A)p Fj(,)e(since)g(only)h Fh(A)g Fj(should)g(b)q(e)h(able)e(to)i(decrypt) 60 2149 y(message)g(6)g(to)h(obtain)g Fh(N)539 2156 y Fg(b)556 2149 y Fj(.)133 2209 y(This)j(proto)q(col)g(can)g(b)q(e)f(considered)g(as)h (the)g(in)o(terlea)o(ving)d(of)j(t)o(w)o(o)f(logically)g(disjoin)o(t)60 2269 y(proto)q(cols:)37 b(messages)24 b(1,)h(2,)h(4)e(and)g(5)h(are)e (concerned)h(with)f(obtaining)i(public)d(k)o(eys,)60 2329 y(whereas)17 b(messages)e(3,)h(6)h(and)g(7)g(are)f(concerned)g(with)g(the)g(authen)o (tication)f(of)i Fh(A)f Fj(and)h Fh(B)s Fj(.)133 2389 y(Denning)k(and)f (Sacco)h([DS81)q(])f(ha)o(v)o(e)f(p)q(oin)o(ted)h(out)h(that)g(this)f(proto)q (col)h(pro)o(vides)f(no)60 2450 y(guaran)o(tee)e(that)g(the)g(public)f(k)o (eys)f(obtained)i(are)g(curren)o(t,)f(rather)h(than)g(repla)o(ys)f(of)h(old,) 60 2510 y(p)q(ossibly)g(compromised)d(k)o(eys.)24 b(This)18 b(problem)e(can)h(b)q(e)h(o)o(v)o(ercome)d(in)i(v)m(arious)h(w)o(a)o(ys,)g (for)60 2570 y(example)c(b)o(y)i(including)f(timestamps)f(in)i(the)g(k)o(ey)f (deliv)o(eries.)133 2630 y(In)h(this)g(pap)q(er)g(w)o(e)g(will)f(assume)g (that)i(eac)o(h)e(agen)o(t)i(initially)d(has)i(eac)o(h)g(other's)g(public)903 2856 y(2)p eop %%Page: 3 3 3 2 bop 60 203 a Fj(k)o(ey)l(,)15 b(and)h(restrict)g(our)g(atten)o(tion)g(to) h(just)f(the)g(follo)o(wing)g(messages:)631 296 y(3)p Fh(:)41 b(A)14 b Fd(!)f Fh(B)45 b Fj(:)c Fd(f)p Fh(N)1025 303 y Fg(a)1045 296 y Fh(;)8 b(A)p Fd(g)1129 303 y Fg(K)1159 309 y Fc(b)631 356 y Fj(6)p Fh(:)41 b(B)17 b Fd(!)c Fh(A)42 b Fj(:)f Fd(f)p Fh(N)1025 363 y Fg(a)1045 356 y Fh(;)8 b(N)1106 363 y Fg(b)1123 356 y Fd(g)1148 363 y Fg(K)1178 367 y Fc(a)631 416 y Fj(7)p Fh(:)41 b(A)14 b Fd(!)f Fh(B)45 b Fj(:)c Fd(f)p Fh(N)1025 423 y Fg(b)1042 416 y Fd(g)1067 423 y Fg(K)1097 429 y Fc(b)1122 416 y Fh(:)60 562 y Fi(3)83 b(An)27 b(attac)n(k)g(on)h(the)f(proto)r(col)60 671 y Fj(W)l(e)21 b(will)e(consider)i(ho)o(w)g(an)g(in)o(truder)f(can)h(in)o (teract)f(with)h(this)f(proto)q(col.)36 b(W)l(e)21 b(assume)60 731 y(that)e(the)g(in)o(truder)f Fh(I)k Fj(is)d(a)g(user)g(of)g(the)g (computer)e(net)o(w)o(ork,)i(and)g(so)h(is)e(able)h(to)g(set)g(up)60 792 y(standard)e(sessions)g(with)e(other)h(agen)o(ts,)g(and)h(other)f(agen)o (ts)g(ma)o(y)f(try)g(to)h(set)g(up)g(sessions)60 852 y(with)d Fh(I)t Fj(|indeed,)f(the)h(attac)o(k)g(b)q(elo)o(w)h(starts)g(with)f(agen)o (t)h Fh(A)f Fj(trying)g(to)h(establish)f(a)h(session)60 912 y(with)j Fh(I)t Fj(.)24 b(W)l(e)17 b(assume)f(that)i(the)f(in)o(truder)f(can) i(in)o(tercept)d(an)o(y)i(messages)g(in)g(the)g(system,)60 972 y(and)d(in)o(tro)q(duce)e(new)i(messages.)19 b(Ho)o(w)o(ev)o(er,)12 b(w)o(e)g(ha)o(v)o(e)h(to)g(mak)o(e)f(some)g(assumptions)h(ab)q(out)60 1032 y(what)k(sort)g(of)f(messages)g(the)g(in)o(truder)f(ma)o(y)g(in)o(tro)q (duce.)21 b(W)l(e)16 b(assume)f(that)i(the)f(in)o(truder)60 1093 y(cannot)d(guess)g(the)f(v)m(alue)g(of)h(nonces)f(b)q(eing)h(passed)g (in)f(encrypted)f(messages,)h(unless)h(those)60 1153 y(messages)19 b(are)g(encrypted)f(with)h(his)h(o)o(wn)f(k)o(ey)l(.)29 b(Th)o(us)20 b(the)f(in)o(truder)f(can)i(only)f(pro)q(duce)60 1213 y(new)e(messages)g (using)g(nonces)h(that)g(it)e(in)o(v)o(en)o(ted)f(itself,)h(or)i(that)f(it)g (has)h(previously)e(seen)60 1273 y(and)21 b(understo)q(o)q(d.)37 b(It)20 b(can)h(also)h(repla)o(y)e(complete)e(encrypted)i(messages,)h(ev)o (en)f(if)g(it)g(is)60 1333 y(unable)c(to)h(understand)g(the)f(con)o(ten)o (ts.)133 1393 y(The)26 b(attac)o(k)f(on)i(the)e(proto)q(col)i(allo)o(ws)e(an) i(in)o(truder)d Fh(I)30 b Fj(to)c(imp)q(ersonate)e(another)60 1454 y(agen)o(t)d Fh(A)g Fj(to)g(set)g(up)g(a)h(false)f(session)g(with)g Fh(B)s Fj(.)35 b(The)21 b(attac)o(k)g(in)o(v)o(olv)o(es)e(t)o(w)o(o)i(sim)o (ultane-)60 1514 y(ous)c(runs)g(of)f(the)g(proto)q(col:)22 b(in)16 b(run)g(1,)h Fh(A)e Fj(establishes)h(a)h(v)m(alid)f(session)g(with)h Fh(I)t Fj(;)e(in)h(run)g(2,)60 1574 y Fh(I)g Fj(imp)q(ersonates)c Fh(A)h Fj(to)g(establish)f(a)h(fak)o(e)g(session)g(with)f Fh(B)s Fj(.)20 b(Belo)o(w)12 b(w)o(e)g(write,)h(for)g(example,)60 1634 y(1.3)h(to)h(represen)o(t)e(message)g(3)i(in)e(run)i(1;)f(w)o(e)g(write) g Fh(I)t Fj(\()p Fh(A)p Fj(\))f(to)h(represen)o(t)f(the)h(in)o(truder)f Fh(I)18 b Fj(im-)60 1694 y(p)q(ersonating)f Fh(A)p Fj(:)550 1750 y(1)p Fh(:)p Fj(3)p Fh(:)105 b(A)13 b Fd(!)h Fh(I)119 b Fj(:)41 b Fd(f)p Fh(N)1105 1757 y Fg(a)1126 1750 y Fh(;)8 b(A)p Fd(g)1210 1757 y Fg(K)1240 1762 y Fc(i)550 1811 y Fj(2)p Fh(:)p Fj(3)p Fh(:)41 b(I)t Fj(\()p Fh(A)p Fj(\))13 b Fd(!)h Fh(B)104 b Fj(:)41 b Fd(f)p Fh(N)1105 1818 y Fg(a)1126 1811 y Fh(;)8 b(A)p Fd(g)1210 1818 y Fg(K)1240 1824 y Fc(b)550 1871 y Fj(2)p Fh(:)p Fj(6)p Fh(:)102 b(B)16 b Fd(!)e Fh(I)t Fj(\()p Fh(A)p Fj(\))40 b(:)h Fd(f)p Fh(N)1105 1878 y Fg(a)1126 1871 y Fh(;)8 b(N)1187 1878 y Fg(b)1204 1871 y Fd(g)1229 1878 y Fg(K)1259 1882 y Fc(a)550 1931 y Fj(1)p Fh(:)p Fj(6)p Fh(:)116 b(I)17 b Fd(!)d Fh(A)104 b Fj(:)41 b Fd(f)p Fh(N)1105 1938 y Fg(a)1126 1931 y Fh(;)8 b(N)1187 1938 y Fg(b)1204 1931 y Fd(g)1229 1938 y Fg(K)1259 1942 y Fc(a)550 1991 y Fj(1)p Fh(:)p Fj(7)p Fh(:)105 b(A)13 b Fd(!)h Fh(I)119 b Fj(:)41 b Fd(f)p Fh(N)1105 1998 y Fg(b)1123 1991 y Fd(g)1148 1998 y Fg(K)1178 2003 y Fc(i)550 2051 y Fj(2)p Fh(:)p Fj(7)p Fh(:)g(I)t Fj(\()p Fh(A)p Fj(\))13 b Fd(!)h Fh(B)104 b Fj(:)41 b Fd(f)p Fh(N)1105 2058 y Fg(b)1123 2051 y Fd(g)1148 2058 y Fg(K)1178 2064 y Fc(b)1203 2051 y Fh(:)60 2130 y Fj(In)16 b(step)f(1.3,)h Fh(A)g Fj(starts)g(to)g (establish)g(a)g(normal)f(session)i(with)e Fh(I)t Fj(,)g(sending)h(it)g(a)g (nonce)g Fh(N)1736 2137 y Fg(a)1756 2130 y Fj(.)60 2190 y(In)d(step)h(2.3,)f (the)h(in)o(truder)e(imp)q(ersonates)h Fh(A)g Fj(to)h(try)f(to)g(establish)h (a)g(false)f(session)h(with)f Fh(B)s Fj(,)60 2250 y(sending)19 b(it)e(the)h(nonce)h Fh(N)555 2257 y Fg(a)594 2250 y Fj(obtained)g(in)f(the)g (previous)g(message.)27 b Fh(B)21 b Fj(resp)q(onds)e(in)f(mes-)60 2310 y(sage)j(2.6)g(b)o(y)g(selecting)e(a)i(new)g(nonce)g Fh(N)860 2317 y Fg(b)877 2310 y Fj(,)g(and)h(trying)e(to)h(return)g(it,)f(along)i (with)f Fh(N)1736 2317 y Fg(a)1756 2310 y Fj(,)60 2370 y(to)e Fh(A)p Fj(.)27 b(The)18 b(in)o(truder)g(in)o(tercepts)f(this)h(message,)g (but)g(cannot)h(decrypt)f(it)g(b)q(ecause)g(it)g(is)60 2430 y(encrypted)g(with)g Fh(A)p Fj('s)g(k)o(ey)l(.)27 b(The)18 b(in)o(truder)g(therefore)f(seeks)i(to)f(use)h Fh(A)f Fj(as)h(an)g(oracle,)g (b)o(y)60 2491 y(forw)o(arding)14 b(the)g(message)e(to)i Fh(A)g Fj(in)f(message)g(1.6;)h(note)g(that)g(this)g(message)e(is)i(of)g(the)f(form) 60 2551 y(exp)q(ected)f(b)o(y)h Fh(A)f Fj(in)h(run)g(1)h(of)f(the)g(proto)q (col.)21 b Fh(A)13 b Fj(decrypts)g(the)f(message)h(to)g(obtain)h Fh(N)1647 2558 y Fg(b)1664 2551 y Fj(,)f(and)60 2611 y(returns)k(this)h(to)g Fh(I)i Fj(in)d(message)g(1.7.)25 b Fh(I)c Fj(can)d(then)f(decrypt)g(this)g (message)g(to)g(obtain)h Fh(N)1739 2618 y Fg(b)1756 2611 y Fj(,)60 2671 y(whic)o(h)k(it)g(returns)g(to)h Fh(B)i Fj(in)d(message)f(2.7,)j (th)o(us)e(completing)f(run)h(2)h(of)g(the)f(proto)q(col.)60 2731 y(Hence)15 b Fh(B)k Fj(b)q(eliev)o(es)14 b(that)j Fh(A)f Fj(has)h(correctly)e(established)g(a)i(session)g(with)f(it.)903 2856 y(3)p eop %%Page: 4 4 4 3 bop 133 203 a Fj(W)l(e)29 b(should)h(consider)f(the)g(consequences)f(of)i (this)f(attac)o(k.)60 b(It)29 b(has)h(b)q(een)f(sug-)60 264 y(gested)20 b([NS78,)f(BAN89)o(])h(that)g(b)q(ecause)g(the)f(nonces)h(are)g Fk(shar)n(e)n(d)f(se)n(cr)n(ets)p Fj(,)h(they)f(can)h(b)q(e)60 324 y(included)12 b(within)g(subsequen)o(t)h(messages)f(as)i(authen)o (tication.)19 b(Ho)o(w)o(ev)o(er,)12 b(after)g(the)h(ab)q(o)o(v)o(e)60 384 y(attac)o(k,)h(the)h(in)o(truder)f(kno)o(ws)h(the)f(nonces,)h(and)h(so)f (he)g(ma)o(y)e(con)o(tin)o(ue)g(to)j(imp)q(ersonate)d Fh(A)60 444 y Fj(to)i(send)f(messages)g(to)h Fh(B)i Fj(during)d(the)g(session.)21 b(F)l(or)15 b(example,)d(the)i(in)o(truder)f(ma)o(y)g(include)60 504 y(the)j(nonces)g(within)f(a)h(subsequen)o(t)g(message)f(suggesting)h(a)h (session)f(k)o(ey)l(,)e(and)j Fh(B)h Fj(will)d(b)q(e-)60 565 y(liev)o(e)e(that)j(this)f(message)f(originated)i(from)e Fh(A)p Fj(.)20 b(Similarly)l(,)12 b(if)j Fh(B)j Fj(is)d(a)g(bank,)g(then)h Fh(I)i Fj(could)60 625 y(imp)q(ersonate)d Fh(A)h Fj(to)h(send)f(a)h(message)e (suc)o(h)h(as:)203 715 y Fh(I)t Fj(\()p Fh(A)p Fj(\))c Fd(!)i Fh(B)j Fj(:)c Fd(f)p Fh(N)525 722 y Fg(a)546 715 y Fh(;)8 b(N)607 722 y Fg(b)624 715 y Fh(;)g Fj(\\T)l(ransfer)17 b Fk($)p Fj(1000)g(from)e(m)o (y)g(accoun)o(t)h(to)g Fh(I)t Fj('s")p Fd(g)1558 722 y Fg(K)1588 728 y Fc(b)1614 715 y Fh(:)60 879 y Fi(4)83 b(Conclusions)60 988 y Fj(In)13 b(this)h(pap)q(er)g(w)o(e)f(ha)o(v)o(e)g(presen)o(ted)g(an)h (attac)o(k)f(on)h(the)g(w)o(ell)e(kno)o(wn)i(Needham-Sc)o(hro)q(eder)60 1048 y(public-k)o(ey)g(authen)o(tication)h(proto)q(col;)h(the)f(attac)o(k)h (allo)o(ws)f(an)h(in)o(truder)f(to)h(imp)q(ersonate)60 1109 y(one)g(agen)o(t)h(in)f(a)g(session)h(with)f(another.)133 1169 y(It)22 b(is)f(fairly)g(easy)h(to)g(c)o(hange)g(the)f(proto)q(col)i(so)f(as)h (to)f(prev)o(en)o(t)e(the)i(attac)o(k.)37 b(If)21 b(w)o(e)60 1229 y(include)15 b(the)h(resp)q(onder's)h(iden)o(tit)o(y)d(in)i(message)f(6) i(of)f(the)g(proto)q(col:)589 1319 y(6)p Fh(:)42 b(B)16 b Fd(!)e Fh(A)41 b Fj(:)g Fd(f)p Fh(B)s(;)8 b(N)1045 1326 y Fg(a)1065 1319 y Fh(;)g(N)1126 1326 y Fg(b)1143 1319 y Fd(g)1168 1326 y Fg(K)1198 1330 y Fc(a)1227 1319 y Fh(;)60 1410 y Fj(then)16 b(step)g(2.6)h(of)f(the)g(attac)o(k)h(w)o(ould)f(b)q(ecome)539 1500 y(2)p Fh(:)p Fj(6)p Fh(:)41 b(B)16 b Fd(!)e Fh(I)t Fj(\()p Fh(A)p Fj(\))41 b(:)g Fd(f)p Fh(B)s(;)8 b(N)1096 1507 y Fg(a)1116 1500 y Fh(;)g(N)1177 1507 y Fg(b)1194 1500 y Fd(g)1219 1507 y Fg(K)1249 1511 y Fc(a)1278 1500 y Fh(;)60 1591 y Fj(and)15 b(the)f(in)o(truder)f(can)h(not)h(successfully)e(repla)o(y)g(this)h(message)g (in)g(message)f(1.6,)i(b)q(ecause)60 1651 y Fh(A)j Fj(is)h(exp)q(ecting)f(a)h (message)g(con)o(taining)f Fh(I)t Fj('s)g(iden)o(tit)o(y)l(.)27 b(This)19 b(correction)f(represen)o(ts)h(an)60 1711 y(instance)d(of)g (Principle)f(3)i(of)f([AN94]:)182 1796 y(If)11 b(the)h(iden)o(tit)o(y)e(of)j (a)f(principal)f(is)h(essen)o(tial)f(to)h(the)g(meaning)f(of)h(a)h(message,)f (it)182 1856 y(is)k(pruden)o(t)g(to)g(men)o(tion)e(the)i(principal's)f(name)g (explicitly)f(in)h(the)h(message.)133 1941 y(W)l(e)i(conjecture)f(that)i(the) f(revised)f(proto)q(col)h(is)g(safe)h(against)g(all)e(attac)o(ks|at)i(least,) 60 2001 y(those)24 b(attac)o(ks)f(not)h(dep)q(enden)o(t)f(up)q(on)h(prop)q (erties)f(of)h(the)f(encryption)g(metho)q(d)f(used.)60 2061 y(Pro)o(ving)16 b(this)g(formally)f(is)h(the)g(topic)g(of)g(curren)o(t)g (researc)o(h.)60 2225 y Fi(References)60 2334 y Fj([AN94])58 b(Mart)-5 b(\023)-19 b(\020n)19 b(Abadi)h(and)g(Roger)g(Needham.)29 b(Pruden)o(t)19 b(engineering)g(practice)g(for)268 2395 y(cryptographic)14 b(proto)q(cols.)k(Researc)o(h)c(Rep)q(ort)g(125,)h(Digital)f(Equipmen)o(t)d (Cor-)268 2455 y(p)q(oration)17 b(Systems)e(Researc)o(h)h(Cen)o(ter,)f(1994.) 60 2551 y([BAN89])23 b(Mic)o(hael)17 b(Burro)o(ws,)i(Mart)-5 b(\023)-19 b(\020n)18 b(Abadi,)h(and)g(Roger)g(Needham.)27 b(A)18 b(logic)g(of)h(au-)268 2611 y(then)o(tication.)28 b Fk(Pr)n(o)n(c)n(e)n(e)n(dings)18 b(of)i(the)g(R)n(oyal)f(So)n(ciety)h(of)g(L) n(ondon)f(A)p Fj(,)g(426:233{)268 2671 y(271,)f(1989.)25 b(A)17 b(preliminary)d(v)o(ersion)j(app)q(eared)h(as)g(Digital)e(Equipmen)o(t)f (Cor-)268 2731 y(p)q(oration)i(Systems)e(Researc)o(h)h(Cen)o(ter)f(rep)q(ort) i(No.)f(39,)g(1989.)903 2856 y(4)p eop %%Page: 5 5 5 4 bop 60 203 a Fj([DH76])58 b(W.)23 b(Di\016e)f(and)i(M.)e(Hellman.)39 b(New)23 b(directions)f(in)h(cryptograph)o(y)l(.)42 b Fk(IEEE)268 264 y(T)l(r)n(ansactions)17 b(on)h(Information)f(The)n(ory)p Fj(,)e(22:644{654,)k(1976.)60 365 y([DS81])68 b(Doroth)o(y)21 b(E.)g(Denning)g(and)g(Gio)o(v)m(anni)g(Maria)f(Sacco.)35 b(Timestamps)19 b(in)h(k)o(ey)268 425 y(distribution)h(proto)q(cols.)39 b Fk(Communic)n (ations)23 b(of)f(the)h(A)o(CM)p Fj(,)e(24\(8\):533{536,)268 486 y(1981.)60 587 y([NS78])68 b(Roger)17 b(Needham)f(and)h(Mic)o(hael)f(Sc)o (hro)q(eder.)23 b(Using)17 b(encryption)f(for)h(authen-)268 648 y(tication)e(in)g(large)h(net)o(w)o(orks)f(of)h(computers.)i Fk(Communic)n(ations)f(of)g(the)g(A)o(CM)p Fj(,)268 708 y(21\(12\):993{999)q (,)h(1978.)60 809 y([RSA78])32 b(R.)21 b(L.)h(Riv)o(est,)g(A.)f(Shamir,)h (and)h(L.)f(Adleman.)36 b(A)22 b(metho)q(d)f(for)h(obtaining)268 870 y(digital)f(signatures)h(and)g(public-k)o(ey)d(cryptosystems.)35 b Fk(Communic)n(ations)22 b(of)268 930 y(the)c(A)o(CM)p Fj(,)d (21\(2\):120{126)q(,)j(F)l(ebruary)e(1978.)903 2856 y(5)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF