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 --- keypair.go | 3 +- misc.go | 7 --- receive.go | 2 +- replay.go | 79 --------------------------------- replay/replay.go | 84 +++++++++++++++++++++++++++++++++++ replay/replay_test.go | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++ replay_test.go | 118 ------------------------------------------------- 7 files changed, 207 insertions(+), 206 deletions(-) delete mode 100644 replay.go create mode 100644 replay/replay.go create mode 100644 replay/replay_test.go delete mode 100644 replay_test.go diff --git a/keypair.go b/keypair.go index be7600b..face310 100644 --- a/keypair.go +++ b/keypair.go @@ -7,6 +7,7 @@ package main import ( + "./replay" "crypto/cipher" "sync" "time" @@ -23,7 +24,7 @@ type Keypair struct { sendNonce uint64 send cipher.AEAD receive cipher.AEAD - replayFilter ReplayFilter + replayFilter replay.ReplayFilter isInitiator bool created time.Time localIndex uint32 diff --git a/misc.go b/misc.go index af61718..ede94f9 100644 --- a/misc.go +++ b/misc.go @@ -47,10 +47,3 @@ func min(a, b uint) uint { } return a } - -func minUint64(a uint64, b uint64) uint64 { - if a > b { - return b - } - return a -} diff --git a/receive.go b/receive.go index 3d9710c..707b056 100644 --- a/receive.go +++ b/receive.go @@ -544,7 +544,7 @@ func (peer *Peer) RoutineSequentialReceiver() { // check for replay - if !elem.keypair.replayFilter.ValidateCounter(elem.counter) { + if !elem.keypair.replayFilter.ValidateCounter(elem.counter, RejectAfterMessages) { continue } diff --git a/replay.go b/replay.go deleted file mode 100644 index 2d9c6e1..0000000 --- a/replay.go +++ /dev/null @@ -1,79 +0,0 @@ -/* 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 main - -/* Copyright (C) 2015-2017 Jason A. Donenfeld . All Rights Reserved. */ - -/* 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 -) - -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) bool { - if counter >= RejectAfterMessages { - 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.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) +} diff --git a/replay_test.go b/replay_test.go deleted file mode 100644 index 8b2e57d..0000000 --- a/replay_test.go +++ /dev/null @@ -1,118 +0,0 @@ -/* 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 main - -import ( - "testing" -) - -/* Ported from the linux kernel implementation - * - * - */ - -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) != 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-54-g00ecf