| Internet-Draft | vcpot | March 2024 |
| Liu | Expires 4 September 2024 | [Page] |
This document describes an ordered Proof of Transit mechanism.¶
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 (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.¶
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.¶
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.¶
The terminology and definition of key concepts in this document, such as path, node and link was defined in [RFC9473]. Others:¶
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.¶
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. 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.¶
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.¶
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 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.¶
In our approach, there is one network controller (Alice) and many network elements. We use controller and elements from now on.¶
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].¶
Controller chooses maximum number of element t in the vector. Here t is the maximum number of elements N on the path.¶
Controller chooses a random positive integer secret a.¶
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.¶
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).¶
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.¶
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).¶
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.¶
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:¶
[*] 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.¶
Controller sends the following data to each network element: ciphersuite (curve, hash function), public parameter pp, polynomial phi(x).¶
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.¶
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.¶
Network element i attaches p_i to the packet header, or send them out-of-band.¶
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:¶
[*] Network element i attaches p_i and (x_i, y_i) to the packet header, or send them out-of-band.¶
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.¶
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 Parameters pp | Commitment C | Transit Proof p_i | Has Implementation |
|---|---|---|---|---|
| BLS12-381 | (N+1)*48 | 48 | 48 | Y |
| BLS48 | (N+1)*36 | 36 | 36 | N |
| BW19-P286 | (N+1)*36 | 36 | 36 | N |
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.¶
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.¶
A working Proof-of-Concept demo implementation is published here:¶
https://github.com/liuchunchi/vcpot-demo¶
Runnable in MacOS environment.¶
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].¶
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.¶
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.¶
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.¶
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.¶
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:¶
If PQ-safe is a must, lattice-based or hash-based VC is also available. 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)).¶
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.¶
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 can be used to construct POT mechanisms, such as simple Merkle Tree, aggregate signatures.¶
This document has no IANA actions.¶