Line data    Source code

       1             : /*
       2             :  * rdb.c
       3             :  *
       4             :  * Implements a replay database for packet security
       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             : 
      47             : #include "rdb.h"
      48             : 
      49             : 
      50             : /*
      51             :  * this implementation of a replay database works as follows:
      52             :  * 
      53             :  * window_start is the index of the first packet in the window
      54             :  * bitmask      a bit-buffer, containing the most recently entered
      55             :  *              index as the leftmost bit 
      56             :  *
      57             :  */
      58             : 
      59             : /* rdb_init initalizes rdb */
      60             : 
      61             : err_status_t
      62           0 : rdb_init(rdb_t *rdb) {
      63           0 :   v128_set_to_zero(&rdb->bitmask);
      64           0 :   rdb->window_start = 0;
      65           0 :   return err_status_ok;
      66             : }
      67             : 
      68             : /*
      69             :  * rdb_check checks to see if index appears in rdb
      70             :  */
      71             : 
      72             : err_status_t
      73           0 : rdb_check(const rdb_t *rdb, uint32_t p_index) {
      74             :   
      75             :   /* if the index appears after (or at very end of) the window, its good */
      76           0 :   if (p_index >= rdb->window_start + rdb_bits_in_bitmask)
      77           0 :     return err_status_ok;
      78             :   
      79             :   /* if the index appears before the window, its bad */
      80           0 :   if (p_index < rdb->window_start)
      81           0 :     return err_status_replay_old;
      82             : 
      83             :   /* otherwise, the index appears within the window, so check the bitmask */
      84           0 :   if (v128_get_bit(&rdb->bitmask, (p_index - rdb->window_start)) == 1)
      85           0 :     return err_status_replay_fail;    
      86             :       
      87             :   /* otherwise, the index is okay */
      88           0 :   return err_status_ok;
      89             : }
      90             : 
      91             : /*
      92             :  * rdb_add_index adds index to rdb_t (and does *not* check if
      93             :  * index appears in db)
      94             :  *
      95             :  * this function should be called only after rdb_check has
      96             :  * indicated that the index does not appear in the rdb, e.g., a mutex
      97             :  * should protect the rdb between these calls
      98             :  */
      99             : 
     100             : err_status_t
     101           0 : rdb_add_index(rdb_t *rdb, uint32_t p_index) {
     102             :   int delta;  
     103             : 
     104             :   /* here we *assume* that p_index > rdb->window_start */
     105             : 
     106           0 :   delta = (p_index - rdb->window_start);    
     107           0 :   if (delta < (int)rdb_bits_in_bitmask) {
     108             : 
     109             :     /* if the p_index is within the window, set the appropriate bit */
     110           0 :     v128_set_bit(&rdb->bitmask, delta);
     111             : 
     112             :   } else { 
     113             :     
     114           0 :     delta -= rdb_bits_in_bitmask - 1;
     115             : 
     116             :     /* shift the window forward by delta bits*/
     117           0 :     v128_left_shift(&rdb->bitmask, delta);
     118           0 :     v128_set_bit(&rdb->bitmask, rdb_bits_in_bitmask-1);
     119           0 :     rdb->window_start += delta;
     120             : 
     121             :   }    
     122             : 
     123           0 :   return err_status_ok;
     124             : }
     125             : 
     126             : err_status_t
     127           0 : rdb_increment(rdb_t *rdb) {
     128             : 
     129           0 :   if (rdb->window_start++ > 0x7fffffff)
     130           0 :     return err_status_key_expired;
     131           0 :   return err_status_ok;
     132             : }
     133             : 
     134             : uint32_t
     135           0 : rdb_get_value(const rdb_t *rdb) {
     136           0 :   return rdb->window_start;
     137             : }