xref: /openbmc/linux/net/xfrm/xfrm_replay.c (revision 075a46a0) 
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