From d8a4e42b7d19a87eacc00c825e913907a58f39ee Mon Sep 17 00:00:00 2001 From: JR Rivers Date: Thu, 13 Sep 2012 17:17:36 +0000 Subject: lib: improve fletcher checksum validation OVERVIEW The checksum used in OSPF (rfc2328) is specified in rc905 annex B. There is an sample implementation in rfc1008 which forms the basis of the quagga implementation. This algorithm works perfectly when generating a checksum; however, validation is a bit problematic. The following LSA (generated by a non-quagga implementation) is received by quagga and marked with an invalid checksum; however, it passes both the rfc905 and rfc1008 validation checks. static uint8_t lsa_10_121_233_29[] = { 0x0e, 0x10, 0x02, 0x03, 0x09, 0x00, 0x35, 0x40, 0x0a, 0x79, 0xe9, 0x1d, 0x80, 0x00, 0x00, 0x03, 0x00, 0x8a, 0x00, 0x1c, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x36, 0xb0 }; LS Type: Summary-LSA (IP network) LS Age: 3600 seconds Do Not Age: False Options: 0x02 (E) Link-State Advertisement Type: Summary-LSA (IP network) (3) Link State ID: 9.0.53.64 Advertising Router: 10.121.233.29 (10.121.233.29) LS Sequence Number: 0x80000003 LS Checksum: 0x008a Length: 28 Netmask: 255.255.255.224 Metric: 14000 You'll note that one byte of the checksum is 0x00; quagga would calculate the checksum as 0xff8a. It can be argued that the sourcing implementation generates an incorrect checksum; however, rfc905 indicates that, for 1's complement arithmetic, the value 255 shall be regarded as 0, thus either values are valid. EXPLANATION The quagga ospfd and ospf6d implementations operate by copying the PDU's existing checksum in a holding variable, calculating the checksum, and comparing the resulting checksum to the original. As a note, this implementation has the side effect of modifying the contents of the PDU. Evaluation of both rfc905 and rfc1008 shows that checksum validation should involve calculating the sum over the PDU and checking that both resulting C0 and C1 values are zero. This behavior is enacted in the rfc1008 implementation by calling encodecc with k = 0 (checksum offset); however, this functionality had been omitted from the quagga implementation. PATCH This patch adds the ability to call the quagga's fletcher_checksum() with a checksum offset value of 0xffff (aka FLETCHER_CHECKSUM_VALIDATE) which returns the sum over the buffer (a value of 0 indicates a valid checksum). This is similar to the mechanism in rfc1008 when called with k = 0. The patch also introduces ospf_lsa_checksum_valid(). ospf6d had it's own implementation of the fletcher checksum in ospf6_lsa_checksum(); it's the same algorithm as in fletcher_checksum(). This patch removes the local implementation in favor of the library's as well as creates and uses ospf6_lsa_checksum_valid(). quagga's ISIS implementation suffers from the same problem; however, I do not have the facilities to validate a fix to ISIS, thus this change has been left to the ISIS maintainers. The function iso_csum_verify() should be reduced to running the fletcher checksum over the buffer using an offset of 0. Signed-off-by: JR Rivers Reviewed-by: Scott Feldman Reviewed-by: Nolan Leake Reviewed-by: Ayan Banerjee Reviewed-by: Shrijeet Mukherjee Signed-off-by: David Lamparter --- ospf6d/ospf6_flood.c | 4 +--- ospf6d/ospf6_lsa.c | 54 +++++++++++++++++++++------------------------------- ospf6d/ospf6_lsa.h | 1 + 3 files changed, 24 insertions(+), 35 deletions(-) (limited to 'ospf6d') diff --git a/ospf6d/ospf6_flood.c b/ospf6d/ospf6_flood.c index 670c5d1d..b8159729 100644 --- a/ospf6d/ospf6_flood.c +++ b/ospf6d/ospf6_flood.c @@ -733,7 +733,6 @@ ospf6_receive_lsa (struct ospf6_neighbor *from, { struct ospf6_lsa *new = NULL, *old = NULL, *rem = NULL; int ismore_recent; - unsigned short cksum; int is_debug = 0; ismore_recent = 1; @@ -751,8 +750,7 @@ ospf6_receive_lsa (struct ospf6_neighbor *from, } /* (1) LSA Checksum */ - cksum = ntohs (new->header->checksum); - if (ntohs (ospf6_lsa_checksum (new->header)) != cksum) + if (! ospf6_lsa_checksum_valid (new->header)) { if (is_debug) zlog_debug ("Wrong LSA Checksum, discard"); diff --git a/ospf6d/ospf6_lsa.c b/ospf6d/ospf6_lsa.c index e65752d8..ff061dfb 100644 --- a/ospf6d/ospf6_lsa.c +++ b/ospf6d/ospf6_lsa.c @@ -29,6 +29,7 @@ #include "command.h" #include "memory.h" #include "thread.h" +#include "checksum.h" #include "ospf6_proto.h" #include "ospf6_lsa.h" @@ -672,47 +673,36 @@ ospf6_lsa_refresh (struct thread *thread) -/* enhanced Fletcher checksum algorithm, RFC1008 7.2 */ -#define MODX 4102 -#define LSA_CHECKSUM_OFFSET 15 +/* Fletcher Checksum -- Refer to RFC1008. */ +/* All the offsets are zero-based. The offsets in the RFC1008 are + one-based. */ unsigned short ospf6_lsa_checksum (struct ospf6_lsa_header *lsa_header) { - u_char *sp, *ep, *p, *q; - int c0 = 0, c1 = 0; - int x, y; - u_int16_t length; + u_char *buffer = (u_char *) &lsa_header->type; + int type_offset = buffer - (u_char *) &lsa_header->age; /* should be 2 */ - lsa_header->checksum = 0; - length = ntohs (lsa_header->length) - 2; - sp = (u_char *) &lsa_header->type; + /* Skip the AGE field */ + u_int16_t len = ntohs(lsa_header->length) - type_offset; - for (ep = sp + length; sp < ep; sp = q) - { - q = sp + MODX; - if (q > ep) - q = ep; - for (p = sp; p < q; p++) - { - c0 += *p; - c1 += c0; - } - c0 %= 255; - c1 %= 255; - } + /* Checksum offset starts from "type" field, not the beginning of the + lsa_header struct. The offset is 14, rather than 16. */ + int checksum_offset = (u_char *) &lsa_header->checksum - buffer; + + return (unsigned short)fletcher_checksum(buffer, len, checksum_offset); +} - /* r = (c1 << 8) + c0; */ - x = ((length - LSA_CHECKSUM_OFFSET) * c0 - c1) % 255; - if (x <= 0) - x += 255; - y = 510 - c0 - x; - if (y > 255) - y -= 255; +int +ospf6_lsa_checksum_valid (struct ospf6_lsa_header *lsa_header) +{ + u_char *buffer = (u_char *) &lsa_header->type; + int type_offset = buffer - (u_char *) &lsa_header->age; /* should be 2 */ - lsa_header->checksum = htons ((x << 8) + y); + /* Skip the AGE field */ + u_int16_t len = ntohs(lsa_header->length) - type_offset; - return (lsa_header->checksum); + return (fletcher_checksum(buffer, len, FLETCHER_CHECKSUM_VALIDATE) == 0); } void diff --git a/ospf6d/ospf6_lsa.h b/ospf6d/ospf6_lsa.h index 7d93f5cb..263411fc 100644 --- a/ospf6d/ospf6_lsa.h +++ b/ospf6d/ospf6_lsa.h @@ -237,6 +237,7 @@ extern int ospf6_lsa_expire (struct thread *); extern int ospf6_lsa_refresh (struct thread *); extern unsigned short ospf6_lsa_checksum (struct ospf6_lsa_header *); +extern int ospf6_lsa_checksum_valid (struct ospf6_lsa_header *); extern int ospf6_lsa_prohibited_duration (u_int16_t type, u_int32_t id, u_int32_t adv_router, void *scope); -- cgit v1.2.1