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 if (unlikely(x->replay.oseq == 0)) { 103 x->replay.oseq--; 104 xfrm_audit_state_replay_overflow(x, skb); 105 err = -EOVERFLOW; 106 107 return err; 108 } 109 if (xfrm_aevent_is_on(net)) 110 x->repl->notify(x, XFRM_REPLAY_UPDATE); 111 } 112 113 return err; 114 } 115 116 static int xfrm_replay_check(struct xfrm_state *x, 117 struct sk_buff *skb, __be32 net_seq) 118 { 119 u32 diff; 120 u32 seq = ntohl(net_seq); 121 122 if (!x->props.replay_window) 123 return 0; 124 125 if (unlikely(seq == 0)) 126 goto err; 127 128 if (likely(seq > x->replay.seq)) 129 return 0; 130 131 diff = x->replay.seq - seq; 132 if (diff >= x->props.replay_window) { 133 x->stats.replay_window++; 134 goto err; 135 } 136 137 if (x->replay.bitmap & (1U << diff)) { 138 x->stats.replay++; 139 goto err; 140 } 141 return 0; 142 143 err: 144 xfrm_audit_state_replay(x, skb, net_seq); 145 return -EINVAL; 146 } 147 148 static void xfrm_replay_advance(struct xfrm_state *x, __be32 net_seq) 149 { 150 u32 diff; 151 u32 seq = ntohl(net_seq); 152 153 if (!x->props.replay_window) 154 return; 155 156 if (seq > x->replay.seq) { 157 diff = seq - x->replay.seq; 158 if (diff < x->props.replay_window) 159 x->replay.bitmap = ((x->replay.bitmap) << diff) | 1; 160 else 161 x->replay.bitmap = 1; 162 x->replay.seq = seq; 163 } else { 164 diff = x->replay.seq - seq; 165 x->replay.bitmap |= (1U << diff); 166 } 167 168 if (xfrm_aevent_is_on(xs_net(x))) 169 x->repl->notify(x, XFRM_REPLAY_UPDATE); 170 } 171 172 static int xfrm_replay_overflow_bmp(struct xfrm_state *x, struct sk_buff *skb) 173 { 174 int err = 0; 175 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 176 struct net *net = xs_net(x); 177 178 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 179 XFRM_SKB_CB(skb)->seq.output.low = ++replay_esn->oseq; 180 if (unlikely(replay_esn->oseq == 0)) { 181 replay_esn->oseq--; 182 xfrm_audit_state_replay_overflow(x, skb); 183 err = -EOVERFLOW; 184 185 return err; 186 } 187 if (xfrm_aevent_is_on(net)) 188 x->repl->notify(x, XFRM_REPLAY_UPDATE); 189 } 190 191 return err; 192 } 193 194 static int xfrm_replay_check_bmp(struct xfrm_state *x, 195 struct sk_buff *skb, __be32 net_seq) 196 { 197 unsigned int bitnr, nr; 198 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 199 u32 pos; 200 u32 seq = ntohl(net_seq); 201 u32 diff = replay_esn->seq - seq; 202 203 if (!replay_esn->replay_window) 204 return 0; 205 206 if (unlikely(seq == 0)) 207 goto err; 208 209 if (likely(seq > replay_esn->seq)) 210 return 0; 211 212 if (diff >= replay_esn->replay_window) { 213 x->stats.replay_window++; 214 goto err; 215 } 216 217 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 218 219 if (pos >= diff) 220 bitnr = (pos - diff) % replay_esn->replay_window; 221 else 222 bitnr = replay_esn->replay_window - (diff - pos); 223 224 nr = bitnr >> 5; 225 bitnr = bitnr & 0x1F; 226 if (replay_esn->bmp[nr] & (1U << bitnr)) 227 goto err_replay; 228 229 return 0; 230 231 err_replay: 232 x->stats.replay++; 233 err: 234 xfrm_audit_state_replay(x, skb, net_seq); 235 return -EINVAL; 236 } 237 238 static void xfrm_replay_advance_bmp(struct xfrm_state *x, __be32 net_seq) 239 { 240 unsigned int bitnr, nr, i; 241 u32 diff; 242 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 243 u32 seq = ntohl(net_seq); 244 u32 pos; 245 246 if (!replay_esn->replay_window) 247 return; 248 249 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 250 251 if (seq > replay_esn->seq) { 252 diff = seq - replay_esn->seq; 253 254 if (diff < replay_esn->replay_window) { 255 for (i = 1; i < diff; i++) { 256 bitnr = (pos + i) % replay_esn->replay_window; 257 nr = bitnr >> 5; 258 bitnr = bitnr & 0x1F; 259 replay_esn->bmp[nr] &= ~(1U << bitnr); 260 } 261 } else { 262 nr = (replay_esn->replay_window - 1) >> 5; 263 for (i = 0; i <= nr; i++) 264 replay_esn->bmp[i] = 0; 265 } 266 267 bitnr = (pos + diff) % replay_esn->replay_window; 268 replay_esn->seq = seq; 269 } else { 270 diff = replay_esn->seq - seq; 271 272 if (pos >= diff) 273 bitnr = (pos - diff) % replay_esn->replay_window; 274 else 275 bitnr = replay_esn->replay_window - (diff - pos); 276 } 277 278 nr = bitnr >> 5; 279 bitnr = bitnr & 0x1F; 280 replay_esn->bmp[nr] |= (1U << bitnr); 281 282 if (xfrm_aevent_is_on(xs_net(x))) 283 x->repl->notify(x, XFRM_REPLAY_UPDATE); 284 } 285 286 static void xfrm_replay_notify_bmp(struct xfrm_state *x, int event) 287 { 288 struct km_event c; 289 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 290 struct xfrm_replay_state_esn *preplay_esn = x->preplay_esn; 291 292 /* we send notify messages in case 293 * 1. we updated on of the sequence numbers, and the seqno difference 294 * is at least x->replay_maxdiff, in this case we also update the 295 * timeout of our timer function 296 * 2. if x->replay_maxage has elapsed since last update, 297 * and there were changes 298 * 299 * The state structure must be locked! 300 */ 301 302 switch (event) { 303 case XFRM_REPLAY_UPDATE: 304 if (!x->replay_maxdiff || 305 ((replay_esn->seq - preplay_esn->seq < x->replay_maxdiff) && 306 (replay_esn->oseq - preplay_esn->oseq 307 < x->replay_maxdiff))) { 308 if (x->xflags & XFRM_TIME_DEFER) 309 event = XFRM_REPLAY_TIMEOUT; 310 else 311 return; 312 } 313 314 break; 315 316 case XFRM_REPLAY_TIMEOUT: 317 if (memcmp(x->replay_esn, x->preplay_esn, 318 xfrm_replay_state_esn_len(replay_esn)) == 0) { 319 x->xflags |= XFRM_TIME_DEFER; 320 return; 321 } 322 323 break; 324 } 325 326 memcpy(x->preplay_esn, x->replay_esn, 327 xfrm_replay_state_esn_len(replay_esn)); 328 c.event = XFRM_MSG_NEWAE; 329 c.data.aevent = event; 330 km_state_notify(x, &c); 331 332 if (x->replay_maxage && 333 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 334 x->xflags &= ~XFRM_TIME_DEFER; 335 } 336 337 static void xfrm_replay_notify_esn(struct xfrm_state *x, int event) 338 { 339 u32 seq_diff, oseq_diff; 340 struct km_event c; 341 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 342 struct xfrm_replay_state_esn *preplay_esn = x->preplay_esn; 343 344 /* we send notify messages in case 345 * 1. we updated on of the sequence numbers, and the seqno difference 346 * is at least x->replay_maxdiff, in this case we also update the 347 * timeout of our timer function 348 * 2. if x->replay_maxage has elapsed since last update, 349 * and there were changes 350 * 351 * The state structure must be locked! 352 */ 353 354 switch (event) { 355 case XFRM_REPLAY_UPDATE: 356 if (x->replay_maxdiff) { 357 if (replay_esn->seq_hi == preplay_esn->seq_hi) 358 seq_diff = replay_esn->seq - preplay_esn->seq; 359 else 360 seq_diff = ~preplay_esn->seq + replay_esn->seq 361 + 1; 362 363 if (replay_esn->oseq_hi == preplay_esn->oseq_hi) 364 oseq_diff = replay_esn->oseq 365 - preplay_esn->oseq; 366 else 367 oseq_diff = ~preplay_esn->oseq 368 + replay_esn->oseq + 1; 369 370 if (seq_diff >= x->replay_maxdiff || 371 oseq_diff >= x->replay_maxdiff) 372 break; 373 } 374 375 if (x->xflags & XFRM_TIME_DEFER) 376 event = XFRM_REPLAY_TIMEOUT; 377 else 378 return; 379 380 break; 381 382 case XFRM_REPLAY_TIMEOUT: 383 if (memcmp(x->replay_esn, x->preplay_esn, 384 xfrm_replay_state_esn_len(replay_esn)) == 0) { 385 x->xflags |= XFRM_TIME_DEFER; 386 return; 387 } 388 389 break; 390 } 391 392 memcpy(x->preplay_esn, x->replay_esn, 393 xfrm_replay_state_esn_len(replay_esn)); 394 c.event = XFRM_MSG_NEWAE; 395 c.data.aevent = event; 396 km_state_notify(x, &c); 397 398 if (x->replay_maxage && 399 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 400 x->xflags &= ~XFRM_TIME_DEFER; 401 } 402 403 static int xfrm_replay_overflow_esn(struct xfrm_state *x, struct sk_buff *skb) 404 { 405 int err = 0; 406 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 407 struct net *net = xs_net(x); 408 409 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 410 XFRM_SKB_CB(skb)->seq.output.low = ++replay_esn->oseq; 411 XFRM_SKB_CB(skb)->seq.output.hi = replay_esn->oseq_hi; 412 413 if (unlikely(replay_esn->oseq == 0)) { 414 XFRM_SKB_CB(skb)->seq.output.hi = ++replay_esn->oseq_hi; 415 416 if (replay_esn->oseq_hi == 0) { 417 replay_esn->oseq--; 418 replay_esn->oseq_hi--; 419 xfrm_audit_state_replay_overflow(x, skb); 420 err = -EOVERFLOW; 421 422 return err; 423 } 424 } 425 if (xfrm_aevent_is_on(net)) 426 x->repl->notify(x, XFRM_REPLAY_UPDATE); 427 } 428 429 return err; 430 } 431 432 static int xfrm_replay_check_esn(struct xfrm_state *x, 433 struct sk_buff *skb, __be32 net_seq) 434 { 435 unsigned int bitnr, nr; 436 u32 diff; 437 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 438 u32 pos; 439 u32 seq = ntohl(net_seq); 440 u32 wsize = replay_esn->replay_window; 441 u32 top = replay_esn->seq; 442 u32 bottom = top - wsize + 1; 443 444 if (!wsize) 445 return 0; 446 447 if (unlikely(seq == 0 && replay_esn->seq_hi == 0 && 448 (replay_esn->seq < replay_esn->replay_window - 1))) 449 goto err; 450 451 diff = top - seq; 452 453 if (likely(top >= wsize - 1)) { 454 /* A. same subspace */ 455 if (likely(seq > top) || seq < bottom) 456 return 0; 457 } else { 458 /* B. window spans two subspaces */ 459 if (likely(seq > top && seq < bottom)) 460 return 0; 461 if (seq >= bottom) 462 diff = ~seq + top + 1; 463 } 464 465 if (diff >= replay_esn->replay_window) { 466 x->stats.replay_window++; 467 goto err; 468 } 469 470 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 471 472 if (pos >= diff) 473 bitnr = (pos - diff) % replay_esn->replay_window; 474 else 475 bitnr = replay_esn->replay_window - (diff - pos); 476 477 nr = bitnr >> 5; 478 bitnr = bitnr & 0x1F; 479 if (replay_esn->bmp[nr] & (1U << bitnr)) 480 goto err_replay; 481 482 return 0; 483 484 err_replay: 485 x->stats.replay++; 486 err: 487 xfrm_audit_state_replay(x, skb, net_seq); 488 return -EINVAL; 489 } 490 491 static int xfrm_replay_recheck_esn(struct xfrm_state *x, 492 struct sk_buff *skb, __be32 net_seq) 493 { 494 if (unlikely(XFRM_SKB_CB(skb)->seq.input.hi != 495 htonl(xfrm_replay_seqhi(x, net_seq)))) { 496 x->stats.replay_window++; 497 return -EINVAL; 498 } 499 500 return xfrm_replay_check_esn(x, skb, net_seq); 501 } 502 503 static void xfrm_replay_advance_esn(struct xfrm_state *x, __be32 net_seq) 504 { 505 unsigned int bitnr, nr, i; 506 int wrap; 507 u32 diff, pos, seq, seq_hi; 508 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 509 510 if (!replay_esn->replay_window) 511 return; 512 513 seq = ntohl(net_seq); 514 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 515 seq_hi = xfrm_replay_seqhi(x, net_seq); 516 wrap = seq_hi - replay_esn->seq_hi; 517 518 if ((!wrap && seq > replay_esn->seq) || wrap > 0) { 519 if (likely(!wrap)) 520 diff = seq - replay_esn->seq; 521 else 522 diff = ~replay_esn->seq + seq + 1; 523 524 if (diff < replay_esn->replay_window) { 525 for (i = 1; i < diff; i++) { 526 bitnr = (pos + i) % replay_esn->replay_window; 527 nr = bitnr >> 5; 528 bitnr = bitnr & 0x1F; 529 replay_esn->bmp[nr] &= ~(1U << bitnr); 530 } 531 } else { 532 nr = (replay_esn->replay_window - 1) >> 5; 533 for (i = 0; i <= nr; i++) 534 replay_esn->bmp[i] = 0; 535 } 536 537 bitnr = (pos + diff) % replay_esn->replay_window; 538 replay_esn->seq = seq; 539 540 if (unlikely(wrap > 0)) 541 replay_esn->seq_hi++; 542 } else { 543 diff = replay_esn->seq - seq; 544 545 if (pos >= diff) 546 bitnr = (pos - diff) % replay_esn->replay_window; 547 else 548 bitnr = replay_esn->replay_window - (diff - pos); 549 } 550 551 nr = bitnr >> 5; 552 bitnr = bitnr & 0x1F; 553 replay_esn->bmp[nr] |= (1U << bitnr); 554 555 if (xfrm_aevent_is_on(xs_net(x))) 556 x->repl->notify(x, XFRM_REPLAY_UPDATE); 557 } 558 559 static struct xfrm_replay xfrm_replay_legacy = { 560 .advance = xfrm_replay_advance, 561 .check = xfrm_replay_check, 562 .recheck = xfrm_replay_check, 563 .notify = xfrm_replay_notify, 564 .overflow = xfrm_replay_overflow, 565 }; 566 567 static struct xfrm_replay xfrm_replay_bmp = { 568 .advance = xfrm_replay_advance_bmp, 569 .check = xfrm_replay_check_bmp, 570 .recheck = xfrm_replay_check_bmp, 571 .notify = xfrm_replay_notify_bmp, 572 .overflow = xfrm_replay_overflow_bmp, 573 }; 574 575 static struct xfrm_replay xfrm_replay_esn = { 576 .advance = xfrm_replay_advance_esn, 577 .check = xfrm_replay_check_esn, 578 .recheck = xfrm_replay_recheck_esn, 579 .notify = xfrm_replay_notify_esn, 580 .overflow = xfrm_replay_overflow_esn, 581 }; 582 583 int xfrm_init_replay(struct xfrm_state *x) 584 { 585 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 586 587 if (replay_esn) { 588 if (replay_esn->replay_window > 589 replay_esn->bmp_len * sizeof(__u32) * 8) 590 return -EINVAL; 591 592 if (x->props.flags & XFRM_STATE_ESN) { 593 if (replay_esn->replay_window == 0) 594 return -EINVAL; 595 x->repl = &xfrm_replay_esn; 596 } else 597 x->repl = &xfrm_replay_bmp; 598 } else 599 x->repl = &xfrm_replay_legacy; 600 601 return 0; 602 } 603 EXPORT_SYMBOL(xfrm_init_replay); 604