1386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 2386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdb.c 3386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 4386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Implements a replay database for packet security 5386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 6386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * David A. McGrew 7386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Cisco Systems, Inc. 8386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 9386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 10386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 11386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 12386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Copyright (c) 2001-2006, Cisco Systems, Inc. 13386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * All rights reserved. 14386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 15386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistribution and use in source and binary forms, with or without 16386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * modification, are permitted provided that the following conditions 17386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * are met: 18386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 19386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistributions of source code must retain the above copyright 20386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * notice, this list of conditions and the following disclaimer. 21386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 22386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistributions in binary form must reproduce the above 23386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * copyright notice, this list of conditions and the following 24386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * disclaimer in the documentation and/or other materials provided 25386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * with the distribution. 26386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 27386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Neither the name of the Cisco Systems, Inc. nor the names of its 28386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * contributors may be used to endorse or promote products derived 29386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * from this software without specific prior written permission. 30386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 31386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 34386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 35386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 36386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 37386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 38386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 39386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 41386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 42386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * OF THE POSSIBILITY OF SUCH DAMAGE. 43386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 44386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 45386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 46386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 47386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "rdb.h" 48386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 49386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 50386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 51386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * this implementation of a replay database works as follows: 52386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 53386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * window_start is the index of the first packet in the window 54386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * bitmask a bit-buffer, containing the most recently entered 55386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * index as the leftmost bit 56386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 57386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 58386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 59386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* rdb_init initalizes rdb */ 60386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 61386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 62386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_init(rdb_t *rdb) { 63386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari v128_set_to_zero(&rdb->bitmask); 64386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdb->window_start = 0; 65386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 66386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 67386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 68386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 69386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdb_check checks to see if index appears in rdb 70386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 71386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 72386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 73386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_check(const rdb_t *rdb, uint32_t index) { 74386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 75386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* if the index appears after (or at very end of) the window, its good */ 76386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (index >= rdb->window_start + rdb_bits_in_bitmask) 77386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 78386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 79386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* if the index appears before the window, its bad */ 80386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (index < rdb->window_start) 81386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_replay_old; 82386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 83386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* otherwise, the index appears within the window, so check the bitmask */ 84386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (v128_get_bit(&rdb->bitmask, (index - rdb->window_start)) == 1) 85386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_replay_fail; 86386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 87386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* otherwise, the index is okay */ 88386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 89386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 90386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 91386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 92386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdb_add_index adds index to rdb_t (and does *not* check if 93386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * index appears in db) 94386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 95386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * this function should be called only after rdb_check has 96386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * indicated that the index does not appear in the rdb, e.g., a mutex 97386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * should protect the rdb between these calls 98386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 99386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 100386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 101386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_add_index(rdb_t *rdb, uint32_t index) { 102386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari int delta; 103386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 104386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* here we *assume* that index > rdb->window_start */ 105386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 106386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari delta = (index - rdb->window_start); 107386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (delta < rdb_bits_in_bitmask) { 108386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 109386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* if the index is within the window, set the appropriate bit */ 110386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari v128_set_bit(&rdb->bitmask, delta); 111386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 112386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else { 113386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 114386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari delta -= rdb_bits_in_bitmask - 1; 115386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 116386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* shift the window forward by delta bits*/ 117386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari v128_left_shift(&rdb->bitmask, delta); 118386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari v128_set_bit(&rdb->bitmask, rdb_bits_in_bitmask - 1); 119386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdb->window_start += delta; 120386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 121386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 122386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 123386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 124386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 125386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 126386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 127386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_increment(rdb_t *rdb) { 128386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 129386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb->window_start++ > 0x7fffffff) 130386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_key_expired; 131386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 132386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 133386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 134386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariuint32_t 135386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_get_value(const rdb_t *rdb) { 136386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return rdb->window_start; 137386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 138