1 /* $OpenBSD: flowspec.c,v 1.5 2023/10/23 13:07:44 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
flowspec_next_component(const uint8_t * buf,int len,int is_v6,int * type)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
flowspec_cmp_prefix4(const uint8_t * abuf,int ablen,const uint8_t * bbuf,int bblen)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
flowspec_cmp_prefix6(const uint8_t * abuf,int ablen,const uint8_t * bbuf,int bblen)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
flowspec_valid(const uint8_t * buf,int len,int is_v6)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
flowspec_cmp(const uint8_t * a,int alen,const uint8_t * b,int blen,int is_v6)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
shift_right(uint8_t * dst,const uint8_t * src,int off,int len)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
flowspec_get_component(const uint8_t * flow,int flowlen,int type,int is_v6,const uint8_t ** buf,int * len)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
flowspec_get_addr(const uint8_t * flow,int flowlen,int type,int is_v6,struct bgpd_addr * addr,uint8_t * plen,uint8_t * olen)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, xoff, xlen);
370 *plen = comp[0];
371 if (olen != NULL)
372 *olen = comp[1];
373 }
374
375 return 1;
376 }
377
378 const char *
flowspec_fmt_label(int type)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
extract_val(const uint8_t * comp,int len)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 *
flowspec_fmt_num_op(const uint8_t * comp,int complen,int * off)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 *
fmt_flags(uint64_t val,const char * bits,char * buf,size_t blen)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 *
flowspec_fmt_bin_op(const uint8_t * comp,int complen,int * off,const char * bits)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