• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
index_init(xtd_seq_num_t * pi)90 index_init(xtd_seq_num_t *pi) {
91 #ifdef NO_64BIT_MATH
92   *pi = make64(0,0);
93 #else
94   *pi = 0;
95 #endif
96 }
97 
98 void
index_advance(xtd_seq_num_t * pi,sequence_number_t s)99 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   *pi += s;
106 #endif
107 }
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
index_guess(const xtd_seq_num_t * local,xtd_seq_num_t * guess,sequence_number_t s)124 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   uint32_t local_roc = (uint32_t)(*local >> 16);
133   uint16_t local_seq = (uint16_t) *local;
134 #endif
135 #ifdef NO_64BIT_MATH
136   uint32_t guess_roc = ((high32(*guess) << 16) |
137 						(low32(*guess) >> 16));
138   uint16_t guess_seq = (uint16_t) (low32(*guess));
139 #else
140   uint32_t guess_roc = (uint32_t)(*guess >> 16);
141   uint16_t guess_seq = (uint16_t) *guess;
142 #endif
143   int difference;
144 
145   if (local_seq < seq_num_median) {
146     if (s - local_seq > seq_num_median) {
147       guess_roc = local_roc - 1;
148       difference = s - local_seq - seq_num_max;
149     } else {
150       guess_roc = local_roc;
151       difference = s - local_seq;
152     }
153   } else {
154     if (local_seq - seq_num_median > s) {
155       guess_roc = local_roc + 1;
156       difference = s - local_seq + seq_num_max;
157     } else {
158       guess_roc = local_roc;
159       difference = s - local_seq;
160     }
161   }
162   guess_seq = s;
163 
164   /* Note: guess_roc is 32 bits, so this generates a 48-bit result! */
165 #ifdef NO_64BIT_MATH
166   *guess = make64(guess_roc >> 16,
167 				  (guess_roc << 16) | guess_seq);
168 #else
169   *guess = (((uint64_t) guess_roc) << 16) | guess_seq;
170 #endif
171 
172   return difference;
173 }
174 
175 /*
176  * rdbx
177  *
178  */
179 
180 
181 /*
182  *  rdbx_init(&r, ws) initializes the rdbx_t pointed to by r with window size ws
183  */
184 
185 err_status_t
rdbx_init(rdbx_t * rdbx,unsigned long ws)186 rdbx_init(rdbx_t *rdbx, unsigned long ws) {
187   if (ws == 0)
188     return err_status_bad_param;
189 
190   if (bitvector_alloc(&rdbx->bitmask, ws) != 0)
191     return err_status_alloc_fail;
192 
193   index_init(&rdbx->index);
194 
195   return err_status_ok;
196 }
197 
198 /*
199  *  rdbx_dealloc(&r) frees memory for the rdbx_t pointed to by r
200  */
201 
202 err_status_t
rdbx_dealloc(rdbx_t * rdbx)203 rdbx_dealloc(rdbx_t *rdbx) {
204   bitvector_dealloc(&rdbx->bitmask);
205 
206   return err_status_ok;
207 }
208 
209 /*
210  * rdbx_set_roc(rdbx, roc) initalizes the rdbx_t at the location rdbx
211  * to have the rollover counter value roc.  If that value is less than
212  * the current rollover counter value, then the function returns
213  * err_status_replay_old; otherwise, err_status_ok is returned.
214  *
215  */
216 
217 err_status_t
rdbx_set_roc(rdbx_t * rdbx,uint32_t roc)218 rdbx_set_roc(rdbx_t *rdbx, uint32_t roc) {
219   bitvector_set_to_zero(&rdbx->bitmask);
220 
221 #ifdef NO_64BIT_MATH
222   #error not yet implemented
223 #else
224 
225   /* make sure that we're not moving backwards */
226   if (roc < (rdbx->index >> 16))
227     return err_status_replay_old;
228 
229   rdbx->index &= 0xffff;   /* retain lowest 16 bits */
230   rdbx->index |= ((uint64_t)roc) << 16;  /* set ROC */
231 #endif
232 
233   return err_status_ok;
234 }
235 
236 /*
237  * rdbx_get_packet_index(rdbx) returns the value of the packet index
238  * for the rdbx_t pointed to by rdbx
239  *
240  */
241 
242 xtd_seq_num_t
rdbx_get_packet_index(const rdbx_t * rdbx)243 rdbx_get_packet_index(const rdbx_t *rdbx) {
244   return rdbx->index;
245 }
246 
247 /*
248  * rdbx_get_window_size(rdbx) returns the value of the window size
249  * for the rdbx_t pointed to by rdbx
250  *
251  */
252 
253 unsigned long
rdbx_get_window_size(const rdbx_t * rdbx)254 rdbx_get_window_size(const rdbx_t *rdbx) {
255   return bitvector_get_length(&rdbx->bitmask);
256 }
257 
258 /*
259  * rdbx_check(&r, delta) checks to see if the xtd_seq_num_t
260  * which is at rdbx->index + delta is in the rdb
261  */
262 
263 err_status_t
rdbx_check(const rdbx_t * rdbx,int delta)264 rdbx_check(const rdbx_t *rdbx, int delta) {
265 
266   if (delta > 0) {       /* if delta is positive, it's good */
267     return err_status_ok;
268   } else if ((int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta < 0) {
269                          /* if delta is lower than the bitmask, it's bad */
270     return err_status_replay_old;
271   } else if (bitvector_get_bit(&rdbx->bitmask,
272 			       (int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta) == 1) {
273                          /* delta is within the window, so check the bitmask */
274     return err_status_replay_fail;
275   }
276  /* otherwise, the index is okay */
277 
278   return err_status_ok;
279 }
280 
281 /*
282  * rdbx_add_index adds the xtd_seq_num_t at rdbx->window_start + d to
283  * replay_db (and does *not* check if that xtd_seq_num_t appears in db)
284  *
285  * this function should be called only after replay_check has
286  * indicated that the index does not appear in the rdbx, e.g., a mutex
287  * should protect the rdbx between these calls if need be
288  */
289 
290 err_status_t
rdbx_add_index(rdbx_t * rdbx,int delta)291 rdbx_add_index(rdbx_t *rdbx, int delta) {
292 
293   if (delta > 0) {
294     /* shift forward by delta */
295     index_advance(&rdbx->index, delta);
296     bitvector_left_shift(&rdbx->bitmask, delta);
297     bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) - 1);
298   } else {
299     /* delta is in window */
300     bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) -1 + delta);
301   }
302 
303   /* note that we need not consider the case that delta == 0 */
304 
305   return err_status_ok;
306 }
307 
308 
309 
310 /*
311  * rdbx_estimate_index(rdbx, guess, s)
312  *
313  * given an rdbx and a sequence number s (from a newly arrived packet),
314  * sets the contents of *guess to contain the best guess of the packet
315  * index to which s corresponds, and returns the difference between
316  * *guess and the locally stored synch info
317  */
318 
319 int
rdbx_estimate_index(const rdbx_t * rdbx,xtd_seq_num_t * guess,sequence_number_t s)320 rdbx_estimate_index(const rdbx_t *rdbx,
321 		    xtd_seq_num_t *guess,
322 		    sequence_number_t s) {
323 
324   /*
325    * if the sequence number and rollover counter in the rdbx are
326    * non-zero, then use the index_guess(...) function, otherwise, just
327    * set the rollover counter to zero (since the index_guess(...)
328    * function might incorrectly guess that the rollover counter is
329    * 0xffffffff)
330    */
331 
332 #ifdef NO_64BIT_MATH
333   /* seq_num_median = 0x8000 */
334   if (high32(rdbx->index) > 0 ||
335 	  low32(rdbx->index) > seq_num_median)
336 #else
337   if (rdbx->index > seq_num_median)
338 #endif
339     return index_guess(&rdbx->index, guess, s);
340 
341 #ifdef NO_64BIT_MATH
342   *guess = make64(0,(uint32_t) s);
343 #else
344   *guess = s;
345 #endif
346 
347 #ifdef NO_64BIT_MATH
348   return s - (uint16_t) low32(rdbx->index);
349 #else
350   return s - (uint16_t) rdbx->index;
351 #endif
352 }
353