1 /* $OpenBSD: flowspec.c,v 1.4 2023/04/19 09:31:58 claudio Exp $ */ 2 3 /* 4 * Copyright (c) 2023 Claudio Jeker <claudio@openbsd.org> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <string.h> 20 #include <stdio.h> 21 22 #include "bgpd.h" 23 #include "rde.h" 24 25 /* 26 * Extract the next component from a flowspec NLRI buffer. 27 * Returns the length of the component including type field or -1 on failure. 28 * Also checks that the prefix encoding is valid. 29 */ 30 static int 31 flowspec_next_component(const uint8_t *buf, int len, int is_v6, int *type) 32 { 33 int vlen = 0; 34 uint8_t plen, off, op; 35 36 *type = 0; 37 if (len < 1) 38 return -1; 39 *type = buf[vlen]; 40 vlen++; 41 if (*type < FLOWSPEC_TYPE_MIN || *type >= FLOWSPEC_TYPE_MAX) 42 return -1; 43 44 switch (*type) { 45 case FLOWSPEC_TYPE_DEST: 46 case FLOWSPEC_TYPE_SOURCE: 47 if (!is_v6) { 48 /* regular RFC 4271 encoding of prefixes */ 49 if (len < vlen + 1) 50 return -1; 51 plen = buf[vlen]; 52 vlen += PREFIX_SIZE(plen); 53 if (plen > 32 || len < vlen) 54 return -1; 55 } else { 56 /* special RFC 8956 encoding with extra offset */ 57 if (len < vlen + 2) 58 return -1; 59 plen = buf[vlen]; 60 off = buf[vlen + 1]; 61 if (plen > 128 || off >= plen) 62 return -1; 63 vlen += PREFIX_SIZE(plen - off) + 1; /* off is extra */ 64 if (len < vlen) 65 return -1; 66 } 67 break; 68 case FLOWSPEC_TYPE_FLOW: 69 if (!is_v6) 70 return -1; 71 /* FALLTHROUGH */ 72 default: 73 do { 74 if (len < vlen + 1) 75 return -1; 76 op = buf[vlen]; 77 /* first component cannot have and flag set */ 78 if (vlen == 1 && op & FLOWSPEC_OP_AND) 79 return -1; 80 vlen += FLOWSPEC_OP_LEN(op) + 1; 81 82 if (len < vlen) 83 return -1; 84 } while ((op & FLOWSPEC_OP_EOL) == 0); 85 break; 86 } 87 return vlen; 88 } 89 90 #define MINIMUM(a, b) ((a) < (b) ? (a) : (b)) 91 92 /* 93 * Compare two IPv4 flowspec prefix components. 94 * Returns -1 if first prefix is preferred, 1 if second, 0 if equal. 95 */ 96 static int 97 flowspec_cmp_prefix4(const uint8_t *abuf, int ablen, const uint8_t *bbuf, 98 int bblen) 99 { 100 uint8_t a[4] = { 0 }, b[4] = { 0 }; 101 int alen, blen, clen, cmp; 102 103 alen = abuf[1]; 104 blen = bbuf[1]; 105 clen = MINIMUM(alen, blen); 106 107 /* only extract the common prefix */ 108 extract_prefix(abuf + 2, ablen - 2, &a, clen, sizeof(a)); 109 extract_prefix(bbuf + 2, bblen - 2, &b, clen, sizeof(b)); 110 111 /* lowest IP value has precedence */ 112 cmp = memcmp(a, b, sizeof(a)); 113 if (cmp < 0) 114 return -1; 115 if (cmp > 0) 116 return 1; 117 118 /* if common prefix, more specific route has precedence */ 119 if (alen > blen) 120 return -1; 121 if (alen < blen) 122 return 1; 123 return 0; 124 } 125 126 /* 127 * Compare two IPv6 flowspec prefix components. 128 * Returns 1 if first prefix is preferred, -1 if second, 0 if equal. 129 * As usual the encoding of IPv6 addresses is extra complex. 130 */ 131 static int 132 flowspec_cmp_prefix6(const uint8_t *abuf, int ablen, const uint8_t *bbuf, 133 int bblen) 134 { 135 uint8_t a[16] = { 0 }, b[16] = { 0 }; 136 int alen, blen, clen, cmp; 137 138 /* lowest offset has precedence */ 139 if (abuf[2] < bbuf[2]) 140 return -1; 141 if (abuf[2] > bbuf[2]) 142 return 1; 143 144 /* calculate actual pattern size (len - offset) */ 145 alen = abuf[1] - abuf[2]; 146 blen = bbuf[1] - bbuf[2]; 147 clen = MINIMUM(alen, blen); 148 149 /* only extract the common prefix */ 150 extract_prefix(abuf + 3, ablen - 3, &a, clen, sizeof(a)); 151 extract_prefix(bbuf + 3, bblen - 3, &b, clen, sizeof(b)); 152 153 /* lowest IP value has precedence */ 154 cmp = memcmp(a, b, sizeof(a)); 155 if (cmp < 0) 156 return -1; 157 if (cmp > 0) 158 return 1; 159 160 /* if common prefix, more specific route has precedence */ 161 if (alen > blen) 162 return -1; 163 if (alen < blen) 164 return 1; 165 return 0; 166 } 167 168 /* 169 * Check if the flowspec NLRI is syntactically valid. 170 */ 171 int 172 flowspec_valid(const uint8_t *buf, int len, int is_v6) 173 { 174 int l, type, prev = 0; 175 176 /* empty NLRI is invalid */ 177 if (len == 0) 178 return -1; 179 180 while (len > 0) { 181 l = flowspec_next_component(buf, len, is_v6, &type); 182 if (l == -1) 183 return -1; 184 /* ensure that types are ordered */ 185 if (prev >= type) 186 return -1; 187 prev = type; 188 buf += l; 189 len -= l; 190 } 191 if (len < 0) 192 return -1; 193 return 0; 194 } 195 196 /* 197 * Compare two valid flowspec NLRI objects according to RFC 8955 & 8956. 198 * Returns -1 if the first object has preference, 1 if not, and 0 if the 199 * two objects are equal. 200 */ 201 int 202 flowspec_cmp(const uint8_t *a, int alen, const uint8_t *b, int blen, int is_v6) 203 { 204 int atype, btype; 205 int acomplen, bcomplen; 206 int cmp; 207 208 while (alen > 0 && blen > 0) { 209 acomplen = flowspec_next_component(a, alen, is_v6, &atype); 210 bcomplen = flowspec_next_component(b, blen, is_v6, &btype); 211 /* should not happen */ 212 if (acomplen == -1) 213 return 1; 214 if (bcomplen == -1) 215 return -1; 216 217 /* If types differ, lowest type wins. */ 218 if (atype < btype) 219 return -1; 220 if (atype > btype) 221 return 1; 222 223 switch (atype) { 224 case FLOWSPEC_TYPE_DEST: 225 case FLOWSPEC_TYPE_SOURCE: 226 if (!is_v6) { 227 cmp = flowspec_cmp_prefix4(a, acomplen, 228 b, bcomplen); 229 } else { 230 cmp = flowspec_cmp_prefix6(a, acomplen, 231 b, bcomplen); 232 } 233 if (cmp != 0) 234 return cmp; 235 break; 236 default: 237 cmp = memcmp(a, b, MINIMUM(acomplen, bcomplen)); 238 /* 239 * Lowest common component prefix wins also 240 * if both commponents are same length also lowest 241 * string has precedence. 242 */ 243 if (cmp < 0) 244 return -1; 245 if (cmp > 0) 246 return 1; 247 /* 248 * Longest component wins when common prefix is equal. 249 * This is not really possible because EOL encoding will 250 * always tie break on the memcmp but the RFC mandates 251 * it (and it is cheap). 252 */ 253 if (acomplen > bcomplen) 254 return -1; 255 if (acomplen < bcomplen) 256 return 1; 257 break; 258 } 259 a += acomplen; 260 alen -= acomplen; 261 b += bcomplen; 262 blen -= bcomplen; 263 264 /* Rule with more components wins */ 265 if (alen > 0 && blen <= 0) 266 return -1; 267 if (alen <= 0 && blen > 0) 268 return 1; 269 } 270 return 0; 271 } 272 273 static void 274 shift_right(uint8_t *dst, const uint8_t *src, int off, int len) 275 { 276 uint8_t carry = 0; 277 int i; 278 279 dst += off / 8; /* go to inital start point */ 280 off %= 8; 281 len = (len + 7) / 8; /* how much to copy in bytes */ 282 283 for (i = 0; i < len; i++) { 284 dst[i] = carry | src[i] >> off; 285 if (off != 0) 286 carry = src[i] << (8 - off); 287 } 288 dst[i] = carry; 289 } 290 291 /* 292 * Extract a flowspec component and return its buffer and size. 293 * Returns 1 on success, 0 if component is not present and -1 on error. 294 */ 295 int 296 flowspec_get_component(const uint8_t *flow, int flowlen, int type, int is_v6, 297 const uint8_t **buf, int *len) 298 { 299 int complen, t; 300 301 *buf = NULL; 302 *len = 0; 303 304 do { 305 complen = flowspec_next_component(flow, flowlen, is_v6, &t); 306 if (complen == -1) 307 return -1; 308 if (type == t) 309 break; 310 if (type < t) 311 return 0; 312 313 flow += complen; 314 flowlen -= complen; 315 } while (1); 316 317 *buf = flow + 1; 318 *len = complen - 1; 319 320 return 1; 321 } 322 323 /* 324 * Extract source or destination address into provided bgpd_addr. 325 * Returns 1 on success, 0 if no address was present, -1 on error. 326 * Sets plen to the prefix len and olen to the offset for IPv6 case. 327 * If olen is set to NULL when an IPv6 prefix with offset is fetched 328 * the function will return -1. 329 */ 330 int 331 flowspec_get_addr(const uint8_t *flow, int flowlen, int type, int is_v6, 332 struct bgpd_addr *addr, uint8_t *plen, uint8_t *olen) 333 { 334 const uint8_t *comp; 335 int complen, rv; 336 337 memset(addr, 0, sizeof(*addr)); 338 *plen = 0; 339 if (olen != NULL) 340 *olen = 0; 341 342 rv = flowspec_get_component(flow, flowlen, type, is_v6, 343 &comp, &complen); 344 if (rv != 1) 345 return rv; 346 347 /* flowspec_get_component only returns valid encodings */ 348 if (!is_v6) { 349 addr->aid = AID_INET; 350 if (extract_prefix(comp + 1, complen - 1, &addr->v4, comp[0], 351 sizeof(addr->v4)) == -1) 352 return -1; 353 *plen = comp[0]; 354 } else { 355 uint8_t buf[16] = { 0 }; 356 int xlen, xoff = 0; 357 358 addr->aid = AID_INET6; 359 xlen = comp[0]; 360 if (comp[1] != 0) { 361 if (olen == NULL) 362 return -1; 363 xoff = comp[1]; 364 xlen -= xoff; 365 } 366 if (extract_prefix(comp + 2, complen - 2, buf, xlen, 367 sizeof(buf)) == -1) 368 return -1; 369 shift_right(addr->v6.s6_addr, buf, *olen, xlen); 370 *plen = comp[0]; 371 if (olen != NULL) 372 *olen = comp[1]; 373 } 374 375 return 1; 376 } 377 378 const char * 379 flowspec_fmt_label(int type) 380 { 381 switch (type) { 382 case FLOWSPEC_TYPE_DEST: 383 return "to"; 384 case FLOWSPEC_TYPE_SOURCE: 385 return "from"; 386 case FLOWSPEC_TYPE_PROTO: 387 return "proto"; 388 case FLOWSPEC_TYPE_PORT: 389 case FLOWSPEC_TYPE_DST_PORT: 390 case FLOWSPEC_TYPE_SRC_PORT: 391 return "port"; 392 case FLOWSPEC_TYPE_ICMP_TYPE: 393 return "icmp-type"; 394 case FLOWSPEC_TYPE_ICMP_CODE: 395 return "icmp-code"; 396 case FLOWSPEC_TYPE_TCP_FLAGS: 397 return "flags"; 398 case FLOWSPEC_TYPE_PKT_LEN: 399 return "length"; 400 case FLOWSPEC_TYPE_DSCP: 401 return "tos"; 402 case FLOWSPEC_TYPE_FRAG: 403 return "fragment"; 404 case FLOWSPEC_TYPE_FLOW: 405 return "flow"; 406 default: 407 return "???"; 408 } 409 } 410 411 static uint64_t 412 extract_val(const uint8_t *comp, int len) 413 { 414 uint64_t val = 0; 415 416 while (len-- > 0) { 417 val <<= 8; 418 val |= *comp++; 419 } 420 return val; 421 } 422 423 const char * 424 flowspec_fmt_num_op(const uint8_t *comp, int complen, int *off) 425 { 426 static char buf[32]; 427 uint64_t val, val2 = 0; 428 uint8_t op, op2 = 0; 429 int len, len2 = 0; 430 431 if (*off == -1) 432 return ""; 433 if (complen < *off + 1) 434 return "bad encoding"; 435 436 op = comp[*off]; 437 len = FLOWSPEC_OP_LEN(op) + 1; 438 if (complen < *off + len) 439 return "bad encoding"; 440 val = extract_val(comp + *off + 1, FLOWSPEC_OP_LEN(op)); 441 442 if ((op & FLOWSPEC_OP_EOL) == 0) { 443 if (complen < *off + len + 1) 444 return "bad encoding"; 445 op2 = comp[*off + len]; 446 /* 447 * Check if this is a range specification else fall back 448 * to basic rules. 449 */ 450 if (op2 & FLOWSPEC_OP_AND && 451 (op & FLOWSPEC_OP_NUM_MASK) == FLOWSPEC_OP_NUM_GE && 452 (op2 & FLOWSPEC_OP_NUM_MASK) == FLOWSPEC_OP_NUM_LE) { 453 len2 = FLOWSPEC_OP_LEN(op2) + 1; 454 val2 = extract_val(comp + *off + len + 1, 455 FLOWSPEC_OP_LEN(op2)); 456 } else 457 op2 = 0; 458 } 459 460 if (op2 & FLOWSPEC_OP_AND) { 461 /* binary range operation */ 462 snprintf(buf, sizeof(buf), "%llu - %llu", 463 (unsigned long long)val, (unsigned long long)val2); 464 } else { 465 /* unary operation */ 466 switch (op & FLOWSPEC_OP_NUM_MASK) { 467 case 0: 468 snprintf(buf, sizeof(buf), "%sfalse", 469 op & FLOWSPEC_OP_AND ? "&& " : ""); 470 break; 471 case FLOWSPEC_OP_NUM_EQ: 472 snprintf(buf, sizeof(buf), "%s%llu", 473 op & FLOWSPEC_OP_AND ? "&& " : "", 474 (unsigned long long)val); 475 break; 476 case FLOWSPEC_OP_NUM_GT: 477 snprintf(buf, sizeof(buf), "%s> %llu", 478 op & FLOWSPEC_OP_AND ? "&& " : "", 479 (unsigned long long)val); 480 break; 481 case FLOWSPEC_OP_NUM_GE: 482 snprintf(buf, sizeof(buf), "%s>= %llu", 483 op & FLOWSPEC_OP_AND ? "&& " : "", 484 (unsigned long long)val); 485 break; 486 case FLOWSPEC_OP_NUM_LT: 487 snprintf(buf, sizeof(buf), "%s< %llu", 488 op & FLOWSPEC_OP_AND ? "&& " : "", 489 (unsigned long long)val); 490 break; 491 case FLOWSPEC_OP_NUM_LE: 492 snprintf(buf, sizeof(buf), "%s<= %llu", 493 op & FLOWSPEC_OP_AND ? "&& " : "", 494 (unsigned long long)val); 495 break; 496 case FLOWSPEC_OP_NUM_NOT: 497 snprintf(buf, sizeof(buf), "%s!= %llu", 498 op & FLOWSPEC_OP_AND ? "&& " : "", 499 (unsigned long long)val); 500 break; 501 case 0x7: 502 snprintf(buf, sizeof(buf), "%strue", 503 op & FLOWSPEC_OP_AND ? "&& " : ""); 504 break; 505 } 506 } 507 508 if (op2 & FLOWSPEC_OP_EOL || op & FLOWSPEC_OP_EOL) 509 *off = -1; 510 else 511 *off += len + len2; 512 513 return buf; 514 } 515 516 static const char * 517 fmt_flags(uint64_t val, const char *bits, char *buf, size_t blen) 518 { 519 int i, bi; 520 521 for (i = 0, bi = 0; i < 64 && val != 0; i++) { 522 if (val & 1) { 523 if (bits[i] == '\0' || bits[i] == ' ') 524 goto fail; 525 buf[bi++] = bits[i]; 526 } 527 val >>= 1; 528 } 529 buf[bi++] = '\0'; 530 return buf; 531 532 fail: 533 snprintf(buf, blen, "%llx", (unsigned long long)val); 534 return buf; 535 } 536 537 const char * 538 flowspec_fmt_bin_op(const uint8_t *comp, int complen, int *off, 539 const char *bits) 540 { 541 static char buf[36], bit[17], mask[17]; 542 uint64_t val, val2 = 0; 543 uint8_t op, op2 = 0; 544 int len, len2 = 0; 545 546 if (*off == -1) 547 return ""; 548 if (complen < *off + 1) 549 return "bad encoding"; 550 551 op = comp[*off]; 552 len = FLOWSPEC_OP_LEN(op) + 1; 553 if (complen < *off + len) 554 return "bad encoding"; 555 val = extract_val(comp + *off + 1, FLOWSPEC_OP_LEN(op)); 556 557 if ((op & FLOWSPEC_OP_EOL) == 0) { 558 if (complen < *off + len + 1) 559 return "bad encoding"; 560 op2 = comp[*off + len]; 561 /* 562 * Check if this is a mask specification else fall back 563 * to basic rules. 564 */ 565 if (op2 & FLOWSPEC_OP_AND && 566 (op & FLOWSPEC_OP_BIT_MASK) == FLOWSPEC_OP_BIT_MATCH && 567 (op2 & FLOWSPEC_OP_BIT_MASK) == FLOWSPEC_OP_BIT_NOT) { 568 len2 = FLOWSPEC_OP_LEN(op2) + 1; 569 val2 = extract_val(comp + *off + len + 1, 570 FLOWSPEC_OP_LEN(op2)); 571 } else 572 op2 = 0; 573 } 574 575 if (op2 & FLOWSPEC_OP_AND) { 576 val2 |= val; 577 snprintf(buf, sizeof(buf), "%s / %s", 578 fmt_flags(val, bits, bit, sizeof(bit)), 579 fmt_flags(val2, bits, mask, sizeof(mask))); 580 } else { 581 switch (op & FLOWSPEC_OP_BIT_MASK) { 582 case 0: 583 snprintf(buf, sizeof(buf), "%s", 584 fmt_flags(val, bits, bit, sizeof(bit))); 585 break; 586 case FLOWSPEC_OP_BIT_NOT: 587 snprintf(buf, sizeof(buf), "/ %s", 588 fmt_flags(val, bits, mask, sizeof(mask))); 589 break; 590 case FLOWSPEC_OP_BIT_MATCH: 591 snprintf(buf, sizeof(buf), "%s / %s", 592 fmt_flags(val, bits, bit, sizeof(bit)), 593 fmt_flags(val, bits, mask, sizeof(mask))); 594 break; 595 case FLOWSPEC_OP_BIT_NOT | FLOWSPEC_OP_BIT_MATCH: 596 snprintf(buf, sizeof(buf), "???"); 597 break; 598 } 599 } 600 601 if (op2 & FLOWSPEC_OP_EOL || op & FLOWSPEC_OP_EOL) 602 *off = -1; 603 else 604 *off += len + len2; 605 606 return buf; 607 } 608