Add replay detection to handshakes.

This is done by maintaining a map keyed off the SipHash-2-4 digest of
the MAC_C component of the handshake.  Collisions, while possible are
unlikely in the extreme and are thus treated as replays.

In concept this is fairly similar to the ScrambleSuit `replay.py` code,
with a few modifications:

 * There is a upper bound on how large the replay filter can grow.
   Currently this is set to 102400 entries, though it is unlikely that
   this limit will be hit.

 * A doubly linked list is also maintained parallel to the map, so the
   filter compaction process does not need to iterate over the entire
   filter.

1 files changed, 138 insertions, 0 deletions

diff --git a/replay_filter.go b/replay_filter.go
new file mode 100644
index 0000000..f5c64f8
--- /dev/null
+++ b/replay_filter.go
@@ -0,0 +1,138 @@
+/*
+ * 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 obfs4
+
+import (
+	"container/list"
+	"crypto/rand"
+	"encoding/binary"
+	"sync"
+
+	"github.com/dchest/siphash"
+)
+
+// maxFilterSize is the maximum capacity of the replay filter.  The busiest
+// bridge I know about processes something along the order of 3000 connections
+// per day.  The maximum timespan any entry can live in the filter is 2 hours,
+// so this value should be sufficient.
+const maxFilterSize = 100 * 1024
+
+// replayFilter is a simple filter designed only to answer if it has seen a
+// given byte sequence before.  It is based around comparing the SipHash-2-4
+// digest of data to match against.  Collisions are treated as positive matches
+// however, the probability of such occurences is negligible.
+type replayFilter struct {
+	lock   sync.Mutex
+	key    [2]uint64
+	filter map[uint64]*filterEntry
+	fifo   *list.List
+}
+
+type filterEntry struct {
+	firstSeen int64
+	hash      uint64
+	element   *list.Element
+}
+
+// newReplayFilter creates a new replayFilter instance.
+func newReplayFilter() (filter *replayFilter, err error) {
+	// Initialize the SipHash-2-4 instance with a random key.
+	var key [16]byte
+	_, err = rand.Read(key[:])
+	if err != nil {
+		return
+	}
+
+	filter = new(replayFilter)
+	filter.key[0] = binary.BigEndian.Uint64(key[0:8])
+	filter.key[1] = binary.BigEndian.Uint64(key[8:16])
+	filter.filter = make(map[uint64]*filterEntry)
+	filter.fifo = list.New()
+
+	return
+}
+
+// testAndSet queries the filter for buf, adds it if it was not present and
+// returns if it has added the entry or not.
+func (f *replayFilter) testAndSet(now int64, buf []byte) bool {
+	hash := siphash.Hash(f.key[0], f.key[1], buf)
+
+	f.lock.Lock()
+	defer f.lock.Unlock()
+
+	f.compactFilter(now)
+
+	entry := f.filter[hash]
+	if entry != nil {
+		return true
+	}
+
+	entry = new(filterEntry)
+	entry.hash = hash
+	entry.firstSeen = now
+	entry.element = f.fifo.PushBack(entry)
+	f.filter[hash] = entry
+
+	return false
+}
+
+// compactFilter purges entries that are too old to be relevant.  If the filter
+// is filled to maxFilterCapacity, it will force purge a single entry.
+func (f *replayFilter) compactFilter(now int64) {
+	e := f.fifo.Front()
+	for e != nil {
+		entry, _ := e.Value.(*filterEntry)
+
+		// If the filter is at max capacity, force purge at least one entry.
+		if f.fifo.Len() < maxFilterSize {
+			deltaT := now - entry.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.filter = make(map[uint64]*filterEntry)
+				f.fifo = list.New()
+				return
+			}
+			if deltaT < 3600*2 {
+				// Why yes, this is 2 hours.  The MAC code includes a hour
+				// resolution timestamp, but to deal with clock skew, it
+				// accepts time +- 1 hour.
+				break
+			}
+		}
+		eNext := e.Next()
+		f.filter[entry.hash] = nil
+		f.fifo.Remove(entry.element)
+		entry.element = nil
+		e = eNext
+	}
+}
+
+/* vim :set ts=4 sw=4 sts=4 noet : */