Line data Source code
1 : /*
2 : * rdbx.c
3 : *
4 : * a replay database with extended range, using a rollover counter
5 : *
6 : * David A. McGrew
7 : * Cisco Systems, Inc.
8 : */
9 :
10 : /*
11 : *
12 : * Copyright (c) 2001-2006, Cisco Systems, Inc.
13 : * All rights reserved.
14 : *
15 : * Redistribution and use in source and binary forms, with or without
16 : * modification, are permitted provided that the following conditions
17 : * are met:
18 : *
19 : * Redistributions of source code must retain the above copyright
20 : * notice, this list of conditions and the following disclaimer.
21 : *
22 : * Redistributions in binary form must reproduce the above
23 : * copyright notice, this list of conditions and the following
24 : * disclaimer in the documentation and/or other materials provided
25 : * with the distribution.
26 : *
27 : * Neither the name of the Cisco Systems, Inc. nor the names of its
28 : * contributors may be used to endorse or promote products derived
29 : * from this software without specific prior written permission.
30 : *
31 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
33 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
34 : * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
35 : * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
36 : * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
37 : * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
38 : * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
39 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
42 : * OF THE POSSIBILITY OF SUCH DAMAGE.
43 : *
44 : */
45 :
46 : #include "rdbx.h"
47 :
48 :
49 : /*
50 : * from RFC 3711:
51 : *
52 : * A receiver reconstructs the index i of a packet with sequence
53 : * number SEQ using the estimate
54 : *
55 : * i = 2^16 * v + SEQ,
56 : *
57 : * where v is chosen from the set { ROC-1, ROC, ROC+1 } such that i is
58 : * closest to the value 2^16 * ROC + s_l. If the value r+1 is used,
59 : * then the rollover counter r in the cryptographic context is
60 : * incremented by one (if the packet containing s is authentic).
61 : */
62 :
63 :
64 :
65 : /*
66 : * rdbx implementation notes
67 : *
68 : * A xtd_seq_num_t is essentially a sequence number for which some of
69 : * the data on the wire are implicit. It logically consists of a
70 : * rollover counter and a sequence number; the sequence number is the
71 : * explicit part, and the rollover counter is the implicit part.
72 : *
73 : * Upon receiving a sequence_number (e.g. in a newly received SRTP
74 : * packet), the complete xtd_seq_num_t can be estimated by using a
75 : * local xtd_seq_num_t as a basis. This is done using the function
76 : * index_guess(&local, &guess, seq_from_packet). This function
77 : * returns the difference of the guess and the local value. The local
78 : * xtd_seq_num_t can be moved forward to the guess using the function
79 : * index_advance(&guess, delta), where delta is the difference.
80 : *
81 : *
82 : * A rdbx_t consists of a xtd_seq_num_t and a bitmask. The index is highest
83 : * sequence number that has been received, and the bitmask indicates
84 : * which of the recent indicies have been received as well. The
85 : * highest bit in the bitmask corresponds to the index in the bitmask.
86 : */
87 :
88 :
89 : void
90 0 : index_init(xtd_seq_num_t *pi) {
91 : #ifdef NO_64BIT_MATH
92 : *pi = make64(0,0);
93 : #else
94 0 : *pi = 0;
95 : #endif
96 0 : }
97 :
98 : void
99 0 : index_advance(xtd_seq_num_t *pi, sequence_number_t s) {
100 : #ifdef NO_64BIT_MATH
101 : /* a > ~b means a+b will generate a carry */
102 : /* s is uint16 here */
103 : *pi = make64(high32(*pi) + (s > ~low32(*pi) ? 1 : 0),low32(*pi) + s);
104 : #else
105 0 : *pi += s;
106 : #endif
107 0 : }
108 :
109 :
110 : /*
111 : * index_guess(local, guess, s)
112 : *
113 : * given a xtd_seq_num_t local (which represents the last
114 : * known-to-be-good received xtd_seq_num_t) and a sequence number s
115 : * (from a newly arrived packet), sets the contents of *guess to
116 : * contain the best guess of the packet index to which s corresponds,
117 : * and returns the difference between *guess and *local
118 : *
119 : * nota bene - the output is a signed integer, DON'T cast it to a
120 : * unsigned integer!
121 : */
122 :
123 : int
124 0 : index_guess(const xtd_seq_num_t *local,
125 : xtd_seq_num_t *guess,
126 : sequence_number_t s) {
127 : #ifdef NO_64BIT_MATH
128 : uint32_t local_roc = ((high32(*local) << 16) |
129 : (low32(*local) >> 16));
130 : uint16_t local_seq = (uint16_t) (low32(*local));
131 : #else
132 0 : uint32_t local_roc = (uint32_t)(*local >> 16);
133 0 : uint16_t local_seq = (uint16_t) *local;
134 : #endif
135 : uint32_t guess_roc;
136 : uint16_t guess_seq;
137 : int difference;
138 :
139 0 : if (local_seq < seq_num_median) {
140 0 : if (s - local_seq > seq_num_median) {
141 0 : guess_roc = local_roc - 1;
142 0 : difference = seq_num_max - s + local_seq;
143 : } else {
144 0 : guess_roc = local_roc;
145 0 : difference = s - local_seq;
146 : }
147 : } else {
148 0 : if (local_seq - seq_num_median > s) {
149 0 : guess_roc = local_roc+1;
150 0 : difference = seq_num_max - local_seq + s;
151 : } else {
152 0 : difference = s - local_seq;
153 0 : guess_roc = local_roc;
154 : }
155 : }
156 0 : guess_seq = s;
157 :
158 : /* Note: guess_roc is 32 bits, so this generates a 48-bit result! */
159 : #ifdef NO_64BIT_MATH
160 : *guess = make64(guess_roc >> 16,
161 : (guess_roc << 16) | guess_seq);
162 : #else
163 0 : *guess = (((uint64_t) guess_roc) << 16) | guess_seq;
164 : #endif
165 :
166 0 : return difference;
167 : }
168 :
169 : /*
170 : * rdbx
171 : *
172 : */
173 :
174 :
175 : /*
176 : * rdbx_init(&r, ws) initializes the rdbx_t pointed to by r with window size ws
177 : */
178 :
179 : err_status_t
180 0 : rdbx_init(rdbx_t *rdbx, unsigned long ws) {
181 0 : if (ws == 0)
182 0 : return err_status_bad_param;
183 :
184 0 : if (bitvector_alloc(&rdbx->bitmask, ws) != 0)
185 0 : return err_status_alloc_fail;
186 :
187 0 : index_init(&rdbx->index);
188 :
189 0 : return err_status_ok;
190 : }
191 :
192 : /*
193 : * rdbx_dealloc(&r) frees memory for the rdbx_t pointed to by r
194 : */
195 :
196 : err_status_t
197 0 : rdbx_dealloc(rdbx_t *rdbx) {
198 0 : bitvector_dealloc(&rdbx->bitmask);
199 :
200 0 : return err_status_ok;
201 : }
202 :
203 : /*
204 : * rdbx_set_roc(rdbx, roc) initalizes the rdbx_t at the location rdbx
205 : * to have the rollover counter value roc. If that value is less than
206 : * the current rollover counter value, then the function returns
207 : * err_status_replay_old; otherwise, err_status_ok is returned.
208 : *
209 : */
210 :
211 : err_status_t
212 0 : rdbx_set_roc(rdbx_t *rdbx, uint32_t roc) {
213 0 : bitvector_set_to_zero(&rdbx->bitmask);
214 :
215 : #ifdef NO_64BIT_MATH
216 : #error not yet implemented
217 : #else
218 :
219 : /* make sure that we're not moving backwards */
220 0 : if (roc < (rdbx->index >> 16))
221 0 : return err_status_replay_old;
222 :
223 0 : rdbx->index &= 0xffff; /* retain lowest 16 bits */
224 0 : rdbx->index |= ((uint64_t)roc) << 16; /* set ROC */
225 : #endif
226 :
227 0 : return err_status_ok;
228 : }
229 :
230 : /*
231 : * rdbx_get_packet_index(rdbx) returns the value of the packet index
232 : * for the rdbx_t pointed to by rdbx
233 : *
234 : */
235 :
236 : xtd_seq_num_t
237 0 : rdbx_get_packet_index(const rdbx_t *rdbx) {
238 0 : return rdbx->index;
239 : }
240 :
241 : /*
242 : * rdbx_get_window_size(rdbx) returns the value of the window size
243 : * for the rdbx_t pointed to by rdbx
244 : *
245 : */
246 :
247 : unsigned long
248 0 : rdbx_get_window_size(const rdbx_t *rdbx) {
249 0 : return bitvector_get_length(&rdbx->bitmask);
250 : }
251 :
252 : /*
253 : * rdbx_check(&r, delta) checks to see if the xtd_seq_num_t
254 : * which is at rdbx->index + delta is in the rdb
255 : */
256 :
257 : err_status_t
258 0 : rdbx_check(const rdbx_t *rdbx, int delta) {
259 :
260 0 : if (delta > 0) { /* if delta is positive, it's good */
261 0 : return err_status_ok;
262 0 : } else if ((int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta < 0) {
263 : /* if delta is lower than the bitmask, it's bad */
264 0 : return err_status_replay_old;
265 0 : } else if (bitvector_get_bit(&rdbx->bitmask,
266 : (int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta) == 1) {
267 : /* delta is within the window, so check the bitmask */
268 0 : return err_status_replay_fail;
269 : }
270 : /* otherwise, the index is okay */
271 :
272 0 : return err_status_ok;
273 : }
274 :
275 : /*
276 : * rdbx_add_index adds the xtd_seq_num_t at rdbx->window_start + d to
277 : * replay_db (and does *not* check if that xtd_seq_num_t appears in db)
278 : *
279 : * this function should be called only after replay_check has
280 : * indicated that the index does not appear in the rdbx, e.g., a mutex
281 : * should protect the rdbx between these calls if need be
282 : */
283 :
284 : err_status_t
285 0 : rdbx_add_index(rdbx_t *rdbx, int delta) {
286 :
287 0 : if (delta > 0) {
288 : /* shift forward by delta */
289 0 : index_advance(&rdbx->index, delta);
290 0 : bitvector_left_shift(&rdbx->bitmask, delta);
291 0 : bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) - 1);
292 : } else {
293 : /* delta is in window */
294 0 : bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) -1 + delta);
295 : }
296 :
297 : /* note that we need not consider the case that delta == 0 */
298 :
299 0 : return err_status_ok;
300 : }
301 :
302 :
303 :
304 : /*
305 : * rdbx_estimate_index(rdbx, guess, s)
306 : *
307 : * given an rdbx and a sequence number s (from a newly arrived packet),
308 : * sets the contents of *guess to contain the best guess of the packet
309 : * index to which s corresponds, and returns the difference between
310 : * *guess and the locally stored synch info
311 : */
312 :
313 : int
314 0 : rdbx_estimate_index(const rdbx_t *rdbx,
315 : xtd_seq_num_t *guess,
316 : sequence_number_t s) {
317 :
318 : /*
319 : * if the sequence number and rollover counter in the rdbx are
320 : * non-zero, then use the index_guess(...) function, otherwise, just
321 : * set the rollover counter to zero (since the index_guess(...)
322 : * function might incorrectly guess that the rollover counter is
323 : * 0xffffffff)
324 : */
325 :
326 : #ifdef NO_64BIT_MATH
327 : /* seq_num_median = 0x8000 */
328 : if (high32(rdbx->index) > 0 ||
329 : low32(rdbx->index) > seq_num_median)
330 : #else
331 0 : if (rdbx->index > seq_num_median)
332 : #endif
333 0 : return index_guess(&rdbx->index, guess, s);
334 :
335 : #ifdef NO_64BIT_MATH
336 : *guess = make64(0,(uint32_t) s);
337 : #else
338 0 : *guess = s;
339 : #endif
340 :
341 : #ifdef NO_64BIT_MATH
342 : return s - (uint16_t) low32(rdbx->index);
343 : #else
344 0 : return s - (uint16_t) rdbx->index;
345 : #endif
346 : }
|
