United States Patent [19]
`Rogaway
`
`11111111111111111111111111111111 1111111111111111111111111111111111111111111
`5,491,749
`Feb. 13, 1996
`
`[11] Patent Number:
`[45] Date of Patent:
`
`[54] 如1ETHOD AND APPARATUS FOR ENTITY
`AUTHENTICATION AND KEY
`DISTRlBUTION SECURE AGAINST
`OFF-L剧E ADVERSARIAL ATTACKS
`
`[7句Inventor: Phillip W. Rogaway, Austin, Tex.
`
`[73] Assigoee: Ioternational Business Machines
`Corporation, Annonk, N.Y.
`
`[21) Appl. No.: 175,881
`Dcc. 30, 1993
`[2勾 Filed:
`[51] IoιCI.6 ………"…..………"…….........…..... H04L 9/08
`[52) U.S. CI. ................…………"…·…......... 380/21; 380/25
`[58) Field of Search ………………..…........... 3801剑， 23-25;
`340/825.31
`
`[56]
`
`References Cited
`
`U.S. PA'τ卫NT DOCl.Th但NTS
`
`3/1980. Lennon et al. …………...……·… 380.121
`4,193.131
`4,438,824
`3/1984 Mueller-Schlωr ....................... 380.尼1
`4,549,0.75 10./1985 Saada el al. ........…............. 380.125
`4,588,985 5/1986 Carter et al. ......…………·… 340/825.31
`4,720..859
`1/1988 A缸。 et al. .............……….......... 380.125
`211988 Munck el al. ............…..……… 380.125
`4,723,284
`4,799.061
`1/1989 Abraham et al. ......…................ 380.123
`4,80.5,216
`211989 Gruenb仅E …"………………… 380.尼1
`5,148,479 9/1992 Bù吐 et al. .....………..………….... 380.尼5
`5,153,919 10./1992 Reeds，皿 el al. ..…"…·…......... 380.尼1
`5,241,599
`8/1993 BeJlovin et al. ……"……...……... 380.121
`5,299,263 3/1994 BelJer et al. ...……………-……... 380.121
`1万1994 Difli.e et al. ……...........…......... 380.尼1
`5,371,294
`
`。ηffiR PUBLlC且lONS
`
`R. R. Juenema口， S. M. Matyas, C. H. Meyer, "Message
`Authentication", Sep. 1985, vol. 23, No. 9, pp. 2弘-40.
`R. Bird, et al., "Systematic Design of a Family of
`
`Attack- Resistant Authenticalion Proto∞，1s飞 Jun. 1993, pp.
`1-28.
`Steven M. Bellovin, Micbael Me时[t， "Encrypted Key
`Excbange: Password-Based 玩otocols Secure Against Dic(cid:173)
`tionary Attacks", pp. 1- 13.
`T. Mark A. Lomas, et al. "Reducing Risks from Poorly
`Chosen Keys飞 pp.I4-18.
`Li Gong, el al. "Protecting Poorly Chosen Secrets from
`Guessing Attacks", Sep. 25, 1992, pp. 1- 18.
`Refik Molva, et al., "Research Report, KryptoKrùgbt
`Authentication and K巳yDis时bution Syslem", Apr. 1, 1992,
`pp. 1-17.
`
`Primary Examiner-Salvatore Cangialosj
`Allomey, Agenl. or Fiml-Jeffrey S. LaBaw; Melvin A.
`Hunn; Andrew 1. Dillon
`
`[57]
`
`ABSTRACT
`
`A melhod is described for substantially concurrent1y per(cid:173)
`fo口ning entity authentication operations and shon礼ived
`seα'et k巳y distribution operations over an insec町e commu(cid:173)
`nication channel between communication parlners, wherein
`au出enticity of communication p缸tners is determined by
`possession of thc 10ng-lived shared secret k巳y. Tbc method
`inc1udes a number of steps. Data fiows 缸e exchanged
`between the communication p缸tners to defin巳 a composite
`key. At least a portion of the data fiows have been encrypted
`or otberwisc masked in a manner which utilizes the 10ng(cid:173)
`lived sbared secret key. At least on巳 authentication tag is
`passed between communication p缸tners. over the commu(cid:173)
`nication channel. Tbe at least one aulhentication tag is based
`at leasl p缸咀刽ly upon the composite key. Tbe authentication
`tag is uti1izcd to determine the authenticity of at 1巳ast one
`commurucabon partner.
`
`24 Clairns, 4 Drawing Sbeets
`
`Aô ①丁ex门， EJuα)
`
`Te×T2， E;(gPLhJ(B， AsTe×↑川ex↑2， Ej(gα)， E;(g 町， σ)
`
`因υ
`
`②
`
`③ Te×qd(E;(抖，丁时3， 9 aß )
`
`Where σ = 9α，
`
`1
`
`

`

`u.s. Patent
`
`Feb. 13, 1996
`
`Sheet 1 of 4
`
`5,491,749
`
`RAJ T ex(cid:157)
`Aô ①
`
`i
`
`Ba
`
`-RBJ T ext2J ha (BJ AJ RAJ RB J T ex(cid:157) L Tex↑2) ②
`
`③ Tex口，时 (RAJTex↑3)
`
`•
`
`FIG. 1
`PRIOR ART
`
`A ①
`
`α 9
`F 9
`
`B
`
`②
`
`Where σ = H 1 (9αß)
`
`FIG. 2
`PRIOR ART
`
`2
`
`

`

`u.s. Patent
`
`Feb. 13, 1996
`
`Sheet 2 of 4
`
`5,491,749
`
`A8 ①
`
`Ea (gα)
`
`ε;(gF)
`
`B8
`
`②
`
`Where σ= H, (gαP)
`
`FIG. 3
`PRIOR ART
`
`3
`
`

`

`u.s. Patent
`c m
`
`Feb. 13, 1996
`
`Sheet 3 of 4
`
`5,491,749
`
`。
`
`、事
`
`-OHF陆
`
`电
`
`60
`
`11
`b
`
`。LOL3
`
`(航飞60
`
`俨〕
`+(cid:173)
`X
`O
`
`(cid:157)
`
`飞 。
`
`〉
`
`('\1(0 w
`N (O
`i二
`
`σ3
`+-
`×
`
`ω (cid:157)
`@
`
`(b『(飞。)忖山『
`
`(60)节付←xω← J←×φ←『〈『囚)叫王『(也。)
`
`('\1(0 w
`『N
`
`←xo←
`
`"胃、
`
`6
`
`)叮ω
`
`J←×ω←
`
`。
`ω〈
`
`4
`
`

`

`u.s. Patent
`
`US. Patent
`
`Feb. 13, 1996
`Feb. 13, 1996
`
`Sheet 4 of 4
`Sheet 4 of 4
`
`5,491,749
`5,491,749
`
`-r
`
`l(j
`
`FIG.5
`
`-OHF陶
`
`.....
`<.0
`
`
`SERVER 3&6
`GATEWAY
`LOCALAREANETWORK
`
`
`NETWORK
`
`f气、
`
`∞
`
`
`
`5
`
`

`

`5,491,749
`
`1
`R钮TBOD AND APPARATUS FOR ENTITY
`AUTBENTICATION AND KEY
`DISTRIBUTION SECURE AGAINST
`OFF.LINE ADVERSARIAL ATTACKS
`
`BACKGROUND OF THE 即VENτ10N
`
`2
`由an is absolutely nc∞ssary， and i1 is further useful to 伊缸d
`ag创nst "replay anacks" across tbe communication sessions
`wbich commuoicating p彼tners may engage În. Typically,
`the long-lived and sharcd secrel key is utilized only during
`s cntity autbentication opcrations. Immediatcly after authcn.
`tication of the communica归g parties is obtained, the short(cid:173)
`lived and s∞ret session kcy is distributed and utilized to
`a1low comrnunication back and fortb belween 出巳 P缸tiesin
`tbat particu1ar sessioo, 10 be autbcnticat，时， eo<汀ypted， or
`both.
`Thc 也ird broad industry goal is tbat of ass町iog a com.
`municating party wbich has received data over an insecure
`line tbat tb巳 data has not been modified in transit. Oft阳，
`such mωsage autbenticalion is acbieved by having the
`originating p红ty compu1e a short "autbentication tag" as a
`fuoction of tbe m巳ssage being transrnitted and 由es优rctkcy
`shared by the communicating p缸tners. This autbentication
`tag is typicaHy appeoded to tb巳 data stream wlúch is being
`communicated betwecn th巳 parties. Upon receipt of th巳 data
`stream and autbentication tag. tbc r∞巳iving p缸ty analyzes
`由e au山entic甜00 tag by perforrning lhe same operations
`wbich were performed upon thc data sel by thc sending party
`to generate its own 扭曲emication tag. If tbe sender's 扭曲en­
`lication tag matchcs identically 由e receiver's authcnticated
`tag, tbeo the recipient of tb巳 data can be assured 也al tbe dala
`has 001 beeo altered in any way. This type of protection
`prevents an active adversary 仕om enlering tbe insecurc
`communication channel and meddling with the data.
`In devising security systcms for alJowing secure commu.
`nication between communication p缸tners， it is geoerally
`assumed 由at an adversary may bc (1) passive and perform
`eavesdropping operations to monitor and record all commu.
`nications between tbe p缸ties in 由edis创buted data process(cid:173)
`ing system. or (2) active and actually part:icipate in commu-
`nications wi也扭曲e distributed data pr以范ssing system by
`reques出g l!J∞ess 10 data or resour，ωs and issuing or
`responding 10 autbentication cballenges. The capabilities of
`an activc advers缸y are takcn to include all those of a passive
`one. One type of adversarial attack wbich is contemplated is
`由at of an initi创 passive period of monitoring and recording
`activities, followed by a pcriod of otf-line analysis and
`manipulatioo of tbe data obtaincd during mooitoring activi(cid:173)
`ties, foUowed by a brief interval of activity whcrein access
`to data 创始 data proccssing resources is requesled. Altema.
`tively, the adversary may merely engage in passive moni(cid:173)
`toring and recording activitiωfollowed by analysis and
`atlemp1S 10αypt analyze p。而ons of the data, p缸ticul缸ly io
`an attempt to recover the scssioo key, which is tben utilized
`10 d巳αypt any encrypted da1a which was tra且srniued
`between 由ep缸U巳s and recorded by 由e adversary.
`Since it is more diOicu1t 10 dctcct a passive adversary, wbo
`on1y monitors, records, and Ihen la1er pcrforms off-line
`analysis，也an an active adversary who is forced to intcract
`witb one or more autborized communicatioo p缸ties， adver(cid:173)
`saries favor a passive mode of attack. A still more significant
`reason off-line analysis is prcfcrred by 翻 adversary is tbc
`bandwidth li皿itations pr，ωenl 切 Ihe communicatio 口 chan­
`oel: the adversary can on1y speak 10 partners 刨出巳 rate
`wlúch is defined and allowed by tbe system architecture; but
`otf.line analysis can be pcñormed at the rate of the adver.
`sary's ∞mputing resourα:s. Thus. it is especially important
`to provided幽 security systems which prevent an adversary
`from gatbe由19 useful dala during passi ve acti vities. It is
`especially important 也al security systcms be de到gned 10
`prevcot a compromise of 由c long.lived and secret sh缸ed
`key as well as any short-livcò and secret session keys which
`may have been uωized. It is espccialJy important tbat 由e
`
`15
`
`1. Technical Field
`τb巳 present invention relatcs in general 10 techniqucs for
`secur臼g the flow of inforτnation from an adversary. and in 10
`P缸ticul缸 to lechniques for verify旭.g thc idenlÍty of a
`communication partncr and distribulÍng session keys 创Dong
`commurncaoon p红lDers.
`2. DcscnplÍon of tbc Rela1ed Art
`Wi白白巳 increased uúlization of distributed data process.
`ing systems to share and cornmunicate seositiv巳刽1d con自-
`deotial information. the computing 缸ld rela位Ig industrics
`ar巳 paying si伊通ωntlyinα巳ased attention to improving and
`refining known techniqucs for securio~ dal~ whi~h is ~om- 20
`m皿iωted over insecure communication channels sucb as
`telephone lines and clectromagnetic-based communicatioo
`systems sucb as cellu1ar oelworks.
`τbree loog standing industry goals exisL Firsl, it is
`important that tbe p缸tiαJlar communication partners in a 25
`distributed da.ta processing system be able to autbenticate
`the identity of otber communication parmers within the
`distributed data processing system. Commonly. 也is entity
`authenticatioo requircmen1 is met by depositing a long-livcd
`缸ld sbarcd Secre1 key at two or morc communicatioo nodes 30
`泊 tbe data processing syslem. For examplc. a user may
`poss巳ss a secret password whicb is also known by a host
`∞mputerw地io 由e data processing systcm. When autbeo.
`ticatio日 is desired, a proω∞1 is executed whicb, based on
`出is shared secret, servesωauthentiω1e ooe party 10 由e 35
`other. or eacb 归rty to the otber. For example, the loog.lived
`and sbared secret key can be uω泣ed 泊 a convcntional
`eocryption operation such as a DES eoαyptioo. Most com-
`mo创y. tbe communication p缸tner desiring autbentication of
`缸lotber partner directs a "cballeoge" to tbe otber partner 40
`wbich is in 也巳 form of a random bit stream. Th巳 P缸tner for
`whicb authentication is sought typically performs an encryp-
`tion operation 叩on 由e cballcnge bit stream utilizing 由e
`long-lived and sbared s∞ret key, and then passes this data
`back to the challenging party. This data is decrypted to 45
`deterrnine whetber the res归自ding party has possession or
`knowledge of 也e long-lived and shared s阳et key, or 由E
`challenger u创泣es an encryption engine to generaω 由e
`response b巳 or she is secking, and tben ∞mpress 由巳
`response to 由ecoπ'CCt answer.τbis operation may be 50
`performed unilateral.ly or bilaterally. In a unilateral opcra-
`tion, one p缸ty obtains authentication of tbe identity of
`another party within tbc distributed data processing system.
`In a bilateral entity authentication procedu窍， both parties
`typically issue a "challcnge" to 也巳 otber p缸ty， wbicb must SS
`be rcsponded 10 propcrly before communicatioo can be
`allowed between thc communication oodes.
`The second broad goal of tbe industry is to provide
`techniques for generating and distributing sbort-lived and
`seα-et seSSiOD keys wlúch 缸"C sh缸ed by two or more 60
`commu皿cation partners in a dis缸ibuted data processing
`system after autbentication of tbe various communication
`p缸tners has been obtained. In aα:ordance witb 也e prescnt
`invcntion, tbe distribution of 也e short-lived and secrct
`session key is tigbtly couplcd witb the cntity autbentication 65
`operatioDs. The utiüzatioD of a session key ensures tbat 也e
`long.lived and shared secret key need not be used more oftcn
`
`6
`
`

`

`5,491,749
`
`3
`security systcm preveot th巳 passive adversary 台'omcorr，巳clly
`思lcssing thc long-lived or shorl-lived keys during oJI-line
`analysis, and then confirming thc vcracity of the guess
`during off-line activiú盹 lt is imponant tb矶山eadvers缸ybc
`forced to actively engage one or more communication 5
`parties in ordcr to confirm tbe accuracy of a ∞π∞tly
`gucssed key. This type of protection is identifi巳d as "security
`against oJI-line attack", and can be best understood wi山
`rcspcct to 山e speci 自c ex缸nple of one type of off-Iine attack,
`which is known as a "diction缸y attack", which wil1 hc 10
`d沁cussed here below.
`Dictionary atlacks 缸巳 c1fective because the long-livcd
`kcy uscd for the entity authentication is based on a user' s
`password and tbese passwords are often chosen poorly,
`Many data processing systems allow the human operators 10 15
`selecl their own passwords. Of course, tbe humans select
`familiar words 1ypical1y, in ordcr to hc bettcr able to
`remcmbcr thc pass word in the fu1ure , 11 is not uncommon
`for users 10 use proper namcs or ∞mmon Ilouns or verbs as
`passwords. Since human languag巳 is a f;缸rly small and static 20
`sct, it is possible for a passive adversary ωiteratively guess
`1he candidate of one or more particul红 languages and then
`sec if such gucss "cxplains" 由e transcript recorded in an
`earlier session during 巳avesdropping activity. When a match
`is identified，也e ∞π'ect password is typically recovered as 25
`is any shorl-lived kcy whose distribuúon had been based on
`出is password. Of ∞urse，也is type of off-line attack can hc
`computationally dcmanding if the size of 由e diction缸y is
`very large, but the significant advanccs which are continu(cid:173)
`ally bcing madc in proccssing speed and power malcc such 30
`olf-linc anacks practical even if tbe dictionary ∞ntains
`many millions of words.
`
`SUMMARY OF THE INVENTION
`
`45
`
`It is one objcctive of tbe present invention to provide a 35
`security system which is not susceptible to off-line anacks,
`such as a dictionary attack, by forcing an adversary to test
`the a∞uracy of each 忽lesS of a candidate key interactively
`with onc or more communicaúon p红úes.
`It is anolhcr objcc1ive of tbe present invention to provide 40
`a security sys1em which minimizes th巳 number of commu-
`nication tJows which must pass between communicating
`partíes during entily autbentication operations and key dis(cid:173)
`tributions.
`Il is yel another obj∞tive of tbe present invention to
`provide a 何curi1y sys1em which is less reliant on encryption
`and d∞ryplion operations than existing prior an security
`systems, and which is much more reliant u阳n transforms,
`such as mcssage authcntication codes and enαyplion hash 50
`functions, which are applied 10 a plurality of Par副nctcrs
`including thc long-Iived and secret sbared key, or its dcriva-
`tives, in ordcr 10 maximizc system sec山ity.
`Jt is slill ano山er objective of thc pr'ωent invcntion 10
`provide a 民curity systcm which utilizes onc or more ∞m- S5
`putationally irreversible transforms which arC applied to a
`plurality of parameters, including tbe long-lived and s优ret
`shared key or its derivativ邸， 10 a∞omplish entily authen-
`tication, in Iieu of 也巳 more conventional utilization of
`cncryption techniques such 豁出c DES algori也m. In也巳 ω
`preferred embodiment， 由is type of authcntication-tag-based
`entity authentication is utiJized in combination wilh an
`exponential key exchange. The present technique can bc
`uúlized to perfoπn unilateral or multilateral authcntication,
`involving lwo parties or 山ree parlÏes.
`These and other objectives 缸e achieved as is now
`dcscrihcd. A mcthod i5 provided for auth巳nticating a com-
`
`65
`
`4
`municaúon partncr on an insecure communication channel,
`whcrcin the authenticity of a communication partner is
`dClCπTÚned by possession of a long-lived shared seα'CI key.
`τnc method includes a numhcr of steps. First, a .. ∞mposilc
`key" is exchangcd in data flows between communication
`partncrs, whercin all阻st a ponion of tbe data flows has bcen
`encryptcd or othcrwise masked in a manner which utilizes
`the long-lived sh缸巳d sccrel key. Next, at leasl one authcn(cid:173)
`tication tag is passed belween communication p红tners， wi1h
`由c al Icast one authentication tag being based at leasl
`partial1y upon the composi1c kcy. Finally, lhe authcntication
`lag is utilizcd by al leasl one communicatio口 p缸tner 10
`determine authcnticity of another communication p缸tncr.ln
`thc preferred embodimcnt of 由巳 present invention, the at
`leasl onc authcntication 1ag is defined by a transforrn which
`includcs al lcast one of (1) a message authentication ∞de
`which is keyed by said long-Iivcd sharcd sccret key 缸ld
`takcn ovcr a p)urality of parameters, (2) a cryptographic
`hash function takcn over tbc long-lived shared secret key
`and a plurality of other parameters, and (3) the cncryption or
`message authcntication cod巳 keyed by said long-Jived key
`and takcn ovcr 由 c cryp10graphic hash of a pJurality of
`par缸neters. ln onc p组ticular embodùncnt of the present
`invcntion, whcrcin muωal authentication is dcsired bclween
`first and second parlÏcs, the parlÏes firs1 exchange ponions of
`a ∞mpo5ite kcy using a conventional secret key exchange,
`ex∞pt 由al somc or alJ of the flows of 由is exchangc arC
`encryp1ed, as is describcd 臼 U.S . PaL No. 4,241 ,599 to
`BcUovin ct al . τñen， 负rst and second 剧tbcntication lags are
`cxchanged between 也E 且rst and second communication
`partics. Thc autbcntication tags are analyzed to 萨江form an
`entity autbcntication of tbe 自rsl andωcond communication
`panncrs. In onc specific embodiment of the prcsent Învcn(cid:173)
`tion. at Jω5t one of the first and second autbentication tags
`is communicatcd hclween the first and second communica(cid:173)
`tion panners a10ng wi山 al least a portion of thc composilc
`session key, in ordcr to minirnize thc number of communi(cid:173)
`cation flows betw巳en 出e 6rst and s巳cond communication
`p缸tners. ln parlÏcular embodiments of thc present invention,
`thc authcntication tags are generated by applying a hash
`function to a plurality of par缸nete邸， which include the
`newly-distribu1ed session key, and then using as the autbcn(cid:173)
`tication tag a prefix of this hash function.
`Whilc lhc prcsent invenlion is descrihcd wi由 reference 10
`onc principal commercial application in distribut巳d data
`processing systems, it is clcar that 由c prcscnl invcntion is of
`gencral applicability and can be utilized to ∞mmuniωte
`m巳ssages in any conceivable communication channcl, and
`thal it is particularly uscful for secret tel饥。mmu时cations.
`Thc abovc as well as additional objectives, features, and
`advanlages of 由e prcsent invention will hccome app缸'Cnt io
`thc following dctail巳d wrinen description.
`BRIEF DESCRIPTION OF THE DRAW1NGS
`
`节le novel features believed characleristic of 由巳 invention
`缸c sct forlh in thc append巳d c1aims.τnc invcntion itscJf
`however, as wel1 as a prcfcπ'cd modc of USe，也时1巳r objec(cid:173)
`tives and advantagcs thcrωf. will bcst bc underst仪>d by
`reference to thc foUowing detail巳dd巳scription of an illus(cid:173)
`lrativc cmbodimcnl when read in conjunction wi由 the
`accompanying drawings, wherein:
`FlG. 1 depicts a prior 缸t two-pany, message authentica-
`110n;
`FlG. 2 dcpicts a prior art conventional key exchange,
`exponenlial key exchang巳， such as the Di纽巳-Hellman key
`cxchangc;
`
`7
`
`

`

`5,491,749
`
`25
`
`5
`FIG. 3 depicts a prior art key exchange in accordance with
`the teachings of Bellovin and Merritt;
`FIG. 4 depicts a two-party, mutu31 authentication opera(cid:173)
`tion in accordance with one 巳mbodiment of the present
`invention; 缸ld
`FIG. 5 depicts a distributed data processing system which
`can be programmed to perform the authentication opcration
`of 由e presenl invention.
`DETAILED DESCRJPTION OF PREFERRED
`EMBODTh伍1\11'
`FIGS. 1, 2, and 3 providc views of prior 副 techniques for
`S巳curing the communication of data. An understanding of
`these prior art techniqu巳s will facilitate an understanding of
`由e prefcrred embodiments of the present invention which 15
`are depicted 归 FIGS. 4 30d 5.
`In FIG. 1, a prior 红飞 three-pass message authentication
`technique is depicted. As is shown, A and B are 也巳 com-
`munication partn叭 which share a 10呛Hvedmd sumd20
`secrct key a. Communication partners A 30d B communicate
`over an insecure communication channel. Three data flows
`are depicted in FIG. 1.τbe 缸st data flow is from commu-
`nication partner A to communication partner B, 30d includes
`a r3Odom bit s创ng R.. which represents an entity authenti-
`cation challeng巳. The first fiow 31so includ巳s an arbitr缸y
`text s町旭g Textl. Communication p缸tner B responds to the
`缸5t communication flow by dir巳cting to communication
`p红tner A a random bit string challenge Ra an arbi衍缸y text
`string Text2, and a bit string whicb is the result of a
`transform 时， whicb is keyed with 由巳 long-lived and shared
`sccret key a, 30d taken over a pl旧创ity of further data items
`including an identi自cation of communication p缸tnersA， B,
`the authentication challenges RA • RB• which have been
`genera也d by the communication partners A, B, and Text2.
`Since communication partner A possesses 也e long-lived
`and shared secret key a, then sb巳 c30 utilize 也巳 authenti­
`cation challenge RB from communication p缸tner B to
`generate a bit stream whicb is identical (迁出e second fiow
`is computed ∞rrectly and received as it is 位缸lsmiue~) t~ 40
`that provided by communication p缸tner B as a result of
`utiliz创on of transforτn ha1. At the end of ∞mmunication
`fiow 2, communication partner A can b巳 certain that com(cid:173)
`munication p缸tner B is "authentic", since possession of the
`10暗lived and sh蚓阳'et key is 叫uired 岛r commu~- 45
`cation p征tner B to gencrate a bit stream through the utili-
`zation of transform ha I wlúch is identic31 to that generat巳d
`by cornmunication p缸tner A.
`In由e 也ird communication tlow, communication p缸tner
`A directs Text3，缸ld 由e resuJt of the application of transform 50
`%2ωthe authentication cha1lenge RB 30d Tcxt3. Commu-
`nication p缸tner B can utilize 也e long-lived 30d shared
`S巳cret key a，由e authentication challenge RB' Text3. 30d
`transform h2 to generate a bit stream which is compared to
`that provided by cornmunication p红m巳r A. Uthe bit streams 55
`are identical, then communication p缸tner B can b巳 ceπain
`that communication partner A is "authentic". The techniques
`depicted in FIG. 1 are more fully discussed in a publication
`by M. Bellare 30d P. Rogaway, entitled "Entity Auth巳ntica-
`tion 但d Key Distribution", published in The Proceeding 01 60
`Cryplo '93, by Springer-Verlag, which is incorporated here
`负llly as is set forth herein. Basica1ly, in the technique ofFIG.
`1, convention31 entity authentication ch31lenging techniques
`are combined with convention31 message authentication
`techniques.
`FlG. 2 depicts a conventional key exchange in accord3Oce
`with the teachings ofW. Di组e， and M. Hellman, in an 缸ticle
`
`6
`巳nω叫 "New Directions in Cryptography", IEEE Transac(cid:173)
`tions On Informalion Theo吵~ IT-22, No. 6, 1976, which is
`incorporated herein as if fully set forth , Tlús techniquc may
`b巳 identjfied specific31ly as a Diffic-Hellman key exchange.
`5 The p旧pose of 也is technique is to publicly exchange
`information tbat can be ∞mbined to gcnerate a shared secret
`key which can be utilized for particul红 communication
`sessions. In accordance with this protocol, communication
`p缸tner A directs to communication partncr B a bit stre却n
`10 wlúchisg巳neratcd by expotentiating a publicly-known base
`g to a secretly select巳d power or, selected from a publicly(cid:173)
`known group such as the multiplicative group Modulo a
`fixed prim巳 numbcr p. Communication p缸tner EI responds
`in communication fiow 2 by directing to communication
`p缸tner A a bit strcam which is generated by expotentiating
`a publicly-known bas巳 g to a secretly selected power [3,
`selected from the same publicly-known group 仕'omwhich α
`was selected. Thc sh缸ed secretσ， is generated by utilization
`of 由e information passed betwe巳n communication p缸tners
`A, B in tbe two communication fiows. As is shown in FIG.
`2. 出e shared seαetσ， is a function of a transform H as
`applied to 出e exponenti31 product of g<X and gP, Preferably,
`也ev创ues forα， 30d ß are randomly selected by commu(cid:173)
`nication p红tners A, B f云om a predefined set of integers.
`The Diffie-Hellman key exch30ge is uscful only over
`communication channels which may be subject to passive
`adversari邸， but not communication channels wlúch 缸巳
`subject to activc adversaries. In other words, if the commu(cid:173)
`nication channeJ is susceptibleωinteraction by 由c adver-
`S缸y， then 也巳 Diffie-Hel1man key exchange protocol is not
`very useful, since thc adversary ωn pos'e as eith巳r commu(cid:173)
`nication p缸tner A or communication partner B and 凶itiate
`也巳 g巳neration of a shared sια悦， which can then be utilized
`to obtain information from 30 authorized party.
`Convention31 key exchange techniques like 由at of the
`Diffic-Hellman key exchange protocol of FIG. 2 have becn
`elaborated on by B巳Uovin 30d Merritt in the paper entitl叫
`"Encrypted Key Exch3Oge: Password Based Protocol
`Secure Against Dictionary Attacks飞 proceedings of the
`IEEE Symposium On Research And Securily A.nd Privacy,
`1992, wlúch is 31so the subjecl matte:r of U.S. Pat. No.
`5,241,599, issued on Aug. 31, 1993 to Bellovin et 31., and
`wlúch i沁s entiωtleω:d
`munic::u彼甜.tio∞ns'飞 both of which are i阳nc∞or叩porat惚.ed he.町f巳ein by
`refercnc比c巳 fu川'ull汹11均y. The broad concept behind the approach of
`Bellovi日创d Me时tt is depicted in FIG. 3. As is shown,
`communication partners A, B share a long-Jived secret key
`a. Two communication fiows 缸'e depicted in FIG. 3,
`31though additional cornmunication flows are 31so possible.
`In the first communication flow, A applies a randomly(cid:173)
`seJected and secrel a (30 authenticatioll key picked from a
`fixed und巳rlying group), as 30 expooentωthe publicly(cid:173)
`known base g, and then applies an enαyption of masking
`transform Ea 1 wlúch is keyed with the long-lived 30d shared
`seαet key a to the bit stream representati ve of gσ. 1且也e
`second communication fiow, communication partner B
`responds by applying a randomly-selected ß as ap exponent
`to the base g, 30d 也en appJies ~ transform E.. ~ to 也e bit
`stream which is generated by gP. 1n accordance witb 也is
`technique, the key wlúch has been generated ~ a result of
`this interaction isσwhich is 饲u31 to H1(gα内. for some
`function H1. 1n this protocol the transforms E1 and E2can be
`exclusive-or operations or any 0也巳r masking operation.
`uωizing 也is technique Bellovin 30d Merritt have devised a
`65 protocol which can be utilized to periodica1ly gencrate
`short-lived session keys, in accord3Oce with the Di伍e­
`Hellman key exchange, which are secure against both active
`
`30
`
`35
`
`8
`
`

`

`…阳明阳的川器时…
`umymM叫叫归阴阳-M剧他mmMm队tu肌mmww川dmM伽毗·们mMVmm…ummn，勺mm-mm川ω伽mFM阳阳们mwk陆 mMM伽AMM伯阳-m恤
`
`wm四川川队摆出们也阳mml…川口也时均以也黯提出口叫
`
`7
`
`5,491,749
`
`zm川口们叫出叫叫叫出政均可叫出且也儿跳出矶山川
`-mmm盯dwwm 刷 oe 」出 mmEpcu --m-mhmummn-mm 川剧-Meω川 mI-m-m也 wsn ∞1.m甜、aodw
`出口ω市内mdm叫"口战叫阿肌叫也…吼叫川川川剧出……山山川
`∞曲-MMMW吼叫ω刷刷阳 mhMω-mnuMm
`ω叫WMhI4胁m内仰 mm-m-m均由
`m叫乱叫叫mM
`MmMMWPωωhmmd明m叼时dm附mM白 CZm ，阴阳弘可mωmmmu川总山mmmmF弘切m阿f扣MLH阳川叫
`去出阳也阳刚创山川rzwm…均叫md…刷川江胁口总叫叭叭响…川叫
`叫捆在川江wm汪叫"百旦河∞叫…
`mm川市叩hhmuMMU恼mwr且阴阳也咖啡jJm山注口
`""呻川阴暗议时以"!umocfnlmu毗whnEtFdMnz03h阳gfdmzmlmu:MH叫In;tEK∞:
`圳圳市川口出m拟川血口白白川俨挝叫川出出口忧川山川鸣也
`mm川MmmUMW叫川…川川mMt川川良后均可比m时mwmhm川川江出Brmz阳川剧B&W巾MMhMmum
`帆乙阳
`出地沁创出ωomm眈ω哈比……灿灿品哈比…削阶州时
`
`sm地 C 町
`mMAm"比萨的"mm阳刊阳山川阳m叫J叫乱叫世阳也骂骂m山川mn出 ω创nmwm
`
`umdud-四川剧的mmω 也
`
`f morg 句Pωm-ul创 UEyhotu
`
`mr叫叫川h川口也叫MZm
`
`阳灿叫仕modm严admb·由刽
`
`。tdF10
`
`mzm以可怕出叮叮览
`
`-m
`M阳
`
`也 mu ·"叫"阳mh
`町'则'mmm阳们明叫MR创刊'川
`
`E阳啊创ω阳JMm几叭队础ω阴阳川m曲ω-m血dmp由川阳阳m叩·阳也四川
`
`-m
`
`。如
`nm阳阳g出比川、牛盼"队AmmD仙。由句uwd
`
`叫ωmm们仰
`
`'均
`创m
`
`FL江山时叫…毗川吼叫问侃出
`
`μ出
`
`h…哝川刷出咄咄矿总ωm
`
`hmhmw罚赔付出吭吭叫"叫出口也出」
`
`…川……黯峨山川………
`
`m…r…………………吼叫~……………黯……叩…………
`
`rm扭扭…………ω灿灿…
`
`刊出私照比段内战MM阳也tMJ以阳山叫aMmMtmrM
`Mmmmu叫"m出岳阳灿黯J
`
`2
`
`33
`
`巾阳mmm毗hm向拟出山吭吭刷出报提川阳山叫
`
`MM阳Mhr州川出也叫阳U沾 hp州民rh叫苦'叫"间向阳川山阿
`
`mMUmmmh刷刷刷阳，巾问阴阳
`
`50
`
`5
`l2
`
`8
`
`dω巳
`
`-W
`
`0505050505
`
`…监轮机机密战班且…
`emLULtmc·m-mAhn
`阳叫阳刚出时川出M川JtzhoZMm吨矶smmwm 叽pu官问UMd即 mumzm川出德mmmmmwrmmwu
`
`Mh叫川叫"叫Fmnu川扪汀剧时-mmmmu川叩hm创始ωrapd ∞mtMm·
`
`认立∞叫hM川江山叫mwMLmw川剧时叫rhdeωpEddmMmmmt
`
`帆MMdcobM
`
`阳
`
`-mwm叫部则Jrmω∞n
`
`…部黯堤坝Mm盯阳山川…留且吼叫…盟招摇础较扭扭瓢叫叫川叫…川机
`
`p叫
`
`驯叫阳mm山川川剧"咖问
`
`MM仙创ωωpmM臼仰川巾ωmhomwmmJrmm阳dM幽暗比创刊mf币町m惊叫时m协山川amdM阳dmvμ阳
`
`w足
`
`足……比MUω旦旦黯川队阶段川黯蓝蓝山
`
`445506
`
`9
`
`

`

`5,491 ,749
`
`APPLICATIONS OF TIffi AUTHENτlCATION
`PROTOCOLS
`
`MESSAGE AUTHENTICATION CODE
`OPERA:ηONS
`
`10
`9
`h 也e prefeπed embodiment of the present invcntion,
`由e keying of the message authentication code 伽1AC)
`2 are ei由er conventional messagc
`U缸lsforrns b" I 缸Id ba
`operaLion with a secrel key eosures 也at 由e authcntication
`authentication code techniques or conventional basb func(cid:173)
`tag produced as a result of thc message aUlhentication code
`tions. Many mccbanisms are available to accomplish thc
`operalion serves to authenlicale 由c one or more communi(cid:173)
`0战jcctives of messagc autbentication code operations, but 5
`catío日 parties.
`some of the principal oncs includ巳:
`An article publishcd in the SepLemb巳r 1985 issue of IEEE
`Communications Magazinc, Volume 23, No. 9, enlitl叫
`(1) 由e pr巳fix of tbe last word of 由e CBC-encryption
`using a block ciphcrα(也at is, cipher block chaining)
`"Message Authenlication" by R. 民 Juenem徊， s. M. Ma1-
`yas, and C. 日. Meyer selS forth alternatives 10 由巳 Cipher
`of a particular bit stream under a long-lived and sωm
`key a, denoled as "CBCQC(x)";
`10 Block Chaining operatioD， ωd is incorporaled herein fully
`as if sel forth.
`(2) 也e prefix of tbe αyptograpbic hasb of a p红ticul缸 bit
`S回回1 an.d the long-lived and shared secrel key a,
`denoted as "阳h 仇， a)tt;
`。) a cO!Dbin~~?n _of the o~ration_ of ~o. 1 an~. tb_c 15
`opera丘on of No. 2 10 drive the prefìx of a cipher block
`cbaining operation which is perfo口ned upon a crypto-
`grapbic bash function of ope.ration No. 2, which is
`denoted "CBCø(hash(x,a)); and
`(4) a combination of a hash operation and an cncryption 20
`operation (such as tbe DES algori吐un) wbich can be
`denoted as "EnCryptiOD (hash(x))".
`
`Tbc protocols of 也e present inveotion may be uti1ized in
`a distributcd data processing sys1em to authenticate on巳 or
`more communication partners in tbe distributed data pro(cid:173)
`ccssing system. In such an environmcDt, 18 ooe or more data
`proccssiog units perform 山巳 functions of the LruSted inter(cid:173)
`mediary. FIG. 5 depicLS a distributed data procωsing system
`8 wbich may be programmed to perforrn tbe proto∞ls
`descri民d herein.
`25 _ As is_sh?w_n in ~G.~， disr_:ibuted ~ta pr~∞ssing system
`8 may include a plur刻ity of oetworks, sucb as local 缸ea
`networks (LAj问 10 and 32, cach of wbich preferably
`Message autbenlication codes (MACs) 缸e utilized in
`includes a pl町刽ity of iodividual computers 12, 30, respec-
`cryptography to assure thc authenticity of communications.
`Tbese types of operalions 红c frequentl y referred to as
`ti vely.αcourse， those skilled in the art will appreciate that
`"m~ssa~e authentication operations". Typically, ~~ssage 30 a plurality of intelligcnt w~rk slalions coupled 10 a host
`authentication operations perrnil a rcceiver to validaωa
`∞mputer may bc 四lized for each such nerwork. As is
`message's origin and destination, cootents, timeliness, and
`common in such distributcd data processing systems, each
`sequence relaùve to other messages f10wing between ∞m-
`individual computer may be ∞upled to a storage deviα14
`andlor a printcrloutput device 16. One or more such sωrage
`m田ùcanLS.
`While a v缸iety of algorithms may serve to perform 由巳 35 devices 14 m_ay bc u副ized， in accordance witll the me'让10d
`me由od autbentication code (MAC) operations，也e best --
`and system ofthe present invention, to store v四ous "group-
`known and 0篮ciaI scheme is 8 documented in 由e DES
`ware" applications or d侃umenLS which may be sim凶ta-
`MODES OF OPERATION public血on， more s严cifically
`neousl)' or successively ac∞sscdωd processed by multiple
`ideotified as the Federal Information Processing -Standard's
`uscrs. F山thermore， one or morc systems may be includcd
`Publicatioo, FIPS PUB 机， publishcd by the Nalional 40 for managing data proccssing resourc邸， including the
`Bureau of Standards on Dcc. 2, -1980. Preferably, tlle Cipher
`groupware applications and documents, in ac~ordance with
`Block Chaining (CBC) mode is used to enαypt plaintext,
`convenlional lechnologies.
`which must be padded (for example, witll zero bits) if
`Still referring to FIG. 5, it may be seen 阳t distributed
`necess缸Y to make il a multiple of si.xty-four bits in length.
`data processing network 8 may also înclude multiple main-
`TbeMAC ∞nsisLS of thc Iasl k biLS of cypbertext，由e rest 45 fr缸到巳 computers. such as mainframe computcr 18, wbich
`of wbich is discarded. 切由 p严roceωss i沁s discussed î凶nana缸rticlc
`ma'叼yb忱eprefi岛巳:rab悦ly ∞upμ>le叫d~ω010∞ca挝l 缸E阻a ne眩et阳.wor汰kιAN) 10
`by C. H. M巳叼ye'衍rand S. M. Ma均叨a战s， en川川础lt削血li山ωi抗汕tled
`18 may be ∞upled to a storagc device 20 which may serve
`A New Dimcnsion in Computer Dat饱a SeαK川ity"二， published
`by 10hn Wùey & Sons, ofNew Yo汰， in 19