Vector Commitment-based Proof of Transit
draft-liu-vcpot-00

Network Working Group                                             C. Liu
Internet-Draft                                                    Huawei
Intended status: Standards Track                            3 March 2024
Expires: 4 September 2024

                Vector Commitment-based Proof of Transit
                           draft-liu-vcpot-00

Abstract

   This document describes an ordered Proof of Transit mechanism.

Status of This Memo

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

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on 4 September 2024.

Copyright Notice

   Copyright (c) 2024 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 (https://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.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Liu                     Expires 4 September 2024                [Page 1]
Internet-Draft                    vcpot                       March 2024

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Background  . . . . . . . . . . . . . . . . . . . . . . . . .   3
   4.  Basic Idea  . . . . . . . . . . . . . . . . . . . . . . . . .   3
   5.  Solution  . . . . . . . . . . . . . . . . . . . . . . . . . .   4
     5.1.  Algorithm . . . . . . . . . . . . . . . . . . . . . . . .   4
     5.2.  Approach  . . . . . . . . . . . . . . . . . . . . . . . .   5
       5.2.1.  Setup . . . . . . . . . . . . . . . . . . . . . . . .   5
       5.2.2.  Commit to a Path  . . . . . . . . . . . . . . . . . .   5
       5.2.3.  Configure . . . . . . . . . . . . . . . . . . . . . .   6
       5.2.4.  Create Transit Proof  . . . . . . . . . . . . . . . .   6
       5.2.5.  Verify Transit Proof  . . . . . . . . . . . . . . . .   7
   6.  Sizing the Data for VCPOT . . . . . . . . . . . . . . . . . .   7
   7.  Running Implementation  . . . . . . . . . . . . . . . . . . .   8
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .   8
     8.1.  Biding and Hiding . . . . . . . . . . . . . . . . . . . .   8
     8.2.  Unforgeability of Transit Proof . . . . . . . . . . . . .   8
     8.3.  Need Trusted Setup (A Centralized Controller) . . . . . .   9
     8.4.  No-mods, No-sweat . . . . . . . . . . . . . . . . . . . .   9
     8.5.  No Post-Quantum Resistance  . . . . . . . . . . . . . . .   9
     8.6.  Other Possible Constructions  . . . . . . . . . . . . . .   9
   9.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  10
   10. Informative References  . . . . . . . . . . . . . . . . . . .  10
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  11

1.  Introduction

   Proof of Transit (POT) is a secure log or evidence that proves
   traffic transited certain elements of a network path, in a specified
   order.  The "elements" could be either virtual network functions or
   physical network devices, per the definition of [RFC9473].

   POT mechanism can be used to prove the actual forwarding of a packet
   follows a predetermined path, in order to satisfy certain compliance
   or performance requirements.  As a result, POT is important for
   several technologies that explicitly appoints traffic path, such as
   Service Function Chaining (SFC), Segment Routing (SR), Traffic
   Engineering (TE), etc-- it can help prove a packet's forwarding
   compliance to a path, or at least, confirm its deviation.  Other use
   cases are discussed in [I-D.liu-path-validation-problem-statement].

   POT is a critical building block for routing security assurance, but
   a secure yet efficient POT mechanism is still under standardization.
   [I-D.ietf-sfc-proof-of-transit] presented a Shamir Secret Sharing-
   based POT solution, but has not become a proposed standard until now.

Liu                     Expires 4 September 2024                [Page 2]
Internet-Draft                    vcpot                       March 2024

   This document describes a secure, efficient ordered Proof of Transit
   mechanism using a cryptographic primitive called Vector Commitment.
   We select efficient cryptographic constructions of Vector Commitment,
   which is KZG polynomial commitment, for high computation efficiency
   and succinct proof size.  We also define the efficiency benchmark and
   security definitions of Proof of Transit mechanisms.  Since we
   believe order-compliance is a must, we omit "ordered" from now.

2.  Terminology

   The terminology and definition of key concepts in this document, such
   as path, node and link was defined in [RFC9473].  Others:

   *  POT: Proof of Transit

   *  VC: Vector Commitment

   *  KZG: Kate, Zaverucha and Goldberg Polynomial Commitment

   *  SFC: Service Function Chaining

   *  SR: Segment Routing

3.  Background

   The absence of a secure POT mechanism (along with lack of control to
   Internet devices) causes a gap between routing integrity and
   forwarding integrity.  This means the routing information could be
   propagated correctly (with efforts like BGPSEC), but it is each
   router who makes the actual forwarding decision, which can be
   negatively affected by faulty configurations or malicious attacks
   [RIvsFI].  POT mechanisms, if designed secure and efficient enough,
   can be a trustworthy mark or evidence reflecting the actual path a
   packet has taken in the forwarding plane.

4.  Basic Idea

   The proposed method uses Vector Commitment (VC).  A regular
   cryptographic Commitment scheme allows Alice to commit to a single
   secret value and reveal it later; while a Vector Commitment scheme
   allows Alice to commit to a vector of secrets, and reveal it one-by-
   one or all at once.  This allows our solutions to do the following:

   For a network controller, she can orchestrate a routing path, where
   each value represents a network element's identity (or attributes),
   and the vector represents the whole path.  She can compute a
   ciphertext-like commitment C that reflects the full vector
   information, in this way committing to this path, and this path only.

Liu                     Expires 4 September 2024                [Page 3]
Internet-Draft                    vcpot                       March 2024

   Also, no adversary can interpret any information about the values
   just by observing the commitment C.  These are the binding and hiding
   properties provided by the original cryptographic VC primitive.
   Detailed security analysis are provided in the Security
   Considerations.  Also the commitment C is always constant size
   regardless of the length of the path or information committed.

   For a network element, he can compute an opening proof for himself,
   functions as a proof-of-transit, which proves who he is, the path he
   is on, his index on this path, all at the same time.  The opening
   proof p_i is also always constant size and is aggregateable with
   other opening proofs p_J.

   For any public verifier, he can verify the opening proof p_i against
   commitment C.  Only when the three-tuple information of opening proof
   p_i aligns with controller's three-tuple information of commitment C,
   will the transit proof p_i pass verification against commitment C.
   The verifier does not need any pre-shared secrets or auxiliary data,
   meaning the verification is stateless.  The verification time is also
   constant time.

   Vector Commitment has many low level constructions-- obviously Merkle
   Tree is one of many possible constructions.  But the advantage of our
   proposed solution is the efficiency of the low-level construction we
   use-- KZG Polynomial Commitment.  By comparison, when verifying an
   opening proof p_i, we only need constant O(1) size of p_i and
   commitment C as compared with O(logN) size of auxiliary data in
   Merkle Trees.  The opening proof p_i can also be directly verified
   against commitment C, requiring O(1) constant verification time as
   compared with O(logN) computation in Merkle Trees.  The number N is
   the total number of committed elements (and its information) in a
   vector.  Such efficiency advantage is critical when assessing the
   usability to apply advanced crypto to the routing area.

5.  Solution

5.1.  Algorithm

   We avoid cryptographic deep-dive.  Consider VC as a blackbox with the
   following functions:

   *  Setup: On input a security parameter k, generate a set of public
      parameters pp for following functions.

   *  Commit: On input parameter pp, a vector V=(v_1, v_2, ..., v_N),
      output a commitment value C to the vector V.

Liu                     Expires 4 September 2024                [Page 4]
Internet-Draft                    vcpot                       March 2024

   *  Open: On input parameter pp, element i's identity information and
      auxiliary information, output an opening proof p_i.

   *  Verify: On input parameter pp, commitment C, opening proof p_i and
      i's identity information, output either pass or fail.

   This abstraction is given in this SoK
   (https://www.di.ens.fr/~nitulesc/files/vc-sok.pdf) The function
   Commit is used by network controllers to orchestrate a network path.
   The function Open is used by a network element to compute a transit
   proof.  The function Verify is used by a public verifier to verify a
   transit proof.

5.2.  Approach

   In our approach, there is one network controller (Alice) and many
   network elements.  We use controller and elements from now on.

5.2.1.  Setup

   1.  Controller chooses a pairing-friendly curve to use.  She uses a
       unique ciphersuite identifier to represent the selection.
       Reference ciphersuite format of pairing-friendly curve is defined
       in Section 7.1 [I-D.irtf-cfrg-pairing-friendly-curves].

   2.  Controller chooses maximum number of element t in the vector.
       Here t is the maximum number of elements N on the path.

   3.  Controller chooses a random positive integer secret a.

   4.  Controller computes a t+1 tuple public parameter pp=(g, g^a,
       g^a+1, ..., g^a^t), where g is the group generator of the
       selected curve, part of public parameters of the curve.

5.2.2.  Commit to a Path

   The Commit function introduced above is a high level abstraction.  In
   KZG's actual construction, in the Commit step, there is another step
   of conversion from the vector V to an interpolated polynomial phi(x).
   The commitment, opening and verification all requires this polynomial
   phi(x).

   1.  Controller decides a routing path V=(v_1, v_2, ..., v_N), where
       v_i is the unique identifier (or the profile containing list of
       attributes) of the network element i.

Liu                     Expires 4 September 2024                [Page 5]
Internet-Draft                    vcpot                       March 2024

   2.  Controller transform the vector V into N number of two-
       dimensional points (x_i, y_i), where x_i equals integer 1,2,3...
       and y_i equals the hash of v_i, y_i=hash(v_i).

   3.  Controller uses Lagrange interpolation to compute a polynomial
       phi(x) using above N two-dimensional points (x_i, y_i).  The
       polynomial phi(x) is represented by the coefficients of it.

   4.  Given polynomial phi(x) and public parameters pp, controller
       computes a commitment C using the Commit() from KZG mechanism.

   Since the polynomial phi(x) is needed when computing any opening
   proof, if x_i is 1,2,3... then all participating network elements
   would have access to any (i, v_i) pair, hence trust among the network
   elements are required.  To achieve transit proof unforgeability, the
   security-enhanced step 2 is:

   1.  [*] Controller randomly generates a secret s_i and share with the
       element i through a private secure channel. x_i=s_i,
       y_i=hash(v_i||s_i).

   and the rest remains same.

5.2.3.  Configure

   1.  Controller sends the following data to each network element:
       ciphersuite (curve, hash function), public parameter pp,
       polynomial phi(x).

   2.  Controller broadcasts public parameter pp and commitment C for
       any public verifier (could be an external verifier or also any
       participating network element).

   For enhanced security option: 1. [*] Controller sends the following
   data to each network element i: ciphersuite (curve, hash function),
   public parameter pp, polynomial phi(x), _and secret s_i_.

5.2.4.  Create Transit Proof

   1.  Upon receiving a request to compute a transit proof, the network
       element i compute an opening proof p_i using Open(), with input
       of his (x_i, y_i), polynomial phi(x) and public parameter pp.

   2.  Network element i attaches p_i to the packet header, or send them
       out-of-band.

Liu                     Expires 4 September 2024                [Page 6]
Internet-Draft                    vcpot                       March 2024

   Because the verification of p_i requires also (x_i, y_i), for normal
   procedures, (x_i, y_i) is public information and does not require
   sending.  For enhanced security option, since x_i and y_i is secret,
   do the following:

   1.  [*] Network element i attaches p_i and (x_i, y_i) to the packet
       header, or send them out-of-band.

5.2.5.  Verify Transit Proof

   1.  The verifier takes public parameter pp, commitment C, index x_i,
       element's identity y_i, opening proof p_i, uses Verify() to
       accept or reject a transit proof.  If the p_i is sent out-of-
       band, then the verifier is the external party.  If p_i is
       attached to the packet payload or header, the following network
       element can also be verifiers.

6.  Sizing the Data for VCPOT

   The major data in our proposed solution is the Commitment C and
   transit proof p_i, which represents path-level information and
   individual-level information.  We compare the size of Commitment C
   and transit proof p_i.  C and p_i is a group element of G1, where e:
   G1 x G1 -> GT is a symmetric (type 1) bilinear pairing.  As a result,
   it is relevant to different pairing-friendly curves we use:

   +===========+===============+============+=========+================+
   | Curve     | Public        | Commitment | Transit | Has            |
   |           | Parameters    | C          | Proof   | Implementation |
   |           | pp            |            | p_i     |                |
   +===========+===============+============+=========+================+
   | BLS12-381 | (N+1)*48      | 48         | 48      | Y              |
   +-----------+---------------+------------+---------+----------------+
   | BLS48     | (N+1)*36      | 36         | 36      | N              |
   +-----------+---------------+------------+---------+----------------+
   | BW19-P286 | (N+1)*36      | 36         | 36      | N              |
   +-----------+---------------+------------+---------+----------------+

                        Table 1: Data sizes in Bytes

   KZG polynomial commitment utilizes pairing-friendly curves.  Common
   implementations [GOKZG][RUSTKZG] uses BLS12-381 elliptic curves
   defined in Section 4.2.1 of [I-D.irtf-cfrg-pairing-friendly-curves].
   With a field modulus q of 381 bits in length, we receive 126-bits of
   security (close enough to 128 bits).  To achieve same bits of
   security, BN-curves requires 462 bits and increases overhead so we
   don't use them.

Liu                     Expires 4 September 2024                [Page 7]
Internet-Draft                    vcpot                       March 2024

   The reason why size of field modulus is important is because it is
   the exact size of a group element in G1, therefore both the size of a
   commitment and opening proof to be attached to the packet header and
   transmitted.  Although BLS12-381 is the most popular curve, there are
   also curves with a smaller 286-bit G1-- BW19-P286 and BLS48 [PFC].
   They decrease the packet overhead from 48B to 36B.

   A complete YANG model is TBD.

7.  Running Implementation

   A working Proof-of-Concept demo implementation is published here:

   https://github.com/liuchunchi/vcpot-demo

   Runnable in MacOS environment.

8.  Security Considerations

8.1.  Biding and Hiding

   The hiding and binding property is offered by the original KZG
   Polynomial Commitment cryptographic scheme, not by our design.
   Informally:

   The commitment C is cryptographically hiding, meaning without x_i and
   polynomial phi(x), simply by observing commitment C, no adversary can
   interpret y_i hence compute an opening proof p_i.  The commitment C
   is cryptographically binding, meaning computing an opening proof
   using any (x_i, y'_i) different than (x_i, y_i) cannot pass
   verification against commitment C.

   For complete cryptographic details, please refer to the original
   paper [KZG].

8.2.  Unforgeability of Transit Proof

   A transit proof p_i should be unforgeable.

   With the cryptographic hiding property, for our normal option, no
   malicious adversary outside of participating network elements can
   forge a transit proof.  But this requires a security assumption of
   trusting the network elements being benign.

Liu                     Expires 4 September 2024                [Page 8]
Internet-Draft                    vcpot                       March 2024

   The enhanced security option eliminates this trust assumption.  With
   (x_i, y_i) being secret plus the hiding property, no adversary can
   guess (x_i, y_i) and forge a p_i before element i's revelation.  This
   means even a participating element j is malicious, it still cannot
   forge the transit proof of element i.

8.3.  Need Trusted Setup (A Centralized Controller)

   The Setup step requires a centralized trusted authority to generate
   and distribute the public parameters.  This is not very problematic
   since a network controller that orchestrates a path can (and also
   should) serve as a setup center.

8.4.  No-mods, No-sweat

   The POT approach described in this document did not make
   modifications to the KZG polynomial commitment itself-- we are merely
   using it.  Therefore, the approach does not introduce additional
   potential security vulnerabilities compared to the original scheme.

8.5.  No Post-Quantum Resistance

   The approach described in this document uses bilinear pairing, which
   assumes (Elliptic Curve) Discrete Log Problem (DL) is hard.  This
   also means this approach is not quantum-resistant.  We have two
   arguments for that:

   1.  If PQ-safe is a must, lattice-based or hash-based VC is also
       available (https://www.di.ens.fr/~nitulesc/files/vc-sok.pdf).
       For instance, Fast Reed-Solomon Interactive Oracle Proof (FRI) is
       another alternative vector commitment construction to KZG.  FRI
       commitment is constructed using merkle trees and is hence quantum
       resistant, but the proof size is much bigger, slower to verify,
       dependent to the number of elements in the vector (both
       O(log\^2N)).

   2.  Considering general elliptic curve cryptography is still in wide
       use, it is fair to say forging a transit proof is less severe
       than forging an ECDSA signature to Bitcoin.

8.6.  Other Possible Constructions

   Vector Commitment can be seen as a special type of Cryptographic
   Accumulators, which can prove the membership of one or many elements
   in a set, by computing an inclusion proof.  What is special about VC
   is it can also prove the order/position of the element inside the
   set.  In use cases where the order is not important, or cryptographic
   capability is limited, other simplified Cryptographic Accumulators

Liu                     Expires 4 September 2024                [Page 9]
Internet-Draft                    vcpot                       March 2024

   can be used to construct POT mechanisms, such as simple Merkle Tree,
   aggregate signatures.

9.  IANA Considerations

   This document has no IANA actions.

10.  Informative References

   [RFC9473]  Enghardt, R. and C. Krähenbühl, "A Vocabulary of Path
              Properties", RFC 9473, DOI 10.17487/RFC9473, September
              2023, <https://www.rfc-editor.org/rfc/rfc9473>.

   [I-D.ietf-sfc-proof-of-transit]
              Brockners, F., Bhandari, S., Mizrahi, T., Dara, S., and S.
              Youell, "Proof of Transit", Work in Progress, Internet-
              Draft, draft-ietf-sfc-proof-of-transit-08, 1 November
              2020, <https://datatracker.ietf.org/doc/html/draft-ietf-
              sfc-proof-of-transit-08>.

   [I-D.liu-path-validation-problem-statement]
              Liu, P. C., Wu, Q., and L. Xia, "Path Validation Problem
              Statement, History, Gap Analysis and Use Cases", Work in
              Progress, Internet-Draft, draft-liu-path-validation-
              problem-statement-00, 23 October 2023,
              <https://datatracker.ietf.org/doc/html/draft-liu-path-
              validation-problem-statement-00>.

   [I-D.irtf-cfrg-pairing-friendly-curves]
              Sakemi, Y., Kobayashi, T., Saito, T., and R. S. Wahby,
              "Pairing-Friendly Curves", Work in Progress, Internet-
              Draft, draft-irtf-cfrg-pairing-friendly-curves-11, 6
              November 2022, <https://datatracker.ietf.org/doc/html/
              draft-irtf-cfrg-pairing-friendly-curves-11>.

   [RIvsFI]   "Opinion":" Is secured routing a market failure?",
              December 2022, <https://blog.apnic.net/2022/12/16/opinion-
              is-secured-routing-a-market-failure/>.

   [KZG]      "Constant-Size Commitments to Polynomials and Their
              Applications", n.d., <https://www.iacr.org/archive/
              asiacrypt2010/6477178/6477178.pdf>.

   [GOKZG]    "Go implementation of KZG proofs", n.d.,
              <https://github.com/protolambda/go-kzg>.

   [RUSTKZG]  "RUST implementation of KZG proofs", n.d.,
              <https://github.com/ralexstokes/kzg>.

Liu                     Expires 4 September 2024               [Page 10]
Internet-Draft                    vcpot                       March 2024

   [PFC]      "PAIRING-FRIENDLY CURVES, Aurore Guillevic", n.d.,
              <https://members.loria.fr/AGuillevic/pairing-friendly-
              curves/>.

Author's Address

   Chunchi Liu
   Huawei
   China
   Email: liuchunchi@huawei.com

Liu                     Expires 4 September 2024               [Page 11]