4 * a replay database with extended range, using a rollover counter
12 * Copyright (c) 2001-2006, Cisco Systems, Inc.
13 * All rights reserved.
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
19 * Redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer.
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.
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.
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.
52 * A receiver reconstructs the index i of a packet with sequence
53 * number SEQ using the estimate
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).
66 * rdbx implementation notes
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.
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.
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.
90 index_init(xtd_seq_num_t
*pi
) {
99 index_advance(xtd_seq_num_t
*pi
, sequence_number_t s
) {
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
);
111 * index_guess(local, guess, s)
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
119 * nota bene - the output is a signed integer, DON'T cast it to a
124 index_guess(const xtd_seq_num_t
*local
,
125 xtd_seq_num_t
*guess
,
126 sequence_number_t s
) {
128 uint32_t local_roc
= ((high32(*local
) << 16) |
129 (low32(*local
) >> 16));
130 uint16_t local_seq
= (uint16_t) (low32(*local
));
132 uint32_t local_roc
= (uint32_t)(*local
>> 16);
133 uint16_t local_seq
= (uint16_t) *local
;
136 uint32_t guess_roc
= ((high32(*guess
) << 16) |
137 (low32(*guess
) >> 16));
138 uint16_t guess_seq
= (uint16_t) (low32(*guess
));
140 uint32_t guess_roc
= (uint32_t)(*guess
>> 16);
141 uint16_t guess_seq
= (uint16_t) *guess
;
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
;
150 guess_roc
= local_roc
;
151 difference
= s
- local_seq
;
154 if (local_seq
- seq_num_median
> s
) {
155 guess_roc
= local_roc
+ 1;
156 difference
= s
- local_seq
+ seq_num_max
;
158 guess_roc
= local_roc
;
159 difference
= s
- local_seq
;
164 /* Note: guess_roc is 32 bits, so this generates a 48-bit result! */
166 *guess
= make64(guess_roc
>> 16,
167 (guess_roc
<< 16) | guess_seq
);
169 *guess
= (((uint64_t) guess_roc
) << 16) | guess_seq
;
182 * rdbx_init(&r, ws) initializes the rdbx_t pointed to by r with window size ws
186 rdbx_init(rdbx_t
*rdbx
, unsigned long ws
) {
188 return err_status_bad_param
;
190 if (bitvector_alloc(&rdbx
->bitmask
, ws
) != 0)
191 return err_status_alloc_fail
;
193 index_init(&rdbx
->index
);
195 return err_status_ok
;
199 * rdbx_dealloc(&r) frees memory for the rdbx_t pointed to by r
203 rdbx_dealloc(rdbx_t
*rdbx
) {
204 bitvector_dealloc(&rdbx
->bitmask
);
206 return err_status_ok
;
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.
218 rdbx_set_roc(rdbx_t
*rdbx
, uint32_t roc
) {
219 bitvector_set_to_zero(&rdbx
->bitmask
);
222 #error not yet implemented
225 /* make sure that we're not moving backwards */
226 if (roc
< (rdbx
->index
>> 16))
227 return err_status_replay_old
;
229 rdbx
->index
&= 0xffff; /* retain lowest 16 bits */
230 rdbx
->index
|= ((uint64_t)roc
) << 16; /* set ROC */
233 return err_status_ok
;
237 * rdbx_get_packet_index(rdbx) returns the value of the packet index
238 * for the rdbx_t pointed to by rdbx
243 rdbx_get_packet_index(const rdbx_t
*rdbx
) {
248 * rdbx_get_window_size(rdbx) returns the value of the window size
249 * for the rdbx_t pointed to by rdbx
254 rdbx_get_window_size(const rdbx_t
*rdbx
) {
255 return bitvector_get_length(&rdbx
->bitmask
);
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
264 rdbx_check(const rdbx_t
*rdbx
, int delta
) {
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
;
276 /* otherwise, the index is okay */
278 return err_status_ok
;
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)
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
291 rdbx_add_index(rdbx_t
*rdbx
, int delta
) {
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);
299 /* delta is in window */
300 bitvector_set_bit(&rdbx
->bitmask
, bitvector_get_length(&rdbx
->bitmask
) -1 + delta
);
303 /* note that we need not consider the case that delta == 0 */
305 return err_status_ok
;
311 * rdbx_estimate_index(rdbx, guess, s)
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
320 rdbx_estimate_index(const rdbx_t
*rdbx
,
321 xtd_seq_num_t
*guess
,
322 sequence_number_t s
) {
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
333 /* seq_num_median = 0x8000 */
334 if (high32(rdbx
->index
) > 0 ||
335 low32(rdbx
->index
) > seq_num_median
)
337 if (rdbx
->index
> seq_num_median
)
339 return index_guess(&rdbx
->index
, guess
, s
);
342 *guess
= make64(0,(uint32_t) s
);
348 return s
- (uint16_t) low32(rdbx
->index
);
350 return s
- (uint16_t) rdbx
->index
;