1 /*
2 * Copyright (C) 2016 Red Hat, Inc.
3 *
4 * Authors: Fridolin Pokorny
5 * Nikos Mavrogiannopoulos
6 *
7 * This file is part of GNUTLS.
8 *
9 * The GNUTLS library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public License
11 * as published by the Free Software Foundation; either version 2.1 of
12 * the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public License
20 * along with this program. If not, see <https://www.gnu.org/licenses/>
21 *
22 */
23
24 /* Functions that relate to DTLS sliding window handling.
25 */
26
27 #ifndef DTLS_SW_NO_INCLUDES
28 #include "gnutls_int.h"
29 #include "errors.h"
30 #include "debug.h"
31 #include "dtls.h"
32 #include "record.h"
33 #endif
34
35 /*
36 * DTLS sliding window handling
37 */
38 #define DTLS_EPOCH_SHIFT (6*CHAR_BIT)
39 #define DTLS_SEQ_NUM_MASK 0x0000FFFFFFFFFFFF
40
41 #define DTLS_EMPTY_BITMAP (0xFFFFFFFFFFFFFFFFULL)
42
_dtls_reset_window(struct record_parameters_st * rp)43 void _dtls_reset_window(struct record_parameters_st *rp)
44 {
45 rp->dtls_sw_have_recv = 0;
46 }
47
48 /* Checks if a sequence number is not replayed. If a replayed
49 * packet is detected it returns a negative value (but no sensible error code).
50 * Otherwise zero.
51 */
_dtls_record_check(struct record_parameters_st * rp,uint64_t seq_num)52 int _dtls_record_check(struct record_parameters_st *rp, uint64_t seq_num)
53 {
54 if ((seq_num >> DTLS_EPOCH_SHIFT) != rp->epoch) {
55 return gnutls_assert_val(-1);
56 }
57
58 seq_num &= DTLS_SEQ_NUM_MASK;
59
60 /*
61 * rp->dtls_sw_next is the next *expected* packet (N), being
62 * the sequence number *after* the latest we have received.
63 *
64 * By definition, therefore, packet N-1 *has* been received.
65 * And thus there's no point wasting a bit in the bitmap for it.
66 *
67 * So the backlog bitmap covers the 64 packets prior to that,
68 * with the LSB representing packet (N - 2), and the MSB
69 * representing (N - 65). A received packet is represented
70 * by a zero bit, and a missing packet is represented by a one.
71 *
72 * Thus we can allow out-of-order reception of packets that are
73 * within a reasonable interval of the latest packet received.
74 */
75 if (!rp->dtls_sw_have_recv) {
76 rp->dtls_sw_next = seq_num + 1;
77 rp->dtls_sw_bits = DTLS_EMPTY_BITMAP;
78 rp->dtls_sw_have_recv = 1;
79 return 0;
80 } else if (seq_num == rp->dtls_sw_next) {
81 /* The common case. This is the packet we expected next. */
82
83 rp->dtls_sw_bits <<= 1;
84
85 /* This might reach a value higher than 48-bit DTLS sequence
86 * numbers can actually reach. Which is fine. When that
87 * happens, we'll do the right thing and just not accept
88 * any newer packets. Someone needs to start a new epoch. */
89 rp->dtls_sw_next++;
90 return 0;
91 } else if (seq_num > rp->dtls_sw_next) {
92 /* The packet we were expecting has gone missing; this one is newer.
93 * We always advance the window to accommodate it. */
94 uint64_t delta = seq_num - rp->dtls_sw_next;
95
96 if (delta >= 64) {
97 /* We jumped a long way into the future. We have not seen
98 * any of the previous 32 packets so set the backlog bitmap
99 * to all ones. */
100 rp->dtls_sw_bits = DTLS_EMPTY_BITMAP;
101 } else if (delta == 63) {
102 /* Avoid undefined behaviour that shifting by 64 would incur.
103 * The (clear) top bit represents the packet which is currently
104 * rp->dtls_sw_next, which we know was already received. */
105 rp->dtls_sw_bits = DTLS_EMPTY_BITMAP >> 1;
106 } else {
107 /* We have missed (delta) packets. Shift the backlog by that
108 * amount *plus* the one we would have shifted it anyway if
109 * we'd received the packet we were expecting. The zero bit
110 * representing the packet which is currently rp->dtls_sw_next-1,
111 * which we know has been received, ends up at bit position
112 * (1<<delta). Then we set all the bits lower than that, which
113 * represent the missing packets. */
114 rp->dtls_sw_bits <<= delta + 1;
115 rp->dtls_sw_bits |= (1ULL << delta) - 1;
116 }
117 rp->dtls_sw_next = seq_num + 1;
118 return 0;
119 } else {
120 /* This packet is older than the one we were expecting. By how much...? */
121 uint64_t delta = rp->dtls_sw_next - seq_num;
122
123 if (delta > 65) {
124 /* Too old. We can't know if it's a replay */
125 return gnutls_assert_val(-2);
126 } else if (delta == 1) {
127 /* Not in the bitmask since it is by definition already received. */
128 return gnutls_assert_val(-3);
129 } else {
130 /* Within the sliding window, so we remember whether we've seen it or not */
131 uint64_t mask = 1ULL << (rp->dtls_sw_next - seq_num - 2);
132
133 if (!(rp->dtls_sw_bits & mask))
134 return gnutls_assert_val(-3);
135
136 rp->dtls_sw_bits &= ~mask;
137 return 0;
138 }
139 }
140 }
141