XMSS: Extended Hash-Based Signatures
draft-irtf-cfrg-xmss-hash-based-signatures-09

Internet Architecture Board (IAB)                              D. Thaler
Request for Comments: 5902                                      L. Zhang
Category: Informational                                      G. Lebovitz
ISSN: 2070-1721                                                July 2010

            IAB Thoughts on IPv6 Network Address Translation

Abstract

   There has been much recent discussion on the topic of whether the
   IETF should develop standards for IPv6 Network Address Translators
   (NATs).  This document articulates the architectural issues raised by
   IPv6 NATs, the pros and cons of having IPv6 NATs, and provides the
   IAB's thoughts on the current open issues and the solution space.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Architecture Board (IAB)
   and represents information that the IAB has deemed valuable to
   provide for permanent record.  Documents approved for publication by
   the IAB are not a candidate for any level of Internet Standard; see
   Section 2 of RFC 5741.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   http://www.rfc-editor.org/info/rfc5902.

Copyright Notice

   Copyright (c) 2010 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
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.

Thaler, et al.                Informational                     [Page 1]
RFC 5902                 IPv6 NAT Considerations               July 2010

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  2
   2.  What is the problem? . . . . . . . . . . . . . . . . . . . . .  3
     2.1.  Avoiding Renumbering . . . . . . . . . . . . . . . . . . .  3
     2.2.  Site Multihoming . . . . . . . . . . . . . . . . . . . . .  4
     2.3.  Homogenous Edge Network Configurations . . . . . . . . . .  4
     2.4.  Network Obfuscation  . . . . . . . . . . . . . . . . . . .  5
       2.4.1.  Hiding Hosts . . . . . . . . . . . . . . . . . . . . .  5
       2.4.2.  Topology Hiding  . . . . . . . . . . . . . . . . . . .  8
       2.4.3.  Summary Regarding NAT as a Tool for Network
               Obfuscation  . . . . . . . . . . . . . . . . . . . . .  8
     2.5.  Simple Security  . . . . . . . . . . . . . . . . . . . . .  9
     2.6.  Discussion . . . . . . . . . . . . . . . . . . . . . . . .  9
   3.  Architectural Considerations of IPv6 NAT . . . . . . . . . . .  9
   4.  Solution Space . . . . . . . . . . . . . . . . . . . . . . . . 11
     4.1.  Discussion . . . . . . . . . . . . . . . . . . . . . . . . 12
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . . 13
   6.  IAB Members at the Time of Approval  . . . . . . . . . . . . . 13
   7.  Informative References . . . . . . . . . . . . . . . . . . . . 14

1.  Introduction

   In the past, the IAB has published a number of documents relating to
   Internet transparency and the end-to-end principle, and other IETF
   documents have also touched on these issues as well.  These documents
   articulate the general principles on which the Internet architecture
   is based, as well as the core values that the Internet community
   seeks to protect going forward.  Most recently, RFC 4924 [RFC4924]
   reaffirms these principles and provides a review of the various
   documents in this area.

   Facing imminent IPv4 address space exhaustion, recently there have
   been increased efforts in IPv6 deployment.  However, since late 2008
   there have also been increased discussions about whether the IETF
   should standardize network address translation within IPv6.  People
   who are against standardizing IPv6 NAT argue that there is no
   fundamental need for IPv6 NAT, and that as IPv6 continues to roll
   out, the Internet should converge towards reinstallation of the end-
   to-end reachability that has been a key factor in the Internet's
   success.  On the other hand, people who are for IPv6 NAT believe that
   NAT vendors would provide IPv6 NAT implementations anyway as NAT can
   be a solution to a number of problems, and that the IETF should avoid
   repeating the same mistake as with IPv4 NAT, where the lack of
   protocol standards led to different IPv4 NAT implementations, making
   NAT traversal difficult.

Thaler, et al.                Informational                     [Page 2]
RFC 5902                 IPv6 NAT Considerations               July 2010

   An earlier effort, [RFC4864], provides a discussion of the real or
   perceived benefits of NAT and suggests alternatives for most of them,
   with the intent of showing that NAT is not required to get the
   desired benefits.  However, it also identifies several gaps remaining
   to be filled.

   This document provides the IAB's current thoughts on this debate.  We
   believe that the issue at hand must be viewed from an overall
   architectural standpoint in order to fully assess the pros and cons
   of IPv6 NAT on the global Internet and its future development.

2.  What is the problem?

   The discussions on the desire for IPv6 NAT can be summarized as
   follows.  Network address translation is viewed as a solution to
   achieve a number of desired properties for individual networks:
   avoiding renumbering, facilitating multihoming, making configurations
   homogenous, hiding internal network details, and providing simple
   security.

