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 <net/xfrm.h> 22 23 u32 xfrm_replay_seqhi(struct xfrm_state *x, __be32 net_seq) 24 { 25 u32 seq, seq_hi, bottom; 26 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 27 28 if (!(x->props.flags & XFRM_STATE_ESN)) 29 return 0; 30 31 seq = ntohl(net_seq); 32 seq_hi = replay_esn->seq_hi; 33 bottom = replay_esn->seq - replay_esn->replay_window + 1; 34 35 if (likely(replay_esn->seq >= replay_esn->replay_window - 1)) { 36 /* A. same subspace */ 37 if (unlikely(seq < bottom)) 38 seq_hi++; 39 } else { 40 /* B. window spans two subspaces */ 41 if (unlikely(seq >= bottom)) 42 seq_hi--; 43 } 44 45 return seq_hi; 46 } 47 48 static void xfrm_replay_notify(struct xfrm_state *x, int event) 49 { 50 struct km_event c; 51 /* we send notify messages in case 52 * 1. we updated on of the sequence numbers, and the seqno difference 53 * is at least x->replay_maxdiff, in this case we also update the 54 * timeout of our timer function 55 * 2. if x->replay_maxage has elapsed since last update, 56 * and there were changes 57 * 58 * The state structure must be locked! 59 */ 60 61 switch (event) { 62 case XFRM_REPLAY_UPDATE: 63 if (x->replay_maxdiff && 64 (x->replay.seq - x->preplay.seq < x->replay_maxdiff) && 65 (x->replay.oseq - x->preplay.oseq < x->replay_maxdiff)) { 66 if (x->xflags & XFRM_TIME_DEFER) 67 event = XFRM_REPLAY_TIMEOUT; 68 else 69 return; 70 } 71 72 break; 73 74 case XFRM_REPLAY_TIMEOUT: 75 if (memcmp(&x->replay, &x->preplay, 76 sizeof(struct xfrm_replay_state)) == 0) { 77 x->xflags |= XFRM_TIME_DEFER; 78 return; 79 } 80 81 break; 82 } 83 84 memcpy(&x->preplay, &x->replay, sizeof(struct xfrm_replay_state)); 85 c.event = XFRM_MSG_NEWAE; 86 c.data.aevent = event; 87 km_state_notify(x, &c); 88 89 if (x->replay_maxage && 90 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 91 x->xflags &= ~XFRM_TIME_DEFER; 92 } 93 94 static int xfrm_replay_overflow(struct xfrm_state *x, struct sk_buff *skb) 95 { 96 int err = 0; 97 struct net *net = xs_net(x); 98 99 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 100 XFRM_SKB_CB(skb)->seq.output.low = ++x->replay.oseq; 101 if (unlikely(x->replay.oseq == 0)) { 102 x->replay.oseq--; 103 xfrm_audit_state_replay_overflow(x, skb); 104 err = -EOVERFLOW; 105 106 return err; 107 } 108 if (xfrm_aevent_is_on(net)) 109 x->repl->notify(x, XFRM_REPLAY_UPDATE); 110 } 111 112 return err; 113 } 114 115 static int xfrm_replay_check(struct xfrm_state *x, 116 struct sk_buff *skb, __be32 net_seq) 117 { 118 u32 diff; 119 u32 seq = ntohl(net_seq); 120 121 if (!x->props.replay_window) 122 return 0; 123 124 if (unlikely(seq == 0)) 125 goto err; 126 127 if (likely(seq > x->replay.seq)) 128 return 0; 129 130 diff = x->replay.seq - seq; 131 if (diff >= min_t(unsigned int, x->props.replay_window, 132 sizeof(x->replay.bitmap) * 8)) { 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 xfrm_replay_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 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 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 if (pos >= diff) { 220 bitnr = (pos - diff) % replay_esn->replay_window; 221 nr = bitnr >> 5; 222 bitnr = bitnr & 0x1F; 223 if (replay_esn->bmp[nr] & (1U << bitnr)) 224 goto err_replay; 225 } else { 226 bitnr = replay_esn->replay_window - (diff - pos); 227 nr = bitnr >> 5; 228 bitnr = bitnr & 0x1F; 229 if (replay_esn->bmp[nr] & (1U << bitnr)) 230 goto err_replay; 231 } 232 return 0; 233 234 err_replay: 235 x->stats.replay++; 236 err: 237 xfrm_audit_state_replay(x, skb, net_seq); 238 return -EINVAL; 239 } 240 241 static void xfrm_replay_advance_bmp(struct xfrm_state *x, __be32 net_seq) 242 { 243 unsigned int bitnr, nr, i; 244 u32 diff; 245 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 246 u32 seq = ntohl(net_seq); 247 u32 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 248 249 if (!replay_esn->replay_window) 250 return; 251 252 if (seq > replay_esn->seq) { 253 diff = seq - replay_esn->seq; 254 255 if (diff < replay_esn->replay_window) { 256 for (i = 1; i < diff; i++) { 257 bitnr = (pos + i) % replay_esn->replay_window; 258 nr = bitnr >> 5; 259 bitnr = bitnr & 0x1F; 260 replay_esn->bmp[nr] &= ~(1U << bitnr); 261 } 262 263 bitnr = (pos + diff) % replay_esn->replay_window; 264 nr = bitnr >> 5; 265 bitnr = bitnr & 0x1F; 266 replay_esn->bmp[nr] |= (1U << bitnr); 267 } else { 268 nr = (replay_esn->replay_window - 1) >> 5; 269 for (i = 0; i <= nr; i++) 270 replay_esn->bmp[i] = 0; 271 272 bitnr = (pos + diff) % replay_esn->replay_window; 273 nr = bitnr >> 5; 274 bitnr = bitnr & 0x1F; 275 replay_esn->bmp[nr] |= (1U << bitnr); 276 } 277 278 replay_esn->seq = seq; 279 } else { 280 diff = replay_esn->seq - seq; 281 282 if (pos >= diff) { 283 bitnr = (pos - diff) % replay_esn->replay_window; 284 nr = bitnr >> 5; 285 bitnr = bitnr & 0x1F; 286 replay_esn->bmp[nr] |= (1U << bitnr); 287 } else { 288 bitnr = replay_esn->replay_window - (diff - pos); 289 nr = bitnr >> 5; 290 bitnr = bitnr & 0x1F; 291 replay_esn->bmp[nr] |= (1U << bitnr); 292 } 293 } 294 295 if (xfrm_aevent_is_on(xs_net(x))) 296 xfrm_replay_notify(x, XFRM_REPLAY_UPDATE); 297 } 298 299 static void xfrm_replay_notify_bmp(struct xfrm_state *x, int event) 300 { 301 struct km_event c; 302 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 303 struct xfrm_replay_state_esn *preplay_esn = x->preplay_esn; 304 305 /* we send notify messages in case 306 * 1. we updated on of the sequence numbers, and the seqno difference 307 * is at least x->replay_maxdiff, in this case we also update the 308 * timeout of our timer function 309 * 2. if x->replay_maxage has elapsed since last update, 310 * and there were changes 311 * 312 * The state structure must be locked! 313 */ 314 315 switch (event) { 316 case XFRM_REPLAY_UPDATE: 317 if (x->replay_maxdiff && 318 (replay_esn->seq - preplay_esn->seq < x->replay_maxdiff) && 319 (replay_esn->oseq - preplay_esn->oseq < x->replay_maxdiff)) { 320 if (x->xflags & XFRM_TIME_DEFER) 321 event = XFRM_REPLAY_TIMEOUT; 322 else 323 return; 324 } 325 326 break; 327 328 case XFRM_REPLAY_TIMEOUT: 329 if (memcmp(x->replay_esn, x->preplay_esn, 330 xfrm_replay_state_esn_len(replay_esn)) == 0) { 331 x->xflags |= XFRM_TIME_DEFER; 332 return; 333 } 334 335 break; 336 } 337 338 memcpy(x->preplay_esn, x->replay_esn, 339 xfrm_replay_state_esn_len(replay_esn)); 340 c.event = XFRM_MSG_NEWAE; 341 c.data.aevent = event; 342 km_state_notify(x, &c); 343 344 if (x->replay_maxage && 345 !mod_timer(&x->rtimer, jiffies + x->replay_maxage)) 346 x->xflags &= ~XFRM_TIME_DEFER; 347 } 348 349 static int xfrm_replay_overflow_esn(struct xfrm_state *x, struct sk_buff *skb) 350 { 351 int err = 0; 352 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 353 struct net *net = xs_net(x); 354 355 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 356 XFRM_SKB_CB(skb)->seq.output.low = ++replay_esn->oseq; 357 XFRM_SKB_CB(skb)->seq.output.hi = replay_esn->oseq_hi; 358 359 if (unlikely(replay_esn->oseq == 0)) { 360 XFRM_SKB_CB(skb)->seq.output.hi = ++replay_esn->oseq_hi; 361 362 if (replay_esn->oseq_hi == 0) { 363 replay_esn->oseq--; 364 replay_esn->oseq_hi--; 365 xfrm_audit_state_replay_overflow(x, skb); 366 err = -EOVERFLOW; 367 368 return err; 369 } 370 } 371 if (xfrm_aevent_is_on(net)) 372 x->repl->notify(x, XFRM_REPLAY_UPDATE); 373 } 374 375 return err; 376 } 377 378 static int xfrm_replay_check_esn(struct xfrm_state *x, 379 struct sk_buff *skb, __be32 net_seq) 380 { 381 unsigned int bitnr, nr; 382 u32 diff; 383 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 384 u32 pos; 385 u32 seq = ntohl(net_seq); 386 u32 wsize = replay_esn->replay_window; 387 u32 top = replay_esn->seq; 388 u32 bottom = top - wsize + 1; 389 390 if (!wsize) 391 return 0; 392 393 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 394 395 if (unlikely(seq == 0 && replay_esn->seq_hi == 0 && 396 (replay_esn->seq < replay_esn->replay_window - 1))) 397 goto err; 398 399 diff = top - seq; 400 401 if (likely(top >= wsize - 1)) { 402 /* A. same subspace */ 403 if (likely(seq > top) || seq < bottom) 404 return 0; 405 } else { 406 /* B. window spans two subspaces */ 407 if (likely(seq > top && seq < bottom)) 408 return 0; 409 if (seq >= bottom) 410 diff = ~seq + top + 1; 411 } 412 413 if (diff >= replay_esn->replay_window) { 414 x->stats.replay_window++; 415 goto err; 416 } 417 418 if (pos >= diff) { 419 bitnr = (pos - diff) % replay_esn->replay_window; 420 nr = bitnr >> 5; 421 bitnr = bitnr & 0x1F; 422 if (replay_esn->bmp[nr] & (1U << bitnr)) 423 goto err_replay; 424 } else { 425 bitnr = replay_esn->replay_window - (diff - pos); 426 nr = bitnr >> 5; 427 bitnr = bitnr & 0x1F; 428 if (replay_esn->bmp[nr] & (1U << bitnr)) 429 goto err_replay; 430 } 431 return 0; 432 433 err_replay: 434 x->stats.replay++; 435 err: 436 xfrm_audit_state_replay(x, skb, net_seq); 437 return -EINVAL; 438 } 439 440 static void xfrm_replay_advance_esn(struct xfrm_state *x, __be32 net_seq) 441 { 442 unsigned int bitnr, nr, i; 443 int wrap; 444 u32 diff, pos, seq, seq_hi; 445 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 446 447 if (!replay_esn->replay_window) 448 return; 449 450 seq = ntohl(net_seq); 451 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 452 seq_hi = xfrm_replay_seqhi(x, net_seq); 453 wrap = seq_hi - replay_esn->seq_hi; 454 455 if ((!wrap && seq > replay_esn->seq) || wrap > 0) { 456 if (likely(!wrap)) 457 diff = seq - replay_esn->seq; 458 else 459 diff = ~replay_esn->seq + seq + 1; 460 461 if (diff < replay_esn->replay_window) { 462 for (i = 1; i < diff; i++) { 463 bitnr = (pos + i) % replay_esn->replay_window; 464 nr = bitnr >> 5; 465 bitnr = bitnr & 0x1F; 466 replay_esn->bmp[nr] &= ~(1U << bitnr); 467 } 468 469 bitnr = (pos + diff) % replay_esn->replay_window; 470 nr = bitnr >> 5; 471 bitnr = bitnr & 0x1F; 472 replay_esn->bmp[nr] |= (1U << bitnr); 473 } else { 474 nr = (replay_esn->replay_window - 1) >> 5; 475 for (i = 0; i <= nr; i++) 476 replay_esn->bmp[i] = 0; 477 478 bitnr = (pos + diff) % replay_esn->replay_window; 479 nr = bitnr >> 5; 480 bitnr = bitnr & 0x1F; 481 replay_esn->bmp[nr] |= (1U << bitnr); 482 } 483 484 replay_esn->seq = seq; 485 486 if (unlikely(wrap > 0)) 487 replay_esn->seq_hi++; 488 } else { 489 diff = replay_esn->seq - seq; 490 491 if (pos >= diff) { 492 bitnr = (pos - diff) % replay_esn->replay_window; 493 nr = bitnr >> 5; 494 bitnr = bitnr & 0x1F; 495 replay_esn->bmp[nr] |= (1U << bitnr); 496 } else { 497 bitnr = replay_esn->replay_window - (diff - pos); 498 nr = bitnr >> 5; 499 bitnr = bitnr & 0x1F; 500 replay_esn->bmp[nr] |= (1U << bitnr); 501 } 502 } 503 504 if (xfrm_aevent_is_on(xs_net(x))) 505 xfrm_replay_notify(x, XFRM_REPLAY_UPDATE); 506 } 507 508 static struct xfrm_replay xfrm_replay_legacy = { 509 .advance = xfrm_replay_advance, 510 .check = xfrm_replay_check, 511 .notify = xfrm_replay_notify, 512 .overflow = xfrm_replay_overflow, 513 }; 514 515 static struct xfrm_replay xfrm_replay_bmp = { 516 .advance = xfrm_replay_advance_bmp, 517 .check = xfrm_replay_check_bmp, 518 .notify = xfrm_replay_notify_bmp, 519 .overflow = xfrm_replay_overflow_bmp, 520 }; 521 522 static struct xfrm_replay xfrm_replay_esn = { 523 .advance = xfrm_replay_advance_esn, 524 .check = xfrm_replay_check_esn, 525 .notify = xfrm_replay_notify_bmp, 526 .overflow = xfrm_replay_overflow_esn, 527 }; 528 529 int xfrm_init_replay(struct xfrm_state *x) 530 { 531 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 532 533 if (replay_esn) { 534 if (replay_esn->replay_window > 535 replay_esn->bmp_len * sizeof(__u32) * 8) 536 return -EINVAL; 537 538 if ((x->props.flags & XFRM_STATE_ESN) && replay_esn->replay_window == 0) 539 return -EINVAL; 540 541 if ((x->props.flags & XFRM_STATE_ESN) && x->replay_esn) 542 x->repl = &xfrm_replay_esn; 543 else 544 x->repl = &xfrm_replay_bmp; 545 } else 546 x->repl = &xfrm_replay_legacy; 547 548 return 0; 549 } 550 EXPORT_SYMBOL(xfrm_init_replay); 551