From fd4e3c7c74ad4d1acb37c43fde8d18786616846a Mon Sep 17 00:00:00 2001 From: Yawning Angel Date: Thu, 22 May 2014 18:42:16 +0000 Subject: 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. --- replay_filter.go | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 138 insertions(+) create mode 100644 replay_filter.go (limited to 'replay_filter.go') 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 + * 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 : */ -- cgit v1.2.3