2.1.  Avoiding Renumbering

   As discussed in [RFC4864], Section 2.5, the ability to change service
   providers with minimal operational difficulty is an important
   requirement in many networks.  However, renumbering is still quite
   painful today, as discussed in [RFC5887].  Currently it requires
   reconfiguring devices that deal with IP addresses or prefixes,
   including DNS servers, DHCP servers, firewalls, IPsec policies, and
   potentially many other systems such as intrusion detection systems,
   inventory management systems, patch management systems, etc.

   In practice today, renumbering does not seem to be a significant
   problem in consumer networks, such as home networks, where addresses
   or prefixes are typically obtained through DHCP and are rarely
   manually configured in any component.  However, in managed networks,
   renumbering can be a serious problem.

   We also note that many, if not most, large enterprise networks avoid
   the renumbering problem by using provider-independent (PI) IP address
   blocks.  The use of PI addresses is inherent in today's Internet
   operations.  However, in smaller managed networks that cannot get
   provider-independent IP address blocks, renumbering remains a serious
   issue.  Regional Internet Registries (RIRs) constantly receive
   requests for PI address blocks; one main reason that they hesitate in
   assigning PI address blocks to all users is the concern about the PI
   addresses' impact on the routing system scalability.

Thaler, et al.                Informational                     [Page 3]
RFC 5902                 IPv6 NAT Considerations               July 2010

