`Munger et ai.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006502135Bl
`US 6,502,135 Bl
`(10) Patent No.:
`(45) Date of Patent:
`Dec. 31, 2002
`
`(75)
`
`( *) Notice:
`
`(63)
`(60)
`
`(54) AGILE NETWORK PROTOCOL FOR
`SECURE COMMUNICATIONS WITH
`ASSURED SYSTEM AVAILABILITY
`Inventors: Edmund Colby Munger, Crownsville,
`MD (US); Douglas Charles Schmidt,
`Severna Park, MD (US); Robert
`Dunham Short, III, Leesburg, VA
`(US); Victor Larson, Fairfax, VA (US);
`Michael Williamson, South Riding, VA
`(US)
`(73) Assignee: Science Applications International
`Corporation, San Diego, CA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.c. 154(b) by 0 days.
`(21) Appl. No.: 09/504,783
`Feb. 15,2000
`(22) Filed:
`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
`Jun. 7, 1999.
`Int. CI? . ... ..... ... ... ... ..... ... ... ... ... ..... ... ... G06F 15/173
`U.S. CI. ........................ 709/225; 709/229; 709/245
`Field of Search ................................. 709/249,223,
`709/225, 229, 245; 713/201
`References Cited
`U.S. PATENT DOCUMENTS
`4,933,846 A
`6/1990 Humphrey et al.
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`0838930
`12/1999
`
`(51)
`(52)
`(58)
`
`(56)
`
`DE
`
`DE
`EP
`EP
`GB
`WO
`WO
`WO
`WO
`WO
`WO
`
`12/1999
`19924575
`4/1998
`2317792
`8/1998
`0858189
`12/1997
`0814589
`6/1998
`WO 98/27783
`12/1998
`WO 98 59470
`7/1999
`WO 99 38081
`9/1999
`WO 99 48303
`11/2000
`WO 00/70458
`7/2001
`WO 01 50688
`OTHER PUBLICATIONS
`Fasbender, Kesdogan, and Kubitz: "Variable and Scalable
`Security: Protection of Location Information in Mobile IP",
`IEEE publication, 1996, pp. 963-967.
`(List continued on next page.)
`
`Primary Examiner---Krisna Lim
`(74) Attorney, Agent, or Firm-Banner & Witcoff, Ltd.
`ABSTRACT
`(57)
`A plurality of computer nodes communicate using seem-
`ingly random Internet Protocol source and destination
`addresses. Data packets matching criteria defined by a
`moving window of valid addresses are accepted for further
`processing, while those that do not meet the criteria are
`quickly rejected. Improvements to the basic design include
`(1) a load balancer that distributes packets across different
`transmission paths according to transmission path quality;
`(2) a DNS proxy server that transparently creates a virtual
`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; (4)
`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.
`
`17 Claims, 35 Drawing Sheets
`
`Petitioner Apple - Ex. 1001
`
`
`
`US 6,502,135 BI
`Page 2
`
`U.S. PATENT DOCUMENTS
`12/1996 Aziz
`5,588,060 A
`5,689,566 A
`11/1997 Nguyen
`5,796,942 A
`8/1998 Esbensen
`5,805,801 A
`9/1998 Holloway et al.
`5,842,040 A
`11/1998 Hughes et al.
`5,878,231 A * 3/1999 Baehr et al. ................ 709/243
`5,892,903 A
`4/1999 Klaus
`5,898,830 A * 4/1999 Wesinger et al.
`........... 709/225
`5,905,859 A
`5/1999 Holloway et al.
`6,006,259 A
`12/1999 Adelman et al.
`6,016,318 A * 1/2000 Tomoike ..................... 370/338
`6,052,788 A
`4/2000 Wesinger, Jr. et al.
`6,079,020 A * 6/2000 Liu ............................ 713/201
`6,119,171 A
`9/2000 Alkhatib
`6,178,505 B1 * 1/2001 Schneider et al.
`.......... 713/168
`6,226,751 B1 * 5/2001 Arrow et al.
`............... 370/351
`6,243,749 B1
`6/2001 Sitaraman et al.
`6,286,047 B1 * 9/2001 Ramanathan et al. ....... 345/733
`6,330,562 B1 * 12/2001 Boden et al.
`................. 707/10
`6,332,158 B1 * 12/2001 Risley et al.
`............... 709/219
`6,353,614 B1 * 3/2002 Borella et al. .............. 370/389
`OlliER PUBLICATIONS
`Linux FreeS/WAN Index File, printed from http://1iberty-
`.freeswan.org/freeswan_trees/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/freeswan_trees/freeswan-1.3/
`doc/glossary.html on Feb. 21, 2002, 25 pages.
`
`Alan O. Frier et aI., "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 aI., "Congestion-Oriented Shortest Multi-
`path Routing", Proceedings of IEEE INFOCOM, 1996, pp.
`1028-1036.
`Jim Jones et aI., "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 aI., "Building Internet Firewalls", Nov.
`1995, pp. 278-297 and pp. 351-375 .
`P. Srisuresh et aI., "DNS extensions to Network Address
`Translators", JuI. 1998,27 pages.
`Laurie Wells, "Security Icon", Oct. 19, 1998, 1 page.
`W. Stallings, "Cryptography And Network Security", 2nd
`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
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 1 of 35
`
`US 6,502,135 Bl
`
`107
`
`26
`
`1lA8
`
`110
`
`100
`ORIGINATING
`TERMINAL
`
`r 25
`
`INTERNET
`
`IP
`ROUTER
`
`IP
`ROUTER
`
`ENCRYPTION KEY
`
`FIG. 1
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 2 of 35
`
`US 6,502,135 Bl
`
`100
`
`TARP
`TERMINAL
`
`107
`
`TARP
`ROUTER
`
`IP
`ROUTER
`
`INTERNET
`
`ROUTER
`----' LINK KEY
`127
`
`0
`
`iTARP
`
`0
`
`LINK KEY
`
`ROUTER
`
`132
`ROUTER
`126
`
`IP
`ROUTER
`
`SESSION KEY
`
`110
`
`FIG.2
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 3 of 35
`
`US 6,502,135 Bl
`
`• • •
`
`INTERLEAVED
`PAYLOAD DATA
`320
`
`SESSION-KEY-ENCRYPTED
`PAYLOAD DATA 330
`TARP PACKET WITH
`ENCRYPTED PAYLOADS 340
`LlNK-KEY-ENCRYPTED
`TARP PACKETS 350
`
`TARP
`DESTINATION
`
`FIG.3A
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q
`e rJ'l
`
`(I)
`I--"
`",N
`
`Ul
`
`o ....,
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`INTO PAYLOADS INTERLEAVED 523
`
`ENCRYPTED BLOCK DIVIDED
`
`I
`
`DUMMY BLOCKS OR DATA
`
`MAY BE ADDED
`
`• • •
`
`DATA STREAM 300
`
`207d •••
`
`FIG. 38
`
`ENCRYPTED PAYLOADS 340
`
`TARP PACKETS WITH
`
`INTO PAYLOADS INTERLEAVED 523
`
`ENCRYPTED BLOCK DIVIDED
`
`'j:" G : .', ,":'.
`,::
`I:':'::": ,:,:' ','/'::':·:'·:1
`
`,.:.',:,
`.. :. ;',: '.
`I':':'·· ::"':':' ':'.: :,:':·::1
`
`:'. :.'.'-,
`. :.......,.,..,-::::,.....,,·::·:·1
`
`:' ,
`"""""'1:,,':::':-:-:-<':"':""':""::'
`
`INTERLEAVE WINDOW 517
`
`C.-J
`.:.J:: g.;.:
`' .. ; .....• ,'. "'1
`
`I"
`
`\..
`A
`) .. :·r (J).';': (z· :}: .:.JJ .';'::: . :-,r:
`'"
`.;. '! '." .. <I r·· ... : ','1' . "'1
`
`y
`B
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e \Jl
`
`(I)
`I--"
`
`Ul
`
`Ul o ....,
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`DATA LINK PROTOCOL
`
`WRAPPER 450
`... ... ... ... ... ,
`! _____
`IIPC l:::····:::·.·:A.-:.· ....... :·::J
`
`I
`
`FIG.4
`
`DATA LINK LAYER 430 -
`
`.. ::·;·:· ..
`
`t
`
`I
`... ::
`
`TARP LAYER 420
`
`IPC t)·.=/::::::
`
`PROM)
`(E.G.) BURN INTO BOARD
`WITH D.L. PROCESSOR
`PROCESSING
`TO COMBINE TARP
`OTHER ALTERNATIVE
`
`PROCESSOR
`WITH OIS IP
`TARP PROCESSING
`COMBINE
`ONE ALTERNATIVE TO
`
`I
`
`NETWORK (IP) LAYER 410
`
`TARP TRANSCEIVER 405
`
`I
`415
`
`t
`
`I IP I
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 6 of 35
`
`US 6,502,135 Bl
`
`LOOP-DECOY
`GENERATION
`
`TARP PACKET
`
`! OUTER LAYER DECRYPTION OF
`TARP PACKET USING LINK KEY
`
`5 CHECK FOR DECOY AND
`
`INCREMENT PERISHABLE DECOY
`COUNTER AS APPROPRIATE
`
`S6
`
`DUMP DECOY
`
`NO
`
`NO
`
`S9
`DETERMINE DESTINATION TARP
`ADDRESS AND STORE LINK KEY
`AND IP ADDRESS
`
`YES
`NEXT-HOP TARP
`ADDRESS AND STORE LINK KEY
`AND IP ADDRESS
`
`NEXT-HOPTARP
`ADDRESS AND STORE LINK KEY
`AND IP ADDRESS
`
`[
`
`GENERATE IP HEADER
`AND TRANSMIT
`
`FIG.5
`
`SO
`
`S2
`
`S3
`
`S4
`
`S5
`
`S7
`
`S8
`
`S10
`
`S11
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 7 of 35
`
`US 6,502,135 Bl
`
`GENERATION
`
`\.. 520
`
`GROUP RECEIVED IP PACKETS "-
`INTO INTERLEAVE WINDOW
`
`S21
`
`DETERMINE DESTINATION TARP
`ADDRESS, INITIALIZE TIll, STORE
`IN TARP HEADER
`
`RECORD WINDOW SEQ. NOS. AND
`INTERLEAVE SEQ. NOS IN TARP
`HEADERS
`,
`CHOOSE FIRST HOP TARP
`ROUTER, LOOK UP IP ADDRESS "-
`AND STORE IN CLEAR IP HEADER,
`OUTER LAYER ENCRYPT
`
`INSTALL CLEAR IP HEADER
`AND TRANSMIT
`FIG.6
`
`S22
`
`S23
`
`S24
`
`525
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 8 of 35
`
`US 6,502,135 Bl
`
`S49 L
`
`DIVIDE BLOCK INTO PACKETS
`USING WINDOW SEQUENCE DATA,
`ADD CLEAR IP HEADERS
`GENERATED FROM TARP
`HEADERS
`S50
`)
`HAND COMPLETED IP PACKETS
`TO IP LAYER PROCESS
`
`S40
`BACKGROUND LOOP-DECOY
`GENERATION
`
`S42
`)
`AUTHENTICATE TARP PACKET
`RECEIVED
`
`S43
`)
`DECRYPT OUTER LAYER
`ENCRYPTION WITH LINK KEY
`S44
`;
`INCREMENT PERISHABLE
`COUNTER IF DECOY
`
`S45
`)
`THROW AWAY DECOY OR KEEP
`IN RESPONSE TO ALGORITHM
`S46
`)
`CACHE TARP PACKETS UNTIL
`WINDOW IS ASSEMBLED
`
`S47 L
`
`DE INTERLEAVE PACKETS
`FORMING WINDOW
`S48
`)
`
`DECRYPT BLOCK
`
`FIG.7
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I--"
`
`Ul
`
`0 ....,
`\C
`'JJ. =- .....
`
`'""'" N c c N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`FIG.8
`
`811 J
`ROUTER
`TARP
`
`-
`
`/'
`
`SECURE SESSION INITIATION ACK 825
`SECURE SESSION INITIATION 824
`
`SSYN ACK ACK PACKET 823
`SSYN ACK PACKET 822
`SSYN PACKET 821
`
`-
`
`CLIENT TERMINAL
`
`801
`
`'" '"
`n
`
`I
`
`I
`
`Petitioner Apple - Ex. 1001
`
`
`
`io-oo"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`io-oo"
`
`Ul
`
`o ....,
`'""'" c
`'JJ. =- .....
`
`'""'" N c c N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`FIG.9
`
`131.218.204.49
`131.218.204.127
`131.218.204.212
`131.218.204.89
`
`131.218.204.119
`131.218.204.201
`131.218.204.66
`131.218.204.161
`
`TRANSMIT TABLE 923
`
`131.218.204.55
`131.218.204.186
`131.218.204.97
`131.218.204.65
`
`131.218.204.12
`131.218.204.139
`131.218.204.221
`131.218.204.98
`
`RECEIVE TABLE 924
`
`131.218.204.49
`131.218.204.127
`131.218.204.212
`131.218.204.89
`
`131.218.204.119
`131.218.204.201
`131.218.204.66
`131.218.204.161
`
`RECEIVE TABLE 922
`
`131.218.204.55
`131,218.204.186
`131,218.204.97
`131.218.204.65
`
`131.218.204.12
`131.218.204.139
`131.218.204.221
`131.218.204.98
`
`TRANSMIT TABLE 921
`
`CLIENT 1
`
`901
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`US. Patent
`
`Dec. 31, 2002
`
`Dec. 31, 2002
`
`Sheet 11 of 35
`
`Sheet 11 0f 35
`
`US 6,502,135 Bl
`
`US 6,502,135 B1
`
`E:
`
`N2:
`
`28
`
`$5<mg
`
`$53
`
`mmfim.5
`
`mmSom
`
`nag0m2
`
`mmSom
`
`58
`
`mm?
`
`8.8
`
`or.0_u_
`-LL
`
`I-:z: w
`Hzmjo
`---I U
`
`‘
`
`52
`
`Petitioner Apple - EX. 1001
`
`Petitioner Apple - Ex. 1001
`
`
`
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I--"
`
`Ul
`
`'""'" N o ....,
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`IP3
`
`;..1105
`
`;..1104
`
`PAYLOAD #3
`
`DISCRIM FIELD: 45
`DEST. IP ADDRESS: 91
`SOURCE IPADDRESS: 71
`
`DEST. HW ADDRESS: 88
`SRC. HW ADDRESS: 53
`ETHERNET FRAME
`
`HEADER
`
`HEADER
`IP PACKET
`
`1160-.
`
`FIG. 11
`
`1113
`
`1105C
`11058
`1105A
`
`11048
`1104A
`
`1112
`1103C
`11038
`1103A
`
`1110
`1102C
`11028
`1102A
`
`11018
`1101A
`
`PAYLOAD #2
`
`DISCRIM FIELD: 13
`DEST. IP ADDRESS: 15
`SOURCE IPADDRESS: 13
`
`HEADER
`IP PACKET
`
`PAYLOAD #1
`
`DISCRIM FIELD: 77
`DEST.IPADDRESS: 14
`SOURCE IP ADDRESS: 10
`
`DEST. HW ADDRESS: 88
`SRC. HWADDRESS: 53
`ETHERNET FRAME
`
`HEADER
`
`HEADER
`IPPACKET
`
`1103-<
`
`-
`
`IP2
`
`1102
`
`-
`
`IP1
`
`1101 -<
`
`1150-.
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I--"
`
`Ul
`
`o ....,
`'""'"
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`W4
`
`'t-
`
`"
`1224
`4
`59 98
`99 45
`15 53
`72 51
`53 88
`3 40
`S 0
`(RX)
`
`\
`1224X
`
`"
`1223
`4
`60 19
`87 49
`14 17
`31 56
`3 40
`53 88
`S 0
`(TX)
`
`W3
`76 10 8
`22 86 62
`18 14 26 (
`81 62 5
`89 6 82
`71 91 45
`S 0 OS
`(TX)
`IPHOP ALG B I IPHOP ALG A HWHOP ALG 0 I HWHOP ALG C I
`\
`1221X
`
`28 36 12
`22 6 98
`19 18 19
`13 15 13
`10 14 77
`57 98 40
`S 0 OS
`(RX)
`
`STACK -
`ISO
`
`....L
`316
`
`7-_
`
`APPLICATION
`
`USER
`
`1209X..---
`APPLICATION f--STACK
`ISO
`USER
`\
`1203
`
`22 86 62
`18 14 26
`81 62 5
`89 6 82
`71 91 45
`57 98 40
`S 0 OS
`(RX)
`
`---\
`
`FIG.12A
`
`'I'-W2
`
`1211
`\
`4
`51 91
`60 19
`87 49
`14 17
`31 56
`3 40
`S 0
`(RX)
`
`\
`1211X
`
`"
`1210
`\
`37 3
`59 98
`99 45
`15 53
`72 51
`53 88
`S 0
`(TX)
`
`-\
`
`1208
`(
`4 29 20
`28 36 12
`22 6 98 I
`19 18 19
`13 15 13
`10 14 77
`S 0 OS
`(TX)
`IPHOP ALG A I IPHOP ALG B HWHOP ALG C J HWHOP ALG 0 J
`\
`1208X
`
`1209
`(
`
`W1
`
`00
`1)15
`
`\
`ETHERNET
`
`00
`\ \
`1206 1207
`
`....L
`
`12\
`
`1202
`
`1201
`
`Petitioner Apple - Ex. 1001
`
`
`
`i-o"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`i-o"
`
`Ul
`
`o ....,
`'""'"
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`FIG. 12B
`
`:
`
`I
`
`i
`
`CAN BE VARIED
`
`IN SYNC
`
`CAN BE VARIED
`
`IN SYNC
`
`CAN BE VARIED
`
`IN SYNC
`
`DISCRIMINATOR FIELD
`
`VALUES
`
`CAN BE VARIED
`
`IN SYNC
`
`CAN BE VARIED
`
`IN SYNC
`
`CAN BE VARIED
`
`IN SYNC
`
`IP ADDRESSES
`
`CAN BE VARIED
`
`IN SYNC
`
`FIXED FOR EACH VPN
`
`SAME FOR ALL NODES
`
`OR COMPLETELY
`
`RANDOM
`
`ADDRESSES
`HARDWARE
`
`HOPPING
`3. HARDWARE
`PERVPN
`2. PROMISCUOUS
`
`1. PROMISCUOUS
`EMBODIMENT
`
`OR
`MODE
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`(I)
`I--"
`Q ",N
`1J.
`0'1
`rJ'l
`e
`
`Ul
`
`0 ....,
`'""'" Ul
`.....
`'JJ. =-
`
`N
`C
`C
`N
`'""'"
`!"l
`
`..... =
`.....
`•
`rJl
`d •
`
`CLIENT B
`
`1304
`
`FIG. 13
`
`PACKET
`DISCARD
`
`PACKET
`
`.
`
`1310
`
`RNGALG.
`
`COMBINED SYNC
`
`1309
`
`1307
`fDECRYPTl
`
`PAYLOAD
`ENCRYPTED
`L1NK·KEY
`
`I
`
`(PRIVATE PORTION)
`
`SYNC VALUE
`
`(PUBLIC PORTION)
`IP DEST. ADDRESS
`IP SOURCE ADDRESS
`
`SYNC VALUE
`
`1305-< I
`
`"---/
`
`ISP#2
`
`I
`
`"---/
`
`ISP #1
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I ,
`
`CLIENT A
`
`1303
`
`1302
`
`1301
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I--"
`
`Ul
`
`'""'" 0'1 o ....,
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`--------------------------------______ ckpU
`ckptn
`--ckpt_o
`CURRENT IP PAIR
`
`RECEIVER
`
`--------.. ckpt n
`--------------____ --------.. ckpto
`IP PAIR W ./
`•
`:
`IP PAIR 2
`IP PAIR 1
`
`--_____
`---.. WINDOW -<
`
`-
`
`------------------------------
`
`ckpU ... ------
`ckptn --
`ckpto
`IPPAIRW
`•
`• •
`IP PAIR 2
`IP PAIR 1 """
`
`WINDOW
`
`SENDER'S ISP
`RECEIVER
`
`ckpt r -..-
`--------
`ckptn ... -___
`--
`ckpto ... -___
`CURRENT IP PAIR ... ---__
`
`-----r--
`
`TRANSMITTER
`
`... ------------------------.-
`
`RECIPIENT'S ISP
`TRANSMITTER
`
`FIG. 14
`
`KEPT IN SYNC FOR RECIPIENT TO SENDER SYNCHRONIZER
`KEPT IN SYNC FOR SENDER TO RECIPIENT SYNCHRONIZER
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I--"
`
`Ul
`
`-..J o ....,
`'""'"
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`IP PAIR ckptr
`USING NEW CHECKPOINT
`• TRANSMIT SYNC_ACK
`ckptr IN TRANSMITTER
`CHECKPOINT IP PAIR
`• GENERATE NEW
`ckptn IN RECEIVER
`CHECKPOINT IP PAIR
`• GENERATE NEW
`W
`• UPDATE WINDOW
`WITH INCOMING HEADER =
`* WHEN SYNC_REQ ARRIVES
`
`t RECEIVER'S ckptn:
`
`t
`
`tw
`
`i
`
`I
`
`FIG. 15
`
`CHECKPOINT ckptr
`NEW RECEIVER RESPONSE
`PAIR ckptnAND GENERATE
`TRANSMITTER CHECKPOINT IP
`SYNC_REO USING NEW
`PERIODICALLY UNTIL ACKed)
`BEGINS TRANSMIT (RETRANSMIT
`@ WHEN SYNCHRONIZATION
`@
`
`#
`
`ckptn IN TRANSMITTER
`CHECKPOINT IP PAIR
`GENERATE NEW
`HEADER = ckptr:
`ARRIVES WITH INCOMING
`# WH EN SYNC _ACK
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`US. Patent
`
`Dec. 31, 2002
`Dec. 31,2002
`
`Sheet 18 of 35
`Sheet 18 0f 35
`
`US 6,502,135 Bl
`US 6,502,135 B1
`
`c.o
`.
`FIG.16
`(9
`u..
`
`• T""-
`
`'—
`
`T""-
`
`..
`
`Petitioner Apple - EX. 1001
`
`4095
`
`0 4
`
`095
`
`0
`
`LO 0>
`4095
`"""'"
`
`0 4
`
`1.O 0>
`095
`"""'"
`
`|
`
`20
`1-----/ C"J
`
`00
`
`20
`
`<...:> o ---I co en en w cr:: 0 0 <C
`
`
`
`
`
`en
`
`::::.::::
`
`(ETHERNETLAN-TWOAADDRESSBLOCKS)
`
`<C
`0
`
`::s
`I :z:
`I-
`UJ
`:z: cr:: w
`:::c I-
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 19 of 35
`
`US 6,502,135 Bl
`
`INACTIVE
`ACTIVE
`USED
`
`000
`
`• • •
`
`• • •
`
`• • •
`
`FIG. 17
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 20 of 35
`
`US 6,502,135 Bl
`
`INACTIVE
`ACTIVE
`USED
`
`000
`
`• • •
`
`•
`• •
`
`• • •
`
`FIG. 18
`
`Petitioner Apple - Ex. 1001
`
`
`
`U.S. Patent
`
`Dec. 31, 2002
`
`Sheet 21 of 35
`
`US 6,502,135 Bl
`
`000
`
`• • •
`
`INACTIVE
`ACTIVE
`USED
`
`000
`
`FIG. 19
`
`Petitioner Apple - Ex. 1001
`
`
`
`0'1 1J. Q
`e rJ'l
`
`(I)
`I--"
`",N
`
`US 6,502,135 B1
`
`I--"
`
`Ul
`
`N N o ....,
`'JJ. =- .....
`
`Sheet 22 0f 35
`
`Dec. 31, 2002
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`US. Patent
`
`•
`
`)
`
`COMPUTER #2
`
`
`
`FIG. 20
`
`2011
`V
`
`2011
`
`FIG.20
`
`\..
`
`2008
`
`2008
`
`2005
`
`Petitioner Apple - EX. 1001
`
`
`COMPUTER #1
`
`
`
`2001
`
`
`
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 23 of 35
`
`US 6,502,135 Bl
`
`2101
`
`2102
`
`2103
`
`2104
`
`2105
`
`2106
`
`2107
`
`2108
`
`2109
`
`AD TABLE
`IP1
`IP2
`IP3
`IP4
`
`AE TABLE
`
`AF TABLE
`
`BDTABLE
`
`BE TABLE
`
`BF TABLE
`
`CD TABLE
`
`CE TABLE
`
`CFTABLE
`
`FIG. 21
`
`LINK DOWN
`
`2100)
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 24 of 35
`
`US 6,502,135 Bl
`
`2201
`
`2202
`
`NO
`
`2205
`
`2206
`
`MEASURE
`QUALITY OF
`TRANSMISSION
`PATH X
`
`YES
`
`INCREASE WEIGHT
`FOR PATH X
`TOWARD STEADY
`STATE VALUE
`
`ADJUST WEIGHTS
`FOR REMAINING
`PATHS SO THAT
`WEIGHTS EQUAL ONE
`
`2209
`
`NO
`
`SET WEIGHT
`TO MIN. VALUE
`
`YES
`2208
`
`DECREASE
`WEIGHT FOR
`PATH X
`
`FIG.22A
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 25 of 35
`
`US 6,502,135 Bl
`
`2215
`
`o DROP ALL PACKETS
`N UNTIL A TRANSMITTER
`TURNS ON
`
`2210
`
`(EVENT) TRANSMITTER
`FOR PATH X
`TURNS OFF
`
`2211
`
`2212
`
`2213
`
`2214
`
`YES
`
`SET WEIGHT
`TO ZERO
`
`ADJUST WEIGHTS
`FOR REMAINING
`PATHS SO THAT
`WEIGHTS EQUAL ONE
`
`DONE
`
`FIG. 228
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I--"
`
`Ul
`
`....,
`0
`N 0'1
`.....
`'JJ. =-
`
`C N
`N c
`'""'"
`·
`I"l
`
`= .....
`.....
`•
`d • rJl
`
`FIG. 23
`
`FUNCTION
`ADJUSTMENT
`WEIGHT V 2305
`
`FUNCTION
`MEASUREMENT
`LINK QUALITY
`
`2304
`
`2301
`
`PATH X4
`
`PATH X3
`
`PATH X2
`
`PATH X1
`
`If306
`
`'"
`
`•
`
`•
`
`W(X4) = 0.1
`W(X3) = 0.6
`W(X2) = 0.1
`l W(X1) = 0.2
`2303
`
`....
`
`• RECEIVER
`I PACKET
`
`!
`
`2309
`
`S D L
`RECEIVE TABLE
`
`!
`
`2307
`
`TRANSMITTER
`PACKET
`I
`2302
`
`TRANSMIT TABLE
`
`S D
`
`\
`
`2308
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`(I)
`
`0'1 1J. Q N
`e rJ'l
`
`Ul
`
`0 ....,
`-..J
`N
`'JJ. =- .....
`
`'""'" N c C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`! CO:PUTER I
`
`2402
`
`/
`
`\
`
`FIG. 24
`
`25 Mb/s MESS T = 8
`75 Mb/s MESS T = 24
`100 Mb/s MESS T = 32
`
`2404
`
`2403
`
`COMPUTER 1-1 ----I
`
`2401
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 28 of 35
`
`US 6,502,135 Bl
`
`en z Cl
`
`LOt='
`-0:::
`(,90
`-0:::
`
`LLo... --
`
`Petitioner Apple - Ex. 1001
`
`
`
`I-"
`
`0'1 1J. Q ",N
`e rJ'l
`
`(I)
`I-"
`
`Ul
`
`\C o ....,
`'JJ. =- .....
`
`N
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`2611
`
`2604
`
`TARGET SITE
`UNSECURE
`
`liP HOPPING
`2608
`SECURE TARGET SITE
`
`FIG. 26
`
`2603
`
`I HOPPING I I RULES I
`
`GATE KEEPER
`
`2602
`
`PROXY
`DNS
`
`SERVER
`DNS
`
`HOPPING
`
`IP
`
`2607"", I
`
`BROWSER
`
`WEB
`
`2605
`
`2601
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 30 of 35
`
`US 6,502,135 Bl
`
`2701
`
`2702
`
`2704
`
`2706
`
`RECEIVE DNS
`REQUEST FOR
`TARGET SITE
`
`2703
`
`NO
`
`PASSTHRU
`REQUEST TO
`DNS SERVER
`
`2705
`
`NO
`
`RETURN
`"HOST UNKNOWN"
`ERROR
`
`YES
`
`ESTABLISH
`VPNWITH
`TARGET SITE
`
`FIG. 27
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`(I)
`
`;....
`0'1 1J. Q N
`e rJ'l
`
`Ul
`
`0 ....,
`'""'"
`'JJ. =- .....
`
`'""'" N C C N
`
`!"l
`
`= .....
`.....
`•
`rJl
`d •
`
`;-
`
`..........
`
`INTERNET
`
`---L
`
`HIGH BW
`2805
`
`GUARD
`LINK
`
`I
`
`2810
`I
`
`ISP
`
`\
`2803
`
`FIG. 28
`
`COMPUTER #2
`
`HOST
`
`2804
`
`I
`
`\
`
`I
`
`\
`
`ROUTER
`
`( EDGE
`\
`2802
`
`COMPUTER #1
`
`HOST
`
`2801
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`(I)
`
`0'1 1J. Q N
`e rJ'l
`
`Ul
`
`0 ....,
`N
`'JJ. =- .....
`
`'""'" N c C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`2901
`
`GUARD
`I LINK
`
`'2c::J
`
`ISP
`
`I
`2909 -..J
`
`,
`
`LOWBW
`
`2904
`
`HOST COMPUTER #1
`
`FIG. 29
`
`:/hOOD IP TX 100·200
`
`HACKER COMPUTER
`
`2903
`
`INTERNET
`
`/' -----
`
`(
`
`J
`
`2908 V HIl:iH J;W
`
`2907
`
`2913
`
`2912
`
`RX
`
`TX
`
`I
`
`HOST COMPUTER #2
`
`2902""", I
`
`I..\lVV
`
`I..\lVV
`
`2900
`
`RX
`
`TX
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`(I)
`I--"
`",N
`1J. Q
`0'1
`e rJ'l
`
`Ul
`
`....,
`.....
`'JJ. =-
`
`0
`
`N
`c c
`N
`'""'"
`!"l
`
`..... =
`.....
`d • rJl
`
`•
`
`I
`
`(SYNCjCK)
`CKPT N
`PROCESS
`3011
`
`J
`
`SYNC_REO
`GENERATE
`3010
`
`I
`
`3001
`\
`
`FIG. 30
`
`3003
`!
`
`TX TABLE
`
`w-
`
`I TRANSMITIER
`N
`
`\
`
`SECONDS
`DELAY
`
`3008
`DISCARD
`
`3006
`
`3009
`
`CKPT_N
`GENERATE
`
`3007
`
`(
`
`3000
`\
`
`3002
`!
`
`N
`
`3005
`
`Y
`
`I II
`
`W-N I
`
`RXTABLE
`
`3004
`
`SYNC_REO
`RECEIVE
`
`RECEIVER
`
`Petitioner Apple - Ex. 1001
`
`
`
`I--"
`
`(I)
`
`0'1 1J. Q N
`e rJ'l
`
`Ul
`
`o ....,
`'JJ. =-
`
`'""'" N C C N
`
`!"l
`
`..... = .....
`d • rJl
`
`•
`
`FIG. 31
`
`3105
`
`HACKER
`
`3210
`
`3209
`
`3208
`
`3104
`
`CLIENT #2
`
`3103
`
`CKPT_R
`CKPT 0
`CKPT N
`
`CLIENT #1
`
`3111
`
`TXlRX TXlRX TXlRX
`
`3102
`
`3112
`CKPT R
`CKPT 0
`CKPT N
`CKPT R
`CKPT 0
`CKPT_N
`
`3107
`
`3101
`
`Petitioner Apple - Ex. 1001
`
`
`
`u.s. Patent
`
`Dec. 31, 2002
`
`Sheet 35 of 35
`
`US 6,502,135 Bl
`
`CLIENT
`
`SEND DATA PACKET
`USING CKPT N
`CKPT O=CKPT N
`GENERATE NEW CKPT N
`START TIMER, SHUT -
`TRANSMITIER OFF
`IF CKPT 0 IN SYNC ACK
`MATCHES TRANSMiTTER'S
`CKPT 0
`UPDATE RECEIVER'S
`CKPT R
`KILL TIMER, TURN
`TRANSMITIER ON
`
`SEND DATA PACKET
`USING CKPT N
`CKPT O=CKPT N
`GENERATE NEW CKPT N
`START TIMER, SHUT -
`TRANSMITIER OFF
`WHEN TIMER EXPIRES
`TRANSMIT SYNC REQ
`USING TRANSMITTERS
`CKPL 0, START TIMER
`
`IF CKPT 0 IN SYNC ACK
`MATCHE-S TRANSMITTER'S
`CKPT 0
`UPDATE RECEIVER'S
`CKPT R
`KILL TIMER, TURN
`TRANSMITIER ON
`
`SERVER
`
`PASS DATA UP STACK
`CKPT O=CKPT N
`GENERATE NEW CKPT N
`GENERATE NEW CKPf R
`FOR TRANSMITIER SIDE
`TRANSMIT SYNC ACK
`CONTAINING CKPT_O
`
`X
`
`CKPT O=CKPT N
`GENERATE NEW CKPT N
`GENERATE NEW CKPT-R
`FOR TRANSMITIER SIDE
`TRANSMIT SYNC ACK
`CONTAINING CKPtO
`
`FIG. 32
`
`Petitioner Apple - Ex. 1001
`
`
`
`US 6,502,135 Bl
`
`40
`
`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
`A tremendous 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 25
`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 55
`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 60
`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 65
`employs a proxy server that transmits and receives fixed
`length messages, including dummy messages. Multiple
`
`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
`5 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
`10 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
`15 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
`20 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-
`30 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
`35 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.
`Firewalls attempt to protect LANs from unauthorized
`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
`
`45
`
`50
`
`Petitioner Apple - Ex. 1001
`
`
`
`US 6,502,135 Bl
`
`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 5
`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 10
`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 15
`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 25
`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 35
`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
`