1 /* 2 ** Copyright (c) 2015, Asim Jamshed, Robin Sommer, Seth Hall 3 ** and the International Computer Science Institute. All rights reserved. 4 ** 5 ** Redistribution and use in source and binary forms, with or without 6 ** modification, are permitted provided that the following conditions are met: 7 ** 8 ** (1) Redistributions of source code must retain the above copyright 9 ** notice, this list of conditions and the following disclaimer. 10 ** 11 ** (2) Redistributions in binary form must reproduce the above copyright 12 ** notice, this list of conditions and the following disclaimer in the 13 ** documentation and/or other materials provided with the distribution. 14 ** 15 ** 16 ** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 ** AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 ** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 ** ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20 ** LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 ** CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 ** SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 ** INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 ** CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 ** ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 ** POSSIBILITY OF SUCH DAMAGE. 27 **/ 28 29 /* for func prototypes */ 30 #include "pkt_hash.h" 31 32 /* Make Linux headers choose BSD versions of some of the data structures */ 33 #define __FAVOR_BSD 34 35 /* for types */ 36 #include <sys/types.h> 37 /* for [n/h]to[h/n][ls] */ 38 #include <netinet/in.h> 39 /* iphdr */ 40 #include <netinet/ip.h> 41 /* ipv6hdr */ 42 #include <netinet/ip6.h> 43 /* tcphdr */ 44 #include <netinet/tcp.h> 45 /* udphdr */ 46 #include <netinet/udp.h> 47 /* eth hdr */ 48 #include <net/ethernet.h> 49 /* for memset */ 50 #include <string.h> 51 52 #include <stdio.h> 53 #include <assert.h> 54 55 //#include <libnet.h> 56 /*---------------------------------------------------------------------*/ 57 /** 58 * * The cache table is used to pick a nice seed for the hash value. It is 59 * * built only once when sym_hash_fn is called for the very first time 60 * */ 61 static void 62 build_sym_key_cache(uint32_t *cache, int cache_len) 63 { 64 static const uint8_t key[] = { 0x50, 0x6d }; 65 66 uint32_t result = (((uint32_t)key[0]) << 24) | 67 (((uint32_t)key[1]) << 16) | 68 (((uint32_t)key[0]) << 8) | 69 ((uint32_t)key[1]); 70 71 uint32_t idx = 32; 72 int i; 73 74 for (i = 0; i < cache_len; i++, idx++) { 75 uint8_t shift = (idx % 8); 76 uint32_t bit; 77 78 cache[i] = result; 79 bit = ((key[(idx/8) & 1] << shift) & 0x80) ? 1 : 0; 80 result = ((result << 1) | bit); 81 } 82 } 83 84 static void 85 build_byte_cache(uint32_t byte_cache[256][4]) 86 { 87 #define KEY_CACHE_LEN 96 88 int i, j, k; 89 uint32_t key_cache[KEY_CACHE_LEN]; 90 91 build_sym_key_cache(key_cache, KEY_CACHE_LEN); 92 93 for (i = 0; i < 4; i++) { 94 for (j = 0; j < 256; j++) { 95 uint8_t b = j; 96 byte_cache[j][i] = 0; 97 for (k = 0; k < 8; k++) { 98 if (b & 0x80) 99 byte_cache[j][i] ^= key_cache[8 * i + k]; 100 b <<= 1U; 101 } 102 } 103 } 104 } 105 106 107 /*---------------------------------------------------------------------*/ 108 /** 109 ** Computes symmetric hash based on the 4-tuple header data 110 **/ 111 static uint32_t 112 sym_hash_fn(uint32_t sip, uint32_t dip, uint16_t sp, uint32_t dp) 113 { 114 uint32_t rc = 0; 115 static int first_time = 1; 116 static uint32_t byte_cache[256][4]; 117 uint8_t *sip_b = (uint8_t *)&sip, 118 *dip_b = (uint8_t *)&dip, 119 *sp_b = (uint8_t *)&sp, 120 *dp_b = (uint8_t *)&dp; 121 122 if (first_time) { 123 build_byte_cache(byte_cache); 124 first_time = 0; 125 } 126 127 rc = byte_cache[sip_b[3]][0] ^ 128 byte_cache[sip_b[2]][1] ^ 129 byte_cache[sip_b[1]][2] ^ 130 byte_cache[sip_b[0]][3] ^ 131 byte_cache[dip_b[3]][0] ^ 132 byte_cache[dip_b[2]][1] ^ 133 byte_cache[dip_b[1]][2] ^ 134 byte_cache[dip_b[0]][3] ^ 135 byte_cache[sp_b[1]][0] ^ 136 byte_cache[sp_b[0]][1] ^ 137 byte_cache[dp_b[1]][2] ^ 138 byte_cache[dp_b[0]][3]; 139 140 return rc; 141 } 142 static uint32_t decode_gre_hash(const uint8_t *, uint8_t, uint8_t); 143 /*---------------------------------------------------------------------*/ 144 /** 145 ** Parser + hash function for the IPv4 packet 146 **/ 147 static uint32_t 148 decode_ip_n_hash(const struct ip *iph, uint8_t hash_split, uint8_t seed) 149 { 150 uint32_t rc = 0; 151 152 if (iph->ip_hl < 5 || iph->ip_hl * 4 > iph->ip_len) { 153 rc = 0; 154 } else if (hash_split == 2) { 155 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 156 ntohl(iph->ip_dst.s_addr), 157 ntohs(0xFFFD) + seed, 158 ntohs(0xFFFE) + seed); 159 } else { 160 const struct tcphdr *tcph = NULL; 161 const struct udphdr *udph = NULL; 162 163 switch (iph->ip_p) { 164 case IPPROTO_TCP: 165 tcph = (const struct tcphdr *)((const uint8_t *)iph + (iph->ip_hl<<2)); 166 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 167 ntohl(iph->ip_dst.s_addr), 168 ntohs(tcph->th_sport) + seed, 169 ntohs(tcph->th_dport) + seed); 170 break; 171 case IPPROTO_UDP: 172 udph = (const struct udphdr *)((const uint8_t *)iph + (iph->ip_hl<<2)); 173 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 174 ntohl(iph->ip_dst.s_addr), 175 ntohs(udph->uh_sport) + seed, 176 ntohs(udph->uh_dport) + seed); 177 break; 178 case IPPROTO_IPIP: 179 /* tunneling */ 180 rc = decode_ip_n_hash((const struct ip *)((const uint8_t *)iph + (iph->ip_hl<<2)), 181 hash_split, seed); 182 break; 183 case IPPROTO_GRE: 184 rc = decode_gre_hash((const uint8_t *)iph + (iph->ip_hl<<2), 185 hash_split, seed); 186 break; 187 case IPPROTO_ICMP: 188 case IPPROTO_ESP: 189 case IPPROTO_PIM: 190 case IPPROTO_IGMP: 191 default: 192 /* 193 ** the hash strength (although weaker but) should still hold 194 ** even with 2 fields 195 **/ 196 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 197 ntohl(iph->ip_dst.s_addr), 198 ntohs(0xFFFD) + seed, 199 ntohs(0xFFFE) + seed); 200 break; 201 } 202 } 203 return rc; 204 } 205 /*---------------------------------------------------------------------*/ 206 /** 207 ** Parser + hash function for the IPv6 packet 208 **/ 209 static uint32_t 210 decode_ipv6_n_hash(const struct ip6_hdr *ipv6h, uint8_t hash_split, uint8_t seed) 211 { 212 uint32_t saddr, daddr; 213 uint32_t rc = 0; 214 215 /* Get only the first 4 octets */ 216 saddr = ipv6h->ip6_src.s6_addr[0] | 217 (ipv6h->ip6_src.s6_addr[1] << 8) | 218 (ipv6h->ip6_src.s6_addr[2] << 16) | 219 (ipv6h->ip6_src.s6_addr[3] << 24); 220 daddr = ipv6h->ip6_dst.s6_addr[0] | 221 (ipv6h->ip6_dst.s6_addr[1] << 8) | 222 (ipv6h->ip6_dst.s6_addr[2] << 16) | 223 (ipv6h->ip6_dst.s6_addr[3] << 24); 224 225 if (hash_split == 2) { 226 rc = sym_hash_fn(ntohl(saddr), 227 ntohl(daddr), 228 ntohs(0xFFFD) + seed, 229 ntohs(0xFFFE) + seed); 230 } else { 231 const struct tcphdr *tcph = NULL; 232 const struct udphdr *udph = NULL; 233 234 switch(ntohs(ipv6h->ip6_ctlun.ip6_un1.ip6_un1_nxt)) { 235 case IPPROTO_TCP: 236 tcph = (const struct tcphdr *)(ipv6h + 1); 237 rc = sym_hash_fn(ntohl(saddr), 238 ntohl(daddr), 239 ntohs(tcph->th_sport) + seed, 240 ntohs(tcph->th_dport) + seed); 241 break; 242 case IPPROTO_UDP: 243 udph = (const struct udphdr *)(ipv6h + 1); 244 rc = sym_hash_fn(ntohl(saddr), 245 ntohl(daddr), 246 ntohs(udph->uh_sport) + seed, 247 ntohs(udph->uh_dport) + seed); 248 break; 249 case IPPROTO_IPIP: 250 /* tunneling */ 251 rc = decode_ip_n_hash((const struct ip *)(ipv6h + 1), 252 hash_split, seed); 253 break; 254 case IPPROTO_IPV6: 255 /* tunneling */ 256 rc = decode_ipv6_n_hash((const struct ip6_hdr *)(ipv6h + 1), 257 hash_split, seed); 258 break; 259 case IPPROTO_GRE: 260 rc = decode_gre_hash((const uint8_t *)(ipv6h + 1), hash_split, seed); 261 break; 262 case IPPROTO_ICMP: 263 case IPPROTO_ESP: 264 case IPPROTO_PIM: 265 case IPPROTO_IGMP: 266 default: 267 /* 268 ** the hash strength (although weaker but) should still hold 269 ** even with 2 fields 270 **/ 271 rc = sym_hash_fn(ntohl(saddr), 272 ntohl(daddr), 273 ntohs(0xFFFD) + seed, 274 ntohs(0xFFFE) + seed); 275 } 276 } 277 return rc; 278 } 279 /*---------------------------------------------------------------------*/ 280 /** 281 * * A temp solution while hash for other protocols are filled... 282 * * (See decode_vlan_n_hash & pkt_hdr_hash functions). 283 * */ 284 static uint32_t 285 decode_others_n_hash(const struct ether_header *ethh, uint8_t seed) 286 { 287 uint32_t saddr, daddr, rc; 288 289 saddr = ethh->ether_shost[5] | 290 (ethh->ether_shost[4] << 8) | 291 (ethh->ether_shost[3] << 16) | 292 (ethh->ether_shost[2] << 24); 293 daddr = ethh->ether_dhost[5] | 294 (ethh->ether_dhost[4] << 8) | 295 (ethh->ether_dhost[3] << 16) | 296 (ethh->ether_dhost[2] << 24); 297 298 rc = sym_hash_fn(ntohl(saddr), 299 ntohl(daddr), 300 ntohs(0xFFFD) + seed, 301 ntohs(0xFFFE) + seed); 302 303 return rc; 304 } 305 /*---------------------------------------------------------------------*/ 306 /** 307 ** Parser + hash function for VLAN packet 308 **/ 309 static inline uint32_t 310 decode_vlan_n_hash(const struct ether_header *ethh, uint8_t hash_split, uint8_t seed) 311 { 312 uint32_t rc = 0; 313 const struct vlanhdr *vhdr = (const struct vlanhdr *)(ethh + 1); 314 315 switch (ntohs(vhdr->proto)) { 316 case ETHERTYPE_IP: 317 rc = decode_ip_n_hash((const struct ip *)(vhdr + 1), 318 hash_split, seed); 319 break; 320 case ETHERTYPE_IPV6: 321 rc = decode_ipv6_n_hash((const struct ip6_hdr *)(vhdr + 1), 322 hash_split, seed); 323 break; 324 case ETHERTYPE_ARP: 325 default: 326 /* others */ 327 rc = decode_others_n_hash(ethh, seed); 328 break; 329 } 330 return rc; 331 } 332 333 /*---------------------------------------------------------------------*/ 334 /** 335 ** General parser + hash function... 336 **/ 337 uint32_t 338 pkt_hdr_hash(const unsigned char *buffer, uint8_t hash_split, uint8_t seed) 339 { 340 uint32_t rc = 0; 341 const struct ether_header *ethh = (const struct ether_header *)buffer; 342 343 switch (ntohs(ethh->ether_type)) { 344 case ETHERTYPE_IP: 345 rc = decode_ip_n_hash((const struct ip *)(ethh + 1), 346 hash_split, seed); 347 break; 348 case ETHERTYPE_IPV6: 349 rc = decode_ipv6_n_hash((const struct ip6_hdr *)(ethh + 1), 350 hash_split, seed); 351 break; 352 case ETHERTYPE_VLAN: 353 rc = decode_vlan_n_hash(ethh, hash_split, seed); 354 break; 355 case ETHERTYPE_ARP: 356 default: 357 /* others */ 358 rc = decode_others_n_hash(ethh, seed); 359 break; 360 } 361 362 return rc; 363 } 364 365 /*---------------------------------------------------------------------*/ 366 /** 367 ** Parser + hash function for the GRE packet 368 **/ 369 static uint32_t 370 decode_gre_hash(const uint8_t *grehdr, uint8_t hash_split, uint8_t seed) 371 { 372 uint32_t rc = 0; 373 int len = 4 + 2 * (!!(*grehdr & 1) + /* Checksum */ 374 !!(*grehdr & 2) + /* Routing */ 375 !!(*grehdr & 4) + /* Key */ 376 !!(*grehdr & 8)); /* Sequence Number */ 377 uint16_t proto = ntohs(*(const uint16_t *)(const void *)(grehdr + 2)); 378 379 switch (proto) { 380 case ETHERTYPE_IP: 381 rc = decode_ip_n_hash((const struct ip *)(grehdr + len), 382 hash_split, seed); 383 break; 384 case ETHERTYPE_IPV6: 385 rc = decode_ipv6_n_hash((const struct ip6_hdr *)(grehdr + len), 386 hash_split, seed); 387 break; 388 case 0x6558: /* Transparent Ethernet Bridging */ 389 rc = pkt_hdr_hash(grehdr + len, hash_split, seed); 390 break; 391 default: 392 /* others */ 393 break; 394 } 395 return rc; 396 } 397 /*---------------------------------------------------------------------*/ 398 399