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 >= min_t(unsigned int, x->props.replay_window, 133 sizeof(x->replay.bitmap) * 8)) { 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 if (unlikely(replay_esn->oseq == 0)) { 182 replay_esn->oseq--; 183 xfrm_audit_state_replay_overflow(x, skb); 184 err = -EOVERFLOW; 185 186 return err; 187 } 188 if (xfrm_aevent_is_on(net)) 189 x->repl->notify(x, XFRM_REPLAY_UPDATE); 190 } 191 192 return err; 193 } 194 195 static int xfrm_replay_check_bmp(struct xfrm_state *x, 196 struct sk_buff *skb, __be32 net_seq) 197 { 198 unsigned int bitnr, nr; 199 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 200 u32 pos; 201 u32 seq = ntohl(net_seq); 202 u32 diff = replay_esn->seq - seq; 203 204 if (!replay_esn->replay_window) 205 return 0; 206 207 if (unlikely(seq == 0)) 208 goto err; 209 210 if (likely(seq > replay_esn->seq)) 211 return 0; 212 213 if (diff >= replay_esn->replay_window) { 214 x->stats.replay_window++; 215 goto err; 216 } 217 218 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 219 220 if (pos >= diff) 221 bitnr = (pos - diff) % replay_esn->replay_window; 222 else 223 bitnr = replay_esn->replay_window - (diff - pos); 224 225 nr = bitnr >> 5; 226 bitnr = bitnr & 0x1F; 227 if (replay_esn->bmp[nr] & (1U << bitnr)) 228 goto err_replay; 229 230 return 0; 231 232 err_replay: 233 x->stats.replay++; 234 err: 235 xfrm_audit_state_replay(x, skb, net_seq); 236 return -EINVAL; 237 } 238 239 static void xfrm_replay_advance_bmp(struct xfrm_state *x, __be32 net_seq) 240 { 241 unsigned int bitnr, nr, i; 242 u32 diff; 243 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 244 u32 seq = ntohl(net_seq); 245 u32 pos; 246 247 if (!replay_esn->replay_window) 248 return; 249 250 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 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 } else { 263 nr = (replay_esn->replay_window - 1) >> 5; 264 for (i = 0; i <= nr; i++) 265 replay_esn->bmp[i] = 0; 266 } 267 268 bitnr = (pos + diff) % replay_esn->replay_window; 269 replay_esn->seq = seq; 270 } else { 271 diff = replay_esn->seq - seq; 272 273 if (pos >= diff) 274 bitnr = (pos - diff) % replay_esn->replay_window; 275 else 276 bitnr = replay_esn->replay_window - (diff - pos); 277 } 278 279 nr = bitnr >> 5; 280 bitnr = bitnr & 0x1F; 281 replay_esn->bmp[nr] |= (1U << bitnr); 282 283 if (xfrm_aevent_is_on(xs_net(x))) 284 x->repl->notify(x, XFRM_REPLAY_UPDATE); 285 } 286 287 static void xfrm_replay_notify_bmp(struct xfrm_state *x, int event) 288 { 289 struct km_event c; 290 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 291 struct xfrm_replay_state_esn *preplay_esn = x->preplay_esn; 292 293 /* we send notify messages in case 294 * 1. we updated on of the sequence numbers, and the seqno difference 295 * is at least x->replay_maxdiff, in this case we also update the 296 * timeout of our timer function 297 * 2. if x->replay_maxage has elapsed since last update, 298 * and there were changes 299 * 300 * The state structure must be locked! 301 */ 302 303 switch (event) { 304 case XFRM_REPLAY_UPDATE: 305 if (x->replay_maxdiff && 306 (replay_esn->seq - preplay_esn->seq < x->replay_maxdiff) && 307 (replay_esn->oseq - preplay_esn->oseq < 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 int xfrm_replay_overflow_esn(struct xfrm_state *x, struct sk_buff *skb) 338 { 339 int err = 0; 340 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 341 struct net *net = xs_net(x); 342 343 if (x->type->flags & XFRM_TYPE_REPLAY_PROT) { 344 XFRM_SKB_CB(skb)->seq.output.low = ++replay_esn->oseq; 345 XFRM_SKB_CB(skb)->seq.output.hi = replay_esn->oseq_hi; 346 347 if (unlikely(replay_esn->oseq == 0)) { 348 XFRM_SKB_CB(skb)->seq.output.hi = ++replay_esn->oseq_hi; 349 350 if (replay_esn->oseq_hi == 0) { 351 replay_esn->oseq--; 352 replay_esn->oseq_hi--; 353 xfrm_audit_state_replay_overflow(x, skb); 354 err = -EOVERFLOW; 355 356 return err; 357 } 358 } 359 if (xfrm_aevent_is_on(net)) 360 x->repl->notify(x, XFRM_REPLAY_UPDATE); 361 } 362 363 return err; 364 } 365 366 static int xfrm_replay_check_esn(struct xfrm_state *x, 367 struct sk_buff *skb, __be32 net_seq) 368 { 369 unsigned int bitnr, nr; 370 u32 diff; 371 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 372 u32 pos; 373 u32 seq = ntohl(net_seq); 374 u32 wsize = replay_esn->replay_window; 375 u32 top = replay_esn->seq; 376 u32 bottom = top - wsize + 1; 377 378 if (!wsize) 379 return 0; 380 381 if (unlikely(seq == 0 && replay_esn->seq_hi == 0 && 382 (replay_esn->seq < replay_esn->replay_window - 1))) 383 goto err; 384 385 diff = top - seq; 386 387 if (likely(top >= wsize - 1)) { 388 /* A. same subspace */ 389 if (likely(seq > top) || seq < bottom) 390 return 0; 391 } else { 392 /* B. window spans two subspaces */ 393 if (likely(seq > top && seq < bottom)) 394 return 0; 395 if (seq >= bottom) 396 diff = ~seq + top + 1; 397 } 398 399 if (diff >= replay_esn->replay_window) { 400 x->stats.replay_window++; 401 goto err; 402 } 403 404 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 405 406 if (pos >= diff) 407 bitnr = (pos - diff) % replay_esn->replay_window; 408 else 409 bitnr = replay_esn->replay_window - (diff - pos); 410 411 nr = bitnr >> 5; 412 bitnr = bitnr & 0x1F; 413 if (replay_esn->bmp[nr] & (1U << bitnr)) 414 goto err_replay; 415 416 return 0; 417 418 err_replay: 419 x->stats.replay++; 420 err: 421 xfrm_audit_state_replay(x, skb, net_seq); 422 return -EINVAL; 423 } 424 425 static int xfrm_replay_recheck_esn(struct xfrm_state *x, 426 struct sk_buff *skb, __be32 net_seq) 427 { 428 if (unlikely(XFRM_SKB_CB(skb)->seq.input.hi != 429 htonl(xfrm_replay_seqhi(x, net_seq)))) { 430 x->stats.replay_window++; 431 return -EINVAL; 432 } 433 434 return xfrm_replay_check_esn(x, skb, net_seq); 435 } 436 437 static void xfrm_replay_advance_esn(struct xfrm_state *x, __be32 net_seq) 438 { 439 unsigned int bitnr, nr, i; 440 int wrap; 441 u32 diff, pos, seq, seq_hi; 442 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 443 444 if (!replay_esn->replay_window) 445 return; 446 447 seq = ntohl(net_seq); 448 pos = (replay_esn->seq - 1) % replay_esn->replay_window; 449 seq_hi = xfrm_replay_seqhi(x, net_seq); 450 wrap = seq_hi - replay_esn->seq_hi; 451 452 if ((!wrap && seq > replay_esn->seq) || wrap > 0) { 453 if (likely(!wrap)) 454 diff = seq - replay_esn->seq; 455 else 456 diff = ~replay_esn->seq + seq + 1; 457 458 if (diff < replay_esn->replay_window) { 459 for (i = 1; i < diff; i++) { 460 bitnr = (pos + i) % replay_esn->replay_window; 461 nr = bitnr >> 5; 462 bitnr = bitnr & 0x1F; 463 replay_esn->bmp[nr] &= ~(1U << bitnr); 464 } 465 } else { 466 nr = (replay_esn->replay_window - 1) >> 5; 467 for (i = 0; i <= nr; i++) 468 replay_esn->bmp[i] = 0; 469 } 470 471 bitnr = (pos + diff) % replay_esn->replay_window; 472 replay_esn->seq = seq; 473 474 if (unlikely(wrap > 0)) 475 replay_esn->seq_hi++; 476 } else { 477 diff = replay_esn->seq - seq; 478 479 if (pos >= diff) 480 bitnr = (pos - diff) % replay_esn->replay_window; 481 else 482 bitnr = replay_esn->replay_window - (diff - pos); 483 } 484 485 nr = bitnr >> 5; 486 bitnr = bitnr & 0x1F; 487 replay_esn->bmp[nr] |= (1U << bitnr); 488 489 if (xfrm_aevent_is_on(xs_net(x))) 490 x->repl->notify(x, XFRM_REPLAY_UPDATE); 491 } 492 493 static struct xfrm_replay xfrm_replay_legacy = { 494 .advance = xfrm_replay_advance, 495 .check = xfrm_replay_check, 496 .recheck = xfrm_replay_check, 497 .notify = xfrm_replay_notify, 498 .overflow = xfrm_replay_overflow, 499 }; 500 501 static struct xfrm_replay xfrm_replay_bmp = { 502 .advance = xfrm_replay_advance_bmp, 503 .check = xfrm_replay_check_bmp, 504 .recheck = xfrm_replay_check_bmp, 505 .notify = xfrm_replay_notify_bmp, 506 .overflow = xfrm_replay_overflow_bmp, 507 }; 508 509 static struct xfrm_replay xfrm_replay_esn = { 510 .advance = xfrm_replay_advance_esn, 511 .check = xfrm_replay_check_esn, 512 .recheck = xfrm_replay_recheck_esn, 513 .notify = xfrm_replay_notify_bmp, 514 .overflow = xfrm_replay_overflow_esn, 515 }; 516 517 int xfrm_init_replay(struct xfrm_state *x) 518 { 519 struct xfrm_replay_state_esn *replay_esn = x->replay_esn; 520 521 if (replay_esn) { 522 if (replay_esn->replay_window > 523 replay_esn->bmp_len * sizeof(__u32) * 8) 524 return -EINVAL; 525 526 if (x->props.flags & XFRM_STATE_ESN) { 527 if (replay_esn->replay_window == 0) 528 return -EINVAL; 529 x->repl = &xfrm_replay_esn; 530 } else 531 x->repl = &xfrm_replay_bmp; 532 } else 533 x->repl = &xfrm_replay_legacy; 534 535 return 0; 536 } 537 EXPORT_SYMBOL(xfrm_init_replay); 538