idnits 2.17.1 draft-ietf-sfc-proof-of-transit-00.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 (May 31, 2018) is 2150 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Outdated reference: A later version (-30) exists of draft-ietf-anima-autonomic-control-plane-03 Summary: 0 errors (**), 0 flaws (~~), 2 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 S. Dara 5 Expires: December 2, 2018 C. Pignataro 6 Cisco 7 J. Leddy 8 Comcast 9 S. Youell 10 JPMC 11 D. Mozes 13 T. Mizrahi 14 Marvell 15 May 31, 2018 17 Proof of Transit 18 draft-ietf-sfc-proof-of-transit-00 20 Abstract 22 Several technologies such as Traffic Engineering (TE), Service 23 Function Chaining (SFC), and policy based routing are used to steer 24 traffic through a specific, user-defined path. This document defines 25 mechanisms to securely prove that traffic transited said defined 26 path. These mechanisms allow to securely verify whether, within a 27 given path, all packets traversed all the nodes that they are 28 supposed to visit. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on December 2, 2018. 47 Copyright Notice 49 Copyright (c) 2018 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 3. Proof of Transit . . . . . . . . . . . . . . . . . . . . . . 5 67 3.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . 5 68 3.2. Solution Approach . . . . . . . . . . . . . . . . . . . . 6 69 3.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 7 70 3.2.2. In Transit . . . . . . . . . . . . . . . . . . . . . 7 71 3.2.3. Verification . . . . . . . . . . . . . . . . . . . . 7 72 3.3. Illustrative Example . . . . . . . . . . . . . . . . . . 7 73 3.3.1. Basic Version . . . . . . . . . . . . . . . . . . . . 7 74 3.3.1.1. Secret Shares . . . . . . . . . . . . . . . . . . 8 75 3.3.1.2. Lagrange Polynomials . . . . . . . . . . . . . . 8 76 3.3.1.3. LPC Computation . . . . . . . . . . . . . . . . . 8 77 3.3.1.4. Reconstruction . . . . . . . . . . . . . . . . . 9 78 3.3.1.5. Verification . . . . . . . . . . . . . . . . . . 9 79 3.3.2. Enhanced Version . . . . . . . . . . . . . . . . . . 9 80 3.3.2.1. Random Polynomial . . . . . . . . . . . . . . . . 9 81 3.3.2.2. Reconstruction . . . . . . . . . . . . . . . . . 10 82 3.3.2.3. Verification . . . . . . . . . . . . . . . . . . 10 83 3.3.3. Final Version . . . . . . . . . . . . . . . . . . . . 11 84 3.4. Operational Aspects . . . . . . . . . . . . . . . . . . . 11 85 3.5. Alternative Approach . . . . . . . . . . . . . . . . . . 12 86 3.5.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . 12 87 3.5.2. Pros . . . . . . . . . . . . . . . . . . . . . . . . 12 88 3.5.3. Cons . . . . . . . . . . . . . . . . . . . . . . . . 12 89 4. Sizing the Data for Proof of Transit . . . . . . . . . . . . 12 90 5. Node Configuration . . . . . . . . . . . . . . . . . . . . . 13 91 5.1. Procedure . . . . . . . . . . . . . . . . . . . . . . . . 14 92 5.2. YANG Model . . . . . . . . . . . . . . . . . . . . . . . 14 93 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 94 7. Manageability Considerations . . . . . . . . . . . . . . . . 17 95 8. Security Considerations . . . . . . . . . . . . . . . . . . . 17 96 8.1. Proof of Transit . . . . . . . . . . . . . . . . . . . . 18 97 8.2. Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . 18 98 8.3. Anti-Replay . . . . . . . . . . . . . . . . . . . . . . . 19 99 8.4. Anti-Preplay . . . . . . . . . . . . . . . . . . . . . . 19 100 8.5. Anti-Tampering . . . . . . . . . . . . . . . . . . . . . 20 101 8.6. Recycling . . . . . . . . . . . . . . . . . . . . . . . . 20 102 8.7. Redundant Nodes and Failover . . . . . . . . . . . . . . 20 103 8.8. Controller Operation . . . . . . . . . . . . . . . . . . 20 104 8.9. Verification Scope . . . . . . . . . . . . . . . . . . . 21 105 8.9.1. Node Ordering . . . . . . . . . . . . . . . . . . . . 21 106 8.9.2. Stealth Nodes . . . . . . . . . . . . . . . . . . . . 21 107 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21 108 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 21 109 10.1. Normative References . . . . . . . . . . . . . . . . . . 21 110 10.2. Informative References . . . . . . . . . . . . . . . . . 22 111 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 113 1. Introduction 115 Several deployments use Traffic Engineering, policy routing, Segment 116 Routing (SR), and Service Function Chaining (SFC) [RFC7665] to steer 117 packets through a specific set of nodes. In certain cases, 118 regulatory obligations or a compliance policy require operators to 119 prove that all packets that are supposed to follow a specific path 120 are indeed being forwarded across and exact set of pre-determined 121 nodes. 123 If a packet flow is supposed to go through a series of service 124 functions or network nodes, it has to be proven that indeed all 125 packets of the flow followed the path or service chain or collection 126 of nodes specified by the policy. In case some packets of a flow 127 weren't appropriately processed, a verification device should 128 determine the policy violation and take corresponding actions 129 corresponding to the policy (e.g., drop or redirect the packet, send 130 an alert etc.) In today's deployments, the proof that a packet 131 traversed a particular path or service chain is typically delivered 132 in an indirect way: Service appliances and network forwarding are in 133 different trust domains. Physical hand-off-points are defined 134 between these trust domains (i.e. physical interfaces). Or in other 135 terms, in the "network forwarding domain" things are wired up in a 136 way that traffic is delivered to the ingress interface of a service 137 appliance and received back from an egress interface of a service 138 appliance. This "wiring" is verified and then trusted upon. The 139 evolution to Network Function Virtualization (NFV) and modern service 140 chaining concepts (using technologies such as Locator/ID Separation 141 Protocol (LISP), Network Service Header (NSH), Segment Routing (SR), 142 etc.) blurs the line between the different trust domains, because the 143 hand-off-points are no longer clearly defined physical interfaces, 144 but are virtual interfaces. As a consequence, different trust layers 145 should not to be mixed in the same device. For an NFV scenario a 146 different type of proof is required. Offering a proof that a packet 147 indeed traversed a specific set of service functions or nodes allows 148 operators to evolve from the above described indirect methods of 149 proving that packets visit a predetermined set of nodes. 151 The solution approach presented in this document is based on a small 152 portion of operational data added to every packet. This "in-situ" 153 operational data is also referred to as "proof of transit data", or 154 POT data. The POT data is updated at every required node and is used 155 to verify whether a packet traversed all required nodes. A 156 particular set of nodes "to be verified" is either described by a set 157 of secret keys, or a set of shares of a single secret. Nodes on the 158 path retrieve their individual keys or shares of a key (using for 159 e.g., Shamir's Secret Sharing scheme) from a central controller. The 160 complete key set is only known to the controller and a verifier node, 161 which is typically the ultimate node on a path that performs 162 verification. Each node in the path uses its secret or share of the 163 secret to update the POT data of the packets as the packets pass 164 through the node. When the verifier receives a packet, it uses its 165 key(s) along with data found in the packet to validate whether the 166 packet traversed the path correctly. 168 2. Conventions 170 Abbreviations used in this document: 172 HMAC: Hash based Message Authentication Code. For example, 173 HMAC-SHA256 generates 256 bits of MAC 175 IOAM: In-situ Operations, Administration, and Maintenance 177 LISP: Locator/ID Separation Protocol 179 LPC: Lagrange Polynomial Constants 181 MTU: Maximum Transmit Unit 183 NFV: Network Function Virtualization 185 NSH: Network Service Header 187 POT: Proof of Transit 189 POT-profile: Proof of Transit Profile that has the necessary data 190 for nodes to participate in proof of transit 192 RND: Random Bits generated per packet. Packet fields that 193 donot change during the traversal are given as input to 194 HMAC-256 algorithm. A minimum of 32 bits (left most) need 195 to be used from the output if RND is used to verify the 196 packet integrity. This is a standard recommendation by 197 NIST. 199 SEQ_NO: Sequence number initialized to a predefined constant. 200 This is used in concatenation with RND bits to mitigate 201 different attacks discussed later. 203 SFC: Service Function Chain 205 SR: Segment Routing 207 3. Proof of Transit 209 This section discusses methods and algorithms to provide for a "proof 210 of transit" for packets traversing a specific path. A path which is 211 to be verified consists of a set of nodes. Transit of the data 212 packets through those nodes is to be proven. Besides the nodes, the 213 setup also includes a Controller that creates secrets and secrets 214 shares and configures the nodes for POT operations. 216 The methods how traffic is identified and associated to a specific 217 path is outside the scope of this document. Identification could be 218 done using a filter (e.g., 5-tuple classifier), or an identifier 219 which is already present in the packet (e.g., path or service 220 identifier, NSH Service Path Identifier (SPI), flow-label, etc.) 222 The solution approach is detailed in two steps. Initially the 223 concept of the approach is explained. This concept is then further 224 refined to make it operationally feasible. 226 3.1. Basic Idea 228 The method relies on adding POT data to all packets that traverse a 229 path. The added POT data allows a verifying node (egress node) to 230 check whether a packet traversed the identified set of nodes on a 231 path correctly or not. Security mechanisms are natively built into 232 the generation of the POT data to protect against misuse (i.e. 233 configuration mistakes, malicious administrators playing tricks with 234 routing, capturing, spoofing and replaying packets). The mechanism 235 for POT leverages "Shamir's Secret Sharing" scheme [SSS]. 237 Shamir's secret sharing base idea: A polynomial (represented by its 238 coefficients) is chosen as a secret by the controller. A polynomial 239 represents a curve. A set of well-defined points on the curve are 240 needed to construct the polynomial. Each point of the polynomial is 241 called "share" of the secret. A single secret is associated with a 242 particular set of nodes, which typically represent the path, to be 243 verified. Shares of the single secret (i.e., points on the curve) 244 are securely distributed from a Controller to the network nodes. 245 Nodes use their respective share to update a cumulative value in the 246 POT data of each packet. Only a verifying node has access to the 247 complete secret. The verifying node validates the correctness of the 248 received POT data by reconstructing the curve. 250 The polynomial cannot be constructed if any of the points are missed 251 or tampered. Per Shamir's Secret Sharing Scheme, any lesser points 252 means one or more nodes are missed. Details of the precise 253 configuration needed for achieving security are discussed further 254 below. 256 While applicable in theory, a vanilla approach based on Shamir's 257 secret sharing could be easily attacked. If the same polynomial is 258 reused for every packet for a path a passive attacker could reuse the 259 value. As a consequence, one could consider creating a different 260 polynomial per packet. Such an approach would be operationally 261 complex. It would be complex to configure and recycle so many curves 262 and their respective points for each node. Rather than using a 263 single polynomial, two polynomials are used for the solution 264 approach: A secret polynomial which is kept constant, and a per- 265 packet polynomial which is public. Operations are performed on the 266 sum of those two polynomials - creating a third polynomial which is 267 secret and per packet. 269 3.2. Solution Approach 271 Solution approach: The overall algorithm uses two polynomials: POLY-1 272 and POLY-2. POLY-1 is secret and constant. Each node gets a point 273 on POLY-1 at setup-time and keeps it secret. POLY-2 is public, 274 random and per packet. Each node generates a point on POLY-2 each 275 time a packet crosses it. Each node then calculates (point on POLY-1 276 + point on POLY-2) to get a (point on POLY-3) and passes it to 277 verifier by adding it to each packet. The verifier constructs POLY-3 278 from the points given by all the nodes and cross checks whether 279 POLY-3 = POLY-1 + POLY-2. Only the verifier knows POLY-1. The 280 solution leverages finite field arithmetic in a field of size "prime 281 number". 283 Detailed algorithms are discussed next. A simple example is 284 discussed in Section 3.3. 286 3.2.1. Setup 288 A controller generates a first polynomial (POLY-1) of degree k and 289 k+1 points on the polynomial. The constant coefficient of POLY-1 is 290 considered the SECRET. The non-constant coefficients are used to 291 generate the Lagrange Polynomial Constants (LPC). Each of the k 292 nodes (including verifier) are assigned a point on the polynomial 293 i.e., shares of the SECRET. The verifier is configured with the 294 SECRET. The Controller also generates coefficients (except the 295 constant coefficient, called "RND", which is changed on a per packet 296 basis) of a second polynomial POLY-2 of the same degree. Each node 297 is configured with the LPC of POLY-2. Note that POLY-2 is public. 299 3.2.2. In Transit 301 For each packet, the ingress node generates a random number (RND). 302 It is considered as the constant coefficient for POLY-2. A 303 cumulative value (CML) is initialized to 0. Both RND, CML are 304 carried as within the packet POT data. As the packet visits each 305 node, the RND is retrieved from the packet and the respective share 306 of POLY-2 is calculated. Each node calculates (Share(POLY-1) + 307 Share(POLY-2)) and CML is updated with this sum. This step is 308 performed by each node until the packet completes the path. The 309 verifier also performs the step with its respective share. 311 3.2.3. Verification 313 The verifier cross checks whether CML = SECRET + RND. If this 314 matches then the packet traversed the specified set of nodes in the 315 path. This is due to the additive homomorphic property of Shamir's 316 Secret Sharing scheme. 318 3.3. Illustrative Example 320 This section shows a simple example to illustrate step by step the 321 approach described above. 323 3.3.1. Basic Version 325 Assumption: It is to be verified whether packets passed through 3 326 nodes. A polynomial of degree 2 is chosen for verification. 328 Choices: Prime = 53. POLY-1(x) = (3x^2 + 3x + 10) mod 53. The 329 secret to be re-constructed is the constant coefficient of POLY-1, 330 i.e., SECRET=10. It is important to note that all operations are 331 done over a finite field (i.e., modulo prime). 333 3.3.1.1. Secret Shares 335 The shares of the secret are the points on POLY-1 chosen for the 3 336 nodes. For example, let x0=2, x1=4, x2=5. 338 POLY-1(2) = 28 => (x0, y0) = (2, 28) 340 POLY-1(4) = 17 => (x1, y1) = (4, 17) 342 POLY-1(5) = 47 => (x2, y2) = (5, 47) 344 The three points above are the points on the curve which are 345 considered the shares of the secret. They are assigned to three 346 nodes respectively and are kept secret. 348 3.3.1.2. Lagrange Polynomials 350 Lagrange basis polynomials (or Lagrange polynomials) are used for 351 polynomial interpolation. For a given set of points on the curve 352 Lagrange polynomials (as defined below) are used to reconstruct the 353 curve and thus reconstruct the complete secret. 355 l0(x) = (((x-x1) / (x0-x1)) * ((x-x2)/x0-x2))) mod 53 = 356 (((x-4) / (2-4)) * ((x-5)/2-5))) mod 53 = 357 (10/3 - 3x/2 + (1/6)x^2) mod 53 359 l1(x) = (((x-x0) / (x1-x0)) * ((x-x2)/x1-x2))) mod 53 = 360 (-5 + 7x/2 - (1/2)x^2) mod 53 362 l2(x) = (((x-x0) / (x2-x0)) * ((x-x1)/x2-x1))) mod 53 = 363 (8/3 - 2 + (1/3)x^2) mod 53 365 3.3.1.3. LPC Computation 367 Since x0=2, x1=4, x2=5 are chosen points. Given that computations 368 are done over a finite arithmetic field ("modulo a prime number"), 369 the Lagrange basis polynomial constants are computed modulo 53. The 370 Lagrange Polynomial Constant (LPC) would be 10/3 , -5 , 8/3. 372 LPC(x0) = (10/3) mod 53 = 21 374 LPC(x1) = (-5) mod 53 = 48 376 LPC(x2) = (8/3) mod 53 = 38 378 For a general way to compute the modular multiplicative inverse, see 379 e.g., the Euclidean algorithm. 381 3.3.1.4. Reconstruction 383 Reconstruction of the polynomial is well-defined as 385 POLY1(x) = l0(x) * y0 + l1(x) * y1 + l2(x) * y2 387 Subsequently, the SECRET, which is the constant coefficient of 388 POLY1(x) can be computed as below 390 SECRET = (y0*LPC(l0)+y1*LPC(l1)+y2*LPC(l2)) mod 53 392 The secret can be easily reconstructed using the y-values and the 393 LPC: 395 SECRET = (y0*LPC(l0) + y1*LPC(l1) + y2*LPC(l2)) mod 53 = mod (28 * 21 396 + 17 * 48 + 47 * 38) mod 53 = 3190 mod 53 = 10 398 One observes that the secret reconstruction can easily be performed 399 cumulatively hop by hop. CML represents the cumulative value. It is 400 the POT data in the packet that is updated at each hop with the 401 node's respective (yi*LPC(i)), where i is their respective value. 403 3.3.1.5. Verification 405 Upon completion of the path, the resulting CML is retrieved by the 406 verifier from the packet POT data. Recall that verifier is 407 preconfigured with the original SECRET. It is cross checked with the 408 CML by the verifier. Subsequent actions based on the verification 409 failing or succeeding could be taken as per the configured policies. 411 3.3.2. Enhanced Version 413 As observed previously, the vanilla algorithm that involves a single 414 secret polynomial is not secure. Therefore, the solution is further 415 enhanced with usage of a random second polynomial chosen per packet. 417 3.3.2.1. Random Polynomial 419 Let the second polynomial POLY-2 be (RND + 7x + 10 x^2). RND is a 420 random number and is generated for each packet. Note that POLY-2 is 421 public and need not be kept secret. The nodes can be pre-configured 422 with the non-constant coefficients (for example, 7 and 10 in this 423 case could be configured through the Controller on each node). So 424 precisely only RND value changes per packet and is public and the 425 rest of the non-constant coefficients of POLY-2 kept secret. 427 3.3.2.2. Reconstruction 429 Recall that each node is preconfigured with their respective 430 Share(POLY-1). Each node calculates its respective Share(POLY-2) 431 using the RND value retrieved from the packet. The CML 432 reconstruction is enhanced as below. At every node, CML is updated 433 as 435 CML = CML+(((Share(POLY-1)+ Share(POLY-2)) * LPC) mod Prime 437 Let us observe the packet level transformations in detail. For the 438 example packet here, let the value RND be 45. Thus POLY-2 would be 439 (45 + 7x + 10x^2). 441 The shares that could be generated are (2, 46), (4, 21), (5, 12). 443 At ingress: The fields RND = 45. CML = 0. 445 At node-1 (x0): Respective share of POLY-2 is generated i.e., (2, 446 46) because share index of node-1 is 2. 448 CML = 0 + ((28 + 46)* 21) mod 53 = 17 450 At node-2 (x1): Respective share of POLY-2 is generated i.e., (4, 451 21) because share index of node-2 is 4. 453 CML = 17 + ((17 + 21)*48) mod 53 = 17 + 22 = 39 455 At node-3 (x2), which is also the verifier: The respective share 456 of POLY-2 is generated i.e., (5, 12) because the share index of 457 the verifier is 12. 459 CML = 39 + ((47 + 12)*38) mod 53 = 39 + 16 = 55 mod 53 = 2 461 The verification using CML is discussed in next section. 463 3.3.2.3. Verification 465 As shown in the above example, for final verification, the verifier 466 compares: 468 VERIFY = (SECRET + RND) mod Prime, with Prime = 53 here 470 VERIFY = (RND-1 + RND-2) mod Prime = ( 10 + 45 ) mod 53 = 2 472 Since VERIFY = CML the packet is proven to have gone through nodes 1, 473 2, and 3. 475 3.3.3. Final Version 477 The enhanced version of the protocol is still prone to replay and 478 preplay attacks. An attacker could reuse the POT metadata for 479 bypassing the verification. So additional measures using packet 480 integrity checks (HMAC) and sequence numbers (SEQ_NO) are discussed 481 later "Security Considerations" section. 483 3.4. Operational Aspects 485 To operationalize this scheme, a central controller is used to 486 generate the necessary polynomials, the secret share per node, the 487 prime number, etc. and distributing the data to the nodes 488 participating in proof of transit. The identified node that performs 489 the verification is provided with the verification key. The 490 information provided from the Controller to each of the nodes 491 participating in proof of transit is referred to as a proof of 492 transit profile (POT-profile). Also note that the set of nodes for 493 which the transit has to be proven are typically associated to a 494 different trust domain than the verifier. Note that building the 495 trust relationship between the Controller and the nodes is outside 496 the scope of this document. Techniques such as those described in 497 [I-D.ietf-anima-autonomic-control-plane] might be applied. 499 To optimize the overall data amount of exchanged and the processing 500 at the nodes the following optimizations are performed: 502 1. The points (x, y) for each of the nodes on the public and private 503 polynomials are picked such that the x component of the points 504 match. This lends to the LPC values which are used to calculate 505 the cumulative value CML to be constant. Note that the LPC are 506 only depending on the x components. They can be computed at the 507 controller and communicated to the nodes. Otherwise, one would 508 need to distributed the x components to all the nodes. 510 2. A pre-evaluated portion of the public polynomial for each of the 511 nodes is calculated and added to the POT-profile. Without this 512 all the coefficients of the public polynomial had to be added to 513 the POT profile and each node had to evaluate them. As stated 514 before, the public portion is only the constant coefficient RND 515 value, the pre-evaluated portion for each node should be kept 516 secret as well. 518 3. To provide flexibility on the size of the cumulative and random 519 numbers carried in the POT data a field to indicate this is 520 shared and interpreted at the nodes. 522 3.5. Alternative Approach 524 In certain scenarios preserving the order of the nodes traversed by 525 the packet may be needed. An alternative, "nested encryption" based 526 approach is described here for preserving the order 528 3.5.1. Basic Idea 530 1. The controller provisions all the nodes with their respective 531 secret keys. 533 2. The controller provisions the verifier with all the secret keys 534 of the nodes. 536 3. For each packet, the ingress node generates a random number RND 537 and encrypts it with its secret key to generate CML value 539 4. Each subsequent node on the path encrypts CML with their 540 respective secret key and passes it along 542 5. The verifier is also provisioned with the expected sequence of 543 nodes in order to verify the order 545 6. The verifier receives the CML, RND values, re-encrypts the RND 546 with keys in the same order as expected sequence to verify. 548 3.5.2. Pros 550 Nested encryption approach retains the order in which the nodes are 551 traversed. 553 3.5.3. Cons 555 1. Standard AES encryption would need 128 bits of RND, CML. This 556 results in a 256 bits of additional overhead is added per packet 558 2. In hardware platforms that do not support native encryption 559 capabilities like (AES-NI). This approach would have 560 considerable impact on the computational latency 562 4. Sizing the Data for Proof of Transit 564 Proof of transit requires transport of two data fields in every 565 packet that should be verified: 567 1. RND: Random number (the constant coefficient of public 568 polynomial) 570 2. CML: Cumulative 572 The size of the data fields determines how often a new set of 573 polynomials would need to be created. At maximum, the largest RND 574 number that can be represented with a given number of bits determines 575 the number of unique polynomials POLY-2 that can be created. The 576 table below shows the maximum interval for how long a single set of 577 polynomials could last for a variety of bit rates and RND sizes: When 578 choosing 64 bits for RND and CML data fields, the time between a 579 renewal of secrets could be as long as 3,100 years, even when running 580 at 100 Gbps. 582 +-------------+--------------+------------------+-------------------+ 583 | Transfer | Secret/RND | Max # of packets | Time RND lasts | 584 | rate | size | | | 585 +-------------+--------------+------------------+-------------------+ 586 | 1 Gbps | 64 | 2^64 = approx. | approx. 310,000 | 587 | | | 2*10^19 | years | 588 | 10 Gbps | 64 | 2^64 = approx. | approx. 31,000 | 589 | | | 2*10^19 | years | 590 | 100 Gbps | 64 | 2^64 = approx. | approx. 3,100 | 591 | | | 2*10^19 | years | 592 | 1 Gbps | 32 | 2^32 = approx. | 2,200 seconds | 593 | | | 4*10^9 | | 594 | 10 Gbps | 32 | 2^32 = approx. | 220 seconds | 595 | | | 4*10^9 | | 596 | 100 Gbps | 32 | 2^32 = approx. | 22 seconds | 597 | | | 4*10^9 | | 598 +-------------+--------------+------------------+-------------------+ 600 Table assumes 64 octet packets 602 Table 1: Proof of transit data sizing 604 5. Node Configuration 606 A POT system consists of a number of nodes that participate in POT 607 and a Controller, which serves as a control and configuration entity. 608 The Controller is to create the required parameters (polynomials, 609 prime number, etc.) and communicate those to the nodes. The sum of 610 all parameters for a specific node is referred to as "POT-profile". 611 This document does not define a specific protocol to be used between 612 Controller and nodes. It only defines the procedures and the 613 associated YANG data model. 615 5.1. Procedure 617 The Controller creates new POT-profiles at a constant rate and 618 communicates the POT-profile to the nodes. The controller labels a 619 POT-profile "even" or "odd" and the Controller cycles between "even" 620 and "odd" labeled profiles. The rate at which the POT-profiles are 621 communicated to the nodes is configurable and is more frequent than 622 the speed at which a POT-profile is "used up" (see table above). 623 Once the POT-profile has been successfully communicated to all nodes 624 (e.g., all NETCONF transactions completed, in case NETCONF is used as 625 a protocol), the controller sends an "enable POT-profile" request to 626 the ingress node. 628 All nodes maintain two POT-profiles (an even and an odd POT-profile): 629 One POT-profile is currently active and in use; one profile is 630 standby and about to get used. A flag in the packet is indicating 631 whether the odd or even POT-profile is to be used by a node. This is 632 to ensure that during profile change the service is not disrupted. 633 If the "odd" profile is active, the Controller can communicate the 634 "even" profile to all nodes. Only if all the nodes have received the 635 POT-profile, the Controller will tell the ingress node to switch to 636 the "even" profile. Given that the indicator travels within the 637 packet, all nodes will switch to the "even" profile. The "even" 638 profile gets active on all nodes and nodes are ready to receive a new 639 "odd" profile. 641 Unless the ingress node receives a request to switch profiles, it'll 642 continue to use the active profile. If a profile is "used up" the 643 ingress node will recycle the active profile and start over (this 644 could give rise to replay attacks in theory - but with 2^32 or 2^64 645 packets this isn't really likely in reality). 647 5.2. YANG Model 649 This section defines that YANG data model for the information 650 exchange between the Controller and the nodes. 652 file "ietf-pot-profile@2016-06-15.yang" 653 module ietf-pot-profile { 655 yang-version 1; 657 namespace "urn:ietf:params:xml:ns:yang:ietf-pot-profile"; 659 prefix ietf-pot-profile; 661 organization "IETF xxx Working Group"; 662 contact ""; 664 description "This module contains a collection of YANG 665 definitions for proof of transit configuration 666 parameters. The model is meant for proof of 667 transit and is targeted for communicating the 668 POT-profile between a controller and nodes 669 participating in proof of transit."; 671 revision 2016-06-15 { 672 description 673 "Initial revision."; 674 reference 675 ""; 676 } 678 typedef profile-index-range { 679 type int32 { 680 range "0 .. 1"; 681 } 682 description 683 "Range used for the profile index. Currently restricted to 684 0 or 1 to identify the odd or even profiles."; 685 } 687 grouping pot-profile { 688 description "A grouping for proof of transit profiles."; 689 list pot-profile-list { 690 key "pot-profile-index"; 691 ordered-by user; 692 description "A set of pot profiles."; 694 leaf pot-profile-index { 695 type profile-index-range; 696 mandatory true; 697 description 698 "Proof of transit profile index."; 699 } 701 leaf prime-number { 702 type uint64; 703 mandatory true; 704 description 705 "Prime number used for module math computation"; 706 } 708 leaf secret-share { 709 type uint64; 710 mandatory true; 711 description 712 "Share of the secret of polynomial 1 used in computation"; 713 } 715 leaf public-polynomial { 716 type uint64; 717 mandatory true; 718 description 719 "Pre evaluated Public polynomial"; 720 } 722 leaf lpc { 723 type uint64; 724 mandatory true; 725 description 726 "Lagrange Polynomial Coefficient"; 727 } 729 leaf validator { 730 type boolean; 731 default "false"; 732 description 733 "True if the node is a verifier node"; 734 } 736 leaf validator-key { 737 type uint64; 738 description 739 "Secret key for validating the path, constant of poly 1"; 740 } 742 leaf bitmask { 743 type uint64; 744 default 4294967295; 745 description 746 "Number of bits as mask used in controlling the size of the 747 random value generation. 32-bits of mask is default."; 748 } 749 } 750 } 752 container pot-profiles { 753 description "A group of proof of transit profiles."; 755 list pot-profile-set { 756 key "pot-profile-name"; 757 ordered-by user; 758 description 759 "Set of proof of transit profiles that group parameters 760 required to classify and compute proof of transit 761 metadata at a node"; 763 leaf pot-profile-name { 764 type string; 765 mandatory true; 766 description 767 "Unique identifier for each proof of transit profile"; 768 } 770 leaf active-profile-index { 771 type profile-index-range; 772 description 773 "Proof of transit profile index that is currently active. 774 Will be set in the first hop of the path or chain. 775 Other nodes will not use this field."; 776 } 778 uses pot-profile; 779 } 780 /*** Container: end ***/ 781 } 782 /*** module: end ***/ 783 } 784 786 6. IANA Considerations 788 IANA considerations will be added in a future version of this 789 document. 791 7. Manageability Considerations 793 Manageability considerations will be addressed in a later version of 794 this document. 796 8. Security Considerations 798 Different security requirements achieved by the solution approach are 799 discussed here. 801 8.1. Proof of Transit 803 Proof of correctness and security of the solution approach is per 804 Shamir's Secret Sharing Scheme [SSS]. Cryptographically speaking it 805 achieves information-theoretic security i.e., it cannot be broken by 806 an attacker even with unlimited computing power. As long as the 807 below conditions are met it is impossible for an attacker to bypass 808 one or multiple nodes without getting caught. 810 o If there are k+1 nodes in the path, the polynomials (POLY-1, POLY- 811 2) should be of degree k. Also k+1 points of POLY-1 are chosen 812 and assigned to each node respectively. The verifier can re- 813 construct the k degree polynomial (POLY-3) only when all the 814 points are correctly retrieved. 816 o Precisely three values are kept secret by individual nodes. Share 817 of SECRET (i.e. points on POLY-1), Share of POLY-2, LPC, P. Note 818 that only constant coefficient, RND, of POLY-2 is public. x values 819 and non-constant coefficient of POLY-2 are secret 821 An attacker bypassing a few nodes will miss adding a respective point 822 on POLY-1 to corresponding point on POLY-2 , thus the verifier cannot 823 construct POLY-3 for cross verification. 825 Also it is highly recommended that different polynomials should be 826 used as POLY-1 across different paths, traffic profiles or service 827 chains. 829 8.2. Cryptanalysis 831 A passive attacker could try to harvest the POT data (i.e., CML, RND 832 values) in order to determine the configured secrets. Subsequently 833 two types of differential analysis for guessing the secrets could be 834 done. 836 o Inter-Node: A passive attacker observing CML values across nodes 837 (i.e., as the packets entering and leaving), cannot perform 838 differential analysis to construct the points on POLY-1. This is 839 because at each point there are four unknowns (i.e. Share(POLY- 840 1), Share(Poly-2) LPC and prime number P) and three known values 841 (i.e. RND, CML-before, CML-after). 843 o Inter-Packets: A passive attacker could observe CML values across 844 packets (i.e., values of PKT-1 and subsequent PKT-2), in order to 845 predict the secrets. Differential analysis across packets could 846 be mitigated using a good PRNG for generating RND. Note that if 847 constant coefficient is a sequence number than CML values become 848 quite predictable and the scheme would be broken. 850 8.3. Anti-Replay 852 A passive attacker could reuse a set of older RND and the 853 intermediate CML values to bypass certain nodes in later packets. 854 Such attacks could be avoided by carefully choosing POLY-2 as a 855 (SEQ_NO + RND). For example, if 64 bits are being used for POLY-2 856 then first 16 bits could be a sequence number SEQ_NO and next 48 bits 857 could be a random number. 859 Subsequently, the verifier could use the SEQ_NO bits to run classic 860 anti-replay techniques like sliding window used in IPSEC. The 861 verifier could buffer up to 2^16 packets as a sliding window. 862 Packets arriving with a higher SEQ_NO than current buffer could be 863 flagged legitimate. Packets arriving with a lower SEQ_NO than 864 current buffer could be flagged as suspicious. 866 For all practical purposes in the rest of the document RND means 867 SEQ_NO + RND to keep it simple. 869 The solution discussed in this memo does not currently mitigate 870 replay attacks. An anti-replay mechanism may be included in future 871 versions of the solution. 873 8.4. Anti-Preplay 875 An active attacker could try to perform a man-in-the-middle (MITM) 876 attack by extracting the POT of PKT-1 and using it in PKT-2. 877 Subsequently attacker drops the PKT-1 in order to avoid duplicate POT 878 values reaching the verifier. If the PKT-1 reaches the verifier, 879 then this attack is same as Replay attacks discussed before. 881 Preplay attacks are possible since the POT metadata is not dependent 882 on the packet fields. Below steps are recommended for remediation: 884 o Ingress node and Verifier are configured with common pre shared 885 key 887 o Ingress node generates a Message Authentication Code (MAC) from 888 packet fields using standard HMAC algorithm. 890 o The left most bits of the output are truncated to desired length 891 to generate RND. It is recommended to use a minimum of 32 bits. 893 o The verifier regenerates the HMAC from the packet fields and 894 compares with RND. To ensure the POT data is in fact that of the 895 packet. 897 If an HMAC is used, an active attacker lacks the knowledge of the 898 pre-shared key, and thus cannot launch preplay attacks. 900 The solution discussed in this memo does not currently mitigate 901 prereplay attacks. A mitigation mechanism may be included in future 902 versions of the solution. 904 8.5. Anti-Tampering 906 An active attacker could not insert any arbitrary value for CML. 907 This would subsequently fail the reconstruction of the POLY-3. Also 908 an attacker could not update the CML with a previously observed 909 value. This could subsequently be detected by using timestamps 910 within the RND value as discussed above. 912 8.6. Recycling 914 The solution approach is flexible for recycling long term secrets 915 like POLY-1. All the nodes could be periodically updated with shares 916 of new SECRET as best practice. The table above could be consulted 917 for refresh cycles (see Section 4). 919 8.7. Redundant Nodes and Failover 921 A "node" or "service" in terms of POT can be implemented by one or 922 multiple physical entities. In case of multiple physical entities 923 (e.g., for load-balancing, or business continuity situations - 924 consider for example a set of firewalls), all physical entities which 925 are implementing the same POT node are given that same share of the 926 secret. This makes multiple physical entities represent the same POT 927 node from an algorithm perspective. 929 8.8. Controller Operation 931 The Controller needs to be secured given that it creates and holds 932 the secrets, as need to be the nodes. The communication between 933 Controller and the nodes also needs to be secured. As secure 934 communication protocol such as for example NETCONF over SSH should be 935 chosen for Controller to node communication. 937 The Controller only interacts with the nodes during the initial 938 configuration and thereafter at regular intervals at which the 939 operator chooses to switch to a new set of secrets. In case 64 bits 940 are used for the data fields "CML" and "RND" which are carried within 941 the data packet, the regular intervals are expected to be quite long 942 (e.g., at 100 Gbps, a profile would only be used up after 3100 years) 943 - see Section 4 above, thus even a "headless" operation without a 944 Controller can be considered feasible. In such a case, the 945 Controller would only be used for the initial configuration of the 946 POT-profiles. 948 8.9. Verification Scope 950 The POT solution defined in this document verifies that a data-packet 951 traversed or transited a specific set of nodes. From an algorithm 952 perspective, a "node" is an abstract entity. It could be represented 953 by one or multiple physical or virtual network devices, or is could 954 be a component within a networking device or system. The latter 955 would be the case if a forwarding path within a device would need to 956 be securely verified. 958 8.9.1. Node Ordering 960 POT using Shamir's secret sharing scheme as discussed in this 961 document provides for a means to verify that a set of nodes has been 962 visited by a data packet. It does not verify the order in which the 963 data packet visited the nodes. In case the order in which a data 964 packet traversed a particular set of nodes needs to be verified as 965 well, alternate schemes that e.g., rely on "nested encryption" could 966 to be considered. 968 8.9.2. Stealth Nodes 970 The POT approach discussed in this document is to prove that a data 971 packet traversed a specific set of "nodes". This set could be all 972 nodes within a path, but could also be a subset of nodes in a path. 973 Consequently, the POT approach isn't suited to detect whether 974 "stealth" nodes which do not participate in proof-of-transit have 975 been inserted into a path. 977 9. Acknowledgements 979 The authors would like to thank Eric Vyncke, Nalini Elkins, Srihari 980 Raghavan, Ranganathan T S, Karthik Babu Harichandra Babu, Akshaya 981 Nadahalli, Erik Nordmark, and Andrew Yourtchenko for the comments and 982 advice. 984 10. References 986 10.1. Normative References 988 [RFC7665] Halpern, J., Ed. and C. Pignataro, Ed., "Service Function 989 Chaining (SFC) Architecture", RFC 7665, 990 DOI 10.17487/RFC7665, October 2015, . 993 [SSS] "Shamir's Secret Sharing", . 996 10.2. Informative References 998 [I-D.ietf-anima-autonomic-control-plane] 999 Behringer, M., Eckert, T., and S. Bjarnason, "An Autonomic 1000 Control Plane", draft-ietf-anima-autonomic-control- 1001 plane-03 (work in progress), July 2016. 1003 Authors' Addresses 1005 Frank Brockners 1006 Cisco Systems, Inc. 1007 Hansaallee 249, 3rd Floor 1008 DUESSELDORF, NORDRHEIN-WESTFALEN 40549 1009 Germany 1011 Email: fbrockne@cisco.com 1013 Shwetha Bhandari 1014 Cisco Systems, Inc. 1015 Cessna Business Park, Sarjapura Marathalli Outer Ring Road 1016 Bangalore, KARNATAKA 560 087 1017 India 1019 Email: shwethab@cisco.com 1021 Sashank Dara 1022 Cisco Systems, Inc. 1023 Cessna Business Park, Sarjapura Marathalli Outer Ring Road 1024 BANGALORE, Bangalore, KARNATAKA 560 087 1025 INDIA 1027 Email: sadara@cisco.com 1029 Carlos Pignataro 1030 Cisco Systems, Inc. 1031 7200-11 Kit Creek Road 1032 Research Triangle Park, NC 27709 1033 United States 1035 Email: cpignata@cisco.com 1036 John Leddy 1037 Comcast 1039 Email: John_Leddy@cable.comcast.com 1041 Stephen Youell 1042 JP Morgan Chase 1043 25 Bank Street 1044 London E14 5JP 1045 United Kingdom 1047 Email: stephen.youell@jpmorgan.com 1049 David Mozes 1051 Email: mosesster@gmail.com 1053 Tal Mizrahi 1054 Marvell 1055 6 Hamada St. 1056 Yokneam 20692 1057 Israel 1059 Email: talmi@marvell.com