idnits 2.17.1 draft-ietf-sfc-proof-of-transit-01.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 (October 1, 2018) is 2034 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-18 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: April 4, 2019 C. Pignataro 6 Cisco 7 J. Leddy 8 Comcast 9 S. Youell 10 JPMC 11 D. Mozes 13 T. Mizrahi 14 Marvell 15 A. Aguado 16 Universidad Politecnica de Madrid 17 D. Lopez 18 Telefonica I+D 19 October 1, 2018 21 Proof of Transit 22 draft-ietf-sfc-proof-of-transit-01 24 Abstract 26 Several technologies such as Traffic Engineering (TE), Service 27 Function Chaining (SFC), and policy based routing are used to steer 28 traffic through a specific, user-defined path. This document defines 29 mechanisms to securely prove that traffic transited said defined 30 path. These mechanisms allow to securely verify whether, within a 31 given path, all packets traversed all the nodes that they are 32 supposed to visit. 34 Status of This Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at http://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on April 4, 2019. 50 Copyright Notice 52 Copyright (c) 2018 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 4 69 3. Proof of Transit . . . . . . . . . . . . . . . . . . . . . . 5 70 3.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . 5 71 3.2. Solution Approach . . . . . . . . . . . . . . . . . . . . 6 72 3.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 7 73 3.2.2. In Transit . . . . . . . . . . . . . . . . . . . . . 7 74 3.2.3. Verification . . . . . . . . . . . . . . . . . . . . 7 75 3.3. Illustrative Example . . . . . . . . . . . . . . . . . . 7 76 3.3.1. Basic Version . . . . . . . . . . . . . . . . . . . . 7 77 3.3.1.1. Secret Shares . . . . . . . . . . . . . . . . . . 8 78 3.3.1.2. Lagrange Polynomials . . . . . . . . . . . . . . 8 79 3.3.1.3. LPC Computation . . . . . . . . . . . . . . . . . 8 80 3.3.1.4. Reconstruction . . . . . . . . . . . . . . . . . 9 81 3.3.1.5. Verification . . . . . . . . . . . . . . . . . . 9 82 3.3.2. Enhanced Version . . . . . . . . . . . . . . . . . . 9 83 3.3.2.1. Random Polynomial . . . . . . . . . . . . . . . . 9 84 3.3.2.2. Reconstruction . . . . . . . . . . . . . . . . . 10 85 3.3.2.3. Verification . . . . . . . . . . . . . . . . . . 10 86 3.3.3. Final Version . . . . . . . . . . . . . . . . . . . . 11 87 3.4. Operational Aspects . . . . . . . . . . . . . . . . . . . 11 88 3.5. Ordered POT (OPOT) . . . . . . . . . . . . . . . . . . . 12 89 3.5.1. Nested Encryption . . . . . . . . . . . . . . . . . . 12 90 3.5.2. Symmetric Masking Between Nodes . . . . . . . . . . . 12 91 4. Sizing the Data for Proof of Transit . . . . . . . . . . . . 13 92 5. Node Configuration . . . . . . . . . . . . . . . . . . . . . 14 93 5.1. Procedure . . . . . . . . . . . . . . . . . . . . . . . . 14 94 5.2. YANG Model . . . . . . . . . . . . . . . . . . . . . . . 15 95 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 96 7. Manageability Considerations . . . . . . . . . . . . . . . . 18 97 8. Security Considerations . . . . . . . . . . . . . . . . . . . 18 98 8.1. Proof of Transit . . . . . . . . . . . . . . . . . . . . 18 99 8.2. Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . 19 100 8.3. Anti-Replay . . . . . . . . . . . . . . . . . . . . . . . 20 101 8.4. Anti-Preplay . . . . . . . . . . . . . . . . . . . . . . 20 102 8.5. Anti-Tampering . . . . . . . . . . . . . . . . . . . . . 21 103 8.6. Recycling . . . . . . . . . . . . . . . . . . . . . . . . 21 104 8.7. Redundant Nodes and Failover . . . . . . . . . . . . . . 21 105 8.8. Controller Operation . . . . . . . . . . . . . . . . . . 21 106 8.9. Verification Scope . . . . . . . . . . . . . . . . . . . 22 107 8.9.1. Node Ordering . . . . . . . . . . . . . . . . . . . . 22 108 8.9.2. Stealth Nodes . . . . . . . . . . . . . . . . . . . . 22 109 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 23 110 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 111 10.1. Normative References . . . . . . . . . . . . . . . . . . 23 112 10.2. Informative References . . . . . . . . . . . . . . . . . 23 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 115 1. Introduction 117 Several deployments use Traffic Engineering, policy routing, Segment 118 Routing (SR), and Service Function Chaining (SFC) [RFC7665] to steer 119 packets through a specific set of nodes. In certain cases, 120 regulatory obligations or a compliance policy require operators to 121 prove that all packets that are supposed to follow a specific path 122 are indeed being forwarded across and exact set of pre-determined 123 nodes. 125 If a packet flow is supposed to go through a series of service 126 functions or network nodes, it has to be proven that indeed all 127 packets of the flow followed the path or service chain or collection 128 of nodes specified by the policy. In case some packets of a flow 129 weren't appropriately processed, a verification device should 130 determine the policy violation and take corresponding actions 131 corresponding to the policy (e.g., drop or redirect the packet, send 132 an alert etc.) In today's deployments, the proof that a packet 133 traversed a particular path or service chain is typically delivered 134 in an indirect way: Service appliances and network forwarding are in 135 different trust domains. Physical hand-off-points are defined 136 between these trust domains (i.e. physical interfaces). Or in other 137 terms, in the "network forwarding domain" things are wired up in a 138 way that traffic is delivered to the ingress interface of a service 139 appliance and received back from an egress interface of a service 140 appliance. This "wiring" is verified and then trusted upon. The 141 evolution to Network Function Virtualization (NFV) and modern service 142 chaining concepts (using technologies such as Locator/ID Separation 143 Protocol (LISP), Network Service Header (NSH), Segment Routing (SR), 144 etc.) blurs the line between the different trust domains, because the 145 hand-off-points are no longer clearly defined physical interfaces, 146 but are virtual interfaces. As a consequence, different trust layers 147 should not to be mixed in the same device. For an NFV scenario a 148 different type of proof is required. Offering a proof that a packet 149 indeed traversed a specific set of service functions or nodes allows 150 operators to evolve from the above described indirect methods of 151 proving that packets visit a predetermined set of nodes. 153 The solution approach presented in this document is based on a small 154 portion of operational data added to every packet. This "in-situ" 155 operational data is also referred to as "proof of transit data", or 156 POT data. The POT data is updated at every required node and is used 157 to verify whether a packet traversed all required nodes. A 158 particular set of nodes "to be verified" is either described by a set 159 of secret keys, or a set of shares of a single secret. Nodes on the 160 path retrieve their individual keys or shares of a key (using for 161 e.g., Shamir's Secret Sharing scheme) from a central controller. The 162 complete key set is only known to the controller and a verifier node, 163 which is typically the ultimate node on a path that performs 164 verification. Each node in the path uses its secret or share of the 165 secret to update the POT data of the packets as the packets pass 166 through the node. When the verifier receives a packet, it uses its 167 key(s) along with data found in the packet to validate whether the 168 packet traversed the path correctly. 170 2. Conventions 172 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 173 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 174 document are to be interpreted as described in [RFC2119]. 176 Abbreviations used in this document: 178 HMAC: Hash based Message Authentication Code. For example, 179 HMAC-SHA256 generates 256 bits of MAC 181 IOAM: In-situ Operations, Administration, and Maintenance 183 LISP: Locator/ID Separation Protocol 185 LPC: Lagrange Polynomial Constants 187 MTU: Maximum Transmit Unit 189 NFV: Network Function Virtualization 191 NSH: Network Service Header 192 POT: Proof of Transit 194 POT-profile: Proof of Transit Profile that has the necessary data 195 for nodes to participate in proof of transit 197 RND: Random Bits generated per packet. Packet fields that 198 donot change during the traversal are given as input to 199 HMAC-256 algorithm. A minimum of 32 bits (left most) need 200 to be used from the output if RND is used to verify the 201 packet integrity. This is a standard recommendation by 202 NIST. 204 SEQ_NO: Sequence number initialized to a predefined constant. 205 This is used in concatenation with RND bits to mitigate 206 different attacks discussed later. 208 SFC: Service Function Chain 210 SR: Segment Routing 212 3. Proof of Transit 214 This section discusses methods and algorithms to provide for a "proof 215 of transit" for packets traversing a specific path. A path which is 216 to be verified consists of a set of nodes. Transit of the data 217 packets through those nodes is to be proven. Besides the nodes, the 218 setup also includes a Controller that creates secrets and secrets 219 shares and configures the nodes for POT operations. 221 The methods how traffic is identified and associated to a specific 222 path is outside the scope of this document. Identification could be 223 done using a filter (e.g., 5-tuple classifier), or an identifier 224 which is already present in the packet (e.g., path or service 225 identifier, NSH Service Path Identifier (SPI), flow-label, etc.) 227 The solution approach is detailed in two steps. Initially the 228 concept of the approach is explained. This concept is then further 229 refined to make it operationally feasible. 231 3.1. Basic Idea 233 The method relies on adding POT data to all packets that traverse a 234 path. The added POT data allows a verifying node (egress node) to 235 check whether a packet traversed the identified set of nodes on a 236 path correctly or not. Security mechanisms are natively built into 237 the generation of the POT data to protect against misuse (i.e. 238 configuration mistakes, malicious administrators playing tricks with 239 routing, capturing, spoofing and replaying packets). The mechanism 240 for POT leverages "Shamir's Secret Sharing" scheme [SSS]. 242 Shamir's secret sharing base idea: A polynomial (represented by its 243 coefficients) is chosen as a secret by the controller. A polynomial 244 represents a curve. A set of well-defined points on the curve are 245 needed to construct the polynomial. Each point of the polynomial is 246 called "share" of the secret. A single secret is associated with a 247 particular set of nodes, which typically represent the path, to be 248 verified. Shares of the single secret (i.e., points on the curve) 249 are securely distributed from a Controller to the network nodes. 250 Nodes use their respective share to update a cumulative value in the 251 POT data of each packet. Only a verifying node has access to the 252 complete secret. The verifying node validates the correctness of the 253 received POT data by reconstructing the curve. 255 The polynomial cannot be constructed if any of the points are missed 256 or tampered. Per Shamir's Secret Sharing Scheme, any lesser points 257 means one or more nodes are missed. Details of the precise 258 configuration needed for achieving security are discussed further 259 below. 261 While applicable in theory, a vanilla approach based on Shamir's 262 secret sharing could be easily attacked. If the same polynomial is 263 reused for every packet for a path a passive attacker could reuse the 264 value. As a consequence, one could consider creating a different 265 polynomial per packet. Such an approach would be operationally 266 complex. It would be complex to configure and recycle so many curves 267 and their respective points for each node. Rather than using a 268 single polynomial, two polynomials are used for the solution 269 approach: A secret polynomial which is kept constant, and a per- 270 packet polynomial which is public. Operations are performed on the 271 sum of those two polynomials - creating a third polynomial which is 272 secret and per packet. 274 3.2. Solution Approach 276 Solution approach: The overall algorithm uses two polynomials: POLY-1 277 and POLY-2. POLY-1 is secret and constant. Each node gets a point 278 on POLY-1 at setup-time and keeps it secret. POLY-2 is public, 279 random and per packet. Each node generates a point on POLY-2 each 280 time a packet crosses it. Each node then calculates (point on POLY-1 281 + point on POLY-2) to get a (point on POLY-3) and passes it to 282 verifier by adding it to each packet. The verifier constructs POLY-3 283 from the points given by all the nodes and cross checks whether 284 POLY-3 = POLY-1 + POLY-2. Only the verifier knows POLY-1. The 285 solution leverages finite field arithmetic in a field of size "prime 286 number". 288 Detailed algorithms are discussed next. A simple example is 289 discussed in Section 3.3. 291 3.2.1. Setup 293 A controller generates a first polynomial (POLY-1) of degree k and 294 k+1 points on the polynomial. The constant coefficient of POLY-1 is 295 considered the SECRET. The non-constant coefficients are used to 296 generate the Lagrange Polynomial Constants (LPC). Each of the k 297 nodes (including verifier) are assigned a point on the polynomial 298 i.e., shares of the SECRET. The verifier is configured with the 299 SECRET. The Controller also generates coefficients (except the 300 constant coefficient, called "RND", which is changed on a per packet 301 basis) of a second polynomial POLY-2 of the same degree. Each node 302 is configured with the LPC of POLY-2. Note that POLY-2 is public. 304 3.2.2. In Transit 306 For each packet, the ingress node generates a random number (RND). 307 It is considered as the constant coefficient for POLY-2. A 308 cumulative value (CML) is initialized to 0. Both RND, CML are 309 carried as within the packet POT data. As the packet visits each 310 node, the RND is retrieved from the packet and the respective share 311 of POLY-2 is calculated. Each node calculates (Share(POLY-1) + 312 Share(POLY-2)) and CML is updated with this sum. This step is 313 performed by each node until the packet completes the path. The 314 verifier also performs the step with its respective share. 316 3.2.3. Verification 318 The verifier cross checks whether CML = SECRET + RND. If this 319 matches then the packet traversed the specified set of nodes in the 320 path. This is due to the additive homomorphic property of Shamir's 321 Secret Sharing scheme. 323 3.3. Illustrative Example 325 This section shows a simple example to illustrate step by step the 326 approach described above. 328 3.3.1. Basic Version 330 Assumption: It is to be verified whether packets passed through 3 331 nodes. A polynomial of degree 2 is chosen for verification. 333 Choices: Prime = 53. POLY-1(x) = (3x^2 + 3x + 10) mod 53. The 334 secret to be re-constructed is the constant coefficient of POLY-1, 335 i.e., SECRET=10. It is important to note that all operations are 336 done over a finite field (i.e., modulo prime). 338 3.3.1.1. Secret Shares 340 The shares of the secret are the points on POLY-1 chosen for the 3 341 nodes. For example, let x0=2, x1=4, x2=5. 343 POLY-1(2) = 28 => (x0, y0) = (2, 28) 345 POLY-1(4) = 17 => (x1, y1) = (4, 17) 347 POLY-1(5) = 47 => (x2, y2) = (5, 47) 349 The three points above are the points on the curve which are 350 considered the shares of the secret. They are assigned to three 351 nodes respectively and are kept secret. 353 3.3.1.2. Lagrange Polynomials 355 Lagrange basis polynomials (or Lagrange polynomials) are used for 356 polynomial interpolation. For a given set of points on the curve 357 Lagrange polynomials (as defined below) are used to reconstruct the 358 curve and thus reconstruct the complete secret. 360 l0(x) = (((x-x1) / (x0-x1)) * ((x-x2)/x0-x2))) mod 53 = 361 (((x-4) / (2-4)) * ((x-5)/2-5))) mod 53 = 362 (10/3 - 3x/2 + (1/6)x^2) mod 53 364 l1(x) = (((x-x0) / (x1-x0)) * ((x-x2)/x1-x2))) mod 53 = 365 (-5 + 7x/2 - (1/2)x^2) mod 53 367 l2(x) = (((x-x0) / (x2-x0)) * ((x-x1)/x2-x1))) mod 53 = 368 (8/3 - 2 + (1/3)x^2) mod 53 370 3.3.1.3. LPC Computation 372 Since x0=2, x1=4, x2=5 are chosen points. Given that computations 373 are done over a finite arithmetic field ("modulo a prime number"), 374 the Lagrange basis polynomial constants are computed modulo 53. The 375 Lagrange Polynomial Constant (LPC) would be 10/3 , -5 , 8/3. 377 LPC(x0) = (10/3) mod 53 = 21 379 LPC(x1) = (-5) mod 53 = 48 381 LPC(x2) = (8/3) mod 53 = 38 383 For a general way to compute the modular multiplicative inverse, see 384 e.g., the Euclidean algorithm. 386 3.3.1.4. Reconstruction 388 Reconstruction of the polynomial is well-defined as 390 POLY1(x) = l0(x) * y0 + l1(x) * y1 + l2(x) * y2 392 Subsequently, the SECRET, which is the constant coefficient of 393 POLY1(x) can be computed as below 395 SECRET = (y0*LPC(l0)+y1*LPC(l1)+y2*LPC(l2)) mod 53 397 The secret can be easily reconstructed using the y-values and the 398 LPC: 400 SECRET = (y0*LPC(l0) + y1*LPC(l1) + y2*LPC(l2)) mod 53 = mod (28 * 21 401 + 17 * 48 + 47 * 38) mod 53 = 3190 mod 53 = 10 403 One observes that the secret reconstruction can easily be performed 404 cumulatively hop by hop. CML represents the cumulative value. It is 405 the POT data in the packet that is updated at each hop with the 406 node's respective (yi*LPC(i)), where i is their respective value. 408 3.3.1.5. Verification 410 Upon completion of the path, the resulting CML is retrieved by the 411 verifier from the packet POT data. Recall that verifier is 412 preconfigured with the original SECRET. It is cross checked with the 413 CML by the verifier. Subsequent actions based on the verification 414 failing or succeeding could be taken as per the configured policies. 416 3.3.2. Enhanced Version 418 As observed previously, the vanilla algorithm that involves a single 419 secret polynomial is not secure. Therefore, the solution is further 420 enhanced with usage of a random second polynomial chosen per packet. 422 3.3.2.1. Random Polynomial 424 Let the second polynomial POLY-2 be (RND + 7x + 10 x^2). RND is a 425 random number and is generated for each packet. Note that POLY-2 is 426 public and need not be kept secret. The nodes can be pre-configured 427 with the non-constant coefficients (for example, 7 and 10 in this 428 case could be configured through the Controller on each node). So 429 precisely only RND value changes per packet and is public and the 430 rest of the non-constant coefficients of POLY-2 kept secret. 432 3.3.2.2. Reconstruction 434 Recall that each node is preconfigured with their respective 435 Share(POLY-1). Each node calculates its respective Share(POLY-2) 436 using the RND value retrieved from the packet. The CML 437 reconstruction is enhanced as below. At every node, CML is updated 438 as 440 CML = CML+(((Share(POLY-1)+ Share(POLY-2)) * LPC) mod Prime 442 Let us observe the packet level transformations in detail. For the 443 example packet here, let the value RND be 45. Thus POLY-2 would be 444 (45 + 7x + 10x^2). 446 The shares that could be generated are (2, 46), (4, 21), (5, 12). 448 At ingress: The fields RND = 45. CML = 0. 450 At node-1 (x0): Respective share of POLY-2 is generated i.e., (2, 451 46) because share index of node-1 is 2. 453 CML = 0 + ((28 + 46)* 21) mod 53 = 17 455 At node-2 (x1): Respective share of POLY-2 is generated i.e., (4, 456 21) because share index of node-2 is 4. 458 CML = 17 + ((17 + 21)*48) mod 53 = 17 + 22 = 39 460 At node-3 (x2), which is also the verifier: The respective share 461 of POLY-2 is generated i.e., (5, 12) because the share index of 462 the verifier is 12. 464 CML = 39 + ((47 + 12)*38) mod 53 = 39 + 16 = 55 mod 53 = 2 466 The verification using CML is discussed in next section. 468 3.3.2.3. Verification 470 As shown in the above example, for final verification, the verifier 471 compares: 473 VERIFY = (SECRET + RND) mod Prime, with Prime = 53 here 475 VERIFY = (RND-1 + RND-2) mod Prime = ( 10 + 45 ) mod 53 = 2 477 Since VERIFY = CML the packet is proven to have gone through nodes 1, 478 2, and 3. 480 3.3.3. Final Version 482 The enhanced version of the protocol is still prone to replay and 483 preplay attacks. An attacker could reuse the POT metadata for 484 bypassing the verification. So additional measures using packet 485 integrity checks (HMAC) and sequence numbers (SEQ_NO) are discussed 486 later "Security Considerations" section. 488 3.4. Operational Aspects 490 To operationalize this scheme, a central controller is used to 491 generate the necessary polynomials, the secret share per node, the 492 prime number, etc. and distributing the data to the nodes 493 participating in proof of transit. The identified node that performs 494 the verification is provided with the verification key. The 495 information provided from the Controller to each of the nodes 496 participating in proof of transit is referred to as a proof of 497 transit profile (POT-profile). Also note that the set of nodes for 498 which the transit has to be proven are typically associated to a 499 different trust domain than the verifier. Note that building the 500 trust relationship between the Controller and the nodes is outside 501 the scope of this document. Techniques such as those described in 502 [I-D.ietf-anima-autonomic-control-plane] might be applied. 504 To optimize the overall data amount of exchanged and the processing 505 at the nodes the following optimizations are performed: 507 1. The points (x, y) for each of the nodes on the public and private 508 polynomials are picked such that the x component of the points 509 match. This lends to the LPC values which are used to calculate 510 the cumulative value CML to be constant. Note that the LPC are 511 only depending on the x components. They can be computed at the 512 controller and communicated to the nodes. Otherwise, one would 513 need to distributed the x components to all the nodes. 515 2. A pre-evaluated portion of the public polynomial for each of the 516 nodes is calculated and added to the POT-profile. Without this 517 all the coefficients of the public polynomial had to be added to 518 the POT profile and each node had to evaluate them. As stated 519 before, the public portion is only the constant coefficient RND 520 value, the pre-evaluated portion for each node should be kept 521 secret as well. 523 3. To provide flexibility on the size of the cumulative and random 524 numbers carried in the POT data a field to indicate this is 525 shared and interpreted at the nodes. 527 3.5. Ordered POT (OPOT) 529 In certain scenarios preserving the order of the nodes traversed by 530 the packet may be needed. Two alternatives, one based on "nested 531 encryption", and another based on "symmetric masking between nodes" 532 are described here for preserving the order 534 3.5.1. Nested Encryption 536 1. The controller provisions all the nodes with their respective 537 secret keys. 539 2. The controller provisions the verifier with all the secret keys 540 of the nodes. 542 3. For each packet, the ingress node generates a random number RND 543 and encrypts it with its secret key to generate CML value 545 4. Each subsequent node on the path encrypts CML with their 546 respective secret key and passes it along 548 5. The verifier is also provisioned with the expected sequence of 549 nodes in order to verify the order 551 6. The verifier receives the CML, RND values, re-encrypts the RND 552 with keys in the same order as expected sequence to verify. 554 With this nested encryption approach it is possible to retain the 555 order in which the nodes are traversed, at the cost of: 557 1. Standard AES encryption would need 128 bits of RND, CML. This 558 results in a 256 bits of additional overhead is added per packet 560 2. In hardware platforms that do not support native encryption 561 capabilities like (AES-NI). This approach would have 562 considerable impact on the computational latency 564 3.5.2. Symmetric Masking Between Nodes 566 1. The controller provisions all the nodes with (or asks them to 567 agree on) a couple of secrets, that we will refer as masks, one 568 for the connection from the upstream node(s), another for the 569 connection to the downstream node(s). For obvious reasons, the 570 ingress and egress (verifier) nodes only receive one, for 571 downstream and upstream, respectively. 573 2. Any two contiguous nodes in the OPOT stream share the mask for 574 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.2), the masks used between nodes adjacent in the path 653 MUST 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 those to the nodes. The sum of 661 all parameters for a specific node is referred to as "POT-profile". 662 This document does not define a specific protocol to be used between 663 Controller and nodes. It only defines the procedures and the 664 associated YANG data model. 666 5.1. Procedure 668 The Controller creates new POT-profiles at a constant rate and 669 communicates the POT-profile to the nodes. The controller labels a 670 POT-profile "even" or "odd" and the Controller cycles between "even" 671 and "odd" labeled profiles. The rate at which the POT-profiles are 672 communicated to the nodes is configurable and is more frequent than 673 the speed at which a POT-profile is "used up" (see table above). 674 Once the POT-profile has been successfully communicated to all nodes 675 (e.g., all NETCONF transactions completed, in case NETCONF is used as 676 a protocol), the controller sends an "enable POT-profile" request to 677 the ingress node. 679 All nodes maintain two POT-profiles (an even and an odd POT-profile): 680 One POT-profile is currently active and in use; one profile is 681 standby and about to get used. A flag in the packet is indicating 682 whether the odd or even POT-profile is to be used by a node. This is 683 to ensure that during profile change the service is not disrupted. 684 If the "odd" profile is active, the Controller can communicate the 685 "even" profile to all nodes. Only if all the nodes have received the 686 POT-profile, the Controller will tell the ingress node to switch to 687 the "even" profile. Given that the indicator travels within the 688 packet, all nodes will switch to the "even" profile. The "even" 689 profile gets active on all nodes and nodes are ready to receive a new 690 "odd" profile. 692 Unless the ingress node receives a request to switch profiles, it'll 693 continue to use the active profile. If a profile is "used up" the 694 ingress node will recycle the active profile and start over (this 695 could give rise to replay attacks in theory - but with 2^32 or 2^64 696 packets this isn't really likely in reality). 698 5.2. YANG Model 700 This section defines that YANG data model for the information 701 exchange between the Controller and the nodes. 703 file "ietf-pot-profile@2016-06-15.yang" 704 module ietf-pot-profile { 706 yang-version 1; 708 namespace "urn:ietf:params:xml:ns:yang:ietf-pot-profile"; 710 prefix ietf-pot-profile; 712 organization "IETF xxx Working Group"; 714 contact ""; 716 description "This module contains a collection of YANG 717 definitions for proof of transit configuration 718 parameters. The model is meant for proof of 719 transit and is targeted for communicating the 720 POT-profile between a controller and nodes 721 participating in proof of transit."; 723 revision 2016-06-15 { 724 description 725 "Initial revision."; 726 reference 727 ""; 728 } 730 typedef profile-index-range { 731 type int32 { 732 range "0 .. 1"; 733 } 734 description 735 "Range used for the profile index. Currently restricted to 736 0 or 1 to identify the odd or even profiles."; 737 } 739 grouping pot-profile { 740 description "A grouping for proof of transit profiles."; 741 list pot-profile-list { 742 key "pot-profile-index"; 743 ordered-by user; 744 description "A set of pot profiles."; 746 leaf pot-profile-index { 747 type profile-index-range; 748 mandatory true; 749 description 750 "Proof of transit profile index."; 751 } 753 leaf prime-number { 754 type uint64; 755 mandatory true; 756 description 757 "Prime number used for module math computation"; 758 } 760 leaf secret-share { 761 type uint64; 762 mandatory true; 763 description 764 "Share of the secret of polynomial 1 used in computation"; 765 } 766 leaf public-polynomial { 767 type uint64; 768 mandatory true; 769 description 770 "Pre evaluated Public polynomial"; 771 } 773 leaf lpc { 774 type uint64; 775 mandatory true; 776 description 777 "Lagrange Polynomial Coefficient"; 778 } 780 leaf validator { 781 type boolean; 782 default "false"; 783 description 784 "True if the node is a verifier node"; 785 } 787 leaf validator-key { 788 type uint64; 789 description 790 "Secret key for validating the path, constant of poly 1"; 791 } 793 leaf bitmask { 794 type uint64; 795 default 4294967295; 796 description 797 "Number of bits as mask used in controlling the size of the 798 random value generation. 32-bits of mask is default."; 799 } 800 } 801 } 803 container pot-profiles { 804 description "A group of proof of transit profiles."; 806 list pot-profile-set { 807 key "pot-profile-name"; 808 ordered-by user; 809 description 810 "Set of proof of transit profiles that group parameters 811 required to classify and compute proof of transit 812 metadata at a node"; 814 leaf pot-profile-name { 815 type string; 816 mandatory true; 817 description 818 "Unique identifier for each proof of transit profile"; 819 } 821 leaf active-profile-index { 822 type profile-index-range; 823 description 824 "Proof of transit profile index that is currently active. 825 Will be set in the first hop of the path or chain. 826 Other nodes will not use this field."; 827 } 829 uses pot-profile; 830 } 831 /*** Container: end ***/ 832 } 833 /*** module: end ***/ 834 } 835 837 6. IANA Considerations 839 IANA considerations will be added in a future version of this 840 document. 842 7. Manageability Considerations 844 Manageability considerations will be addressed in a later version of 845 this document. 847 8. Security Considerations 849 Different security requirements achieved by the solution approach are 850 discussed here. 852 8.1. Proof of Transit 854 Proof of correctness and security of the solution approach is per 855 Shamir's Secret Sharing Scheme [SSS]. Cryptographically speaking it 856 achieves information-theoretic security i.e., it cannot be broken by 857 an attacker even with unlimited computing power. As long as the 858 below conditions are met it is impossible for an attacker to bypass 859 one or multiple nodes without getting caught. 861 o If there are k+1 nodes in the path, the polynomials (POLY-1, POLY- 862 2) should be of degree k. Also k+1 points of POLY-1 are chosen 863 and assigned to each node respectively. The verifier can re- 864 construct the k degree polynomial (POLY-3) only when all the 865 points are correctly retrieved. 867 o Precisely three values are kept secret by individual nodes. Share 868 of SECRET (i.e. points on POLY-1), Share of POLY-2, LPC, P. Note 869 that only constant coefficient, RND, of POLY-2 is public. x values 870 and non-constant coefficient of POLY-2 are secret 872 An attacker bypassing a few nodes will miss adding a respective point 873 on POLY-1 to corresponding point on POLY-2 , thus the verifier cannot 874 construct POLY-3 for cross verification. 876 Also it is highly recommended that different polynomials should be 877 used as POLY-1 across different paths, traffic profiles or service 878 chains. 880 If symmetric masking is used to assure OPOT (Section 3.5.2), the 881 nodes need to keep two additional secrets: the upstream and upstream 882 masks, that have to be managed under the same conditions as the 883 secrets mentioned above. And it is equally recommended to employ a 884 different set of mask pairs across different paths, traffic profiles 885 or service chains. 887 8.2. Cryptanalysis 889 A passive attacker could try to harvest the POT data (i.e., CML, RND 890 values) in order to determine the configured secrets. Subsequently 891 two types of differential analysis for guessing the secrets could be 892 done. 894 o Inter-Node: A passive attacker observing CML values across nodes 895 (i.e., as the packets entering and leaving), cannot perform 896 differential analysis to construct the points on POLY-1. This is 897 because at each point there are four unknowns (i.e. Share(POLY- 898 1), Share(Poly-2) LPC and prime number P) and three known values 899 (i.e. RND, CML-before, CML-after). The application of symmetric 900 masking for OPOT makes inter-node analysis less feasible. 902 o Inter-Packets: A passive attacker could observe CML values across 903 packets (i.e., values of PKT-1 and subsequent PKT-2), in order to 904 predict the secrets. Differential analysis across packets could 905 be mitigated using a good PRNG for generating RND. Note that if 906 constant coefficient is a sequence number than CML values become 907 quite predictable and the scheme would be broken. If symmetric 908 masking is used for OPOT, inter-packet analysis could be applied 909 to guess mask values, what requires a proper refresh rate for 910 masks, at least as high as the one used for LPCs. 912 8.3. Anti-Replay 914 A passive attacker could reuse a set of older RND and the 915 intermediate CML values to bypass certain nodes in later packets. 916 Such attacks could be avoided by carefully choosing POLY-2 as a 917 (SEQ_NO + RND). For example, if 64 bits are being used for POLY-2 918 then first 16 bits could be a sequence number SEQ_NO and next 48 bits 919 could be a random number. 921 Subsequently, the verifier could use the SEQ_NO bits to run classic 922 anti-replay techniques like sliding window used in IPSEC. The 923 verifier could buffer up to 2^16 packets as a sliding window. 924 Packets arriving with a higher SEQ_NO than current buffer could be 925 flagged legitimate. Packets arriving with a lower SEQ_NO than 926 current buffer could be flagged as suspicious. 928 For all practical purposes in the rest of the document RND means 929 SEQ_NO + RND to keep it simple. 931 The solution discussed in this memo does not currently mitigate 932 replay attacks. An anti-replay mechanism may be included in future 933 versions of the solution. 935 8.4. Anti-Preplay 937 An active attacker could try to perform a man-in-the-middle (MITM) 938 attack by extracting the POT of PKT-1 and using it in PKT-2. 939 Subsequently attacker drops the PKT-1 in order to avoid duplicate POT 940 values reaching the verifier. If the PKT-1 reaches the verifier, 941 then this attack is same as Replay attacks discussed before. 943 Preplay attacks are possible since the POT metadata is not dependent 944 on the packet fields. Below steps are recommended for remediation: 946 o Ingress node and Verifier are configured with common pre shared 947 key 949 o Ingress node generates a Message Authentication Code (MAC) from 950 packet fields using standard HMAC algorithm. 952 o The left most bits of the output are truncated to desired length 953 to generate RND. It is recommended to use a minimum of 32 bits. 955 o The verifier regenerates the HMAC from the packet fields and 956 compares with RND. To ensure the POT data is in fact that of the 957 packet. 959 If an HMAC is used, an active attacker lacks the knowledge of the 960 pre-shared key, and thus cannot launch preplay attacks. 962 The solution discussed in this memo does not currently mitigate 963 prereplay attacks. A mitigation mechanism may be included in future 964 versions of the solution. 966 8.5. Anti-Tampering 968 An active attacker could not insert any arbitrary value for CML. 969 This would subsequently fail the reconstruction of the POLY-3. Also 970 an attacker could not update the CML with a previously observed 971 value. This could subsequently be detected by using timestamps 972 within the RND value as discussed above. 974 8.6. Recycling 976 The solution approach is flexible for recycling long term secrets 977 like POLY-1. All the nodes could be periodically updated with shares 978 of new SECRET as best practice. The table above could be consulted 979 for refresh cycles (see Section 4). 981 If symmetric masking is used for OPOT (Section 3.5.2), mask values 982 must be periodically updated as well, at least as frequently as the 983 other secrets are. 985 8.7. Redundant Nodes and Failover 987 A "node" or "service" in terms of POT can be implemented by one or 988 multiple physical entities. In case of multiple physical entities 989 (e.g., for load-balancing, or business continuity situations - 990 consider for example a set of firewalls), all physical entities which 991 are implementing the same POT node are given that same share of the 992 secret. This makes multiple physical entities represent the same POT 993 node from an algorithm perspective. 995 8.8. Controller Operation 997 The Controller needs to be secured given that it creates and holds 998 the secrets, as need to be the nodes. The communication between 999 Controller and the nodes also needs to be secured. As secure 1000 communication protocol such as for example NETCONF over SSH should be 1001 chosen for Controller to node communication. 1003 The Controller only interacts with the nodes during the initial 1004 configuration and thereafter at regular intervals at which the 1005 operator chooses to switch to a new set of secrets. In case 64 bits 1006 are used for the data fields "CML" and "RND" which are carried within 1007 the data packet, the regular intervals are expected to be quite long 1008 (e.g., at 100 Gbps, a profile would only be used up after 3100 years) 1009 - see Section 4 above, thus even a "headless" operation without a 1010 Controller can be considered feasible. In such a case, the 1011 Controller would only be used for the initial configuration of the 1012 POT-profiles. 1014 If OPOT (Section 3.5.2) is applied using symmetric masking, the 1015 Controller will be required to perform a a periodic refresh of the 1016 mask pairs. The use of OPOT SHOULD be configurable as part of the 1017 required level of assurance through the Controller management 1018 interface. 1020 8.9. Verification Scope 1022 The POT solution defined in this document verifies that a data-packet 1023 traversed or transited a specific set of nodes. From an algorithm 1024 perspective, a "node" is an abstract entity. It could be represented 1025 by one or multiple physical or virtual network devices, or is could 1026 be a component within a networking device or system. The latter 1027 would be the case if a forwarding path within a device would need to 1028 be securely verified. 1030 8.9.1. Node Ordering 1032 POT using Shamir's secret sharing scheme as discussed in this 1033 document provides for a means to verify that a set of nodes has been 1034 visited by a data packet. It does not verify the order in which the 1035 data packet visited the nodes. 1037 In case the order in which a data packet traversed a particular set 1038 of nodes needs to be verified as well, the alternate schemes related 1039 to OPOT (Section 3.5) have to be considered. Since these schemes 1040 introduce at least additional control requirements, the selection of 1041 order verification SHOULD be configurable the Controller management 1042 interface. 1044 8.9.2. Stealth Nodes 1046 The POT approach discussed in this document is to prove that a data 1047 packet traversed a specific set of "nodes". This set could be all 1048 nodes within a path, but could also be a subset of nodes in a path. 1049 Consequently, the POT approach isn't suited to detect whether 1050 "stealth" nodes which do not participate in proof-of-transit have 1051 been inserted into a path. 1053 9. Acknowledgements 1055 The authors would like to thank Eric Vyncke, Nalini Elkins, Srihari 1056 Raghavan, Ranganathan T S, Karthik Babu Harichandra Babu, Akshaya 1057 Nadahalli, Erik Nordmark, and Andrew Yourtchenko for the comments and 1058 advice. 1060 10. References 1062 10.1. Normative References 1064 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1065 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 1066 RFC2119, March 1997, . 1069 [RFC7665] Halpern, J., Ed. and C. Pignataro, Ed., "Service Function 1070 Chaining (SFC) Architecture", RFC 7665, DOI 10.17487/ 1071 RFC7665, October 2015, . 1074 [SSS] "Shamir's Secret Sharing", . 1077 10.2. Informative References 1079 [I-D.ietf-anima-autonomic-control-plane] 1080 Eckert, T., Behringer, M., and S. Bjarnason, "An Autonomic 1081 Control Plane (ACP)", draft-ietf-anima-autonomic-control- 1082 plane-18 (work in progress), August 2018. 1084 Authors' Addresses 1086 Frank Brockners 1087 Cisco Systems, Inc. 1088 Hansaallee 249, 3rd Floor 1089 DUESSELDORF, NORDRHEIN-WESTFALEN 40549 1090 Germany 1092 Email: fbrockne@cisco.com 1093 Shwetha Bhandari 1094 Cisco Systems, Inc. 1095 Cessna Business Park, Sarjapura Marathalli Outer Ring Road 1096 Bangalore, KARNATAKA 560 087 1097 India 1099 Email: shwethab@cisco.com 1101 Sashank Dara 1102 Cisco Systems, Inc. 1103 Cessna Business Park, Sarjapura Marathalli Outer Ring Road 1104 BANGALORE, Bangalore, KARNATAKA 560 087 1105 INDIA 1107 Email: sadara@cisco.com 1109 Carlos Pignataro 1110 Cisco Systems, Inc. 1111 7200-11 Kit Creek Road 1112 Research Triangle Park, NC 27709 1113 United States 1115 Email: cpignata@cisco.com 1117 John Leddy 1118 Comcast 1120 Email: John_Leddy@cable.comcast.com 1122 Stephen Youell 1123 JP Morgan Chase 1124 25 Bank Street 1125 London E14 5JP 1126 United Kingdom 1128 Email: stephen.youell@jpmorgan.com 1130 David Mozes 1132 Email: mosesster@gmail.com 1133 Tal Mizrahi 1134 Marvell 1135 6 Hamada St. 1136 Yokneam 20692 1137 Israel 1139 Email: talmi@marvell.com 1141 Alejandro Aguado 1142 Universidad Politecnica de Madrid 1143 Campus Montegancedo, Boadilla del Monte 1144 Madrid 28660 1145 Spain 1147 Phone: +34 910 673 086 1148 Email: a.aguadom@fi.upm.es 1150 Diego R. Lopez 1151 Telefonica I+D 1152 Editor Jose Manuel Lara, 9 (1-B) 1153 Seville 41013 1154 Spain 1156 Phone: +34 913 129 041 1157 Email: diego.r.lopez@telefonica.com