Internet DRAFT - draft-liu-vcpot
draft-liu-vcpot
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]
