OLD | NEW |
| (Empty) |
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 #ifdef HAVE_CONFIG_H | |
47 #include <config.h> | |
48 #endif | |
49 | |
50 #include "rdbx.h" | |
51 | |
52 | |
53 /* | |
54 * from RFC 3711: | |
55 * | |
56 * A receiver reconstructs the index i of a packet with sequence | |
57 * number SEQ using the estimate | |
58 * | |
59 * i = 2^16 * v + SEQ, | |
60 * | |
61 * where v is chosen from the set { ROC-1, ROC, ROC+1 } such that i is | |
62 * closest to the value 2^16 * ROC + s_l. If the value r+1 is used, | |
63 * then the rollover counter r in the cryptographic context is | |
64 * incremented by one (if the packet containing s is authentic). | |
65 */ | |
66 | |
67 | |
68 | |
69 /* | |
70 * rdbx implementation notes | |
71 * | |
72 * A xtd_seq_num_t is essentially a sequence number for which some of | |
73 * the data on the wire are implicit. It logically consists of a | |
74 * rollover counter and a sequence number; the sequence number is the | |
75 * explicit part, and the rollover counter is the implicit part. | |
76 * | |
77 * Upon receiving a sequence_number (e.g. in a newly received SRTP | |
78 * packet), the complete xtd_seq_num_t can be estimated by using a | |
79 * local xtd_seq_num_t as a basis. This is done using the function | |
80 * index_guess(&local, &guess, seq_from_packet). This function | |
81 * returns the difference of the guess and the local value. The local | |
82 * xtd_seq_num_t can be moved forward to the guess using the function | |
83 * index_advance(&guess, delta), where delta is the difference. | |
84 * | |
85 * | |
86 * A rdbx_t consists of a xtd_seq_num_t and a bitmask. The index is highest | |
87 * sequence number that has been received, and the bitmask indicates | |
88 * which of the recent indicies have been received as well. The | |
89 * highest bit in the bitmask corresponds to the index in the bitmask. | |
90 */ | |
91 | |
92 | |
93 void | |
94 index_init(xtd_seq_num_t *pi) { | |
95 #ifdef NO_64BIT_MATH | |
96 *pi = make64(0,0); | |
97 #else | |
98 *pi = 0; | |
99 #endif | |
100 } | |
101 | |
102 void | |
103 index_advance(xtd_seq_num_t *pi, sequence_number_t s) { | |
104 #ifdef NO_64BIT_MATH | |
105 /* a > ~b means a+b will generate a carry */ | |
106 /* s is uint16 here */ | |
107 *pi = make64(high32(*pi) + (s > ~low32(*pi) ? 1 : 0),low32(*pi) + s); | |
108 #else | |
109 *pi += s; | |
110 #endif | |
111 } | |
112 | |
113 | |
114 /* | |
115 * index_guess(local, guess, s) | |
116 * | |
117 * given a xtd_seq_num_t local (which represents the last | |
118 * known-to-be-good received xtd_seq_num_t) and a sequence number s | |
119 * (from a newly arrived packet), sets the contents of *guess to | |
120 * contain the best guess of the packet index to which s corresponds, | |
121 * and returns the difference between *guess and *local | |
122 * | |
123 * nota bene - the output is a signed integer, DON'T cast it to a | |
124 * unsigned integer! | |
125 */ | |
126 | |
127 int | |
128 index_guess(const xtd_seq_num_t *local, | |
129 xtd_seq_num_t *guess, | |
130 sequence_number_t s) { | |
131 #ifdef NO_64BIT_MATH | |
132 uint32_t local_roc = ((high32(*local) << 16) | | |
133 (low32(*local) >> 16)); | |
134 uint16_t local_seq = (uint16_t) (low32(*local)); | |
135 #else | |
136 uint32_t local_roc = (uint32_t)(*local >> 16); | |
137 uint16_t local_seq = (uint16_t) *local; | |
138 #endif | |
139 #ifdef NO_64BIT_MATH | |
140 uint32_t guess_roc = ((high32(*guess) << 16) | | |
141 (low32(*guess) >> 16)); | |
142 uint16_t guess_seq = (uint16_t) (low32(*guess)); | |
143 #else | |
144 uint32_t guess_roc = (uint32_t)(*guess >> 16); | |
145 uint16_t guess_seq = (uint16_t) *guess; | |
146 #endif | |
147 int difference; | |
148 | |
149 if (local_seq < seq_num_median) { | |
150 if (s - local_seq > seq_num_median) { | |
151 guess_roc = local_roc - 1; | |
152 difference = s - local_seq - seq_num_max; | |
153 } else { | |
154 guess_roc = local_roc; | |
155 difference = s - local_seq; | |
156 } | |
157 } else { | |
158 if (local_seq - seq_num_median > s) { | |
159 guess_roc = local_roc + 1; | |
160 difference = s - local_seq + seq_num_max; | |
161 } else { | |
162 guess_roc = local_roc; | |
163 difference = s - local_seq; | |
164 } | |
165 } | |
166 guess_seq = s; | |
167 | |
168 /* Note: guess_roc is 32 bits, so this generates a 48-bit result! */ | |
169 #ifdef NO_64BIT_MATH | |
170 *guess = make64(guess_roc >> 16, | |
171 (guess_roc << 16) | guess_seq); | |
172 #else | |
173 *guess = (((uint64_t) guess_roc) << 16) | guess_seq; | |
174 #endif | |
175 | |
176 return difference; | |
177 } | |
178 | |
179 /* | |
180 * rdbx | |
181 * | |
182 */ | |
183 | |
184 | |
185 /* | |
186 * rdbx_init(&r, ws) initializes the rdbx_t pointed to by r with window size ws | |
187 */ | |
188 | |
189 err_status_t | |
190 rdbx_init(rdbx_t *rdbx, unsigned long ws) { | |
191 if (ws == 0) | |
192 return err_status_bad_param; | |
193 | |
194 if (bitvector_alloc(&rdbx->bitmask, ws) != 0) | |
195 return err_status_alloc_fail; | |
196 | |
197 index_init(&rdbx->index); | |
198 | |
199 return err_status_ok; | |
200 } | |
201 | |
202 /* | |
203 * rdbx_dealloc(&r) frees memory for the rdbx_t pointed to by r | |
204 */ | |
205 | |
206 err_status_t | |
207 rdbx_dealloc(rdbx_t *rdbx) { | |
208 bitvector_dealloc(&rdbx->bitmask); | |
209 | |
210 return err_status_ok; | |
211 } | |
212 | |
213 /* | |
214 * rdbx_set_roc(rdbx, roc) initalizes the rdbx_t at the location rdbx | |
215 * to have the rollover counter value roc. If that value is less than | |
216 * the current rollover counter value, then the function returns | |
217 * err_status_replay_old; otherwise, err_status_ok is returned. | |
218 * | |
219 */ | |
220 | |
221 err_status_t | |
222 rdbx_set_roc(rdbx_t *rdbx, uint32_t roc) { | |
223 bitvector_set_to_zero(&rdbx->bitmask); | |
224 | |
225 #ifdef NO_64BIT_MATH | |
226 #error not yet implemented | |
227 #else | |
228 | |
229 /* make sure that we're not moving backwards */ | |
230 if (roc < (rdbx->index >> 16)) | |
231 return err_status_replay_old; | |
232 | |
233 rdbx->index &= 0xffff; /* retain lowest 16 bits */ | |
234 rdbx->index |= ((uint64_t)roc) << 16; /* set ROC */ | |
235 #endif | |
236 | |
237 return err_status_ok; | |
238 } | |
239 | |
240 /* | |
241 * rdbx_get_packet_index(rdbx) returns the value of the packet index | |
242 * for the rdbx_t pointed to by rdbx | |
243 * | |
244 */ | |
245 | |
246 xtd_seq_num_t | |
247 rdbx_get_packet_index(const rdbx_t *rdbx) { | |
248 return rdbx->index; | |
249 } | |
250 | |
251 /* | |
252 * rdbx_get_window_size(rdbx) returns the value of the window size | |
253 * for the rdbx_t pointed to by rdbx | |
254 * | |
255 */ | |
256 | |
257 unsigned long | |
258 rdbx_get_window_size(const rdbx_t *rdbx) { | |
259 return bitvector_get_length(&rdbx->bitmask); | |
260 } | |
261 | |
262 /* | |
263 * rdbx_check(&r, delta) checks to see if the xtd_seq_num_t | |
264 * which is at rdbx->index + delta is in the rdb | |
265 */ | |
266 | |
267 err_status_t | |
268 rdbx_check(const rdbx_t *rdbx, int delta) { | |
269 | |
270 if (delta > 0) { /* if delta is positive, it's good */ | |
271 return err_status_ok; | |
272 } else if ((int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta < 0) { | |
273 /* if delta is lower than the bitmask, it's bad */ | |
274 return err_status_replay_old; | |
275 } else if (bitvector_get_bit(&rdbx->bitmask, | |
276 (int)(bitvector_get_length(&rdbx->bitmask) - 1) +
delta) == 1) { | |
277 /* delta is within the window, so check the bitmask */ | |
278 return err_status_replay_fail; | |
279 } | |
280 /* otherwise, the index is okay */ | |
281 | |
282 return err_status_ok; | |
283 } | |
284 | |
285 /* | |
286 * rdbx_add_index adds the xtd_seq_num_t at rdbx->window_start + d to | |
287 * replay_db (and does *not* check if that xtd_seq_num_t appears in db) | |
288 * | |
289 * this function should be called only after replay_check has | |
290 * indicated that the index does not appear in the rdbx, e.g., a mutex | |
291 * should protect the rdbx between these calls if need be | |
292 */ | |
293 | |
294 err_status_t | |
295 rdbx_add_index(rdbx_t *rdbx, int delta) { | |
296 | |
297 if (delta > 0) { | |
298 /* shift forward by delta */ | |
299 index_advance(&rdbx->index, delta); | |
300 bitvector_left_shift(&rdbx->bitmask, delta); | |
301 bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) - 1); | |
302 } else { | |
303 /* delta is in window */ | |
304 bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) -1 +
delta); | |
305 } | |
306 | |
307 /* note that we need not consider the case that delta == 0 */ | |
308 | |
309 return err_status_ok; | |
310 } | |
311 | |
312 | |
313 | |
314 /* | |
315 * rdbx_estimate_index(rdbx, guess, s) | |
316 * | |
317 * given an rdbx and a sequence number s (from a newly arrived packet), | |
318 * sets the contents of *guess to contain the best guess of the packet | |
319 * index to which s corresponds, and returns the difference between | |
320 * *guess and the locally stored synch info | |
321 */ | |
322 | |
323 int | |
324 rdbx_estimate_index(const rdbx_t *rdbx, | |
325 xtd_seq_num_t *guess, | |
326 sequence_number_t s) { | |
327 | |
328 /* | |
329 * if the sequence number and rollover counter in the rdbx are | |
330 * non-zero, then use the index_guess(...) function, otherwise, just | |
331 * set the rollover counter to zero (since the index_guess(...) | |
332 * function might incorrectly guess that the rollover counter is | |
333 * 0xffffffff) | |
334 */ | |
335 | |
336 #ifdef NO_64BIT_MATH | |
337 /* seq_num_median = 0x8000 */ | |
338 if (high32(rdbx->index) > 0 || | |
339 low32(rdbx->index) > seq_num_median) | |
340 #else | |
341 if (rdbx->index > seq_num_median) | |
342 #endif | |
343 return index_guess(&rdbx->index, guess, s); | |
344 | |
345 #ifdef NO_64BIT_MATH | |
346 *guess = make64(0,(uint32_t) s); | |
347 #else | |
348 *guess = s; | |
349 #endif | |
350 | |
351 #ifdef NO_64BIT_MATH | |
352 return s - (uint16_t) low32(rdbx->index); | |
353 #else | |
354 return s - (uint16_t) rdbx->index; | |
355 #endif | |
356 } | |
OLD | NEW |