111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007032242B 1
`
`c12) United States Patent
`Grabelsky et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,032,242 Bl
`Apr. 18, 2006
`
`(54) METHOD AND SYSTEM FOR DISTRIBUTED
`NETWORK ADDRESS TRANSLATION WITH
`NETWORK SECURITY FEATURES
`
`wo
`
`FOREIGN PATENT DOCUMENTS
`wo 01/31888
`
`5/2001
`
`(75)
`
`Inventors: David Grabelsky, Skokie, IL (US);
`Michael S. Borella, Naperville, IL
`(US); Ikhlaq Sidhu, Vernon Hills, IL
`(US); Danny M. Nessett, Fremont, CA
`(US)
`
`(73) Assignee: 3Com Corporation, Marlborough, MA
`(US)
`
`( *) Notice:
`
`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/270,967
`
`(22)
`
`Filed:
`
`Mar. 17, 1999
`
`Related U.S. Application Data
`
`(63)
`
`Continuation-in-part of application No. 09/035,600,
`filed on Mar. 5, 1998, now Pat. No. 6,353,614.
`
`(51)
`
`Int. Cl.
`H04K 1100
`H04L 9100
`G06F 15116
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`(52) U.S. Cl. .............................. 726111; 726/3; 726/12;
`726/26; 713/151; 713/153; 713/168; 709/201;
`709/225; 709/229; 380/28; 380/270
`
`(58) Field of Classification Search ................ 713/201;
`370/351, 356, 389
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,953,198 A
`5,159,592 A
`
`8/1990 Daly eta!. .................... 379/61
`10/1992 Perkins
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`G. Montene, Internet Engineering Task Force, Internet
`Draft, "Negotiated Address Reuse" (NAR), <draft-montene(cid:173)
`gro-aatn-nar-OO.txt>, May 1998, pp. 1 to 22.
`
`(Continued)
`
`Primary Examiner---Gilberto Barron, Jr.
`Assistant Examiner-A. Nobahar
`(74) Attorney, Agent, or Firm-McDonnell Boehnen
`Hulbert & Berghoff LLP
`
`(57)
`
`ABSTRACT
`
`A method and system for distributed network address trans(cid:173)
`lation with security features. The method and system allow
`Internet Protocol security protocol ("IPsec") to be used with
`distributed network address translation. The distributed net(cid:173)
`work address translation is accomplished with IPsec by
`mapping a local Internet Protocol ("IP") address of a given
`local network device and a IPsec Security Parameter Index
`("SPI") associated with an inbound IPsec Security Associa(cid:173)
`tion ("SA") that terminates at the local network device. A
`router allocates locally unique security values that are used
`as the IPsec SPis. A router used for distributed network
`address translation is used as a local certificate authority that
`may vouch for identities of local network devices, allowing
`local network devices to bind a public key to a security name
`space that combines a global IP address for the router with
`a set of locally unique port numbers used for distributed
`network address translation. The router issues security cer(cid:173)
`tificates and may itself be authenticated by a higher certifi(cid:173)
`cate authority. Using a security certificate, a local network
`device may initiate and be a termination point of an IPsec
`security association to virtually any other network device on
`an IP network like the Internet or an intranet. The method
`and system may also allow distributed network address
`translation with security features to be used with Mobile IP
`or other protocols in the Internet Protocol suite.
`
`(Continued)
`
`33 Claims, 22 Drawing Sheets
`
`~~-;---,~··~~~--~~
`
`-
`I
`1o.o.o.7 11sa.,o.2o.ao
`\.28
`:
`:
`~
`~
`20
`22
`FAX 24
`i 10.0.0.4 10.0.0.5 10.0.0.6
`i
`t---------------------;~-~~-~~-------1·--J
`
`12
`
`10
`
`/
`
`192.200.20.3
`
`Ex. 1006
`Apple v. MPH Techs. Oy
`IPR2019-00823
`
`0001
`
`

`

