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
24u32 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
49static 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
95static 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
117static 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
144err:
145	xfrm_audit_state_replay(x, skb, net_seq);
146	return -EINVAL;
147}
148
149static 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
173static 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
196static 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
233err_replay:
234	x->stats.replay++;
235err:
236	xfrm_audit_state_replay(x, skb, net_seq);
237	return -EINVAL;
238}
239
240static 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
288static 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
339static 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
405static 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
434static 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
486err_replay:
487	x->stats.replay++;
488err:
489	xfrm_audit_state_replay(x, skb, net_seq);
490	return -EINVAL;
491}
492
493static 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
505static 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
561static 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
569static 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
577static 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
585int 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}
605EXPORT_SYMBOL(xfrm_init_replay);
606