1 /* 2 * xfrm_replay.c - xfrm replay detection, derived from xfrm_state.c. 3 * 4 * Copyright (C) 2010 secunet Security Networks AG 5 * Copyright (C) 2010 Steffen Klassert <steffen.klassert@secunet.com> 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms and conditions of the GNU General Public License, 9 * version 2, as published by the Free Software Foundation. 10 * 11 * This program is distributed in the hope it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 14 * more details. 15 * 16 * You should have received a copy of the GNU General Public License along with 17 * this program; if not, write to the Free Software Foundation, Inc., 18 * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. 19 */ 20 21 #include <linux/export.h> 22 #include <net/xfrm.h> 23 24 u32 xfrm_replay_seqhi(struct xfrm_state *x, __be32 net_seq) 25 { 26 u32 seq, seq_hi, bottom; 27 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 28 29 if (!(x->props.flags & XFRM_STATE_ESN)) 30 return 0; 31 32 seq = ntohl(net_seq); 33 seq_hi = replay_esn->seq_hi; 34 bottom = replay_esn->seq - replay_esn->replay_window + 1; 35 36 if (likely(replay_esn->seq >= replay_esn->replay_window - 1)) { 37 /* A. same subspace */ 38 if (unlikely(seq < bottom)) 39 seq_hi++; 40 } else { 41 /* B. window spans two subspaces */ 42 if (unlikely(seq >= bottom)) 43 seq_hi--; 44 } 45 46 return seq_hi; 47 } 48 49 static void xfrm_replay_notify(struct xfrm_state *x, int event) 50 { 51 struct km_event c; 52 /* we send notify messages in case 53 * 1. we updated on of the sequence numbers, and the seqno difference 54 * is at least x->replay_maxdiff, in this case we also update the 55 * timeout of our timer function 56 * 2. if x->replay_maxage has elapsed since last update, 57 * and there were changes 58 * 59 * The state structure must be locked! 60 */ 61 62 switch (event) { 63 case XFRM_REPLAY_UPDATE: 64 if (!x->replay_maxdiff || 65 ((x->replay.seq - x->preplay.seq < x->replay_maxdiff) && 66 (x->replay.oseq - x->preplay.oseq < x->replay_maxdiff))) { 67 if (x->xflags & XFRM_TIME_DEFER) 68 event = XFRM_REPLAY_TIMEOUT; 69 else 70 return; 71 } 72 73 break; 74 75 case XFRM_REPLAY_TIMEOUT: 76 if (memcmp(&x->replay, &x->preplay, 77 sizeof(struct xfrm_replay_state)) == 0) { 78 x->xflags |= XFRM_TIME_DEFER; 79 return; 80 } 81 82 break; 83 } 84 85 memcpy(&x->preplay, &x->replay, sizeof(struct xfrm_replay_state)); 86 c.event = XFRM_MSG_NEWAE; 87 c.data.aevent = event; 88 km_state_notify(x, &c); 89 90 if (x->replay_maxage && 91 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 92 x->xflags &= ~XFRM_TIME_DEFER; 93 } 94 95 static int xfrm_replay_overflow(struct xfrm_state *x, struct sk_buff *skb) 96 { 97 int err = 0; 98 struct net *net = xs_net(x); 99 100 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 101 XFRM_SKB_CB(skb)->seq.output.low = ++x->replay.oseq; 102 XFRM_SKB_CB(skb)->seq.output.hi = 0; 103 if (unlikely(x->replay.oseq == 0)) { 104 x->replay.oseq--; 105 xfrm_audit_state_replay_overflow(x, skb); 106 err = -EOVERFLOW; 107 108 return err; 109 } 110 if (xfrm_aevent_is_on(net)) 111 x->repl->notify(x, XFRM_REPLAY_UPDATE); 112 } 113 114 return err; 115 } 116 117 static int xfrm_replay_check(struct xfrm_state *x, 118 struct sk_buff *skb, __be32 net_seq) 119 { 120 u32 diff; 121 u32 seq = ntohl(net_seq); 122 123 if (!x->props.replay_window) 124 return 0; 125 126 if (unlikely(seq == 0)) 127 goto err; 128 129 if (likely(seq > x->replay.seq)) 130 return 0; 131 132 diff = x->replay.seq - seq; 133 if (diff >= x->props.replay_window) { 134 x->stats.replay_window++; 135 goto err; 136 } 137 138 if (x->replay.bitmap & (1U << diff)) { 139 x->stats.replay++; 140 goto err; 141 } 142 return 0; 143 144 err: 145 xfrm_audit_state_replay(x, skb, net_seq); 146 return -EINVAL; 147 } 148 149 static void xfrm_replay_advance(struct xfrm_state *x, __be32 net_seq) 150 { 151 u32 diff; 152 u32 seq = ntohl(net_seq); 153 154 if (!x->props.replay_window) 155 return; 156 157 if (seq > x->replay.seq) { 158 diff = seq - x->replay.seq; 159 if (diff < x->props.replay_window) 160 x->replay.bitmap = ((x->replay.bitmap) << diff) | 1; 161 else 162 x->replay.bitmap = 1; 163 x->replay.seq = seq; 164 } else { 165 diff = x->replay.seq - seq; 166 x->replay.bitmap |= (1U << diff); 167 } 168 169 if (xfrm_aevent_is_on(xs_net(x))) 170 x->repl->notify(x, XFRM_REPLAY_UPDATE); 171 } 172 173 static int xfrm_replay_overflow_bmp(struct xfrm_state *x, struct sk_buff *skb) 174 { 175 int err = 0; 176 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 177 struct net *net = xs_net(x); 178 179 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 180 XFRM_SKB_CB(skb)->seq.output.low = ++replay_esn->oseq; 181 XFRM_SKB_CB(skb)->seq.output.hi = 0; 182 if (unlikely(replay_esn->oseq == 0)) { 183 replay_esn->oseq--; 184 xfrm_audit_state_replay_overflow(x, skb); 185 err = -EOVERFLOW; 186 187 return err; 188 } 189 if (xfrm_aevent_is_on(net)) 190 x->repl->notify(x, XFRM_REPLAY_UPDATE); 191 } 192 193 return err; 194 } 195 196 static int xfrm_replay_check_bmp(struct xfrm_state *x, 197 struct sk_buff *skb, __be32 net_seq) 198 { 199 unsigned int bitnr, nr; 200 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 201 u32 pos; 202 u32 seq = ntohl(net_seq); 203 u32 diff = replay_esn->seq - seq; 204 205 if (!replay_esn->replay_window) 206 return 0; 207 208 if (unlikely(seq == 0)) 209 goto err; 210 211 if (likely(seq > replay_esn->seq)) 212 return 0; 213 214 if (diff >= replay_esn->replay_window) { 215 x->stats.replay_window++; 216 goto err; 217 } 218 219 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 220 221 if (pos >= diff) 222 bitnr = (pos - diff) % replay_esn->replay_window; 223 else 224 bitnr = replay_esn->replay_window - (diff - pos); 225 226 nr = bitnr >> 5; 227 bitnr = bitnr & 0x1F; 228 if (replay_esn->bmp[nr] & (1U << bitnr)) 229 goto err_replay; 230 231 return 0; 232 233 err_replay: 234 x->stats.replay++; 235 err: 236 xfrm_audit_state_replay(x, skb, net_seq); 237 return -EINVAL; 238 } 239 240 static void xfrm_replay_advance_bmp(struct xfrm_state *x, __be32 net_seq) 241 { 242 unsigned int bitnr, nr, i; 243 u32 diff; 244 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 245 u32 seq = ntohl(net_seq); 246 u32 pos; 247 248 if (!replay_esn->replay_window) 249 return; 250 251 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 252 253 if (seq > replay_esn->seq) { 254 diff = seq - replay_esn->seq; 255 256 if (diff < replay_esn->replay_window) { 257 for (i = 1; i < diff; i++) { 258 bitnr = (pos + i) % replay_esn->replay_window; 259 nr = bitnr >> 5; 260 bitnr = bitnr & 0x1F; 261 replay_esn->bmp[nr] &= ~(1U << bitnr); 262 } 263 } else { 264 nr = (replay_esn->replay_window - 1) >> 5; 265 for (i = 0; i <= nr; i++) 266 replay_esn->bmp[i] = 0; 267 } 268 269 bitnr = (pos + diff) % replay_esn->replay_window; 270 replay_esn->seq = seq; 271 } else { 272 diff = replay_esn->seq - seq; 273 274 if (pos >= diff) 275 bitnr = (pos - diff) % replay_esn->replay_window; 276 else 277 bitnr = replay_esn->replay_window - (diff - pos); 278 } 279 280 nr = bitnr >> 5; 281 bitnr = bitnr & 0x1F; 282 replay_esn->bmp[nr] |= (1U << bitnr); 283 284 if (xfrm_aevent_is_on(xs_net(x))) 285 x->repl->notify(x, XFRM_REPLAY_UPDATE); 286 } 287 288 static void xfrm_replay_notify_bmp(struct xfrm_state *x, int event) 289 { 290 struct km_event c; 291 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 292 struct xfrm_replay_state_esn *preplay_esn = x->preplay_esn; 293 294 /* we send notify messages in case 295 * 1. we updated on of the sequence numbers, and the seqno difference 296 * is at least x->replay_maxdiff, in this case we also update the 297 * timeout of our timer function 298 * 2. if x->replay_maxage has elapsed since last update, 299 * and there were changes 300 * 301 * The state structure must be locked! 302 */ 303 304 switch (event) { 305 case XFRM_REPLAY_UPDATE: 306 if (!x->replay_maxdiff || 307 ((replay_esn->seq - preplay_esn->seq < x->replay_maxdiff) && 308 (replay_esn->oseq - preplay_esn->oseq 309 < x->replay_maxdiff))) { 310 if (x->xflags & XFRM_TIME_DEFER) 311 event = XFRM_REPLAY_TIMEOUT; 312 else 313 return; 314 } 315 316 break; 317 318 case XFRM_REPLAY_TIMEOUT: 319 if (memcmp(x->replay_esn, x->preplay_esn, 320 xfrm_replay_state_esn_len(replay_esn)) == 0) { 321 x->xflags |= XFRM_TIME_DEFER; 322 return; 323 } 324 325 break; 326 } 327 328 memcpy(x->preplay_esn, x->replay_esn, 329 xfrm_replay_state_esn_len(replay_esn)); 330 c.event = XFRM_MSG_NEWAE; 331 c.data.aevent = event; 332 km_state_notify(x, &c); 333 334 if (x->replay_maxage && 335 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 336 x->xflags &= ~XFRM_TIME_DEFER; 337 } 338 339 static void xfrm_replay_notify_esn(struct xfrm_state *x, int event) 340 { 341 u32 seq_diff, oseq_diff; 342 struct km_event c; 343 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 344 struct xfrm_replay_state_esn *preplay_esn = x->preplay_esn; 345 346 /* we send notify messages in case 347 * 1. we updated on of the sequence numbers, and the seqno difference 348 * is at least x->replay_maxdiff, in this case we also update the 349 * timeout of our timer function 350 * 2. if x->replay_maxage has elapsed since last update, 351 * and there were changes 352 * 353 * The state structure must be locked! 354 */ 355 356 switch (event) { 357 case XFRM_REPLAY_UPDATE: 358 if (x->replay_maxdiff) { 359 if (replay_esn->seq_hi == preplay_esn->seq_hi) 360 seq_diff = replay_esn->seq - preplay_esn->seq; 361 else 362 seq_diff = ~preplay_esn->seq + replay_esn->seq 363 + 1; 364 365 if (replay_esn->oseq_hi == preplay_esn->oseq_hi) 366 oseq_diff = replay_esn->oseq 367 - preplay_esn->oseq; 368 else 369 oseq_diff = ~preplay_esn->oseq 370 + replay_esn->oseq + 1; 371 372 if (seq_diff >= x->replay_maxdiff || 373 oseq_diff >= x->replay_maxdiff) 374 break; 375 } 376 377 if (x->xflags & XFRM_TIME_DEFER) 378 event = XFRM_REPLAY_TIMEOUT; 379 else 380 return; 381 382 break; 383 384 case XFRM_REPLAY_TIMEOUT: 385 if (memcmp(x->replay_esn, x->preplay_esn, 386 xfrm_replay_state_esn_len(replay_esn)) == 0) { 387 x->xflags |= XFRM_TIME_DEFER; 388 return; 389 } 390 391 break; 392 } 393 394 memcpy(x->preplay_esn, x->replay_esn, 395 xfrm_replay_state_esn_len(replay_esn)); 396 c.event = XFRM_MSG_NEWAE; 397 c.data.aevent = event; 398 km_state_notify(x, &c); 399 400 if (x->replay_maxage && 401 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 402 x->xflags &= ~XFRM_TIME_DEFER; 403 } 404 405 static int xfrm_replay_overflow_esn(struct xfrm_state *x, struct sk_buff *skb) 406 { 407 int err = 0; 408 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 409 struct net *net = xs_net(x); 410 411 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 412 XFRM_SKB_CB(skb)->seq.output.low = ++replay_esn->oseq; 413 XFRM_SKB_CB(skb)->seq.output.hi = replay_esn->oseq_hi; 414 415 if (unlikely(replay_esn->oseq == 0)) { 416 XFRM_SKB_CB(skb)->seq.output.hi = ++replay_esn->oseq_hi; 417 418 if (replay_esn->oseq_hi == 0) { 419 replay_esn->oseq--; 420 replay_esn->oseq_hi--; 421 xfrm_audit_state_replay_overflow(x, skb); 422 err = -EOVERFLOW; 423 424 return err; 425 } 426 } 427 if (xfrm_aevent_is_on(net)) 428 x->repl->notify(x, XFRM_REPLAY_UPDATE); 429 } 430 431 return err; 432 } 433 434 static int xfrm_replay_check_esn(struct xfrm_state *x, 435 struct sk_buff *skb, __be32 net_seq) 436 { 437 unsigned int bitnr, nr; 438 u32 diff; 439 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 440 u32 pos; 441 u32 seq = ntohl(net_seq); 442 u32 wsize = replay_esn->replay_window; 443 u32 top = replay_esn->seq; 444 u32 bottom = top - wsize + 1; 445 446 if (!wsize) 447 return 0; 448 449 if (unlikely(seq == 0 && replay_esn->seq_hi == 0 && 450 (replay_esn->seq < replay_esn->replay_window - 1))) 451 goto err; 452 453 diff = top - seq; 454 455 if (likely(top >= wsize - 1)) { 456 /* A. same subspace */ 457 if (likely(seq > top) || seq < bottom) 458 return 0; 459 } else { 460 /* B. window spans two subspaces */ 461 if (likely(seq > top && seq < bottom)) 462 return 0; 463 if (seq >= bottom) 464 diff = ~seq + top + 1; 465 } 466 467 if (diff >= replay_esn->replay_window) { 468 x->stats.replay_window++; 469 goto err; 470 } 471 472 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 473 474 if (pos >= diff) 475 bitnr = (pos - diff) % replay_esn->replay_window; 476 else 477 bitnr = replay_esn->replay_window - (diff - pos); 478 479 nr = bitnr >> 5; 480 bitnr = bitnr & 0x1F; 481 if (replay_esn->bmp[nr] & (1U << bitnr)) 482 goto err_replay; 483 484 return 0; 485 486 err_replay: 487 x->stats.replay++; 488 err: 489 xfrm_audit_state_replay(x, skb, net_seq); 490 return -EINVAL; 491 } 492 493 static int xfrm_replay_recheck_esn(struct xfrm_state *x, 494 struct sk_buff *skb, __be32 net_seq) 495 { 496 if (unlikely(XFRM_SKB_CB(skb)->seq.input.hi != 497 htonl(xfrm_replay_seqhi(x, net_seq)))) { 498 x->stats.replay_window++; 499 return -EINVAL; 500 } 501 502 return xfrm_replay_check_esn(x, skb, net_seq); 503 } 504 505 static void xfrm_replay_advance_esn(struct xfrm_state *x, __be32 net_seq) 506 { 507 unsigned int bitnr, nr, i; 508 int wrap; 509 u32 diff, pos, seq, seq_hi; 510 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 511 512 if (!replay_esn->replay_window) 513 return; 514 515 seq = ntohl(net_seq); 516 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 517 seq_hi = xfrm_replay_seqhi(x, net_seq); 518 wrap = seq_hi - replay_esn->seq_hi; 519 520 if ((!wrap && seq > replay_esn->seq) || wrap > 0) { 521 if (likely(!wrap)) 522 diff = seq - replay_esn->seq; 523 else 524 diff = ~replay_esn->seq + seq + 1; 525 526 if (diff < replay_esn->replay_window) { 527 for (i = 1; i < diff; i++) { 528 bitnr = (pos + i) % replay_esn->replay_window; 529 nr = bitnr >> 5; 530 bitnr = bitnr & 0x1F; 531 replay_esn->bmp[nr] &= ~(1U << bitnr); 532 } 533 } else { 534 nr = (replay_esn->replay_window - 1) >> 5; 535 for (i = 0; i <= nr; i++) 536 replay_esn->bmp[i] = 0; 537 } 538 539 bitnr = (pos + diff) % replay_esn->replay_window; 540 replay_esn->seq = seq; 541 542 if (unlikely(wrap > 0)) 543 replay_esn->seq_hi++; 544 } else { 545 diff = replay_esn->seq - seq; 546 547 if (pos >= diff) 548 bitnr = (pos - diff) % replay_esn->replay_window; 549 else 550 bitnr = replay_esn->replay_window - (diff - pos); 551 } 552 553 nr = bitnr >> 5; 554 bitnr = bitnr & 0x1F; 555 replay_esn->bmp[nr] |= (1U << bitnr); 556 557 if (xfrm_aevent_is_on(xs_net(x))) 558 x->repl->notify(x, XFRM_REPLAY_UPDATE); 559 } 560 561 static struct xfrm_replay xfrm_replay_legacy = { 562 .advance = xfrm_replay_advance, 563 .check = xfrm_replay_check, 564 .recheck = xfrm_replay_check, 565 .notify = xfrm_replay_notify, 566 .overflow = xfrm_replay_overflow, 567 }; 568 569 static struct xfrm_replay xfrm_replay_bmp = { 570 .advance = xfrm_replay_advance_bmp, 571 .check = xfrm_replay_check_bmp, 572 .recheck = xfrm_replay_check_bmp, 573 .notify = xfrm_replay_notify_bmp, 574 .overflow = xfrm_replay_overflow_bmp, 575 }; 576 577 static struct xfrm_replay xfrm_replay_esn = { 578 .advance = xfrm_replay_advance_esn, 579 .check = xfrm_replay_check_esn, 580 .recheck = xfrm_replay_recheck_esn, 581 .notify = xfrm_replay_notify_esn, 582 .overflow = xfrm_replay_overflow_esn, 583 }; 584 585 int xfrm_init_replay(struct xfrm_state *x) 586 { 587 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 588 589 if (replay_esn) { 590 if (replay_esn->replay_window > 591 replay_esn->bmp_len * sizeof(__u32) * 8) 592 return -EINVAL; 593 594 if (x->props.flags & XFRM_STATE_ESN) { 595 if (replay_esn->replay_window == 0) 596 return -EINVAL; 597 x->repl = &xfrm_replay_esn; 598 } else 599 x->repl = &xfrm_replay_bmp; 600 } else 601 x->repl = &xfrm_replay_legacy; 602 603 return 0; 604 } 605 EXPORT_SYMBOL(xfrm_init_replay); 606