Affiliations: Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA | Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712-1188, USA | System Software Department, IBM Austin Research Lab., 11400 Burnet Rd., M/S 9460, Austin, TX 78758, USA E-mail: huangct@cse.sc.edu, gouda@cs.utexas.edu, mootaz@us.ibm.com
Abstract: IPsec is the current security standard for the Internet Protocol IP. According to this standard, a selected computer pair (p, q) in the Internet can be designated a “security association”. This designation guarantees that all sent IP messages whose original source is computer p and whose ultimate destination is computer q cannot be replayed in the future (by an adversary between p and q) and still be received by computer q as fresh messages from p. This guarantee is provided by adding increasing sequence numbers to all IP messages sent from p to q. Thus, p needs to always remember the sequence number of the last sent message, and q needs to always remember the sequence number of the last received message. Unfortunately, when computer p or q is reset these sequence numbers can be forgotten, and this leads to two bad possibilities: unbounded number of fresh messages from p can be discarded by q, and unbounded number of replayed messages can be accepted by q. In this paper, we propose two operations, “SAVE” and “FETCH”, to prevent these possibilities. The SAVE operation can be used to store the last sent sequence number in persistent memory of p once every Kp sent messages, and can be used to store the last received sequence number in persistent memory of q once every Kq received messages. The FETCH operation can be used to fetch the last stored sequence number for a computer when that computer wakes up after a reset. We show that the following three conditions hold when SAVE and FETCH are adopted in both p and q. First, when p is reset, at most 2Kp sequence numbers will be lost but no fresh message sent from p to q will be discarded if no message reorder occurs. Second, when q is reset, the number of discarded fresh messages is bounded by 2Kq. In either case, no replayed message will be accepted by q.
