idnits 2.17.1 draft-rass-panrg-mpath-usecase-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 : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (September 10, 2019) is 1689 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'BB84' is mentioned on line 134, but not defined == Missing Reference: 'BD08' is mentioned on line 136, but not defined == Missing Reference: 'Ver55' is mentioned on line 146, but not defined == Missing Reference: 'RK12' is mentioned on line 206, but not defined == Missing Reference: 'LRPP09' is mentioned on line 493, but not defined == Unused Reference: 'RFC5510' is defined on line 297, but no explicit reference was found in the text == Unused Reference: 'RFC6824' is defined on line 302, but no explicit reference was found in the text == Unused Reference: 'Ras14' is defined on line 322, but no explicit reference was found in the text ** Obsolete normative reference: RFC 6824 (Obsoleted by RFC 8684) Summary: 2 errors (**), 0 flaws (~~), 10 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet S. Rass 3 Internet-Draft Universitaet Klagenfurt 4 Intended status: Informational Y. Qu 5 Expires: March 13, 2020 L. Han 6 Futurewei 7 September 10, 2019 9 Multipath Use Case and Requirement for Security 10 draft-rass-panrg-mpath-usecase-01 12 Abstract 14 This document describes a use case of multipath to achieve full CIA+ 15 by using symmetric cryptography and point-to-point shared secrets. 17 Status of This Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at https://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on March 13, 2020. 34 Copyright Notice 36 Copyright (c) 2019 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (https://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 52 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 53 2. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 3. Multipath Routing . . . . . . . . . . . . . . . . . . . . . . 3 55 3.1. Multi-path Service and User-Network Interface . . . . . . 4 56 3.2. Path and Routing Reliability . . . . . . . . . . . . . . 4 57 3.3. Cross Domain Path Reliability . . . . . . . . . . . . . . 5 58 3.4. Cross Domain Network Connections . . . . . . . . . . . . 5 59 3.5. Updates upon Changing Network Topologies . . . . . . . . 5 60 3.6. Enforced Device Pairing and De-Pairing . . . . . . . . . 6 61 4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 62 5. Security Considerations . . . . . . . . . . . . . . . . . . . 6 63 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 6 64 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 65 7.1. Normative References . . . . . . . . . . . . . . . . . . 6 66 7.2. Informative References . . . . . . . . . . . . . . . . . 7 67 Appendix A. Cryptographic and Graph-Theoretic Basics . . . . . . 9 68 A.1. Secret Sharing . . . . . . . . . . . . . . . . . . . . . 9 69 A.2. Network Connectivity . . . . . . . . . . . . . . . . . . 9 70 Appendix B. Multipath Transmission and Game-Theoretic Security . 10 71 B.1. End-to-end Confidentiality - Parallel Version . . . . . . 10 72 B.2. End-to-end Confidentiality - Sequential-Parallel Version 10 73 B.3. Randomized Routing to Maximize Security against Node 74 (Failures) . . . . . . . . . . . . . . . . . . . . . . . 11 75 B.4. Availability . . . . . . . . . . . . . . . . . . . . . . 12 76 B.5. End-to-End Authenticity . . . . . . . . . . . . . . . . . 12 77 B.5.1. Non-Repudiation . . . . . . . . . . . . . . . . . . . 13 78 B.6. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 13 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14 81 1. Introduction 83 Public-key cryptography is a convenient tool for end-to-end security, 84 but in practice can be cumbersome or complicated for non-expert users 85 to apply. Certificate- and key management rely on complex 86 infrastructures and to a significant extent impose monetary cost and 87 human effort. 89 This document describes a method of using symmetric cryptography and 90 point-to-point shared secrets to establish full CIA+ 91 (confidentiality, integrity, availability and authenticity) end-to- 92 end security. The respective schemes rely on multipath transmission 93 and threshold cryptography, and are intended to work transparently 94 for the users, i.e., entirely below the application layer. The only 95 involvement of human action is for the key establishment, which is in 96 our setting equivalent to a pairing of devices, as is familiar from 97 other contexts, such as Bluetooth. 99 1.1. Requirements Language 101 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 102 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 103 document are to be interpreted as described in [RFC2119]. 105 2. Assumptions 107 We assume a network of bidirectional links, represented as an 108 undirected graph G=(V,E). An edge e=(v_1, v_2) in the set E 109 represents a point-to-point connection between the nodes v_1 and v_2 110 in the network. We assume that every such pair (v_i, v_j) in E 111 shares an individual secret k_ij, which is individually distinct for 112 all edges (i.e., no two pairs have, other than by coincidence, the 113 same secret). The secret exchange or establishment is left to 114 arbitrary means, e.g., any device pairing scheme 115 [I-D.ietf-dnssd-pairing] or cryptographic methods like Diffie-Hellman 116 key exchange [RFC2631] would be admissible, up to quantum key 117 distribution [BB84]. Indeed, end-to-end security in quantum networks 118 is the most natural application area of multipath transmission as we 119 discuss here. 121 We further assume that keys between adjacent nodes in the network 122 have been exchanged in an authentic manner; say, by sufficient 123 proximity during the device pairing (e.g., near field communication). 125 3. Multipath Routing 127 Multipath routing offers the remarking ability of establishing 128 public-key like security without computational intractability. This 129 means that periodic updates of keys or server certificates are no 130 longer required in such systems; updates to keys for symmetric crypto 131 are much easier by device re-pairing or refreshing keys from existing 132 key material, such as is done in quantum key distribution (QKD). 133 Multipath transmission, requiring no quantum technology per se, 134 offers nonetheless the same level of security QKD [BB84] and can 135 resist attacks by quantum computers (like post-quantum cryptography 136 [BD08]). 138 The key element to this end is using multiple paths to send a 139 message, which in the simplest instance is just like humble symmetric 140 encryption: consider two nodes A and B that have no direct connection 141 between them (i.e., A and B are several hops apart). Let us assume 142 that two paths connect A to B, where those paths intersect only at A 143 and B (we call such paths node-disjoint). If so, then A can choose a 144 session key k that it sends to B over the first path, and deliver the 145 encrypted payload over the second path. If the encryption is chosen 146 properly (e.g., Vernam cipher [Ver55]) and the adversary does not 147 intercept both paths, the connection remains secure. 149 The scheme straightforwardly generalizes to more than two paths, 150 where the payload is (always) split into shares and transmitted over 151 separate paths in parallel or sequentially. Security comes from the 152 proper encoding/creation of the pieces so that an attacker needs to 153 intercept a certain number of paths in order to breach 154 confidentiality, insert a forged message, or cause a denial of 155 service. The fundamental circumstance implying security here is the 156 existence of k (>= 2) node and link disjoint paths, so that an 157 adversary needs to conquer at least k nodes in the network to breach 158 security (by mounting a person-in-the-middle attack). 160 Security (up to QKD without trusted relays) thus hinges on the 161 following network-related assumptions: 163 3.1. Multi-path Service and User-Network Interface 165 There are at least two disjoint paths between node A and node B, so A 166 can send packets to node B via different paths efficiently and 167 reliably. 169 New User-Network Interface (UNI) should be defined to exchange 170 information between end device/application and network. The 171 information may include but not limited to: 173 o User expectation: such as number of paths, bandwidth required etc. 175 o Path aware info: the network should dynamically provide end-device 176 information such as number of paths available, each path's 177 attributes: path reliability, routing quality, bandwidth, path 178 elements etc. 180 3.2. Path and Routing Reliability 182 The sender A can deliberately choose any among the existing paths to 183 its receiver B to transmit a message. The routing is reliable in the 184 sense that there is at least a probabilistic guarantee for the packet 185 to travel over exactly the chosen route with a likelihood p that A 186 can quantify (not necessarily control). In other words, the chances 187 for the path to be blocked, or for the packet to take a detour for 188 any reason (e.g., load balancing, temporary congestions, or similar) 189 is at most 1-p, with the value of p being known to A. The ideal case 190 p = 1 expresses that the chosen route has a perfect reliability 191 (i.e., no deviations and guaranteed delivery). 193 It is admissible to express the path reliability in terms of several 194 such probabilities, referring to different dimensions for the quality 195 of service. That is, we may define a probability p_1 for the packet 196 to stay on the chosen route, another probability p_2 for the packet 197 to be delivered at all (i.e., not being blocked), or similar. 199 There are per se no stringent constraints regarding latencies or for 200 several packets to arrive in the order of transmission, since the 201 outer (cryptographic) transmission protocols can handle this. 202 However, the aforementioned probabilities quantifying the quality of 203 routing need to be accurately known to the sender A. Suitable 204 protocols to handle path deviations (temporary detours) and to 205 optimize quality-of-service tradeoffs based on such knowledge are 206 found in the literature [Ras13], [RK12]. 208 3.3. Cross Domain Path Reliability 210 If two distinct network domains are joined together, the topologies 211 of both networks are reliably made known to the nodes in the 212 respective other network. Chosen routes from one network into the 213 other must remain quantifiably reliable in the sense of section 3.2 214 above, i.e., a node A in one network must still be able to determine 215 a probability p for a packet to stay on its route and to arrive at 216 the designated destination across all network domains that it 217 traverses. 219 3.4. Cross Domain Network Connections 221 Whenever a node A has an outside connection to a node in another 222 network domain N_2, A should not have a second connection to another 223 node in the same network domain N_2. That is, if two network domains 224 N_1 and N_2 are joined together via k links, those links should 225 pairwise connect k distinct nodes in N_1 to another k distinct nodes 226 in N_2. This assures that the so-constructed larger network retains 227 the necessary number of (at least) k node disjoint paths across the 228 domains (by avoiding bottle-neck connections between networks N_1 and 229 N_2). 231 3.5. Updates upon Changing Network Topologies 233 The information described under the preceding sections needs to 234 remain up-to-date whenever A wishes to send a packet somewhere. 235 Changing topologies such as in ad hoc networks call for a proper and 236 reliable updating scheme to A's local information about the network 237 topology. This includes also changes in topologies of remote network 238 domains (that the sender does not itself belong to). 240 3.6. Enforced Device Pairing and De-Pairing 242 Whenever a node X joins a network, it must establish shared secrets 243 (for cryptography) with any neighbor with whom it has a direct point- 244 to-point connection. Whenever a node X leaves the network, nodes 245 losing the connection to X need to abandon their cryptographic key 246 formerly assigned to the connection with X. The key exchange 247 protocols can be arbitrary (cf. section 2), but the device pairing 248 must in any case be authenticated. 250 4. Summary 252 The ability to route messages along chosen paths in a network, 253 together with sufficient vertex connectivity and unique neighborhoods 254 for each node opens up the possibility to achieve end-to-end 255 security: 257 o without public-key cryptography. 259 o using only light-weight symmetric cryptographic primitives 260 (encryption and hashing). 262 o and with the most trivial key-management consisting of only the 263 exchange of keys between directly connected devices (along device 264 pairing). 266 5. Security Considerations 268 TBD. 270 6. Acknowledgements 272 TBD. 274 7. References 276 7.1. Normative References 278 [I-D.ietf-dnssd-pairing] 279 Huitema, C. and D. Kaiser, "Device Pairing Using Short 280 Authentication Strings", draft-ietf-dnssd-pairing-05 (work 281 in progress), October 2018. 283 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 284 Hashing for Message Authentication", RFC 2104, 285 DOI 10.17487/RFC2104, February 1997, 286 . 288 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 289 Requirement Levels", BCP 14, RFC 2119, 290 DOI 10.17487/RFC2119, March 1997, 291 . 293 [RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", 294 RFC 2631, DOI 10.17487/RFC2631, June 1999, 295 . 297 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 298 "Reed-Solomon Forward Error Correction (FEC) Schemes", 299 RFC 5510, DOI 10.17487/RFC5510, April 2009, 300 . 302 [RFC6824] Ford, A., Raiciu, C., Handley, M., and O. Bonaventure, 303 "TCP Extensions for Multipath Operation with Multiple 304 Addresses", RFC 6824, DOI 10.17487/RFC6824, January 2013, 305 . 307 7.2. Informative References 309 [FFGV07] Matthias Fitzi, Matthew K. Franklin, Juan Garay, and S. 310 Harsha Vardhan, TCC, LNCS, vol. 4392, Springer, 2007, pp. 311 311--322., "Towards Optimal and Efficient Perfectly Secure 312 Message Transmission". 314 [MS81] R. J. McElice and D. V. Sarwate, Commun. ACM 24 (1981), 315 no. 9, 583--584., "On Sharing Secrets and Reed-Solomon 316 Codes". 318 [Ras13] Stefan Rass, Springer Journal of Network and Systems 319 Management 21 (2013), no. 1, 47--64., "On Game-Theoretic 320 Network Security Provisioning". 322 [Ras14] Stefan Rass, International Journal of Advanced Computer 323 Science and Applications 5 (2014), no. 2, 148--157., 324 "Complexity of Network Design for Private Communication 325 and the P-vs-NP question". 327 [Ras18] Stefan Rass, CoRR abs/1810.05602 (2018)., "Perfectly 328 secure communication, based on graph- topological 329 addressing in unique-neighborhood networks". 331 [RS10] Stefan Rass and Peter Schartner, Proceedings of the 332 International Conference on Security and Management (SAM), 333 vol. 1, CSREA Press, 2010, pp. 111--115., "Multipath 334 Authentication without shared Secrets and with 335 Applications in Quantum Networks". 337 [Sha49] C. E. Shannon, Bell System Technical Journal 28 (1949), 338 656--715., "Communication Theory of Secrecy Systems". 340 [Sha79] Adi Shamir, ACM 22 (1979), no. 11, 612--613., "How to 341 share a secret". 343 Appendix A. Cryptographic and Graph-Theoretic Basics 345 A.1. Secret Sharing 347 We assume a message m to come as a binary string of length L. A 348 simple k-out-of-k secret sharing is by picking a set of k-1 random 349 strings s_1, s_2, ..., s_(k-1) of the same length as m and computes 350 s_k := m XOR s_1 XOR s_2 XOR ... XOR s_(k-1). Information- 351 theoretically, one can prove [Sha49] that the recovery of m is 352 impossible from any set of less than k of the strings s_1, ..., s_k 353 (since the missing string effectively acts as a one-time pad 354 concealing m). 356 The sharing as just described is replaceable by more sophisticated 357 schemes, such as Shamir's polynomial sharing [Sha79], which adds 358 error correction capabilities [MS81] via using an isomorphy to Reed- 359 Solomon encoding. We shall, however, hereafter not further relate to 360 standardized versions of Reed-Solomon forward error correcting codes 361 [LRPP09], but rather work with the above simple scheme instead. 363 Abstractly, we shall introduce a sharing function SPLIT(m, k) that 364 decomposes an input message m into a set of k shares according to any 365 scheme of choice (for the description in this document, the above 366 XOR-based scheme will suffice). The inverse of SPLIT will be the 367 function COMBINE(s_1, ..., s_k), taking k (out of a potentially 368 larger set) of shares to reconstruct the message m from it. Note 369 that COMBINE internally may invoke error correction algorithms 370 [LRPP09], which we do not further expand here. 372 A.2. Network Connectivity 374 If a node A wants to transmit a message m to a node B, we assume that 375 A can choose a path, or a set of paths through the network along a 376 physical connection (over multiple hops) to the end-node B. Further, 377 we assume that the network's node connectivity is such that more than 378 one route from A to B exists, and that at least two routes exist that 379 do not intersect other than at A and B (node-disjoint paths). It is 380 known that the existence of k node-disjoint paths is equivalent to 381 the graph admitting a k-vertex cut; equivalently, we call such a 382 graph k-vertex-connected. The smallest graph with that property is 383 the complete graph with k+1 nodes. Furthermore, if two k-vertex- 384 connected graphs are given, we can combine them into one (big) k- 385 vertex connected graph G as follows: we pick k distinct nodes u_1, 386 ..., u_k in G_1 and another k distinct nodes v_1, ..., v_k in G_2, 387 and connect the two graphs by adding edges (u_i, v_i) for all 388 i=1,2,...,k. The resulting graph contains all nodes and edges from 389 G_1 and G_2, plus the connecting edges between the two graphs. It is 390 provably a k-vertex-connected graph, admitting at least k node- 391 disjoint paths between any two nodes in either graph and from any 392 node in G_1 to any node in G_2 and vice versa. 394 While it may not be too optimistic to hope for a large k in the 395 existing internet topology, matters of resilience against failure of 396 single nodes in the network call for a least k=2, so that the network 397 remains connected if one node (and hence the adjacent edge) fails. 399 Let A's available routes to B be enumerated as R_1, ..., R_k, which A 400 picks with likelihoods p_1, ..., p_k, say, p_i := 1/i for an 401 equiprobable choice of a single route. Moreover, we let each 402 transmission use their point-to-point shared secrets to encrypt a 403 message along the network edge (v_i, v_j) under the key k_ij (e.g., 404 by means of the Advanced Encryption Standard or others). 406 Appendix B. Multipath Transmission and Game-Theoretic Security 408 B.1. End-to-end Confidentiality - Parallel Version 410 To confidentially transmit the message m, A proceeds as follows: 412 1. Decompose m into shares {s_1, ..., s_k} := SPLIT(m) 414 2. Send each share s_i over the route R_i (for i = 1, ..., k) in 415 parallel to B. 417 3. B, upon receiving all shares recovers the message as m := 418 COMBINE(r_1, ..., r_k). 420 By construction, the attacker needs to gather all k shares to recover 421 m, so that if the attacker can intercept only less than k paths, the 422 message m remains perfectly concealed (by the aforementioned 423 arguments). A picture of the scheme is found at 424 https://www.syssec.at/user/themes/syssec-theme/images/publikationen/ 425 MPTrans.png 427 B.2. End-to-end Confidentiality - Sequential-Parallel Version 429 The above scheme can be further strengthened by a two-stage sharing 430 as follows: as before, let m the message that A wishes to send to B 431 in perfect privacy. It proceeds as follows: 433 1. Decompose m into n shares {s_1, ..., s_n} := SPLIT(m) 435 2. For i = 1, 2, ..., n: send each share s_i by the parallel scheme 436 described above; resulting in the transmission of shares r_i1, 437 ..., r_ik for the share s_i 439 3. The receiver B then needs to (i) reconstruct every share s_i := 440 COMBINE(r_i1, ..., r_ik) (as in the parallel version above), and 441 (ii) reconstruct the overall message as m := COMBINE(s_1, ..., 442 s_n). 444 An attacker needs to intercept the entirety of shares for each 445 individual transmission, as well as for all the sequential 446 transmissions. Unless the attacker can mount a full person-in-the- 447 middle attack, the message m remains perfectly concealed. Even if 448 the attacker has a positive probability q < 0 to catch all shares for 449 a single transmission in step 2, the probability to catch the 450 entirety of n sequential shares (created in step 1) equals (1-q)^n 451 (the path choices are made stochastically independent). In choosing 452 n large enough, A can make the adversary's success chances 453 exponentially small. 455 B.3. Randomized Routing to Maximize Security against Node (Failures) 457 Suppose that the attacker can intercept a fixed maximum number t < k 458 of nodes, where k is the network's vertex connectivity. If the 459 network is such that certain routes are more or less reliable than 460 others (e.g., some routes may be easier to intercept for the 461 adversary or temporarily be unavailable), there is no obligation in 462 the above scheme to use the full set of paths per parallel 463 transmission. Instead, to transmit a share (whether in the parallel 464 or sequential-parallel version of the transmission), the sender may 465 randomly pick the route R_i with likelihood p_i, and transmit the 466 share over the chosen route. 468 Knowing the choice rules p_1, ..., p_k for the k routes that A can 469 choose from, the attacker may seek to compute an optimal strategy for 470 intercepting, resulting in probabilities q_1, ..., q_|V| for nodes to 471 attack (excluding the nodes for A and B here, since our security goal 472 is confidentiality, disregarding impersonation attacks for the 473 moment). 475 The optimal computation of probabilities to choose routes, and 476 individual likelihoods to intercept nodes amounts to a simple two- 477 person matrix game [Ras13], whose saddle-point value (computable by 478 means of linear optimization) systematically quantifies (bounds) the 479 likelihood for the attacker to succeed. For a simplified example, 480 assuming that all nodes are equally "easy" for the attacker to 481 conquer, yet with a bound to no more than 1 node to be under the 482 adversary's control at a time, the optimal choice for the sender A 483 would be an equiprobable pick among the routes, i.e., p_i := 1/k for 484 all i, and an equiprobable choice of victim nodes for the attacker 485 (here, we assumed that the sender uses only a single path at a time). 487 B.4. Availability 489 The XOR sharing used in Section 2.1 is vulnerable against packet loss 490 (whether this happens by coincidence or due the attacker's actions; 491 DoS attacks). Making the scheme resilient against packet loss or 492 damage calls for error correction capabilities within the COMBINE 493 function, e.g., using the methods described in [LRPP09]. A full- 494 fledged scheme using Reed-Solomon error correction towards optimized 495 availability and confidentiality is described by [FFGV07]. 497 B.5. End-to-End Authenticity 499 Using a similar idea [RS10], authenticity of messages is 500 accomplishable by message authentication codes. Since the sender A 501 shares secrets only with her/his direct neighbors, it can only use 502 their secrets to attach a message authentication code. The receiver 503 B, being several hops away from A, does not know the secrets to 504 verify the MAC, but, thanks to its ability of chosen path routing, 505 can ask A's neighbors to verify the MACs on B's behalf. 507 Putting this to practice, A authenticates a message m for B as 508 follows, using the keys {k_1, ..., k_n} that A shares with its direct 509 neighbors in the network. We write MAC(m,k) to denote a message 510 authentication code (MAC) for a message m computed under the (secret) 511 key k. Moreover, let H be a cryptographically strong hash function 512 (e.g., SHA-3 or likewise). 514 1. A computes hash-MACs, e.g., using the HMAC scheme in [RFC2104], 515 and attaches the MACs {a_i := MAC(H(m), k_i) | i=1,2,...,n} to 516 the message. 518 2. B receives the message m' (say, over a multipath transmission 519 scheme with chosen routes as described above). To verify that m' 520 is authentic, B computes the hash h' = H(m') and asks A's 521 neighbors to verify the respective MACs. To this end, B contacts 522 the i-th neighbor of A on a chosen route, and sends the data {h', 523 a_i'} to A's neighbor with whom A shares the secret k_i. Here, 524 the value a_i' is the MAC that B received (which could equally 525 well have been corrupted). 527 3. A's neighbor no. i uses its secret k_i to verify if MAC(h',k_i) 528 =?= a_i'. It replies the result ("yes" or "no") back over the 529 same route as how the query came in. This process happens 530 concurrently at all of A's neighbors (for i = 1, ..., n). 532 4. B collects all replies and takes either a majority decision or 533 (in the most stringent setting) rejects if any of the replies 534 comes back negative. 536 A picture of the scheme is found at 537 https://www.syssec.at/user/themes/syssec-theme/images/publikationen/ 538 MPAuth.png 540 The condition upon which B accepts A's message as authentic may 541 depend on how resilient one needs to be about an adversary 542 potentially manipulating the verification query to B. If B rejects 543 upon a single negative verification, then even an attacker that can 544 conquer only a single node on any of the chosen paths can mount a 545 denial-of-service. On the contrary, if B accepts the majority vote, 546 then the attacker needs to intercept (and manipulate) more than half 547 of the routes chosen. 549 The security of this scheme follows by similar arguments as in the 550 case for confidentiality: the scheme is secure as long as the 551 adversary cannot mount a full person-in-the-middle attack, 552 conditional on the attacker's inability to find hash-collisions (in 553 that sense, the scheme is, unlike the multipath transmission for 554 confidentiality), only computationally secure. 556 Note that confidentiality of the message against the verifying 557 neighbors is not directly addressed here beyond the point of sending 558 a hash of m for verification instead of the full message. 559 Heuristically, the message thus remains concealed to the extent of 560 the neighbor's inability to find a meaningful pre-image for the 561 received value h'. We assumed the neighbors to be honest, unless 562 being under the attacker's control, so that a denial-of-service or 563 intentionally incorrect response is in any case possible, and cannot 564 be ruled out by this protocol. 566 B.5.1. Non-Repudiation 568 Under proper graph topological properties, the above authentication 569 scheme, though based on symmetric cryptography only, shares the non- 570 repudiation feature of public-key digital signatures. In fact, if 571 the set of secrets shared between a node and its direct neighbors (or 572 a subset thereof) is unique, i.e., distinct, for each node, then no 573 other node than A can create the MAC-set attached to the message m. 574 Networks with that property are easy to recognize based on their 575 adjacency matrix [Ras18]; moreover, the "unique-neighborhood 576 property" is preserved upon the same network merging operations as 577 described above for k-vertex-connectivity. 579 B.6. Integrity 581 From the construction of Section 3.4, integrity is directly implied 582 by the use of hashes that additionally act as checksums. That is, 583 any distortion on the transmission line will with overwhelming 584 probability invalidate the MAC or inner hash, thus causing the 585 protocol to indicate this error. Conversely, if B accepts A's 586 message as authentic, integrity verification is accomplished in the 587 same blow, unless the attacker managed to forge the message as a 588 whole (in which case, integrity is also unhedgeable). 590 Authors' Addresses 592 Stafan Rass 593 Universitaet Klagenfurt 595 EMail: stefan.rass@aau.at 597 Yingzhen Qu 598 Futurewei 599 2330 Central Expressway 600 Santa Clara, CA 95050 601 USA 603 EMail: yingzhen.qu@futurewei.com 605 Lin Han 606 Futurewei 607 2330 Central Expressway 608 Santa Clara, CA 95050 609 USA 611 EMail: lin.han@futurewei.com