[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04

Network Working Group                                     Sheng Jiang
Internet Draft                            Huawei Technologies Co., Ltd
Intended status: Informational                            May 11, 2009
Expires: November 08, 2009

              Hierarchical Host Identity Tag Architecture

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on October 5, 2009.

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the
   document authors. All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents in effect on the date of
   publication of this document (http://trustee.ietf.org/license-info).
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.

Jiang                 Expires November 08, 2009               [Page 1]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009


   This document analyzes the problems and limitation of the current
   flat-structured Host Identity Tag architecture. The document
   specifies a hierarchical HIT architecture which is compatible with
   the flat-structured HIT architecture. This architecture and the
   process of HIT generation ensure the global uniqueness of HITs. This
   architecture also enables the multiple Host Identity Protocol
   management domains, solves the deployment problem of current flat-
   structured HIT architecture. It also enhances the scalability and
   resolution efficiency of the mapping system from HIT to IP or FQDN.

Table of Contents

   1. Introduction................................................3
   2. Analysis of the Current Flat-structured HIT Architecture......3
   3. Hierarchical HIT Architecture................................5
      3.1. Compatible flat-structured HITs.........................6
      3.2. HITs on nodes..........................................6
   4. Generating a hierarchical HIT................................7
   5. Requirements for modification on HIP.........................7
   6. Acknowledgements............................................8
   7. Security Considerations......................................8
   8. IANA Considerations.........................................8
   9. References..................................................8
      9.1. Normative References....................................8
      9.2. Informative References..................................8
   Author's Addresses.............................................9

Jiang                 Expires November 08, 2009               [Page 2]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

1. Introduction

   This document analyzes the problems and limitation of the current
   flat-structured Host Identity Tag (HIT, [RFC4423]) architecture in
   the Host Identity Protocol (HIP, [RFC5201]). The document specifies a
   hierarchical HIT architecture, which splits a HIT into two parts: a
   HIP management domain tag and a host tag. The proposed hierarchical
   HIT architecture is also compatible with the flat-structured HIT
   architecture. The format of HIT and the detail process of HIT
   generation are defined. This architecture and the process of HIT
   generation ensure the global uniqueness of HITs. This architecture
   also enables the multiple HIP management domains, solves the
   deployment problem of current flat-structured HIT architecture. The
   aggregation of HITs in this architecture also enhances the
   scalability and resolution efficiency of the mapping system from HIT
   to IP or FQDN.

2. Analysis of the Current Flat-structured HIT Architecture

   The HIT concept was defined in [RFC5201]: "... the Host Identity Tag
   (HIT), becomes the operational representation. It is 128 bits long
   and is used in the HIP payloads and to index the corresponding state
   in the end hosts."

   In order to be able to represent hosts, the uniqueness of HITs is
   required in global scope. "In the HIP packets, the HITs identify the
   sender and recipient of a packet. Consequently, a HIT should be
   unique in the whole IP universe as long as it is being used."

   Although mathematically "the probability of HIT collision between two
   hosts is very low" [RFC5201], there is no mechanism to ensure that a
   HIT is global unique.

   The current defined HIT is generated according to the ORCHID
   generation method described in [RFC4843]: "several possible
   methods ... to preserve a low enough probability of collisions".
   However, it cannot guarantee the global uniqueness of HITs.
   Furthermore, while the number of end devices continuously grows in
   the future, the possibility of HIT collision will increase rapidly. A
   technical mechanism is needed to ensure the global uniqueness of HITs,
   particularly with the consideration that collisions may happen. When
   such collision happens, more than one hosts will have the same HIT.
   Then, the HIT cannot uniquely identify a certain host.

Jiang                 Expires November 08, 2009               [Page 3]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

   Although there is a rough solution for how to distinguish duplicated
   HITs, it is far from a feasible or best solution.

   [RFC4423] states "In the extremely rare case of a single HIT mapping
   to more than one Host Identity, the Host Identifiers (public keys)
   will make the final difference." It means the mapping system between
   HIP and IP must store or at least be aware of the Host Identifiers of
   all hosts. Given the facts that the Host Identifiers are quite large
   and may be in various lengths, the storage and management burden of
   the mapping system could be quite high. If there was a mechanism to
   ensure the global uniqueness of HITs, then, the mapping system would
   not have to be aware the Host Identifiers.

   Furthermore, within the flat-structured HIT architecture, the
   robustness of resolution efficiency in the supporting mapping system
   is in a big question mark: a mapping server has to hold or at least
   to be able to access a large database that contains information on
   all HITs in the global scope. There more than a billion hosts now on
   the Internet and a global deployment of HIP would require an equal
   amount of HITs. In the future, there could be even billions of
   machines or even higher. The storage burden, maintenance consumption
   and synchronization updating are problems that are very difficult to
   solve. For each single lookup operation, one may search through most
   of the database. It is unfeasible for both computing power and time

   One more disadvantage that the flat-structured HIT architecture is
   the difficulties for management. There is nothing common between HITs
   that were assigned by the same authority or that their represented
   hosts have the same properties. Hence, it is difficult to categorize
   HITs. Although this provides privacy to the end-hosts, the Access
   Control Lists (ACLs) would have to have a full list of HITs
   accessible to permitted services. Contrarily, the hierarchical HITs
   are more aggregatable. It makes HITs manageable. HITs can be grouped
   according to its belonging authority or domain. Each network operator
   just needs to manage and maintain HITs and their mapping information
   in a relatively small range.

   According to the above analysis, it is natural to turn the flat HIT
   architecture into hierarchy. It can effectively reduce the global
   uniqueness requirement into much smaller scope uniqueness requirement.
   In another word, if a hierarchical HIT with a global unique
   management domain tag is locally unique, it is guaranteed to be
   global unique. It can improve the resolution processing and enhance
   the scalability and resolution efficiency. Furthermore, it can
   optimize the management of both the host identity and the mapping
   database. Each management domain is responsible only for a part of

Jiang                 Expires November 08, 2009               [Page 4]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

   the global HIT architecture. However, it is useful that the new
   hierarchical HIT architecture is compatible with the flat HIT
   architecture for privacy purposes and other usage scenarios.

3. Hierarchical HIT Architecture

   In this document, we introduce a two-level hierarchically structured
   HIT architecture. HIT is "128 bits long value and is used in the HIP
   payloads and to index the corresponding state in the end hosts."
   [RFC5201] "In the HIP packets, the HITs identify the sender and
   recipient of a packet." [RFC4423] HITs refer to nodes or virtual
   nodes. All nodes are required to have at least one HIT. A single node
   may also have multiple HITs. Applications on a same node may bind to
   different HITs.

   In the hierarchical HIT namespace, a 128-bit HIT consists of two
   parts: 32-bit HIP management domain tag and 96-bit host tag. It can
   represent maximum 2^32 management domains and 2^96 hosts within each
   management domain.

   |          32 bits              |              96 bits            |
   |  HIP management domain tag    |             host tag            |

   For the secure consideration, we assign more bits to the host tag,
   which is a hash result, leaving less but enough bits for HIP
   management domain tag. The more the number of bits the host tag is,
   the more secure it is against brute-force attacks. In the worst case,
   if the hash algorithm cannot be inverted, the expected number of
   iterations required for a brute force attack is O(2^96) in order to
   find a host identity that matches with a given host tag. It should be
   noted that this draft does not take into account the ORCHID prefix
   defined in [RFC4843]. It is because the /28 bit orchid prefix with
   32-bit hierarchical HIP management domain tag would leave only 68
   bits or even less for host tag part, which reduce the security
   properties too low and increase collusion possibility too high.

   The HIP management domain, as its literal, is a logic region in which
   the HIs of all nodes are assigned by the same authority. Within a
   same HIP management domain, all the nodes should have the same HIP
   management domain tag or the same leftmost certain bits. Furthermore,
   the authority may be organized internally hierarchically.

   The HIP management domain tag should be assigned by a global
   management organization with the principle that every HIP management
   domain tag must be globally unique.

Jiang                 Expires November 08, 2009               [Page 5]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

   Consequentially, the HIP management domain tags may be organized
   hierarchically. For example, a big organization may obtain a block of
   HIP management tags with an assigned 24-bit prefix. It then can
   assign 32-bit HIP management domain tags to its sub-organizations.
   All these sub-organizations have the same leftmost 24-bit.

   The host tags remain the original meaning of HIT -"a hashed encoding
   of the Host Identity". For each HIP management domain, it is
   mandatory to maintain the uniqueness of all host tags. It is
   guaranteed by the process of generating a HIT, see Section 5.

   For resolution purposes, HITs are aggregatable with management domain
   tags of arbitrary bit-length, similar to IPv4 addresses under
   Classless Inter-Domain Routing [RFC4632].

3.1. Compatible flat-structured HITs

   Obviously, not all hosts are willing to use hierarchical HITs in all
   scenarios for various reasons, such as privacy. Therefore, it is
   useful that the hierarchical HIT architecture keep compatible with
   the flat HIT architecture.

   The flat HITs can be defined as a specific sub-set of the
   hierarchical HITs architecture. With the same reserved Flat HIT Tag
   (2 or 3 bits) at the beginning and the number of bits that can be
   chosen arbitrarily reduce 2 or 3 bits out of 128, flat HITs can be
   used as defined in [RFC4423].

   |                           128 bits                              |
   |FHIT Tag|            Flat host identity tag                      |

3.2. HITs on nodes

   HIP-enabled nodes may have considerable or little knowledge of the
   internal structure of hierarchical HITs, depending on the role the
   node plays (for instance, host versus mapping server). At a minimum,
   a node may consider pre-generated HITs have no internal structure:

   |                           128 bits                              |
   |                       host identity tag                         |

Jiang                 Expires November 08, 2009               [Page 6]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

   Only sophisticated hosts may additionally be aware of the type of
   their HITS and use the hierarchical structure of HITs to simplify the
   resolution procedure.

4. Generating a hierarchical HIT

   The process of generating a new hierarchical HIT takes three input
   values: a 32-bit HIP management domain tag, a 2-bit collusion count,
   the host identity (the public key of an asymmetric key pair). A
   hierarchical HIT should be generated as follows:

      1. Set the 2-bit collision count to zero.

      2. Concatenate from left to right the HIP management domain tag,
         the collusion count, and the host identity. Execute the SHA-1
         algorithm on the concatenation. Take the 94 leftmost bits of
         the SHA-1 hash value.

      3. Concatenate from left to right the 32-bit HIP management
         domain tag, the 2-bit collusion count and 94-bit hash output
         to form a 128-bit HIT.

      4. Perform duplicate detection within the HIP management domain
         scope. If a HIT collision is detected, increment the collision
         count by one and go back to step 2. However, after four
         collisions, stop and report the error. (Note: the duplicate
         detection mechanism is not discussed in this document. It may
         be broadcast or central registration.)

   The design that includes the HIP management domain tag in the hash
   input is mainly against the re-computation attack: create a database
   of HITs and matching public keys. With the design, an attacker must
   create a separate database for each HIP management domain.

   The design reduces the number of bit of hash output from 96 to 94. It
   does reduce the safety. However, O(2^94) iterations is large enough
   to prevent brute-force attacks.

   For security reason, the abovementioned SHA-1 hash algorithm may be
   replaced by any safer algorithm.

5. Requirements for modification on HIP

   The usage of hierarchical HITs requires either a new version of HIP
   protocol or a new critical flag in the header of HIP control packets.
   The latter is considered easier and more fulfill.

Jiang                 Expires November 08, 2009               [Page 7]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

6. Acknowledgements

   Useful comments were made by Miika Komu from HIIT, and other members
   of the IRTF HIPRG research group.

7. Security Considerations

   The most important security property of HIT is that it is self-
   certifying (i.e., given a HIT, it is computationally hard to find a
   Host Identity key that matches the HIT). Although this document
   limits the hash output to be 94-bit long, it does not affect the self
   certifying security property.

8. IANA Considerations

   This document defines a new namespace: HIP management domain tag. It
   is a 32-bit long value, which represents a globally unique HIP
   management domain. IANA may found an authority institute to manage
   the global assignment of HIP management domain tag.

9. References

9.1. Normative References

   [RFC4423] R. Moskowitz, P. Nikander, "Host Identity Protocol (HIP)
             Architecture", RFC4423, May 2006.

   [RFC5201] R. Moskowitz, et al., "Host Identity Protocol", RFC 5201,
             Oct 2007.

9.2. Informative References

   [RFC4632] V. Fuller, T. Li, "Classless Inter-Domain Routing (CIDR):
             The Internet Address Assignment and Aggregation Plan",
             RFC4632, August 2006.

   [RFC4843] P. Nikander, et al., "An IPv6 Prefix for Overlay Routable
             Cryptographic Hash Identifiers (ORCHID)", RFC 4843, April

Jiang                 Expires November 08, 2009               [Page 8]

Internet-Draft   draft-jiang-hiprg-hhit-arch-02.txt           May 2009

Author's Addresses

   Sheng Jiang
   Huawei Technologies Co., Ltd
   KuiKe Building, No.9 Xinxi Rd.,
   Shang-Di Information Industry Base, Hai-Dian District, Beijing 100085
   P.R. China
   Phone: 86-10-82836774
   Email: shengjiang@huawei.com

Jiang                 Expires November 08, 2009               [Page 9]

Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/