(12) United States Patent
`Munger et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,502,135 B1
`Dec. 31, 2002
`
`US006502135B1
`
`(54) AGILE NETWORK PROTOCOL FOR
`SECURE COMMUNICATIONS WITH
`ASSURED SYSTEM AVAILABILITY
`
`(75)
`
`Inventors: Edmund ‘Colby Munger, Crownsville,
`MD (US), Douglas Charles Schmidt,
`Severna Park, MD (US); Robert
`Dunham Sh0I‘t,
`Leesburg,
`(US); Victor Larson, Fairfax, VA (US);
`Michael Williamson, South Riding, VA
`(US)
`
`DE
`E1’
`E1’
`GB
`
`W0
`W0
`W0
`wo
`
`199 24 575
`2 317 792
`0 858 189
`0 814 589
`
`33/
`W0 99 38081
`W0 99 48303
`WO 00/70458
`W0 ()1 50533
`
`12/1999
`4/1993
`8/1998
`12/1997
`
`7/1999
`9/1999
`11/2000
`7/2001
`
`OTHER PUBLICATIONS
`
`(73) Assigned Science Applieadons Inte”13d0n3l
`C0rP01'3ti01L 5311 131380, CA (US)
`
`*
`
`Notice:
`
`J
`Y
`Sub'ect to an disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Fasbender, Kesdogan, and Kubitz: “Variable and Scalable
`Security: Protection of Location Information in Mobile IP”,
`IEEE
`bl'
`t'
`, 1996,
`. 963-967.
`pp
`pu lea Ion
`(List continued on next page.)
`
`(21) Appl. No.: 09/504,783
`
`(22)
`
`Filed:
`
`Feb. 15, 2000
`
`(63)
`(60)
`
`Related U'S' Application Data
`Continuation—in—part of application No. 09/429,643, filed on
`Oct. 29, 1999
`Provisional application No. 60/106,261, filed on Oct. 30,
`1998, and provisional application No. 60/137,704, filed on
`J11I1- 7, 1999-
`Int. Cl.7 ............................................ .. G06F 15/173
`(51)
`(52) U.S. Cl.
`...................... .. 709/225, 709/229, 709/245
`(58) Field of Search ................................. 709/249, 223,
`709/225’ 229’ 245; 713/201
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`4,933,846 A
`
`6/1990 Humphrey et al.
`
`(List continued on next page)
`FOREIGN PATENT DOCUMENTS
`
`Primary Examiner—Krisna Lim
`(74) Attorney, Agent, or Firm—Banner & Witcoff, Ltd.
`
`(57)
`
`ABSTRACT
`
`A plurality of computer nodes communicate using seem-
`’
`1
`d
`I
`t
`t P t
`1
`d d
`t’
`t’
`Héfiy ran (En
`H er?
`r0 Oct? S0ur.Ce .and fiesdmg Ion
`a
`resses.
`ata pac ets matc ing criteria
`e ne
`y a
`m0Ving.Wind0“.' of Valid addresses are aeeepted fer fllrther
`processing, while those that do not meet the criteria are
`quickly rejected. Improvements to the basic design include
`(1) 8 1989 981899“ that dlémbutes P898918 W088 dlffefint
`‘”‘“S”“SS1°“ Paths a°"°rd“‘8 ‘O “a“S”“SS1°“ Path quélltyi
`(2) a DNS proxy Server that aaasparaaay Creates a Vmaal
`private network in response to a domain name inquiry; (3)
`a large-to-small link bandwidth management feature that
`prevents denial-of-service attacks at system chokepoints;
`a traffic limiter that regulates incoming packets by limiting
`the rate at which a transmitter can be synchronized with a
`receiver; and (5) a signaling synchronizer that allows a large
`number of nodes to communicate with a central node by
`partitioning the communication function between two sepa-
`rate entities.
`
`DE
`
`0 838 930
`
`12/1999
`
`17 Claims, 35 Drawing Sheets
`
`
`
`SESSDN KEY
`
`107
`
`IF
`ROUTER
`
`LINK KEY
`\
`TARP
`ROUTE 1
`
`(1 32
`(P
`ROUTER
`
`TARP
`ROUTER
`
`‘P
`ROUTER
`
`UNK KEY
`TARP PACKET
`140 J \
`
`TARP
`
`\/ TERMINAL
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`US 6,502,135 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`......... .. 709/225
`
`.............. .. 709/243
`
`12/1996 Aziz
`5,588,060 A
`11/1997 Nguyen
`5,689,566 A
`8/1998 Esbensen
`5,796,942 A
`9/1998 Holloway et al.
`5,805,801 A
`11/1998 Hughes et al.
`5,842,040 A
`3/1999 Baehr et al.
`5,878,231 A *
`4/1999 Klaus
`5,892,903 A
`4/1999 Wesinger et al.
`5,898,830 A *
`5/1999 Holloway et al.
`5,905,859 A
`12/1999 Adelman et al.
`6,006,259 A
`1/2000 Tomoike ................... .. 370/338
`6,016,318 A *
`4/2000 Wesinger, Jr. et al.
`6,052,788 A
`6/2000 Liu .......................... .. 713/201
`6,079,020 A *
`9/2000 Alkhatib
`6,119,171 A
`........ .. 713/168
`1/2001 Schneider et al.
`6,178,505 B1 *
`5/2001 Arrow et al.
`............. .. 370/351
`6,226,751 B1 *
`6/2001 Sitaraman et al.
`6,243,749 B1
`..... .. 345/733
`9/2001 Ramanathan et al.
`6,286,047 B1 *
`6,330,562 B1 * 12/2001 Boden et al.
`............... .. 707/10
`.. 709/219
`6,332,158 B1 * 12/2001 Risley et al.
`.... ..
`
`............ .. 370/389
`6,353,614 B1 *
`3/2002 Borella et al.
`OTHER PUBLICATIONS
`
`Linux FreeS/WAN Index File, printed from http://liberty-
`.freeswan.org/freeswanitrees/freeswan-1.3/doc/ on Feb.
`21, 2002, 3 pages.
`J. Gilmore, “Swan: Securing the Internet against Wiretap-
`ping”, printed from http://liberty.freeswan.org/freeswan_
`trees/freesswan-1.3/doc/rationale.html on Feb. 21, 2002, 4
`pages.
`Glossary for the Linux FreeS/WAN project, printed from
`http://liberty.freeswan/org/freeswanitrees/freeswan-1.3/
`doc/glossary.html on Feb. 21, 2002, 25 pages.
`
`Alar1 O. Frier et al., “The SSL Protocol Version 3.0”, Nov.
`18, 1996, printed from http://www.netscape.com/eng/ss13/
`draft302.txt on Feb. 4, 2002, 56 pages.
`Reiter, Michael K. and Rubin, Aviel D. (AT&T Labs—
`Research), “Crowds: Anonymity for Web Transactions”, pp.
`1-23.
`
`Dolev, Shlomi and Ostrovsky, Rafail, “Efficient Anonymous
`Multicast and Reception” (Extended Abstract), 16 pages.
`Rubin, Aviel D., Geer, Daniel, and Ranum, Marcus J. (Wiley
`Computer Publishing), “Web Security Sourcebook”, pp.
`82-94.
`
`Shree Murthy et al., “Congestion-Oriented Shortest Multi-
`path Routing”, Proceedings of IEEE INFOCOM, 1996, pp.
`1028-1036.
`Jim Jones et al., “Distributed Denial of Service Attacks:
`Defenses”, Global Integrity Corporation, 2000, pp. 1-14.
`Search Report (dated Jun. 18, 2002), International Applica-
`tion No. PCT/US01/13260.
`Search Report (dated Jun. 28, 2002), International Applica-
`tion No. PCT/US01/13261.
`Donald E. Eastlake, “Domain Name System Security Exten-
`sions”, DNS Security Working Group, Apr. 1998, 51 pages.
`D. B. Chapman et al., “Building Internet Firewalls”, Nov.
`1995, pp. 278-297 and pp. 351-375.
`P. Srisuresh et al., “DNS extensions to Network Address
`Translators”, Jul. 1998, 27 pages.
`Laurie Wells, “Security Icon”, Oct. 19, 1998, 1 page.
`W. Stallings, “Cryptography And Network Security”, 2”“
`Edition, Chapter 13, IP Security, Jun. 8, 1998, pp. 399-400.
`W. Stallings, “New Cryptography and Network Security
`Book”, Jun. 8, 1998, 3 pages.
`
`* cited by examiner
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 1 0135
`
`US 6,502,135 B1
`
`28
`
`‘P
`ROUTER
`
`IP
`ROUTER
`32
`
`H,
`ROUTER
`
`26
`
`IP
`ROUTER
`
`110
`
`TERMINAL
`
`MANGROVE 1001
`
`
`
`IP
`ROUTER
`I 25
`INTERNET
`"3
`ROUTER
`
`/‘ 27
`
`“'7
`
`IP
`ROUTER
`
`29
`
`IP
`ROUTER
`
`ENCRYPTION KEY
`\
`
`F IG. 1
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 2 0135
`
`US 6,502,135 B1
`
`100
`
`
`
`129
`
`r125 INTERNET
`
`1
`
`12
`
`TARP
`
`ROUTER
`
`IPROUTER
`
`
`
`
`
`SESSION KEY
`
`\
`
`127
`
`FIG. 2
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 3 0135
`
`US 6,502,135 B1
`
`207a
`
`207b
`
`2070
`
`207d
`
`° ° °
`
`
`
`DATA STREAM §@
`
`
`
`INTERLEAVED
`
`
`
`SESSION-KEY-ENCRYPTED
`PAYLOAD DATA§§Q
`
`TARP PACKET WITH
`ENCRYPTED PAYLOADS _34_0
`
`LINK-KEY-ENCRYPTED
`
`TARP PACKETS QQ
`
`»-
`
`IP PACKETS w/ ENCRYPTED
`TARP PACKETS AS
`PAYLOAD @
`
`
`
`
`TARP
`
`ROUTER 2
`
`TARP
`ROUTER 1
`
`
`
`
`
`TARP
`ROUTER 3
`
`TARP
`ROUTER 5
`
`TARP
`ROUTER 6
`
`TARP
`ROUTER 7
`
`TARP
`ROUTER 4
`
`
`
`TARP
`
`FIG. 3A
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`Dec. 31, 2002
`
`Sheet 4 of 35
`
`US 6,502,135 B1
`
`
`
`
`
`mWB><.u:~Ez_mo<o._><n_o._.z_
`
`<._.<omo95%£52
`
`
`
`802mm:2gmozmaomw23%
`
`
`
`89%V50;8:305
`
`MN|m8<o§._8;
`
`
`
`omE_>_mvasma§5zm_
`
`
`
`U.S.Patent
`a25%E5ll,‘
`...22:8£8£3
`
`
`
`En__>aV603azzozm
`
`
`
`
`
`mmmu$>§~Ez_8<o:Eo._.z_
`
`
`
`_.E>>mEo<n_has
`
`
`
`%2_<o§_eE;5zm
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`
`
`

`
`U.
`
`wa
`
`2m
`
`U
`
`PIS.wem_>Emz<Ein
`
`2,mommoeamn__maIE,ww_,__mm_8Ehasnm_z_m_>_8Em>_zz$:<mzom3$><:1_:_§Ez
`
`.Mm_%M2282sm_>_zz$:<$15
`
`.m9282z_2%.30mommmoog.3_E>>w.uz_mmaoE
`
`Azomm
`
`1mBW«WW1,W2INm,02.mmaégWM§Eomm:_z_E,a
`
`MANGROVE 1001
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 6 0135
`
`US 6,502,135 B1
`
`BACKGROUND LOOP-DECOY
`GENERATION
`
`S0
`
`EITHENTICATETARP PACKET
`
`S2
`
`S3
`
`S4
`
`88
`
`510
`
`311
`
`MANGROVE 1001
`
`
`
`TRANSMIT DECOY?
`
`YES
`
`DECREMENT
`
`YES
`
`NO
`
`
`
`GENERATE NEXT-HOP TARP
`ADDRESS AND STORE LINK KEY
`AND IP ADDRESS
`
`
`
`GENERATE NEXT-HOP TARP
`ADDRESS AND STORE LINK KEY
`AND IP ADDRESS
`
`
`
`DETERMINE DESTINATION TARP
`ADDRESS AND STORE LINK KEY
`AND IP ADDRESS
`
`
`
`GENERATE IP HEADER
`AND TRANSMIT
`
`FIG. 5
`
`35
`
`DUMP DECOY
`
`OUTER LAYER DECRYPTION OF
`TARP PACKET USING LINK KEY
`
`CHECK FOR DECOY AND
`
`INCREMENT PERISHABLE DECOY
`COUNTER AS APPROPRIATE
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 7 of 35
`
`US 6,502,135 B1
`
`BACKGROUND LOOP-DECOY
`GENERATION
`
`GROUP RECEIVED IP PACKETS
`INTO INTERLEAVE WINDOW
`
`HEADERSLJMCI
`
`DETERMINE DESTINATION TARP
`ADDRESS, INITIALIZE TTIL, STORE
`IN TARP HEADER
`
`RECORD WINDOW SEQ. NOS. AND
`INTERLEAVE SEQ. NOS IN TARP
`
`320
`
`521
`
`S22
`
`323
`
`MANGROVE 1001
`
`824
`
`
`
`CHOOSE FIRST HOP TARP
`ROUTER, LOOK UP IP ADDRESS
`AND STORE IN CLEAR IP HEADER,
`OUTER LAYER ENCRYPT
`
`INSTALL CLEAR IP HEADER
`AND TRANSMIT
`
`325
`
`FIG. 6
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 8 0135
`
`US 6,502,135 B1
`
`DIVIDE BLOCK INTO PACKETS
`
`
`
`
`USING WINDOW SEQUENCE DATA,
`ADD CLEAR IP HEADERS
`GENERATED FROM TARP
`HEADERS
`
`
`
`
`
`HAND COMPLETED IP PACKETS
`TO IP LAYER PROCESS
`
`[
`
`FIG. 7
`
`MANGROVE 1001
`
`S40
`
`BACKGROUND LOOP-DECOY
`
`GENERATION
`
`S42
`
`AUTHENTICATE TARP PACKET
`
`RECEIVED
`
`S43
`
`DECRYPT OUTER LAYER
`ENCRYPTION WITH LINK KEY
`
`INCREMENTPERISHABLE
`COUNTER IF DECOY
`
`S44
`
`S45
`
`THROW AWAY DECOY OR KEEP
`IN RESPONSE TO ALGORITHM
`
`S46
`
`CACHE TARP PACKETS UNTIL
`
`WINDOW IS ASSEMBLED
`
`S47
`
`S48
`
`DEINTERLEAVE PACKETS
`FORMING WINDOW
`
`DECRYPT BLOCK
`
`MANGROVE 1001
`
`

`
`
`
`U.S.Patent
`
`nE<._.
`
`
`
`
`
`$523565va§o<7:3
`
`Dec.31,2002
`
`Md.Ev_o<n_5<Ea
`
`
`
`§_.m_v_o<n_z>mmQ
`
`
`
`._<z__>_mm:.._.zm__._o
`
`
`
`aEzo_z:_z_zoaammmaaw
`
`Sheet9of35
`
`
`
`ma5,‘zo_zEz_zoammwsomm
`
`US 6,502,135 B1
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 10 0135
`
`US 6,502,135 B1
`
`mas
`
`ammpaom
`
`
`
`
`
`am_._.zm__._o
`
`m>_§m
`
`£§.§.§_8g§N.§Qwas
`
`
`
`Nq¢o~w,Ném_._N~voN¢.N;m_
`
`m§.3~_2N_§.E.§_§.§
`
`
`
`mw¢o~w_Ném_.~:vo~w.Nen_
`
` _NN_3N.wE.E§.oN.§.SF.3.32%.3;Qm_._m<._. §§z...§.N:VoN_£N_E$_.3N.w_,~.E_m2_§.§.Ea_g§N_SF.
`._.__>_mz<m._.
`
`
`
`
`
`mwE$CS%§H
`
`
`
`«NWwasm>Ew_
`
`
`
`¢»¢o~w_Ném___@<vo~m_Ném_
`
`E.§.E.§_§8.§.§
`
`
`
`NNe¢o~w_Nem,._o~¢o~w_Ném_
`
`
`
`m«Vo~w_Ném_¢_<qo~w_NemF
`
`
`
`
`
`§_3N.SN.E $_g§N.§_m:_3N.S~.ERZVONSN..2_§_§.§_§NE_3N.£N.:2_8_3~.mE_E$.g§N.F2_
`
`m.o_.._
`
`00EVORGNAM
`
`MANGROVE 1001
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 11 of 35
`
`US 6,502,135 B1
`
`:9
`
`N2:
`
`22
`
`:9
`
`“ES
`
`$59.
`
`“asm%_
`
`$52
`
`maso%_
`
`E53
`
`58
`
`mm?
`
`88
`
`ES
`
`‘V,8,
`
`S.©_u_
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`
`
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 12 0135
`
`US 6,502,135 B1
`
`mmo<mI
`
`mv_2E_
`
`
`3:2”mm%2$__o%252<322”m$%o<$_.o%
`2$$%o<>>_._.Eomg:22221m$m_e_<>>I.5mo
`
`mzétmzmmxm.m_>_§Ez$Im
`Eem__._$5:
`
`K8:»(8:
`
`22.o:m$~_8<n__mo%om_$$%Q<n___5mo22.21m$m8<n_:$o:_E:wm2aQ<n__mo%ow<2:
`
`
`
`
`
`
`
`
`
` 2:2SEsigma0222Em:_>__5wa
`
`295252:;5<o2§
`
`S.O_u_
`
`IIY
`
`2:
`
`25<o2<n_
`
`
`
`02:2Em:_>__§_o
`
`mg:2”m.m%9:_HmaE<222”mm_§<n__52.8
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 13 0135
`
`US 6,502,135 B1
`
`S8
`
`SS
`
`
`
`o3:01;:oo._<n_o_._>>_._mo._<..._o_._n__<o._<n_o_._n__
`
`xx:X22xgsX22
`
`zo:<o_E<
`
`<3.o_u_
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 14 0135
`
`US 6,502,135 B1
`
`BEm_o._.<z_s__mom_o
`
`$3,;
`
`82%mm25
`
`025z_
`
`82%mm25
`
`02%z_
`
`82%mmz<o
`
`02%z_
`
`m_wm#_8<n__
`
`32>mm25
`
`025z_
`
`82>mmz<o
`
`02$z_
`
`83>ms25
`
`02$z_
`
`m_§>E<I
`
`$mm_~_8<
`
`
`
`maoz._._<mam_s_<m
`
`E5528mo
`
`282%
`
`2%_._o<mmeex:
`
`8:;ma25
`
`02:,z_
`
`ms..w_u_
`
`302
`
`mo
`
`:ms_a8_>m
`
`m88m__>_oE._
`
`
`
`m=o8m__>_oE.N
`
`zn_>ma
`
`
`
`mm_<>>n_m_<_._.m
`
`2&0:
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 15 of 35
`
`US 6,502,135 B1
`
`mhzmzo
`
`Hm¥o<m
`
`mmmoommmm>
`
`.o4<ezm
`
`o_m_
`
`Hm>momo
`
`Fmxu<m
`
`2.o_u_
`
`
`
`2058m:<>_E
`
`V
`
`mas,02$
`
`was,025
`
`
`
`;_o_Eon_Osman:
`
`mom_
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`
`
`

`
`3U
`
`tnm
`
`P:__<&_
`
`MmmmAm
`
`U
`
`m$E_>_wz<E
`
`
`
`
`
`%_Ezm_n__amn_m_mfiozmm
`
`
`figzma9:ma_8mme02$z_Em:MwA......................:vEN_zo$az>$zm_%mmEmmozmmmom02$z_.Em§
`1mB.H53OEWBmmxillllllv$N_zo$_oz>m
`
`MANGROVE 1001
`
`

`
`
`
`U.S.Patent
`a5.023@zo_E_zo%oz>mE1;@
`
`
`
`
`
`§_mz<Eg:_%z<Ewzawm
`
`Dec.31,2002
`Sheet170135
`
`$:_s_mz<Ez__E95%Hfiemxmim_Fz_o._§$oz__>_8z_.E_>>
`m_<&_Eoeamxo3,-52Hémzmo.2.”_mzo%_mm_
`
`
`$>_§<m5,1023zmis#
`$>_§<Sm02$22%.52oza:am025
`>>8z_>>M295.-
`
`
`
`
`ummE<mIo2_s_ooz__.E>>n__;__oe_om_Io$E_>_mz<E
`
`
`auaxom_mm>_m_om_m_Eémzmeoz<=E0m_<n_
`-.Emzmo
`
`
`
`as?E2:§<o_oo_$._
`
`US6,502,135B1
`
`MANGROVE 1001
`
`
`
`3%m_<n_n__$:__2wz<Ez_5%
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 18 0135
`
`US 6,502,135 B1
`
`f
`
`—.?———:_.:—j>
`
`‘.._.
`
` }
`
`FIG.16
`
`MANGROVE 1001
`
`L‘?
`O?
`'
`
`3<
`
`4095
`
`$
`
`I-K3
`C7
`Q’
`
`3‘
`
`CD
`
`I!)
`C)
`"
`
`1W
`
`i
`
`
`
`20
`
`
`
`(ETHERNETLAN-TWOAADDRESSBLOCKS)
`
`
`
`
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 19 0135
`
`US 6,502,135 B1
`
`000
`
`W|NDOW_S|ZE
`
`
`
`I INACTIVE
`ACTIVE
`
`ig, USED
`
`
`
`W'”°°W-SEE 7//////////////////////A
`7//////////////////////A
`
`
`
`7//////////////////////A
`
`
`7/////////////////////Z
`
`FIG. 17
`
`MANGROVE 1001
`
`
` ?
`
`
`,///////////////////////A
`
`
`
`
`
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 20 of 35
`
`US 6,502,135 B1
`
`| INACTIVE
`ACTIVE
`
`agk USED
`
`MANGROVE 1001
`
`——
`
`000
`
`
`_'////////////////I/////.
`,'////////////////I/////.
`
`
`
`WlNDOW_S|ZE
`
`WlNDOW_S|ZE
`
`///A
`
`FIG. 18
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 21 0135
`
`US 6,502,135 B1
`
`7//////////////////////A
`
`
`
` 7//////////////////////A
`
`
`7///////////////////////.
`V///////////////////////.
`
`O00
`
`W|NDOW_S|ZE
`
`INACTIVE
`
`% ACTIVE
`
`
`
`%
`
`O00
`
`MANGROVE 1001
`
`
`
`
`
`
`
`7//////////////////////A
`'//////////////////////A
`,7////////////////////fl
`,7///////////////////I//.
`7//////////////////I///A
`
`W|NDOW_S|ZE
`
`
`
`
`
`
`FIG. 19
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 22 0135
`
`US 6,502,135 B1
`
`2011
`
`FIG.20
`
`MANGROVE 1001
`
`COMPUTER #2
`
`
`
`
`COMPUTER #1
`
`
`2005
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 23 of 35
`
`US 6,502,135 B1
`
`AD TABLE
`
`IP1
`
`{P3
`
`IP2
`
`IP4
`
`AE TABLE
`
`AF TABLE
`
`BD TABLE
`
`BE TABLE
`
`BF TABLE
`
`IIIIIIIIKIIIIIII
`
`CD TABLE
`
`CE TABLE
`
`CF TABLE
`
`2101
`
`2102
`
`2103
`
`2104
`
`2105
`
`2106
`
`2107
`
`2108
`
`2109
`
`LINK DOWN
`
`2100 /{
`
`FIG. 21
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 24 0135
`
`US 6,502,135 B1
`
`
`
`MEASURE
`QUALITY OF
`TRANSMISSION
`PATH X
`
`MORE
`
`
`
`
`
`THAN ONE
`TRANSMITTER
`TURNED
`
`ON?
`
`TO MIN. VALUE
`
`2209
`
`SET WEIGHT
`
`
`
`DECREASE
`WEIGHT FOR
`PATH X
`
`PATH X
`
`
`
`WEIGHT LESS
`THAN STEADY
`STATE
`VALUE?
`
`
`
`FOR PATH X
`TOWARD STEADY
`
` INCREASE WEIGHT
`STATE VALUE
`
` ADJUST WEIGHTS
`
`
`FOR REMAINING
`PATHS SO THAT
`
`WEIGHTS EQUAL ONE
`
` FIG. 22A
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 25 0135
`
`US 6,502,135 B1
`
` (EVENT) TRANSMITTER
`2210
`
`FOR PATH X
`
`TURNS OFF
`
`
`
`
`
`
`AT LEAST
`ONE TRANSMITTER
`TURNED ON?
`
`
`
`NO
`
`DROP ALL PACKETS
`UNTILA TRANSMITTER
`TURNS ON
`
`2211
`
`
`
`SET WEIGHT
`
`2212
`
`TO ZERO
`
`ADJUST WEIGHTS
`
` 2213
`
`FOR REMAINING
`
`
`PATHS SO THAT
`
`WEIGHTS EQUAL ONE
`
` 2214
`
`FIG. 22B
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`S.U
`
`M
`
`mmu
`
`3Mmm
`
`/0S
`
`wE:__>_mz<ED520$
`
`.83
`
`
`
`Mwas=_>_mz<Ew/
`
`E
`
`
`
`U2252329522
`
`
`
`:m__>_§2_<:m_>_m_%m$s_
`
`
`
`:.:<:ov_z_._
`
`1MwmmGEMW
`
`MANGROVE 1001
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 27 0135
`
`US 6,502,135 B1
`
`mmhgmzoo
`
`mmhamzoo
`
`«N_e_“_
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 28 0135
`
`US 6,502,135 B1
`
`593
`
`m._._m$2
`
`fiesommB;
`
`mm.0_..._
`
`62meg
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 29 of 35
`
`US 6,502,135 B1
`
`E.me_E0
`
`Eoz_&oI
`
`Es
`
`mmmaomm
`
`gem
`
`:8
`
`88wz_n_n_o_._m_
`
`
`
`EaEmsm_%om_m
`
`mm.0_n_
`
`00EVORGNAM
`
`MANGROVE 1001
`
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 30 0135
`
`US 6,502,135 B1
`
`2701
`
`RECEIVE DNS
`REQUEST FOR
`
`TARGET SITE
`
`2703
`
`
`
`SECURE SITE
`REQUESTED?
`
`ACCESS TO
`
`
`PASS THRU
`REQUEST TO
`DNS SERVER
`
`YES
`
`2705
`
`
`
`USER
`AUTHORIZED TO
`CONNECT?
`
`
`
`RETURN
`"HOST UNKNOWN"
`ERROR
`
`2702
`
`2704
`
`YES
`
`2705
`
`ESTABLISH
`VPN WITH
`
`TARGET SITE
`
`FIG. 27
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`tHCtaP3nu
`
`Dec. 31, 2002
`
`Sheet 31 of 35
`
`1B531,20596SU
`
`momm
`
`Nona
`
`meow
`
`mmpaom
`
`Hmo:
`
`Nfimmhamzoo
`
`mm.o_u_
`
`Ewe:
`
`_%mmH=m2oo
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 32 0135
`
`US 6,502,135 B1
`
`O3
`C\l
`
`j
`
`H
`
`8C\l
`
`§
`5
`&
`
`O
`8
`§
`5
`E-
`
`C\l
`=I=I=
`x
`E
`an
`E
`0
`0
`I-—
`cn
`o
`II:
`
`ECD
`II:
`(2:1:
`
`I
`
`8
`N
`
`§
`“'
`
`LO
`3
`$1
`
`10
`
`§
`N
`
`8
`on
`<\l
`
`‘_.
`‘)
`
`EG
`
`0
`
`3 '
`
`1‘
`
`EO
`
`...J
`
`8
`%
`
`K
`EH
`$8
`ca:
`
`3
`%
`
`35
`m
`5
`Q_
`CE)
`0
`"’
`U)
`0
`
`3:
`
`
`
`C")
`T“
`3
`
`g
`N
`
`.1
`
`E
`:-2
`0.
`E
`o
`ca:
`l.IJ
`Z
`o
`<:
`II:
`
`§
`€\l
`
`é’
`C\l
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 33 of 35
`
`US 6,502,135 B1
`
`$Es_mz<E
`
`m_>_m_omm
`
`8m-oz>w
`
`e_§_o
`
`32cm.O_n_
`
`88
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 34 0135
`
`US 6,502,135 B1
`
`3103
`
`3106
`
`3104
`
` CLIENT#2
`
`3105
`
` FIG.31
`
` TX/RX
`
`TX/RXTX/RX
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 35 0135
`
`US 6,502,135 B1
`
`CLIENT
`
`SERVER
`
`SEND DATA PACKET
`
`II§'rIITG§K€’TITI' N
`GENERATE NEW CKPT_N
`
`START TIMER, SHUT
`TRANSMITTER OFF
`
`IF CKPT_O IN SYNC_ACK
`MATCHES TRANSMITTER'S
`CKPT_O
`UPDATE RECE|VER'S
`CKPT_R
`KILL TIMER, TURN
`TRANSMITTER ON
`
`SEND DATA PACKET
`USING CKPT_N
`CKPT_O=CKPT_N
`GENERATE NEW CKPT_N
`START TIMER, SHUT
`TRANSMITTER OFF
`
`WHEN TIMER EXPIRES
`TRANSMIT SYNC_REQ
`USING TRANSMITTERS
`CKPT_O, START TIMER
`
`IF CKPT_O IN SYNC_ACK
`MATCHES TRANSMITTER'S
`CKPT_O
`UPDATE RECE|VER'S
`CKPT_R
`KILL TIMER, TURN
`TRANSMITTER ON
`
`SYNQREQ
`
`FIG. 32
`
`f;I‘(§,§P(§IIé,I’PPf§ACK
`
`GENERATE NEW CKPT_N
`GENERATE NEW CKPT_R
`FOR TRANSMITTER SIDE
`TRANSMIT SYNC_ACK
`CONTAINING CKPT_O
`
`CKPT O=CKPT N
`GENERATE NEW CK
`PT_N
`GENERATE NEW CK
`PT_R
`FOR TRANSMITTER SIDE
`TRANSM|TSYNC_ACK
`CONTAINING CKPT_O
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`US 6,502,135 B1
`
`1
`AGILE NETWORK PROTOCOL FOR
`SECURE COMMUNICATIONS WITH
`ASSURED SYSTEM AVAILABILITY
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application claims priority from and is a
`continuation-in-part of previously filed U.S. application Ser.
`No. 09/429,643, filed on Oct. 29, 1999. The subject matter
`of that application, which is bodily incorporated herein,
`derives from provisional U.S. application No. 60/106,261
`(filed Oct. 30, 1998) and No. 60/137,704 (filed Jun. 7, 1999).
`BACKGROUND OF THE INVENTION
`
`Atremendous variety of methods have been proposed and
`implemented to provide security and anonymity for com-
`munications over the Internet. The variety stems, in part,
`from the different needs of different Internet users. A basic
`
`heuristic framework to aid in discussing these different
`security techniques is illustrated in FIG. 1. Two terminals, an
`originating terminal 100 and a destination terminal 110 are
`in communication over the Internet. It is desired for the
`
`communications to be secure, that is, immune to eavesdrop-
`ping. For example, terminal 100 may transmit secret infor-
`mation to terminal 110 over the Internet 107. Also, it may be
`desired to prevent an eavesdropper from discovering that
`terminal 100 is in communication with terminal 110. For
`
`example, if terminal 100 is a user and terminal 110 hosts a
`web site, terminal 100’s user may not want anyone in the
`intervening networks to know what web sites he is “visit-
`ing.” Anonymity would thus be an issue, for example, for
`companies that want to keep their market research interests
`private and thus would prefer to prevent outsiders from
`knowing which web-sites or other Internet resources they
`are “visiting.” These two security issues may be called data
`security and anonymity, respectively.
`Data security is usually tackled using some form of data
`encryption. An encryption key 48 is known at both the
`originating and terminating terminals 100 and 110. The keys
`may be private and public at the originating and destination
`terminals 100 and 110, respectively or they may be sym-
`metrical keys (the same key is used by both parties to
`encrypt and decrypt). Many encryption methods are known
`and usable in this context.
`
`To hide traffic from a local administrator or ISP, a user can
`employ a local proxy server in communicating over an
`encrypted channel with an outside proxy such that the local
`administrator or ISP only sees the encrypted traffic. Proxy
`servers prevent destination servers from determining the
`identities of the originating clients. This system employs an
`intermediate server interposed between client and destina-
`tion server. The destination server sees only the Internet
`Protocol
`(IP) address of the proxy server and not
`the
`originating client. The target server only sees the address of
`the outside proxy. This scheme relies on a trusted outside
`proxy server. Also, proxy schemes are vulnerable to traffic
`analysis methods of determining identities of transmitters
`and receivers. Another important limitation of proxy servers
`is that the server knows the identities of both calling and
`called parties. In many instances, an originating terminal,
`such as terminal A, would prefer to keep its identity con-
`cealed from the proxy, for example, if the proxy server is
`provided by an Internet service provider (ISP).
`To defeat traffic analysis, a scheme called Chaum’s mixes
`employs a proxy server that transmits and receives fixed
`length messages,
`including dummy messages. Multiple
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`originating terminals are connected through a mix (a server)
`to multiple target servers. It is difficult to tell which of the
`originating terminals are communicating to which of the
`connected target servers, and the dummy messages confuse
`eavesdroppers’ efforts to detect communicating pairs by
`analyzing traffic. A drawback is that there is a risk that the
`mix server could be compromised. One way to deal with this
`risk is to spread the trust among multiple mixes. If one mix
`is compromised, the identities of the originating and target
`terminals may remain concealed. This strategy requires a
`number of alternative mixes so that the intermediate servers
`
`interposed between the originating and target terminals are
`not determinable except by compromising more than one
`mix. The strategy wraps the message with multiple layers of
`encrypted addresses. The first mix in a sequence can decrypt
`only the outer layer of the message to reveal
`the next
`destination mix in sequence. The second mix can decrypt the
`message to reveal the next mix and so on. The target server
`receives the message and, optionally, a multi-layer
`encrypted payload containing return information to send
`data back in the same fashion. The only way to defeat such
`a mix scheme is to collude among mixes. If the packets are
`all fixed-length and intermixed with dummy packets, there
`is no way to do any kind of traffic analysis.
`Still another anonymity technique, called ‘crowds,’ pro-
`tects the identity of the originating terminal from the inter-
`mediate proxies by providing that originating terminals
`belong to groups of proxies called crowds. The crowd
`proxies are interposed between originating and target termi-
`nals. Each proxy through which the message is sent
`is
`randomly chosen by an upstream proxy. Each intermediate
`proxy can send the message either to another randomly
`chosen proxy in the “crowd” or to the destination. Thus,
`even crowd members cannot determine if a preceding proxy
`is the originator of the message or if it was simply passed
`from another proxy.
`ZKS (Zero-Knowledge Systems) Anonymous IP Protocol
`allows users to select up to any of five different pseudonyms,
`while desktop software encrypts outgoing traffic and wraps
`it in User Datagram Protocol (UDP) packets. The first server
`in a 2+-hop system gets the UDP packets, strips off one layer
`of encryption to add another, then sends the traffic to the next
`server, which strips off yet another layer of encryption and
`adds a new one. The user is permitted to control the number
`of hops. At the final server,
`traffic is decrypted with an
`untraceable IP address. The technique is called onion-
`routing. This method can be defeated using traffic analysis.
`For a simple example, bursts of packets from a user during
`low-duty periods can reveal the identities of sender and
`receiver.
`
`to protect LANs from unauthorized
`Firewalls attempt
`access and hostile exploitation or damage to computers
`connected to the LAN. Firewalls provide a server through
`which all access to the LAN must pass. Firewalls are
`centralized systems that require administrative overhead to
`maintain. They can be compromised by virtual-machine
`applications (“applets”). They instill a false sense of security
`that leads to security breaches for example by users sending
`sensitive information to servers outside the firewall or
`
`encouraging use of modems to sidestep the firewall security.
`Firewalls are not useful for distributed systems such as
`business travelers, extranets, small teams, etc.
`
`SUMMARY OF THE INVENTION
`
`A secure mechanism for communicating over the internet,
`including a protocol referred to as the Tunneled Agile
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`US 6,502,135 B1
`
`3
`
`Routing Protocol (TARP), uses a unique two-layer encryp-
`tion format and special TARP routers. TARP routers are
`similar in function to regular IP routers. Each TARP router
`has one or more IP addresses and uses normal IP protocol to
`send IP packet messages (“packets” or “datagrams”). The IP
`packets exchanged between TARP terminals via TARP rout-
`ers are actually encrypted packets whose true destination
`address is concealed except to TARP routers and servers.
`The normal or “clear” or “outside” IP header attached to
`TARP IP packets contains only the address of a next hop
`router or destination server. That is, instead of indicating a
`final destination in the destination field of the IP header, the
`TARP packet’s IP header always points to a next-hop in a
`series of TARP router hops, or to the final destination. This
`means there is no overt indication from an intercepted TARP
`packet of the true destination of the TARP packet since the
`destination could always be next-hop TARP router as well as
`the final destination.
`
`Each TARP packet’s true destination is concealed behind
`a layer of encryption generated using a link key. The link key
`is the encryption key used for encrypted communication
`between the hops intervening between an originating TARP
`terminal and a destination TARP terminal. Each TARP
`
`router can remove the outer layer of encryption to reveal the
`destination router for each TARP packet. To identify the link
`key needed to decrypt the outer layer of encryption of a
`TARP packet, a receiving TARP or routing terminal may
`identify the transmitting terminal by the sender/receiver IP
`numbers in the cleartext IP header.
`
`Once the outer layer of encryption is removed, the TARP
`router determines the final destination. Each TARP packet
`140 undergoes a minimum number of hops to help foil traffic
`analysis. The hops may be chosen at random or by a fixed
`value. As a result, each TARP packet may make random trips
`among a number of geographically disparate routers before
`reaching its destination. Each trip is highly likely to be
`different for each packet composing a given message
`because each trip is independently randomly determined.
`This feature is called agile routing. The fact that different
`packets take different routes provides distinct advantages by
`making it difficult for an interloper to obtain all the packets
`forming an entire multi-packet message. The associated
`advantages have to do with the inner layer of encryption
`discussed below. Agile routing is combined with another
`feature that furthers this purpose; a feature that ensures that
`any message is broken into multiple packets.
`The IP address of a TARP router can be changed, a feature
`called IP agility. Each TARP router, independently or under
`direction from another TARP terminal or router, can change
`its IP address. A separate, unchangeable identifier or address
`is also defined. This address, called the TARP address, is
`known only to TARP routers and terminals and may be
`correlated at any time by a TARP router or a TARP terminal
`using a Lookup Table (LUT). When a TARP router or
`terminal changes its IP address, it updates the other TARP
`routers and terminals which in turn update their respective
`LUTs.
`
`The message payload is hidden behind an inner layer of
`encryption in the TARP packet that can only be unlocked
`using a session key. The session key is not available to any
`of the intervening TARP routers. The session key is used to
`decrypt the payloads of the TARP packets permitting the
`data stream to be reconstructed.
`
`Communication may be made private using link and
`session keys, which in turn may be shared and used accord-
`ing to any desired method. For example, public/private keys
`or symmetric keys may be used.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`To transmit a data stream, a TARP originating terminal
`constructs a series of TARP packets from a series of IP
`packets generated by a network (IP) layer process. (Note that
`the terms “network layer,” “data link layer,” “application
`layer,” etc. used in this specification correspond to the Open
`Systems Intercomection (OSI) network terminology.) The
`payloads of these packets are assembled into a block and
`chain-block encrypted using the session key. This assumes,
`of course, that all the IP packets are destined for the same
`TARP terminal. The block is then interleaved and the
`
`interleaved encrypted block is broken into a series of
`payloads, one for each TARP packet to be generated. Special
`TARP headers IPT are then added to each payload using the
`IP headers from the data stream packets. The TARP headers
`can be identical to normal IP headers or customized in some
`
`way. They should contain a formula or data for deinterleav-
`ing the data at the destination TARP terminal, a time-to-live
`(TTL) parameter to indicate the number of hops still to be
`executed, a data type identifier which indicates whether the
`payload contains,
`for example, TCP or UDP data,
`the
`sender’s TARP address, the destination TARP address, and
`an indicator as to whether the packet contains real or decoy
`data or a formula for filtering out decoy data if decoy data
`is spread in some way through the TARP payload data.
`Note that although chain-block encryption is discussed
`here with reference to the session key, any encryption
`method may be used. Preferably, as in chain block
`encryption, a method should be used that makes unautho-
`rized decryption difficult without an entire result of the
`encryption process. Thus, by separating the encrypted block
`among multiple packets and making it difficult
`for an
`interloper to obtain access to all of such packets, the contents
`of the communications are provided an extra layer of
`security.
`Decoy or dummy data can be added to a stream to help
`foil traffic analysis by reducing the peak-to-average network
`load. It may be desirable to provide the TARP process with
`an ability to respond to the time of day or other criteria to
`generate more decoy data during low traffic periods so that
`communication bursts at one point in the Internet cannot be
`tied to communication bursts at another point to reveal the
`communicating endpoints.
`Dummy data also helps to break the data into a larger
`number of inconspicuously-sized packets permitting the
`interleave window size to be increased while maintaining a
`reasonable size for each packet. (The packet size can be a
`single standard size or selected from a fixed range of sizes.)
`One primary reason for desiring for each message to be
`broken into multiple packets is apparent if a chain block
`encryption scheme is used to form the first encryption layer
`prior to interleaving. A single block encryption may be
`applied to portion, or entirety, of a message, and that portion
`or entirety then interleaved into a number of separate
`packets. Considering the agile IP routing of the packets, and
`the attendant difficulty of reconstructing an entire sequence
`of packets to form a single block-encrypted message
`element, decoy packets can significantly increase the diffi-
`culty of reconstructing an entire data stream.
`The above scheme may be implemented entirely by
`processes operating between the data link layer and the
`network layer of each server or terminal participating in the
`TARP system. Because the encryption system described
`above is insertable between the data link and network layers,
`the processes involved in supporting the encrypted commu-
`nication may be completely transparent to processes at the IP
`(network) layer and above. The TARP processes may also be
`completely transparent to the data link layer processes as
`
`MANGROVE 1001
`
`MANGROVE 1001
`
`

`
`US 6,502,135 B1
`
`5
`well. Thus, no operations at or above the Network layer, or
`at or below the data link layer, are affected by the insertion
`of the TARP stack. This provides additional security to all
`processes at or above the network layer, since the difficulty
`of unauthorized penetration of the network layer (by, for
`example, a hacker) is increased substantially. Even newly
`developed servers running at
`the session layer leave all
`processes below the session layer vulnerable to