From 6b7fb33aa035bc07170811947582a08e5538a9a1 Mon Sep 17 00:00:00 2001 From: Sergey Matveev Date: Sun, 24 May 2015 10:53:09 +0300 Subject: [PATCH] Replace -noncediff with the hash keeping up to 256 seen nonces Signed-off-by: Sergey Matveev --- VERSION | 2 +- doc/client.texi | 3 -- doc/news.texi | 3 ++ doc/noncediff.texi | 17 ------- doc/server.texi | 4 -- doc/todo.texi | 1 - doc/transport.texi | 15 +++--- doc/user.texi | 2 - src/govpn/cmd/govpn-client/main.go | 2 - src/govpn/identify.go | 6 +-- src/govpn/transport.go | 74 +++++++++++++++++++----------- src/govpn/transport_test.go | 3 +- 12 files changed, 61 insertions(+), 71 deletions(-) delete mode 100644 doc/noncediff.texi diff --git a/VERSION b/VERSION index eb39e53..2f4b607 100644 --- a/VERSION +++ b/VERSION @@ -1 +1 @@ -3.3 +3.4 diff --git a/doc/client.texi b/doc/client.texi index a6fc6b0..e2c26fd 100644 --- a/doc/client.texi +++ b/doc/client.texi @@ -22,9 +22,6 @@ how to enter passphrase from stdin silently and store it in the file. @item -timeout @ref{Timeout} setting in seconds. -@item -noncediff -Allowable @ref{Nonce difference}. - @item -noise Enable @ref{Noise}. diff --git a/doc/news.texi b/doc/news.texi index b0b6437..d3a9ab1 100644 --- a/doc/news.texi +++ b/doc/news.texi @@ -8,6 +8,9 @@ @item Ability to use external @ref{EGD}-compatible PRNGs. Now you are able to use GoVPN even on systems with the bad @code{/dev/random}, providing higher quality entropy from external sources. +@item Removed @code{-noncediff} option. It is replaced with in-memory +storage of seen nonces, thus eliminating possible replay attacks at all +without performance degradation related to inbound packets reordering. @end itemize @item Release 3.3 diff --git a/doc/noncediff.texi b/doc/noncediff.texi deleted file mode 100644 index 7ce3aa2..0000000 --- a/doc/noncediff.texi +++ /dev/null @@ -1,17 +0,0 @@ -@node Nonce difference -@section Nonce difference - -GoVPN prevents replay attacks by remembering the last used nonce in -messages from the remote peer. All incoming messages must have higher -nonce number (technically it is counter), otherwise they are dropped. - -Because of UDP nature that does not guarantee packet ordering during -transmission, GoVPN will drop valid non-replayed UDP packets. That leads -to performance decrease. - -In most cases there is no need in so strict nonce boundaries and -@code{-noncediff} command line option allows to create the window of -allowable nonce differences. This is trade-off between highest security -and possible performance degradation. For example @code{-noncediff 128} -works rather well (no packet drops) with 1 Gbps link with two switches. -By default no nonce differences are allowed (highest security). diff --git a/doc/server.texi b/doc/server.texi index 810461e..989a8a8 100644 --- a/doc/server.texi +++ b/doc/server.texi @@ -46,10 +46,6 @@ Optional. Contains human readable username. Used to beauty output of Optional. Contains @ref{Timeout} setting (decimal notation) in seconds. Otherwise default minute timeout will be used. -@item noncediff -Optional. Contains allowable @ref{Nonce difference} setting (decimal -notation). - @item noise Optional. Contains either "1" (enable @ref{Noise} adding), or "0". diff --git a/doc/todo.texi b/doc/todo.texi index 8e912e3..481bb19 100644 --- a/doc/todo.texi +++ b/doc/todo.texi @@ -2,7 +2,6 @@ @unnumbered TODO @itemize -@item Replace -noncediff with in-memory storage of previously seen nonces. @item Ability to tunnel only specified TCP connections, without full featured VPN solution. Similar to ssh -R. @item Ability to work over HTTP, WebSockets and something similar. diff --git a/doc/transport.texi b/doc/transport.texi index b762861..c1e0d7f 100644 --- a/doc/transport.texi +++ b/doc/transport.texi @@ -34,12 +34,9 @@ Salsa20 output are used as a one-time key for @code{AUTH}. Next 256 bits of Salsa20 are ignored. All remaining output is XORed with the data, encrypting it. -To prevent replay attacks we remember latest @code{SERIAL} from the -remote peer. If received message's @code{SERIAL} is not greater that the -saved one, then drop it. Optionally, because some UDP packets can be -reordered during transmission, we can allow some window for valid -serials with the @code{-noncediff} option. @code{-noncediff 10} with -current saved serial state equals to 78 allows messages with 68…78 -serials. That time window can be used by attacker to replay packets, so -by default it equals to 1. However it can improve performance because of -rearranged UDP packets. +To prevent replay attacks we must remember received @code{SERIAL}s and +if meet one, then drop it. Basically we could just store latest number +and check if received one is greater, but because of UDP packets +reordering this can lead to valid packets dropping and overall +performance degradation. We store 256 seen nonces in hash structure, in +two swapping buckets. diff --git a/doc/user.texi b/doc/user.texi index 19e24e3..3702f84 100644 --- a/doc/user.texi +++ b/doc/user.texi @@ -14,7 +14,6 @@ automate it using up and down shell scripts. * Identity:: * PAKE:: Password Authenticated Key Agreement * Timeout:: -* Nonce difference:: * MTU:: Maximum Transmission Unit * Stats:: * Noise:: @@ -29,7 +28,6 @@ automate it using up and down shell scripts. @include identity.texi @include pake.texi @include timeout.texi -@include noncediff.texi @include mtu.texi @include stats.texi @include noise.texi diff --git a/src/govpn/cmd/govpn-client/main.go b/src/govpn/cmd/govpn-client/main.go index f212490..9b65677 100644 --- a/src/govpn/cmd/govpn-client/main.go +++ b/src/govpn/cmd/govpn-client/main.go @@ -39,7 +39,6 @@ var ( downPath = flag.String("down", "", "Path to down-script") stats = flag.String("stats", "", "Enable stats retrieving on host:port") mtu = flag.Int("mtu", 1452, "MTU for outgoing packets") - nonceDiff = flag.Int("noncediff", 1, "Allow nonce difference") timeoutP = flag.Int("timeout", 60, "Timeout seconds") noisy = flag.Bool("noise", false, "Enable noise appending") cpr = flag.Int("cpr", 0, "Enable constant KiB/sec out traffic rate") @@ -68,7 +67,6 @@ func main() { conf := &govpn.PeerConf{ Id: id, Timeout: time.Second * time.Duration(timeout), - Noncediff: *nonceDiff, NoiseEnable: *noisy, CPR: *cpr, DSAPub: pub, diff --git a/src/govpn/identify.go b/src/govpn/identify.go index 663afe7..c7675b6 100644 --- a/src/govpn/identify.go +++ b/src/govpn/identify.go @@ -59,7 +59,6 @@ func (id PeerId) MarshalJSON() ([]byte, error) { type PeerConf struct { Id *PeerId Timeout time.Duration - Noncediff int NoiseEnable bool CPR int // This is passphrase verifier @@ -180,7 +179,7 @@ func (id *PeerId) Conf() *PeerConf { if dummyConf != nil { return dummyConf } - conf := PeerConf{Id: id, Noncediff: 1, NoiseEnable: false, CPR: 0} + conf := PeerConf{Id: id, NoiseEnable: false, CPR: 0} peerPath := path.Join(PeersPath, id.String()) verPath := path.Join(peerPath, "verifier") @@ -207,9 +206,6 @@ func (id *PeerId) Conf() *PeerConf { } conf.Timeout = time.Second * time.Duration(timeout) - if val, err := readIntFromFile(path.Join(peerPath, "noncediff")); err == nil { - conf.Noncediff = val - } if val, err := readIntFromFile(path.Join(peerPath, "noise")); err == nil && val == 1 { conf.NoiseEnable = true } diff --git a/src/govpn/transport.go b/src/govpn/transport.go index f46eeef..2f5a345 100644 --- a/src/govpn/transport.go +++ b/src/govpn/transport.go @@ -30,7 +30,8 @@ import ( ) const ( - NonceSize = 8 + NonceSize = 8 + NonceBucketSize = 128 // S20BS is Salsa20's internal blocksize in bytes S20BS = 64 // Maximal amount of bytes transfered with single key (4 GiB) @@ -56,11 +57,14 @@ type Peer struct { CPRCycle time.Duration `json:"-"` // Cryptography related - Key *[SSize]byte `json:"-"` - Noncediff int - NonceOur uint64 `json:"-"` - NonceRecv uint64 `json:"-"` - NonceCipher *xtea.Cipher `json:"-"` + Key *[SSize]byte `json:"-"` + NonceOur uint64 `json:"-"` + NonceRecv uint64 `json:"-"` + NonceCipher *xtea.Cipher `json:"-"` + nonceBucket0 map[uint64]struct{} + nonceBucket1 map[uint64]struct{} + nonceFound bool + nonceBucketN int32 // Timers Timeout time.Duration `json:"-"` @@ -243,23 +247,24 @@ func newPeer(addr *net.UDPAddr, conf *PeerConf, nonce int, key *[SSize]byte) *Pe timeout = timeout / TimeoutHeartbeat } peer := Peer{ - Addr: addr, - Timeout: timeout, - Established: now, - LastPing: now, - Id: conf.Id, - NoiseEnable: noiseEnable, - CPR: conf.CPR, - CPRCycle: cprCycle, - Noncediff: conf.Noncediff, - NonceOur: uint64(conf.Noncediff + nonce), - NonceRecv: uint64(conf.Noncediff + 0), - Key: key, - NonceCipher: newNonceCipher(key), - buf: make([]byte, MTU+S20BS), - tag: new([poly1305.TagSize]byte), - keyAuth: new([SSize]byte), - nonce: make([]byte, NonceSize), + Addr: addr, + Timeout: timeout, + Established: now, + LastPing: now, + Id: conf.Id, + NoiseEnable: noiseEnable, + CPR: conf.CPR, + CPRCycle: cprCycle, + NonceOur: uint64(nonce), + NonceRecv: uint64(0), + nonceBucket0: make(map[uint64]struct{}, NonceBucketSize), + nonceBucket1: make(map[uint64]struct{}, NonceBucketSize), + Key: key, + NonceCipher: newNonceCipher(key), + buf: make([]byte, MTU+S20BS), + tag: new([poly1305.TagSize]byte), + keyAuth: new([SSize]byte), + nonce: make([]byte, NonceSize), } return &peer } @@ -286,14 +291,31 @@ func (p *Peer) UDPProcess(udpPkt []byte, tap io.Writer, ready chan struct{}) boo p.FramesUnauth++ return false } + + // Check if received nonce is known to us in either of two buckets. + // If yes, then this is ignored duplicate. + // Check from the oldest bucket, as in most cases this will result + // in constant time check. + // If Bucket0 is filled, then it becomes Bucket1. p.NonceCipher.Decrypt(p.buf, udpPkt[:NonceSize]) + ready <- struct{}{} p.nonceRecv, _ = binary.Uvarint(p.buf[:NonceSize]) - if int(p.NonceRecv)-p.Noncediff >= 0 && int(p.nonceRecv) < int(p.NonceRecv)-p.Noncediff { - ready <- struct{}{} + if _, p.nonceFound = p.nonceBucket1[p.NonceRecv]; p.nonceFound { p.FramesDup++ return false } - ready <- struct{}{} + if _, p.nonceFound = p.nonceBucket0[p.NonceRecv]; p.nonceFound { + p.FramesDup++ + return false + } + p.nonceBucket0[p.NonceRecv] = struct{}{} + p.nonceBucketN++ + if p.nonceBucketN == NonceBucketSize { + p.nonceBucket1 = p.nonceBucket0 + p.nonceBucket0 = make(map[uint64]struct{}, NonceBucketSize) + p.nonceBucketN = 0 + } + p.FramesIn++ p.BytesIn += int64(p.size) p.LastPing = time.Now() diff --git a/src/govpn/transport_test.go b/src/govpn/transport_test.go index d12c26d..45f4d01 100644 --- a/src/govpn/transport_test.go +++ b/src/govpn/transport_test.go @@ -24,7 +24,6 @@ func init() { conf = &PeerConf{ Id: peerId, Timeout: time.Second * time.Duration(TimeoutDefault), - Noncediff: 1, NoiseEnable: false, CPR: 0, } @@ -62,6 +61,8 @@ func BenchmarkDec(b *testing.B) { peer = newPeer(addr, conf, 128, new([SSize]byte)) b.ResetTimer() for i := 0; i < b.N; i++ { + peer.nonceBucket0 = make(map[uint64]struct{}, 1) + peer.nonceBucket1 = make(map[uint64]struct{}, 1) if !peer.UDPProcess(ciphertext, dummy, ready) { b.Fail() } -- 2.44.0