From 5a2228a5c910ada948677f1dd3fcc59f74e5cb20 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Wed, 23 May 2018 02:32:02 +0200 Subject: Move replay into subpackage --- replay/replay.go | 84 +++++++++++++++++++++++++++++++++++ replay/replay_test.go | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 204 insertions(+) create mode 100644 replay/replay.go create mode 100644 replay/replay_test.go (limited to 'replay') diff --git a/replay/replay.go b/replay/replay.go new file mode 100644 index 0000000..993ff58 --- /dev/null +++ b/replay/replay.go @@ -0,0 +1,84 @@ +/* SPDX-License-Identifier: GPL-2.0 + * + * Copyright (C) 2017-2018 Jason A. Donenfeld . All Rights Reserved. + * Copyright (C) 2017-2018 Mathias N. Hall-Andersen . + */ + +package replay + +/* Implementation of RFC6479 + * https://tools.ietf.org/html/rfc6479 + * + * The implementation is not safe for concurrent use! + */ + +const ( + // See: https://golang.org/src/math/big/arith.go + _Wordm = ^uintptr(0) + _WordLogSize = _Wordm>>8&1 + _Wordm>>16&1 + _Wordm>>32&1 + _WordSize = 1 << _WordLogSize +) + +const ( + CounterRedundantBitsLog = _WordLogSize + 3 + CounterRedundantBits = _WordSize * 8 + CounterBitsTotal = 2048 + CounterWindowSize = uint64(CounterBitsTotal - CounterRedundantBits) +) + +const ( + BacktrackWords = CounterBitsTotal / _WordSize +) + +func minUint64(a uint64, b uint64) uint64 { + if a > b { + return b + } + return a +} + +type ReplayFilter struct { + counter uint64 + backtrack [BacktrackWords]uintptr +} + +func (filter *ReplayFilter) Init() { + filter.counter = 0 + filter.backtrack[0] = 0 +} + +func (filter *ReplayFilter) ValidateCounter(counter uint64, limit uint64) bool { + if counter >= limit { + return false + } + + indexWord := counter >> CounterRedundantBitsLog + + if counter > filter.counter { + + // move window forward + + current := filter.counter >> CounterRedundantBitsLog + diff := minUint64(indexWord-current, BacktrackWords) + for i := uint64(1); i <= diff; i++ { + filter.backtrack[(current+i)%BacktrackWords] = 0 + } + filter.counter = counter + + } else if filter.counter-counter > CounterWindowSize { + + // behind current window + + return false + } + + indexWord %= BacktrackWords + indexBit := counter & uint64(CounterRedundantBits-1) + + // check and set bit + + oldValue := filter.backtrack[indexWord] + newValue := oldValue | (1 << indexBit) + filter.backtrack[indexWord] = newValue + return oldValue != newValue +} diff --git a/replay/replay_test.go b/replay/replay_test.go new file mode 100644 index 0000000..da39498 --- /dev/null +++ b/replay/replay_test.go @@ -0,0 +1,120 @@ +/* SPDX-License-Identifier: GPL-2.0 + * + * Copyright (C) 2017-2018 Jason A. Donenfeld . All Rights Reserved. + * Copyright (C) 2017-2018 Mathias N. Hall-Andersen . + */ + +package replay + +import ( + "testing" +) + +/* Ported from the linux kernel implementation + * + * + */ + +const RejectAfterMessages = (1 << 64) - (1 << 4) - 1 + +func TestReplay(t *testing.T) { + var filter ReplayFilter + + T_LIM := CounterWindowSize + 1 + + testNumber := 0 + T := func(n uint64, v bool) { + testNumber++ + if filter.ValidateCounter(n, RejectAfterMessages) != v { + t.Fatal("Test", testNumber, "failed", n, v) + } + } + + filter.Init() + + T(0, true) /* 1 */ + T(1, true) /* 2 */ + T(1, false) /* 3 */ + T(9, true) /* 4 */ + T(8, true) /* 5 */ + T(7, true) /* 6 */ + T(7, false) /* 7 */ + T(T_LIM, true) /* 8 */ + T(T_LIM-1, true) /* 9 */ + T(T_LIM-1, false) /* 10 */ + T(T_LIM-2, true) /* 11 */ + T(2, true) /* 12 */ + T(2, false) /* 13 */ + T(T_LIM+16, true) /* 14 */ + T(3, false) /* 15 */ + T(T_LIM+16, false) /* 16 */ + T(T_LIM*4, true) /* 17 */ + T(T_LIM*4-(T_LIM-1), true) /* 18 */ + T(10, false) /* 19 */ + T(T_LIM*4-T_LIM, false) /* 20 */ + T(T_LIM*4-(T_LIM+1), false) /* 21 */ + T(T_LIM*4-(T_LIM-2), true) /* 22 */ + T(T_LIM*4+1-T_LIM, false) /* 23 */ + T(0, false) /* 24 */ + T(RejectAfterMessages, false) /* 25 */ + T(RejectAfterMessages-1, true) /* 26 */ + T(RejectAfterMessages, false) /* 27 */ + T(RejectAfterMessages-1, false) /* 28 */ + T(RejectAfterMessages-2, true) /* 29 */ + T(RejectAfterMessages+1, false) /* 30 */ + T(RejectAfterMessages+2, false) /* 31 */ + T(RejectAfterMessages-2, false) /* 32 */ + T(RejectAfterMessages-3, true) /* 33 */ + T(0, false) /* 34 */ + + t.Log("Bulk test 1") + filter.Init() + testNumber = 0 + for i := uint64(1); i <= CounterWindowSize; i++ { + T(i, true) + } + T(0, true) + T(0, false) + + t.Log("Bulk test 2") + filter.Init() + testNumber = 0 + for i := uint64(2); i <= CounterWindowSize+1; i++ { + T(i, true) + } + T(1, true) + T(0, false) + + t.Log("Bulk test 3") + filter.Init() + testNumber = 0 + for i := CounterWindowSize + 1; i > 0; i-- { + T(i, true) + } + + t.Log("Bulk test 4") + filter.Init() + testNumber = 0 + for i := CounterWindowSize + 2; i > 1; i-- { + T(i, true) + } + T(0, false) + + t.Log("Bulk test 5") + filter.Init() + testNumber = 0 + for i := CounterWindowSize; i > 0; i-- { + T(i, true) + } + T(CounterWindowSize+1, true) + T(0, false) + + t.Log("Bulk test 6") + filter.Init() + testNumber = 0 + for i := CounterWindowSize; i > 0; i-- { + T(i, true) + } + T(0, true) + T(CounterWindowSize+1, true) +} -- cgit v1.2.3