Proof of Transit
draftbrocknersproofoftransit02
The information below is for an old version of the document.
Document  Type 
This is an older version of an InternetDraft whose latest revision state is "Replaced".



Authors  Frank Brockners , Shwetha Bhandari , Sashank Dara , Carlos Pignataro , John Leddy , Stephen Youell , David Mozes , Tal Mizrahi  
Last updated  20161031  
Replaced by  draftietfsfcproofoftransit  
RFC stream  (None)  
Formats  
Stream  Stream state  (No stream defined)  
Consensus boilerplate  Unknown  
RFC Editor Note  (None)  
IESG  IESG state  ID Exists  
Telechat date  (None)  
Responsible AD  (None)  
Send notices to  (None) 
draftbrocknersproofoftransit02
Network Working Group F. Brockners InternetDraft S. Bhandari Intended status: Experimental S. Dara Expires: May 3, 2017 C. Pignataro Cisco J. Leddy Comcast S. Youell JMPC D. Mozes Mellanox Technologies Ltd. T. Mizrahi Marvell October 30, 2016 Proof of Transit draftbrocknersproofoftransit02 Abstract Several technologies such as Traffic Engineering (TE), Service Function Chaining (SFC), and policy based routing are used to steer traffic through a specific, userdefined path. This document defines mechanisms to securely prove that traffic transited said defined path. These mechanisms allow to securely verify whether, within a given path, all packets traversed all the nodes that they are supposed to visit. Status of This Memo This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79. InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current Internet Drafts is at http://datatracker.ietf.org/drafts/current/. InternetDrafts 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 InternetDrafts as reference material or to cite them other than as "work in progress." This InternetDraft will expire on May 3, 2017. Brockners, et al. Expires May 3, 2017 [Page 1] InternetDraft Proof of Transit October 2016 Copyright Notice Copyright (c) 2016 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/licenseinfo) 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 Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Proof of Transit . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . 5 3.2. Solution Approach . . . . . . . . . . . . . . . . . . . . 6 3.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2.2. In Transit . . . . . . . . . . . . . . . . . . . . . 7 3.2.3. Verification . . . . . . . . . . . . . . . . . . . . 7 3.3. Illustrative Example . . . . . . . . . . . . . . . . . . 7 3.3.1. Basic Version . . . . . . . . . . . . . . . . . . . . 7 3.3.1.1. Secret Shares . . . . . . . . . . . . . . . . . . 8 3.3.1.2. Lagrange Polynomials . . . . . . . . . . . . . . 8 3.3.1.3. LPC Computation . . . . . . . . . . . . . . . . . 8 3.3.1.4. Reconstruction . . . . . . . . . . . . . . . . . 9 3.3.1.5. Verification . . . . . . . . . . . . . . . . . . 9 3.3.2. Enhanced Version . . . . . . . . . . . . . . . . . . 9 3.3.2.1. Random Polynomial . . . . . . . . . . . . . . . . 9 3.3.2.2. Reconstruction . . . . . . . . . . . . . . . . . 10 3.3.2.3. Verification . . . . . . . . . . . . . . . . . . 10 3.3.3. Final Version . . . . . . . . . . . . . . . . . . . . 11 3.4. Operational Aspects . . . . . . . . . . . . . . . . . . . 11 3.5. Alternative Approach . . . . . . . . . . . . . . . . . . 12 3.5.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . 12 3.5.2. Pros . . . . . . . . . . . . . . . . . . . . . . . . 12 3.5.3. Cons . . . . . . . . . . . . . . . . . . . . . . . . 12 4. Sizing the Data for Proof of Transit . . . . . . . . . . . . 12 5. Node Configuration . . . . . . . . . . . . . . . . . . . . . 13 5.1. Procedure . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2. YANG Model . . . . . . . . . . . . . . . . . . . . . . . 14 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 7. Manageability Considerations . . . . . . . . . . . . . . . . 17 Brockners, et al. Expires May 3, 2017 [Page 2] InternetDraft Proof of Transit October 2016 8. Security Considerations . . . . . . . . . . . . . . . . . . . 17 8.1. Proof of Transit . . . . . . . . . . . . . . . . . . . . 18 8.2. Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . 18 8.3. AntiReplay . . . . . . . . . . . . . . . . . . . . . . . 19 8.4. AntiPreplay . . . . . . . . . . . . . . . . . . . . . . 19 8.5. AntiTampering . . . . . . . . . . . . . . . . . . . . . 20 8.6. Recycling . . . . . . . . . . . . . . . . . . . . . . . . 20 8.7. Redundant Nodes and Failover . . . . . . . . . . . . . . 20 8.8. Controller Operation . . . . . . . . . . . . . . . . . . 20 8.9. Verification Scope . . . . . . . . . . . . . . . . . . . 21 8.9.1. Node Ordering . . . . . . . . . . . . . . . . . . . . 21 8.9.2. Stealth Nodes . . . . . . . . . . . . . . . . . . . . 21 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 21 10.1. Normative References . . . . . . . . . . . . . . . . . . 21 10.2. Informative References . . . . . . . . . . . . . . . . . 22 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 1. Introduction Several deployments use Traffic Engineering, policy routing, Segment Routing (SR), and Service Function Chaining (SFC) [RFC7665] to steer packets through a specific set of nodes. In certain cases, regulatory obligations or a compliance policy require operators to prove that all packets that are supposed to follow a specific path are indeed being forwarded across and exact set of predetermined nodes. If a packet flow is supposed to go through a series of service functions or network nodes, it has to be proven that indeed all packets of the flow followed the path or service chain or collection of nodes specified by the policy. In case some packets of a flow weren't appropriately processed, a verification device should determine the policy violation and take corresponding actions corresponding to the policy (e.g., drop or redirect the packet, send an alert etc.) In today's deployments, the proof that a packet traversed a particular path or service chain is typically delivered in an indirect way: Service appliances and network forwarding are in different trust domains. Physical handoffpoints are defined between these trust domains (i.e. physical interfaces). Or in other terms, in the "network forwarding domain" things are wired up in a way that traffic is delivered to the ingress interface of a service appliance and received back from an egress interface of a service appliance. This "wiring" is verified and then trusted upon. The evolution to Network Function Virtualization (NFV) and modern service chaining concepts (using technologies such as Locator/ID Separation Protocol (LISP), Network Service Header (NSH), Segment Routing (SR), etc.) blurs the line between the different trust domains, because the Brockners, et al. Expires May 3, 2017 [Page 3] InternetDraft Proof of Transit October 2016 handoffpoints are no longer clearly defined physical interfaces, but are virtual interfaces. As a consequence, different trust layers should not to be mixed in the same device. For an NFV scenario a different type of proof is required. Offering a proof that a packet indeed traversed a specific set of service functions or nodes allows operators to evolve from the above described indirect methods of proving that packets visit a predetermined set of nodes. The solution approach presented in this document is based on a small portion of operational data added to every packet. This "insitu" operational data is also referred to as "proof of transit data", or POT data. The POT data is updated at every required node and is used to verify whether a packet traversed all required nodes. A particular set of nodes "to be verified" is either described by a set of secret keys, or a set of shares of a single secret. Nodes on the path retrieve their individual keys or shares of a key (using for e.g., Shamir's Secret Sharing scheme) from a central controller. The complete key set is only known to the controller and a verifier node, which is typically the ultimate node on a path that performs verification. Each node in the path uses its secret or share of the secret to update the POT data of the packets as the packets pass through the node. When the verifier receives a packet, it uses its key(s) along with data found in the packet to validate whether the packet traversed the path correctly. 2. Conventions Abbreviations used in this document: HMAC: Hash based Message Authentication Code. For example, HMACSHA256 generates 256 bits of MAC LISP: Locator/ID Separation Protocol LPC: Lagrange Polynomial Constants MTU: Maximum Transmit Unit NFV: Network Function Virtualization NSH: Network Service Header POT: Proof of Transit POTprofile: Proof of Transit Profile that has the necessary data for nodes to participate in proof of transit Brockners, et al. Expires May 3, 2017 [Page 4] InternetDraft Proof of Transit October 2016 RND: Random Bits generated per packet. Packet fields that donot change during the traversal are given as input to HMAC256 algorithm. A minimum of 32 bits (left most) need to be used from the output if RND is used to verify the packet integrity. This is a standard recommendation by NIST. SEQ_NO: Sequence number initialized to a predefined constant. This is used in concatenation with RND bits to mitigate different attacks discussed later. SFC: Service Function Chain SR: Segment Routing 3. Proof of Transit This section discusses methods and algorithms to provide for a "proof of transit" for packets traversing a specific path. A path which is to be verified consists of a set of nodes. Transit of the data packets through those nodes is to be proven. Besides the nodes, the setup also includes a Controller that creates secrets and secrets shares and configures the nodes for POT operations. The methods how traffic is identified and associated to a specific path is outside the scope of this document. Identification could be done using a filter (e.g., 5tuple classifier), or an identifier which is already present in the packet (e.g., path or service identifier, NSH Service Path Identifier (SPI), flowlabel, etc.) The solution approach is detailed in two steps. Initially the concept of the approach is explained. This concept is then further refined to make it operationally feasible. 3.1. Basic Idea The method relies on adding POT data to all packets that traverse a path. The added POT data allows a verifying node (egress node) to check whether a packet traversed the identified set of nodes on a path correctly or not. Security mechanisms are natively built into the generation of the POT data to protect against misuse (i.e. configuration mistakes, malicious administrators playing tricks with routing, capturing, spoofing and replaying packets). The mechanism for POT leverages "Shamir's Secret Sharing" scheme [SSS]. Shamir's secret sharing base idea: A polynomial (represented by its coefficients) is chosen as a secret by the controller. A polynomial represents a curve. A set of welldefined points on the curve are Brockners, et al. Expires May 3, 2017 [Page 5] InternetDraft Proof of Transit October 2016 needed to construct the polynomial. Each point of the polynomial is called "share" of the secret. A single secret is associated with a particular set of nodes, which typically represent the path, to be verified. Shares of the single secret (i.e., points on the curve) are securely distributed from a Controller to the network nodes. Nodes use their respective share to update a cumulative value in the POT data of each packet. Only a verifying node has access to the complete secret. The verifying node validates the correctness of the received POT data by reconstructing the curve. The polynomial cannot be constructed if any of the points are missed or tampered. Per Shamir's Secret Sharing Scheme, any lesser points means one or more nodes are missed. Details of the precise configuration needed for achieving security are discussed further below. While applicable in theory, a vanilla approach based on Shamir's secret sharing could be easily attacked. If the same polynomial is reused for every packet for a path a passive attacker could reuse the value. As a consequence, one could consider creating a different polynomial per packet. Such an approach would be operationally complex. It would be complex to configure and recycle so many curves and their respective points for each node. Rather than using a single polynomial, two polynomials are used for the solution approach: A secret polynomial which is kept constant, and a per packet polynomial which is public. Operations are performed on the sum of those two polynomials  creating a third polynomial which is secret and per packet. 3.2. Solution Approach Solution approach: The overall algorithm uses two polynomials: POLY1 and POLY2. POLY1 is secret and constant. Each node gets a point on POLY1 at setuptime and keeps it secret. POLY2 is public, random and per packet. Each node generates a point on POLY2 each time a packet crosses it. Each node then calculates (point on POLY1 + point on POLY2) to get a (point on POLY3) and passes it to verifier by adding it to each packet. The verifier constructs POLY3 from the points given by all the nodes and cross checks whether POLY3 = POLY1 + POLY2. Only the verifier knows POLY1. The solution leverages finite field arithmetic in a field of size "prime number". Detailed algorithms are discussed next. A simple example is discussed in Section 3.3. Brockners, et al. Expires May 3, 2017 [Page 6] InternetDraft Proof of Transit October 2016 3.2.1. Setup A controller generates a first polynomial (POLY1) of degree k and k+1 points on the polynomial. The constant coefficient of POLY1 is considered the SECRET. The nonconstant coefficients are used to generate the Lagrange Polynomial Constants (LPC). Each of the k nodes (including verifier) are assigned a point on the polynomial i.e., shares of the SECRET. The verifier is configured with the SECRET. The Controller also generates coefficients (except the constant coefficient, called "RND", which is changed on a per packet basis) of a second polynomial POLY2 of the same degree. Each node is configured with the LPC of POLY2. Note that POLY2 is public. 3.2.2. In Transit For each packet, the ingress node generates a random number (RND). It is considered as the constant coefficient for POLY2. A cumulative value (CML) is initialized to 0. Both RND, CML are carried as within the packet POT data. As the packet visits each node, the RND is retrieved from the packet and the respective share of POLY2 is calculated. Each node calculates (Share(POLY1) + Share(POLY2)) and CML is updated with this sum. This step is performed by each node until the packet completes the path. The verifier also performs the step with its respective share. 3.2.3. Verification The verifier cross checks whether CML = SECRET + RND. If this matches then the packet traversed the specified set of nodes in the path. This is due to the additive homomorphic property of Shamir's Secret Sharing scheme. 3.3. Illustrative Example This section shows a simple example to illustrate step by step the approach described above. 3.3.1. Basic Version Assumption: It is to be verified whether packets passed through 3 nodes. A polynomial of degree 2 is chosen for verification. Choices: Prime = 53. POLY1(x) = (3x^2 + 3x + 10) mod 53. The secret to be reconstructed is the constant coefficient of POLY1, i.e., SECRET=10. It is important to note that all operations are done over a finite field (i.e., modulo prime). Brockners, et al. Expires May 3, 2017 [Page 7] InternetDraft Proof of Transit October 2016 3.3.1.1. Secret Shares The shares of the secret are the points on POLY1 chosen for the 3 nodes. For example, let x0=2, x1=4, x2=5. POLY1(2) = 28 => (x0, y0) = (2, 28) POLY1(4) = 17 => (x1, y1) = (4, 17) POLY1(5) = 47 => (x2, y2) = (5, 47) The three points above are the points on the curve which are considered the shares of the secret. They are assigned to three nodes respectively and are kept secret. 3.3.1.2. Lagrange Polynomials Lagrange basis polynomials (or Lagrange polynomials) are used for polynomial interpolation. For a given set of points on the curve Lagrange polynomials (as defined below) are used to reconstruct the curve and thus reconstruct the complete secret. l0(x) = (((xx1) / (x0x1)) * ((xx2)/x0x2))) mod 53 = (((x4) / (24)) * ((x5)/25))) mod 53 = (10/3  3x/2 + (1/6)x^2) mod 53 l1(x) = (((xx0) / (x1x0)) * ((xx2)/x1x2))) mod 53 = (5 + 7x/2  (1/2)x^2) mod 53 l2(x) = (((xx0) / (x2x0)) * ((xx1)/x2x1))) mod 53 = (8/3  2 + (1/3)x^2) mod 53 3.3.1.3. LPC Computation Since x0=2, x1=4, x2=5 are chosen points. Given that computations are done over a finite arithmetic field ("modulo a prime number"), the Lagrange basis polynomial constants are computed modulo 53. The Lagrange Polynomial Constant (LPC) would be 10/3 , 5 , 8/3. LPC(x0) = (10/3) mod 53 = 21 LPC(x1) = (5) mod 53 = 48 LPC(x2) = (8/3) mod 53 = 38 For a general way to compute the modular multiplicative inverse, see e.g., the Euclidean algorithm. Brockners, et al. Expires May 3, 2017 [Page 8] InternetDraft Proof of Transit October 2016 3.3.1.4. Reconstruction Reconstruction of the polynomial is welldefined as POLY1(x) = l0(x) * y0 + l1(x) * y1 + l2(x) * y2 Subsequently, the SECRET, which is the constant coefficient of POLY1(x) can be computed as below SECRET = (y0*LPC(l0)+y1*LPC(l1)+y2*LPC(l2)) mod 53 The secret can be easily reconstructed using the yvalues and the LPC: SECRET = (y0*LPC(l0) + y1*LPC(l1) + y2*LPC(l2)) mod 53 = mod (28 * 21 + 17 * 48 + 47 * 38) mod 53 = 3190 mod 53 = 10 One observes that the secret reconstruction can easily be performed cumulatively hop by hop. CML represents the cumulative value. It is the POT data in the packet that is updated at each hop with the node's respective (yi*LPC(i)), where i is their respective value. 3.3.1.5. Verification Upon completion of the path, the resulting CML is retrieved by the verifier from the packet POT data. Recall that verifier is preconfigured with the original SECRET. It is cross checked with the CML by the verifier. Subsequent actions based on the verification failing or succeeding could be taken as per the configured policies. 3.3.2. Enhanced Version As observed previously, the vanilla algorithm that involves a single secret polynomial is not secure. Therefore, the solution is further enhanced with usage of a random second polynomial chosen per packet. 3.3.2.1. Random Polynomial Let the second polynomial POLY2 be (RND + 7x + 10 x^2). RND is a random number and is generated for each packet. Note that POLY2 is public and need not be kept secret. The nodes can be preconfigured with the nonconstant coefficients (for example, 7 and 10 in this case could be configured through the Controller on each node). So precisely only RND value changes per packet and is public and the rest of the nonconstant coefficients of POLY2 kept secret. Brockners, et al. Expires May 3, 2017 [Page 9] InternetDraft Proof of Transit October 2016 3.3.2.2. Reconstruction Recall that each node is preconfigured with their respective Share(POLY1). Each node calculates its respective Share(POLY2) using the RND value retrieved from the packet. The CML reconstruction is enhanced as below. At every node, CML is updated as CML = CML+(((Share(POLY1)+ Share(POLY2)) * LPC) mod Prime Let us observe the packet level transformations in detail. For the example packet here, let the value RND be 45. Thus POLY2 would be (45 + 7x + 10x^2). The shares that could be generated are (2, 46), (4, 21), (5, 12). At ingress: The fields RND = 45. CML = 0. At node1 (x0): Respective share of POLY2 is generated i.e., (2, 46) because share index of node1 is 2. CML = 0 + ((28 + 46)* 21) mod 53 = 17 At node2 (x1): Respective share of POLY2 is generated i.e., (4, 21) because share index of node2 is 4. CML = 17 + ((17 + 21)*48) mod 53 = 17 + 22 = 39 At node3 (x2), which is also the verifier: The respective share of POLY2 is generated i.e., (5, 12) because the share index of the verifier is 12. CML = 39 + ((47 + 12)*38) mod 53 = 39 + 16 = 55 mod 53 = 2 The verification using CML is discussed in next section. 3.3.2.3. Verification As shown in the above example, for final verification, the verifier compares: VERIFY = (SECRET + RND) mod Prime, with Prime = 53 here VERIFY = (RND1 + RND2) mod Prime = ( 10 + 45 ) mod 53 = 2 Since VERIFY = CML the packet is proven to have gone through nodes 1, 2, and 3. Brockners, et al. Expires May 3, 2017 [Page 10] InternetDraft Proof of Transit October 2016 3.3.3. Final Version The enhanced version of the protocol is still prone to replay and preplay attacks. An attacker could reuse the POT metadata for bypassing the verification. So additional measures using packet integrity checks (HMAC) and sequence numbers (SEQ_NO) are discussed later "Security Considerations" section. 3.4. Operational Aspects To operationalize this scheme, a central controller is used to generate the necessary polynomials, the secret share per node, the prime number, etc. and distributing the data to the nodes participating in proof of transit. The identified node that performs the verification is provided with the verification key. The information provided from the Controller to each of the nodes participating in proof of transit is referred to as a proof of transit profile (POTprofile). Also note that the set of nodes for which the transit has to be proven are typically associated to a different trust domain than the verifier. Note that building the trust relationship between the Controller and the nodes is outside the scope of this document. Techniques such as those described in [ID.ietfanimaautonomiccontrolplane] might be applied. To optimize the overall data amount of exchanged and the processing at the nodes the following optimizations are performed: 1. The points (x, y) for each of the nodes on the public and private polynomials are picked such that the x component of the points match. This lends to the LPC values which are used to calculate the cumulative value CML to be constant. Note that the LPC are only depending on the x components. They can be computed at the controller and communicated to the nodes. Otherwise, one would need to distributed the x components to all the nodes. 2. A preevaluated portion of the public polynomial for each of the nodes is calculated and added to the POTprofile. Without this all the coefficients of the public polynomial had to be added to the POT profile and each node had to evaluate them. As stated before, the public portion is only the constant coefficient RND value, the preevaluated portion for each node should be kept secret as well. 3. To provide flexibility on the size of the cumulative and random numbers carried in the POT data a field to indicate this is shared and interpreted at the nodes. Brockners, et al. Expires May 3, 2017 [Page 11] InternetDraft Proof of Transit October 2016 3.5. Alternative Approach In certain scenarios preserving the order of the nodes traversed by the packet may be needed. An alternative, "nested encryption" based approach is described here for preserving the order 3.5.1. Basic Idea 1. The controller provisions all the nodes with their respective secret keys. 2. The controller provisions the verifier with all the secret keys of the nodes. 3. For each packet, the ingress node generates a random number RND and encrypts it with its secret key to generate CML value 4. Each subsequent node on the path encrypts CML with their respective secret key and passes it along 5. The verifier is also provisioned with the expected sequence of nodes in order to verify the order 6. The verifier receives the CML, RND values, reencrypts the RND with keys in the same order as expected sequence to verify. 3.5.2. Pros Nested encryption approach retains the order in which the nodes are traversed. 3.5.3. Cons 1. Standard AES encryption would need 128 bits of RND, CML. This results in a 256 bits of additional overhead is added per packet 2. In hardware platforms that do not support native encryption capabilities like (AESNI). This approach would have considerable impact on the computational latency 4. Sizing the Data for Proof of Transit Proof of transit requires transport of two data records in every packet that should be verified: 1. RND: Random number (the constant coefficient of public polynomial) Brockners, et al. Expires May 3, 2017 [Page 12] InternetDraft Proof of Transit October 2016 2. CML: Cumulative The size of the data records determines how often a new set of polynomials would need to be created. At maximum, the largest RND number that can be represented with a given number of bits determines the number of unique polynomials POLY2 that can be created. The table below shows the maximum interval for how long a single set of polynomials could last for a variety of bit rates and RND sizes: When choosing 64 bits for RND and CML data records, the time between a renewal of secrets could be as long as 3,100 years, even when running at 100 Gbps. +++++  Transfer  Secret/RND  Max # of packets  Time RND lasts   rate  size    +++++  1 Gbps  64  2^64 = approx.  approx. 310,000     2*10^19  years   10 Gbps  64  2^64 = approx.  approx. 31,000     2*10^19  years   100 Gbps  64  2^64 = approx.  approx. 3,100     2*10^19  years   1 Gbps  32  2^32 = approx.  2,200 seconds     4*10^9    10 Gbps  32  2^32 = approx.  220 seconds     4*10^9    100 Gbps  32  2^32 = approx.  22 seconds     4*10^9   +++++ Table assumes 64 octet packets Table 1: Proof of transit data sizing 5. Node Configuration A POT system consists of a number of nodes that participate in POT and a Controller, which serves as a control and configuration entity. The Controller is to create the required parameters (polynomials, prime number, etc.) and communicate those to the nodes. The sum of all parameters for a specific node is referred to as "POTprofile". This document does not define a specific protocol to be used between Controller and nodes. It only defines the procedures and the associated YANG data model. Brockners, et al. Expires May 3, 2017 [Page 13] InternetDraft Proof of Transit October 2016 5.1. Procedure The Controller creates new POTprofiles at a constant rate and communicates the POTprofile to the nodes. The controller labels a POTprofile "even" or "odd" and the Controller cycles between "even" and "odd" labeled profiles. The rate at which the POTprofiles are communicated to the nodes is configurable and is more frequent than the speed at which a POTprofile is "used up" (see table above). Once the POTprofile has been successfully communicated to all nodes (e.g., all NETCONF transactions completed, in case NETCONF is used as a protocol), the controller sends an "enable POTprofile" request to the ingress node. All nodes maintain two POTprofiles (an even and an odd POTprofile): One POTprofile is currently active and in use; one profile is standby and about to get used. A flag in the packet is indicating whether the odd or even POTprofile is to be used by a node. This is to ensure that during profile change the service is not disrupted. If the "odd" profile is active, the Controller can communicate the "even" profile to all nodes. Only if all the nodes have received the POTprofile, the Controller will tell the ingress node to switch to the "even" profile. Given that the indicator travels within the packet, all nodes will switch to the "even" profile. The "even" profile gets active on all nodes and nodes are ready to receive a new "odd" profile. Unless the ingress node receives a request to switch profiles, it'll continue to use the active profile. If a profile is "used up" the ingress node will recycle the active profile and start over (this could give rise to replay attacks in theory  but with 2^32 or 2^64 packets this isn't really likely in reality). 5.2. YANG Model This section defines that YANG data model for the information exchange between the Controller and the nodes. <CODE BEGINS> file "ietfpotprofile@20160615.yang" module ietfpotprofile { yangversion 1; namespace "urn:ietf:params:xml:ns:yang:ietfpotprofile"; prefix ietfpotprofile; organization "IETF xxx Working Group"; Brockners, et al. Expires May 3, 2017 [Page 14] InternetDraft Proof of Transit October 2016 contact ""; description "This module contains a collection of YANG definitions for proof of transit configuration parameters. The model is meant for proof of transit and is targeted for communicating the POTprofile between a controller and nodes participating in proof of transit."; revision 20160615 { description "Initial revision."; reference ""; } typedef profileindexrange { type int32 { range "0 .. 1"; } description "Range used for the profile index. Currently restricted to 0 or 1 to identify the odd or even profiles."; } grouping potprofile { description "A grouping for proof of transit profiles."; list potprofilelist { key "potprofileindex"; orderedby user; description "A set of pot profiles."; leaf potprofileindex { type profileindexrange; mandatory true; description "Proof of transit profile index."; } leaf primenumber { type uint64; mandatory true; description "Prime number used for module math computation"; } leaf secretshare { Brockners, et al. Expires May 3, 2017 [Page 15] InternetDraft Proof of Transit October 2016 type uint64; mandatory true; description "Share of the secret of polynomial 1 used in computation"; } leaf publicpolynomial { type uint64; mandatory true; description "Pre evaluated Public polynomial"; } leaf lpc { type uint64; mandatory true; description "Lagrange Polynomial Coefficient"; } leaf validator { type boolean; default "false"; description "True if the node is a verifier node"; } leaf validatorkey { type uint64; description "Secret key for validating the path, constant of poly 1"; } leaf bitmask { type uint64; default 4294967295; description "Number of bits as mask used in controlling the size of the random value generation. 32bits of mask is default."; } } } container potprofiles { description "A group of proof of transit profiles."; list potprofileset { key "potprofilename"; Brockners, et al. Expires May 3, 2017 [Page 16] InternetDraft Proof of Transit October 2016 orderedby user; description "Set of proof of transit profiles that group parameters required to classify and compute proof of transit metadata at a node"; leaf potprofilename { type string; mandatory true; description "Unique identifier for each proof of transit profile"; } leaf activeprofileindex { type profileindexrange; description "Proof of transit profile index that is currently active. Will be set in the first hop of the path or chain. Other nodes will not use this field."; } uses potprofile; } /*** Container: end ***/ } /*** module: end ***/ } <CODE ENDS> 6. IANA Considerations IANA considerations will be added in a future version of this document. 7. Manageability Considerations Manageability considerations will be addressed in a later version of this document. 8. Security Considerations Different security requirements achieved by the solution approach are discussed here. Brockners, et al. Expires May 3, 2017 [Page 17] InternetDraft Proof of Transit October 2016 8.1. Proof of Transit Proof of correctness and security of the solution approach is per Shamir's Secret Sharing Scheme [SSS]. Cryptographically speaking it achieves informationtheoretic security i.e., it cannot be broken by an attacker even with unlimited computing power. As long as the below conditions are met it is impossible for an attacker to bypass one or multiple nodes without getting caught. o If there are k+1 nodes in the path, the polynomials (POLY1, POLY 2) should be of degree k. Also k+1 points of POLY1 are chosen and assigned to each node respectively. The verifier can re construct the k degree polynomial (POLY3) only when all the points are correctly retrieved. o Precisely three values are kept secret by individual nodes. Share of SECRET (i.e. points on POLY1), Share of POLY2, LPC, P. Note that only constant coefficient, RND, of POLY2 is public. x values and nonconstant coefficient of POLY2 are secret An attacker bypassing a few nodes will miss adding a respective point on POLY1 to corresponding point on POLY2 , thus the verifier cannot construct POLY3 for cross verification. Also it is highly recommended that different polynomials should be used as POLY1 across different paths, traffic profiles or service chains. 8.2. Cryptanalysis A passive attacker could try to harvest the POT data (i.e., CML, RND values) in order to determine the configured secrets. Subsequently two types of differential analysis for guessing the secrets could be done. o InterNode: A passive attacker observing CML values across nodes (i.e., as the packets entering and leaving), cannot perform differential analysis to construct the points on POLY1. This is because at each point there are four unknowns (i.e. Share(POLY 1), Share(Poly2) LPC and prime number P) and three known values (i.e. RND, CMLbefore, CMLafter). o InterPackets: A passive attacker could observe CML values across packets (i.e., values of PKT1 and subsequent PKT2), in order to predict the secrets. Differential analysis across packets could be mitigated using a good PRNG for generating RND. Note that if constant coefficient is a sequence number than CML values become quite predictable and the scheme would be broken. Brockners, et al. Expires May 3, 2017 [Page 18] InternetDraft Proof of Transit October 2016 8.3. AntiReplay A passive attacker could reuse a set of older RND and the intermediate CML values to bypass certain nodes in later packets. Such attacks could be avoided by carefully choosing POLY2 as a (SEQ_NO + RND). For example, if 64 bits are being used for POLY2 then first 16 bits could be a sequence number SEQ_NO and next 48 bits could be a random number. Subsequently, the verifier could use the SEQ_NO bits to run classic antireplay techniques like sliding window used in IPSEC. The verifier could buffer up to 2^16 packets as a sliding window. Packets arriving with a higher SEQ_NO than current buffer could be flagged legitimate. Packets arriving with a lower SEQ_NO than current buffer could be flagged as suspicious. For all practical purposes in the rest of the document RND means SEQ_NO + RND to keep it simple. The solution discussed in this memo does not currently mitigate replay attacks. An antireplay mechanism may be included in future versions of the solution. 8.4. AntiPreplay An active attacker could try to perform a maninthemiddle (MITM) attack by extracting the POT of PKT1 and using it in PKT2. Subsequently attacker drops the PKT1 in order to avoid duplicate POT values reaching the verifier. If the PKT1 reaches the verifier, then this attack is same as Replay attacks discussed before. Preplay attacks are possible since the POT metadata is not dependent on the packet fields. Below steps are recommended for remediation: o Ingress node and Verifier are configured with common pre shared key o Ingress node generates a Message Authentication Code (MAC) from packet fields using standard HMAC algorithm. o The left most bits of the output are truncated to desired length to generate RND. It is recommended to use a minimum of 32 bits. o The verifier regenerates the HMAC from the packet fields and compares with RND. To ensure the POT data is in fact that of the packet. Brockners, et al. Expires May 3, 2017 [Page 19] InternetDraft Proof of Transit October 2016 If an HMAC is used, an active attacker lacks the knowledge of the preshared key, and thus cannot launch preplay attacks. The solution discussed in this memo does not currently mitigate prereplay attacks. A mitigation mechanism may be included in future versions of the solution. 8.5. AntiTampering An active attacker could not insert any arbitrary value for CML. This would subsequently fail the reconstruction of the POLY3. Also an attacker could not update the CML with a previously observed value. This could subsequently be detected by using timestamps within the RND value as discussed above. 8.6. Recycling The solution approach is flexible for recycling long term secrets like POLY1. All the nodes could be periodically updated with shares of new SECRET as best practice. The table above could be consulted for refresh cycles (see Section 4). 8.7. Redundant Nodes and Failover A "node" or "service" in terms of POT can be implemented by one or multiple physical entities. In case of multiple physical entities (e.g., for loadbalancing, or business continuity situations  consider for example a set of firewalls), all physical entities which are implementing the same POT node are given that same share of the secret. This makes multiple physical entities represent the same POT node from an algorithm perspective. 8.8. Controller Operation The Controller needs to be secured given that it creates and holds the secrets, as need to be the nodes. The communication between Controller and the nodes also needs to be secured. As secure communication protocol such as for example NETCONF over SSH should be chosen for Controller to node communication. The Controller only interacts with the nodes during the initial configuration and thereafter at regular intervals at which the operator chooses to switch to a new set of secrets. In case 64 bits are used for the datarecords "CML" and "RND" which are carried within the data packet, the regular intervals are expected to be quite long (e.g., at 100 Gbps, a profile would only be used up after 3100 years)  see Section 4 above, thus even a "headless" operation without a Controller can be considered feasible. In such a case, the Brockners, et al. Expires May 3, 2017 [Page 20] InternetDraft Proof of Transit October 2016 Controller would only be used for the initial configuration of the POTprofiles. 8.9. Verification Scope The POT solution defined in this document verifies that a datapacket traversed or transited a specific set of nodes. From an algorithm perspective, a "node" is an abstract entity. It could be represented by one or multiple physical or virtual network devices, or is could be a component within a networking device or system. The latter would be the case if a forwarding path within a device would need to be securely verified. 8.9.1. Node Ordering POT using Shamir's secret sharing scheme as discussed in this document provides for a means to verify that a set of nodes has been visited by a data packet. It does not verify the order in which the data packet visited the nodes. In case the order in which a data packet traversed a particular set of nodes needs to be verified as well, alternate schemes that e.g., rely on "nested encryption" could to be considered. 8.9.2. Stealth Nodes The POT approach discussed in this document is to prove that a data packet traversed a specific set of "nodes". This set could be all nodes within a path, but could also be a subset of nodes in a path. Consequently, the POT approach isn't suited to detect whether "stealth" nodes which do not participate in proofoftransit have been inserted into a path. 9. Acknowledgements The authors would like to thank Eric Vyncke, Nalini Elkins, Srihari Raghavan, Ranganathan T S, Karthik Babu Harichandra Babu, Akshaya Nadahalli, Erik Nordmark, and Andrew Yourtchenko for the comments and advice. 10. References 10.1. Normative References [RFC7665] Halpern, J., Ed. and C. Pignataro, Ed., "Service Function Chaining (SFC) Architecture", RFC 7665, DOI 10.17487/ RFC7665, October 2015, <http://www.rfceditor.org/info/rfc7665>. Brockners, et al. Expires May 3, 2017 [Page 21] InternetDraft Proof of Transit October 2016 [SSS] "Shamir's Secret Sharing", <https://en.wikipedia.org/wiki/ Shamir%27s_Secret_Sharing>. 10.2. Informative References [ID.ietfanimaautonomiccontrolplane] Behringer, M., Eckert, T., and S. Bjarnason, "An Autonomic Control Plane", draftietfanimaautonomiccontrol plane03 (work in progress), July 2016. Authors' Addresses Frank Brockners Cisco Systems, Inc. Hansaallee 249, 3rd Floor DUESSELDORF, NORDRHEINWESTFALEN 40549 Germany Email: fbrockne@cisco.com Shwetha Bhandari Cisco Systems, Inc. Cessna Business Park, Sarjapura Marathalli Outer Ring Road Bangalore, KARNATAKA 560 087 India Email: shwethab@cisco.com Sashank Dara Cisco Systems, Inc. Cessna Business Park, Sarjapura Marathalli Outer Ring Road BANGALORE, Bangalore, KARNATAKA 560 087 INDIA Email: sadara@cisco.com Carlos Pignataro Cisco Systems, Inc. 720011 Kit Creek Road Research Triangle Park, NC 27709 United States Email: cpignata@cisco.com Brockners, et al. Expires May 3, 2017 [Page 22] InternetDraft Proof of Transit October 2016 John Leddy Comcast Email: John_Leddy@cable.comcast.com Stephen Youell JP Morgan Chase 25 Bank Street London E14 5JP United Kingdom Email: stephen.youell@jpmorgan.com David Mozes Mellanox Technologies Ltd. Email: davidm@mellanox.com Tal Mizrahi Marvell 6 Hamada St. Yokneam 20692 Israel Email: talmi@marvell.com Brockners, et al. Expires May 3, 2017 [Page 23]