2.2.  Site Multihoming

   Another important requirement in many networks is site multihoming.
   A multihomed site essentially requires that its IP prefixes be
   present in the global routing table to achieve the desired
   reliability in its Internet connectivity as well as load balancing.
   In today's practice, multihomed sites with PI addresses announce
   their PI prefixes to the global routing system; multihomed sites with
   provider-allocated (PA) addresses also announce the PA prefix they
   obtained from one service provider to the global routing system
   through another service provider, effectively disabling provider-
   based prefix aggregation.  This practice makes the global routing
   table scale linearly with the number of multihomed user networks.

   This issue was identified in [RFC4864], Section 6.4.  Unfortunately,
   no solution except NAT has been deployed today that can insulate the
   global routing system from the growing number of multihomed sites,
   where a multihomed site simply assigns multiple IPv4 addresses (one
   from each of its service providers) to its exit router, which is an
   IPv4 NAT box.  Using address translation to facilitate multihoming
   support has one unique advantage: there is no impact on the routing
   system scalability, as the NAT box simply takes one address from each
   service provider, and the multihomed site does not inject its own
   routes into the system.  Intuitively, it also seems straightforward
   to roll the same solution into multihoming support in the IPv6
   deployment.  However, one should keep in mind that this approach
   brings all the drawbacks of putting a site behind a NAT box,
   including the loss of reachability to the servers behind the NAT box.

   It is also important to point out that a multihomed site announcing
   its own prefix(es) achieves two important benefits that NAT-based
   multihoming support does not provide.  First, end-to-end
   communications can be preserved in face of connectivity failures of
   individual service providers, as long as the site remains connected
   through at least one operational service provider.  Second,
   announcing one&

        case xmssmt_shake256_w16_h60_d12:
          bytestring64 rand_n64;

        default:
          void;     /* error condition */
      };

      /* Type for reduced XMSS signatures */

      union xmss_reduced (xmss_algorithm_type type) {
        case xmssmt_sha2-256_w16_h20_d2:
        case xmssmt_sha2-256_w16_h40_d4:
        case xmssmt_sha2-256_w16_h60_d6:
        case xmssmt_shake128_w16_h20_d2:
        case xmssmt_shake128_w16_h40_d4:
        case xmssmt_shake128_w16_h60_d6:
          bytestring32 xmss_reduced_n32_t77[77];

        case xmssmt_sha2-256_w16_h20_d4:
        case xmssmt_sha2-256_w16_h40_d8:
        case xmssmt_sha2-256_w16_h60_d12:
        case xmssmt_shake128_w16_h20_d4:
        case xmssmt_shake128_w16_h40_d8:
        case xmssmt_shake128_w16_h60_d12:
          bytestring32 xmss_reduced_n32_t72[72];

        case xmssmt_sha2-256_w16_h40_d2:
        case xmssmt_sha2-256_w16_h60_d3:
        case xmssmt_shake128_w16_h40_d2:
        case xmssmt_shake128_w16_h60_d3:
          bytestring32 xmss_reduced_n32_t87[87];

        case xmssmt_sha2-512_w16_h20_d2:
        case xmssmt_sha2-512_w16_h40_d4:
        case xmssmt_sha2-512_w16_h60_d6:
        case xmssmt_shake256_w16_h20_d2:
        case xmssmt_shake256_w16_h40_d4:
        case xmssmt_shake256_w16_h60_d6:
          bytestring64 xmss_reduced_n32_t141[141];

        case xmssmt_sha2-512_w16_h20_d4:
        case xmssmt_sha2-512_w16_h40_d8:
        case xmssmt_sha2-512_w16_h60_d12:
        case xmssmt_shake256_w16_h20_d4:
        case xmssmt_shake256_w16_h40_d8:
        case xmssmt_shake256_w16_h60_d12:
          bytestring64 xmss_reduced_n32_t136[136];

Huelsing, et al.         Expires October 1, 2017               [Page 62]
Internet-Draft    XMSS: Extended Hash-Based Signatures        March 2017

        case xmssmt_sha2-512_w16_h40_d2:
        case xmssmt_sha2-512_w16_h60_d3:
        case xmssmt_shake256_w16_h40_d2:
        case xmssmt_shake256_w16_h60_d3:
          bytestring64 xmss_reduced_n32_t151[151];

        default:
          void;     /* error condition */
      };

      /* xmss_reduced_array depends on d */

      union xmss_reduced_array (xmss_algorithm_type type) {
        case xmssmt_sha2-256_w16_h20_d2:
        case xmssmt_sha2-512_w16_h20_d2:
        case xmssmt_sha2-256_w16_h40_d2:
        case xmssmt_sha2-512_w16_h40_d2:
        case xmssmt_shake128_w16_h20_d2:
        case xmssmt_shake256_w16_h20_d2:
        case xmssmt_shake128_w16_h40_d2:
        case xmssmt_shake256_w16_h40_d2:
          xmss_reduced xmss_red_arr_d2[2];

        case xmssmt_sha2-256_w16_h60_d3:
        case xmssmt_sha2-512_w16_h60_d3:
        case xmssmt_shake128_w16_h60_d3:
        case xmssmt_shake256_w16_h60_d3:
          xmss_reduced xmss_red_arr_d3[3];

        case xmssmt_sha2-256_w16_h20_d4:
        case xmssmt_sha2-512_w16_h20_d4:
        case xmssmt_sha2-256_w16_h40_d4:
        case xmssmt_sha2-512_w16_h40_d4:
        case xmssmt_shake128_w16_h20_d4:
        case xmssmt_shake256_w16_h20_d4:
        case xmssmt_shake128_w16_h40_d4:
        case xmssmt_shake256_w16_h40_d4:
          xmss_reduced xmss_red_arr_d4[4];

        case xmssmt_sha2-256_w16_h60_d6:
        case xmssmt_sha2-512_w16_h60_d6:
        case xmssmt_shake128_w16_h60_d6:
        case xmssmt_shake256_w16_h60_d6:
          xmss_reduced xmss_red_arr_d6[6];

        case xmssmt_sha2-256_w16_h40_d8:
        case xmssmt_sha2-512_w16_h40_d8:
        case xmssmt_shake128_w16_h40_d8:

Huelsing, et al.         Expires October 1, 2017               [Page 63]
Internet-Draft    XMSS: Extended Hash-Based Signatures        March 2017

        case xmssmt_shake256_w16_h40_d8:
          xmss_reduced xmss_red_arr_d8[8];

        case xmssmt_sha2-256_w16_h60_d12:
        case xmssmt_sha2-512_w16_h60_d12:
        case xmssmt_shake128_w16_h60_d12:
        case xmssmt_shake256_w16_h60_d12:
          xmss_reduced xmss_red_arr_d12[12];

        default:
          void;     /* error condition */
      };

      /* XMSS^MT signature structure */

      struct xmssmt_signature {
        /* WOTS+ key pair index */
        idx_sig_xmssmt idx_sig;
        /* Random string for randomized hashing */
        random_string_xmssmt randomness;
        /* Array of d reduced XMSS signatures */
        xmss_reduced_array;
      };

   XMSS^MT public keys are defined using XDR syntax as follows:

      /* Types for bitmask seed */

      union seed switch (xmssmt_algorithm_type type) {
        case xmssmt_sha2-256_w16_h20_d2:
        case xmssmt_sha2-256_w16_h40_d4:
        case xmssmt_sha2-256_w16_h60_d6:
        case xmssmt_sha2-256_w16_h20_d4:
        case xmssmt_sha2-256_w16_h40_d8:
        case xmssmt_sha2-256_w16_h60_d12:
        case xmssmt_sha2-256_w16_h40_d2:
        case xmssmt_sha2-256_w16_h60_d3:
        case xmssmt_shake128_w16_h20_d2:
        case xmssmt_shake128_w16_h40_d4:
        case xmssmt_shake128_w16_h60_d6:
        case xmssmt_shake128_w16_h20_d4:
        case xmssmt_shake128_w16_h40_d8:
        case xmssmt_shake128_w16_h60_d12:
        case xmssmt_shake128_w16_h40_d2:
        case xmssmt_shake128_w16_h60_d3:
          bytestring32 seed_n32;

Huelsing, et al.         Expires October 1, 2017               [Page 64]
Internet-Draft    XMSS: Extended Hash-Based Signatures        March 2017

        case xmssmt_sha2-512_w16_h20_d2:
        case xmssmt_sha2-512_w16_h40_d4:
        case xmssmt_sha2-512_w16_h60_d6:
        case xmssmt_sha2-512_w16_h20_d4:
        case xmssmt_sha2-512_w16_h40_d8:
        case xmssmt_sha2-512_w16_h60_d12:
        case xmssmt_sha2-512_w16_h40_d2:
        case xmssmt_sha2-512_w16_h60_d3:
        case xmssmt_shake256_w16_h20_d2:
        case xmssmt_shake256_w16_h40_d4:
        case xmssmt_shake256_w16_h60_d6:
        case xmssmt_shake256_w16_h20_d4:
        case xmssmt_shake256_w16_h40_d8:
        case xmssmt_shake256_w16_h60_d12:
        case xmssmt_shake256_w16_h40_d2:
        case xmssmt_shake256_w16_h60_d3:
          bytestring64 seed_n64;

        default:
          void;     /* error condition */
      };

      /* Types for XMSS^MT root node */

      union xmssmt_root switch (xmssmt_algorithm_type type) {
        case xmssmt_sha2-256_w16_h20_d2:
        case xmssmt_sha2-256_w16_h20_d4:
        case xmssmt_sha2-256_w16_h40_d2:
        case xmssmt_sha2-256_w16_h40_d4:
        case xmssmt_sha2-256_w16_h40_d8:
        case xmssmt_sha2-256_w16_h60_d3:
        case xmssmt_sha2-256_w16_h60_d6:
        case xmssmt_sha2-256_w16_h60_d12:
        case xmssmt_shake128_w16_h20_d2:
        case xmssmt_shake128_w16_h20_d4:
        case xmssmt_shake128_w16_h40_d2:
        case xmssmt_shake128_w16_h40_d4:
        case xmssmt_shake128_w16_h40_d8:
        case xmssmt_shake128_w16_h60_d3:
        case xmssmt_shake128_w16_h60_d6:
        case xmssmt_shake128_w16_h60_d12:
          bytestring32 root_n32;

        case xmssmt_sha2-512_w16_h20_d2:
        case xmssmt_sha2-512_w16_h20_d4:
        case xmssmt_sha2-512_w16_h40_d2:
        case xmssmt_sha2-512_w16_h40_d4:
        case xmssmt_sha2-512_w16_h40_d8:

Huelsing, et al.         Expires October 1, 2017               [Page 65]
Internet-Draft    XMSS: Extended Hash-Based Signatures        March 2017

        case xmssmt_sha2-512_w16_h60_d3:
        case xmssmt_sha2-512_w16_h60_d6:
        case xmssmt_sha2-512_w16_h60_d12:
        case xmssmt_shake256_w16_h20_d2:
        case xmssmt_shake256_w16_h20_d4:
        case xmssmt_shake256_w16_h40_d2:
        case xmssmt_shake256_w16_h40_d4:
        case xmssmt_shake256_w16_h40_d8:
        case xmssmt_shake256_w16_h60_d3:
        case xmssmt_shake256_w16_h60_d6:
        case xmssmt_shake256_w16_h60_d12:
          bytestring64 root_n64;

        default:
          void;     /* error condition */
      };

      /* XMSS^MT public key structure */

      struct xmssmt_public_key {
        xmssmt_root root;  /* Root node */
        seed SEED;  /* Seed for bitmasks */
      };

Authors' Addresses

   Andreas Huelsing
   TU Eindhoven
   P.O. Box 513
   Eindhoven  5600 MB
   NL

   Email: ietf@huelsing.net

   Denis Butin
   TU Darmstadt
   Hochschulstrasse 10
   Darmstadt  64289
   DE

   Email: dbutin@cdc.informatik.tu-darmstadt.de

Huelsing, et al.         Expires October 1, 2017               [Page 66]
Internet-Draft    XMSS: Extended Hash-Based Signatures        March 2017

   Stefan-Lukas Gazdag
   genua GmbH
   Domagkstrasse 7
   Kirchheim bei Muenchen  85551
   DE

   Email: ietf@gazdag.de

   Aziz Mohaisen
   SUNY Buffalo
   323 Davis Hall
   Buffalo, NY  14260
   US

   Phone: +1 716 645-1592
   Email: mohaisen@buffalo.edu

Huelsing, et al.         Expires October 1, 2017               [Page 67]