`US 7,032,242 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,227,778 A
`5,327,365 A
`5,497,339 A
`5,526,353 A
`5,526,489 A
`5,550,984 A
`5,604,737 A
`5,606,594 A
`5,636,216 A
`5,654,957 A
`5,708,655 A
`5,737,333 A
`5,742,596 A
`5,754,547 A
`5,793,657 A
`5,793,763 A
`5,812,819 A
`5,828,846 A *
`5,835,723 A
`5,862,331 A
`5,867,495 A
`5,867,660 A
`5,872,847 A
`5,889,774 A
`5,892,924 A
`5,915,008 A
`5,933,778 A
`5,950,195 A
`5,968,176 A *
`5,983,350 A *
`6,011,782 A
`6,055,236 A
`6,055,561 A
`6,058,421 A
`6,079,021 A
`6,101,189 A
`6,101,543 A
`6,104,711 A
`6,115,751 A
`6,134,591 A
`6,137,791 A
`6,157,950 A
`6,172,986 B1
`6,185,184 B1
`6,195,705 B1
`6,212,183 B1
`6,212,563 B1
`6,249,820 B1
`6,266,707 B1
`6,269,099 B1
`6,353,614 B1
`6,353,891 B1
`6,438,612 B1 *
`6,510,513 B1 *
`
`7 I 1993 Vacon et a!.
`7 I 1994 Fuji saki et a!.
`............. 364/717
`311996 Bernard ................... 364/705.5
`611996 Henley eta!. ............. 370160.1
`611996 Nilakantan et a!.
`811996 Gelb
`211997 Iwarni eta!. ............... 3701352
`211997 Register eta!. ............... 379158
`611997 Fox eta!.
`811997 Koyama ..................... 3701355
`111998 Toth et a!.
`411998 Civanlar eta!. ............ 3701352
`411998 Baratz eta!. ............... 3701356
`511998 Nakazawa .................. 3701401
`811998 Nemoto ................. 364/717.01
`811998 Mayes et a!.
`911998 Rodwin et al.
`1011998 Kirby eta!. ................ 3701351
`1111998 Andrews eta!. ....... 3951200.56
`111999 Herriot .................. 3951200.49
`211999 Elliott eta!. ................ 3701352
`211999 Schmidt et a!.
`211999 Boyle et al.
`311999 Mirashrafi eta!. .......... 3701352
`411999 Lyon et al ............. 3951200.75
`611999 Dulman ...................... 3791201
`811999 Buhrmann et al .......... 4551461
`911999 Stockwell et a!.
`1011999 Nessett eta!. .............. 7131201
`1111999 Minear et a!.
`.............. 7131201
`112000 DeSimone et al.
`412000 Nessett et a!.
`412000 Feldman et al ............. 7091200
`512000 Fijolek et al.
`. ............. 7091225
`612000 Abadi et al.
`812000 Tsuruoka .................... 3701401
`812000 Alden et al ................. 7091229
`812000 Voit ........................... 3701352
`912000 Tarn et a!.
`.................. 7091240
`1012000 Nickles
`1012000 Frid et al .................... 3701352
`1212000 Krishnan .................... 7091223
`112001 Watanuki et a!. ........... 3701466
`212001 Mattaway et a!.
`.......... 3701230
`212001 Leung ........................ 7091245
`412001 Wilford ...................... 3701392
`412001 Beser ......................... 7091227
`612001 Dobbins et a!.
`............ 7091238
`............... 7091245
`712001 Boden et a!.
`712001 Borella eta!. .............. 3701389
`312002 Borella et a!.
`.............. 3701389
`312002 Borella et a!.
`.............. 7131201
`812002 Ylonen et a!.
`.............. 7091249
`112003 Danieli ....................... 7131156
`
`FOREIGN PATENT DOCUMENTS
`
`wo
`
`WO 01131888 A1
`
`512001
`
`OTHER PUBLICATIONS
`
`George Tsirtis, Alan O'Neill, Internet Engineering Task
`Force, Internet Draft, "NAT Bypass for End 2 End 'Sensi(cid:173)
`tive' Applications," <draft-tsirtsis-nat-bypass-OO.txt>, Jan.
`1998, pp. 1 to 5.
`George Tsirtis, Pyda Srishuresh, Internet Engineering Task
`Force,
`Internet
`Draft,
`"Network
`Address
`Translation-Protocol Translation" (NAT-PT), <draft-ietf(cid:173)
`ngtrans-natpt-04.txt>, Jan. 1999, pp. 1 to 13.
`Jeffrey Lo, K, Taniguchi, Internet Engineering Task Force,
`Internet Draft, "IP Host Network Address (and port) Transla(cid:173)
`tion," <draft-ietf-hnat-OO.txt>, Nov. 1998, pp. 1 to 13.
`
`Michael Borella, David Grabelsky, Ikhlaq Sidhu, Brian
`Petry, Internet Engineering Task Force, Internet Draft,
`"Distributed Network Address Translation," <draft-borella(cid:173)
`aatn-dnat-Ol.txt>, Oct. 1998, pp. 1 to 21.
`P. Srisuresh, G. Tsirsis, P. Akkiraju, A. Heffernan, Internet
`Engineering Task Force, Internet Draft, "DNS Extensions to
`Network Address Translators" (DNS_ALG), <draft-ietf(cid:173)
`nat-dns-Ol.txt>, Oct. 1998, pp. 1 to 24.
`P. Srisuresh, Internet Engineering Task Force, Internet Draft
`"Security for IP Network Address Translator (NAT)
`Domains," <draft-ietf-nat-security-OO.txt.>, Nov. 1998, pp.
`1 to 11.
`P. Srisuresh, K. Eg, Internet Engineering Task Force,
`Internet Draft, "The IP Network Address Translator" (NAT),
`<draft-rfced-info-srisuresh-05.txt>, Feb. 1998, pp. 1 to 24.
`P. Srisuresh, K. Egev, Internet Engineering Task Force,
`Internet Draft, "Traditional IP Network Address Translator
`(Traditional NAT)," <draft-ietf-nat-traditional-01.txt>, Oct.
`1998, pp. 1 to 17.
`P. Srisuresh, Matt Holdrege, Internet Engineering Task
`Force, Internet Draft, "IP Network Address Translator
`(NAT) Terminology and Consideration," <draft-ietf-nat(cid:173)
`terminology-Ol.txt>, Oct. 1998, pp. 1 to 28.
`PraveenAkkiraju, Yakov Rekhter, Internet Engineering Task
`Force, Internet Draft, "A Multihoming Solution Using
`NATs" <draft-akkiraju-nat-multihoming-OO.txt>, Nov. 1998,
`pp. 1 to 32.
`R. G. Moskowitz, Internet Engineering Task Force, Internet
`Draft, "Network Address Translation Issues with IPsec,"
`<draft-moskowitz-net66-vpn-OO.txt>, Feb. 5, 1998, p. 1 to 8.
`R. Thay, N. Doraswa and R. Gle, Internet-Engineering-Task
`Force, Internet Draft "IP Security," <drat-ietf-ipsec-doc(cid:173)
`roadmap-02.txt.>, Nov. 1997, pp. 1 to 12.
`T. Hain, Internet Engineering Task Force, Internet Draft,
`"Architectural
`implications of NAT," <draft-iab-nat(cid:173)
`implications-02.txt>, Oct. 1998, pp. 1 to 14.
`W.T. Teo, S.W. Yeeow, R. Singh, Internet Engineering Task
`Force, Internet Draft, "IP Relocation Through Twice
`Network Address Translator," <draft-ietf-nat-rnat-OO.txt>,
`Feb. 1999, pp. 1 to 20.
`W.T. Teo, S.W. Yeow, R. Singh, Internet Engineering Task
`Force, Internet Draft, "Reverse Twice Network Address
`Translators" (RAT), <draft-teoyeow-mip-rat-Ol.txt>, Dec.
`1998, pp. 1 to 20.
`W.T. Teo, Y. Li, Internet Engineering Task Force, Internet
`Draft, "Mobile IP Extension for Private Internets Support,"
`<draft-teoyli-mobileip-mvpn-02.txt>, Feb. 1999, pp. 1 to 24.
`Yakov Rekhter, Internet Engineering Task Force, Internet
`Draft, "Implications of NATs on the TCP/IP Architecture,"
`<draft-ietf-nat-arch-implications-OO.txt>, Feb. 1999, pp. 1 to
`7.
`K. Egevang and P. Francis, "The IP Network Address
`Translator (NAT)", RFC 1631, Internet Engineering Task
`Force, www.ietf.org/rfc/rfc1631.txt, May 1994, pp. 1 to 10.
`Borella, Michael, Technology Update-Protocol Helps
`Stretch !Pv4 Addresses, "Network World", vol. 17, No. 3,
`Jan. 17, 2000, p. 43.
`Kent, Stephen, Evaluating Certification Authority Security,
`Aerospace Conference, 1998 IEEE, Online, vol. 4, pp.
`319-327 (Mar. 21-23, 1998).
`Thayer, Rodney, Bulletproof IP With Authentication and
`Encryption IPSec Adds a Layer of Armor to IP, Data
`Communications, vol. 26, No. 16, pp. 55-58, 60 (Nov. 21,
`1997).
`Borella, M., Grabelsky, D., Lo, J., Tuniguchi, K., Internet
`Engineering Task Force, Internet Draft, "Realm Specific IP:
`Protocol Specification <draft-ietf-nat -rsip-protocol-.06.
`txt>", Mar. 2000, pp. 1-48.
`
`0002
`
`

`

`US 7,032,242 Bl
`Page 3
`
`Borella, M., Grabelsky, D., Lo, J., Tuniguchi, K., Internet
`Engineering Task Force, Internet Draft, "Realm Specific IP:
`Procotol Specification <draft-ietf-nat-rsip-protocol-. 07.
`txt>", Jul. 2000, pp. 1-49.
`Montenegro, G., Internet Engineering Task Force, Internet
`Draft, "RSIP Support for End-to-End IPsec," <draft-ietf-nat(cid:173)
`rsip-ipsec-04.txt>, Jul. 2000, pp. 1 to 17.
`Borella, M., Lo, J., Grabelsky, D., Montenegro, G., Internet
`Engineering Task Force, Internet Draft, "Realm Specific IP:
`Framework <draft-ietf-nat-rsip-framework-05.txt>", Jul.
`2000, pp. 1-30.
`Borella, M., Montenegro, G., RSIP: Address Sharing with
`End-to-End Security, USENIX Conference, San Francisco,
`California, Mar. 9, 2000, pp. 1-9.
`Handley, M., et a!., SIP: Session Initiation Protocol,
`Network-Working Group, Request for Comments 2543,
`Mar. 1999, pp. 1 to 153.
`ITU-T Recommendation H.225 .0, Call Signaling Protocols
`and Media Stream Packetization
`for Packet-Based
`Multimedia Communication Systems, Series H: Audiovisual
`and Multimedia Systems-Infrastructure of Audiovisual
`Services-Transmission Multiplexing and Synchronization,
`(Feb., 1998).
`.
`.
`ITU-T Recommendation H.323, Packet-Based Multzmedza
`Communications Systems, Series H: Audiovisual and
`Multimedia
`Systems-Infrastructure
`of Audiovisual
`Services-Systems and Terminal Terminal Equipment for
`Audiovisual Services, (Feb. 1998).
`McCaune et a!., "The BSD Packet Filter: A New
`Architecture for User-Level Packet Capture," Proceedings
`of the 1993 Winter USENIX Technical Conference (Jan.
`1993).
`Postel, J., User Datagram Protocol, Request for Comments
`768, Aug. 1980, pp. 1 to 3.
`Postel, J., Internet Protocol, Request for Comments 791,
`Sep. 1981, pp. 1 to 45.
`Postel J., Internet Control Message Protocol, Request for
`Comments 792, Sep. 1981, pp. 1 to 21.
`Postel, J., Transmission Control Protocol, Request for Com(cid:173)
`ments 793, Sep. 1981, pp. ito 84.
`Postel, J., File Transfer Protocol (FTP), Request for Com(cid:173)
`ments 959, Oct. 1985, pp. 1 to 69.
`Jacobson, V., TCP Extensions for High Performance,
`Request for Comments 1323, May 1992, pp. 1 to 37.
`Drams, R., Dynamic Host Configuration Protocol, Request
`for Comments 2131, Mar. 1997, pp. 1 to 45.
`Stevens, W., Advanced Sockets API for IPv6, Request for
`Comments 2292, Feb. 1998, pp. 1 to 67.
`Gilligan, R. et a!., Basic Socket Interface Extensions for
`IPv6, Request for Comments 2553, Mar. 1999, pp. 1 to 41.
`Srisuresh, P.,et a!., IP Network Address Translator(NAT)
`Terminology and Considerations, Request for Comments
`2663, Aug. 1999, pp. 1 to 30.
`Maurice J. Bach, The Design of the Unix Operating System,
`Prentice Hall Software Series, 1986, pp. 382-390.
`Durand, Alain, Deploying Ipv6, IEEE Internet Computing,
`http://computer.org/internet, Jan.-Feb. 2001, pp. 79-81.
`3COM SIP Sloutions 1.0 benefits brochure. ( 4 total pages).
`Sidhu, Ikhlaq and Bezaitis, Andrew, Eat or be eaten, www.
`americasnetwork.com/issues/99issues/9911 01/991191_eat.
`htm, printed May 10, 2000. (6 total pages).
`Myers, Brad A.; Stiel, Herb; and Gargiulo, Robert, Col(cid:173)
`laboration Using Multiple PDAs Connected to a PC,
`Proceedings of the ACM 1998 conference on Computer
`
`supported cooperative work, Nov. 14-18, 1998, Seattle, WA.
`(total 11 pages).
`Dalgic, Ismail; Borella, Michael; Dean, Rick; Grabiec,
`Jacek; Mahler, Jerry; Schuster, Guido; and Sidhu, Ikhlaq,
`True Number Portability and Advanced Call Screening in a
`SIP-Based IP Telephony System, IEEE Communications
`Magazine, vol. 37, No. 7, Jul. 1999, pp. 96-101. (8 total
`pages).
`.
`Handley/Schulzrinne/Schooler/Rosenberg, SIP: Sesswn
`Initiation Protocol, Internet Engineering Task Force, draft(cid:173)
`ietf-sip-rfc2543bis-02.ps. Sep. 4, 2000. (131 pages).
`Borella, M., Lo., J., Grabelsky, D., Montenegro, G., IETF
`Proceedings presentation, Realm Specific IP: Protocol
`Specification <draft-nat-rsip-protocol-OO.txt>, Apr. 9, 1999
`(13 pages).
`Marsan, Carolyn DuffY, The Next Best Things to Ipv6?
`Network World Fusion at http://www.nbwfusion.com/news/
`1999/0920ipv6.html, Mar. 29, 2000, pp. 1-3.
`Borella, M., Lo, J., Grabelsky, D., Montenegro, G., Internet
`Engineering Task Force, Internet Draft, "Realm Specific IP:
`Framework <draft-ietf-nat-rsip-framework-.04.txt>", Mar.
`2000, pp. 1-30.
`IETF Mar. 1999 Proceedings, 2.7.10 Network Address
`Translators (nat), pp. 1-13.
`Rosenberg, Jonathan D. and Shockey, Richard, The Session
`Initiation Protocol (SIP): A Key Component for Internet
`Telephony, ComputerTelephony.com, Jun. 2000, pp. 124-
`139.
`Fenner, W., Internet Group Management Protocol Version 2,
`RFC 2236, Nov. 1997, pp. 1-24.
`Mogul, J. et a!., "Internet Standard Subnetting Procedure",
`RFC 950, Aug., 1985, pp. 1-18.
`Schulzrinne et a!., "RTP: A Transport Protocol for Real(cid:173)
`Time Applications", RFC 1889, pp. 1-75.
`Privat Jermone, "Double Phase DHCP Configuration",
`<draft-privat-dhc-doublephase-01.txt>, Internet Engineer(cid:173)
`ing Task Force, Sep. 1999, pps. 1-4.
`Maughan, D. et a!., "Internet Security Association and Key
`Management Protocol", RFC 2408, Nov. 1998, pps. 1-86.
`Karn, P., "Photuris Session-Key Management Protocol",
`RFC-2522, Mar. 1999, pps. 1-58.
`"Random Number Generators", Computational Science
`Education Projects, 1991, 1992, 1993, 1994, and 1995.
`Foster, Ian, "10 Random Numbers", 1995.
`Borella, Michael et a!., "Realm Specific IP: Protocol
`Specification", <draft-ietf.nat-rsip-protocol-02.txt>, Internet
`Draft, Aug. 1999, pps. 1-27.
`Gilligan, R. eta!., "Transition Mechanisms for IPv6 Hosts
`and Routers", RFC 1933, Apr. 1996, pps. 1-22.
`Afifi, H. eta!., "Method for IPv4-IPv6 Transition", Proceed(cid:173)
`ings IEEE International Symposium on Computers and
`Communications, Jul. 6-8, 1999, pps. 478-484.
`.
`"Cisco lOS Release 12.0 Network Protocols ConfiguratiOn
`Guide, Part. 1", Configuring IP Addressing, Cisco Systems,
`1998, pp. P1C-7 to P1C-58.
`International Search Report for PCT Application Serial No.
`PCT/US00/07057, Dated Aug. 9, 2000.
`"Cisco lOS Release 12.0 Network protocols Configuration
`Guide, Part 1", Configuring IP Addressing, CISCO Systems,
`1998, pp. P1C-7 to PiC-58.
`.
`.
`.
`International Search Report for PCT ApphcatJon Senal No.
`PCT/US00/07057, Dated Aug. 9, 2000.
`* cited by examiner
`
`0003
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 1 of 22
`
`US 7,032,242 Bl
`
`FIG.l
`
`10
`
`/
`
`10.0.0.1
`
`1 0.0.0.2
`
`PRINTER
`
`1 0.0.0.3
`PC
`
`PC
`
`14
`
`16
`
`10.0.0.4 10.0.0.5
`
`10.0.0.6
`
`ROUTER:
`10.0.0.7l198.~0.20.30
`:
`\.28
`
`I
`I
`I
`I
`
`:
`
`I
`I
`
`---------------------~~~~-~~~-------~---J
`
`12
`
`192.200.20.3
`
`0004
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 2 of 22
`
`US 7,032,242 Bl
`
`FIG. 2
`PROTOCOL STACK
`
`APPLICATION
`PROGRAMS
`
`62
`
`UDP
`60
`
`TCP
`58
`
`ICMP
`56
`
`IGMP
`54
`
`PAP
`52
`
`50
`
`IP
`48
`
`46
`
`NETWORK INTERFACE CARD DEVICE DRIVERS
`
`44
`
`__! __ _
`
`0005
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 3 of 22
`
`US 7,032,242 Bl
`
`64
`
`I
`1\
`1\
`
`66
`
`67
`
`FIG.3
`PORT ALLOCATION PROTOCOL (PAP)
`
`PAP REQUEST
`MESSAGE
`
`PAP SECURITY
`REQUEST MESSAGE
`
`PAP RESPONSE MESSAGE
`
`PAP SECURITY
`RESPONSE MESSAGE
`
`PAP INVALIDATE MESSAGE
`
`PAP SECURITY
`INVALIDATE MESSAGE
`
`" 68
`' 68
`' 70
`
`1\
`71
`
`COMBINATION NETWORK ADDRESS (COMMON EXTERNAL V72
`
`NETWORK ADDRESS/LOCALLY UNIQUE PORT)
`
`0006
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 4 of 22
`
`US 7,032,242 Bl
`
`FIG. 4
`
`PAP REQUEST MESSAGE LAYOUT
`78
`80
`(
`(
`CODE
`CHECKSUM
`
`I
`
`UNUSED
`'-84
`
`4 BYTES
`
`FIG. 5
`
`PAP RESPONSE MESSAGE LAYOUT
`90
`92
`(
`r:-~
`CODE
`CHECKSUM
`TOTAL
`PORTS
`'- 96
`
`I
`
`'-9 8
`
`4 BYTES
`
`FIG. 6
`
`PAP INVALIDATE MESSAGE LAYOUT
`104
`106
`('
`_C_
`CODE
`CHECKSUM
`
`74 I
`
`86 I
`
`UNUSED
`
`100
`
`I
`
`76
`
`(
`TYPE
`PORTS
`REQUESTED
`'-82
`
`88
`
`(
`TYPE
`
`I
`
`LOWEST PORT
`
`"-94
`
`102
`
`(
`TYPE
`
`"-108
`
`I
`
`PORT
`
`UNUSED
`
`'- 110
`
`4 BYTES
`
`0007
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 5 of 22
`
`US 7,032,242 Bl
`
`FIG. 4A
`
`PAP SECURITY REQUEST MESSAGE LAYOUT
`
`75
`
`(I
`77
`I CODE
`
`(
`TYPE
`NUMBER OF SECURITY VALUES
`REQUESTED
`'--81
`
`79
`
`(
`CHECKSUM
`
`UNUSED
`
`83
`
`73
`
`I
`
`87
`
`I
`
`(
`TYPE
`TOTAL NUMBER OF SECURITY
`VALUES RETURNED
`
`4 BYTES
`
`FIG. SA
`
`PAP SECURITY RESPONSE MESSAGE LAYOUT
`(i
`91
`89
`(
`CHECKSUM
`
`CODE
`
`(
`3
`9
`
`UNUSED
`
`LOWEST LOCALLY UNIQUE SECURITY VALUE
`
`4BYTES
`
`FIG. 6A
`
`PAP SECURITY INVALIDATE MESSAGE LAYOUT
`
`(
`
`101
`
`TYPE
`
`I
`
`(103
`
`CODE
`
`I
`
`(
`
`105
`
`CHECKSUM
`
`LOCALLY UNIQUE SECURITY VALUE
`
`'--107
`
`4 BYTES
`
`85
`
`I
`---
`\
`
`5
`9
`
`97
`
`99
`
`I
`
`0008
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 6 of 22
`
`US 7,032,242 Bl
`
`FIG. 7
`114 COMBINATION NETWORK ADDRESS
`
`(
`
`112 I
`
`116
`
`(
`
`EXTERNAL NETWORK ADDRESS
`(E.G., EXTERNAL IP ADDRESS)
`
`LOCALLY UNIQUE
`PORT
`
`198.10.20.30
`
`1032
`
`I
`I
`
`I
`
`14
`
`120 ---~~1'4111t---
`
`I
`I
`
`l
`
`I
`
`I
`
`FIG. 8
`
`118
`
`122 __ _,~~~ .... t - - - 124----~~~~ I
`
`INTERNAL
`NETWORK
`ADDRESS
`
`10.0.0.1
`
`10.0.0.3
`
`LOWEST PORT
`
`NUMBER OF PORTS
`
`1027
`
`1058
`
`32
`
`16
`
`PORT -TO-INTERNAL-NETWORK
`ADDRESS TABLE
`
`·r--
`126 +-128
`
`_i __
`
`0009
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 7 of 22
`
`US 7,032,242 Bl
`
`FIG. 9
`
`START
`
`+
`
`130
`
`I
`
`REQUEST ONE OR MORE LOCALLY UNIQUE PORTS ON A
`FIRST NETWORK DEVICE ON A FIRST NETWORK FROM A
`SECOND NETWORK DEVICE ON THE FIRST NETWORK ~
`USING A FIRST PROTOCOL
`1 32
`+
`
`RECEIVE ONE OR MORE LOCALLY UNIQUE PORTS FROM
`THE SECOND NETWORK DEVICE ON THE FIRST NETWORK
`DEVICE USING THE FIRST PROTOCOL.
`
`~
`1 34
`
`+
`REPLACE ONE OR MORE DEFAULT OR EPHEMERAL PORTS h
`IN A PROTOCOL LAYER IN A LAYERED PROTOCOL STACK
`1 36
`WITH ONE OR MORE LOCALLY UNIQUE PORTS
`+
`
`CONSTRUCT A COMBINATION NETWORK ADDRESS USING A
`LOCALLY UNIQUE PORT AND A COMMON EXTERNAL
`NETWORK ADDRESS FOR COMMUNICATING WITH A
`SECOND EXTERNAL NETWORK WITHOUT NETWORK
`ADDRESS TRANSLATION
`
`h
`1 38
`
`~
`
`END
`
`0010
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 8 of 22
`
`US 7,032,242 Bl
`
`FIG. 10
`
`140
`
`I
`
`START
`t
`SEND A REQUEST FOR A SECOND EXTERNAL NETWORK
`WITH A COMBINATION NETWORK ADDRESS FROM A FIRST
`NETWORK DEVICE ON A FIRST NETWORK TO A SECOND ~
`NETWORK DEVICE ON THE FIRST NETWORK
`1 42
`t
`ROUTE THE REQUEST FROM THE SECOND NETWORK
`DEVICE TO THE SECOND EXTERNAL NETWORK
`
`~
`1 44
`
`~
`RECEIVE A RESPONSE ON THE SECOND NETWORK DEVICE
`ON THE FIRST NETWORK FROM THE EXTERNAL SECOND
`NETWORK AT THE COMMON EXTERNAL NETWORK
`ADDRESS FROM THE COMBINATION NETWORK ADDRESS
`~
`ROUTE THE RESPONSE FROM THE SECOND NETWORK
`DEVICE ON THE FIRST NETWORK TO THE FIRST NETWORK
`DEVICE ON THE FIRST NETWORK USING A LOCALLY
`UNIQUE PORT FROM COMBINATION NETWORK ADDRESS
`
`~
`1 46
`
`~
`1
`48
`
`~
`END
`
`0011
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 9 of 22
`
`US 7,032,242 Bl
`
`FIG. 11
`SOURCE PORT TRANSLATION TABLE
`(SPTT)
`
`(154
`
`DEFAULT PORT
`
`PROTOCOL
`
`"-156
`
`I
`
`I
`
`TRANSLATED PORT
`
`TIMESTAMP
`
`'--158
`
`FIG. 12
`IP ADDRESS TRANSLATION TABLE
`(IPATT)
`
`(164
`
`DESTINATION PORT I
`PROTOCOL I
`
`INTERNAL DESTINATION
`IPADDRESS
`
`TIMESTAMP
`
`'-168
`
`150
`
`I
`
`160
`
`I
`
`0012
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 10 of 22
`
`US 7,032,242 Bl
`
`FIG. 13
`
`RECEIVE A DATA PACKET ON A NETWORK INTERFACE
`CARD DEVICE DRIVER IN A LINK LAYER FROM A NETWORK
`LAYER
`
`170 I
`
`172
`
`YES
`
`NO PORT TRANSLATION IS
`PERFORMED
`
`ADD OUTER IP HEADER WITH SOURCE IP ADDRESS SET TO
`NETWORK DEVICE'S INTERNAL IP ADDRESS AND
`DESTINATION SET TO ROUTER'S INTERNAL IPADDRESS
`
`176
`
`TRANSLATE DEFAULT SOURCE PORT IN INNER IP HEADER
`INTO A LOCALLY UNIQUE PORT FOR THE NETWORK
`DEVICE USING A SPTT
`
`178
`
`TRANSMIT PACKET WITH OUTER IP HEADER TO NETWORK
`HARDWARE
`
`180
`
`0013
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 11 of 22
`
`US 7,032,242 Bl
`
`FIG.14
`
`RECEIVE A DATA PACKET ON A NETWORK INTERFACE
`CARD DEVICE DRIVER IN A LINK LAYER FROM NETWORK
`INTERFACE HARDWARE
`
`184 I
`
`186
`
`COPY OUTER SOURCE IP
`YES ADDRESS TO INNER SOURCE IP
`ADDRESS
`
`TRANSLATE SOURCE PORT FROM INNER IP HEADER TO
`LOCALLY UNIQUE PORT USING A SPTT
`
`STRIP OFF OUTER IP HEADER
`
`FORWARD PACKET TO NETWORK LAYER
`
`192
`
`194
`
`0014
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 12 of 22
`
`US 7,032,242 Bl
`
`FIG. 15
`
`IP HEADER FORMAT
`
`200 I
`
`VER
`202
`
`IHL
`204
`
`TOS
`206
`
`IDENTIFICATION
`210
`
`TIME-TO-LIVE
`214
`
`PROTOCOL
`216
`
`TOTAL
`LENGTH
`208
`
`FRAGMENT OFFSET
`212
`
`HEADER
`CHECKSUM
`218
`
`SOURCE ADDRESS
`220
`
`DESTINATION ADDRESS
`222
`
`OPTIONS
`224
`
`0015
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 13 of 22
`
`US 7,032,242 Bl
`
`226
`
`I
`
`FIG. 16
`
`NEXT
`HEADER
`228
`
`AH HEADER FORMAT
`
`PAYLOAD
`RESERVED
`LENGTH
`232
`230
`SECURITY PARAMETER INDEX ("SPI")
`234
`SEQUENCE NUMBER FIELD
`236
`
`AUTHENTICATION DATA
`238
`
`0016
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 14 of 22
`
`US 7,032,242 Bl
`
`FIG.17
`
`ESP HEADER FORMAT
`
`240 I
`
`SECURITY PARAMETERS INDEX ("SPI")
`242
`
`SEQUENCE NUMBER
`244
`
`PAYLOAD DATA (VARIABLE)
`246
`
`PADDING (VARIABLE)
`250
`
`PAD LEN
`252
`AUTHENTICATION DATA
`254
`
`NEXT HEADER
`248
`
`0017
`
`

`

`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 15 of 22
`
`US 7,032,242 Bl
`
`FIG. 18
`
`258
`
`260
`
`256
`
`I
`
`262
`
`264
`266
`268
`
`270
`272
`
`TRANSPORT
`IP1 AH UPPER
`IP1 ESP UPPER
`IP1 AH ESP UPPER
`
`TUNNEL
`
`TIP
`TIP ESP
`
`IP1 UPPER
`
`0018
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 16 of 22
`
`US 7,032,242 Bl
`
`274
`
`I
`
`FIG. 19
`c START
`t
`REQUEST ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES ON A FIRST NETWORK DEVICE ON A FIRST
`NETWORK FROM A SECOND NETWORK DEVICE ON THE I)
`FIRST NETWORK USING A FIRST PROTOCOL
`2 76
`t
`RECEIVE ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES FROM THE SECOND NETWORK DEVICE ON THE ~
`FIRST NETWORK DEVICE USING THE FIRST PROTOCOL
`2 78
`t
`STORE THE ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES ON THE FIRST NETWORK DEVICE FOR USE WITH A
`SECOND SECURE PROTOCOL
`~
`END
`
`~
`2 80
`
`0019
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 17 of 22
`
`US 7,032,242 Bl
`
`FIG. 20
`
`START
`
`+
`
`RECEIVE A REQUEST MESSAGE WITH A FIRST PROTOCOL
`ON A SECOND NETWORK DEVICE FOR ONE OR MORE
`LOCALLY UNIQUE SECURITY VALUES FROM A FIRST ~
`NETWORK DEVICE
`2 84
`~
`
`282
`
`I
`
`~
`2 86
`
`ALLOCATE ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES ON THE SECOND NETWORK DEVICE
`
`+
`
`STORE A NETWORK ADDRESS FOR THE FIRST NETWORK
`DEVICE FROM THE REQUEST MESSAGE IN A TABLE
`ASSOCIATED WITH THE SECOND NETWORK DEVICE,
`WHERE THE TABLE IS USED TO MAINTAIN A MAPPING
`
`BETWEEN THE ONE OR MORE LOCALLY UNIQUE SECURITY h
`
`VALUES AND THE NETWORK ADDRESS FOR THE FIRST
`NETWORK DEVICE FOR DISTRIBUTED NETWORK ADDRESS
`TRANSLATION
`~
`
`2 88
`
`SEND THE ONE OR MORE LOCALLY UNIQUE SECURITY
`
`VALUES TO THE FIRST NETWORK DEVICE IN A RESPONSE h
`
`MESSAGE WITH THE FIRST PROTOCOL
`
`2 90
`
`,,
`
`END
`
`0020
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 18 of 22
`
`US 7,032,242 Bl
`
`llltfooll ... .._- 296 - -........ fooli ... ....__ 298 ---~ ... .:i I
`
`FIG. 21
`
`292
`
`I
`
`I
`
`294--.....
`
`I
`I
`
`1
`
`I
`I
`
`: ...
`
`I
`
`INTERNAL
`NETWORK
`ADDRESS
`
`10.0.0.1
`
`10.0.0.3
`
`LOWEST SPI
`
`NUMBER OF SPis
`
`280
`
`312
`
`32
`
`16
`
`SPI-TO-INTERNAL-NETWORK ADDRESS
`TABLE
`
`0021
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 19 of 22
`
`US 7,032,242 Bl
`
`FIG. 22
`
`( START
`
`t
`
`304 I
`
`REQUEST ONE OR MORE LOCALLY UNIQUE PORTS ON A
`FIRST NETWORK DEVICE FROM A SECOND NETWORK
`DEVICE
`
`~
`306
`
`REQUEST ONE OR MORE LOCALLY UNIQUE SECURITY
`VALUES ON THE FIRST NETWORK DEVICE FROM THE
`SECOND NETWORK DEVICE
`
`0
`308
`
`RECEIVE A SECURITY CERTIFICATE FROM THE SECOND
`NETWORK DEVICE ON THE FIRST NETWORK DEVICE, ~
`WHERE THE SECURITY CERTIFICATE IS USED TO CREATE A
`3
`1 O
`SECURE VIRTUAL CONNECTION
`
`END
`
`0022
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 20 of 22
`
`US 7,032,242 Bl
`
`FIG. 23
`
`START
`
`312
`
`I
`
`SEND ONE OR MORE LOCALLY UNIQUE PORTS TO A FIRST v---.
`NETWORK DEVICE FROM A SECOND NETWORK DEVICE
`314
`
`SEND ONE OR MORE LOCALLY UNIQUE SECURITY VALUES
`FROM THE SECOND NETWORK DEVICE TO THE FIRST ~
`NETWORK DEVICE
`316
`
`SEND A SECURITY CERTIFICATE FROM THE SECOND
`NETWORK DEVICE TO THE FIRST NETWORK DEVICE, ~
`WHERE THE SECURITY CERTIFICATE IS USED TO CREATE A 318
`SECURE VIRTUAL CONNECTION
`
`END
`
`0023
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 21 of 22
`
`US 7,032,242 Bl
`
`FIG. 24
`
`320
`
`I
`
`START
`J
`RECEIVE A FIRST MESSAGE IN A SECOND SECURE
`PROTOCOL ON FIRST NETWORK DEVICE TO ESTABLISH A
`SECURE VIRTUAL CONNECTION TO THE FIRST NETWORK ~
`DEVICE FROM A THIRD NETWORK DEVICE ON A SECOND
`322
`EXTERNAL NETWORK
`
`SELECT A LOCALLY UNIQUE SECURITY VALUE FOR THE
`SECURE CONNECTION FROM A LIST OF LOCALLY UNIQUE
`SECURITY VALUES STORED ON THE FIRST NETWORK
`DEVICE
`
`~
`324
`
`SEND A SECOND MESSAGE IN THE SECOND SECURE
`PROTOCOL FROM THE FIRST NETWORK DEVICE TO
`ESTABLISH A SECURE VIRTUAL CONNECTION TO THE
`FIRST NETWORK DEVICE FROM THE THIRD NETWORK
`DEVICE, WHERE THE SECOND MESSAGE INCLUDES THE
`LOCALLY UNIQUE SECURITY VALUE AND A SECURITY
`CERTIFICATE SENT TO THE FIRST NETWORK DEVICE FROM
`THE SECOND NETWORK DEVICE
`
`~
`326
`
`END
`
`0024
`
`

`

`U.S. Patent
`
`Apr. 18, 2006
`
`Sheet 22 of 22
`
`US 7,032,242 Bl
`
`FIG. 25
`
`START)
`
`+
`
`SEND A REQUEST FROM A FIRST NETWORK DEVICE ON A
`FIRST NETWORK TO A SECOND NETWORK DEVICE ON A
`FIRST NETWORK FOR A THIRD NETWORK DEVICE ON AN
`EXTERNAL SECOND NETWORK, WHERE THE REQUEST
`INCLUDES SECURITY INFORMATION
`
`,
`
`328 I
`
`~
`330
`
`ROUTE THE REQUEST FROM THE SECOND NETWORK
`DEVICE TO THE THIRD NETWORK DEVICE
`
`~
`332
`
`RECEIVE A RESPONSE MESSAGE ON THE SECOND
`NETWORK DEVICE FROM THE THIRD NETWORK DEVICE
`WHERE THE RESPONSE INCLUDES SECURITY
`INFORMATION FROM THE REQUEST
`
`~
`334
`
`,,
`
`ROUTE THE RESPONSE MESSAGE FROM THE SECOND
`NETWORK DEVICE TO THE FIRST NETWORK DEVICE USING f-"\
`LOCALLY UNIQUE PORTS USED FOR DISTRIBUTED
`336
`NETWORK ADDRESS TRANSLATION
`
`END
`
`0025
`
`

`

`US 7,032,242 Bl
`
`1
`METHOD AND SYSTEM FOR DISTRIBUTED
`NETWORK ADDRESS TRANSLATION WITH
`NETWORK SECURITY FEATURES
`
`CROSS REFERENCES TO RELATED
`APPLICATIONS
`
`This application is a Continuation-In-Part of U.S. appli(cid:173)
`cation Ser. No. 09/035,600 filed on Mar. 5, 1998 now U.S.
`Pat. No. 6,353,614.
`
`FIELD OF INVENTION
`
`This invention relates to computer networks. More spe(cid:173)
`cifically, it relates to a method and system for distributed
`network address translation with network security features.
`
`BACKGROUND OF THE INVENTION
`
`The Internet Protocol ("IP") is an addressing protocol
`designed to facilitate the routing of traffic within a network 20
`or between networks. The Internet Protocol is used on many
`computer networks including the Internet, intranets and
`other networks. Current versions oflnternet Protocol such as
`Internet Protocol version-4 ("IPv4") are becoming obsolete
`because of limited address space. With a 32-bit address- 25
`field, it is possible to assign 232 different addresses, which is
`4,294,967,296, or greater than 4 billion globally unique
`addresses.
`However, with the explosive growth of the Internet and
`intranets, Internet Protocol addresses using a 32-bit address(cid:173)
`field may soon be exhausted. Internet Protocol version-6
`("IPv6") proposes the use of a 128-bit address-field for IP
`addresses. However, a large number of legacy networks
`including a large number of Internet subnets will still be
`using older versions for Internet Protocol with a 32-bit
`address space for many years to come.
`Network Address Translation ("NAT') has been proposed
`to extend the lifetime of Internet Protocol version 4 and
`earlier versions of Internet Protocol by allowing subnets to
`exist behind a single or small number of globally unique 40
`Internet Protocol addresses (see e.g., "The IP Network
`Address Translator", by P. Srisuresh and K. Egevang, Inter(cid:173)
`net Engineering Task Force ("IETF"), Internet Draft <draft(cid:173)
`rfced-info-srisuresh-05.txt>, February 1998). A single glo(cid:173)
`bal Internet Protocol address is used for communication with 45
`external networks such as the Internet. Internally, a sub(cid:173)
`network ("subnet") uses local addressing. Local addressing
`may be either any addressing scheme that is different from
`Internet Protocol addressing, or a non-unique usage of
`Internet Protocol addresses. In either case, local addresses
`on a subnet are not used on the external, global Internet.
`When a device or node using local addressing desires to
`communicate with the external world, its local address is
`translated to a common external Internet Protocol address
`used for communication with an external network by a 55
`network address translation device. That is, network address
`translation allows one or more global Internet Protocol
`addresses to be shared among a larger number of local
`addresses.
`There are several problems associated with using network 60
`address translation to extend the life of the Internet Protocol.
`Network address translation interferes with the end-to-end
`routing principle of the Internet that recommends that pack(cid:173)
`ets flow end-to-end between network devices with changing
`the contents of any packets along a transmission route (see
`e.g. "Routing in the Internet," by C. Huitema, Prentice Hall,
`1995, ISBN 0-131-321-927).
`
`2
`Current versions of network address translation replace a
`local network address in a data packet header with an
`external global network address on outbound traffic, and
`replace an external network address in a data packet header
`with a local network address on inbound traffic. This type of
`address translation is computationally expensive, causes
`security problems by preventing certain types of encryption
`from being used, or breaks a number of existing applications
`in a network that cannot provide network address translation
`10 (e.g., File Transfer Protocol ("FTP")).
`Current versions of network address translation may not
`gracefully scale beyond a small subnet containing a few
`dozen nodes or devices because of the computational and
`other resources required. Network address translation poten-
`15 tially requires support for many different internal network
`protocols be specifically programmed into a translation
`mechanism for