2 files changed, 242 insertions, 0 deletions
diff --git a/common/replayfilter/replay_filter.go b/common/replayfilter/replay_filter.go
new file mode 100644
index 0000000..95cc5d6
--- /dev/null
+++ b/common/replayfilter/replay_filter.go
@@ -0,0 +1,147 @@
+/*
+ * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *  * Redistributions of source code must retain the above copyright notice,
+ *    this list of conditions and the following disclaimer.
+ *
+ *  * Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+// Package replayfilter implements a generic replay detection filter with a
+// caller specifiable time-to-live.  It only detects if a given byte sequence
+// has been seen before based on the SipHash-2-4 digest of the sequence.
+// Collisions are treated as positive matches, though the probability of this
+// happening is negligible.
+package replayfilter
+
+import (
+	"container/list"
+	"encoding/binary"
+	"sync"
+	"time"
+
+	"github.com/dchest/siphash"
+
+	"git.torproject.org/pluggable-transports/obfs4.git/common/csrand"
+)
+
+// maxFilterSize is the maximum capacity of a replay filter.  This value is
+// more as a safeguard to prevent runaway filter growth, and is sized to be
+// serveral orders of magnitude greater than the number of connections a busy
+// bridge sees in one day, so in practice should never be reached.
+const maxFilterSize = 100 * 1024
+
+type entry struct {
+	digest    uint64
+	firstSeen time.Time
+	element   *list.Element
+}
+
+// ReplayFilter is a simple filter designed only to detect if a given byte
+// sequence has been seen before.
+type ReplayFilter struct {
+	sync.Mutex
+
+	filter map[uint64]*entry
+	fifo   *list.List
+
+	key [2]uint64
+	ttl time.Duration
+}
+
+// New creates a new ReplayFilter instance.
+func New(ttl time.Duration) (filter *ReplayFilter, err error) {
+	// Initialize the SipHash-2-4 instance with a random key.
+	var key [16]byte
+	if err = csrand.Bytes(key[:]); err != nil {
+		return
+	}
+
+	filter = new(ReplayFilter)
+	filter.filter = make(map[uint64]*entry)
+	filter.fifo = list.New()
+	filter.key[0] = binary.BigEndian.Uint64(key[0:8])
+	filter.key[1] = binary.BigEndian.Uint64(key[8:16])
+	filter.ttl = ttl
+
+	return
+}
+
+// TestAndSet queries the filter for a given byte sequence, inserts the
+// sequence, and returns if it was present before the insertion operation.
+func (f *ReplayFilter) TestAndSet(now time.Time, buf []byte) bool {
+	digest := siphash.Hash(f.key[0], f.key[1], buf)
+
+	f.Lock()
+	defer f.Unlock()
+
+	f.compactFilter(now)
+
+	if e := f.filter[digest]; e != nil {
+		// Hit.  Just return.
+		return true
+	}
+
+	// Miss.  Add a new entry.
+	e := new(entry)
+	e.digest = digest
+	e.firstSeen = now
+	e.element = f.fifo.PushBack(e)
+	f.filter[digest] = e
+
+	return false
+}
+
+func (f *ReplayFilter) compactFilter(now time.Time) {
+	e := f.fifo.Front()
+	for e != nil {
+		ent, _ := e.Value.(*entry)
+
+		// If the filter is not full, only purge entries that exceed the TTL,
+		// otherwise purge at least one entry, then revert to TTL based
+		// compaction.
+		if f.fifo.Len() < maxFilterSize && f.ttl > 0 {
+			deltaT := now.Sub(ent.firstSeen)
+			if deltaT < 0 {
+				// Aeeeeeee, the system time jumped backwards, potentially by
+				// a lot.  This will eventually self-correct, but "eventually"
+				// could be a long time.  As much as this sucks, jettison the
+				// entire filter.
+				f.reset()
+				return
+			} else if deltaT < f.ttl {
+				return
+			}
+		}
+
+		// Remove the eldest entry.
+		eNext := e.Next()
+		delete(f.filter, ent.digest)
+		f.fifo.Remove(ent.element)
+		ent.element = nil
+		e = eNext
+	}
+}
+
+func (f *ReplayFilter) reset() {
+	f.filter = make(map[uint64]*entry)
+	f.fifo = list.New()
+}
diff --git a/common/replayfilter/replay_filter_test.go b/common/replayfilter/replay_filter_test.go
new file mode 100644
index 0000000..884e4fb
--- /dev/null
+++ b/common/replayfilter/replay_filter_test.go
@@ -0,0 +1,95 @@
+/*
+ * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *  * Redistributions of source code must retain the above copyright notice,
+ *    this list of conditions and the following disclaimer.
+ *
+ *  * Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package replayfilter
+
+import (
+	"testing"
+	"time"
+)
+
+func TestReplayFilter(t *testing.T) {
+	ttl := 10 * time.Second
+
+	f, err := New(ttl)
+	if err != nil {
+		t.Fatal("newReplayFilter failed:", err)
+	}
+
+	buf := []byte("This is a test of the Emergency Broadcast System.")
+	now := time.Now()
+
+	// testAndSet into empty filter, returns false (not present).
+	set := f.TestAndSet(now, buf)
+	if set {
+		t.Fatal("TestAndSet empty filter returned true")
+	}
+
+	// testAndSet into filter containing entry, should return true(present).
+	set = f.TestAndSet(now, buf)
+	if !set {
+		t.Fatal("testAndSet populated filter (replayed) returned false")
+	}
+
+	buf2 := []byte("This concludes this test of the Emergency Broadcast System.")
+	now = now.Add(ttl)
+
+	// testAndSet with time advanced.
+	set = f.TestAndSet(now, buf2)
+	if set {
+		t.Fatal("testAndSet populated filter, 2nd entry returned true")
+	}
+	set = f.TestAndSet(now, buf2)
+	if !set {
+		t.Fatal("testAndSet populated filter, 2nd entry (replayed) returned false")
+	}
+
+	// Ensure that the first entry has been removed by compact.
+	set = f.TestAndSet(now, buf)
+	if set {
+		t.Fatal("testAndSet populated filter, compact check returned true")
+	}
+
+	// Ensure that the filter gets reaped if the clock jumps backwards.
+	now = time.Time{}
+	set = f.TestAndSet(now, buf)
+	if set {
+		t.Fatal("testAndSet populated filter, backward time jump returned true")
+	}
+	if len(f.filter) != 1 {
+		t.Fatal("filter map has a unexpected number of entries:", len(f.filter))
+	}
+	if f.fifo.Len() != 1 {
+		t.Fatal("filter fifo has a unexpected number of entries:", f.fifo.Len())
+	}
+
+	// Ensure that the entry is properly added after reaping.
+	set = f.TestAndSet(now, buf)
+	if !set {
+		t.Fatal("testAndSet populated filter, post-backward clock jump (replayed) returned false")
+	}
+}