Replace -noncediff with the hash keeping up to 256 seen nonces

Signed-off-by: Sergey Matveev <stargrave@stargrave.org>

diff --git a/VERSION b/VERSION
index eb39e5382f4f035e4d71c7f67712cdbfa6c0c335..2f4b60750dc3500b0e4cf08f316a960a7ca42b40 100644 (file)
--- a/VERSION
+++ b/VERSION
@@ -1 +1 @@
-3.3
+3.4

diff --git a/doc/client.texi b/doc/client.texi
index a6fc6b017602ffcb3cb9fac33dfbc98ec948c10d..e2c26fd727b83089a079e0d1afb14b899ce2d18f 100644 (file)
--- 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 -timeout
 @ref{Timeout} setting in seconds.
 

-@item -noncediff
-Allowable @ref{Nonce difference}.
-

 @item -noise
 Enable @ref{Noise}.
 
 @item -noise
 Enable @ref{Noise}.
 

diff --git a/doc/news.texi b/doc/news.texi
index b0b64372755ffcbdcbfa6b57059092a2cfd5add3..d3a9ab13a56cb511b7afdea17373fd83efa65282 100644 (file)
--- 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 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
 @end itemize
 
 @item Release 3.3

diff --git a/doc/noncediff.texi b/doc/noncediff.texi
deleted file mode 100644 (file)
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 810461ee5077016f6d2830e4cb5d0ca733ec5b8f..989a8a8a8f8e17f0964a7e15a36d82aed7d3fa4f 100644 (file)
--- 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.
 
 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".
 
 @item noise
 Optional. Contains either "1" (enable @ref{Noise} adding), or "0".
 

diff --git a/doc/todo.texi b/doc/todo.texi
index 8e912e3a704d823f5b106b624c98f4aa2a0b9b14..481bb19415e8d8d2aec7a5aa989f7981c5031727 100644 (file)
--- a/doc/todo.texi
+++ b/doc/todo.texi
@@ -2,7 +2,6 @@
 @unnumbered TODO
 
 @itemize
 @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.
 @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 b76286138f63af78bb9f43bc02ec5d774d1e5716..c1e0d7f02ad0dfa39788500d6c0c7165e9e9a48e 100644 (file)
--- 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.
 
 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 19e24e300b0cd204d6110d51d984f27474166c24..3702f8488b7c5a005e7b003cbcb9b466e7b62b93 100644 (file)
--- 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::
 * Identity::
 * PAKE:: Password Authenticated Key Agreement
 * Timeout::

-* Nonce difference::

 * MTU:: Maximum Transmission Unit
 * Stats::
 * Noise::
 * 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 identity.texi
 @include pake.texi
 @include timeout.texi

-@include noncediff.texi

 @include mtu.texi
 @include stats.texi
 @include noise.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 f21249061d4ed0e637f775beccca6c88291ed712..9b6567763ecea2e8f1787c9230f7f712aea0a78a 100644 (file)
--- 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")
        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")
        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),
        conf := &govpn.PeerConf{
                Id:          id,
                Timeout:     time.Second * time.Duration(timeout),

-               Noncediff:   *nonceDiff,

                NoiseEnable: *noisy,
                CPR:         *cpr,
                DSAPub:      pub,
                NoiseEnable: *noisy,
                CPR:         *cpr,
                DSAPub:      pub,

diff --git a/src/govpn/identify.go b/src/govpn/identify.go
index 663afe73599bf14b8fc40acf7e2b738c9ae6d7e6..c7675b6368b48cc62e7eef3180e8515ac1421e1b 100644 (file)
--- 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
 type PeerConf struct {
        Id          *PeerId
        Timeout     time.Duration

-       Noncediff   int

        NoiseEnable bool
        CPR         int
        // This is passphrase verifier
        NoiseEnable bool
        CPR         int
        // This is passphrase verifier


@@ -180,7 +179,7 @@ func (id *PeerId) Conf() *PeerConf {
        if dummyConf != nil {
                return dummyConf
        }
        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")
        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)
 
        }
        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
        }
        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 f46eeefb62b3aae5c9af6fbebe46705d9688e1b7..2f5a345e57a6f5c1dd9034f7885408ff886db64b 100644 (file)
--- a/src/govpn/transport.go
+++ b/src/govpn/transport.go
@@ -30,7 +30,8 @@ import (
 )
 
 const (
 )
 
 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)
        // 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
        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:"-"`
 
        // 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{
                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
 }
        }
        return &peer
 }


@@ -286,14 +291,31 @@ func (p *Peer) UDPProcess(udpPkt []byte, tap io.Writer, ready chan struct{}) boo
                p.FramesUnauth++
                return false
        }
                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])
        p.NonceCipher.Decrypt(p.buf, udpPkt[:NonceSize])

+       ready <- struct{}{}

        p.nonceRecv, _ = binary.Uvarint(p.buf[:NonceSize])
        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
        }
                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()
        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 d12c26dacb68210e1f54ebf8d93ced4580d9eb3f..45f4d01cb6b6997bd871b7d9b6a5df29c87894d0 100644 (file)
--- 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),
        conf = &PeerConf{
                Id:          peerId,
                Timeout:     time.Second * time.Duration(TimeoutDefault),

-               Noncediff:   1,

                NoiseEnable: false,
                CPR:         0,
        }
                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 = 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()
                }
                if !peer.UDPProcess(ciphertext, dummy, ready) {
                        b.Fail()
                }