idnits 2.17.1 draft-ietf-sfc-proof-of-transit-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 11, 2019) is 1866 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Outdated reference: A later version (-17) exists of draft-ietf-ippm-ioam-data-04 == Outdated reference: A later version (-30) exists of draft-ietf-anima-autonomic-control-plane-18 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group F. Brockners 3 Internet-Draft S. Bhandari 4 Intended status: Experimental Cisco 5 Expires: September 12, 2019 S. Dara 6 Seconize 7 C. Pignataro 8 Cisco 9 J. Leddy 10 Comcast 11 S. Youell 12 JPMC 13 D. Mozes 15 T. Mizrahi 16 Huawei Network.IO Innovation Lab 17 A. Aguado 18 Universidad Politecnica de Madrid 19 D. Lopez 20 Telefonica I+D 21 March 11, 2019 23 Proof of Transit 24 draft-ietf-sfc-proof-of-transit-02 26 Abstract 28 Several technologies such as Traffic Engineering (TE), Service 29 Function Chaining (SFC), and policy based routing are used to steer 30 traffic through a specific, user-defined path. This document defines 31 mechanisms to securely prove that traffic transited said defined 32 path. These mechanisms allow to securely verify whether, within a 33 given path, all packets traversed all the nodes that they are 34 supposed to visit. 36 Status of This Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at http://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on September 12, 2019. 53 Copyright Notice 55 Copyright (c) 2019 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (http://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the Simplified BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 71 2. Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 4 72 3. Proof of Transit . . . . . . . . . . . . . . . . . . . . . . 5 73 3.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . 6 74 3.2. Solution Approach . . . . . . . . . . . . . . . . . . . . 7 75 3.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 7 76 3.2.2. In Transit . . . . . . . . . . . . . . . . . . . . . 7 77 3.2.3. Verification . . . . . . . . . . . . . . . . . . . . 8 78 3.3. Illustrative Example . . . . . . . . . . . . . . . . . . 8 79 3.3.1. Baseline . . . . . . . . . . . . . . . . . . . . . . 8 80 3.3.1.1. Secret Shares . . . . . . . . . . . . . . . . . . 8 81 3.3.1.2. Lagrange Polynomials . . . . . . . . . . . . . . 9 82 3.3.1.3. LPC Computation . . . . . . . . . . . . . . . . . 9 83 3.3.1.4. Reconstruction . . . . . . . . . . . . . . . . . 9 84 3.3.1.5. Verification . . . . . . . . . . . . . . . . . . 10 85 3.3.2. Complete Solution . . . . . . . . . . . . . . . . . . 10 86 3.3.2.1. Random Polynomial . . . . . . . . . . . . . . . . 10 87 3.3.2.2. Reconstruction . . . . . . . . . . . . . . . . . 10 88 3.3.2.3. Verification . . . . . . . . . . . . . . . . . . 11 89 3.3.3. Solution Deployment Considerations . . . . . . . . . 11 90 3.4. Operational Aspects . . . . . . . . . . . . . . . . . . . 12 91 3.5. Ordered POT (OPOT) . . . . . . . . . . . . . . . . . . . 12 92 4. Sizing the Data for Proof of Transit . . . . . . . . . . . . 13 93 5. Node Configuration . . . . . . . . . . . . . . . . . . . . . 14 94 5.1. Procedure . . . . . . . . . . . . . . . . . . . . . . . . 15 95 5.2. YANG Model . . . . . . . . . . . . . . . . . . . . . . . 15 97 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 98 7. Manageability Considerations . . . . . . . . . . . . . . . . 18 99 8. Security Considerations . . . . . . . . . . . . . . . . . . . 19 100 8.1. Proof of Transit . . . . . . . . . . . . . . . . . . . . 19 101 8.2. Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . 20 102 8.3. Anti-Replay . . . . . . . . . . . . . . . . . . . . . . . 20 103 8.4. Anti-Preplay . . . . . . . . . . . . . . . . . . . . . . 21 104 8.5. Tampering . . . . . . . . . . . . . . . . . . . . . . . . 21 105 8.6. Recycling . . . . . . . . . . . . . . . . . . . . . . . . 21 106 8.7. Redundant Nodes and Failover . . . . . . . . . . . . . . 22 107 8.8. Controller Operation . . . . . . . . . . . . . . . . . . 22 108 8.9. Verification Scope . . . . . . . . . . . . . . . . . . . 22 109 8.9.1. Node Ordering . . . . . . . . . . . . . . . . . . . . 23 110 8.9.2. Stealth Nodes . . . . . . . . . . . . . . . . . . . . 23 111 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 23 112 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 113 10.1. Normative References . . . . . . . . . . . . . . . . . . 23 114 10.2. Informative References . . . . . . . . . . . . . . . . . 24 115 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24 117 1. Introduction 119 Several deployments use Traffic Engineering, policy routing, Segment 120 Routing (SR), and Service Function Chaining (SFC) [RFC7665] to steer 121 packets through a specific set of nodes. In certain cases, 122 regulatory obligations or a compliance policy require operators to 123 prove that all packets that are supposed to follow a specific path 124 are indeed being forwarded across and exact set of pre-determined 125 nodes. 127 If a packet flow is supposed to go through a series of service 128 functions or network nodes, it has to be proven that indeed all 129 packets of the flow followed the path or service chain or collection 130 of nodes specified by the policy. In case some packets of a flow 131 weren't appropriately processed, a verification device should 132 determine the policy violation and take corresponding actions 133 corresponding to the policy (e.g., drop or redirect the packet, send 134 an alert etc.) In today's deployments, the proof that a packet 135 traversed a particular path or service chain is typically delivered 136 in an indirect way: Service appliances and network forwarding are in 137 different trust domains. Physical hand-off-points are defined 138 between these trust domains (i.e. physical interfaces). Or in other 139 terms, in the "network forwarding domain" things are wired up in a 140 way that traffic is delivered to the ingress interface of a service 141 appliance and received back from an egress interface of a service 142 appliance. This "wiring" is verified and then trusted upon. The 143 evolution to Network Function Virtualization (NFV) and modern service 144 chaining concepts (using technologies such as Locator/ID Separation 145 Protocol (LISP), Network Service Header (NSH), Segment Routing (SR), 146 etc.) blurs the line between the different trust domains, because the 147 hand-off-points are no longer clearly defined physical interfaces, 148 but are virtual interfaces. As a consequence, different trust layers 149 should not to be mixed in the same device. For an NFV scenario a 150 different type of proof is required. Offering a proof that a packet 151 indeed traversed a specific set of service functions or nodes allows 152 operators to evolve from the above described indirect methods of 153 proving that packets visit a predetermined set of nodes. 155 The solution approach presented in this document is based on a small 156 portion of operational data added to every packet. This "in-situ" 157 operational data is also referred to as "proof of transit data", or 158 POT data. The POT data is updated at every required node and is used 159 to verify whether a packet traversed all required nodes. A 160 particular set of nodes "to be verified" is either described by a set 161 of shares of a single secret. Nodes on the path retrieve their 162 individual shares of the secret using Shamir's Secret Sharing scheme 163 from a central controller. The complete secret set is only known to 164 the controller and a verifier node, which is typically the ultimate 165 node on a path that performs verification. Each node in the path 166 uses its share of the secret to update the POT data of the packets as 167 the packets pass through the node. When the verifier receives a 168 packet, it uses its key along with data found in the packet to 169 validate whether the packet traversed the path correctly. 171 2. Conventions 173 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 174 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 175 document are to be interpreted as described in [RFC2119]. 177 Abbreviations used in this document: 179 HMAC: Hash based Message Authentication Code. For example, 180 HMAC-SHA256 generates 256 bits of MAC 182 IOAM: In-situ Operations, Administration, and Maintenance 184 LISP: Locator/ID Separation Protocol 186 LPC: Lagrange Polynomial Constants 188 MTU: Maximum Transmit Unit 190 NFV: Network Function Virtualization 192 NSH: Network Service Header 193 POT: Proof of Transit 195 POT-profile: Proof of Transit Profile that has the necessary data 196 for nodes to participate in proof of transit 198 RND: Random Bits generated per packet. Packet fields that do 199 not change during the traversal are given as input to 200 HMAC-256 algorithm. A minimum of 32 bits (left most) need 201 to be used from the output if RND is used to verify the 202 packet integrity. This is a standard recommendation by 203 NIST. 205 SEQ_NO: Sequence number initialized to a predefined constant. 206 This is used in concatenation with RND bits to mitigate 207 different attacks discussed later. 209 SFC: Service Function Chain 211 SSSS: Shamir's Secret Sharing Scheme 213 SR: Segment Routing 215 3. Proof of Transit 217 This section discusses methods and algorithms to provide for a "proof 218 of transit" for packets traversing a specific path. A path which is 219 to be verified consists of a set of nodes. Transit of the data 220 packets through those nodes is to be proven. Besides the nodes, the 221 setup also includes a Controller that creates secrets and secrets 222 shares and configures the nodes for POT operations. 224 The methods how traffic is identified and associated to a specific 225 path is outside the scope of this document. Identification could be 226 done using a filter (e.g., 5-tuple classifier), or an identifier 227 which is already present in the packet (e.g., path or service 228 identifier, NSH Service Path Identifier (SPI), flow-label, etc.) 230 The POT information is encapsulated in packets as an IOAM Proof Of 231 Transit Option. The details and format of the encapsulation and the 232 POT Option format are specified in [I-D.ietf-ippm-ioam-data]. 234 The solution approach is detailed in two steps. Initially the 235 concept of the approach is explained. This concept is then further 236 refined to make it operationally feasible. 238 3.1. Basic Idea 240 The method relies on adding POT data to all packets that traverse a 241 path. The added POT data allows a verifying node (egress node) to 242 check whether a packet traversed the identified set of nodes on a 243 path correctly or not. Security mechanisms are natively built into 244 the generation of the POT data to protect against misuse (e.g., 245 configuration mistakes). The mechanism for POT leverages "Shamir's 246 Secret Sharing" scheme [SSS]. 248 Shamir's secret sharing base idea: A polynomial (represented by its 249 coefficients) of degree k is chosen as a secret by the controller. A 250 polynomial represents a curve. A set of k+1 points on the curve 251 define the polynomial and are thus needed to (re-)construct the 252 polynomial. Each of these k+1 points of the polynomial is called a 253 "share" of the secret. A single secret is associated with a 254 particular set of k+1 nodes, which typically represent the path to be 255 verified. k+1 shares of the single secret (i.e., k+1 points on the 256 curve) are securely distributed from a Controller to the network 257 nodes. Nodes use their respective share to update a cumulative value 258 in the POT data of each packet. Only a verifying node has access to 259 the complete secret. The verifying node validates the correctness of 260 the received POT data by reconstructing the curve. 262 The polynomial cannot be reconstructed if any of the points are 263 missed or tampered. Per Shamir's Secret Sharing Scheme, any lesser 264 points means one or more nodes are missed. Details of the precise 265 configuration needed for achieving security are discussed further 266 below. 268 While applicable in theory, a vanilla approach based on Shamir's 269 Secret Sharing Scheme could be easily attacked. If the same 270 polynomial is reused for every packet for a path a passive attacker 271 could reuse the value. As a consequence, one could consider creating 272 a different polynomial per packet. Such an approach would be 273 operationally complex. It would be complex to configure and recycle 274 so many curves and their respective points for each node. Rather 275 than using a single polynomial, two polynomials are used for the 276 solution approach: A secret polynomial as described above which is 277 kept constant, and a per-packet polynomial which is public and 278 generated by the ingress node (the first node along the path). 279 Operations are performed on the sum of those two polynomials - 280 creating a third polynomial which is secret and per packet. 282 3.2. Solution Approach 284 Solution approach: The overall algorithm uses two polynomials: POLY-1 285 and POLY-2. POLY-1 is secret and constant. A different POLY-1 is 286 used for each path, and its value is known to the controller and to 287 the verifier of the respective path. Each node gets a point on 288 POLY-1 at setup-time and keeps it secret. POLY-2 is public, random 289 and per packet. Each node generates a point on POLY-2 each time a 290 packet crosses it. Each node then calculates (point on POLY-1 + 291 point on POLY-2) to get a (point on POLY-3) and passes it to verifier 292 by adding it to each packet. The verifier constructs POLY-3 from the 293 points given by all the nodes and cross checks whether POLY-3 = 294 POLY-1 + POLY-2. Only the verifier knows POLY-1. 296 The solution leverages finite field arithmetic in a field of size 297 "prime number", i.e. all operations are performed "modulo prime 298 number". 300 Detailed algorithms are discussed next. A simple example that 301 describes how the algorithms work is discussed in Section 3.3. 303 The algorithms themselves do not constrain the ranges of possible 304 values for the different parameters and coefficients used. A 305 deployment of the algorithms will always need to define appropriate 306 ranges. Please refer to the YANG model in Section 5.2 for details on 307 the units and ranges of possible values of the different parameters 308 and coefficients. 310 3.2.1. Setup 312 A controller generates a first polynomial (POLY-1) of degree k and 313 k+1 points on the polynomial, corresponding to the k+1 nodes along 314 the path. The constant coefficient of POLY-1 is considered the 315 SECRET, which is per the definition of the SSSS algorithm [SSS]. The 316 non-constant coefficients are used to generate the Lagrange 317 Polynomial Constants (LPC). Each of the k+1 nodes (including 318 verifier) are assigned a point on the polynomial i.e., shares of the 319 SECRET. The verifier is configured with the SECRET. The Controller 320 also generates coefficients (except the constant coefficient, called 321 "RND", which is changed on a per packet basis) of a second polynomial 322 POLY-2 of the same degree. Each node is configured with the LPC of 323 POLY-2. Note that POLY-2 is public. 325 3.2.2. In Transit 327 For each packet, the ingress node generates a random number (RND). 328 It is considered as the constant coefficient for POLY-2. A 329 cumulative value (CML) is initialized to 0. Both RND, CML are 330 carried as within the packet POT data. As the packet visits each 331 node, the RND is retrieved from the packet and the respective share 332 of POLY-2 is calculated. Each node calculates (Share(POLY-1) + 333 Share(POLY-2)) and CML is updated with this sum, specifically each 334 node performs 336 CML = CML+(((Share(POLY-1)+ Share(POLY-2)) * LPC) mod Prime, with 337 "LPC" being the Lagrange Polynomial Constant and "Prime" being the 338 prime number which defines the finite field arithmetic that all 339 operations are done over. Please also refer to Section 3.3.2 below 340 for further details how the operations are performed. 342 This step is performed by each node until the packet completes the 343 path. The verifier also performs the step with its respective share. 345 3.2.3. Verification 347 The verifier cross checks whether CML = SECRET + RND. If this 348 matches then the packet traversed the specified set of nodes in the 349 path. This is due to the additive homomorphic property of Shamir's 350 Secret Sharing scheme. 352 3.3. Illustrative Example 354 This section shows a simple example to illustrate step by step the 355 approach described above. The example assumes a network with 3 356 nodes. The last node that packets traverse also serves as the 357 verifier. A Controller communicates the required parameters to the 358 individual nodes. 360 3.3.1. Baseline 362 Assumption: It is to be verified whether packets passed through the 3 363 nodes. A polynomial of degree 2 is chosen for verification. 365 Choices: Prime = 53. POLY-1(x) = (3x^2 + 3x + 10) mod 53. The 366 secret to be re-constructed is the constant coefficient of POLY-1, 367 i.e., SECRET=10. It is important to note that all operations are 368 done over a finite field (i.e., modulo Prime = 53). 370 3.3.1.1. Secret Shares 372 The shares of the secret are the points on POLY-1 chosen for the 3 373 nodes. For example, let x0=2, x1=4, x2=5. 375 POLY-1(2) = 28 => (x0, y0) = (2, 28) 377 POLY-1(4) = 17 => (x1, y1) = (4, 17) 378 POLY-1(5) = 47 => (x2, y2) = (5, 47) 380 The three points above are the points on the curve which are 381 considered the shares of the secret. They are assigned by the 382 Controller to three nodes respectively and are kept secret. 384 3.3.1.2. Lagrange Polynomials 386 Lagrange basis polynomials (or Lagrange polynomials) are used for 387 polynomial interpolation. For a given set of points on the curve 388 Lagrange polynomials (as defined below) are used to reconstruct the 389 curve and thus reconstruct the complete secret. 391 l0(x) = (((x-x1) / (x0-x1)) * ((x-x2)/x0-x2))) mod 53 = 392 (((x-4) / (2-4)) * ((x-5)/2-5))) mod 53 = 393 (10/3 - 3x/2 + (1/6)x^2) mod 53 395 l1(x) = (((x-x0) / (x1-x0)) * ((x-x2)/x1-x2))) mod 53 = 396 (-5 + 7x/2 - (1/2)x^2) mod 53 398 l2(x) = (((x-x0) / (x2-x0)) * ((x-x1)/x2-x1))) mod 53 = 399 (8/3 - 2 + (1/3)x^2) mod 53 401 3.3.1.3. LPC Computation 403 Since x0=2, x1=4, x2=5 are chosen points. Given that computations 404 are done over a finite arithmetic field ("modulo a prime number"), 405 the Lagrange basis polynomial constants are computed modulo 53. The 406 Lagrange Polynomial Constant (LPC) would be 10/3 , -5 , 8/3.LPC are 407 computed by the Controller and communicated to the individual nodes. 409 LPC(l0) = (10/3) mod 53 = 21 411 LPC(l1) = (-5) mod 53 = 48 413 LPC(l2) = (8/3) mod 53 = 38 415 For a general way to compute the modular multiplicative inverse, see 416 e.g., the Euclidean algorithm. 418 3.3.1.4. Reconstruction 420 Reconstruction of the polynomial is well-defined as 422 POLY1(x) = l0(x) * y0 + l1(x) * y1 + l2(x) * y2 424 Subsequently, the SECRET, which is the constant coefficient of 425 POLY1(x) can be computed as below 426 SECRET = (y0*LPC(l0)+y1*LPC(l1)+y2*LPC(l2)) mod 53 428 The secret can be easily reconstructed using the y-values and the 429 LPC: 431 SECRET = (y0*LPC(l0) + y1*LPC(l1) + y2*LPC(l2)) mod 53 = mod (28 * 21 432 + 17 * 48 + 47 * 38) mod 53 = 3190 mod 53 = 10 434 One observes that the secret reconstruction can easily be performed 435 cumulatively hop by hop, i.e. by every node. CML represents the 436 cumulative value. It is the POT data in the packet that is updated 437 at each hop with the node's respective (yi*LPC(i)), where i is their 438 respective value. 440 3.3.1.5. Verification 442 Upon completion of the path, the resulting CML is retrieved by the 443 verifier from the packet POT data. Recall that the verifier is 444 preconfigured with the original SECRET. It is cross checked with the 445 CML by the verifier. Subsequent actions based on the verification 446 failing or succeeding could be taken as per the configured policies. 448 3.3.2. Complete Solution 450 As observed previously, the baseline algorithm that involves a single 451 secret polynomial is not secure. The complete solution leverages a 452 random second polynomial, which is chosen per packet. 454 3.3.2.1. Random Polynomial 456 Let the second polynomial POLY-2 be (RND + 7x + 10 x^2). RND is a 457 random number and is generated for each packet. Note that POLY-2 is 458 public and need not be kept secret. The nodes can be pre-configured 459 with the non-constant coefficients (for example, 7 and 10 in this 460 case could be configured through the Controller on each node). So 461 precisely only the RND value changes per packet and is public and the 462 rest of the non-constant coefficients of POLY-2 is kept secret. 464 3.3.2.2. Reconstruction 466 Recall that each node is preconfigured with their respective 467 Share(POLY-1). Each node calculates its respective Share(POLY-2) 468 using the RND value retrieved from the packet. The CML 469 reconstruction is enhanced as below. At every node, CML is updated 470 as 472 CML = CML+(((Share(POLY-1)+ Share(POLY-2)) * LPC) mod Prime 473 Let us observe the packet level transformations in detail. For the 474 example packet here, let the value RND be 45. Thus POLY-2 would be 475 (45 + 7x + 10x^2). 477 The shares that could be generated are (2, 46), (4, 21), (5, 12). 479 At ingress: The fields RND = 45. CML = 0. 481 At node-1 (x0): Respective share of POLY-2 is generated i.e., (2, 482 46) because share index of node-1 is 2. 484 CML = 0 + ((28 + 46)* 21) mod 53 = 17 486 At node-2 (x1): Respective share of POLY-2 is generated i.e., (4, 487 21) because share index of node-2 is 4. 489 CML = 17 + ((17 + 21)*48) mod 53 = 17 + 22 = 39 491 At node-3 (x2), which is also the verifier: The respective share 492 of POLY-2 is generated i.e., (5, 12) because the share index of 493 the verifier is 12. 495 CML = 39 + ((47 + 12)*38) mod 53 = 39 + 16 = 55 mod 53 = 2 497 The verification using CML is discussed in next section. 499 3.3.2.3. Verification 501 As shown in the above example, for final verification, the verifier 502 compares: 504 VERIFY = (SECRET + RND) mod Prime, with Prime = 53 here 506 VERIFY = (RND-1 + RND-2) mod Prime = ( 10 + 45 ) mod 53 = 2 508 Since VERIFY = CML the packet is proven to have gone through nodes 1, 509 2, and 3. 511 3.3.3. Solution Deployment Considerations 513 The "complete solution" described above in Section 3.3.2 could still 514 be prone to replay or preplay attacks. An attacker could e.g. reuse 515 the POT metadata for bypassing the verification. These threats can 516 be mitigated by appropriate parameterization of the algorithm. 517 Please refer to Section 8 for details. 519 3.4. Operational Aspects 521 To operationalize this scheme, a central controller is used to 522 generate the necessary polynomials, the secret share per node, the 523 prime number, etc. and distributing the data to the nodes 524 participating in proof of transit. The identified node that performs 525 the verification is provided with the verification key. The 526 information provided from the Controller to each of the nodes 527 participating in proof of transit is referred to as a proof of 528 transit profile (POT-profile). Also note that the set of nodes for 529 which the transit has to be proven are typically associated to a 530 different trust domain than the verifier. Note that building the 531 trust relationship between the Controller and the nodes is outside 532 the scope of this document. Techniques such as those described in 533 [I-D.ietf-anima-autonomic-control-plane] might be applied. 535 To optimize the overall data amount of exchanged and the processing 536 at the nodes the following optimizations are performed: 538 1. The points (x, y) for each of the nodes on the public and private 539 polynomials are picked such that the x component of the points 540 match. This lends to the LPC values which are used to calculate 541 the cumulative value CML to be constant. Note that the LPC are 542 only depending on the x components. They can be computed at the 543 controller and communicated to the nodes. Otherwise, one would 544 need to distributed the x components to all the nodes. 546 2. A pre-evaluated portion of the public polynomial for each of the 547 nodes is calculated and added to the POT-profile. Without this 548 all the coefficients of the public polynomial had to be added to 549 the POT profile and each node had to evaluate them. As stated 550 before, the public portion is only the constant coefficient RND 551 value, the pre-evaluated portion for each node should be kept 552 secret as well. 554 3. To provide flexibility on the size of the cumulative and random 555 numbers carried in the POT data a field to indicate this is 556 shared and interpreted at the nodes. 558 3.5. Ordered POT (OPOT) 560 POT as discussed in this document so far only verifies that a defined 561 set of nodes have been traversed by a packet. The order in which 562 nodes where traversed is not verified. "Ordered Proof of Transit 563 (OPOT)" addresses the need of deployments, that require to verify the 564 order in which nodes were traversed. OPOT extends the POT scheme 565 with symmetric masking between the nodes. 567 1. For each path the controller provisions all the nodes with (or 568 asks them to agree on) two secrets per node, that we will refer 569 to as masks, one for the connection from the upstream node(s), 570 another for the connection to the downstream node(s). For 571 obvious reasons, the ingress and egress (verifier) nodes only 572 receive one, for downstream and upstream, respectively. 574 2. Any two contiguous nodes in the OPOT stream share the mask for 575 the connection between them, in the shape of symmetric keys. 576 Masks can be refreshed as per-policy, defined at each hop or 577 globally by the controller. 579 3. Each mask has the same size in bits as the length assigned to CML 580 plus RND, as described in the above sections. 582 4. Whenever a packet is received at an intermediate node, the 583 CML+RND sequence is deciphered (by XORing, though other ciphering 584 schemas MAY be possible) with the upstream mask before applying 585 the procedures described in Section 3.3.2. 587 5. Once the new values of CML+RND are produced, they are ciphered 588 (by XORing, though other ciphering schemas MAY be possible) with 589 the downstream mask before transmitting the packet to the next 590 node downstream. 592 6. The ingress node only applies step 5 above, while the verifier 593 only applies step 4 before running the verification procedure. 595 The described process allows the verifier to check if the packet has 596 followed the correct order while traversing the path. In particular, 597 the reconstruction process will fail if the order is not respected, 598 as the deciphering process will produce invalid CML and RND values, 599 and the interpolation (secret reconstruction) will finally generate a 600 wrong verification value. 602 This procedure does not impose a high computational burden, does not 603 require additional packet overhead, can be deployed on chains of any 604 length, does not require any node to be aware of any additional 605 information than the upstream and downstream masks, and can be 606 integrated with the other operational mechanisms applied by the 607 controller to distribute shares and other secret material. 609 4. Sizing the Data for Proof of Transit 611 Proof of transit requires transport of two data fields in every 612 packet that should be verified: 614 1. RND: Random number (the constant coefficient of public 615 polynomial) 617 2. CML: Cumulative 619 The size of the data fields determines how often a new set of 620 polynomials would need to be created. At maximum, the largest RND 621 number that can be represented with a given number of bits determines 622 the number of unique polynomials POLY-2 that can be created. The 623 table below shows the maximum interval for how long a single set of 624 polynomials could last for a variety of bit rates and RND sizes: When 625 choosing 64 bits for RND and CML data fields, the time between a 626 renewal of secrets could be as long as 3,100 years, even when running 627 at 100 Gbps. 629 +-------------+--------------+------------------+-------------------+ 630 | Transfer | Secret/RND | Max # of packets | Time RND lasts | 631 | rate | size | | | 632 +-------------+--------------+------------------+-------------------+ 633 | 1 Gbps | 64 | 2^64 = approx. | approx. 310,000 | 634 | | | 2*10^19 | years | 635 | 10 Gbps | 64 | 2^64 = approx. | approx. 31,000 | 636 | | | 2*10^19 | years | 637 | 100 Gbps | 64 | 2^64 = approx. | approx. 3,100 | 638 | | | 2*10^19 | years | 639 | 1 Gbps | 32 | 2^32 = approx. | 2,200 seconds | 640 | | | 4*10^9 | | 641 | 10 Gbps | 32 | 2^32 = approx. | 220 seconds | 642 | | | 4*10^9 | | 643 | 100 Gbps | 32 | 2^32 = approx. | 22 seconds | 644 | | | 4*10^9 | | 645 +-------------+--------------+------------------+-------------------+ 647 Table assumes 64 octet packets 649 Table 1: Proof of transit data sizing 651 If the symmetric masking method for ordered POT is used 652 (Section 3.5), the masks used between nodes adjacent in the path MUST 653 have a length equal to the sum of the ones of RND and CML. 655 5. Node Configuration 657 A POT system consists of a number of nodes that participate in POT 658 and a Controller, which serves as a control and configuration entity. 659 The Controller is to create the required parameters (polynomials, 660 prime number, etc.) and communicate the associated values (i.e. prime 661 number, secret-share, LPC, etc.) to the nodes. The sum of all 662 parameters for a specific node is referred to as "POT-profile". For 663 details see the YANG model in Section 5.2.This document does not 664 define a specific protocol to be used between Controller and nodes. 665 It only defines the procedures and the associated YANG data model. 667 5.1. Procedure 669 The Controller creates new POT-profiles at a constant rate and 670 communicates the POT-profile to the nodes. The controller labels a 671 POT-profile "even" or "odd" and the Controller cycles between "even" 672 and "odd" labeled profiles. This means that the parameters for the 673 algorithms are continuously refreshed. Please refer to Section 4 for 674 choosing an appropriate refresh rate: The rate at which the POT- 675 profiles are communicated to the nodes is configurable and MUST be 676 more frequent than the speed at which a POT-profile is "used up". 677 Once the POT-profile has been successfully communicated to all nodes 678 (e.g., all NETCONF transactions completed, in case NETCONF is used as 679 a protocol), the controller sends an "enable POT-profile" request to 680 the ingress node. 682 All nodes maintain two POT-profiles (an even and an odd POT-profile): 683 One POT-profile is currently active and in use; one profile is 684 standby and about to get used. A flag in the packet is indicating 685 whether the odd or even POT-profile is to be used by a node. This is 686 to ensure that during profile change the service is not disrupted. 687 If the "odd" profile is active, the Controller can communicate the 688 "even" profile to all nodes. Only if all the nodes have received the 689 POT-profile, the Controller will tell the ingress node to switch to 690 the "even" profile. Given that the indicator travels within the 691 packet, all nodes will switch to the "even" profile. The "even" 692 profile gets active on all nodes and nodes are ready to receive a new 693 "odd" profile. 695 Unless the ingress node receives a request to switch profiles, it'll 696 continue to use the active profile. If a profile is "used up" the 697 ingress node will recycle the active profile and start over (this 698 could give rise to replay attacks in theory - but with 2^32 or 2^64 699 packets this isn't really likely in reality). 701 5.2. YANG Model 703 This section defines that YANG data model for the information 704 exchange between the Controller and the nodes. 706 file "ietf-pot-profile@2016-06-15.yang" 707 module ietf-pot-profile { 709 yang-version 1; 710 namespace "urn:ietf:params:xml:ns:yang:ietf-pot-profile"; 712 prefix ietf-pot-profile; 714 organization "IETF xxx Working Group"; 716 contact ""; 718 description "This module contains a collection of YANG 719 definitions for proof of transit configuration 720 parameters. The model is meant for proof of 721 transit and is targeted for communicating the 722 POT-profile between a controller and nodes 723 participating in proof of transit."; 725 revision 2016-06-15 { 726 description 727 "Initial revision."; 728 reference 729 ""; 730 } 732 typedef profile-index-range { 733 type int32 { 734 range "0 .. 1"; 735 } 736 description 737 "Range used for the profile index. Currently restricted to 738 0 or 1 to identify the odd or even profiles."; 739 } 741 grouping pot-profile { 742 description "A grouping for proof of transit profiles."; 743 list pot-profile-list { 744 key "pot-profile-index"; 745 ordered-by user; 746 description "A set of pot profiles."; 748 leaf pot-profile-index { 749 type profile-index-range; 750 mandatory true; 751 description 752 "Proof of transit profile index."; 753 } 755 leaf prime-number { 756 type uint64; 757 mandatory true; 758 description 759 "Prime number used for module math computation"; 760 } 762 leaf secret-share { 763 type uint64; 764 mandatory true; 765 description 766 "Share of the secret of polynomial 1 used in computation"; 767 } 769 leaf public-polynomial { 770 type uint64; 771 mandatory true; 772 description 773 "Pre evaluated Public polynomial"; 774 } 776 leaf lpc { 777 type uint64; 778 mandatory true; 779 description 780 "Lagrange Polynomial Coefficient"; 781 } 783 leaf validator { 784 type boolean; 785 default "false"; 786 description 787 "True if the node is a verifier node"; 788 } 790 leaf validator-key { 791 type uint64; 792 description 793 "Secret key for validating the path, constant of poly 1"; 794 } 796 leaf bitmask { 797 type uint64; 798 default 4294967295; 799 description 800 "Number of bits as mask used in controlling the size of the 801 random value generation. 32-bits of mask is default."; 802 } 803 } 804 } 805 container pot-profiles { 806 description "A group of proof of transit profiles."; 808 list pot-profile-set { 809 key "pot-profile-name"; 810 ordered-by user; 811 description 812 "Set of proof of transit profiles that group parameters 813 required to classify and compute proof of transit 814 metadata at a node"; 816 leaf pot-profile-name { 817 type string; 818 mandatory true; 819 description 820 "Unique identifier for each proof of transit profile"; 821 } 823 leaf active-profile-index { 824 type profile-index-range; 825 description 826 "Proof of transit profile index that is currently active. 827 Will be set in the first hop of the path or chain. 828 Other nodes will not use this field."; 829 } 831 uses pot-profile; 832 } 833 /*** Container: end ***/ 834 } 835 /*** module: end ***/ 836 } 837 839 6. IANA Considerations 841 IANA considerations will be added in a future version of this 842 document. 844 7. Manageability Considerations 846 Manageability considerations will be addressed in a later version of 847 this document. 849 8. Security Considerations 851 POT is a mechanism that is used for verifying the path through which 852 a packet was forwarded. The security considerations of IOAM in 853 general are discussed in [I-D.ietf-ippm-ioam-data]. Specifically, it 854 is assumed that POT is used in a confined network domain, and 855 therefore the potential threats that POT is intended to mitigate 856 should be viewed accordingly. POT prevents spoofing and tampering; 857 an attacker cannot maliciously create a bogus POT or modify a 858 legitimate one. Furthermore, a legitimate node that takes part in 859 the POT protocol cannot masquerade as another node along the path. 860 These considerations are discussed in detail in the rest of this 861 section. 863 8.1. Proof of Transit 865 Proof of correctness and security of the solution approach is per 866 Shamir's Secret Sharing Scheme [SSS]. Cryptographically speaking it 867 achieves information-theoretic security i.e., it cannot be broken by 868 an attacker even with unlimited computing power. As long as the 869 below conditions are met it is impossible for an attacker to bypass 870 one or multiple nodes without getting caught. 872 o If there are k+1 nodes in the path, the polynomials (POLY-1, POLY- 873 2) should be of degree k. Also k+1 points of POLY-1 are chosen 874 and assigned to each node respectively. The verifier can re- 875 construct the k degree polynomial (POLY-3) only when all the 876 points are correctly retrieved. 878 o Precisely three values are kept secret by individual nodes. Share 879 of SECRET (i.e. points on POLY-1), Share of POLY-2, LPC, P. Note 880 that only constant coefficient, RND, of POLY-2 is public. x values 881 and non-constant coefficient of POLY-2 are secret 883 An attacker bypassing a few nodes will miss adding a respective point 884 on POLY-1 to corresponding point on POLY-2 , thus the verifier cannot 885 construct POLY-3 for cross verification. 887 Also it is highly recommended that different polynomials should be 888 used as POLY-1 across different paths, traffic profiles or service 889 chains. 891 If symmetric masking is used to assure OPOT (Section 3.5), the nodes 892 need to keep two additional secrets: the downstream and upstream 893 masks, that have to be managed under the same conditions as the 894 secrets mentioned above. And it is equally recommended to employ a 895 different set of mask pairs across different paths, traffic profiles 896 or service chains. 898 8.2. Cryptanalysis 900 A passive attacker could try to harvest the POT data (i.e., CML, RND 901 values) in order to determine the configured secrets. Subsequently 902 two types of differential analysis for guessing the secrets could be 903 done. 905 o Inter-Node: A passive attacker observing CML values across nodes 906 (i.e., as the packets entering and leaving), cannot perform 907 differential analysis to construct the points on POLY-1. This is 908 because at each point there are four unknowns (i.e. Share(POLY- 909 1), Share(Poly-2) LPC and prime number P) and three known values 910 (i.e. RND, CML-before, CML-after). The application of symmetric 911 masking for OPOT makes inter-node analysis less feasible. 913 o Inter-Packets: A passive attacker could observe CML values across 914 packets (i.e., values of PKT-1 and subsequent PKT-2), in order to 915 predict the secrets. Differential analysis across packets could 916 be mitigated using a good PRNG for generating RND. Note that if 917 constant coefficient is a sequence number than CML values become 918 quite predictable and the scheme would be broken. If symmetric 919 masking is used for OPOT, inter-packet analysis could be applied 920 to guess mask values, which requires a proper refresh rate for 921 masks, at least as high as the one used for LPCs. 923 8.3. Anti-Replay 925 A passive attacker could reuse a set of older RND and the 926 intermediate CML values. Thus, an attacker can attack an old 927 (replayed) RND and CML with a new packet in order to bypass some of 928 the nodes along the path. 930 Such attacks could be avoided by carefully choosing POLY-2 as a 931 (SEQ_NO + RND). For example, if 64 bits are being used for POLY-2 932 then first 16 bits could be a sequence number SEQ_NO and next 48 bits 933 could be a random number. 935 Subsequently, the verifier could use the SEQ_NO bits to run classic 936 anti-replay techniques like sliding window used in IPSEC. The 937 verifier could buffer up to 2^16 packets as a sliding window. 938 Packets arriving with a higher SEQ_NO than current buffer could be 939 flagged legitimate. Packets arriving with a lower SEQ_NO than 940 current buffer could be flagged as suspicious. 942 For all practical purposes in the rest of the document RND means 943 SEQ_NO + RND to keep it simple. 945 The solution discussed in this memo does not currently mitigate 946 replay attacks. An anti-replay mechanism may be included in future 947 versions of the solution. 949 8.4. Anti-Preplay 951 An active attacker could try to perform a man-in-the-middle (MITM) 952 attack by extracting the POT of PKT-1 and using it in PKT-2. 953 Subsequently attacker drops the PKT-1 in order to avoid duplicate POT 954 values reaching the verifier. If the PKT-1 reaches the verifier, 955 then this attack is same as Replay attacks discussed before. 957 Preplay attacks are possible since the POT metadata is not dependent 958 on the packet fields. Below steps are recommended for remediation: 960 o Ingress node and Verifier are configured with common pre shared 961 key 963 o Ingress node generates a Message Authentication Code (MAC) from 964 packet fields using standard HMAC algorithm. 966 o The left most bits of the output are truncated to desired length 967 to generate RND. It is recommended to use a minimum of 32 bits. 969 o The verifier regenerates the HMAC from the packet fields and 970 compares with RND. To ensure the POT data is in fact that of the 971 packet. 973 If an HMAC is used, an active attacker lacks the knowledge of the 974 pre-shared key, and thus cannot launch preplay attacks. 976 The solution discussed in this memo does not currently mitigate 977 preplay attacks. A mitigation mechanism may be included in future 978 versions of the solution. 980 8.5. Tampering 982 An active attacker could not insert any arbitrary value for CML. 983 This would subsequently fail the reconstruction of the POLY-3. Also 984 an attacker could not update the CML with a previously observed 985 value. This could subsequently be detected by using timestamps 986 within the RND value as discussed above. 988 8.6. Recycling 990 The solution approach is flexible for recycling long term secrets 991 like POLY-1. All the nodes could be periodically updated with shares 992 of new SECRET as best practice. The table above could be consulted 993 for refresh cycles (see Section 4). 995 If symmetric masking is used for OPOT (Section 3.5), mask values must 996 be periodically updated as well, at least as frequently as the other 997 secrets are. 999 8.7. Redundant Nodes and Failover 1001 A "node" or "service" in terms of POT can be implemented by one or 1002 multiple physical entities. In case of multiple physical entities 1003 (e.g., for load-balancing, or business continuity situations - 1004 consider for example a set of firewalls), all physical entities which 1005 are implementing the same POT node are given that same share of the 1006 secret. This makes multiple physical entities represent the same POT 1007 node from an algorithm perspective. 1009 8.8. Controller Operation 1011 The Controller needs to be secured given that it creates and holds 1012 the secrets, as need to be the nodes. The communication between 1013 Controller and the nodes also needs to be secured. As secure 1014 communication protocol such as for example NETCONF over SSH should be 1015 chosen for Controller to node communication. 1017 The Controller only interacts with the nodes during the initial 1018 configuration and thereafter at regular intervals at which the 1019 operator chooses to switch to a new set of secrets. In case 64 bits 1020 are used for the data fields "CML" and "RND" which are carried within 1021 the data packet, the regular intervals are expected to be quite long 1022 (e.g., at 100 Gbps, a profile would only be used up after 3100 years) 1023 - see Section 4 above, thus even a "headless" operation without a 1024 Controller can be considered feasible. In such a case, the 1025 Controller would only be used for the initial configuration of the 1026 POT-profiles. 1028 If OPOT (Section 3.5) is applied using symmetric masking, the 1029 Controller will be required to perform a a periodic refresh of the 1030 mask pairs. The use of OPOT SHOULD be configurable as part of the 1031 required level of assurance through the Controller management 1032 interface. 1034 8.9. Verification Scope 1036 The POT solution defined in this document verifies that a data-packet 1037 traversed or transited a specific set of nodes. From an algorithm 1038 perspective, a "node" is an abstract entity. It could be represented 1039 by one or multiple physical or virtual network devices, or is could 1040 be a component within a networking device or system. The latter 1041 would be the case if a forwarding path within a device would need to 1042 be securely verified. 1044 8.9.1. Node Ordering 1046 POT using Shamir's secret sharing scheme as discussed in this 1047 document provides for a means to verify that a set of nodes has been 1048 visited by a data packet. It does not verify the order in which the 1049 data packet visited the nodes. 1051 In case the order in which a data packet traversed a particular set 1052 of nodes needs to be verified as well, the alternate schemes related 1053 to OPOT (Section 3.5) have to be considered. Since these schemes 1054 introduce at least additional control requirements, the selection of 1055 order verification SHOULD be configurable the Controller management 1056 interface. 1058 8.9.2. Stealth Nodes 1060 The POT approach discussed in this document is to prove that a data 1061 packet traversed a specific set of "nodes". This set could be all 1062 nodes within a path, but could also be a subset of nodes in a path. 1063 Consequently, the POT approach isn't suited to detect whether 1064 "stealth" nodes which do not participate in proof-of-transit have 1065 been inserted into a path. 1067 9. Acknowledgements 1069 The authors would like to thank Eric Vyncke, Nalini Elkins, Srihari 1070 Raghavan, Ranganathan T S, Karthik Babu Harichandra Babu, Akshaya 1071 Nadahalli, Erik Nordmark, and Andrew Yourtchenko for the comments and 1072 advice. 1074 10. References 1076 10.1. Normative References 1078 [I-D.ietf-ippm-ioam-data] 1079 Brockners, F., Bhandari, S., Pignataro, C., Gredler, H., 1080 Leddy, J., Youell, S., Mizrahi, T., Mozes, D., Lapukhov, 1081 P., Chang, R., daniel.bernier@bell.ca, d., and J. Lemon, 1082 "Data Fields for In-situ OAM", draft-ietf-ippm-ioam- 1083 data-04 (work in progress), October 2018. 1085 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1086 Requirement Levels", BCP 14, RFC 2119, 1087 DOI 10.17487/RFC2119, March 1997, . 1090 [RFC7665] Halpern, J., Ed. and C. Pignataro, Ed., "Service Function 1091 Chaining (SFC) Architecture", RFC 7665, 1092 DOI 10.17487/RFC7665, October 2015, . 1095 [SSS] "Shamir's Secret Sharing", . 1098 10.2. Informative References 1100 [I-D.ietf-anima-autonomic-control-plane] 1101 Eckert, T., Behringer, M., and S. Bjarnason, "An Autonomic 1102 Control Plane (ACP)", draft-ietf-anima-autonomic-control- 1103 plane-18 (work in progress), August 2018. 1105 Authors' Addresses 1107 Frank Brockners 1108 Cisco Systems, Inc. 1109 Hansaallee 249, 3rd Floor 1110 DUESSELDORF, NORDRHEIN-WESTFALEN 40549 1111 Germany 1113 Email: fbrockne@cisco.com 1115 Shwetha Bhandari 1116 Cisco Systems, Inc. 1117 Cessna Business Park, Sarjapura Marathalli Outer Ring Road 1118 Bangalore, KARNATAKA 560 087 1119 India 1121 Email: shwethab@cisco.com 1123 Sashank Dara 1124 Seconize 1125 BANGALORE, Bangalore, KARNATAKA 1126 INDIA 1128 Email: sashank@seconize.co 1129 Carlos Pignataro 1130 Cisco Systems, Inc. 1131 7200-11 Kit Creek Road 1132 Research Triangle Park, NC 27709 1133 United States 1135 Email: cpignata@cisco.com 1137 John Leddy 1138 Comcast 1140 Email: John_Leddy@cable.comcast.com 1142 Stephen Youell 1143 JP Morgan Chase 1144 25 Bank Street 1145 London E14 5JP 1146 United Kingdom 1148 Email: stephen.youell@jpmorgan.com 1150 David Mozes 1152 Email: mosesster@gmail.com 1154 Tal Mizrahi 1155 Huawei Network.IO Innovation Lab 1156 Israel 1158 Email: tal.mizrahi.phd@gmail.com 1160 Alejandro Aguado 1161 Universidad Politecnica de Madrid 1162 Campus Montegancedo, Boadilla del Monte 1163 Madrid 28660 1164 Spain 1166 Phone: +34 910 673 086 1167 Email: a.aguadom@fi.upm.es 1168 Diego R. Lopez 1169 Telefonica I+D 1170 Editor Jose Manuel Lara, 9 (1-B) 1171 Seville 41013 1172 Spain 1174 Phone: +34 913 129 041 1175 Email: diego.r.lopez@telefonica.com