[tor-commits] [obfs4/master] Massive cleanup/code reorg.

commit 339c63f0c8cd4374f6fa26484498eb6fa91b7bca Author: Yawning Angel <yawning@torproject.org> Date: Sun Aug 17 17:11:03 2014 +0000 Massive cleanup/code reorg. * Changed obfs4proxy to be more like obfsproxy in terms of design, including being an easy framework for developing new TCP/IP style pluggable transports. * Added support for also acting as an obfs2/obfs3 client or bridge as a transition measure (and because the code itself is trivial). * Massively cleaned up the obfs4 and related code to be easier to read, and more idiomatic Go-like in style. * To ease deployment, obfs4proxy will now autogenerate the node-id, curve25519 keypair, and drbg seed if none are specified, and save them to a JSON file in the pt_state directory (Fixes Tor bug #12605). --- README.md | 23 +- common/csrand/csrand.go | 101 ++++ common/drbg/hash_drbg.go | 149 ++++++ common/ntor/ntor.go | 432 ++++++++++++++++ common/ntor/ntor_test.go | 180 +++++++ common/probdist/weighted_dist.go | 220 +++++++++ common/probdist/weighted_dist_test.go | 80 +++ common/replayfilter/replay_filter.go | 147 ++++++ common/replayfilter/replay_filter_test.go | 95 ++++ common/uniformdh/uniformdh.go | 183 +++++++ common/uniformdh/uniformdh_test.go | 220 +++++++++ csrand/csrand.go | 102 ---- drbg/hash_drbg.go | 147 ------ framing/framing.go | 310 ------------ framing/framing_test.go | 171 ------- handshake_ntor.go | 427 ---------------- handshake_ntor_test.go | 221 --------- ntor/ntor.go | 437 ----------------- ntor/ntor_test.go | 182 ------- obfs4.go | 758 ----------------------------- obfs4proxy/obfs4proxy.go | 553 ++++++++++----------- obfs4proxy/proxy_extras.go | 51 -- obfs4proxy/proxy_http.go | 3 - obfs4proxy/proxy_socks4.go | 2 - obfs4proxy/pt_extras.go | 23 +- packet.go | 212 -------- replay_filter.go | 145 ------ replay_filter_test.go | 92 ---- transports/base/base.go | 88 ++++ transports/obfs2/obfs2.go | 367 ++++++++++++++ transports/obfs3/obfs3.go | 358 ++++++++++++++ transports/obfs4/framing/framing.go | 308 ++++++++++++ transports/obfs4/framing/framing_test.go | 169 +++++++ transports/obfs4/handshake_ntor.go | 426 ++++++++++++++++ transports/obfs4/handshake_ntor_test.go | 222 +++++++++ transports/obfs4/obfs4.go | 579 ++++++++++++++++++++++ transports/obfs4/packet.go | 179 +++++++ transports/obfs4/statefile.go | 156 ++++++ transports/transports.go | 91 ++++ weighted_dist.go | 212 -------- weighted_dist_test.go | 82 ---- 41 files changed, 5014 insertions(+), 3889 deletions(-) diff --git a/README.md b/README.md index c97588a..3ee9c0c 100644 --- a/README.md +++ b/README.md @@ -1,12 +1,6 @@ ## obfs4 - The obfourscator #### Yawning Angel (yawning at torproject dot org) -### WARNING - -This is pre-alpha. Don't expect any security or wire protocol stability yet. -If you want to use something like this, you should currently probably be looking -at ScrambleSuit. - ### What? This is a look-like nothing obfuscation protocol that incorporates ideas and @@ -22,6 +16,9 @@ The notable differences between ScrambleSuit and obfs4: obfuscated via the Elligator 2 mapping. * The link layer encryption uses NaCl secret boxes (Poly1305/XSalsa20). +As an added bonus, obfs4proxy also supports acting as an obfs2/3 client and +bridge to ease the transition to the new protocol. + ### Why not extend ScrambleSuit? It's my protocol and I'll obfuscate if I want to. @@ -43,20 +40,6 @@ listed for clarity. * SipHash-2-4 (https://github.com/dchest/siphash) * goptlib (https://git.torproject.org/pluggable-transports/goptlib.git) -### TODO - - * Code cleanups. - * Write more unit tests. - * Optimize further. - -### WON'T DO - - * I do not care that much about standalone mode. Patches *MAY* be accepted, - especially if they are clean and are useful to Tor users. - * Yes, I use a bunch of code from the borg^w^wGoogle. If that bothers you - feel free to write your own implementation. - * I do not care about older versions of the go runtime. - ### Thanks * David Fifield for goptlib. diff --git a/common/csrand/csrand.go b/common/csrand/csrand.go new file mode 100644 index 0000000..45849d3 --- /dev/null +++ b/common/csrand/csrand.go @@ -0,0 +1,101 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 csrand implements the math/rand interface over crypto/rand, along +// with some utility functions for common random number/byte related tasks. +// +// Not all of the convinience routines are replicated, only those that are +// immediately useful. The Rand variable provides access to the full math/rand +// API. +package csrand + +import ( + cryptRand "crypto/rand" + "encoding/binary" + "fmt" + "io" + "math/rand" +) + +var ( + csRandSourceInstance csRandSource + + // Rand is a math/rand instance backed by crypto/rand CSPRNG. + Rand = rand.New(csRandSourceInstance) +) + +type csRandSource struct { + // This does not keep any state as it is backed by crypto/rand. +} + +func (r csRandSource) Int63() int64 { + var src [8]byte + if err := Bytes(src[:]); err != nil { + panic(err) + } + val := binary.BigEndian.Uint64(src[:]) + val &= (1<<63 - 1) + + return int64(val) +} + +func (r csRandSource) Seed(seed int64) { + // No-op. +} + +// Intn returns, as a int, a pseudo random number in [0, n). +func Intn(n int) int { + return Rand.Intn(n) +} + +// Float64 returns, as a float64, a pesudo random number in [0.0,1.0). +func Float64() float64 { + return Rand.Float64() +} + +// IntRange returns a uniformly distributed int [min, max]. +func IntRange(min, max int) int { + if max < min { + panic(fmt.Sprintf("IntRange: min > max (%d, %d)", min, max)) + } + + r := (max + 1) - min + ret := Rand.Intn(r) + return ret + min +} + +// Bytes fills the slice with random data. +func Bytes(buf []byte) error { + if _, err := io.ReadFull(cryptRand.Reader, buf); err != nil { + return err + } + + return nil +} + +// Reader is a alias of rand.Reader. +var Reader = cryptRand.Reader diff --git a/common/drbg/hash_drbg.go b/common/drbg/hash_drbg.go new file mode 100644 index 0000000..5329828 --- /dev/null +++ b/common/drbg/hash_drbg.go @@ -0,0 +1,149 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 drbg implements a minimalistic DRBG based off SipHash-2-4 in OFB +// mode. +package drbg + +import ( + "encoding/base64" + "encoding/binary" + "fmt" + "hash" + + "github.com/dchest/siphash" + + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" +) + +// Size is the length of the HashDrbg output. +const Size = siphash.Size + +// SeedLength is the length of the HashDrbg seed. +const SeedLength = 16 + Size + +// Seed is the initial state for a HashDrbg. It consists of a SipHash-2-4 +// key, and 8 bytes of initial data. +type Seed [SeedLength]byte + +// Bytes returns a pointer to the raw HashDrbg seed. +func (seed *Seed) Bytes() *[SeedLength]byte { + return (*[SeedLength]byte)(seed) +} + +// Base64 returns the Base64 representation of the seed. +func (seed *Seed) Base64() string { + return base64.StdEncoding.EncodeToString(seed.Bytes()[:]) +} + +// NewSeed returns a Seed initialized with the runtime CSPRNG. +func NewSeed() (seed *Seed, err error) { + seed = new(Seed) + if err = csrand.Bytes(seed.Bytes()[:]); err != nil { + return nil, err + } + + return +} + +// SeedFromBytes creates a Seed from the raw bytes, truncating to SeedLength as +// appropriate. +func SeedFromBytes(src []byte) (seed *Seed, err error) { + if len(src) < SeedLength { + return nil, InvalidSeedLengthError(len(src)) + } + + seed = new(Seed) + copy(seed.Bytes()[:], src) + + return +} + +// SeedFromBase64 creates a Seed from the Base64 representation, truncating to +// SeedLength as appropriate. +func SeedFromBase64(encoded string) (seed *Seed, err error) { + var raw []byte + if raw, err = base64.StdEncoding.DecodeString(encoded); err != nil { + return nil, err + } + + return SeedFromBytes(raw) +} + +// InvalidSeedLengthError is the error returned when the seed provided to the +// DRBG is an invalid length. +type InvalidSeedLengthError int + +func (e InvalidSeedLengthError) Error() string { + return fmt.Sprintf("invalid seed length: %d", int(e)) +} + +// HashDrbg is a CSDRBG based off of SipHash-2-4 in OFB mode. +type HashDrbg struct { + sip hash.Hash64 + ofb [Size]byte +} + +// NewHashDrbg makes a HashDrbg instance based off an optional seed. The seed +// is truncated to SeedLength. +func NewHashDrbg(seed *Seed) (*HashDrbg, error) { + drbg := new(HashDrbg) + if seed == nil { + var err error + if seed, err = NewSeed(); err != nil { + return nil, err + } + } + drbg.sip = siphash.New(seed.Bytes()[:16]) + copy(drbg.ofb[:], seed.Bytes()[16:]) + + return drbg, nil +} + +// Int63 returns a uniformly distributed random integer [0, 1 << 63). +func (drbg *HashDrbg) Int63() int64 { + block := drbg.NextBlock() + ret := binary.BigEndian.Uint64(block) + ret &= (1<<63 - 1) + + return int64(ret) +} + +// Seed does nothing, call NewHashDrbg if you want to reseed. +func (drbg *HashDrbg) Seed(seed int64) { + // No-op. +} + +// NextBlock returns the next 8 byte DRBG block. +func (drbg *HashDrbg) NextBlock() []byte { + drbg.sip.Write(drbg.ofb[:]) + copy(drbg.ofb[:], drbg.sip.Sum(nil)) + + ret := make([]byte, Size) + copy(ret, drbg.ofb[:]) + return ret +} diff --git a/common/ntor/ntor.go b/common/ntor/ntor.go new file mode 100644 index 0000000..37cfe88 --- /dev/null +++ b/common/ntor/ntor.go @@ -0,0 +1,432 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 ntor implements the Tor Project's ntor handshake as defined in +// proposal 216 "Improved circuit-creation key exchange". It also supports +// using Elligator to transform the Curve25519 public keys sent over the wire +// to a form that is indistinguishable from random strings. +// +// Before using this package, it is strongly recommended that the specification +// is read and understood. +package ntor + +import ( + "bytes" + "crypto/hmac" + "crypto/sha256" + "crypto/subtle" + "encoding/base64" + "fmt" + "io" + + "code.google.com/p/go.crypto/curve25519" + "code.google.com/p/go.crypto/hkdf" + + "github.com/agl/ed25519/extra25519" + + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" +) + +const ( + // PublicKeyLength is the length of a Curve25519 public key. + PublicKeyLength = 32 + + // RepresentativeLength is the length of an Elligator representative. + RepresentativeLength = 32 + + // PrivateKeyLength is the length of a Curve25519 private key. + PrivateKeyLength = 32 + + // SharedSecretLength is the length of a Curve25519 shared secret. + SharedSecretLength = 32 + + // NodeIDLength is the length of a ntor node identifier. + NodeIDLength = 20 + + // KeySeedLength is the length of the derived KEY_SEED. + KeySeedLength = sha256.Size + + // AuthLength is the lenght of the derived AUTH. + AuthLength = sha256.Size +) + +var protoID = []byte("ntor-curve25519-sha256-1") +var tMac = append(protoID, []byte(":mac")...) +var tKey = append(protoID, []byte(":key_extract")...) +var tVerify = append(protoID, []byte(":key_verify")...) +var mExpand = append(protoID, []byte(":key_expand")...) + +// PublicKeyLengthError is the error returned when the public key being +// imported is an invalid length. +type PublicKeyLengthError int + +func (e PublicKeyLengthError) Error() string { + return fmt.Sprintf("ntor: Invalid Curve25519 public key length: %d", + int(e)) +} + +// PrivateKeyLengthError is the error returned when the private key being +// imported is an invalid length. +type PrivateKeyLengthError int + +func (e PrivateKeyLengthError) Error() string { + return fmt.Sprintf("ntor: Invalid Curve25519 private key length: %d", + int(e)) +} + +// NodeIDLengthError is the error returned when the node ID being imported is +// an invalid length. +type NodeIDLengthError int + +func (e NodeIDLengthError) Error() string { + return fmt.Sprintf("ntor: Invalid NodeID length: %d", int(e)) +} + +// KeySeed is the key material that results from a handshake (KEY_SEED). +type KeySeed [KeySeedLength]byte + +// Bytes returns a pointer to the raw key material. +func (key_seed *KeySeed) Bytes() *[KeySeedLength]byte { + return (*[KeySeedLength]byte)(key_seed) +} + +// Auth is the verifier that results from a handshake (AUTH). +type Auth [AuthLength]byte + +// Bytes returns a pointer to the raw auth. +func (auth *Auth) Bytes() *[AuthLength]byte { + return (*[AuthLength]byte)(auth) +} + +// NodeID is a ntor node identifier. +type NodeID [NodeIDLength]byte + +// NewNodeID creates a NodeID from the raw bytes. +func NewNodeID(raw []byte) (*NodeID, error) { + if len(raw) != NodeIDLength { + return nil, NodeIDLengthError(len(raw)) + } + + nodeID := new(NodeID) + copy(nodeID[:], raw) + + return nodeID, nil +} + +// NodeIDFromBase64 creates a new NodeID from the Base64 encoded representation. +func NodeIDFromBase64(encoded string) (*NodeID, error) { + raw, err := base64.StdEncoding.DecodeString(encoded) + if err != nil { + return nil, err + } + + return NewNodeID(raw) +} +// Bytes returns a pointer to the raw NodeID. +func (id *NodeID) Bytes() *[NodeIDLength]byte { + return (*[NodeIDLength]byte)(id) +} + +// Base64 returns the Base64 representation of the NodeID. +func (id *NodeID) Base64() string { + return base64.StdEncoding.EncodeToString(id[:]) +} + +// PublicKey is a Curve25519 public key in little-endian byte order. +type PublicKey [PublicKeyLength]byte + +// Bytes returns a pointer to the raw Curve25519 public key. +func (public *PublicKey) Bytes() *[PublicKeyLength]byte { + return (*[PublicKeyLength]byte)(public) +} + +// Base64 returns the Base64 representation of the Curve25519 public key. +func (public *PublicKey) Base64() string { + return base64.StdEncoding.EncodeToString(public.Bytes()[:]) +} + +// NewPublicKey creates a PublicKey from the raw bytes. +func NewPublicKey(raw []byte) (*PublicKey, error) { + if len(raw) != PublicKeyLength { + return nil, PublicKeyLengthError(len(raw)) + } + + pubKey := new(PublicKey) + copy(pubKey[:], raw) + + return pubKey, nil +} + +// PublicKeyFromBase64 returns a PublicKey from a Base64 representation. +func PublicKeyFromBase64(encoded string) (*PublicKey, error) { + raw, err := base64.StdEncoding.DecodeString(encoded) + if err != nil { + return nil, err + } + + return NewPublicKey(raw) +} + +// Representative is an Elligator representative of a Curve25519 public key +// in little-endian byte order. +type Representative [RepresentativeLength]byte + +// Bytes returns a pointer to the raw Elligator representative. +func (repr *Representative) Bytes() *[RepresentativeLength]byte { + return (*[RepresentativeLength]byte)(repr) +} + +// ToPublic converts a Elligator representative to a Curve25519 public key. +func (repr *Representative) ToPublic() *PublicKey { + pub := new(PublicKey) + + extra25519.RepresentativeToPublicKey(pub.Bytes(), repr.Bytes()) + return pub +} + +// PrivateKey is a Curve25519 private key in little-endian byte order. +type PrivateKey [PrivateKeyLength]byte + +// Bytes returns a pointer to the raw Curve25519 private key. +func (private *PrivateKey) Bytes() *[PrivateKeyLength]byte { + return (*[PrivateKeyLength]byte)(private) +} + +// Base64 returns the Base64 representation of the Curve25519 private key. +func (private *PrivateKey) Base64() string { + return base64.StdEncoding.EncodeToString(private.Bytes()[:]) +} + +// Keypair is a Curve25519 keypair with an optional Elligator representative. +// As only certain Curve25519 keys can be obfuscated with Elligator, the +// representative must be generated along with the keypair. +type Keypair struct { + public *PublicKey + private *PrivateKey + representative *Representative +} + +// Public returns the Curve25519 public key belonging to the Keypair. +func (keypair *Keypair) Public() *PublicKey { + return keypair.public +} + +// Private returns the Curve25519 private key belonging to the Keypair. +func (keypair *Keypair) Private() *PrivateKey { + return keypair.private +} + +// Representative returns the Elligator representative of the public key +// belonging to the Keypair. +func (keypair *Keypair) Representative() *Representative { + return keypair.representative +} + +// HasElligator returns true if the Keypair has an Elligator representative. +func (keypair *Keypair) HasElligator() bool { + return nil != keypair.representative +} + +// NewKeypair generates a new Curve25519 keypair, and optionally also generates +// an Elligator representative of the public key. +func NewKeypair(elligator bool) (*Keypair, error) { + keypair := new(Keypair) + keypair.private = new(PrivateKey) + keypair.public = new(PublicKey) + if elligator { + keypair.representative = new(Representative) + } + + for { + // Generate a Curve25519 private key. Like everyone who does this, + // run the CSPRNG output through SHA256 for extra tinfoil hattery. + priv := keypair.private.Bytes()[:] + if err := csrand.Bytes(priv); err != nil { + return nil, err + } + digest := sha256.Sum256(priv) + digest[0] &= 248 + digest[31] &= 127 + digest[31] |= 64 + copy(priv, digest[:]) + + if elligator { + // Apply the Elligator transform. This fails ~50% of the time. + if !extra25519.ScalarBaseMult(keypair.public.Bytes(), + keypair.representative.Bytes(), + keypair.private.Bytes()) { + continue + } + } else { + // Generate the corresponding Curve25519 public key. + curve25519.ScalarBaseMult(keypair.public.Bytes(), + keypair.private.Bytes()) + } + + return keypair, nil + } +} + +// KeypairFromBase64 returns a Keypair from a Base64 representation of the +// private key. +func KeypairFromBase64(encoded string) (*Keypair, error) { + raw, err := base64.StdEncoding.DecodeString(encoded) + if err != nil { + return nil, err + } + + if len(raw) != PrivateKeyLength { + return nil, PrivateKeyLengthError(len(raw)) + } + + keypair := new(Keypair) + keypair.private = new(PrivateKey) + keypair.public = new(PublicKey) + + copy(keypair.private[:], raw) + curve25519.ScalarBaseMult(keypair.public.Bytes(), + keypair.private.Bytes()) + + return keypair, nil +} + +// ServerHandshake does the server side of a ntor handshake and returns status, +// KEY_SEED, and AUTH. If status is not true, the handshake MUST be aborted. +func ServerHandshake(clientPublic *PublicKey, serverKeypair *Keypair, idKeypair *Keypair, id *NodeID) (ok bool, keySeed *KeySeed, auth *Auth) { + var notOk int + var secretInput bytes.Buffer + + // Server side uses EXP(X,y) | EXP(X,b) + var exp [SharedSecretLength]byte + curve25519.ScalarMult(&exp, serverKeypair.private.Bytes(), + clientPublic.Bytes()) + notOk |= constantTimeIsZero(exp[:]) + secretInput.Write(exp[:]) + + curve25519.ScalarMult(&exp, idKeypair.private.Bytes(), + clientPublic.Bytes()) + notOk |= constantTimeIsZero(exp[:]) + secretInput.Write(exp[:]) + + keySeed, auth = ntorCommon(secretInput, id, idKeypair.public, + clientPublic, serverKeypair.public) + return notOk == 0, keySeed, auth +} + +// ClientHandshake does the client side of a ntor handshake and returnes +// status, KEY_SEED, and AUTH. If status is not true or AUTH does not match +// the value recieved from the server, the handshake MUST be aborted. +func ClientHandshake(clientKeypair *Keypair, serverPublic *PublicKey, idPublic *PublicKey, id *NodeID) (ok bool, keySeed *KeySeed, auth *Auth) { + var notOk int + var secretInput bytes.Buffer + + // Client side uses EXP(Y,x) | EXP(B,x) + var exp [SharedSecretLength]byte + curve25519.ScalarMult(&exp, clientKeypair.private.Bytes(), + serverPublic.Bytes()) + notOk |= constantTimeIsZero(exp[:]) + secretInput.Write(exp[:]) + + curve25519.ScalarMult(&exp, clientKeypair.private.Bytes(), + idPublic.Bytes()) + notOk |= constantTimeIsZero(exp[:]) + secretInput.Write(exp[:]) + + keySeed, auth = ntorCommon(secretInput, id, idPublic, + clientKeypair.public, serverPublic) + return notOk == 0, keySeed, auth +} + +// CompareAuth does a constant time compare of a Auth and a byte slice +// (presumably received over a network). +func CompareAuth(auth1 *Auth, auth2 []byte) bool { + auth1Bytes := auth1.Bytes() + return hmac.Equal(auth1Bytes[:], auth2) +} + +func ntorCommon(secretInput bytes.Buffer, id *NodeID, b *PublicKey, x *PublicKey, y *PublicKey) (*KeySeed, *Auth) { + keySeed := new(KeySeed) + auth := new(Auth) + + // secret_input/auth_input use this common bit, build it once. + suffix := bytes.NewBuffer(b.Bytes()[:]) + suffix.Write(b.Bytes()[:]) + suffix.Write(x.Bytes()[:]) + suffix.Write(y.Bytes()[:]) + suffix.Write(protoID) + suffix.Write(id[:]) + + // At this point secret_input has the 2 exponents, concatenated, append the + // client/server common suffix. + secretInput.Write(suffix.Bytes()) + + // KEY_SEED = H(secret_input, t_key) + h := hmac.New(sha256.New, tKey) + h.Write(secretInput.Bytes()) + tmp := h.Sum(nil) + copy(keySeed[:], tmp) + + // verify = H(secret_input, t_verify) + h = hmac.New(sha256.New, tVerify) + h.Write(secretInput.Bytes()) + verify := h.Sum(nil) + + // auth_input = verify | ID | B | Y | X | PROTOID | "Server" + authInput := bytes.NewBuffer(verify) + authInput.Write(suffix.Bytes()) + authInput.Write([]byte("Server")) + h = hmac.New(sha256.New, tMac) + h.Write(authInput.Bytes()) + tmp = h.Sum(nil) + copy(auth[:], tmp) + + return keySeed, auth +} + +func constantTimeIsZero(x []byte) int { + var ret byte + for _, v := range x { + ret |= v + } + + return subtle.ConstantTimeByteEq(ret, 0) +} + +// Kdf extracts and expands KEY_SEED via HKDF-SHA256 and returns `okm_len` bytes +// of key material. +func Kdf(keySeed []byte, okmLen int) []byte { + kdf := hkdf.New(sha256.New, keySeed, tKey, mExpand) + okm := make([]byte, okmLen) + n, err := io.ReadFull(kdf, okm) + if err != nil { + panic(fmt.Sprintf("BUG: Failed HKDF: %s", err.Error())) + } else if n != len(okm) { + panic(fmt.Sprintf("BUG: Got truncated HKDF output: %d", n)) + } + + return okm +} diff --git a/common/ntor/ntor_test.go b/common/ntor/ntor_test.go new file mode 100644 index 0000000..c92c04e --- /dev/null +++ b/common/ntor/ntor_test.go @@ -0,0 +1,180 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 ntor + +import ( + "bytes" + "testing" +) + +// TestNewKeypair tests Curve25519/Elligator keypair generation. +func TestNewKeypair(t *testing.T) { + // Test standard Curve25519 first. + keypair, err := NewKeypair(false) + if err != nil { + t.Fatal("NewKeypair(false) failed:", err) + } + if keypair == nil { + t.Fatal("NewKeypair(false) returned nil") + } + if keypair.HasElligator() { + t.Fatal("NewKeypair(false) has a Elligator representative") + } + + // Test Elligator generation. + keypair, err = NewKeypair(true) + if err != nil { + t.Fatal("NewKeypair(true) failed:", err) + } + if keypair == nil { + t.Fatal("NewKeypair(true) returned nil") + } + if !keypair.HasElligator() { + t.Fatal("NewKeypair(true) mising an Elligator representative") + } +} + +// Test Client/Server handshake. +func TestHandshake(t *testing.T) { + clientKeypair, err := NewKeypair(true) + if err != nil { + t.Fatal("Failed to generate client keypair:", err) + } + if clientKeypair == nil { + t.Fatal("Client keypair is nil") + } + + serverKeypair, err := NewKeypair(true) + if err != nil { + t.Fatal("Failed to generate server keypair:", err) + } + if serverKeypair == nil { + t.Fatal("Server keypair is nil") + } + + idKeypair, err := NewKeypair(false) + if err != nil { + t.Fatal("Failed to generate identity keypair:", err) + } + if idKeypair == nil { + t.Fatal("Identity keypair is nil") + } + + nodeID, err := NewNodeID([]byte("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13")) + if err != nil { + t.Fatal("Failed to load NodeId:", err) + } + + // ServerHandshake + clientPublic := clientKeypair.Representative().ToPublic() + ok, serverSeed, serverAuth := ServerHandshake(clientPublic, + serverKeypair, idKeypair, nodeID) + if !ok { + t.Fatal("ServerHandshake failed") + } + if serverSeed == nil { + t.Fatal("ServerHandshake returned nil KEY_SEED") + } + if serverAuth == nil { + t.Fatal("ServerHandshake returned nil AUTH") + } + + // ClientHandshake + ok, clientSeed, clientAuth := ClientHandshake(clientKeypair, + serverKeypair.Public(), idKeypair.Public(), nodeID) + if !ok { + t.Fatal("ClientHandshake failed") + } + if clientSeed == nil { + t.Fatal("ClientHandshake returned nil KEY_SEED") + } + if clientAuth == nil { + t.Fatal("ClientHandshake returned nil AUTH") + } + + // WARNING: Use a constant time comparison in actual code. + if 0 != bytes.Compare(clientSeed.Bytes()[:], serverSeed.Bytes()[:]) { + t.Fatal("KEY_SEED mismatched between client/server") + } + if 0 != bytes.Compare(clientAuth.Bytes()[:], serverAuth.Bytes()[:]) { + t.Fatal("AUTH mismatched between client/server") + } +} + +// Benchmark Client/Server handshake. The actual time taken that will be +// observed on either the Client or Server is half the reported time per +// operation since the benchmark does both sides. +func BenchmarkHandshake(b *testing.B) { + // Generate the "long lasting" identity key and NodeId. + idKeypair, err := NewKeypair(false) + if err != nil || idKeypair == nil { + b.Fatal("Failed to generate identity keypair") + } + nodeID, err := NewNodeID([]byte("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13")) + if err != nil { + b.Fatal("Failed to load NodeId:", err) + } + b.ResetTimer() + + // Start the actual benchmark. + for i := 0; i < b.N; i++ { + // Generate the keypairs. + serverKeypair, err := NewKeypair(true) + if err != nil || serverKeypair == nil { + b.Fatal("Failed to generate server keypair") + } + + clientKeypair, err := NewKeypair(true) + if err != nil || clientKeypair == nil { + b.Fatal("Failed to generate client keypair") + } + + // Server handshake. + clientPublic := clientKeypair.Representative().ToPublic() + ok, serverSeed, serverAuth := ServerHandshake(clientPublic, + serverKeypair, idKeypair, nodeID) + if !ok || serverSeed == nil || serverAuth == nil { + b.Fatal("ServerHandshake failed") + } + + // Client handshake. + serverPublic := serverKeypair.Representative().ToPublic() + ok, clientSeed, clientAuth := ClientHandshake(clientKeypair, + serverPublic, idKeypair.Public(), nodeID) + if !ok || clientSeed == nil || clientAuth == nil { + b.Fatal("ClientHandshake failed") + } + + // Validate the authenticator. Real code would pass the AUTH read off + // the network as a slice to CompareAuth here. + if !CompareAuth(clientAuth, serverAuth.Bytes()[:]) || + !CompareAuth(serverAuth, clientAuth.Bytes()[:]) { + b.Fatal("AUTH mismatched between client/server") + } + } +} diff --git a/common/probdist/weighted_dist.go b/common/probdist/weighted_dist.go new file mode 100644 index 0000000..2386bbe --- /dev/null +++ b/common/probdist/weighted_dist.go @@ -0,0 +1,220 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 probdist implements a weighted probability distribution suitable for +// protocol parameterization. To allow for easy reproduction of a given +// distribution, the drbg package is used as the random number source. +package probdist + +import ( + "container/list" + "fmt" + "math/rand" + + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" + "git.torproject.org/pluggable-transports/obfs4.git/common/drbg" +) + +const ( + minValues = 1 + maxValues = 100 +) + +// WeightedDist is a weighted distribution. +type WeightedDist struct { + minValue int + maxValue int + biased bool + values []int + weights []float64 + + alias []int + prob []float64 +} + +// New creates a weighted distribution of values ranging from min to max +// based on a HashDrbg initialized with seed. Optionally, bias the weight +// generation to match the ScrambleSuit non-uniform distribution from +// obfsproxy. +func New(seed *drbg.Seed, min, max int, biased bool) (w *WeightedDist) { + w = &WeightedDist{minValue: min, maxValue: max, biased: biased} + + if max <= min { + panic(fmt.Sprintf("wDist.Reset(): min >= max (%d, %d)", min, max)) + } + + w.Reset(seed) + + return +} + +// genValues creates a slice containing a random number of random values +// that when scaled by adding minValue will fall into [min, max]. +func (w *WeightedDist) genValues(rng *rand.Rand) { + nValues := (w.maxValue + 1) - w.minValue + values := rng.Perm(nValues) + if nValues < minValues { + nValues = minValues + } + if nValues > maxValues { + nValues = maxValues + } + nValues = rng.Intn(nValues) + 1 + w.values = values[:nValues] +} + +// genBiasedWeights generates a non-uniform weight list, similar to the +// ScrambleSuit prob_dist module. +func (w *WeightedDist) genBiasedWeights(rng *rand.Rand) { + w.weights = make([]float64, len(w.values)) + + culmProb := 0.0 + for i := range w.weights { + p := (1.0 - culmProb) * rng.Float64() + w.weights[i] = p + culmProb += p + } +} + +// genUniformWeights generates a uniform weight list. +func (w *WeightedDist) genUniformWeights(rng *rand.Rand) { + w.weights = make([]float64, len(w.values)) + for i := range w.weights { + w.weights[i] = rng.Float64() + } +} + +// genTables calculates the alias and prob tables used for Vose's Alias method. +// Algorithm taken from http://www.keithschwarz.com/darts-dice-coins/ +func (w *WeightedDist) genTables() { + n := len(w.weights) + var sum float64 + for _, weight := range w.weights { + sum += weight + } + + // Create arrays $Alias$ and $Prob$, each of size $n$. + alias := make([]int, n) + prob := make([]float64, n) + + // Create two worklists, $Small$ and $Large$. + small := list.New() + large := list.New() + + scaled := make([]float64, n) + for i, weight := range w.weights { + // Multiply each probability by $n$. + p_i := weight * float64(n) / sum + scaled[i] = p_i + + // For each scaled probability $p_i$: + if scaled[i] < 1.0 { + // If $p_i < 1$, add $i$ to $Small$. + small.PushBack(i) + } else { + // Otherwise ($p_i \ge 1$), add $i$ to $Large$. + large.PushBack(i) + } + } + + // While $Small$ and $Large$ are not empty: ($Large$ might be emptied first) + for small.Len() > 0 && large.Len() > 0 { + // Remove the first element from $Small$; call it $l$. + l := small.Remove(small.Front()).(int) + // Remove the first element from $Large$; call it $g$. + g := large.Remove(large.Front()).(int) + + // Set $Prob[l] = p_l$. + prob[l] = scaled[l] + // Set $Alias[l] = g$. + alias[l] = g + + // Set $p_g := (p_g + p_l) - 1$. (This is a more numerically stable option.) + scaled[g] = (scaled[g] + scaled[l]) - 1.0 + + if scaled[g] < 1.0 { + // If $p_g < 1$, add $g$ to $Small$. + small.PushBack(g) + } else { + // Otherwise ($p_g \ge 1$), add $g$ to $Large$. + large.PushBack(g) + } + } + + // While $Large$ is not empty: + for large.Len() > 0 { + // Remove the first element from $Large$; call it $g$. + g := large.Remove(large.Front()).(int) + // Set $Prob[g] = 1$. + prob[g] = 1.0 + } + + // While $Small$ is not empty: This is only possible due to numerical instability. + for small.Len() > 0 { + // Remove the first element from $Small$; call it $l$. + l := small.Remove(small.Front()).(int) + // Set $Prob[l] = 1$. + prob[l] = 1.0 + } + + w.prob = prob + w.alias = alias +} + +// Reset generates a new distribution with the same min/max based on a new +// seed. +func (w *WeightedDist) Reset(seed *drbg.Seed) { + // Initialize the deterministic random number generator. + drbg, _ := drbg.NewHashDrbg(seed) + rng := rand.New(drbg) + + w.genValues(rng) + if w.biased { + w.genBiasedWeights(rng) + } else { + w.genUniformWeights(rng) + } + w.genTables() +} + +// Sample generates a random value according to the distribution. +func (w *WeightedDist) Sample() int { + var idx int + + // Generate a fair die roll from an $n$-sided die; call the side $i$. + i := csrand.Intn(len(w.values)) + // Flip a biased coin that comes up heads with probability $Prob[i]$. + if csrand.Float64() <= w.prob[i] { + // If the coin comes up "heads," return $i$. + idx = i + } else { + // Otherwise, return $Alias[i]$. + idx = w.alias[i] + } + + return w.minValue + w.values[idx] +} diff --git a/common/probdist/weighted_dist_test.go b/common/probdist/weighted_dist_test.go new file mode 100644 index 0000000..b705add --- /dev/null +++ b/common/probdist/weighted_dist_test.go @@ -0,0 +1,80 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 probdist + +import ( + "fmt" + "testing" + + "git.torproject.org/pluggable-transports/obfs4.git/common/drbg" +) + +const debug = false + +func TestWeightedDist(t *testing.T) { + seed, err := drbg.NewSeed() + if err != nil { + t.Fatal("failed to generate a DRBG seed:", err) + } + + const nrTrials = 1000000 + + hist := make([]int, 1000) + + w := New(seed, 0, 999, true) + if debug { + // Dump a string representation of the probability table. + fmt.Println("Table:") + var sum float64 + for _, weight := range w.weights { + sum += weight + } + for i, weight := range w.weights { + p := weight / sum + if p > 0.000001 { // Filter out tiny values. + fmt.Printf(" [%d]: %f\n", w.minValue+w.values[i], p) + } + } + fmt.Println() + } + + for i := 0; i < nrTrials; i++ { + value := w.Sample() + hist[value]++ + } + + if debug { + fmt.Println("Generated:") + for value, count := range hist { + if count != 0 { + p := float64(count) / float64(nrTrials) + fmt.Printf(" [%d]: %f (%d)\n", value, p, count) + } + } + } +} diff --git a/common/replayfilter/replay_filter.go b/common/replayfilter/replay_filter.go new file mode 100644 index 0000000..95cc5d6 --- /dev/null +++ b/common/replayfilter/replay_filter.go @@ -0,0 +1,147 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 replayfilter implements a generic replay detection filter with a +// caller specifiable time-to-live. It only detects if a given byte sequence +// has been seen before based on the SipHash-2-4 digest of the sequence. +// Collisions are treated as positive matches, though the probability of this +// happening is negligible. +package replayfilter + +import ( + "container/list" + "encoding/binary" + "sync" + "time" + + "github.com/dchest/siphash" + + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" +) + +// maxFilterSize is the maximum capacity of a replay filter. This value is +// more as a safeguard to prevent runaway filter growth, and is sized to be +// serveral orders of magnitude greater than the number of connections a busy +// bridge sees in one day, so in practice should never be reached. +const maxFilterSize = 100 * 1024 + +type entry struct { + digest uint64 + firstSeen time.Time + element *list.Element +} + +// ReplayFilter is a simple filter designed only to detect if a given byte +// sequence has been seen before. +type ReplayFilter struct { + sync.Mutex + + filter map[uint64]*entry + fifo *list.List + + key [2]uint64 + ttl time.Duration +} + +// New creates a new ReplayFilter instance. +func New(ttl time.Duration) (filter *ReplayFilter, err error) { + // Initialize the SipHash-2-4 instance with a random key. + var key [16]byte + if err = csrand.Bytes(key[:]); err != nil { + return + } + + filter = new(ReplayFilter) + filter.filter = make(map[uint64]*entry) + filter.fifo = list.New() + filter.key[0] = binary.BigEndian.Uint64(key[0:8]) + filter.key[1] = binary.BigEndian.Uint64(key[8:16]) + filter.ttl = ttl + + return +} + +// TestAndSet queries the filter for a given byte sequence, inserts the +// sequence, and returns if it was present before the insertion operation. +func (f *ReplayFilter) TestAndSet(now time.Time, buf []byte) bool { + digest := siphash.Hash(f.key[0], f.key[1], buf) + + f.Lock() + defer f.Unlock() + + f.compactFilter(now) + + if e := f.filter[digest]; e != nil { + // Hit. Just return. + return true + } + + // Miss. Add a new entry. + e := new(entry) + e.digest = digest + e.firstSeen = now + e.element = f.fifo.PushBack(e) + f.filter[digest] = e + + return false +} + +func (f *ReplayFilter) compactFilter(now time.Time) { + e := f.fifo.Front() + for e != nil { + ent, _ := e.Value.(*entry) + + // If the filter is not full, only purge entries that exceed the TTL, + // otherwise purge at least one entry, then revert to TTL based + // compaction. + if f.fifo.Len() < maxFilterSize && f.ttl > 0 { + deltaT := now.Sub(ent.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.reset() + return + } else if deltaT < f.ttl { + return + } + } + + // Remove the eldest entry. + eNext := e.Next() + delete(f.filter, ent.digest) + f.fifo.Remove(ent.element) + ent.element = nil + e = eNext + } +} + +func (f *ReplayFilter) reset() { + f.filter = make(map[uint64]*entry) + f.fifo = list.New() +} diff --git a/common/replayfilter/replay_filter_test.go b/common/replayfilter/replay_filter_test.go new file mode 100644 index 0000000..884e4fb --- /dev/null +++ b/common/replayfilter/replay_filter_test.go @@ -0,0 +1,95 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 replayfilter + +import ( + "testing" + "time" +) + +func TestReplayFilter(t *testing.T) { + ttl := 10 * time.Second + + f, err := New(ttl) + if err != nil { + t.Fatal("newReplayFilter failed:", err) + } + + buf := []byte("This is a test of the Emergency Broadcast System.") + now := time.Now() + + // testAndSet into empty filter, returns false (not present). + set := f.TestAndSet(now, buf) + if set { + t.Fatal("TestAndSet empty filter returned true") + } + + // testAndSet into filter containing entry, should return true(present). + set = f.TestAndSet(now, buf) + if !set { + t.Fatal("testAndSet populated filter (replayed) returned false") + } + + buf2 := []byte("This concludes this test of the Emergency Broadcast System.") + now = now.Add(ttl) + + // testAndSet with time advanced. + set = f.TestAndSet(now, buf2) + if set { + t.Fatal("testAndSet populated filter, 2nd entry returned true") + } + set = f.TestAndSet(now, buf2) + if !set { + t.Fatal("testAndSet populated filter, 2nd entry (replayed) returned false") + } + + // Ensure that the first entry has been removed by compact. + set = f.TestAndSet(now, buf) + if set { + t.Fatal("testAndSet populated filter, compact check returned true") + } + + // Ensure that the filter gets reaped if the clock jumps backwards. + now = time.Time{} + set = f.TestAndSet(now, buf) + if set { + t.Fatal("testAndSet populated filter, backward time jump returned true") + } + if len(f.filter) != 1 { + t.Fatal("filter map has a unexpected number of entries:", len(f.filter)) + } + if f.fifo.Len() != 1 { + t.Fatal("filter fifo has a unexpected number of entries:", f.fifo.Len()) + } + + // Ensure that the entry is properly added after reaping. + set = f.TestAndSet(now, buf) + if !set { + t.Fatal("testAndSet populated filter, post-backward clock jump (replayed) returned false") + } +} diff --git a/common/uniformdh/uniformdh.go b/common/uniformdh/uniformdh.go new file mode 100644 index 0000000..ab94a2e --- /dev/null +++ b/common/uniformdh/uniformdh.go @@ -0,0 +1,183 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 uniformdh implements the Tor Project's UniformDH key exchange +// mechanism as defined in the obfs3 protocol specification. This +// implementation is suitable for obfuscation but MUST NOT BE USED when strong +// security is required as it is not constant time. +package uniformdh + +import ( + "fmt" + "io" + "math/big" +) + +const ( + // Size is the size of a UniformDH key or shared secret in bytes. + Size = 1536 / 8 + + // modpStr is the RFC3526 1536-bit MODP Group (Group 5). + modpStr = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1" + + "29024E088A67CC74020BBEA63B139B22514A08798E3404DD" + + "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245" + + "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED" + + "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D" + + "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F" + + "83655D23DCA3AD961C62F356208552BB9ED529077096966D" + + "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF" + + g = 2 +) + +var modpGroup *big.Int +var gen *big.Int + +// A PrivateKey represents a UniformDH private key. +type PrivateKey struct { + PublicKey + privateKey *big.Int +} + +// A PublicKey represents a UniformDH public key. +type PublicKey struct { + bytes []byte + publicKey *big.Int +} + +// Bytes returns the byte representation of a PublicKey. +func (pub *PublicKey) Bytes() (pubBytes []byte, err error) { + if len(pub.bytes) != Size || pub.bytes == nil { + return nil, fmt.Errorf("public key is not initialized") + } + pubBytes = make([]byte, Size) + copy(pubBytes, pub.bytes) + + return +} + +// SetBytes sets the PublicKey from a byte slice. +func (pub *PublicKey) SetBytes(pubBytes []byte) error { + if len(pubBytes) != Size { + return fmt.Errorf("public key length %d is not %d", len(pubBytes), Size) + } + pub.bytes = make([]byte, Size) + copy(pub.bytes, pubBytes) + pub.publicKey = new(big.Int).SetBytes(pub.bytes) + + return nil +} + +// GenerateKey generates a UniformDH keypair using the random source random. +func GenerateKey(random io.Reader) (priv *PrivateKey, err error) { + privBytes := make([]byte, Size) + if _, err = io.ReadFull(random, privBytes); err != nil { + return + } + priv, err = generateKey(privBytes) + + return +} + +func generateKey(privBytes []byte) (priv *PrivateKey, err error) { + // This function does all of the actual heavy lifting of creating a public + // key from a raw 192 byte private key. It is split so that the KAT tests + // can be written easily, and not exposed since non-ephemeral keys are a + // terrible idea. + + if len(privBytes) != Size { + return nil, fmt.Errorf("invalid private key size %d", len(privBytes)) + } + + // To pick a private UniformDH key, we pick a random 1536-bit number, + // and make it even by setting its low bit to 0 + privBn := new(big.Int).SetBytes(privBytes) + wasEven := privBn.Bit(0) == 0 + privBn = privBn.SetBit(privBn, 0, 0) + + // Let x be that private key, and X = g^x (mod p). + pubBn := new(big.Int).Exp(gen, privBn, modpGroup) + pubAlt := new(big.Int).Sub(modpGroup, pubBn) + + // When someone sends her public key to the other party, she randomly + // decides whether to send X or p-X. Use the lowest most bit of the + // private key here as the random coin flip since it is masked out and not + // used. + // + // Note: The spec doesn't explicitly specify it, but here we prepend zeros + // to the key so that it is always exactly Size bytes. + pubBytes := make([]byte, Size) + if wasEven { + err = prependZeroBytes(pubBytes, pubBn.Bytes()) + } else { + err = prependZeroBytes(pubBytes, pubAlt.Bytes()) + } + if err != nil { + return + } + + priv = new(PrivateKey) + priv.PublicKey.bytes = pubBytes + priv.PublicKey.publicKey = pubBn + priv.privateKey = privBn + + return +} + +// Handshake generates a shared secret given a PrivateKey and PublicKey. +func Handshake(privateKey *PrivateKey, publicKey *PublicKey) (sharedSecret []byte, err error) { + // When a party wants to calculate the shared secret, she raises the + // foreign public key to her private key. + secretBn := new(big.Int).Exp(publicKey.publicKey, privateKey.privateKey, modpGroup) + sharedSecret = make([]byte, Size) + err = prependZeroBytes(sharedSecret, secretBn.Bytes()) + + return +} + +func prependZeroBytes(dst, src []byte) error { + zeros := len(dst) - len(src) + if zeros < 0 { + return fmt.Errorf("src length is greater than destination: %d", zeros) + } + for i := 0; i < zeros; i++ { + dst[i] = 0 + } + copy(dst[zeros:], src) + + return nil +} + +func init() { + // Load the MODP group and the generator. + var ok bool + modpGroup, ok = new(big.Int).SetString(modpStr, 16) + if !ok { + panic("Failed to load the RFC3526 MODP Group") + } + gen = big.NewInt(g) +} diff --git a/common/uniformdh/uniformdh_test.go b/common/uniformdh/uniformdh_test.go new file mode 100644 index 0000000..d705d66 --- /dev/null +++ b/common/uniformdh/uniformdh_test.go @@ -0,0 +1,220 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 uniformdh + +import ( + "bytes" + "crypto/rand" + "encoding/hex" + "testing" +) + +const ( + xPrivStr = "6f592d676f536874746f20686e6b776f" + + "20736874206561676574202e6f592d67" + + "6f536874746f20687369742065686720" + + "74612e655920676f532d746f6f686874" + + "6920207368742065656b20796e612064" + + "7567726169646e616f20206668742065" + + "61676574202e61507473202c72707365" + + "6e652c746620747572752c6561206c6c" + + "612065726f20656e6920206e6f592d67" + + "6f536874746f2e68482020656e6b776f" + + "2073687772652065687420656c4f2064" + + "6e4f736562206f72656b74207268756f" + + xPubStr = "76a3d17d5c55b03e865fa3e8267990a7" + + "24baa24b0bdd0cc4af93be8de30be120" + + "d5533c91bf63ef923b02edcb84b74438" + + "3f7de232cca6eb46d07cad83dcaa317f" + + "becbc68ca13e2c4019e6a36531067450" + + "04aecc0be1dff0a78733fb0e7d5cb7c4" + + "97cab77b1331bf347e5f3a7847aa0bc0" + + "f4bc64146b48407fed7b931d16972d25" + + "fb4da5e6dc074ce2a58daa8de7624247" + + "cdf2ebe4e4dfec6d5989aac778c87559" + + "d3213d6040d4111ce3a2acae19f9ee15" + + "32509e037f69b252fdc30243cbbce9d0" + + yPrivStr = "736562206f72656b74207268756f6867" + + "6f2020666c6f2c646120646e77206568" + + "657254206568207968736c61206c7262" + + "6165206b68746f726775206867616961" + + "2e6e482020656e6b776f207368777265" + + "2065685479656820766120657274646f" + + "652072616874732766206569646c2c73" + + "6120646e772065686572542065682079" + + "74736c69206c72746165206468746d65" + + "202c6e612064687720796f6e6f20656e" + + "63206e61622068656c6f206468546d65" + + "61202073685479657420657264610a2e" + + yPubStr = "d04e156e554c37ffd7aba749df662350" + + "1e4ff4466cb12be055617c1a36872237" + + "36d2c3fdce9ee0f9b27774350849112a" + + "a5aeb1f126811c9c2f3a9cb13d2f0c3a" + + "7e6fa2d3bf71baf50d839171534f227e" + + "fbb2ce4227a38c25abdc5ba7fc430111" + + "3a2cb2069c9b305faac4b72bf21fec71" + + "578a9c369bcac84e1a7dcf0754e342f5" + + "bc8fe4917441b88254435e2abaf297e9" + + "3e1e57968672d45bd7d4c8ba1bc3d314" + + "889b5bc3d3e4ea33d4f2dfdd34e5e5a7" + + "2ff24ee46316d4757dad09366a0b66b3" + + ssStr = "78afaf5f457f1fdb832bebc397644a33" + + "038be9dba10ca2ce4a076f327f3a0ce3" + + "151d477b869ee7ac467755292ad8a77d" + + "b9bd87ffbbc39955bcfb03b1583888c8" + + "fd037834ff3f401d463c10f899aa6378" + + "445140b7f8386a7d509e7b9db19b677f" + + "062a7a1a4e1509604d7a0839ccd5da61" + + "73e10afd9eab6dda74539d60493ca37f" + + "a5c98cd9640b409cd8bb3be2bc5136fd" + + "42e764fc3f3c0ddb8db3d87abcf2e659" + + "8d2b101bef7a56f50ebc658f9df1287d" + + "a81359543e77e4a4cfa7598a4152e4c0" +) + +var xPriv, xPub, yPriv, yPub, ss []byte + +// TestGenerateKeyOdd tests creating a UniformDH keypair with a odd private +// key. +func TestGenerateKeyOdd(t *testing.T) { + xX, err := generateKey(xPriv) + if err != nil { + t.Fatal("generateKey(xPriv) failed:", err) + } + + xPubGen, err := xX.PublicKey.Bytes() + if err != nil { + t.Fatal("xX.PublicKey.Bytes() failed:", err) + } + if 0 != bytes.Compare(xPubGen, xPub) { + t.Fatal("Generated public key does not match known answer") + } +} + +// TestGenerateKeyEven tests creating a UniformDH keypair with a even private +// key. +func TestGenerateKeyEven(t *testing.T) { + yY, err := generateKey(yPriv) + if err != nil { + t.Fatal("generateKey(yPriv) failed:", err) + } + + yPubGen, err := yY.PublicKey.Bytes() + if err != nil { + t.Fatal("yY.PublicKey.Bytes() failed:", err) + } + if 0 != bytes.Compare(yPubGen, yPub) { + t.Fatal("Generated public key does not match known answer") + } +} + +// TestHandshake tests conductiong a UniformDH handshake with know values. +func TestHandshake(t *testing.T) { + xX, err := generateKey(xPriv) + if err != nil { + t.Fatal("generateKey(xPriv) failed:", err) + } + yY, err := generateKey(yPriv) + if err != nil { + t.Fatal("generateKey(yPriv) failed:", err) + } + + xY, err := Handshake(xX, &yY.PublicKey) + if err != nil { + t.Fatal("Handshake(xX, yY.PublicKey) failed:", err) + } + yX, err := Handshake(yY, &xX.PublicKey) + if err != nil { + t.Fatal("Handshake(yY, xX.PublicKey) failed:", err) + } + + if 0 != bytes.Compare(xY, yX) { + t.Fatal("Generated shared secrets do not match between peers") + } + if 0 != bytes.Compare(xY, ss) { + t.Fatal("Generated shared secret does not match known value") + } +} + +// Benchmark UniformDH key generation + exchange. THe actual time taken per +// peer is half of the reported time as this does 2 key generation an +// handshake operations. +func BenchmarkHandshake(b *testing.B) { + for i := 0; i < b.N; i++ { + xX, err := GenerateKey(rand.Reader) + if err != nil { + b.Fatal("Failed to generate xX keypair", err) + } + + yY, err := GenerateKey(rand.Reader) + if err != nil { + b.Fatal("Failed to generate yY keypair", err) + } + + xY, err := Handshake(xX, &yY.PublicKey) + if err != nil { + b.Fatal("Handshake(xX, yY.PublicKey) failed:", err) + } + yX, err := Handshake(yY, &xX.PublicKey) + if err != nil { + b.Fatal("Handshake(yY, xX.PublicKey) failed:", err) + } + + _ = xY + _ = yX + } +} + +func init() { + // Load the test vectors into byte slices. + var err error + xPriv, err = hex.DecodeString(xPrivStr) + if err != nil { + panic("hex.DecodeString(xPrivStr) failed") + } + xPub, err = hex.DecodeString(xPubStr) + if err != nil { + panic("hex.DecodeString(xPubStr) failed") + } + yPriv, err = hex.DecodeString(yPrivStr) + if err != nil { + panic("hex.DecodeString(yPrivStr) failed") + } + yPub, err = hex.DecodeString(yPubStr) + if err != nil { + panic("hex.DecodeString(yPubStr) failed") + } + ss, err = hex.DecodeString(ssStr) + if err != nil { + panic("hex.DecodeString(ssStr) failed") + } +} diff --git a/csrand/csrand.go b/csrand/csrand.go deleted file mode 100644 index b059ed0..0000000 --- a/csrand/csrand.go +++ /dev/null @@ -1,102 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 csrand implements the math/rand interface over crypto/rand, along -// with some utility functions for common random number/byte related tasks. -// -// Not all of the convinience routines are replicated, only those that are -// useful for obfs4. The CsRand variable provides access to the full math/rand -// API. -package csrand - -import ( - cryptRand "crypto/rand" - "encoding/binary" - "fmt" - "io" - "math/rand" -) - -var ( - csRandSourceInstance csRandSource - - // CsRand is a math/rand instance backed by crypto/rand CSPRNG. - CsRand = rand.New(csRandSourceInstance) -) - -type csRandSource struct { - // This does not keep any state as it is backed by crypto/rand. -} - -func (r csRandSource) Int63() int64 { - var src [8]byte - err := Bytes(src[:]) - if err != nil { - panic(err) - } - val := binary.BigEndian.Uint64(src[:]) - val &= (1<<63 - 1) - - return int64(val) -} - -func (r csRandSource) Seed(seed int64) { - // No-op. -} - -// Intn returns, as a int, a pseudo random number in [0, n). -func Intn(n int) int { - return CsRand.Intn(n) -} - -// Float64 returns, as a float64, a pesudo random number in [0.0,1.0). -func Float64() float64 { - return CsRand.Float64() -} - -// IntRange returns a uniformly distributed int [min, max]. -func IntRange(min, max int) int { - if max < min { - panic(fmt.Sprintf("IntRange: min > max (%d, %d)", min, max)) - } - - r := (max + 1) - min - ret := CsRand.Intn(r) - return ret + min -} - -// Bytes fills the slice with random data. -func Bytes(buf []byte) error { - _, err := io.ReadFull(cryptRand.Reader, buf) - if err != nil { - return err - } - - return nil -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/drbg/hash_drbg.go b/drbg/hash_drbg.go deleted file mode 100644 index c94902a..0000000 --- a/drbg/hash_drbg.go +++ /dev/null @@ -1,147 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 drbg implements a minimalistic DRBG based off SipHash-2-4 in OFB -// mode. -package drbg - -import ( - "encoding/base64" - "encoding/binary" - "fmt" - "hash" - - "github.com/dchest/siphash" - - "git.torproject.org/pluggable-transports/obfs4.git/csrand" -) - -// Size is the length of the HashDrbg output. -const Size = siphash.Size - -// SeedLength is the length of the HashDrbg seed. -const SeedLength = 16 + Size - -// Seed is the initial state for a HashDrbg. It consists of a SipHash-2-4 -// key, and 8 bytes of initial data. -type Seed [SeedLength]byte - -// Bytes returns a pointer to the raw HashDrbg seed. -func (seed *Seed) Bytes() *[SeedLength]byte { - return (*[SeedLength]byte)(seed) -} - -// Base64 returns the Base64 representation of the seed. -func (seed *Seed) Base64() string { - return base64.StdEncoding.EncodeToString(seed.Bytes()[:]) -} - -// NewSeed returns a Seed initialized with the runtime CSPRNG. -func NewSeed() (seed *Seed, err error) { - seed = new(Seed) - err = csrand.Bytes(seed.Bytes()[:]) - if err != nil { - return nil, err - } - - return -} - -// SeedFromBytes creates a Seed from the raw bytes, truncating to SeedLength as -// appropriate. -func SeedFromBytes(src []byte) (seed *Seed, err error) { - if len(src) < SeedLength { - return nil, InvalidSeedLengthError(len(src)) - } - - seed = new(Seed) - copy(seed.Bytes()[:], src) - - return -} - -// SeedFromBase64 creates a Seed from the Base64 representation, truncating to -// SeedLength as appropriate. -func SeedFromBase64(encoded string) (seed *Seed, err error) { - var raw []byte - raw, err = base64.StdEncoding.DecodeString(encoded) - if err != nil { - return nil, err - } - - return SeedFromBytes(raw) -} - -// InvalidSeedLengthError is the error returned when the seed provided to the -// DRBG is an invalid length. -type InvalidSeedLengthError int - -func (e InvalidSeedLengthError) Error() string { - return fmt.Sprintf("invalid seed length: %d", int(e)) -} - -// HashDrbg is a CSDRBG based off of SipHash-2-4 in OFB mode. -type HashDrbg struct { - sip hash.Hash64 - ofb [Size]byte -} - -// NewHashDrbg makes a HashDrbg instance based off an optional seed. The seed -// is truncated to SeedLength. -func NewHashDrbg(seed *Seed) *HashDrbg { - drbg := new(HashDrbg) - drbg.sip = siphash.New(seed.Bytes()[:16]) - copy(drbg.ofb[:], seed.Bytes()[16:]) - - return drbg -} - -// Int63 returns a uniformly distributed random integer [0, 1 << 63). -func (drbg *HashDrbg) Int63() int64 { - block := drbg.NextBlock() - ret := binary.BigEndian.Uint64(block) - ret &= (1<<63 - 1) - - return int64(ret) -} - -// Seed does nothing, call NewHashDrbg if you want to reseed. -func (drbg *HashDrbg) Seed(seed int64) { - // No-op. -} - -// NextBlock returns the next 8 byte DRBG block. -func (drbg *HashDrbg) NextBlock() []byte { - drbg.sip.Write(drbg.ofb[:]) - copy(drbg.ofb[:], drbg.sip.Sum(nil)) - - ret := make([]byte, Size) - copy(ret, drbg.ofb[:]) - return ret -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/framing/framing.go b/framing/framing.go deleted file mode 100644 index 725a762..0000000 --- a/framing/framing.go +++ /dev/null @@ -1,310 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 framing implements the obfs4 link framing and cryptography. -// -// The Encoder/Decoder shared secret format is: -// uint8_t[32] NaCl secretbox key -// uint8_t[16] NaCl Nonce prefix -// uint8_t[16] SipHash-2-4 key (used to obfsucate length) -// uint8_t[8] SipHash-2-4 IV -// -// The frame format is: -// uint16_t length (obfsucated, big endian) -// NaCl secretbox (Poly1305/XSalsa20) containing: -// uint8_t[16] tag (Part of the secretbox construct) -// uint8_t[] payload -// -// The length field is length of the NaCl secretbox XORed with the truncated -// SipHash-2-4 digest ran in OFB mode. -// -// Initialize K, IV[0] with values from the shared secret. -// On each packet, IV[n] = H(K, IV[n - 1]) -// mask[n] = IV[n][0:2] -// obfsLen = length ^ mask[n] -// -// The NaCl secretbox (Poly1305/XSalsa20) nonce format is: -// uint8_t[24] prefix (Fixed) -// uint64_t counter (Big endian) -// -// The counter is initialized to 1, and is incremented on each frame. Since -// the protocol is designed to be used over a reliable medium, the nonce is not -// transmitted over the wire as both sides of the conversation know the prefix -// and the initial counter value. It is imperative that the counter does not -// wrap, and sessions MUST terminate before 2^64 frames are sent. -// -package framing - -import ( - "bytes" - "encoding/binary" - "errors" - "fmt" - "io" - - "code.google.com/p/go.crypto/nacl/secretbox" - - "git.torproject.org/pluggable-transports/obfs4.git/csrand" - "git.torproject.org/pluggable-transports/obfs4.git/drbg" -) - -const ( - // MaximumSegmentLength is the length of the largest possible segment - // including overhead. - MaximumSegmentLength = 1500 - (40 + 12) - - // FrameOverhead is the length of the framing overhead. - FrameOverhead = lengthLength + secretbox.Overhead - - // MaximumFramePayloadLength is the length of the maximum allowed payload - // per frame. - MaximumFramePayloadLength = MaximumSegmentLength - FrameOverhead - - // KeyLength is the length of the Encoder/Decoder secret key. - KeyLength = keyLength + noncePrefixLength + drbg.SeedLength - - maxFrameLength = MaximumSegmentLength - lengthLength - minFrameLength = FrameOverhead - lengthLength - - keyLength = 32 - - noncePrefixLength = 16 - nonceCounterLength = 8 - nonceLength = noncePrefixLength + nonceCounterLength - - lengthLength = 2 -) - -// Error returned when Decoder.Decode() requires more data to continue. -var ErrAgain = errors.New("framing: More data needed to decode") - -// Error returned when Decoder.Decode() failes to authenticate a frame. -var ErrTagMismatch = errors.New("framing: Poly1305 tag mismatch") - -// Error returned when the NaCl secretbox nonce's counter wraps (FATAL). -var ErrNonceCounterWrapped = errors.New("framing: Nonce counter wrapped") - -// InvalidPayloadLengthError is the error returned when Encoder.Encode() -// rejects the payload length. -type InvalidPayloadLengthError int - -func (e InvalidPayloadLengthError) Error() string { - return fmt.Sprintf("framing: Invalid payload length: %d", int(e)) -} - -type boxNonce struct { - prefix [noncePrefixLength]byte - counter uint64 -} - -func (nonce *boxNonce) init(prefix []byte) { - if noncePrefixLength != len(prefix) { - panic(fmt.Sprintf("BUG: Nonce prefix length invalid: %d", len(prefix))) - } - - copy(nonce.prefix[:], prefix) - nonce.counter = 1 -} - -func (nonce boxNonce) bytes(out *[nonceLength]byte) error { - // The security guarantee of Poly1305 is broken if a nonce is ever reused - // for a given key. Detect this by checking for counter wraparound since - // we start each counter at 1. If it ever happens that more than 2^64 - 1 - // frames are transmitted over a given connection, support for rekeying - // will be neccecary, but that's unlikely to happen. - if nonce.counter == 0 { - return ErrNonceCounterWrapped - } - - copy(out[:], nonce.prefix[:]) - binary.BigEndian.PutUint64(out[noncePrefixLength:], nonce.counter) - - return nil -} - -// Encoder is a frame encoder instance. -type Encoder struct { - key [keyLength]byte - nonce boxNonce - drbg *drbg.HashDrbg -} - -// NewEncoder creates a new Encoder instance. It must be supplied a slice -// containing exactly KeyLength bytes of keying material. -func NewEncoder(key []byte) *Encoder { - if len(key) != KeyLength { - panic(fmt.Sprintf("BUG: Invalid encoder key length: %d", len(key))) - } - - encoder := new(Encoder) - copy(encoder.key[:], key[0:keyLength]) - encoder.nonce.init(key[keyLength : keyLength+noncePrefixLength]) - seed, err := drbg.SeedFromBytes(key[keyLength+noncePrefixLength:]) - if err != nil { - panic(fmt.Sprintf("BUG: Failed to initialize DRBG: %s", err)) - } - encoder.drbg = drbg.NewHashDrbg(seed) - - return encoder -} - -// Encode encodes a single frame worth of payload and returns the encoded -// length. InvalidPayloadLengthError is recoverable, all other errors MUST be -// treated as fatal and the session aborted. -func (encoder *Encoder) Encode(frame, payload []byte) (n int, err error) { - payloadLen := len(payload) - if MaximumFramePayloadLength < payloadLen { - return 0, InvalidPayloadLengthError(payloadLen) - } - if len(frame) < payloadLen+FrameOverhead { - return 0, io.ErrShortBuffer - } - - // Generate a new nonce. - var nonce [nonceLength]byte - err = encoder.nonce.bytes(&nonce) - if err != nil { - return 0, err - } - encoder.nonce.counter++ - - // Encrypt and MAC payload. - box := secretbox.Seal(frame[:lengthLength], payload, &nonce, &encoder.key) - - // Obfuscate the length. - length := uint16(len(box) - lengthLength) - lengthMask := encoder.drbg.NextBlock() - length ^= binary.BigEndian.Uint16(lengthMask) - binary.BigEndian.PutUint16(frame[:2], length) - - // Return the frame. - return len(box), nil -} - -// Decoder is a frame decoder instance. -type Decoder struct { - key [keyLength]byte - nonce boxNonce - drbg *drbg.HashDrbg - - nextNonce [nonceLength]byte - nextLength uint16 - nextLengthInvalid bool -} - -// NewDecoder creates a new Decoder instance. It must be supplied a slice -// containing exactly KeyLength bytes of keying material. -func NewDecoder(key []byte) *Decoder { - if len(key) != KeyLength { - panic(fmt.Sprintf("BUG: Invalid decoder key length: %d", len(key))) - } - - decoder := new(Decoder) - copy(decoder.key[:], key[0:keyLength]) - decoder.nonce.init(key[keyLength : keyLength+noncePrefixLength]) - seed, err := drbg.SeedFromBytes(key[keyLength+noncePrefixLength:]) - if err != nil { - panic(fmt.Sprintf("BUG: Failed to initialize DRBG: %s", err)) - } - decoder.drbg = drbg.NewHashDrbg(seed) - - return decoder -} - -// Decode decodes a stream of data and returns the length if any. ErrAgain is -// a temporary failure, all other errors MUST be treated as fatal and the -// session aborted. -func (decoder *Decoder) Decode(data []byte, frames *bytes.Buffer) (int, error) { - // A length of 0 indicates that we do not know how big the next frame is - // going to be. - if decoder.nextLength == 0 { - // Attempt to pull out the next frame length. - if lengthLength > frames.Len() { - return 0, ErrAgain - } - - // Remove the length field from the buffer. - var obfsLen [lengthLength]byte - _, err := io.ReadFull(frames, obfsLen[:]) - if err != nil { - return 0, err - } - - // Derive the nonce the peer used. - err = decoder.nonce.bytes(&decoder.nextNonce) - if err != nil { - return 0, err - } - - // Deobfuscate the length field. - length := binary.BigEndian.Uint16(obfsLen[:]) - lengthMask := decoder.drbg.NextBlock() - length ^= binary.BigEndian.Uint16(lengthMask) - if maxFrameLength < length || minFrameLength > length { - // Per "Plaintext Recovery Attacks Against SSH" by - // Martin R. Albrecht, Kenneth G. Paterson and Gaven J. Watson, - // there are a class of attacks againt protocols that use similar - // sorts of framing schemes. - // - // While obfs4 should not allow plaintext recovery (CBC mode is - // not used), attempt to mitigate out of bound frame length errors - // by pretending that the length was a random valid range as per - // the countermeasure suggested by Denis Bider in section 6 of the - // paper. - - decoder.nextLengthInvalid = true - length = uint16(csrand.IntRange(minFrameLength, maxFrameLength)) - } - decoder.nextLength = length - } - - if int(decoder.nextLength) > frames.Len() { - return 0, ErrAgain - } - - // Unseal the frame. - var box [maxFrameLength]byte - n, err := io.ReadFull(frames, box[:decoder.nextLength]) - if err != nil { - return 0, err - } - out, ok := secretbox.Open(data[:0], box[:n], &decoder.nextNonce, &decoder.key) - if !ok || decoder.nextLengthInvalid { - // When a random length is used (on length error) the tag should always - // mismatch, but be paranoid. - return 0, ErrTagMismatch - } - - // Clean up and prepare for the next frame. - decoder.nextLength = 0 - decoder.nonce.counter++ - - return len(out), nil -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/framing/framing_test.go b/framing/framing_test.go deleted file mode 100644 index 7df0e28..0000000 --- a/framing/framing_test.go +++ /dev/null @@ -1,171 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 framing - -import ( - "bytes" - "crypto/rand" - "testing" -) - -func generateRandomKey() []byte { - key := make([]byte, KeyLength) - - _, err := rand.Read(key) - if err != nil { - panic(err) - } - - return key -} - -func newEncoder(t *testing.T) *Encoder { - // Generate a key to use. - key := generateRandomKey() - - encoder := NewEncoder(key) - if encoder == nil { - t.Fatalf("NewEncoder returned nil") - } - - return encoder -} - -// TestNewEncoder tests the Encoder ctor. -func TestNewEncoder(t *testing.T) { - encoder := newEncoder(t) - _ = encoder -} - -// TestEncoder_Encode tests Encoder.Encode. -func TestEncoder_Encode(t *testing.T) { - encoder := newEncoder(t) - - buf := make([]byte, MaximumFramePayloadLength) - _, _ = rand.Read(buf) // YOLO - for i := 0; i <= MaximumFramePayloadLength; i++ { - var frame [MaximumSegmentLength]byte - n, err := encoder.Encode(frame[:], buf[0:i]) - if err != nil { - t.Fatalf("Encoder.encode([%d]byte), failed: %s", i, err) - } - if n != i+FrameOverhead { - t.Fatalf("Unexpected encoded framesize: %d, expecting %d", n, i+ - FrameOverhead) - } - } -} - -// TestEncoder_Encode_Oversize tests oversized frame rejection. -func TestEncoder_Encode_Oversize(t *testing.T) { - encoder := newEncoder(t) - - var frame [MaximumSegmentLength]byte - var buf [MaximumFramePayloadLength + 1]byte - _, _ = rand.Read(buf[:]) // YOLO - _, err := encoder.Encode(frame[:], buf[:]) - if _, ok := err.(InvalidPayloadLengthError); !ok { - t.Error("Encoder.encode() returned unexpected error:", err) - } -} - -// TestNewDecoder tests the Decoder ctor. -func TestNewDecoder(t *testing.T) { - key := generateRandomKey() - decoder := NewDecoder(key) - if decoder == nil { - t.Fatalf("NewDecoder returned nil") - } -} - -// TestDecoder_Decode tests Decoder.Decode. -func TestDecoder_Decode(t *testing.T) { - key := generateRandomKey() - - encoder := NewEncoder(key) - decoder := NewDecoder(key) - - var buf [MaximumFramePayloadLength]byte - _, _ = rand.Read(buf[:]) // YOLO - for i := 0; i <= MaximumFramePayloadLength; i++ { - var frame [MaximumSegmentLength]byte - encLen, err := encoder.Encode(frame[:], buf[0:i]) - if err != nil { - t.Fatalf("Encoder.encode([%d]byte), failed: %s", i, err) - } - if encLen != i+FrameOverhead { - t.Fatalf("Unexpected encoded framesize: %d, expecting %d", encLen, - i+FrameOverhead) - } - - var decoded [MaximumFramePayloadLength]byte - - decLen, err := decoder.Decode(decoded[:], bytes.NewBuffer(frame[:encLen])) - if err != nil { - t.Fatalf("Decoder.decode([%d]byte), failed: %s", i, err) - } - if decLen != i { - t.Fatalf("Unexpected decoded framesize: %d, expecting %d", - decLen, i) - } - - if 0 != bytes.Compare(decoded[:decLen], buf[:i]) { - t.Fatalf("Frame %d does not match encoder input", i) - } - } -} - -// BencharkEncoder_Encode benchmarks Encoder.Encode processing 1 MiB -// of payload. -func BenchmarkEncoder_Encode(b *testing.B) { - var chopBuf [MaximumFramePayloadLength]byte - var frame [MaximumSegmentLength]byte - payload := make([]byte, 1024*1024) - encoder := NewEncoder(generateRandomKey()) - b.ResetTimer() - - for i := 0; i < b.N; i++ { - transfered := 0 - buffer := bytes.NewBuffer(payload) - for 0 < buffer.Len() { - n, err := buffer.Read(chopBuf[:]) - if err != nil { - b.Fatal("buffer.Read() failed:", err) - } - - n, err = encoder.Encode(frame[:], chopBuf[:n]) - transfered += n - FrameOverhead - } - if transfered != len(payload) { - b.Fatalf("Transfered length mismatch: %d != %d", transfered, - len(payload)) - } - } -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/handshake_ntor.go b/handshake_ntor.go deleted file mode 100644 index 8192494..0000000 --- a/handshake_ntor.go +++ /dev/null @@ -1,427 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ( - "bytes" - "crypto/hmac" - "crypto/sha256" - "encoding/hex" - "errors" - "fmt" - "hash" - "strconv" - "time" - - "git.torproject.org/pluggable-transports/obfs4.git/csrand" - "git.torproject.org/pluggable-transports/obfs4.git/framing" - "git.torproject.org/pluggable-transports/obfs4.git/ntor" -) - -const ( - maxHandshakeLength = 8192 - - clientMinPadLength = (serverMinHandshakeLength + inlineSeedFrameLength) - - clientMinHandshakeLength - clientMaxPadLength = maxHandshakeLength - clientMinHandshakeLength - clientMinHandshakeLength = ntor.RepresentativeLength + markLength + macLength - - serverMinPadLength = 0 - serverMaxPadLength = maxHandshakeLength - (serverMinHandshakeLength + - inlineSeedFrameLength) - serverMinHandshakeLength = ntor.RepresentativeLength + ntor.AuthLength + - markLength + macLength - - markLength = sha256.Size / 2 - macLength = sha256.Size / 2 - - inlineSeedFrameLength = framing.FrameOverhead + packetOverhead + seedPacketPayloadLength -) - -// ErrMarkNotFoundYet is the error returned when the obfs4 handshake is -// incomplete and requires more data to continue. This error is non-fatal and -// is the equivalent to EAGAIN/EWOULDBLOCK. -var ErrMarkNotFoundYet = errors.New("handshake: M_[C,S] not found yet") - -// ErrInvalidHandshake is the error returned when the obfs4 handshake fails due -// to the peer not sending the correct mark. This error is fatal and the -// connection MUST be dropped. -var ErrInvalidHandshake = errors.New("handshake: Failed to find M_[C,S]") - -// ErrReplayedHandshake is the error returned when the obfs4 handshake fails -// due it being replayed. This error is fatal and the connection MUST be -// dropped. -var ErrReplayedHandshake = errors.New("handshake: Replay detected") - -// ErrNtorFailed is the error returned when the ntor handshake fails. This -// error is fatal and the connection MUST be dropped. -var ErrNtorFailed = errors.New("handshake: ntor handshake failure") - -// InvalidMacError is the error returned when the handshake MACs do not match. -// This error is fatal and the connection MUST be dropped. -type InvalidMacError struct { - Derived []byte - Received []byte -} - -func (e *InvalidMacError) Error() string { - return fmt.Sprintf("handshake: MAC mismatch: Dervied: %s Received: %s.", - hex.EncodeToString(e.Derived), hex.EncodeToString(e.Received)) -} - -// InvalidAuthError is the error returned when the ntor AUTH tags do not match. -// This error is fatal and the connection MUST be dropped. -type InvalidAuthError struct { - Derived *ntor.Auth - Received *ntor.Auth -} - -func (e *InvalidAuthError) Error() string { - return fmt.Sprintf("handshake: ntor AUTH mismatch: Derived: %s Received:%s.", - hex.EncodeToString(e.Derived.Bytes()[:]), - hex.EncodeToString(e.Received.Bytes()[:])) -} - -type clientHandshake struct { - keypair *ntor.Keypair - nodeID *ntor.NodeID - serverIdentity *ntor.PublicKey - epochHour []byte - - padLen int - mac hash.Hash - - serverRepresentative *ntor.Representative - serverAuth *ntor.Auth - serverMark []byte -} - -func newClientHandshake(nodeID *ntor.NodeID, serverIdentity *ntor.PublicKey, sessionKey *ntor.Keypair) *clientHandshake { - hs := new(clientHandshake) - hs.keypair = sessionKey - hs.nodeID = nodeID - hs.serverIdentity = serverIdentity - hs.padLen = csrand.IntRange(clientMinPadLength, clientMaxPadLength) - hs.mac = hmac.New(sha256.New, append(hs.serverIdentity.Bytes()[:], hs.nodeID.Bytes()[:]...)) - - return hs -} - -func (hs *clientHandshake) generateHandshake() ([]byte, error) { - var buf bytes.Buffer - - hs.mac.Reset() - hs.mac.Write(hs.keypair.Representative().Bytes()[:]) - mark := hs.mac.Sum(nil)[:markLength] - - // The client handshake is X | P_C | M_C | MAC(X | P_C | M_C | E) where: - // * X is the client's ephemeral Curve25519 public key representative. - // * P_C is [clientMinPadLength,clientMaxPadLength] bytes of random padding. - // * M_C is HMAC-SHA256-128(serverIdentity | NodeID, X) - // * MAC is HMAC-SHA256-128(serverIdentity | NodeID, X .... E) - // * E is the string representation of the number of hours since the UNIX - // epoch. - - // Generate the padding - pad, err := makePad(hs.padLen) - if err != nil { - return nil, err - } - - // Write X, P_C, M_C. - buf.Write(hs.keypair.Representative().Bytes()[:]) - buf.Write(pad) - buf.Write(mark) - - // Calculate and write the MAC. - hs.mac.Reset() - hs.mac.Write(buf.Bytes()) - hs.epochHour = []byte(strconv.FormatInt(getEpochHour(), 10)) - hs.mac.Write(hs.epochHour) - buf.Write(hs.mac.Sum(nil)[:macLength]) - - return buf.Bytes(), nil -} - -func (hs *clientHandshake) parseServerHandshake(resp []byte) (int, []byte, error) { - // No point in examining the data unless the miminum plausible response has - // been received. - if serverMinHandshakeLength > len(resp) { - return 0, nil, ErrMarkNotFoundYet - } - - if hs.serverRepresentative == nil || hs.serverAuth == nil { - // Pull out the representative/AUTH. (XXX: Add ctors to ntor) - hs.serverRepresentative = new(ntor.Representative) - copy(hs.serverRepresentative.Bytes()[:], resp[0:ntor.RepresentativeLength]) - hs.serverAuth = new(ntor.Auth) - copy(hs.serverAuth.Bytes()[:], resp[ntor.RepresentativeLength:]) - - // Derive the mark. - hs.mac.Reset() - hs.mac.Write(hs.serverRepresentative.Bytes()[:]) - hs.serverMark = hs.mac.Sum(nil)[:markLength] - } - - // Attempt to find the mark + MAC. - pos := findMarkMac(hs.serverMark, resp, ntor.RepresentativeLength+ntor.AuthLength+serverMinPadLength, - maxHandshakeLength, false) - if pos == -1 { - if len(resp) >= maxHandshakeLength { - return 0, nil, ErrInvalidHandshake - } - return 0, nil, ErrMarkNotFoundYet - } - - // Validate the MAC. - hs.mac.Reset() - hs.mac.Write(resp[:pos+markLength]) - hs.mac.Write(hs.epochHour) - macCmp := hs.mac.Sum(nil)[:macLength] - macRx := resp[pos+markLength : pos+markLength+macLength] - if !hmac.Equal(macCmp, macRx) { - return 0, nil, &InvalidMacError{macCmp, macRx} - } - - // Complete the handshake. - serverPublic := hs.serverRepresentative.ToPublic() - ok, seed, auth := ntor.ClientHandshake(hs.keypair, serverPublic, - hs.serverIdentity, hs.nodeID) - if !ok { - return 0, nil, ErrNtorFailed - } - if !ntor.CompareAuth(auth, hs.serverAuth.Bytes()[:]) { - return 0, nil, &InvalidAuthError{auth, hs.serverAuth} - } - - return pos + markLength + macLength, seed.Bytes()[:], nil -} - -type serverHandshake struct { - keypair *ntor.Keypair - nodeID *ntor.NodeID - serverIdentity *ntor.Keypair - epochHour []byte - serverAuth *ntor.Auth - - padLen int - mac hash.Hash - - clientRepresentative *ntor.Representative - clientMark []byte -} - -func newServerHandshake(nodeID *ntor.NodeID, serverIdentity *ntor.Keypair, sessionKey *ntor.Keypair) *serverHandshake { - hs := new(serverHandshake) - hs.keypair = sessionKey - hs.nodeID = nodeID - hs.serverIdentity = serverIdentity - hs.padLen = csrand.IntRange(serverMinPadLength, serverMaxPadLength) - hs.mac = hmac.New(sha256.New, append(hs.serverIdentity.Public().Bytes()[:], hs.nodeID.Bytes()[:]...)) - - return hs -} - -func (hs *serverHandshake) parseClientHandshake(filter *replayFilter, resp []byte) ([]byte, error) { - // No point in examining the data unless the miminum plausible response has - // been received. - if clientMinHandshakeLength > len(resp) { - return nil, ErrMarkNotFoundYet - } - - if hs.clientRepresentative == nil { - // Pull out the representative/AUTH. (XXX: Add ctors to ntor) - hs.clientRepresentative = new(ntor.Representative) - copy(hs.clientRepresentative.Bytes()[:], resp[0:ntor.RepresentativeLength]) - - // Derive the mark. - hs.mac.Reset() - hs.mac.Write(hs.clientRepresentative.Bytes()[:]) - hs.clientMark = hs.mac.Sum(nil)[:markLength] - } - - // Attempt to find the mark + MAC. - pos := findMarkMac(hs.clientMark, resp, ntor.RepresentativeLength+clientMinPadLength, - maxHandshakeLength, true) - if pos == -1 { - if len(resp) >= maxHandshakeLength { - return nil, ErrInvalidHandshake - } - return nil, ErrMarkNotFoundYet - } - - // Validate the MAC. - macFound := false - for _, off := range []int64{0, -1, 1} { - // Allow epoch to be off by up to a hour in either direction. - epochHour := []byte(strconv.FormatInt(getEpochHour()+int64(off), 10)) - hs.mac.Reset() - hs.mac.Write(resp[:pos+markLength]) - hs.mac.Write(epochHour) - macCmp := hs.mac.Sum(nil)[:macLength] - macRx := resp[pos+markLength : pos+markLength+macLength] - if hmac.Equal(macCmp, macRx) { - // Ensure that this handshake has not been seen previously. - if filter.testAndSet(time.Now().Unix(), macRx) { - // The client either happened to generate exactly the same - // session key and padding, or someone is replaying a previous - // handshake. In either case, fuck them. - return nil, ErrReplayedHandshake - } - - macFound = true - hs.epochHour = epochHour - - // We could break out here, but in the name of reducing timing - // variation, evaluate all 3 MACs. - } - } - if !macFound { - // This probably should be an InvalidMacError, but conveying the 3 MACS - // that would be accepted is annoying so just return a generic fatal - // failure. - return nil, ErrInvalidHandshake - } - - // Client should never sent trailing garbage. - if len(resp) != pos+markLength+macLength { - return nil, ErrInvalidHandshake - } - - clientPublic := hs.clientRepresentative.ToPublic() - ok, seed, auth := ntor.ServerHandshake(clientPublic, hs.keypair, - hs.serverIdentity, hs.nodeID) - if !ok { - return nil, ErrNtorFailed - } - hs.serverAuth = auth - - return seed.Bytes()[:], nil -} - -func (hs *serverHandshake) generateHandshake() ([]byte, error) { - var buf bytes.Buffer - - hs.mac.Reset() - hs.mac.Write(hs.keypair.Representative().Bytes()[:]) - mark := hs.mac.Sum(nil)[:markLength] - - // The server handshake is Y | AUTH | P_S | M_S | MAC(Y | AUTH | P_S | M_S | E) where: - // * Y is the server's ephemeral Curve25519 public key representative. - // * AUTH is the ntor handshake AUTH value. - // * P_S is [serverMinPadLength,serverMaxPadLength] bytes of random padding. - // * M_S is HMAC-SHA256-128(serverIdentity | NodeID, Y) - // * MAC is HMAC-SHA256-128(serverIdentity | NodeID, Y .... E) - // * E is the string representation of the number of hours since the UNIX - // epoch. - - // Generate the padding - pad, err := makePad(hs.padLen) - if err != nil { - return nil, err - } - - // Write Y, AUTH, P_S, M_S. - buf.Write(hs.keypair.Representative().Bytes()[:]) - buf.Write(hs.serverAuth.Bytes()[:]) - buf.Write(pad) - buf.Write(mark) - - // Calculate and write the MAC. - hs.mac.Reset() - hs.mac.Write(buf.Bytes()) - hs.epochHour = []byte(strconv.FormatInt(getEpochHour(), 10)) - hs.mac.Write(hs.epochHour) - buf.Write(hs.mac.Sum(nil)[:macLength]) - - return buf.Bytes(), nil -} - -// getEpochHour returns the number of hours since the UNIX epoch. -func getEpochHour() int64 { - return time.Now().Unix() / 3600 -} - -func findMarkMac(mark, buf []byte, startPos, maxPos int, fromTail bool) (pos int) { - if len(mark) != markLength { - panic(fmt.Sprintf("BUG: Invalid mark length: %d", len(mark))) - } - - endPos := len(buf) - if startPos > len(buf) { - return -1 - } - if endPos > maxPos { - endPos = maxPos - } - if endPos-startPos < markLength+macLength { - return -1 - } - - if fromTail { - // The server can optimize the search process by only examining the - // tail of the buffer. The client can't send valid data past M_C | - // MAC_C as it does not have the server's public key yet. - pos = endPos - (markLength + macLength) - if !hmac.Equal(buf[pos:pos+markLength], mark) { - return -1 - } - - return - } - - // The client has to actually do a substring search since the server can - // and will send payload trailing the response. - // - // XXX: bytes.Index() uses a naive search, which kind of sucks. - pos = bytes.Index(buf[startPos:endPos], mark) - if pos == -1 { - return -1 - } - - // Ensure that there is enough trailing data for the MAC. - if startPos+pos+markLength+macLength > endPos { - return -1 - } - - // Return the index relative to the start of the slice. - pos += startPos - return -} - -func makePad(padLen int) ([]byte, error) { - pad := make([]byte, padLen) - err := csrand.Bytes(pad) - if err != nil { - return nil, err - } - - return pad, err -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/handshake_ntor_test.go b/handshake_ntor_test.go deleted file mode 100644 index 94d2a7f..0000000 --- a/handshake_ntor_test.go +++ /dev/null @@ -1,221 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ( - "bytes" - "testing" - - "git.torproject.org/pluggable-transports/obfs4.git/ntor" -) - -func TestHandshakeNtor(t *testing.T) { - // Generate the server node id and id keypair. - nodeID, _ := ntor.NewNodeID([]byte("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13")) - idKeypair, _ := ntor.NewKeypair(false) - serverFilter, _ := newReplayFilter() - - // Test client handshake padding. - for l := clientMinPadLength; l <= clientMaxPadLength; l++ { - // Generate the client state and override the pad length. - clientKeypair, err := ntor.NewKeypair(true) - if err != nil { - t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) - } - clientHs := newClientHandshake(nodeID, idKeypair.Public(), clientKeypair) - clientHs.padLen = l - - // Generate what the client will send to the server. - clientBlob, err := clientHs.generateHandshake() - if err != nil { - t.Fatalf("[%d:0] clientHandshake.generateHandshake() failed: %s", l, err) - } - if len(clientBlob) > maxHandshakeLength { - t.Fatalf("[%d:0] Generated client body is oversized: %d", l, len(clientBlob)) - } - if len(clientBlob) < clientMinHandshakeLength { - t.Fatalf("[%d:0] Generated client body is undersized: %d", l, len(clientBlob)) - } - if len(clientBlob) != clientMinHandshakeLength+l { - t.Fatalf("[%d:0] Generated client body incorrect size: %d", l, len(clientBlob)) - } - - // Generate the server state and override the pad length. - serverKeypair, err := ntor.NewKeypair(true) - if err != nil { - t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) - } - serverHs := newServerHandshake(nodeID, idKeypair, serverKeypair) - serverHs.padLen = serverMinPadLength - - // Parse the client handshake message. - serverSeed, err := serverHs.parseClientHandshake(serverFilter, clientBlob) - if err != nil { - t.Fatalf("[%d:0] serverHandshake.parseClientHandshake() failed: %s", l, err) - } - - // Genrate what the server will send to the client. - serverBlob, err := serverHs.generateHandshake() - if err != nil { - t.Fatal("[%d:0]: serverHandshake.generateHandshake() failed: %s", l, err) - } - - // Parse the server handshake message. - clientHs.serverRepresentative = nil - n, clientSeed, err := clientHs.parseServerHandshake(serverBlob) - if err != nil { - t.Fatalf("[%d:0] clientHandshake.parseServerHandshake() failed: %s", l, err) - } - if n != len(serverBlob) { - t.Fatalf("[%d:0] clientHandshake.parseServerHandshake() has bytes remaining: %d", l, n) - } - - // Ensure the derived shared secret is the same. - if 0 != bytes.Compare(clientSeed, serverSeed) { - t.Fatalf("[%d:0] client/server seed mismatch", l) - } - } - - // Test server handshake padding. - for l := serverMinPadLength; l <= serverMaxPadLength+inlineSeedFrameLength; l++ { - // Generate the client state and override the pad length. - clientKeypair, err := ntor.NewKeypair(true) - if err != nil { - t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) - } - clientHs := newClientHandshake(nodeID, idKeypair.Public(), clientKeypair) - clientHs.padLen = clientMinPadLength - - // Generate what the client will send to the server. - clientBlob, err := clientHs.generateHandshake() - if err != nil { - t.Fatalf("[%d:1] clientHandshake.generateHandshake() failed: %s", l, err) - } - if len(clientBlob) > maxHandshakeLength { - t.Fatalf("[%d:1] Generated client body is oversized: %d", l, len(clientBlob)) - } - - // Generate the server state and override the pad length. - serverKeypair, err := ntor.NewKeypair(true) - if err != nil { - t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) - } - serverHs := newServerHandshake(nodeID, idKeypair, serverKeypair) - serverHs.padLen = l - - // Parse the client handshake message. - serverSeed, err := serverHs.parseClientHandshake(serverFilter, clientBlob) - if err != nil { - t.Fatalf("[%d:1] serverHandshake.parseClientHandshake() failed: %s", l, err) - } - - // Genrate what the server will send to the client. - serverBlob, err := serverHs.generateHandshake() - if err != nil { - t.Fatal("[%d:1]: serverHandshake.generateHandshake() failed: %s", l, err) - } - - // Parse the server handshake message. - n, clientSeed, err := clientHs.parseServerHandshake(serverBlob) - if err != nil { - t.Fatalf("[%d:1] clientHandshake.parseServerHandshake() failed: %s", l, err) - } - if n != len(serverBlob) { - t.Fatalf("[%d:1] clientHandshake.parseServerHandshake() has bytes remaining: %d", l, n) - } - - // Ensure the derived shared secret is the same. - if 0 != bytes.Compare(clientSeed, serverSeed) { - t.Fatalf("[%d:1] client/server seed mismatch", l) - } - } - - // Test oversized client padding. - clientKeypair, err := ntor.NewKeypair(true) - if err != nil { - t.Fatalf("ntor.NewKeypair failed: %s", err) - } - clientHs := newClientHandshake(nodeID, idKeypair.Public(), clientKeypair) - if err != nil { - t.Fatalf("newClientHandshake failed: %s", err) - } - - clientHs.padLen = clientMaxPadLength + 1 - clientBlob, err := clientHs.generateHandshake() - if err != nil { - t.Fatalf("clientHandshake.generateHandshake() (forced oversize) failed: %s", err) - } - serverKeypair, err := ntor.NewKeypair(true) - if err != nil { - t.Fatalf("ntor.NewKeypair failed: %s", err) - } - serverHs := newServerHandshake(nodeID, idKeypair, serverKeypair) - _, err = serverHs.parseClientHandshake(serverFilter, clientBlob) - if err == nil { - t.Fatalf("serverHandshake.parseClientHandshake() succeded (oversized)") - } - - // Test undersized client padding. - clientHs.padLen = clientMinPadLength - 1 - clientBlob, err = clientHs.generateHandshake() - if err != nil { - t.Fatalf("clientHandshake.generateHandshake() (forced undersize) failed: %s", err) - } - serverHs = newServerHandshake(nodeID, idKeypair, serverKeypair) - _, err = serverHs.parseClientHandshake(serverFilter, clientBlob) - if err == nil { - t.Fatalf("serverHandshake.parseClientHandshake() succeded (undersized)") - } - - // Test oversized server padding. - // - // NB: serverMaxPadLength isn't the real maxPadLength that triggers client - // rejection, because the implementation is written with the asusmption - // that/ the PRNG_SEED is also inlined with the response. Thus the client - // actually accepts longer padding. The server handshake test and this - // test adjust around that. - clientHs.padLen = clientMinPadLength - clientBlob, err = clientHs.generateHandshake() - if err != nil { - t.Fatalf("clientHandshake.generateHandshake() failed: %s", err) - } - serverHs = newServerHandshake(nodeID, idKeypair, serverKeypair) - serverHs.padLen = serverMaxPadLength + inlineSeedFrameLength + 1 - _, err = serverHs.parseClientHandshake(serverFilter, clientBlob) - if err != nil { - t.Fatalf("serverHandshake.parseClientHandshake() failed: %s", err) - } - serverBlob, err := serverHs.generateHandshake() - if err != nil { - t.Fatal("serverHandshake.generateHandshake() (forced oversize) failed: %s", err) - } - _, _, err = clientHs.parseServerHandshake(serverBlob) - if err == nil { - t.Fatalf("clientHandshake.parseServerHandshake() succeded (oversized)") - } -} diff --git a/ntor/ntor.go b/ntor/ntor.go deleted file mode 100644 index b178454..0000000 --- a/ntor/ntor.go +++ /dev/null @@ -1,437 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ntor implements the Tor Project's ntor handshake as defined in -// proposal 216 "Improved circuit-creation key exchange". It also supports -// using Elligator to transform the Curve25519 public keys sent over the wire -// to a form that is indistinguishable from random strings. -// -// Before using this package, it is strongly recommended that the specification -// is read and understood. -// -package ntor - -import ( - "bytes" - "crypto/hmac" - "crypto/sha256" - "crypto/subtle" - "encoding/base64" - "fmt" - "io" - - "code.google.com/p/go.crypto/curve25519" - "code.google.com/p/go.crypto/hkdf" - - "github.com/agl/ed25519/extra25519" - - "git.torproject.org/pluggable-transports/obfs4.git/csrand" -) - -const ( - // PublicKeyLength is the length of a Curve25519 public key. - PublicKeyLength = 32 - - // RepresentativeLength is the length of an Elligator representative. - RepresentativeLength = 32 - - // PrivateKeyLength is the length of a Curve25519 private key. - PrivateKeyLength = 32 - - // SharedSecretLength is the length of a Curve25519 shared secret. - SharedSecretLength = 32 - - // NodeIDLength is the length of a ntor node identifier. - NodeIDLength = 20 - - // KeySeedLength is the length of the derived KEY_SEED. - KeySeedLength = sha256.Size - - // AuthLength is the lenght of the derived AUTH. - AuthLength = sha256.Size -) - -var protoID = []byte("ntor-curve25519-sha256-1") -var tMac = append(protoID, []byte(":mac")...) -var tKey = append(protoID, []byte(":key_extract")...) -var tVerify = append(protoID, []byte(":key_verify")...) -var mExpand = append(protoID, []byte(":key_expand")...) - -// PublicKeyLengthError is the error returned when the public key being -// imported is an invalid length. -type PublicKeyLengthError int - -func (e PublicKeyLengthError) Error() string { - return fmt.Sprintf("ntor: Invalid Curve25519 public key length: %d", - int(e)) -} - -// PrivateKeyLengthError is the error returned when the private key being -// imported is an invalid length. -type PrivateKeyLengthError int - -func (e PrivateKeyLengthError) Error() string { - return fmt.Sprintf("ntor: Invalid Curve25519 private key length: %d", - int(e)) -} - -// NodeIDLengthError is the error returned when the node ID being imported is -// an invalid length. -type NodeIDLengthError int - -func (e NodeIDLengthError) Error() string { - return fmt.Sprintf("ntor: Invalid NodeID length: %d", int(e)) -} - -// KeySeed is the key material that results from a handshake (KEY_SEED). -type KeySeed [KeySeedLength]byte - -// Bytes returns a pointer to the raw key material. -func (key_seed *KeySeed) Bytes() *[KeySeedLength]byte { - return (*[KeySeedLength]byte)(key_seed) -} - -// Auth is the verifier that results from a handshake (AUTH). -type Auth [AuthLength]byte - -// Bytes returns a pointer to the raw auth. -func (auth *Auth) Bytes() *[AuthLength]byte { - return (*[AuthLength]byte)(auth) -} - -// NodeID is a ntor node identifier. -type NodeID [NodeIDLength]byte - -// NewNodeID creates a NodeID from the raw bytes. -func NewNodeID(raw []byte) (*NodeID, error) { - if len(raw) != NodeIDLength { - return nil, NodeIDLengthError(len(raw)) - } - - nodeID := new(NodeID) - copy(nodeID[:], raw) - - return nodeID, nil -} - -// NodeIDFromBase64 creates a new NodeID from the Base64 encoded representation. -func NodeIDFromBase64(encoded string) (*NodeID, error) { - raw, err := base64.StdEncoding.DecodeString(encoded) - if err != nil { - return nil, err - } - - return NewNodeID(raw) -} -// Bytes returns a pointer to the raw NodeID. -func (id *NodeID) Bytes() *[NodeIDLength]byte { - return (*[NodeIDLength]byte)(id) -} - -// Base64 returns the Base64 representation of the NodeID. -func (id *NodeID) Base64() string { - return base64.StdEncoding.EncodeToString(id[:]) -} - -// PublicKey is a Curve25519 public key in little-endian byte order. -type PublicKey [PublicKeyLength]byte - -// Bytes returns a pointer to the raw Curve25519 public key. -func (public *PublicKey) Bytes() *[PublicKeyLength]byte { - return (*[PublicKeyLength]byte)(public) -} - -// Base64 returns the Base64 representation of the Curve25519 public key. -func (public *PublicKey) Base64() string { - return base64.StdEncoding.EncodeToString(public.Bytes()[:]) -} - -// NewPublicKey creates a PublicKey from the raw bytes. -func NewPublicKey(raw []byte) (*PublicKey, error) { - if len(raw) != PublicKeyLength { - return nil, PublicKeyLengthError(len(raw)) - } - - pubKey := new(PublicKey) - copy(pubKey[:], raw) - - return pubKey, nil -} - -// PublicKeyFromBase64 returns a PublicKey from a Base64 representation. -func PublicKeyFromBase64(encoded string) (*PublicKey, error) { - raw, err := base64.StdEncoding.DecodeString(encoded) - if err != nil { - return nil, err - } - - return NewPublicKey(raw) -} - -// Representative is an Elligator representative of a Curve25519 public key -// in little-endian byte order. -type Representative [RepresentativeLength]byte - -// Bytes returns a pointer to the raw Elligator representative. -func (repr *Representative) Bytes() *[RepresentativeLength]byte { - return (*[RepresentativeLength]byte)(repr) -} - -// ToPublic converts a Elligator representative to a Curve25519 public key. -func (repr *Representative) ToPublic() *PublicKey { - pub := new(PublicKey) - - extra25519.RepresentativeToPublicKey(pub.Bytes(), repr.Bytes()) - return pub -} - -// PrivateKey is a Curve25519 private key in little-endian byte order. -type PrivateKey [PrivateKeyLength]byte - -// Bytes returns a pointer to the raw Curve25519 private key. -func (private *PrivateKey) Bytes() *[PrivateKeyLength]byte { - return (*[PrivateKeyLength]byte)(private) -} - -// Base64 returns the Base64 representation of the Curve25519 private key. -func (private *PrivateKey) Base64() string { - return base64.StdEncoding.EncodeToString(private.Bytes()[:]) -} - -// Keypair is a Curve25519 keypair with an optional Elligator representative. -// As only certain Curve25519 keys can be obfuscated with Elligator, the -// representative must be generated along with the keypair. -type Keypair struct { - public *PublicKey - private *PrivateKey - representative *Representative -} - -// Public returns the Curve25519 public key belonging to the Keypair. -func (keypair *Keypair) Public() *PublicKey { - return keypair.public -} - -// Private returns the Curve25519 private key belonging to the Keypair. -func (keypair *Keypair) Private() *PrivateKey { - return keypair.private -} - -// Representative returns the Elligator representative of the public key -// belonging to the Keypair. -func (keypair *Keypair) Representative() *Representative { - return keypair.representative -} - -// HasElligator returns true if the Keypair has an Elligator representative. -func (keypair *Keypair) HasElligator() bool { - return nil != keypair.representative -} - -// NewKeypair generates a new Curve25519 keypair, and optionally also generates -// an Elligator representative of the public key. -func NewKeypair(elligator bool) (*Keypair, error) { - keypair := new(Keypair) - keypair.private = new(PrivateKey) - keypair.public = new(PublicKey) - if elligator { - keypair.representative = new(Representative) - } - - for { - // Generate a Curve25519 private key. Like everyone who does this, - // run the CSPRNG output through SHA256 for extra tinfoil hattery. - priv := keypair.private.Bytes()[:] - err := csrand.Bytes(priv) - if err != nil { - return nil, err - } - digest := sha256.Sum256(priv) - digest[0] &= 248 - digest[31] &= 127 - digest[31] |= 64 - copy(priv, digest[:]) - - if elligator { - // Apply the Elligator transform. This fails ~50% of the time. - if !extra25519.ScalarBaseMult(keypair.public.Bytes(), - keypair.representative.Bytes(), - keypair.private.Bytes()) { - continue - } - } else { - // Generate the corresponding Curve25519 public key. - curve25519.ScalarBaseMult(keypair.public.Bytes(), - keypair.private.Bytes()) - } - - return keypair, nil - } -} - -// KeypairFromBase64 returns a Keypair from a Base64 representation of the -// private key. -func KeypairFromBase64(encoded string) (*Keypair, error) { - raw, err := base64.StdEncoding.DecodeString(encoded) - if err != nil { - return nil, err - } - - if len(raw) != PrivateKeyLength { - return nil, PrivateKeyLengthError(len(raw)) - } - - keypair := new(Keypair) - keypair.private = new(PrivateKey) - keypair.public = new(PublicKey) - - copy(keypair.private[:], raw) - curve25519.ScalarBaseMult(keypair.public.Bytes(), - keypair.private.Bytes()) - - return keypair, nil -} - -// ServerHandshake does the server side of a ntor handshake and returns status, -// KEY_SEED, and AUTH. If status is not true, the handshake MUST be aborted. -func ServerHandshake(clientPublic *PublicKey, serverKeypair *Keypair, idKeypair *Keypair, id *NodeID) (ok bool, keySeed *KeySeed, auth *Auth) { - var notOk int - var secretInput bytes.Buffer - - // Server side uses EXP(X,y) | EXP(X,b) - var exp [SharedSecretLength]byte - curve25519.ScalarMult(&exp, serverKeypair.private.Bytes(), - clientPublic.Bytes()) - notOk |= constantTimeIsZero(exp[:]) - secretInput.Write(exp[:]) - - curve25519.ScalarMult(&exp, idKeypair.private.Bytes(), - clientPublic.Bytes()) - notOk |= constantTimeIsZero(exp[:]) - secretInput.Write(exp[:]) - - keySeed, auth = ntorCommon(secretInput, id, idKeypair.public, - clientPublic, serverKeypair.public) - return notOk == 0, keySeed, auth -} - -// ClientHandshake does the client side of a ntor handshake and returnes -// status, KEY_SEED, and AUTH. If status is not true or AUTH does not match -// the value recieved from the server, the handshake MUST be aborted. -func ClientHandshake(clientKeypair *Keypair, serverPublic *PublicKey, idPublic *PublicKey, id *NodeID) (ok bool, keySeed *KeySeed, auth *Auth) { - var notOk int - var secretInput bytes.Buffer - - // Client side uses EXP(Y,x) | EXP(B,x) - var exp [SharedSecretLength]byte - curve25519.ScalarMult(&exp, clientKeypair.private.Bytes(), - serverPublic.Bytes()) - notOk |= constantTimeIsZero(exp[:]) - secretInput.Write(exp[:]) - - curve25519.ScalarMult(&exp, clientKeypair.private.Bytes(), - idPublic.Bytes()) - notOk |= constantTimeIsZero(exp[:]) - secretInput.Write(exp[:]) - - keySeed, auth = ntorCommon(secretInput, id, idPublic, - clientKeypair.public, serverPublic) - return notOk == 0, keySeed, auth -} - -// CompareAuth does a constant time compare of a Auth and a byte slice -// (presumably received over a network). -func CompareAuth(auth1 *Auth, auth2 []byte) bool { - auth1Bytes := auth1.Bytes() - return hmac.Equal(auth1Bytes[:], auth2) -} - -func ntorCommon(secretInput bytes.Buffer, id *NodeID, b *PublicKey, x *PublicKey, y *PublicKey) (*KeySeed, *Auth) { - keySeed := new(KeySeed) - auth := new(Auth) - - // secret_input/auth_input use this common bit, build it once. - suffix := bytes.NewBuffer(b.Bytes()[:]) - suffix.Write(b.Bytes()[:]) - suffix.Write(x.Bytes()[:]) - suffix.Write(y.Bytes()[:]) - suffix.Write(protoID) - suffix.Write(id[:]) - - // At this point secret_input has the 2 exponents, concatenated, append the - // client/server common suffix. - secretInput.Write(suffix.Bytes()) - - // KEY_SEED = H(secret_input, t_key) - h := hmac.New(sha256.New, tKey) - h.Write(secretInput.Bytes()) - tmp := h.Sum(nil) - copy(keySeed[:], tmp) - - // verify = H(secret_input, t_verify) - h = hmac.New(sha256.New, tVerify) - h.Write(secretInput.Bytes()) - verify := h.Sum(nil) - - // auth_input = verify | ID | B | Y | X | PROTOID | "Server" - authInput := bytes.NewBuffer(verify) - authInput.Write(suffix.Bytes()) - authInput.Write([]byte("Server")) - h = hmac.New(sha256.New, tMac) - h.Write(authInput.Bytes()) - tmp = h.Sum(nil) - copy(auth[:], tmp) - - return keySeed, auth -} - -func constantTimeIsZero(x []byte) int { - var ret byte - for _, v := range x { - ret |= v - } - - return subtle.ConstantTimeByteEq(ret, 0) -} - -// Kdf extracts and expands KEY_SEED via HKDF-SHA256 and returns `okm_len` bytes -// of key material. -func Kdf(keySeed []byte, okmLen int) []byte { - kdf := hkdf.New(sha256.New, keySeed, tKey, mExpand) - okm := make([]byte, okmLen) - n, err := io.ReadFull(kdf, okm) - if err != nil { - panic(fmt.Sprintf("BUG: Failed HKDF: %s", err.Error())) - } else if n != len(okm) { - panic(fmt.Sprintf("BUG: Got truncated HKDF output: %d", n)) - } - - return okm -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/ntor/ntor_test.go b/ntor/ntor_test.go deleted file mode 100644 index 9d7c687..0000000 --- a/ntor/ntor_test.go +++ /dev/null @@ -1,182 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ntor - -import ( - "bytes" - "testing" -) - -// TestNewKeypair tests Curve25519/Elligator keypair generation. -func TestNewKeypair(t *testing.T) { - // Test standard Curve25519 first. - keypair, err := NewKeypair(false) - if err != nil { - t.Fatal("NewKeypair(false) failed:", err) - } - if keypair == nil { - t.Fatal("NewKeypair(false) returned nil") - } - if keypair.HasElligator() { - t.Fatal("NewKeypair(false) has a Elligator representative") - } - - // Test Elligator generation. - keypair, err = NewKeypair(true) - if err != nil { - t.Fatal("NewKeypair(true) failed:", err) - } - if keypair == nil { - t.Fatal("NewKeypair(true) returned nil") - } - if !keypair.HasElligator() { - t.Fatal("NewKeypair(true) mising an Elligator representative") - } -} - -// Test Client/Server handshake. -func TestHandshake(t *testing.T) { - clientKeypair, err := NewKeypair(true) - if err != nil { - t.Fatal("Failed to generate client keypair:", err) - } - if clientKeypair == nil { - t.Fatal("Client keypair is nil") - } - - serverKeypair, err := NewKeypair(true) - if err != nil { - t.Fatal("Failed to generate server keypair:", err) - } - if serverKeypair == nil { - t.Fatal("Server keypair is nil") - } - - idKeypair, err := NewKeypair(false) - if err != nil { - t.Fatal("Failed to generate identity keypair:", err) - } - if idKeypair == nil { - t.Fatal("Identity keypair is nil") - } - - nodeID, err := NewNodeID([]byte("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13")) - if err != nil { - t.Fatal("Failed to load NodeId:", err) - } - - // ServerHandshake - clientPublic := clientKeypair.Representative().ToPublic() - ok, serverSeed, serverAuth := ServerHandshake(clientPublic, - serverKeypair, idKeypair, nodeID) - if !ok { - t.Fatal("ServerHandshake failed") - } - if serverSeed == nil { - t.Fatal("ServerHandshake returned nil KEY_SEED") - } - if serverAuth == nil { - t.Fatal("ServerHandshake returned nil AUTH") - } - - // ClientHandshake - ok, clientSeed, clientAuth := ClientHandshake(clientKeypair, - serverKeypair.Public(), idKeypair.Public(), nodeID) - if !ok { - t.Fatal("ClientHandshake failed") - } - if clientSeed == nil { - t.Fatal("ClientHandshake returned nil KEY_SEED") - } - if clientAuth == nil { - t.Fatal("ClientHandshake returned nil AUTH") - } - - // WARNING: Use a constant time comparison in actual code. - if 0 != bytes.Compare(clientSeed.Bytes()[:], serverSeed.Bytes()[:]) { - t.Fatal("KEY_SEED mismatched between client/server") - } - if 0 != bytes.Compare(clientAuth.Bytes()[:], serverAuth.Bytes()[:]) { - t.Fatal("AUTH mismatched between client/server") - } -} - -// Benchmark Client/Server handshake. The actual time taken that will be -// observed on either the Client or Server is half the reported time per -// operation since the benchmark does both sides. -func BenchmarkHandshake(b *testing.B) { - // Generate the "long lasting" identity key and NodeId. - idKeypair, err := NewKeypair(false) - if err != nil || idKeypair == nil { - b.Fatal("Failed to generate identity keypair") - } - nodeID, err := NewNodeID([]byte("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13")) - if err != nil { - b.Fatal("Failed to load NodeId:", err) - } - b.ResetTimer() - - // Start the actual benchmark. - for i := 0; i < b.N; i++ { - // Generate the keypairs. - serverKeypair, err := NewKeypair(true) - if err != nil || serverKeypair == nil { - b.Fatal("Failed to generate server keypair") - } - - clientKeypair, err := NewKeypair(true) - if err != nil || clientKeypair == nil { - b.Fatal("Failed to generate client keypair") - } - - // Server handshake. - clientPublic := clientKeypair.Representative().ToPublic() - ok, serverSeed, serverAuth := ServerHandshake(clientPublic, - serverKeypair, idKeypair, nodeID) - if !ok || serverSeed == nil || serverAuth == nil { - b.Fatal("ServerHandshake failed") - } - - // Client handshake. - serverPublic := serverKeypair.Representative().ToPublic() - ok, clientSeed, clientAuth := ClientHandshake(clientKeypair, - serverPublic, idKeypair.Public(), nodeID) - if !ok || clientSeed == nil || clientAuth == nil { - b.Fatal("ClientHandshake failed") - } - - // Validate the authenticator. Real code would pass the AUTH read off - // the network as a slice to CompareAuth here. - if !CompareAuth(clientAuth, serverAuth.Bytes()[:]) || - !CompareAuth(serverAuth, clientAuth.Bytes()[:]) { - b.Fatal("AUTH mismatched between client/server") - } - } -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/obfs4.go b/obfs4.go deleted file mode 100644 index 4cc159c..0000000 --- a/obfs4.go +++ /dev/null @@ -1,758 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 implements the obfs4 protocol. For the most part, obfs4 -// connections are exposed via the net.Conn and net.Listener interface, though -// accepting connections as a server requires calling ServerHandshake on the -// conn to finish connection establishment. -package obfs4 - -import ( - "bytes" - "crypto/sha256" - "encoding/base64" - "fmt" - "io" - "math/rand" - "net" - "syscall" - "time" - - "git.torproject.org/pluggable-transports/obfs4.git/drbg" - "git.torproject.org/pluggable-transports/obfs4.git/framing" - "git.torproject.org/pluggable-transports/obfs4.git/ntor" -) - -const ( - // SeedLength is the length of the obfs4 polymorphism seed. - SeedLength = 32 - headerLength = framing.FrameOverhead + packetOverhead - connectionTimeout = time.Duration(30) * time.Second - - maxCloseDelayBytes = maxHandshakeLength - maxCloseDelay = 60 - - maxIatDelay = 100 -) - -type connState int - -const ( - stateInit connState = iota - stateEstablished - stateBroken - stateClosed -) - -// Obfs4Conn is the implementation of the net.Conn interface for obfs4 -// connections. -type Obfs4Conn struct { - conn net.Conn - - sessionKey *ntor.Keypair - - lenProbDist *wDist - iatProbDist *wDist - - encoder *framing.Encoder - decoder *framing.Decoder - - receiveBuffer bytes.Buffer - receiveDecodedBuffer bytes.Buffer - - state connState - isServer bool - - // Server side state. - listener *Obfs4Listener - startTime time.Time -} - -func (c *Obfs4Conn) padBurst(burst *bytes.Buffer) (err error) { - tailLen := burst.Len() % framing.MaximumSegmentLength - toPadTo := c.lenProbDist.sample() - - padLen := 0 - if toPadTo >= tailLen { - padLen = toPadTo - tailLen - } else { - padLen = (framing.MaximumSegmentLength - tailLen) + toPadTo - } - - if padLen > headerLength { - err = c.producePacket(burst, packetTypePayload, []byte{}, - uint16(padLen-headerLength)) - if err != nil { - return - } - } else if padLen > 0 { - err = c.producePacket(burst, packetTypePayload, []byte{}, - maxPacketPayloadLength) - if err != nil { - return - } - err = c.producePacket(burst, packetTypePayload, []byte{}, - uint16(padLen)) - if err != nil { - return - } - } - - return -} - -func (c *Obfs4Conn) closeAfterDelay() { - // I-it's not like I w-wanna handshake with you or anything. B-b-baka! - defer c.conn.Close() - - delay := time.Duration(c.listener.closeDelay)*time.Second + connectionTimeout - deadline := c.startTime.Add(delay) - if time.Now().After(deadline) { - return - } - - err := c.conn.SetReadDeadline(deadline) - if err != nil { - return - } - - // Consume and discard data on this connection until either the specified - // interval passes or a certain size has been reached. - discarded := 0 - var buf [framing.MaximumSegmentLength]byte - for discarded < int(c.listener.closeDelayBytes) { - n, err := c.conn.Read(buf[:]) - if err != nil { - return - } - discarded += n - } -} - -func (c *Obfs4Conn) setBroken() { - c.state = stateBroken -} - -func (c *Obfs4Conn) clientHandshake(nodeID *ntor.NodeID, publicKey *ntor.PublicKey) (err error) { - if c.isServer { - panic(fmt.Sprintf("BUG: clientHandshake() called for server connection")) - } - - defer func() { - c.sessionKey = nil - if err != nil { - c.setBroken() - } - }() - - // Generate/send the client handshake. - var hs *clientHandshake - var blob []byte - hs = newClientHandshake(nodeID, publicKey, c.sessionKey) - blob, err = hs.generateHandshake() - if err != nil { - return - } - - err = c.conn.SetDeadline(time.Now().Add(connectionTimeout * 2)) - if err != nil { - return - } - - _, err = c.conn.Write(blob) - if err != nil { - return - } - - // Consume the server handshake. - var hsBuf [maxHandshakeLength]byte - for { - var n int - n, err = c.conn.Read(hsBuf[:]) - if err != nil { - // Yes, just bail out of handshaking even if the Read could have - // returned data, no point in continuing on EOF/etc. - return - } - c.receiveBuffer.Write(hsBuf[:n]) - - var seed []byte - n, seed, err = hs.parseServerHandshake(c.receiveBuffer.Bytes()) - if err == ErrMarkNotFoundYet { - continue - } else if err != nil { - return - } - _ = c.receiveBuffer.Next(n) - - err = c.conn.SetDeadline(time.Time{}) - if err != nil { - return - } - - // Use the derived key material to intialize the link crypto. - okm := ntor.Kdf(seed, framing.KeyLength*2) - c.encoder = framing.NewEncoder(okm[:framing.KeyLength]) - c.decoder = framing.NewDecoder(okm[framing.KeyLength:]) - - c.state = stateEstablished - - return nil - } -} - -func (c *Obfs4Conn) serverHandshake(nodeID *ntor.NodeID, keypair *ntor.Keypair) (err error) { - if !c.isServer { - panic(fmt.Sprintf("BUG: serverHandshake() called for client connection")) - } - - defer func() { - c.sessionKey = nil - if err != nil { - c.setBroken() - } - }() - - hs := newServerHandshake(nodeID, keypair, c.sessionKey) - err = c.conn.SetDeadline(time.Now().Add(connectionTimeout)) - if err != nil { - return - } - - // Consume the client handshake. - var hsBuf [maxHandshakeLength]byte - for { - var n int - n, err = c.conn.Read(hsBuf[:]) - if err != nil { - // Yes, just bail out of handshaking even if the Read could have - // returned data, no point in continuing on EOF/etc. - return - } - c.receiveBuffer.Write(hsBuf[:n]) - - var seed []byte - seed, err = hs.parseClientHandshake(c.listener.filter, c.receiveBuffer.Bytes()) - if err == ErrMarkNotFoundYet { - continue - } else if err != nil { - return - } - c.receiveBuffer.Reset() - - err = c.conn.SetDeadline(time.Time{}) - if err != nil { - return - } - - // Use the derived key material to intialize the link crypto. - okm := ntor.Kdf(seed, framing.KeyLength*2) - c.encoder = framing.NewEncoder(okm[framing.KeyLength:]) - c.decoder = framing.NewDecoder(okm[:framing.KeyLength]) - - break - } - - // - // Since the current and only implementation always sends a PRNG seed for - // the length obfuscation, this makes the amount of data received from the - // server inconsistent with the length sent from the client. - // - // Rebalance this by tweaking the client mimimum padding/server maximum - // padding, and sending the PRNG seed unpadded (As in, treat the PRNG seed - // as part of the server response). See inlineSeedFrameLength in - // handshake_ntor.go. - // - - // Generate/send the response. - var blob []byte - blob, err = hs.generateHandshake() - if err != nil { - return - } - var frameBuf bytes.Buffer - _, err = frameBuf.Write(blob) - if err != nil { - return - } - c.state = stateEstablished - - // Send the PRNG seed as the first packet. - err = c.producePacket(&frameBuf, packetTypePrngSeed, c.listener.rawSeed, 0) - if err != nil { - return - } - _, err = c.conn.Write(frameBuf.Bytes()) - if err != nil { - return - } - - return -} - -// CanHandshake queries the connection state to see if it is appropriate to -// call ServerHandshake to complete connection establishment. -func (c *Obfs4Conn) CanHandshake() bool { - return c.state == stateInit -} - -// CanReadWrite queries the connection state to see if it is possible to read -// and write data. -func (c *Obfs4Conn) CanReadWrite() bool { - return c.state == stateEstablished -} - -// ServerHandshake completes the server side of the obfs4 handshake. Servers -// are required to call this after accepting a connection. ServerHandshake -// will treat errors encountered during the handshake as fatal and drop the -// connection before returning. -func (c *Obfs4Conn) ServerHandshake() error { - // Handshakes when already established are a no-op. - if c.CanReadWrite() { - return nil - } else if !c.CanHandshake() { - return syscall.EINVAL - } - - if !c.isServer { - panic(fmt.Sprintf("BUG: ServerHandshake() called for client connection")) - } - - // Complete the handshake. - err := c.serverHandshake(c.listener.nodeID, c.listener.keyPair) - if err != nil { - c.closeAfterDelay() - } - c.listener = nil - - return err -} - -// Read implements the net.Conn Read method. -func (c *Obfs4Conn) Read(b []byte) (n int, err error) { - if !c.CanReadWrite() { - return 0, syscall.EINVAL - } - - for c.receiveDecodedBuffer.Len() == 0 { - _, err = c.consumeFramedPackets(nil) - if err == framing.ErrAgain { - continue - } else if err != nil { - return - } - } - - n, err = c.receiveDecodedBuffer.Read(b) - return -} - -// WriteTo implements the io.WriterTo WriteTo method. -func (c *Obfs4Conn) WriteTo(w io.Writer) (n int64, err error) { - if !c.CanReadWrite() { - return 0, syscall.EINVAL - } - - // If there is buffered payload from earlier Read() calls, write. - wrLen := 0 - if c.receiveDecodedBuffer.Len() > 0 { - wrLen, err = w.Write(c.receiveDecodedBuffer.Bytes()) - if err != nil { - c.setBroken() - return int64(wrLen), err - } else if wrLen < int(c.receiveDecodedBuffer.Len()) { - c.setBroken() - return int64(wrLen), io.ErrShortWrite - } - c.receiveDecodedBuffer.Reset() - } - - for { - wrLen, err = c.consumeFramedPackets(w) - n += int64(wrLen) - if err == framing.ErrAgain { - continue - } else if err != nil { - // io.EOF is treated as not an error. - if err == io.EOF { - err = nil - } - break - } - } - - return -} - -// Write implements the net.Conn Write method. The obfs4 lengt obfuscation is -// done based on the amount of data passed to Write (each call to Write results -// in up to 2 frames of padding). Passing excessively short buffers to Write -// will result in significant overhead. -func (c *Obfs4Conn) Write(b []byte) (n int, err error) { - if !c.CanReadWrite() { - return 0, syscall.EINVAL - } - - defer func() { - if err != nil { - c.setBroken() - } - }() - - // TODO: Change this to write directly to c.conn skipping frameBuf. - chopBuf := bytes.NewBuffer(b) - var payload [maxPacketPayloadLength]byte - var frameBuf bytes.Buffer - - for chopBuf.Len() > 0 { - // Send maximum sized frames. - rdLen := 0 - rdLen, err = chopBuf.Read(payload[:]) - if err != nil { - return 0, err - } else if rdLen == 0 { - panic(fmt.Sprintf("BUG: Write(), chopping length was 0")) - } - n += rdLen - - err = c.producePacket(&frameBuf, packetTypePayload, payload[:rdLen], 0) - if err != nil { - return 0, err - } - } - - // Insert random padding. In theory for some padding lengths, this can be - // inlined with the payload, but doing it this way simplifies the code - // significantly. - err = c.padBurst(&frameBuf) - if err != nil { - return 0, err - } - - // Spit frame(s) onto the network. - // - // Partial writes are fatal because the frame encoder state is advanced - // at this point. It's possible to keep frameBuf around, but fuck it. - // Someone that wants write timeouts can change this. - if c.iatProbDist != nil { - var iatFrame [framing.MaximumSegmentLength]byte - for frameBuf.Len() > 0 { - iatWrLen := 0 - iatWrLen, err = frameBuf.Read(iatFrame[:]) - if err != nil { - return 0, err - } else if iatWrLen == 0 { - panic(fmt.Sprintf("BUG: Write(), iat length was 0")) - } - - // Calculate the delay. The delay resolution is 100 usec, leading - // to a maximum delay of 10 msec. - iatDelta := time.Duration(c.iatProbDist.sample() * 100) - - // Write then sleep. - _, err = c.conn.Write(iatFrame[:iatWrLen]) - if err != nil { - return 0, err - } - time.Sleep(iatDelta * time.Microsecond) - } - } else { - _, err = c.conn.Write(frameBuf.Bytes()) - if err != nil { - return 0, err - } - } - - return -} - -// Close closes the connection. -func (c *Obfs4Conn) Close() error { - if c.conn == nil { - return syscall.EINVAL - } - - c.state = stateClosed - - return c.conn.Close() -} - -// LocalAddr returns the local network address. -func (c *Obfs4Conn) LocalAddr() net.Addr { - if c.state == stateClosed { - return nil - } - - return c.conn.LocalAddr() -} - -// RemoteAddr returns the remote network address. -func (c *Obfs4Conn) RemoteAddr() net.Addr { - if c.state == stateClosed { - return nil - } - - return c.conn.RemoteAddr() -} - -// SetDeadline is a convoluted way to get syscall.ENOTSUP. -func (c *Obfs4Conn) SetDeadline(t time.Time) error { - return syscall.ENOTSUP -} - -// SetReadDeadline implements the net.Conn SetReadDeadline method. Connections -// must be in the established state (CanReadWrite). -func (c *Obfs4Conn) SetReadDeadline(t time.Time) error { - if !c.CanReadWrite() { - return syscall.EINVAL - } - - return c.conn.SetReadDeadline(t) -} - -// SetWriteDeadline is a convoluted way to get syscall.ENOTSUP. -func (c *Obfs4Conn) SetWriteDeadline(t time.Time) error { - return syscall.ENOTSUP -} - -// DialFn is a function pointer to a dial routine that matches the -// net.Dialer.Dial routine. -type DialFn func(string, string) (net.Conn, error) - -// DialObfs4 connects to the remote address on the network, and handshakes with -// the peer's obfs4 Node ID and Identity Public Key. nodeID and publicKey are -// expected as strings containing the Base64 encoded values. -func DialObfs4(network, address, nodeID, publicKey string, iatObfuscation bool) (*Obfs4Conn, error) { - - return DialObfs4DialFn(net.Dial, network, address, nodeID, publicKey, iatObfuscation) -} - -// DialObfs4DialFn connects to the remote address on the network via DialFn, -// and handshakes with the peers' obfs4 Node ID and Identity Public Key. -func DialObfs4DialFn(dialFn DialFn, network, address, nodeID, publicKey string, iatObfuscation bool) (*Obfs4Conn, error) { - // Decode the node_id/public_key. - pub, err := ntor.PublicKeyFromBase64(publicKey) - if err != nil { - return nil, err - } - id, err := ntor.NodeIDFromBase64(nodeID) - if err != nil { - return nil, err - } - - // Generate the initial length obfuscation distribution. - seed, err := drbg.NewSeed() - if err != nil { - return nil, err - } - - // Generate the Obfs4Conn. - c := new(Obfs4Conn) - c.lenProbDist = newWDist(seed, 0, framing.MaximumSegmentLength) - if iatObfuscation { - iatSeedSrc := sha256.Sum256(seed.Bytes()[:]) - iatSeed, err := drbg.SeedFromBytes(iatSeedSrc[:]) - if err != nil { - return nil, err - } - c.iatProbDist = newWDist(iatSeed, 0, maxIatDelay) - } - - // Generate the session keypair *before* connecting to the remote peer. - c.sessionKey, err = ntor.NewKeypair(true) - if err != nil { - return nil, err - } - - // Connect to the remote peer. - c.conn, err = dialFn(network, address) - if err != nil { - return nil, err - } - - // Handshake. - err = c.clientHandshake(id, pub) - if err != nil { - c.conn.Close() - return nil, err - } - - return c, nil -} - -// Obfs4Listener is the implementation of the net.Listener interface for obfs4 -// connections. -type Obfs4Listener struct { - listener net.Listener - - filter *replayFilter - - keyPair *ntor.Keypair - nodeID *ntor.NodeID - - rawSeed []byte - seed *drbg.Seed - iatSeed *drbg.Seed - iatObfuscation bool - - closeDelayBytes int - closeDelay int -} - -// Accept implements the Accept method of the net.Listener interface; it waits -// for the next call and returns a generic net.Conn. Callers are responsible -// for completing the handshake by calling Obfs4Conn.ServerHandshake(). -func (l *Obfs4Listener) Accept() (net.Conn, error) { - conn, err := l.AcceptObfs4() - if err != nil { - return nil, err - } - - return conn, nil -} - -// AcceptObfs4 accepts the next incoming call and returns a new connection. -// Callers are responsible for completing the handshake by calling -// Obfs4Conn.ServerHandshake(). -func (l *Obfs4Listener) AcceptObfs4() (*Obfs4Conn, error) { - // Accept a connection. - c, err := l.listener.Accept() - if err != nil { - return nil, err - } - - // Allocate the obfs4 connection state. - cObfs := new(Obfs4Conn) - - // Generate the session keypair *before* consuming data from the peer, to - // add more noise to the keypair generation time. The idea is that jitter - // here is masked by network latency (the time it takes for a server to - // accept a socket out of the backlog should not be fixed, and the client - // needs to send the public key). - cObfs.sessionKey, err = ntor.NewKeypair(true) - if err != nil { - return nil, err - } - - cObfs.conn = c - cObfs.isServer = true - cObfs.listener = l - cObfs.lenProbDist = newWDist(l.seed, 0, framing.MaximumSegmentLength) - if l.iatObfuscation { - cObfs.iatProbDist = newWDist(l.iatSeed, 0, maxIatDelay) - } - if err != nil { - c.Close() - return nil, err - } - cObfs.startTime = time.Now() - - return cObfs, nil -} - -// Close stops listening on the Obfs4 endpoint. Already Accepted connections -// are not closed. -func (l *Obfs4Listener) Close() error { - return l.listener.Close() -} - -// Addr returns the listener's network address. -func (l *Obfs4Listener) Addr() net.Addr { - return l.listener.Addr() -} - -// PublicKey returns the listener's Identity Public Key, a Base64 encoded -// obfs4.ntor.PublicKey. -func (l *Obfs4Listener) PublicKey() string { - if l.keyPair == nil { - return "" - } - - return l.keyPair.Public().Base64() -} - -// NodeID returns the listener's NodeID, a Base64 encoded obfs4.ntor.NodeID. -func (l *Obfs4Listener) NodeID() string { - if l.nodeID == nil { - return "" - } - - return l.nodeID.Base64() -} - -// ListenObfs4 annnounces on the network and address, and returns and -// Obfs4Listener. nodeId, privateKey and seed are expected as strings -// containing the Base64 encoded values. -func ListenObfs4(network, laddr, nodeID, privateKey, seed string, iatObfuscation bool) (*Obfs4Listener, error) { - var err error - - // Decode node_id/private_key. - l := new(Obfs4Listener) - l.keyPair, err = ntor.KeypairFromBase64(privateKey) - if err != nil { - return nil, err - } - l.nodeID, err = ntor.NodeIDFromBase64(nodeID) - if err != nil { - return nil, err - } - l.rawSeed, err = base64.StdEncoding.DecodeString(seed) - if err != nil { - return nil, err - } - l.seed, err = drbg.SeedFromBytes(l.rawSeed) - if err != nil { - return nil, err - } - l.iatObfuscation = iatObfuscation - if l.iatObfuscation { - iatSeedSrc := sha256.Sum256(l.seed.Bytes()[:]) - l.iatSeed, err = drbg.SeedFromBytes(iatSeedSrc[:]) - if err != nil { - return nil, err - } - } - - l.filter, err = newReplayFilter() - if err != nil { - return nil, err - } - - rng := rand.New(drbg.NewHashDrbg(l.seed)) - l.closeDelayBytes = rng.Intn(maxCloseDelayBytes) - l.closeDelay = rng.Intn(maxCloseDelay) - - // Start up the listener. - l.listener, err = net.Listen(network, laddr) - if err != nil { - return nil, err - } - - return l, nil -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/obfs4proxy/obfs4proxy.go b/obfs4proxy/obfs4proxy.go index c49f3d0..d3490bf 100644 --- a/obfs4proxy/obfs4proxy.go +++ b/obfs4proxy/obfs4proxy.go @@ -23,31 +23,13 @@ * 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. - * - * This file is based off goptlib's dummy-[client,server].go files. */ -// obfs4 pluggable transport. Works only as a managed proxy. -// -// Client usage (in torrc): -// UseBridges 1 -// Bridge obfs4 X.X.X.X:YYYY <Fingerprint> public-key=<Base64 Bridge Public Key> node-id=<Base64 Bridge Node ID> -// ClientTransportPlugin obfs4 exec obfs4proxy -// -// Server usage (in torrc): -// BridgeRelay 1 -// ORPort 9001 -// ExtORPort 6669 -// ServerTransportPlugin obfs4 exec obfs4proxy -// ServerTransportOptions obfs4 private-key=<Base64 Bridge Private Key> node-id=<Base64 Node ID> drbg-seed=<Base64 DRBG Seed> -// -// Because the pluggable transport requires arguments, obfs4proxy requires -// tor-0.2.5.x to be useful. +// Go language Tor Pluggable Transport suite. Works only as a managed +// client/server. package main import ( - "encoding/base64" - "encoding/hex" "flag" "fmt" "io" @@ -61,292 +43,307 @@ import ( "sync" "syscall" + "code.google.com/p/go.net/proxy" + "git.torproject.org/pluggable-transports/goptlib.git" - "git.torproject.org/pluggable-transports/obfs4.git" - "git.torproject.org/pluggable-transports/obfs4.git/csrand" - "git.torproject.org/pluggable-transports/obfs4.git/ntor" + "git.torproject.org/pluggable-transports/obfs4.git/transports" + "git.torproject.org/pluggable-transports/obfs4.git/transports/base" ) const ( - obfs4Method = "obfs4" - obfs4LogFile = "obfs4proxy.log" + obfs4proxyLogFile = "obfs4proxy.log" + socksAddr = "127.0.0.1:0" + elidedAddr = "[scrubbed]" ) var enableLogging bool var unsafeLogging bool -var iatObfuscation bool -var ptListeners []net.Listener +var stateDir string +var handlerChan chan int -// When a connection handler starts, +1 is written to this channel; when it -// ends, -1 is written. -var handlerChan = make(chan int) +// DialFn is a function pointer to a function that matches the net.Dialer.Dial +// interface. +type DialFn func(string, string) (net.Conn, error) -func logAndRecover(conn *obfs4.Obfs4Conn) { - if err := recover(); err != nil { - log.Printf("[ERROR] %p: Panic: %s", conn, err) +func elideAddr(addrStr string) string { + if unsafeLogging { + return addrStr } + + if addr, err := resolveAddrStr(addrStr); err == nil { + // Only scrub off the address so that it's slightly easier to follow + // the logs by looking at the port. + return fmt.Sprintf("%s:%d", elidedAddr, addr.Port) + } + + return elidedAddr } -func copyLoop(a net.Conn, b *obfs4.Obfs4Conn) { - var wg sync.WaitGroup - wg.Add(2) +func clientSetup() (launched bool, listeners []net.Listener) { + ptClientInfo, err := pt.ClientSetup(transports.Transports()) + if err != nil { + log.Fatal(err) + } - go func() { - defer logAndRecover(b) - defer wg.Done() - defer b.Close() - defer a.Close() + ptClientProxy, err := ptGetProxy() + if err != nil { + log.Fatal(err) + } else if ptClientProxy != nil { + ptProxyDone() + } - _, err := io.Copy(b, a) - if err != nil { - log.Printf("[WARN] copyLoop: %p: Connection closed: %s", b, err) + // Launch each of the client listeners. + for _, name := range ptClientInfo.MethodNames { + t := transports.Get(name) + if t == nil { + pt.CmethodError(name, "no such transport is supported") + continue } - }() - go func() { - defer logAndRecover(b) - defer wg.Done() - defer a.Close() - defer b.Close() - _, err := io.Copy(a, b) + f, err := t.ClientFactory(stateDir) if err != nil { - log.Printf("[WARN] copyLoop: %p: Connection closed: %s", b, err) + pt.CmethodError(name, "failed to get ClientFactory") + continue } - }() - - wg.Wait() -} - -func serverHandler(conn *obfs4.Obfs4Conn, info *pt.ServerInfo) error { - defer conn.Close() - defer logAndRecover(conn) - - handlerChan <- 1 - defer func() { - handlerChan <- -1 - }() - var addr string - if unsafeLogging { - addr = conn.RemoteAddr().String() - } else { - addr = "[scrubbed]" - } + ln, err := pt.ListenSocks("tcp", socksAddr) + if err != nil { + pt.CmethodError(name, err.Error()) + continue + } - log.Printf("[INFO] server: %p: New connection from %s", conn, addr) + go clientAcceptLoop(f, ln, ptClientProxy) + pt.Cmethod(name, ln.Version(), ln.Addr()) - // Handshake with the client. - err := conn.ServerHandshake() - if err != nil { - log.Printf("[WARN] server: %p: Handshake failed: %s", conn, err) - return err - } + log.Printf("[INFO]: %s - registered listener: %s", name, ln.Addr()) - or, err := pt.DialOr(info, conn.RemoteAddr().String(), obfs4Method) - if err != nil { - log.Printf("[ERROR] server: %p: DialOr failed: %s", conn, err) - return err + listeners = append(listeners, ln) + launched = true } - defer or.Close() - - copyLoop(or, conn) + pt.CmethodsDone() - return nil + return } -func serverAcceptLoop(ln *obfs4.Obfs4Listener, info *pt.ServerInfo) error { +func clientAcceptLoop(f base.ClientFactory, ln *pt.SocksListener, proxyURI *url.URL) error { defer ln.Close() for { - conn, err := ln.AcceptObfs4() + conn, err := ln.AcceptSocks() if err != nil { if e, ok := err.(net.Error); ok && !e.Temporary() { return err } continue } - go serverHandler(conn, info) + go clientHandler(f, conn, proxyURI) } } -func serverSetup() (launched bool) { - // Initialize pt logging. - err := ptInitializeLogging(enableLogging) +func clientHandler(f base.ClientFactory, conn *pt.SocksConn, proxyURI *url.URL) { + defer conn.Close() + handlerChan <- 1 + defer func() { + handlerChan <- -1 + }() + + name := f.Transport().Name() + addrStr := elideAddr(conn.Req.Target) + log.Printf("[INFO]: %s(%s) - new connection", name, addrStr) + + // Deal with arguments. + args, err := f.ParseArgs(&conn.Req.Args) if err != nil { + log.Printf("[ERROR]: %s(%s) - invalid arguments: %s", name, addrStr, err) + conn.Reject() return } - ptServerInfo, err := pt.ServerSetup([]string{obfs4Method}) + // Obtain the proxy dialer if any, and create the outgoing TCP connection. + var dialFn DialFn + if proxyURI == nil { + dialFn = proxy.Direct.Dial + } else { + // This is unlikely to happen as the proxy protocol is verified during + // the configuration phase. + dialer, err := proxy.FromURL(proxyURI, proxy.Direct) + if err != nil { + log.Printf("[ERROR]: %s(%s) - failed to obtain proxy dialer: %s", name, addrStr, err) + conn.Reject() + return + } + dialFn = dialer.Dial + } + remoteConn, err := dialFn("tcp", conn.Req.Target) // XXX: Allow UDP? if err != nil { + // Note: The error message returned from the dialer can include the IP + // address/port of the remote peer. + if unsafeLogging { + log.Printf("[ERROR]: %s(%s) - outgoing connection failed: %s", name, addrStr, err) + } else { + log.Printf("[ERROR]: %s(%s) - outgoing connection failed", name, addrStr) + } + conn.Reject() return } + defer remoteConn.Close() - for _, bindaddr := range ptServerInfo.Bindaddrs { - switch bindaddr.MethodName { - case obfs4Method: - // Handle the mandetory arguments. - privateKey, ok := bindaddr.Options.Get("private-key") - if !ok { - pt.SmethodError(bindaddr.MethodName, "needs a private-key option") - break - } - nodeID, ok := bindaddr.Options.Get("node-id") - if !ok { - pt.SmethodError(bindaddr.MethodName, "needs a node-id option") - break - } - seed, ok := bindaddr.Options.Get("drbg-seed") - if !ok { - pt.SmethodError(bindaddr.MethodName, "needs a drbg-seed option") - break - } - - // Initialize the listener. - ln, err := obfs4.ListenObfs4("tcp", bindaddr.Addr.String(), nodeID, - privateKey, seed, iatObfuscation) - if err != nil { - pt.SmethodError(bindaddr.MethodName, err.Error()) - break - } + // Instantiate the client transport method, handshake, and start pushing + // bytes back and forth. + remote, err := f.WrapConn(remoteConn, args) + if err != nil { + log.Printf("[ERROR]: %s(%s) - handshake failed: %s", name, addrStr, err) + conn.Reject() + return + } + err = conn.Grant(remoteConn.RemoteAddr().(*net.TCPAddr)) + if err != nil { + log.Printf("[ERROR]: %s(%s) - SOCKS grant failed: %s", name, addrStr, err) + return + } - // Report the SMETHOD including the parameters. - args := pt.Args{} - args.Add("node-id", nodeID) - args.Add("public-key", ln.PublicKey()) - go serverAcceptLoop(ln, &ptServerInfo) - pt.SmethodArgs(bindaddr.MethodName, ln.Addr(), args) - ptListeners = append(ptListeners, ln) - launched = true - default: - pt.SmethodError(bindaddr.MethodName, "no such method") - } + err = copyLoop(conn, remote) + if err != nil { + log.Printf("[INFO]: %s(%s) - closed connection: %s", name, addrStr, err) + } else { + log.Printf("[INFO]: %s(%s) - closed connection", name, addrStr) } - pt.SmethodsDone() return } -func clientHandler(conn *pt.SocksConn, proxyURI *url.URL) error { - defer conn.Close() - - var addr string - if unsafeLogging { - addr = conn.Req.Target - } else { - addr = "[scrubbed]" +func serverSetup() (launched bool, listeners []net.Listener) { + ptServerInfo, err := pt.ServerSetup(transports.Transports()) + if err != nil { + log.Fatal(err) } - log.Printf("[INFO] client: New connection to %s", addr) + for _, bindaddr := range ptServerInfo.Bindaddrs { + name := bindaddr.MethodName + t := transports.Get(name) + if t == nil { + pt.SmethodError(name, "no such transport is supported") + continue + } - // Extract the peer's node ID and public key. - nodeID, ok := conn.Req.Args.Get("node-id") - if !ok { - log.Printf("[ERROR] client: missing node-id argument") - conn.Reject() - return nil - } - publicKey, ok := conn.Req.Args.Get("public-key") - if !ok { - log.Printf("[ERROR] client: missing public-key argument") - conn.Reject() - return nil - } + f, err := t.ServerFactory(stateDir, &bindaddr.Options) + if err != nil { + pt.SmethodError(name, err.Error()) + continue + } - handlerChan <- 1 - defer func() { - handlerChan <- -1 - }() + ln, err := net.ListenTCP("tcp", bindaddr.Addr) + if err != nil { + pt.SmethodError(name, err.Error()) + } - defer logAndRecover(nil) - dialFn, err := getProxyDialer(proxyURI) - if err != nil { - log.Printf("[ERROR] client: failed to get proxy dialer: %s", err) - conn.Reject() - return err - } - remote, err := obfs4.DialObfs4DialFn(dialFn, "tcp", conn.Req.Target, nodeID, publicKey, iatObfuscation) - if err != nil { - log.Printf("[ERROR] client: %p: Handshake failed: %s", remote, err) - conn.Reject() - return err - } - defer remote.Close() - err = conn.Grant(remote.RemoteAddr().(*net.TCPAddr)) - if err != nil { - return err - } + go serverAcceptLoop(f, ln, &ptServerInfo) + if args := f.Args(); args != nil { + pt.SmethodArgs(name, ln.Addr(), *args) + } else { + pt.SmethodArgs(name, ln.Addr(), nil) + } - copyLoop(conn, remote) + log.Printf("[INFO]: %s - registered listener: %s", name, elideAddr(ln.Addr().String())) - return nil + listeners = append(listeners, ln) + launched = true + } + pt.SmethodsDone() + + return } -func clientAcceptLoop(ln *pt.SocksListener, proxyURI *url.URL) error { +func serverAcceptLoop(f base.ServerFactory, ln net.Listener, info *pt.ServerInfo) error { defer ln.Close() for { - conn, err := ln.AcceptSocks() + conn, err := ln.Accept() if err != nil { if e, ok := err.(net.Error); ok && !e.Temporary() { return err } continue } - go clientHandler(conn, proxyURI) + go serverHandler(f, conn, info) } } -func clientSetup() (launched bool) { - // Initialize pt logging. - err := ptInitializeLogging(enableLogging) +func serverHandler(f base.ServerFactory, conn net.Conn, info *pt.ServerInfo) { + defer conn.Close() + handlerChan <- 1 + defer func() { + handlerChan <- -1 + }() + + name := f.Transport().Name() + addrStr := elideAddr(conn.RemoteAddr().String()) + log.Printf("[INFO]: %s(%s) - new connection", name, addrStr) + + // Instantiate the server transport method and handshake. + remote, err := f.WrapConn(conn) if err != nil { + log.Printf("[ERROR]: %s(%s) - handshake failed: %s", name, addrStr, err) return } - ptClientInfo, err := pt.ClientSetup([]string{obfs4Method}) + // Connect to the orport. + orConn, err := pt.DialOr(info, conn.RemoteAddr().String(), name) if err != nil { - log.Fatal(err) + log.Printf("[ERROR]: %s(%s) - failed to connect to ORPort: %s", name, addrStr, err) + return } + defer orConn.Close() - ptClientProxy, err := ptGetProxy() + err = copyLoop(orConn, remote) if err != nil { - log.Fatal(err) - } else if ptClientProxy != nil { - ptProxyDone() + log.Printf("[INFO]: %s(%s) - closed connection: %s", name, addrStr, err) + } else { + log.Printf("[INFO]: %s(%s) - closed connection", name, addrStr) } - for _, methodName := range ptClientInfo.MethodNames { - switch methodName { - case obfs4Method: - ln, err := pt.ListenSocks("tcp", "127.0.0.1:0") - if err != nil { - pt.CmethodError(methodName, err.Error()) - break - } - go clientAcceptLoop(ln, ptClientProxy) - pt.Cmethod(methodName, ln.Version(), ln.Addr()) - ptListeners = append(ptListeners, ln) - launched = true - default: - pt.CmethodError(methodName, "no such method") - } + return +} + +func copyLoop(a net.Conn, b net.Conn) error { + // Note: b is always the pt connection. a is the SOCKS/ORPort connection. + errChan := make(chan error, 2) + + var wg sync.WaitGroup + wg.Add(2) + + go func() { + defer wg.Done() + defer b.Close() + defer a.Close() + _, err := io.Copy(b, a) + errChan <- err + }() + go func() { + defer wg.Done() + defer a.Close() + defer b.Close() + _, err := io.Copy(a, b) + errChan <- err + }() + + // Wait for both upstream and downstream to close. Since one side + // terminating closes the other, the second error in the channel will be + // something like EINVAL (though io.Copy() will swallow EOF), so only the + // first error is returned. + wg.Wait() + if len(errChan) > 0 { + return <-errChan } - pt.CmethodsDone() - return + return nil } func ptInitializeLogging(enable bool) error { if enable { - // pt.MakeStateDir will ENV-ERROR for us. - dir, err := pt.MakeStateDir() - if err != nil { - return err - } - // While we could just exit, log an ENV-ERROR so it will propagate to // the tor log. - f, err := os.OpenFile(path.Join(dir, obfs4LogFile), os.O_CREATE|os.O_APPEND|os.O_WRONLY, 0600) + f, err := os.OpenFile(path.Join(stateDir, obfs4proxyLogFile), os.O_CREATE|os.O_APPEND|os.O_WRONLY, 0600) if err != nil { - return ptEnvError(fmt.Sprintf("Failed to open log file: %s\n", err)) + return ptEnvError(fmt.Sprintf("failed to open log file: %s\n", err)) } log.SetOutput(f) } else { @@ -356,122 +353,74 @@ func ptInitializeLogging(enable bool) error { return nil } -func generateServerParams(id string) { - idIsFP := id != "" - var rawID []byte - - if idIsFP { - var err error - rawID, err = hex.DecodeString(id) - if err != nil { - fmt.Println("Failed to hex decode id:", err) - return - } - } else { - rawID = make([]byte, ntor.NodeIDLength) - err := csrand.Bytes(rawID) - if err != nil { - fmt.Println("Failed to generate random node-id:", err) - return - } - } - parsedID, err := ntor.NewNodeID(rawID) - if err != nil { - fmt.Println("Failed to parse id:", err) - return - } - - fmt.Println("Generated node-id:", parsedID.Base64()) - - keypair, err := ntor.NewKeypair(false) - if err != nil { - fmt.Println("Failed to generate keypair:", err) - return - } - - seed := make([]byte, obfs4.SeedLength) - err = csrand.Bytes(seed) - if err != nil { - fmt.Println("Failed to generate DRBG seed:", err) - return - } - seedBase64 := base64.StdEncoding.EncodeToString(seed) - - fmt.Println("Generated private-key:", keypair.Private().Base64()) - fmt.Println("Generated public-key:", keypair.Public().Base64()) - fmt.Println("Generated drbg-seed:", seedBase64) - fmt.Println() - fmt.Println("Client config: ") - if idIsFP { - fmt.Printf(" Bridge obfs4 <IP Address:Port> %s node-id=%s public-key=%s\n", - id, parsedID.Base64(), keypair.Public().Base64()) - } else { - fmt.Printf(" Bridge obfs4 <IP Address:Port> <Fingerprint> node-id=%s public-key=%s\n", - parsedID.Base64(), keypair.Public().Base64()) - } - fmt.Println() - fmt.Println("Server config:") - fmt.Printf(" ServerTransportOptions obfs4 node-id=%s private-key=%s drbg-seed=%s\n", - parsedID.Base64(), keypair.Private().Base64(), seedBase64) -} - func main() { - // Some command line args. - genParams := flag.Bool("genServerParams", false, "Generate Bridge operator torrc parameters") - genParamsFP := flag.String("genServerParamsFP", "", "Optional bridge fingerprint for genServerParams") - flag.BoolVar(&enableLogging, "enableLogging", false, "Log to TOR_PT_STATE_LOCATION/obfs4proxy.log") - flag.BoolVar(&iatObfuscation, "iatObfuscation", false, "Enable IAT obufscation (EXPENSIVE)") + // Handle the command line arguments. + _, execName := path.Split(os.Args[0]) + flag.BoolVar(&enableLogging, "enableLogging", false, "Log to TOR_PT_STATE_LOCATION/"+obfs4proxyLogFile) flag.BoolVar(&unsafeLogging, "unsafeLogging", false, "Disable the address scrubber") flag.Parse() - if *genParams { - generateServerParams(*genParamsFP) - return - } - // Go through the pt protocol and initialize client or server mode. + // Determine if this is a client or server, initialize logging, and finish + // the pt configuration. + var ptListeners []net.Listener + handlerChan = make(chan int) launched := false isClient, err := ptIsClient() if err != nil { - log.Fatal("[ERROR] obfs4proxy must be run as a managed transport or server") - } else if isClient { - launched = clientSetup() + log.Fatalf("[ERROR]: %s - must be run as a managed transport", execName) + } + if stateDir, err = pt.MakeStateDir(); err != nil { + log.Fatalf("[ERROR]: %s - No state directory: %s", execName, err) + } + if err = ptInitializeLogging(enableLogging); err != nil { + log.Fatalf("[ERROR]: %s - failed to initialize logging", execName) + } + if isClient { + log.Printf("[INFO]: %s - initializing client transport listeners", execName) + launched, ptListeners = clientSetup() } else { - launched = serverSetup() + log.Printf("[INFO]: %s - initializing server transport listeners", execName) + launched, ptListeners = serverSetup() } if !launched { - // Something must have failed in client/server setup, just bail. + // Initialization failed, the client or server setup routines should + // have logged, so just exit here. os.Exit(-1) } - log.Println("[INFO] obfs4proxy - Launched and listening") + log.Printf("[INFO]: %s - launched and accepting connections", execName) defer func() { - log.Println("[INFO] obfs4proxy - Terminated") + log.Printf("[INFO]: %s - terminated", execName) }() - // Handle termination notification. - numHandlers := 0 - var sig os.Signal + // At this point, the pt config protocol is finished, and incoming + // connections will be processed. Per the pt spec, on sane platforms + // termination is signaled via SIGINT (or SIGTERM), so wait on tor to + // request a shutdown of some sort. + sigChan := make(chan os.Signal, 1) signal.Notify(sigChan, syscall.SIGINT, syscall.SIGTERM) - // wait for first signal - sig = nil + // Wait for the first SIGINT (close listeners). + var sig os.Signal + numHandlers := 0 for sig == nil { select { case n := <-handlerChan: numHandlers += n case sig = <-sigChan: + if sig == syscall.SIGTERM { + // SIGTERM causes immediate termination. + return + } } } for _, ln := range ptListeners { ln.Close() } - if sig == syscall.SIGTERM { - return - } - - // wait for second signal or no more handlers + // Wait for the 2nd SIGINT (or a SIGTERM), or for all current sessions to + // finish. sig = nil for sig == nil && numHandlers != 0 { select { @@ -481,5 +430,3 @@ func main() { } } } - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/obfs4proxy/proxy_extras.go b/obfs4proxy/proxy_extras.go deleted file mode 100644 index 5ead3b8..0000000 --- a/obfs4proxy/proxy_extras.go +++ /dev/null @@ -1,51 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 main - -import ( - "net/url" - - "code.google.com/p/go.net/proxy" - - "git.torproject.org/pluggable-transports/obfs4.git" -) - -// getProxyDialer is a trival wrapper around the go.net/proxy package to avoid -// having it as a dependency for anything else. -func getProxyDialer(uri *url.URL) (obfs4.DialFn, error) { - if uri == nil { - return proxy.Direct.Dial, nil - } - - dialer, err := proxy.FromURL(uri, proxy.Direct) - if err != nil { - return nil, err - } - - return dialer.Dial, nil -} diff --git a/obfs4proxy/proxy_http.go b/obfs4proxy/proxy_http.go index c7b926a..2db6ca0 100644 --- a/obfs4proxy/proxy_http.go +++ b/obfs4proxy/proxy_http.go @@ -108,7 +108,6 @@ func (s *httpProxy) Dial(network, addr string) (net.Conn, error) { return conn, nil } -// httpConn is the mountain of bullshit we need to do just for staleReader. type httpConn struct { remoteAddr *net.TCPAddr httpConn *httputil.ClientConn @@ -157,5 +156,3 @@ func (c *httpConn) SetWriteDeadline(t time.Time) error { func init() { proxy.RegisterDialerType("http", newHTTP) } - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/obfs4proxy/proxy_socks4.go b/obfs4proxy/proxy_socks4.go index 95cc7b6..9d6bd4d 100644 --- a/obfs4proxy/proxy_socks4.go +++ b/obfs4proxy/proxy_socks4.go @@ -162,5 +162,3 @@ func init() { // Despite the scheme name, this really is SOCKS4. proxy.RegisterDialerType("socks4a", newSOCKS4) } - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/obfs4proxy/pt_extras.go b/obfs4proxy/pt_extras.go index 2d09cc3..9eddd26 100644 --- a/obfs4proxy/pt_extras.go +++ b/obfs4proxy/pt_extras.go @@ -124,7 +124,7 @@ func ptGetProxy() (*url.URL, error) { return nil, ptProxyError(fmt.Sprintf("proxy URI has invalid scheme: %s", spec.Scheme)) } - err = validateAddrStr(spec.Host) + _, err = resolveAddrStr(spec.Host) if err != nil { return nil, ptProxyError(fmt.Sprintf("proxy URI has invalid host: %s", err)) } @@ -135,27 +135,26 @@ func ptGetProxy() (*url.URL, error) { // Sigh, pt.resolveAddr() isn't exported. Include our own getto version that // doesn't work around #7011, because we don't work with pre-0.2.5.x tor, and // all we care about is validation anyway. -func validateAddrStr(addrStr string) error { +func resolveAddrStr(addrStr string) (*net.TCPAddr, error) { ipStr, portStr, err := net.SplitHostPort(addrStr) if err != nil { - return err + return nil, err } if ipStr == "" { - return net.InvalidAddrError(fmt.Sprintf("address string %q lacks a host part", addrStr)) + return nil, net.InvalidAddrError(fmt.Sprintf("address string %q lacks a host part", addrStr)) } if portStr == "" { - return net.InvalidAddrError(fmt.Sprintf("address string %q lacks a port part", addrStr)) + return nil, net.InvalidAddrError(fmt.Sprintf("address string %q lacks a port part", addrStr)) } - if net.ParseIP(ipStr) == nil { - return net.InvalidAddrError(fmt.Sprintf("not an IP string: %q", ipStr)) + ip := net.ParseIP(ipStr) + if ip == nil { + return nil, net.InvalidAddrError(fmt.Sprintf("not an IP string: %q", ipStr)) } - _, err = strconv.ParseUint(portStr, 10, 16) + port, err := strconv.ParseUint(portStr, 10, 16) if err != nil { - return net.InvalidAddrError(fmt.Sprintf("not a Port string: %q", portStr)) + return nil, net.InvalidAddrError(fmt.Sprintf("not a Port string: %q", portStr)) } - return nil + return &net.TCPAddr{IP: ip, Port: int(port), Zone: ""}, nil } - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/packet.go b/packet.go deleted file mode 100644 index 58a5877..0000000 --- a/packet.go +++ /dev/null @@ -1,212 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ( - "crypto/sha256" - "encoding/binary" - "fmt" - "io" - "syscall" - - "git.torproject.org/pluggable-transports/obfs4.git/drbg" - "git.torproject.org/pluggable-transports/obfs4.git/framing" -) - -const ( - packetOverhead = 2 + 1 - maxPacketPayloadLength = framing.MaximumFramePayloadLength - packetOverhead - maxPacketPaddingLength = maxPacketPayloadLength - seedPacketPayloadLength = SeedLength - - consumeReadSize = framing.MaximumSegmentLength * 16 -) - -const ( - packetTypePayload = iota - packetTypePrngSeed -) - -// InvalidPacketLengthError is the error returned when decodePacket detects a -// invalid packet length/ -type InvalidPacketLengthError int - -func (e InvalidPacketLengthError) Error() string { - return fmt.Sprintf("packet: Invalid packet length: %d", int(e)) -} - -// InvalidPayloadLengthError is the error returned when decodePacket rejects the -// payload length. -type InvalidPayloadLengthError int - -func (e InvalidPayloadLengthError) Error() string { - return fmt.Sprintf("packet: Invalid payload length: %d", int(e)) -} - -var zeroPadBytes [maxPacketPaddingLength]byte - -func (c *Obfs4Conn) producePacket(w io.Writer, pktType uint8, data []byte, padLen uint16) (err error) { - var pkt [framing.MaximumFramePayloadLength]byte - - if !c.CanReadWrite() { - return syscall.EINVAL - } - - if len(data)+int(padLen) > maxPacketPayloadLength { - panic(fmt.Sprintf("BUG: makePacket() len(data) + padLen > maxPacketPayloadLength: %d + %d > %d", - len(data), padLen, maxPacketPayloadLength)) - } - - defer func() { - if err != nil { - c.setBroken() - } - }() - - // Packets are: - // uint8_t type packetTypePayload (0x00) - // uint16_t length Length of the payload (Big Endian). - // uint8_t[] payload Data payload. - // uint8_t[] padding Padding. - pkt[0] = pktType - binary.BigEndian.PutUint16(pkt[1:], uint16(len(data))) - if len(data) > 0 { - copy(pkt[3:], data[:]) - } - copy(pkt[3+len(data):], zeroPadBytes[:padLen]) - - pktLen := packetOverhead + len(data) + int(padLen) - - // Encode the packet in an AEAD frame. - var frame [framing.MaximumSegmentLength]byte - frameLen := 0 - frameLen, err = c.encoder.Encode(frame[:], pkt[:pktLen]) - if err != nil { - // All encoder errors are fatal. - return - } - var wrLen int - wrLen, err = w.Write(frame[:frameLen]) - if err != nil { - return - } else if wrLen < frameLen { - err = io.ErrShortWrite - return - } - - return -} - -func (c *Obfs4Conn) consumeFramedPackets(w io.Writer) (n int, err error) { - if !c.CanReadWrite() { - return n, syscall.EINVAL - } - - var buf [consumeReadSize]byte - rdLen, rdErr := c.conn.Read(buf[:]) - c.receiveBuffer.Write(buf[:rdLen]) - var decoded [framing.MaximumFramePayloadLength]byte - for c.receiveBuffer.Len() > 0 { - // Decrypt an AEAD frame. - decLen := 0 - decLen, err = c.decoder.Decode(decoded[:], &c.receiveBuffer) - if err == framing.ErrAgain { - break - } else if err != nil { - break - } else if decLen < packetOverhead { - err = InvalidPacketLengthError(decLen) - break - } - - // Decode the packet. - pkt := decoded[0:decLen] - pktType := pkt[0] - payloadLen := binary.BigEndian.Uint16(pkt[1:]) - if int(payloadLen) > len(pkt)-packetOverhead { - err = InvalidPayloadLengthError(int(payloadLen)) - break - } - payload := pkt[3 : 3+payloadLen] - - switch pktType { - case packetTypePayload: - if payloadLen > 0 { - if w != nil { - // c.WriteTo() skips buffering in c.receiveDecodedBuffer - var wrLen int - wrLen, err = w.Write(payload) - n += wrLen - if err != nil { - break - } else if wrLen < int(payloadLen) { - err = io.ErrShortWrite - break - } - } else { - // c.Read() stashes decoded payload in receiveDecodedBuffer - c.receiveDecodedBuffer.Write(payload) - n += int(payloadLen) - } - } - case packetTypePrngSeed: - // Only regenerate the distribution if we are the client. - if len(payload) == seedPacketPayloadLength && !c.isServer { - var seed *drbg.Seed - seed, err = drbg.SeedFromBytes(payload) - if err != nil { - break - } - c.lenProbDist.reset(seed) - if c.iatProbDist != nil { - iatSeedSrc := sha256.Sum256(seed.Bytes()[:]) - iatSeed, err := drbg.SeedFromBytes(iatSeedSrc[:]) - if err != nil { - break - } - c.iatProbDist.reset(iatSeed) - } - } - default: - // Ignore unrecognised packet types. - } - } - - // Read errors and non-framing.ErrAgain errors are all fatal. - if (err != nil && err != framing.ErrAgain) || rdErr != nil { - // Propagate read errors correctly. - if err == nil && rdErr != nil { - err = rdErr - } - c.setBroken() - } - - return -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/replay_filter.go b/replay_filter.go deleted file mode 100644 index b8f284a..0000000 --- a/replay_filter.go +++ /dev/null @@ -1,145 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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" - "encoding/binary" - "sync" - - "github.com/dchest/siphash" - - "git.torproject.org/pluggable-transports/obfs4.git/csrand" -) - -// 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 = csrand.Bytes(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. This method is threadsafe. -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. This -// method is NOT threadsafe. -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.reset() - 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() - delete(f.filter, entry.hash) - f.fifo.Remove(entry.element) - entry.element = nil - e = eNext - } -} - -// reset purges the entire filter. This methoid is NOT threadsafe. -func (f *replayFilter) reset() { - f.filter = make(map[uint64]*filterEntry) - f.fifo = list.New() -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/replay_filter_test.go b/replay_filter_test.go deleted file mode 100644 index 09337c0..0000000 --- a/replay_filter_test.go +++ /dev/null @@ -1,92 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ( - "testing" -) - -func TestReplayFilter(t *testing.T) { - f, err := newReplayFilter() - if err != nil { - t.Fatal("newReplayFilter failed:", err) - } - - buf := []byte("This is a test of the Emergency Broadcast System.") - var now int64 = 3600 - - // testAndSet into empty filter, returns false (not present). - set := f.testAndSet(now, buf) - if set { - t.Fatal("testAndSet empty filter returned true") - } - - // testAndSet into filter containing entry, should return true(present). - set = f.testAndSet(now, buf) - if !set { - t.Fatal("testAndSet populated filter (replayed) returned false") - } - - buf2 := []byte("This concludes this test of the Emergency Broadcast System.") - now += 3600 * 2 - - // testAndSet with time advanced. - set = f.testAndSet(now, buf2) - if set { - t.Fatal("testAndSet populated filter, 2nd entry returned true") - } - set = f.testAndSet(now, buf2) - if !set { - t.Fatal("testAndSet populated filter, 2nd entry (replayed) returned false") - } - - // Ensure that the first entry has been removed by compact. - set = f.testAndSet(now, buf) - if set { - t.Fatal("testAndSet populated filter, compact check returned true") - } - - // Ensure that the filter gets reaped if the clock jumps backwards. - now = 0 - set = f.testAndSet(now, buf) - if set { - t.Fatal("testAndSet populated filter, backward time jump returned true") - } - if len(f.filter) != 1 { - t.Fatal("filter map has a unexpected number of entries:", len(f.filter)) - } - if f.fifo.Len() != 1 { - t.Fatal("filter fifo has a unexpected number of entries:", f.fifo.Len()) - } - - // Ensure that the entry is properly added after reaping. - set = f.testAndSet(now, buf) - if !set { - t.Fatal("testAndSet populated filter, post-backward clock jump (replayed) returned false") - } -} diff --git a/transports/base/base.go b/transports/base/base.go new file mode 100644 index 0000000..e81ea03 --- /dev/null +++ b/transports/base/base.go @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 base provides the common interface that each supported transport +// protocol must implement. +package base + +import ( + "net" + + "git.torproject.org/pluggable-transports/goptlib.git" +) + +// ClientFactory is the interface that defines the factory for creating +// pluggable transport protocol client instances. +type ClientFactory interface { + // Transport returns the Transport instance that this ClientFactory belongs + // to. + Transport() Transport + + // ParseArgs parses the supplied arguments into an internal representation + // for use with WrapConn. This routine is called before the outgoing + // TCP/IP connection is created to allow doing things (like keypair + // generation) to be hidden from third parties. + ParseArgs(args *pt.Args) (interface{}, error) + + // WrapConn wraps the provided net.Conn with a transport protocol + // implementation, and does whatever is required (eg: handshaking) to get + // the connection to a point where it is ready to relay data. + WrapConn(conn net.Conn, args interface{}) (net.Conn, error) +} + +// ServerFactory is the interface that defines the factory for creating +// plugable transport protocol server instances. As the arguments are the +// property of the factory, validation is done at factory creation time. +type ServerFactory interface { + // Transport returns the Transport instance that this ServerFactory belongs + // to. + Transport() Transport + + // Args returns the Args required on the client side to handshake with + // server connections created by this factory. + Args() *pt.Args + + // WrapConn wraps the provided net.Conn with a transport protocol + // implementation, and does whatever is required (eg: handshaking) to get + // the connection to a point where it is ready to relay data. + WrapConn(conn net.Conn) (net.Conn, error) +} + +// Transport is an interface that defines a pluggable transport protocol. +type Transport interface { + // Name returns the name of the transport protocol. It MUST be a valid C + // identifier. + Name() string + + // ClientFactory returns a ClientFactory instance for this transport + // protocol. + ClientFactory(stateDir string) (ClientFactory, error) + + // ServerFactory returns a ServerFactory instance for this transport + // protocol. This can fail if the provided arguments are invalid. + ServerFactory(stateDir string, args *pt.Args) (ServerFactory, error) +} diff --git a/transports/obfs2/obfs2.go b/transports/obfs2/obfs2.go new file mode 100644 index 0000000..3490646 --- /dev/null +++ b/transports/obfs2/obfs2.go @@ -0,0 +1,367 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 obfs2 provides an implementation of the Tor Project's obfs2 +// obfuscation protocol. This protocol is considered trivially broken by most +// sophisticated adversaries. +package obfs2 + +import ( + "crypto/aes" + "crypto/cipher" + "crypto/sha256" + "encoding/binary" + "fmt" + "io" + "net" + "time" + + "git.torproject.org/pluggable-transports/goptlib.git" + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" + "git.torproject.org/pluggable-transports/obfs4.git/transports/base" +) + +const ( + transportName = "obfs2" + sharedSecretArg = "shared-secret" + + clientHandshakeTimeout = time.Duration(30) * time.Second + serverHandshakeTimeout = time.Duration(30) * time.Second + + magicValue = 0x2bf5ca7e + initiatorPadString = "Initiator obfuscation padding" + responderPadString = "Responder obfuscation padding" + initiatorKdfString = "Initiator obfuscated data" + responderKdfString = "Responder obfuscated data" + maxPadding = 8192 + keyLen = 16 + seedLen = 16 + hsLen = 4 + 4 +) + +func validateArgs(args *pt.Args) error { + if _, ok := args.Get(sharedSecretArg); ok { + // "shared-secret" is something no bridges use in practice and is thus + // unimplemented. + return fmt.Errorf("unsupported argument '%s'", sharedSecretArg) + } + return nil +} + +// Transport is the obfs2 implementation of the base.Transport interface. +type Transport struct{} + +// Name returns the name of the obfs2 transport protocol. +func (t *Transport) Name() string { + return transportName +} + +// ClientFactory returns a new obfs2ClientFactory instance. +func (t *Transport) ClientFactory(stateDir string) (base.ClientFactory, error) { + cf := &obfs2ClientFactory{transport: t} + return cf, nil +} + +// ServerFactory returns a new obfs2ServerFactory instance. +func (t *Transport) ServerFactory(stateDir string, args *pt.Args) (base.ServerFactory, error) { + if err := validateArgs(args); err != nil { + return nil, err + } + + sf := &obfs2ServerFactory{t} + return sf, nil +} + +type obfs2ClientFactory struct { + transport base.Transport +} + +func (cf *obfs2ClientFactory) Transport() base.Transport { + return cf.transport +} + +func (cf *obfs2ClientFactory) ParseArgs(args *pt.Args) (interface{}, error) { + return nil, validateArgs(args) +} + +func (cf *obfs2ClientFactory) WrapConn(conn net.Conn, args interface{}) (net.Conn, error) { + return newObfs2ClientConn(conn) +} + +type obfs2ServerFactory struct { + transport base.Transport +} + +func (sf *obfs2ServerFactory) Transport() base.Transport { + return sf.transport +} + +func (sf *obfs2ServerFactory) Args() *pt.Args { + return nil +} + +func (sf *obfs2ServerFactory) WrapConn(conn net.Conn) (net.Conn, error) { + return newObfs2ServerConn(conn) +} + +type obfs2Conn struct { + net.Conn + + isInitiator bool + + rx *cipher.StreamReader + tx *cipher.StreamWriter +} + +func (conn *obfs2Conn) Read(b []byte) (int, error) { + return conn.rx.Read(b) +} + +func (conn *obfs2Conn) Write(b []byte) (int, error) { + return conn.tx.Write(b) +} + +func newObfs2ClientConn(conn net.Conn) (c *obfs2Conn, err error) { + // Initialize a client connection, and start the handshake timeout. + c = &obfs2Conn{conn, true, nil, nil} + deadline := time.Now().Add(clientHandshakeTimeout) + if err = c.SetDeadline(deadline); err != nil { + return nil, err + } + + // Handshake. + if err = c.handshake(); err != nil { + return nil, err + } + + // Disarm the handshake timer. + if err = c.SetDeadline(time.Time{}); err != nil { + return nil, err + } + + return +} + +func newObfs2ServerConn(conn net.Conn) (c *obfs2Conn, err error) { + // Initialize a server connection, and start the handshake timeout. + c = &obfs2Conn{conn, false, nil, nil} + deadline := time.Now().Add(serverHandshakeTimeout) + if err = c.SetDeadline(deadline); err != nil { + return nil, err + } + + // Handshake. + if err = c.handshake(); err != nil { + return nil, err + } + + // Disarm the handshake timer. + if err = c.SetDeadline(time.Time{}); err != nil { + return nil, err + } + + return +} + +func (conn *obfs2Conn) handshake() (err error) { + // Each begins by generating a seed and a padding key as follows. + // The initiator generates: + // + // INIT_SEED = SR(SEED_LENGTH) + // INIT_PAD_KEY = MAC("Initiator obfuscation padding", INIT_SEED)[:KEYLEN] + // + // And the responder generates: + // + // RESP_SEED = SR(SEED_LENGTH) + // RESP_PAD_KEY = MAC("Responder obfuscation padding", INIT_SEED)[:KEYLEN] + // + // Each then generates a random number PADLEN in range from 0 through + // MAX_PADDING (inclusive). + var seed [seedLen]byte + if err = csrand.Bytes(seed[:]); err != nil { + return + } + var padMagic []byte + if conn.isInitiator { + padMagic = []byte(initiatorPadString) + } else { + padMagic = []byte(responderPadString) + } + padKey, padIV := hsKdf(padMagic, seed[:], conn.isInitiator) + padLen := uint32(csrand.IntRange(0, maxPadding)) + + hsBlob := make([]byte, hsLen+padLen) + binary.BigEndian.PutUint32(hsBlob[0:4], magicValue) + binary.BigEndian.PutUint32(hsBlob[4:8], padLen) + if padLen > 0 { + if err = csrand.Bytes(hsBlob[8:]); err != nil { + return + } + } + + // The initiator then sends: + // + // INIT_SEED | E(INIT_PAD_KEY, UINT32(MAGIC_VALUE) | UINT32(PADLEN) | WR(PADLEN)) + // + // and the responder sends: + // + // RESP_SEED | E(RESP_PAD_KEY, UINT32(MAGIC_VALUE) | UINT32(PADLEN) | WR(PADLEN)) + var txBlock cipher.Block + if txBlock, err = aes.NewCipher(padKey); err != nil { + return + } + txStream := cipher.NewCTR(txBlock, padIV) + conn.tx = &cipher.StreamWriter{txStream, conn.Conn, nil} + if _, err = conn.Conn.Write(seed[:]); err != nil { + return + } + if _, err = conn.Write(hsBlob); err != nil { + return + } + + // Upon receiving the SEED from the other party, each party derives + // the other party's padding key value as above, and decrypts the next + // 8 bytes of the key establishment message. + var peerSeed [seedLen]byte + if _, err = io.ReadFull(conn.Conn, peerSeed[:]); err != nil { + return + } + var peerPadMagic []byte + if conn.isInitiator { + peerPadMagic = []byte(responderPadString) + } else { + peerPadMagic = []byte(initiatorPadString) + } + peerKey, peerIV := hsKdf(peerPadMagic, peerSeed[:], !conn.isInitiator) + var rxBlock cipher.Block + if rxBlock, err = aes.NewCipher(peerKey); err != nil { + return + } + rxStream := cipher.NewCTR(rxBlock, peerIV) + conn.rx = &cipher.StreamReader{rxStream, conn.Conn} + hsHdr := make([]byte, hsLen) + if _, err = io.ReadFull(conn, hsHdr[:]); err != nil { + return + } + + // If the MAGIC_VALUE does not match, or the PADLEN value is greater than + // MAX_PADDING, the party receiving it should close the connection + // immediately. + if peerMagic := binary.BigEndian.Uint32(hsHdr[0:4]); peerMagic != magicValue { + err = fmt.Errorf("invalid magic value: %x", peerMagic) + return + } + padLen = binary.BigEndian.Uint32(hsHdr[4:8]) + if padLen > maxPadding { + err = fmt.Errorf("padlen too long: %d", padLen) + return + } + + // Otherwise, it should read the remaining PADLEN bytes of padding data + // and discard them. + tmp := make([]byte, padLen) + if _, err = io.ReadFull(conn.Conn, tmp); err != nil { // Note: Skips AES. + return + } + + // Derive the actual keys. + if err = conn.kdf(seed[:], peerSeed[:]); err != nil { + return + } + + return +} + +func (conn *obfs2Conn) kdf(seed, peerSeed []byte) (err error) { + // Additional keys are then derived as: + // + // INIT_SECRET = MAC("Initiator obfuscated data", INIT_SEED|RESP_SEED) + // RESP_SECRET = MAC("Responder obfuscated data", INIT_SEED|RESP_SEED) + // INIT_KEY = INIT_SECRET[:KEYLEN] + // INIT_IV = INIT_SECRET[KEYLEN:] + // RESP_KEY = RESP_SECRET[:KEYLEN] + // RESP_IV = RESP_SECRET[KEYLEN:] + combSeed := make([]byte, 0, seedLen*2) + if conn.isInitiator { + combSeed = append(combSeed, seed...) + combSeed = append(combSeed, peerSeed...) + } else { + combSeed = append(combSeed, peerSeed...) + combSeed = append(combSeed, seed...) + } + + initKey, initIV := hsKdf([]byte(initiatorKdfString), combSeed, true) + var initBlock cipher.Block + if initBlock, err = aes.NewCipher(initKey); err != nil { + return + } + initStream := cipher.NewCTR(initBlock, initIV) + + respKey, respIV := hsKdf([]byte(responderKdfString), combSeed, false) + var respBlock cipher.Block + if respBlock, err = aes.NewCipher(respKey); err != nil { + return + } + respStream := cipher.NewCTR(respBlock, respIV) + + if conn.isInitiator { + conn.tx.S = initStream + conn.rx.S = respStream + } else { + conn.tx.S = respStream + conn.rx.S = initStream + } + + return +} + +func hsKdf(magic, seed []byte, isInitiator bool) (padKey, padIV []byte) { + // The actual key/IV is derived in the form of: + // m = MAC(magic, seed) + // KEY = m[:KEYLEN] + // IV = m[KEYLEN:] + m := mac(magic, seed) + padKey = m[:keyLen] + padIV = m[keyLen:] + + return +} + +func mac(s, x []byte) []byte { + // H(x) is SHA256 of x. + // MAC(s, x) = H(s | x | s) + h := sha256.New() + h.Write(s) + h.Write(x) + h.Write(s) + return h.Sum(nil) +} + +var _ base.ClientFactory = (*obfs2ClientFactory)(nil) +var _ base.ServerFactory = (*obfs2ServerFactory)(nil) +var _ base.Transport = (*Transport)(nil) +var _ net.Conn = (*obfs2Conn)(nil) diff --git a/transports/obfs3/obfs3.go b/transports/obfs3/obfs3.go new file mode 100644 index 0000000..7844443 --- /dev/null +++ b/transports/obfs3/obfs3.go @@ -0,0 +1,358 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 obfs3 provides an implementation of the Tor Project's obfs3 +// obfuscation protocol. +package obfs3 + +import ( + "bytes" + "crypto/aes" + "crypto/cipher" + "crypto/hmac" + "crypto/sha256" + "errors" + "io" + "net" + "time" + + "git.torproject.org/pluggable-transports/goptlib.git" + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" + "git.torproject.org/pluggable-transports/obfs4.git/common/uniformdh" + "git.torproject.org/pluggable-transports/obfs4.git/transports/base" +) + +const ( + transportName = "obfs3" + + clientHandshakeTimeout = time.Duration(30) * time.Second + serverHandshakeTimeout = time.Duration(30) * time.Second + + initiatorKdfString = "Initiator obfuscated data" + responderKdfString = "Responder obfuscated data" + initiatorMagicString = "Initiator magic" + responderMagicString = "Responder magic" + maxPadding = 8194 + keyLen = 16 +) + +// Transport is the obfs3 implementation of the base.Transport interface. +type Transport struct{} + +// Name returns the name of the obfs3 transport protocol. +func (t *Transport) Name() string { + return transportName +} + +// ClientFactory returns a new obfs3ClientFactory instance. +func (t *Transport) ClientFactory(stateDir string) (base.ClientFactory, error) { + cf := &obfs3ClientFactory{transport: t} + return cf, nil +} + +// ServerFactory returns a new obfs3ServerFactory instance. +func (t *Transport) ServerFactory(stateDir string, args *pt.Args) (base.ServerFactory, error) { + sf := &obfs3ServerFactory{transport: t} + return sf, nil +} + +type obfs3ClientFactory struct { + transport base.Transport +} + +func (cf *obfs3ClientFactory) Transport() base.Transport { + return cf.transport +} + +func (cf *obfs3ClientFactory) ParseArgs(args *pt.Args) (interface{}, error) { + return nil, nil +} + +func (cf *obfs3ClientFactory) WrapConn(conn net.Conn, args interface{}) (net.Conn, error) { + return newObfs3ClientConn(conn) +} + +type obfs3ServerFactory struct { + transport base.Transport +} + +func (sf *obfs3ServerFactory) Transport() base.Transport { + return sf.transport +} + +func (sf *obfs3ServerFactory) Args() *pt.Args { + return nil +} + +func (sf *obfs3ServerFactory) WrapConn(conn net.Conn) (net.Conn, error) { + return newObfs3ServerConn(conn) +} + +type obfs3Conn struct { + net.Conn + + isInitiator bool + rxMagic []byte + txMagic []byte + rxBuf *bytes.Buffer + + rx *cipher.StreamReader + tx *cipher.StreamWriter +} + +func newObfs3ClientConn(conn net.Conn) (c *obfs3Conn, err error) { + // Initialize a client connection, and start the handshake timeout. + c = &obfs3Conn{conn, true, nil, nil, new(bytes.Buffer), nil, nil} + deadline := time.Now().Add(clientHandshakeTimeout) + if err = c.SetDeadline(deadline); err != nil { + return nil, err + } + + // Handshake. + if err = c.handshake(); err != nil { + return nil, err + } + + // Disarm the handshake timer. + if err = c.SetDeadline(time.Time{}); err != nil { + return nil, err + } + + return +} + +func newObfs3ServerConn(conn net.Conn) (c *obfs3Conn, err error) { + // Initialize a server connection, and start the handshake timeout. + c = &obfs3Conn{conn, false, nil, nil, new(bytes.Buffer), nil, nil} + deadline := time.Now().Add(serverHandshakeTimeout) + if err = c.SetDeadline(deadline); err != nil { + return nil, err + } + + // Handshake. + if err = c.handshake(); err != nil { + return nil, err + } + + // Disarm the handshake timer. + if err = c.SetDeadline(time.Time{}); err != nil { + return nil, err + } + + return +} + +func (conn *obfs3Conn) handshake() (err error) { + // The party who opens the connection is the 'initiator'; the one who + // accepts it is the 'responder'. Each begins by generating a + // UniformDH keypair, and a random number PADLEN in [0, MAX_PADDING/2]. + // Both parties then send: + // + // PUB_KEY | WR(PADLEN) + var privateKey *uniformdh.PrivateKey + if privateKey, err = uniformdh.GenerateKey(csrand.Reader); err != nil { + return + } + padLen := csrand.IntRange(0, maxPadding/2) + blob := make([]byte, uniformdh.Size+padLen) + var publicKey []byte + if publicKey, err = privateKey.PublicKey.Bytes(); err != nil { + return + } + copy(blob[0:], publicKey) + if err = csrand.Bytes(blob[uniformdh.Size:]); err != nil { + return + } + if _, err = conn.Conn.Write(blob); err != nil { + return + } + + // Read the public key from the peer. + rawPeerPublicKey := make([]byte, uniformdh.Size) + if _, err = io.ReadFull(conn.Conn, rawPeerPublicKey); err != nil { + return + } + var peerPublicKey uniformdh.PublicKey + if err = peerPublicKey.SetBytes(rawPeerPublicKey); err != nil { + return + } + + // After retrieving the public key of the other end, each party + // completes the DH key exchange and generates a shared-secret for the + // session (named SHARED_SECRET). + var sharedSecret []byte + if sharedSecret, err = uniformdh.Handshake(privateKey, &peerPublicKey); err != nil { + return + } + if err = conn.kdf(sharedSecret); err != nil { + return + } + + return +} + +func (conn *obfs3Conn) kdf(sharedSecret []byte) (err error) { + // Using that shared-secret each party derives its encryption keys as + // follows: + // + // INIT_SECRET = HMAC(SHARED_SECRET, "Initiator obfuscated data") + // RESP_SECRET = HMAC(SHARED_SECRET, "Responder obfuscated data") + // INIT_KEY = INIT_SECRET[:KEYLEN] + // INIT_COUNTER = INIT_SECRET[KEYLEN:] + // RESP_KEY = RESP_SECRET[:KEYLEN] + // RESP_COUNTER = RESP_SECRET[KEYLEN:] + initHmac := hmac.New(sha256.New, sharedSecret) + initHmac.Write([]byte(initiatorKdfString)) + initSecret := initHmac.Sum(nil) + initHmac.Reset() + initHmac.Write([]byte(initiatorMagicString)) + initMagic := initHmac.Sum(nil) + + respHmac := hmac.New(sha256.New, sharedSecret) + respHmac.Write([]byte(responderKdfString)) + respSecret := respHmac.Sum(nil) + respHmac.Reset() + respHmac.Write([]byte(responderMagicString)) + respMagic := respHmac.Sum(nil) + + // The INIT_KEY value keys a block cipher (in CTR mode) used to + // encrypt values from initiator to responder thereafter. The counter + // mode's initial counter value is INIT_COUNTER. The RESP_KEY value + // keys a block cipher (in CTR mode) used to encrypt values from + // responder to initiator thereafter. That counter mode's initial + // counter value is RESP_COUNTER. + // + // Note: To have this be the last place where the shared secret is used, + // also generate the magic value to send/scan for here. + var initBlock cipher.Block + if initBlock, err = aes.NewCipher(initSecret[:keyLen]); err != nil { + return err + } + initStream := cipher.NewCTR(initBlock, initSecret[keyLen:]) + + var respBlock cipher.Block + if respBlock, err = aes.NewCipher(respSecret[:keyLen]); err != nil { + return err + } + respStream := cipher.NewCTR(respBlock, respSecret[keyLen:]) + + if conn.isInitiator { + conn.tx = &cipher.StreamWriter{initStream, conn.Conn, nil} + conn.rx = &cipher.StreamReader{respStream, conn.rxBuf} + conn.txMagic = initMagic + conn.rxMagic = respMagic + } else { + conn.tx = &cipher.StreamWriter{respStream, conn.Conn, nil} + conn.rx = &cipher.StreamReader{initStream, conn.rxBuf} + conn.txMagic = respMagic + conn.rxMagic = initMagic + } + + return +} + +func (conn *obfs3Conn) findPeerMagic() error { + var hsBuf [maxPadding + sha256.Size]byte + for { + n, err := conn.Conn.Read(hsBuf[:]) + if err != nil { + // Yes, Read can return partial data and an error, but continuing + // past that is nonsensical. + return err + } + conn.rxBuf.Write(hsBuf[:n]) + + pos := bytes.Index(conn.rxBuf.Bytes(), conn.rxMagic) + if pos == -1 { + if conn.rxBuf.Len() >= maxPadding+sha256.Size { + return errors.New("failed to find peer magic value") + } + continue + } else if pos > maxPadding { + return errors.New("peer sent too much pre-magic-padding") + } + + // Discard the padding/MAC. + pos += len(conn.rxMagic) + _ = conn.rxBuf.Next(pos) + + return nil + } +} + +func (conn *obfs3Conn) Read(b []byte) (n int, err error) { + // If this is the first time we read data post handshake, scan for the + // magic value. + if conn.rxMagic != nil { + if err = conn.findPeerMagic(); err != nil { + conn.Close() + return + } + conn.rxMagic = nil + } + + // If the handshake receive buffer is still present... + if conn.rxBuf != nil { + // And it is empty... + if conn.rxBuf.Len() == 0 { + // There is no more trailing data left from the handshake process, + // so rewire the cipher.StreamReader to pull data from the network + // instead of the temporary receive buffer. + conn.rx.R = conn.Conn + conn.rxBuf = nil + } + } + + return conn.rx.Read(b) +} + +func (conn *obfs3Conn) Write(b []byte) (n int, err error) { + // If this is the first time we write data post handshake, send the + // padding/magic value. + if conn.txMagic != nil { + padLen := csrand.IntRange(0, maxPadding/2) + blob := make([]byte, padLen+len(conn.txMagic)) + if err = csrand.Bytes(blob[:padLen]); err != nil { + conn.Close() + return + } + copy(blob[padLen:], conn.txMagic) + if _, err = conn.Conn.Write(blob); err != nil { + conn.Close() + return + } + conn.txMagic = nil + } + + return conn.tx.Write(b) +} + + +var _ base.ClientFactory = (*obfs3ClientFactory)(nil) +var _ base.ServerFactory = (*obfs3ServerFactory)(nil) +var _ base.Transport = (*Transport)(nil) +var _ net.Conn = (*obfs3Conn)(nil) diff --git a/transports/obfs4/framing/framing.go b/transports/obfs4/framing/framing.go new file mode 100644 index 0000000..04e788f --- /dev/null +++ b/transports/obfs4/framing/framing.go @@ -0,0 +1,308 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 framing implements the obfs4 link framing and cryptography. +// +// The Encoder/Decoder shared secret format is: +// uint8_t[32] NaCl secretbox key +// uint8_t[16] NaCl Nonce prefix +// uint8_t[16] SipHash-2-4 key (used to obfsucate length) +// uint8_t[8] SipHash-2-4 IV +// +// The frame format is: +// uint16_t length (obfsucated, big endian) +// NaCl secretbox (Poly1305/XSalsa20) containing: +// uint8_t[16] tag (Part of the secretbox construct) +// uint8_t[] payload +// +// The length field is length of the NaCl secretbox XORed with the truncated +// SipHash-2-4 digest ran in OFB mode. +// +// Initialize K, IV[0] with values from the shared secret. +// On each packet, IV[n] = H(K, IV[n - 1]) +// mask[n] = IV[n][0:2] +// obfsLen = length ^ mask[n] +// +// The NaCl secretbox (Poly1305/XSalsa20) nonce format is: +// uint8_t[24] prefix (Fixed) +// uint64_t counter (Big endian) +// +// The counter is initialized to 1, and is incremented on each frame. Since +// the protocol is designed to be used over a reliable medium, the nonce is not +// transmitted over the wire as both sides of the conversation know the prefix +// and the initial counter value. It is imperative that the counter does not +// wrap, and sessions MUST terminate before 2^64 frames are sent. +// +package framing + +import ( + "bytes" + "encoding/binary" + "errors" + "fmt" + "io" + + "code.google.com/p/go.crypto/nacl/secretbox" + + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" + "git.torproject.org/pluggable-transports/obfs4.git/common/drbg" +) + +const ( + // MaximumSegmentLength is the length of the largest possible segment + // including overhead. + MaximumSegmentLength = 1500 - (40 + 12) + + // FrameOverhead is the length of the framing overhead. + FrameOverhead = lengthLength + secretbox.Overhead + + // MaximumFramePayloadLength is the length of the maximum allowed payload + // per frame. + MaximumFramePayloadLength = MaximumSegmentLength - FrameOverhead + + // KeyLength is the length of the Encoder/Decoder secret key. + KeyLength = keyLength + noncePrefixLength + drbg.SeedLength + + maxFrameLength = MaximumSegmentLength - lengthLength + minFrameLength = FrameOverhead - lengthLength + + keyLength = 32 + + noncePrefixLength = 16 + nonceCounterLength = 8 + nonceLength = noncePrefixLength + nonceCounterLength + + lengthLength = 2 +) + +// Error returned when Decoder.Decode() requires more data to continue. +var ErrAgain = errors.New("framing: More data needed to decode") + +// Error returned when Decoder.Decode() failes to authenticate a frame. +var ErrTagMismatch = errors.New("framing: Poly1305 tag mismatch") + +// Error returned when the NaCl secretbox nonce's counter wraps (FATAL). +var ErrNonceCounterWrapped = errors.New("framing: Nonce counter wrapped") + +// InvalidPayloadLengthError is the error returned when Encoder.Encode() +// rejects the payload length. +type InvalidPayloadLengthError int + +func (e InvalidPayloadLengthError) Error() string { + return fmt.Sprintf("framing: Invalid payload length: %d", int(e)) +} + +type boxNonce struct { + prefix [noncePrefixLength]byte + counter uint64 +} + +func (nonce *boxNonce) init(prefix []byte) { + if noncePrefixLength != len(prefix) { + panic(fmt.Sprintf("BUG: Nonce prefix length invalid: %d", len(prefix))) + } + + copy(nonce.prefix[:], prefix) + nonce.counter = 1 +} + +func (nonce boxNonce) bytes(out *[nonceLength]byte) error { + // The security guarantee of Poly1305 is broken if a nonce is ever reused + // for a given key. Detect this by checking for counter wraparound since + // we start each counter at 1. If it ever happens that more than 2^64 - 1 + // frames are transmitted over a given connection, support for rekeying + // will be neccecary, but that's unlikely to happen. + if nonce.counter == 0 { + return ErrNonceCounterWrapped + } + + copy(out[:], nonce.prefix[:]) + binary.BigEndian.PutUint64(out[noncePrefixLength:], nonce.counter) + + return nil +} + +// Encoder is a frame encoder instance. +type Encoder struct { + key [keyLength]byte + nonce boxNonce + drbg *drbg.HashDrbg +} + +// NewEncoder creates a new Encoder instance. It must be supplied a slice +// containing exactly KeyLength bytes of keying material. +func NewEncoder(key []byte) *Encoder { + if len(key) != KeyLength { + panic(fmt.Sprintf("BUG: Invalid encoder key length: %d", len(key))) + } + + encoder := new(Encoder) + copy(encoder.key[:], key[0:keyLength]) + encoder.nonce.init(key[keyLength : keyLength+noncePrefixLength]) + seed, err := drbg.SeedFromBytes(key[keyLength+noncePrefixLength:]) + if err != nil { + panic(fmt.Sprintf("BUG: Failed to initialize DRBG: %s", err)) + } + encoder.drbg, _ = drbg.NewHashDrbg(seed) + + return encoder +} + +// Encode encodes a single frame worth of payload and returns the encoded +// length. InvalidPayloadLengthError is recoverable, all other errors MUST be +// treated as fatal and the session aborted. +func (encoder *Encoder) Encode(frame, payload []byte) (n int, err error) { + payloadLen := len(payload) + if MaximumFramePayloadLength < payloadLen { + return 0, InvalidPayloadLengthError(payloadLen) + } + if len(frame) < payloadLen+FrameOverhead { + return 0, io.ErrShortBuffer + } + + // Generate a new nonce. + var nonce [nonceLength]byte + err = encoder.nonce.bytes(&nonce) + if err != nil { + return 0, err + } + encoder.nonce.counter++ + + // Encrypt and MAC payload. + box := secretbox.Seal(frame[:lengthLength], payload, &nonce, &encoder.key) + + // Obfuscate the length. + length := uint16(len(box) - lengthLength) + lengthMask := encoder.drbg.NextBlock() + length ^= binary.BigEndian.Uint16(lengthMask) + binary.BigEndian.PutUint16(frame[:2], length) + + // Return the frame. + return len(box), nil +} + +// Decoder is a frame decoder instance. +type Decoder struct { + key [keyLength]byte + nonce boxNonce + drbg *drbg.HashDrbg + + nextNonce [nonceLength]byte + nextLength uint16 + nextLengthInvalid bool +} + +// NewDecoder creates a new Decoder instance. It must be supplied a slice +// containing exactly KeyLength bytes of keying material. +func NewDecoder(key []byte) *Decoder { + if len(key) != KeyLength { + panic(fmt.Sprintf("BUG: Invalid decoder key length: %d", len(key))) + } + + decoder := new(Decoder) + copy(decoder.key[:], key[0:keyLength]) + decoder.nonce.init(key[keyLength : keyLength+noncePrefixLength]) + seed, err := drbg.SeedFromBytes(key[keyLength+noncePrefixLength:]) + if err != nil { + panic(fmt.Sprintf("BUG: Failed to initialize DRBG: %s", err)) + } + decoder.drbg, _ = drbg.NewHashDrbg(seed) + + return decoder +} + +// Decode decodes a stream of data and returns the length if any. ErrAgain is +// a temporary failure, all other errors MUST be treated as fatal and the +// session aborted. +func (decoder *Decoder) Decode(data []byte, frames *bytes.Buffer) (int, error) { + // A length of 0 indicates that we do not know how big the next frame is + // going to be. + if decoder.nextLength == 0 { + // Attempt to pull out the next frame length. + if lengthLength > frames.Len() { + return 0, ErrAgain + } + + // Remove the length field from the buffer. + var obfsLen [lengthLength]byte + _, err := io.ReadFull(frames, obfsLen[:]) + if err != nil { + return 0, err + } + + // Derive the nonce the peer used. + err = decoder.nonce.bytes(&decoder.nextNonce) + if err != nil { + return 0, err + } + + // Deobfuscate the length field. + length := binary.BigEndian.Uint16(obfsLen[:]) + lengthMask := decoder.drbg.NextBlock() + length ^= binary.BigEndian.Uint16(lengthMask) + if maxFrameLength < length || minFrameLength > length { + // Per "Plaintext Recovery Attacks Against SSH" by + // Martin R. Albrecht, Kenneth G. Paterson and Gaven J. Watson, + // there are a class of attacks againt protocols that use similar + // sorts of framing schemes. + // + // While obfs4 should not allow plaintext recovery (CBC mode is + // not used), attempt to mitigate out of bound frame length errors + // by pretending that the length was a random valid range as per + // the countermeasure suggested by Denis Bider in section 6 of the + // paper. + + decoder.nextLengthInvalid = true + length = uint16(csrand.IntRange(minFrameLength, maxFrameLength)) + } + decoder.nextLength = length + } + + if int(decoder.nextLength) > frames.Len() { + return 0, ErrAgain + } + + // Unseal the frame. + var box [maxFrameLength]byte + n, err := io.ReadFull(frames, box[:decoder.nextLength]) + if err != nil { + return 0, err + } + out, ok := secretbox.Open(data[:0], box[:n], &decoder.nextNonce, &decoder.key) + if !ok || decoder.nextLengthInvalid { + // When a random length is used (on length error) the tag should always + // mismatch, but be paranoid. + return 0, ErrTagMismatch + } + + // Clean up and prepare for the next frame. + decoder.nextLength = 0 + decoder.nonce.counter++ + + return len(out), nil +} diff --git a/transports/obfs4/framing/framing_test.go b/transports/obfs4/framing/framing_test.go new file mode 100644 index 0000000..03e0d3b --- /dev/null +++ b/transports/obfs4/framing/framing_test.go @@ -0,0 +1,169 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 framing + +import ( + "bytes" + "crypto/rand" + "testing" +) + +func generateRandomKey() []byte { + key := make([]byte, KeyLength) + + _, err := rand.Read(key) + if err != nil { + panic(err) + } + + return key +} + +func newEncoder(t *testing.T) *Encoder { + // Generate a key to use. + key := generateRandomKey() + + encoder := NewEncoder(key) + if encoder == nil { + t.Fatalf("NewEncoder returned nil") + } + + return encoder +} + +// TestNewEncoder tests the Encoder ctor. +func TestNewEncoder(t *testing.T) { + encoder := newEncoder(t) + _ = encoder +} + +// TestEncoder_Encode tests Encoder.Encode. +func TestEncoder_Encode(t *testing.T) { + encoder := newEncoder(t) + + buf := make([]byte, MaximumFramePayloadLength) + _, _ = rand.Read(buf) // YOLO + for i := 0; i <= MaximumFramePayloadLength; i++ { + var frame [MaximumSegmentLength]byte + n, err := encoder.Encode(frame[:], buf[0:i]) + if err != nil { + t.Fatalf("Encoder.encode([%d]byte), failed: %s", i, err) + } + if n != i+FrameOverhead { + t.Fatalf("Unexpected encoded framesize: %d, expecting %d", n, i+ + FrameOverhead) + } + } +} + +// TestEncoder_Encode_Oversize tests oversized frame rejection. +func TestEncoder_Encode_Oversize(t *testing.T) { + encoder := newEncoder(t) + + var frame [MaximumSegmentLength]byte + var buf [MaximumFramePayloadLength + 1]byte + _, _ = rand.Read(buf[:]) // YOLO + _, err := encoder.Encode(frame[:], buf[:]) + if _, ok := err.(InvalidPayloadLengthError); !ok { + t.Error("Encoder.encode() returned unexpected error:", err) + } +} + +// TestNewDecoder tests the Decoder ctor. +func TestNewDecoder(t *testing.T) { + key := generateRandomKey() + decoder := NewDecoder(key) + if decoder == nil { + t.Fatalf("NewDecoder returned nil") + } +} + +// TestDecoder_Decode tests Decoder.Decode. +func TestDecoder_Decode(t *testing.T) { + key := generateRandomKey() + + encoder := NewEncoder(key) + decoder := NewDecoder(key) + + var buf [MaximumFramePayloadLength]byte + _, _ = rand.Read(buf[:]) // YOLO + for i := 0; i <= MaximumFramePayloadLength; i++ { + var frame [MaximumSegmentLength]byte + encLen, err := encoder.Encode(frame[:], buf[0:i]) + if err != nil { + t.Fatalf("Encoder.encode([%d]byte), failed: %s", i, err) + } + if encLen != i+FrameOverhead { + t.Fatalf("Unexpected encoded framesize: %d, expecting %d", encLen, + i+FrameOverhead) + } + + var decoded [MaximumFramePayloadLength]byte + + decLen, err := decoder.Decode(decoded[:], bytes.NewBuffer(frame[:encLen])) + if err != nil { + t.Fatalf("Decoder.decode([%d]byte), failed: %s", i, err) + } + if decLen != i { + t.Fatalf("Unexpected decoded framesize: %d, expecting %d", + decLen, i) + } + + if 0 != bytes.Compare(decoded[:decLen], buf[:i]) { + t.Fatalf("Frame %d does not match encoder input", i) + } + } +} + +// BencharkEncoder_Encode benchmarks Encoder.Encode processing 1 MiB +// of payload. +func BenchmarkEncoder_Encode(b *testing.B) { + var chopBuf [MaximumFramePayloadLength]byte + var frame [MaximumSegmentLength]byte + payload := make([]byte, 1024*1024) + encoder := NewEncoder(generateRandomKey()) + b.ResetTimer() + + for i := 0; i < b.N; i++ { + transfered := 0 + buffer := bytes.NewBuffer(payload) + for 0 < buffer.Len() { + n, err := buffer.Read(chopBuf[:]) + if err != nil { + b.Fatal("buffer.Read() failed:", err) + } + + n, err = encoder.Encode(frame[:], chopBuf[:n]) + transfered += n - FrameOverhead + } + if transfered != len(payload) { + b.Fatalf("Transfered length mismatch: %d != %d", transfered, + len(payload)) + } + } +} diff --git a/transports/obfs4/handshake_ntor.go b/transports/obfs4/handshake_ntor.go new file mode 100644 index 0000000..8dcf0c8 --- /dev/null +++ b/transports/obfs4/handshake_ntor.go @@ -0,0 +1,426 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 ( + "bytes" + "crypto/hmac" + "crypto/sha256" + "encoding/hex" + "errors" + "fmt" + "hash" + "strconv" + "time" + + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" + "git.torproject.org/pluggable-transports/obfs4.git/common/ntor" + "git.torproject.org/pluggable-transports/obfs4.git/common/replayfilter" + "git.torproject.org/pluggable-transports/obfs4.git/transports/obfs4/framing" +) + +const ( + maxHandshakeLength = 8192 + + clientMinPadLength = (serverMinHandshakeLength + inlineSeedFrameLength) - + clientMinHandshakeLength + clientMaxPadLength = maxHandshakeLength - clientMinHandshakeLength + clientMinHandshakeLength = ntor.RepresentativeLength + markLength + macLength + + serverMinPadLength = 0 + serverMaxPadLength = maxHandshakeLength - (serverMinHandshakeLength + + inlineSeedFrameLength) + serverMinHandshakeLength = ntor.RepresentativeLength + ntor.AuthLength + + markLength + macLength + + markLength = sha256.Size / 2 + macLength = sha256.Size / 2 + + inlineSeedFrameLength = framing.FrameOverhead + packetOverhead + seedPacketPayloadLength +) + +// ErrMarkNotFoundYet is the error returned when the obfs4 handshake is +// incomplete and requires more data to continue. This error is non-fatal and +// is the equivalent to EAGAIN/EWOULDBLOCK. +var ErrMarkNotFoundYet = errors.New("handshake: M_[C,S] not found yet") + +// ErrInvalidHandshake is the error returned when the obfs4 handshake fails due +// to the peer not sending the correct mark. This error is fatal and the +// connection MUST be dropped. +var ErrInvalidHandshake = errors.New("handshake: Failed to find M_[C,S]") + +// ErrReplayedHandshake is the error returned when the obfs4 handshake fails +// due it being replayed. This error is fatal and the connection MUST be +// dropped. +var ErrReplayedHandshake = errors.New("handshake: Replay detected") + +// ErrNtorFailed is the error returned when the ntor handshake fails. This +// error is fatal and the connection MUST be dropped. +var ErrNtorFailed = errors.New("handshake: ntor handshake failure") + +// InvalidMacError is the error returned when the handshake MACs do not match. +// This error is fatal and the connection MUST be dropped. +type InvalidMacError struct { + Derived []byte + Received []byte +} + +func (e *InvalidMacError) Error() string { + return fmt.Sprintf("handshake: MAC mismatch: Dervied: %s Received: %s.", + hex.EncodeToString(e.Derived), hex.EncodeToString(e.Received)) +} + +// InvalidAuthError is the error returned when the ntor AUTH tags do not match. +// This error is fatal and the connection MUST be dropped. +type InvalidAuthError struct { + Derived *ntor.Auth + Received *ntor.Auth +} + +func (e *InvalidAuthError) Error() string { + return fmt.Sprintf("handshake: ntor AUTH mismatch: Derived: %s Received:%s.", + hex.EncodeToString(e.Derived.Bytes()[:]), + hex.EncodeToString(e.Received.Bytes()[:])) +} + +type clientHandshake struct { + keypair *ntor.Keypair + nodeID *ntor.NodeID + serverIdentity *ntor.PublicKey + epochHour []byte + + padLen int + mac hash.Hash + + serverRepresentative *ntor.Representative + serverAuth *ntor.Auth + serverMark []byte +} + +func newClientHandshake(nodeID *ntor.NodeID, serverIdentity *ntor.PublicKey, sessionKey *ntor.Keypair) *clientHandshake { + hs := new(clientHandshake) + hs.keypair = sessionKey + hs.nodeID = nodeID + hs.serverIdentity = serverIdentity + hs.padLen = csrand.IntRange(clientMinPadLength, clientMaxPadLength) + hs.mac = hmac.New(sha256.New, append(hs.serverIdentity.Bytes()[:], hs.nodeID.Bytes()[:]...)) + + return hs +} + +func (hs *clientHandshake) generateHandshake() ([]byte, error) { + var buf bytes.Buffer + + hs.mac.Reset() + hs.mac.Write(hs.keypair.Representative().Bytes()[:]) + mark := hs.mac.Sum(nil)[:markLength] + + // The client handshake is X | P_C | M_C | MAC(X | P_C | M_C | E) where: + // * X is the client's ephemeral Curve25519 public key representative. + // * P_C is [clientMinPadLength,clientMaxPadLength] bytes of random padding. + // * M_C is HMAC-SHA256-128(serverIdentity | NodeID, X) + // * MAC is HMAC-SHA256-128(serverIdentity | NodeID, X .... E) + // * E is the string representation of the number of hours since the UNIX + // epoch. + + // Generate the padding + pad, err := makePad(hs.padLen) + if err != nil { + return nil, err + } + + // Write X, P_C, M_C. + buf.Write(hs.keypair.Representative().Bytes()[:]) + buf.Write(pad) + buf.Write(mark) + + // Calculate and write the MAC. + hs.mac.Reset() + hs.mac.Write(buf.Bytes()) + hs.epochHour = []byte(strconv.FormatInt(getEpochHour(), 10)) + hs.mac.Write(hs.epochHour) + buf.Write(hs.mac.Sum(nil)[:macLength]) + + return buf.Bytes(), nil +} + +func (hs *clientHandshake) parseServerHandshake(resp []byte) (int, []byte, error) { + // No point in examining the data unless the miminum plausible response has + // been received. + if serverMinHandshakeLength > len(resp) { + return 0, nil, ErrMarkNotFoundYet + } + + if hs.serverRepresentative == nil || hs.serverAuth == nil { + // Pull out the representative/AUTH. (XXX: Add ctors to ntor) + hs.serverRepresentative = new(ntor.Representative) + copy(hs.serverRepresentative.Bytes()[:], resp[0:ntor.RepresentativeLength]) + hs.serverAuth = new(ntor.Auth) + copy(hs.serverAuth.Bytes()[:], resp[ntor.RepresentativeLength:]) + + // Derive the mark. + hs.mac.Reset() + hs.mac.Write(hs.serverRepresentative.Bytes()[:]) + hs.serverMark = hs.mac.Sum(nil)[:markLength] + } + + // Attempt to find the mark + MAC. + pos := findMarkMac(hs.serverMark, resp, ntor.RepresentativeLength+ntor.AuthLength+serverMinPadLength, + maxHandshakeLength, false) + if pos == -1 { + if len(resp) >= maxHandshakeLength { + return 0, nil, ErrInvalidHandshake + } + return 0, nil, ErrMarkNotFoundYet + } + + // Validate the MAC. + hs.mac.Reset() + hs.mac.Write(resp[:pos+markLength]) + hs.mac.Write(hs.epochHour) + macCmp := hs.mac.Sum(nil)[:macLength] + macRx := resp[pos+markLength : pos+markLength+macLength] + if !hmac.Equal(macCmp, macRx) { + return 0, nil, &InvalidMacError{macCmp, macRx} + } + + // Complete the handshake. + serverPublic := hs.serverRepresentative.ToPublic() + ok, seed, auth := ntor.ClientHandshake(hs.keypair, serverPublic, + hs.serverIdentity, hs.nodeID) + if !ok { + return 0, nil, ErrNtorFailed + } + if !ntor.CompareAuth(auth, hs.serverAuth.Bytes()[:]) { + return 0, nil, &InvalidAuthError{auth, hs.serverAuth} + } + + return pos + markLength + macLength, seed.Bytes()[:], nil +} + +type serverHandshake struct { + keypair *ntor.Keypair + nodeID *ntor.NodeID + serverIdentity *ntor.Keypair + epochHour []byte + serverAuth *ntor.Auth + + padLen int + mac hash.Hash + + clientRepresentative *ntor.Representative + clientMark []byte +} + +func newServerHandshake(nodeID *ntor.NodeID, serverIdentity *ntor.Keypair, sessionKey *ntor.Keypair) *serverHandshake { + hs := new(serverHandshake) + hs.keypair = sessionKey + hs.nodeID = nodeID + hs.serverIdentity = serverIdentity + hs.padLen = csrand.IntRange(serverMinPadLength, serverMaxPadLength) + hs.mac = hmac.New(sha256.New, append(hs.serverIdentity.Public().Bytes()[:], hs.nodeID.Bytes()[:]...)) + + return hs +} + +func (hs *serverHandshake) parseClientHandshake(filter *replayfilter.ReplayFilter, resp []byte) ([]byte, error) { + // No point in examining the data unless the miminum plausible response has + // been received. + if clientMinHandshakeLength > len(resp) { + return nil, ErrMarkNotFoundYet + } + + if hs.clientRepresentative == nil { + // Pull out the representative/AUTH. (XXX: Add ctors to ntor) + hs.clientRepresentative = new(ntor.Representative) + copy(hs.clientRepresentative.Bytes()[:], resp[0:ntor.RepresentativeLength]) + + // Derive the mark. + hs.mac.Reset() + hs.mac.Write(hs.clientRepresentative.Bytes()[:]) + hs.clientMark = hs.mac.Sum(nil)[:markLength] + } + + // Attempt to find the mark + MAC. + pos := findMarkMac(hs.clientMark, resp, ntor.RepresentativeLength+clientMinPadLength, + maxHandshakeLength, true) + if pos == -1 { + if len(resp) >= maxHandshakeLength { + return nil, ErrInvalidHandshake + } + return nil, ErrMarkNotFoundYet + } + + // Validate the MAC. + macFound := false + for _, off := range []int64{0, -1, 1} { + // Allow epoch to be off by up to a hour in either direction. + epochHour := []byte(strconv.FormatInt(getEpochHour()+int64(off), 10)) + hs.mac.Reset() + hs.mac.Write(resp[:pos+markLength]) + hs.mac.Write(epochHour) + macCmp := hs.mac.Sum(nil)[:macLength] + macRx := resp[pos+markLength : pos+markLength+macLength] + if hmac.Equal(macCmp, macRx) { + // Ensure that this handshake has not been seen previously. + if filter.TestAndSet(time.Now(), macRx) { + // The client either happened to generate exactly the same + // session key and padding, or someone is replaying a previous + // handshake. In either case, fuck them. + return nil, ErrReplayedHandshake + } + + macFound = true + hs.epochHour = epochHour + + // We could break out here, but in the name of reducing timing + // variation, evaluate all 3 MACs. + } + } + if !macFound { + // This probably should be an InvalidMacError, but conveying the 3 MACS + // that would be accepted is annoying so just return a generic fatal + // failure. + return nil, ErrInvalidHandshake + } + + // Client should never sent trailing garbage. + if len(resp) != pos+markLength+macLength { + return nil, ErrInvalidHandshake + } + + clientPublic := hs.clientRepresentative.ToPublic() + ok, seed, auth := ntor.ServerHandshake(clientPublic, hs.keypair, + hs.serverIdentity, hs.nodeID) + if !ok { + return nil, ErrNtorFailed + } + hs.serverAuth = auth + + return seed.Bytes()[:], nil +} + +func (hs *serverHandshake) generateHandshake() ([]byte, error) { + var buf bytes.Buffer + + hs.mac.Reset() + hs.mac.Write(hs.keypair.Representative().Bytes()[:]) + mark := hs.mac.Sum(nil)[:markLength] + + // The server handshake is Y | AUTH | P_S | M_S | MAC(Y | AUTH | P_S | M_S | E) where: + // * Y is the server's ephemeral Curve25519 public key representative. + // * AUTH is the ntor handshake AUTH value. + // * P_S is [serverMinPadLength,serverMaxPadLength] bytes of random padding. + // * M_S is HMAC-SHA256-128(serverIdentity | NodeID, Y) + // * MAC is HMAC-SHA256-128(serverIdentity | NodeID, Y .... E) + // * E is the string representation of the number of hours since the UNIX + // epoch. + + // Generate the padding + pad, err := makePad(hs.padLen) + if err != nil { + return nil, err + } + + // Write Y, AUTH, P_S, M_S. + buf.Write(hs.keypair.Representative().Bytes()[:]) + buf.Write(hs.serverAuth.Bytes()[:]) + buf.Write(pad) + buf.Write(mark) + + // Calculate and write the MAC. + hs.mac.Reset() + hs.mac.Write(buf.Bytes()) + hs.epochHour = []byte(strconv.FormatInt(getEpochHour(), 10)) + hs.mac.Write(hs.epochHour) + buf.Write(hs.mac.Sum(nil)[:macLength]) + + return buf.Bytes(), nil +} + +// getEpochHour returns the number of hours since the UNIX epoch. +func getEpochHour() int64 { + return time.Now().Unix() / 3600 +} + +func findMarkMac(mark, buf []byte, startPos, maxPos int, fromTail bool) (pos int) { + if len(mark) != markLength { + panic(fmt.Sprintf("BUG: Invalid mark length: %d", len(mark))) + } + + endPos := len(buf) + if startPos > len(buf) { + return -1 + } + if endPos > maxPos { + endPos = maxPos + } + if endPos-startPos < markLength+macLength { + return -1 + } + + if fromTail { + // The server can optimize the search process by only examining the + // tail of the buffer. The client can't send valid data past M_C | + // MAC_C as it does not have the server's public key yet. + pos = endPos - (markLength + macLength) + if !hmac.Equal(buf[pos:pos+markLength], mark) { + return -1 + } + + return + } + + // The client has to actually do a substring search since the server can + // and will send payload trailing the response. + // + // XXX: bytes.Index() uses a naive search, which kind of sucks. + pos = bytes.Index(buf[startPos:endPos], mark) + if pos == -1 { + return -1 + } + + // Ensure that there is enough trailing data for the MAC. + if startPos+pos+markLength+macLength > endPos { + return -1 + } + + // Return the index relative to the start of the slice. + pos += startPos + return +} + +func makePad(padLen int) ([]byte, error) { + pad := make([]byte, padLen) + err := csrand.Bytes(pad) + if err != nil { + return nil, err + } + + return pad, err +} diff --git a/transports/obfs4/handshake_ntor_test.go b/transports/obfs4/handshake_ntor_test.go new file mode 100644 index 0000000..fa03420 --- /dev/null +++ b/transports/obfs4/handshake_ntor_test.go @@ -0,0 +1,222 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 ( + "bytes" + "testing" + + "git.torproject.org/pluggable-transports/obfs4.git/common/ntor" + "git.torproject.org/pluggable-transports/obfs4.git/common/replayfilter" +) + +func TestHandshakeNtor(t *testing.T) { + // Generate the server node id and id keypair. + nodeID, _ := ntor.NewNodeID([]byte("\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13")) + idKeypair, _ := ntor.NewKeypair(false) + serverFilter, _ := replayfilter.New(replayTTL) + + // Test client handshake padding. + for l := clientMinPadLength; l <= clientMaxPadLength; l++ { + // Generate the client state and override the pad length. + clientKeypair, err := ntor.NewKeypair(true) + if err != nil { + t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) + } + clientHs := newClientHandshake(nodeID, idKeypair.Public(), clientKeypair) + clientHs.padLen = l + + // Generate what the client will send to the server. + clientBlob, err := clientHs.generateHandshake() + if err != nil { + t.Fatalf("[%d:0] clientHandshake.generateHandshake() failed: %s", l, err) + } + if len(clientBlob) > maxHandshakeLength { + t.Fatalf("[%d:0] Generated client body is oversized: %d", l, len(clientBlob)) + } + if len(clientBlob) < clientMinHandshakeLength { + t.Fatalf("[%d:0] Generated client body is undersized: %d", l, len(clientBlob)) + } + if len(clientBlob) != clientMinHandshakeLength+l { + t.Fatalf("[%d:0] Generated client body incorrect size: %d", l, len(clientBlob)) + } + + // Generate the server state and override the pad length. + serverKeypair, err := ntor.NewKeypair(true) + if err != nil { + t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) + } + serverHs := newServerHandshake(nodeID, idKeypair, serverKeypair) + serverHs.padLen = serverMinPadLength + + // Parse the client handshake message. + serverSeed, err := serverHs.parseClientHandshake(serverFilter, clientBlob) + if err != nil { + t.Fatalf("[%d:0] serverHandshake.parseClientHandshake() failed: %s", l, err) + } + + // Genrate what the server will send to the client. + serverBlob, err := serverHs.generateHandshake() + if err != nil { + t.Fatal("[%d:0]: serverHandshake.generateHandshake() failed: %s", l, err) + } + + // Parse the server handshake message. + clientHs.serverRepresentative = nil + n, clientSeed, err := clientHs.parseServerHandshake(serverBlob) + if err != nil { + t.Fatalf("[%d:0] clientHandshake.parseServerHandshake() failed: %s", l, err) + } + if n != len(serverBlob) { + t.Fatalf("[%d:0] clientHandshake.parseServerHandshake() has bytes remaining: %d", l, n) + } + + // Ensure the derived shared secret is the same. + if 0 != bytes.Compare(clientSeed, serverSeed) { + t.Fatalf("[%d:0] client/server seed mismatch", l) + } + } + + // Test server handshake padding. + for l := serverMinPadLength; l <= serverMaxPadLength+inlineSeedFrameLength; l++ { + // Generate the client state and override the pad length. + clientKeypair, err := ntor.NewKeypair(true) + if err != nil { + t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) + } + clientHs := newClientHandshake(nodeID, idKeypair.Public(), clientKeypair) + clientHs.padLen = clientMinPadLength + + // Generate what the client will send to the server. + clientBlob, err := clientHs.generateHandshake() + if err != nil { + t.Fatalf("[%d:1] clientHandshake.generateHandshake() failed: %s", l, err) + } + if len(clientBlob) > maxHandshakeLength { + t.Fatalf("[%d:1] Generated client body is oversized: %d", l, len(clientBlob)) + } + + // Generate the server state and override the pad length. + serverKeypair, err := ntor.NewKeypair(true) + if err != nil { + t.Fatalf("[%d:0] ntor.NewKeypair failed: %s", l, err) + } + serverHs := newServerHandshake(nodeID, idKeypair, serverKeypair) + serverHs.padLen = l + + // Parse the client handshake message. + serverSeed, err := serverHs.parseClientHandshake(serverFilter, clientBlob) + if err != nil { + t.Fatalf("[%d:1] serverHandshake.parseClientHandshake() failed: %s", l, err) + } + + // Genrate what the server will send to the client. + serverBlob, err := serverHs.generateHandshake() + if err != nil { + t.Fatal("[%d:1]: serverHandshake.generateHandshake() failed: %s", l, err) + } + + // Parse the server handshake message. + n, clientSeed, err := clientHs.parseServerHandshake(serverBlob) + if err != nil { + t.Fatalf("[%d:1] clientHandshake.parseServerHandshake() failed: %s", l, err) + } + if n != len(serverBlob) { + t.Fatalf("[%d:1] clientHandshake.parseServerHandshake() has bytes remaining: %d", l, n) + } + + // Ensure the derived shared secret is the same. + if 0 != bytes.Compare(clientSeed, serverSeed) { + t.Fatalf("[%d:1] client/server seed mismatch", l) + } + } + + // Test oversized client padding. + clientKeypair, err := ntor.NewKeypair(true) + if err != nil { + t.Fatalf("ntor.NewKeypair failed: %s", err) + } + clientHs := newClientHandshake(nodeID, idKeypair.Public(), clientKeypair) + if err != nil { + t.Fatalf("newClientHandshake failed: %s", err) + } + + clientHs.padLen = clientMaxPadLength + 1 + clientBlob, err := clientHs.generateHandshake() + if err != nil { + t.Fatalf("clientHandshake.generateHandshake() (forced oversize) failed: %s", err) + } + serverKeypair, err := ntor.NewKeypair(true) + if err != nil { + t.Fatalf("ntor.NewKeypair failed: %s", err) + } + serverHs := newServerHandshake(nodeID, idKeypair, serverKeypair) + _, err = serverHs.parseClientHandshake(serverFilter, clientBlob) + if err == nil { + t.Fatalf("serverHandshake.parseClientHandshake() succeded (oversized)") + } + + // Test undersized client padding. + clientHs.padLen = clientMinPadLength - 1 + clientBlob, err = clientHs.generateHandshake() + if err != nil { + t.Fatalf("clientHandshake.generateHandshake() (forced undersize) failed: %s", err) + } + serverHs = newServerHandshake(nodeID, idKeypair, serverKeypair) + _, err = serverHs.parseClientHandshake(serverFilter, clientBlob) + if err == nil { + t.Fatalf("serverHandshake.parseClientHandshake() succeded (undersized)") + } + + // Test oversized server padding. + // + // NB: serverMaxPadLength isn't the real maxPadLength that triggers client + // rejection, because the implementation is written with the asusmption + // that/ the PRNG_SEED is also inlined with the response. Thus the client + // actually accepts longer padding. The server handshake test and this + // test adjust around that. + clientHs.padLen = clientMinPadLength + clientBlob, err = clientHs.generateHandshake() + if err != nil { + t.Fatalf("clientHandshake.generateHandshake() failed: %s", err) + } + serverHs = newServerHandshake(nodeID, idKeypair, serverKeypair) + serverHs.padLen = serverMaxPadLength + inlineSeedFrameLength + 1 + _, err = serverHs.parseClientHandshake(serverFilter, clientBlob) + if err != nil { + t.Fatalf("serverHandshake.parseClientHandshake() failed: %s", err) + } + serverBlob, err := serverHs.generateHandshake() + if err != nil { + t.Fatal("serverHandshake.generateHandshake() (forced oversize) failed: %s", err) + } + _, _, err = clientHs.parseServerHandshake(serverBlob) + if err == nil { + t.Fatalf("clientHandshake.parseServerHandshake() succeded (oversized)") + } +} diff --git a/transports/obfs4/obfs4.go b/transports/obfs4/obfs4.go new file mode 100644 index 0000000..7af7224 --- /dev/null +++ b/transports/obfs4/obfs4.go @@ -0,0 +1,579 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 provides an implementation of the Tor Project's obfs4 +// obfuscation protocol. +package obfs4 + +import ( + "bytes" + "crypto/sha256" + "fmt" + "math/rand" + "net" + "syscall" + "time" + + "git.torproject.org/pluggable-transports/goptlib.git" + "git.torproject.org/pluggable-transports/obfs4.git/common/drbg" + "git.torproject.org/pluggable-transports/obfs4.git/common/ntor" + "git.torproject.org/pluggable-transports/obfs4.git/common/probdist" + "git.torproject.org/pluggable-transports/obfs4.git/common/replayfilter" + "git.torproject.org/pluggable-transports/obfs4.git/transports/base" + "git.torproject.org/pluggable-transports/obfs4.git/transports/obfs4/framing" +) + +const ( + transportName = "obfs4" + + nodeIDArg = "node-id" + publicKeyArg = "public-key" + privateKeyArg = "private-key" + seedArg = "drbg-seed" + + seedLength = 32 + headerLength = framing.FrameOverhead + packetOverhead + clientHandshakeTimeout = time.Duration(60) * time.Second + serverHandshakeTimeout = time.Duration(30) * time.Second + replayTTL = time.Duration(3) * time.Hour + + // Use a ScrambleSuit style biased probability table. + biasedDist = false + + // Use IAT obfuscation. + iatObfuscation = false + + // Maximum IAT delay (100 usec increments). + maxIATDelay = 100 + + maxCloseDelayBytes = maxHandshakeLength + maxCloseDelay = 60 +) + +type obfs4ClientArgs struct { + nodeID *ntor.NodeID + publicKey *ntor.PublicKey + sessionKey *ntor.Keypair +} + +// Transport is the obfs4 implementation of the base.Transport interface. +type Transport struct{} + +// Name returns the name of the obfs4 transport protocol. +func (t *Transport) Name() string { + return transportName +} + +// ClientFactory returns a new obfs4ClientFactory instance. +func (t *Transport) ClientFactory(stateDir string) (base.ClientFactory, error) { + cf := &obfs4ClientFactory{transport: t} + return cf, nil +} + +// ServerFactory returns a new obfs4ServerFactory instance. +func (t *Transport) ServerFactory(stateDir string, args *pt.Args) (base.ServerFactory, error) { + var err error + + var st *obfs4ServerState + if st, err = serverStateFromArgs(stateDir, args); err != nil { + return nil, err + } + + var iatSeed *drbg.Seed + if iatObfuscation { + iatSeedSrc := sha256.Sum256(st.drbgSeed.Bytes()[:]) + iatSeed, err = drbg.SeedFromBytes(iatSeedSrc[:]) + if err != nil { + return nil, err + } + } + + // Store the arguments that should appear in our descriptor for the clients. + ptArgs := pt.Args{} + ptArgs.Add(nodeIDArg, st.nodeID.Base64()) + ptArgs.Add(publicKeyArg, st.identityKey.Public().Base64()) + + // Initialize the replay filter. + filter, err := replayfilter.New(replayTTL) + if err != nil { + return nil, err + } + + // Initialize the close thresholds for failed connections. + drbg, err := drbg.NewHashDrbg(st.drbgSeed) + if err != nil { + return nil, err + } + rng := rand.New(drbg) + + sf := &obfs4ServerFactory{t, &ptArgs, st.nodeID, st.identityKey, st.drbgSeed, iatSeed, filter, rng.Intn(maxCloseDelayBytes), rng.Intn(maxCloseDelay)} + return sf, nil +} + +type obfs4ClientFactory struct { + transport base.Transport +} + +func (cf *obfs4ClientFactory) Transport() base.Transport { + return cf.transport +} + +func (cf *obfs4ClientFactory) ParseArgs(args *pt.Args) (interface{}, error) { + var err error + + // Handle the arguments. + nodeIDStr, ok := args.Get(nodeIDArg) + if !ok { + return nil, fmt.Errorf("missing argument '%s'", nodeIDArg) + } + var nodeID *ntor.NodeID + if nodeID, err = ntor.NodeIDFromBase64(nodeIDStr); err != nil { + return nil, err + } + + publicKeyStr, ok := args.Get(publicKeyArg) + if !ok { + return nil, fmt.Errorf("missing argument '%s'", publicKeyArg) + } + var publicKey *ntor.PublicKey + if publicKey, err = ntor.PublicKeyFromBase64(publicKeyStr); err != nil { + return nil, err + } + + // Generate the session key pair before connectiong to hide the Elligator2 + // rejection sampling from network observers. + sessionKey, err := ntor.NewKeypair(true) + if err != nil { + return nil, err + } + + return &obfs4ClientArgs{nodeID, publicKey, sessionKey}, nil +} + +func (cf *obfs4ClientFactory) WrapConn(conn net.Conn, args interface{}) (net.Conn, error) { + ca, ok := args.(*obfs4ClientArgs) + if !ok { + return nil, fmt.Errorf("invalid argument type for args") + } + + return newObfs4ClientConn(conn, ca) +} + +type obfs4ServerFactory struct { + transport base.Transport + args *pt.Args + + nodeID *ntor.NodeID + identityKey *ntor.Keypair + lenSeed *drbg.Seed + iatSeed *drbg.Seed + replayFilter *replayfilter.ReplayFilter + + closeDelayBytes int + closeDelay int +} + +func (sf *obfs4ServerFactory) Transport() base.Transport { + return sf.transport +} + +func (sf *obfs4ServerFactory) Args() *pt.Args { + return sf.args +} + +func (sf *obfs4ServerFactory) WrapConn(conn net.Conn) (net.Conn, error) { + // Not much point in having a separate newObfs4ServerConn routine when + // wrapping requires using values from the factory instance. + + // Generate the session keypair *before* consuming data from the peer, to + // attempt to mask the rejection sampling due to use of Elligator2. This + // might be futile, but the timing differential isn't very large on modern + // hardware, and there are far easier statistical attacks that can be + // mounted as a distinguisher. + sessionKey, err := ntor.NewKeypair(true) + if err != nil { + return nil, err + } + + lenDist := probdist.New(sf.lenSeed, 0, framing.MaximumSegmentLength, biasedDist) + var iatDist *probdist.WeightedDist + if sf.iatSeed != nil { + iatDist = probdist.New(sf.iatSeed, 0, maxIATDelay, biasedDist) + } + + c := &obfs4Conn{conn, true, lenDist, iatDist, bytes.NewBuffer(nil), bytes.NewBuffer(nil), nil, nil} + + startTime := time.Now() + + if err = c.serverHandshake(sf, sessionKey); err != nil { + c.closeAfterDelay(sf, startTime) + return nil, err + } + + return c, nil +} + +type obfs4Conn struct { + net.Conn + + isServer bool + + lenDist *probdist.WeightedDist + iatDist *probdist.WeightedDist + + receiveBuffer *bytes.Buffer + receiveDecodedBuffer *bytes.Buffer + + encoder *framing.Encoder + decoder *framing.Decoder +} + +func newObfs4ClientConn(conn net.Conn, args *obfs4ClientArgs) (c *obfs4Conn, err error) { + // Generate the initial protocol polymorphism distribution(s). + var seed *drbg.Seed + if seed, err = drbg.NewSeed(); err != nil { + return + } + lenDist := probdist.New(seed, 0, framing.MaximumSegmentLength, biasedDist) + var iatDist *probdist.WeightedDist + if iatObfuscation { + var iatSeed *drbg.Seed + iatSeedSrc := sha256.Sum256(seed.Bytes()[:]) + if iatSeed, err = drbg.SeedFromBytes(iatSeedSrc[:]); err != nil { + return + } + iatDist = probdist.New(iatSeed, 0, maxIATDelay, biasedDist) + } + + // Allocate the client structure. + c = &obfs4Conn{conn, false, lenDist, iatDist, bytes.NewBuffer(nil), bytes.NewBuffer(nil), nil, nil} + + // Start the handshake timeout. + deadline := time.Now().Add(clientHandshakeTimeout) + if err = conn.SetDeadline(deadline); err != nil { + return nil, err + } + + if err = c.clientHandshake(args.nodeID, args.publicKey, args.sessionKey); err != nil { + return nil, err + } + + // Stop the handshake timeout. + if err = conn.SetDeadline(time.Time{}); err != nil { + return nil, err + } + + return +} + +func (conn *obfs4Conn) clientHandshake(nodeID *ntor.NodeID, peerIdentityKey *ntor.PublicKey, sessionKey *ntor.Keypair) error { + if conn.isServer { + return fmt.Errorf("clientHandshake called on server connection") + } + + // Generate and send the client handshake. + hs := newClientHandshake(nodeID, peerIdentityKey, sessionKey) + blob, err := hs.generateHandshake() + if err != nil { + return err + } + if _, err = conn.Conn.Write(blob); err != nil { + return err + } + + // Consume the server handshake. + var hsBuf [maxHandshakeLength]byte + for { + var n int + if n, err = conn.Conn.Read(hsBuf[:]); err != nil { + // The Read() could have returned data and an error, but there is + // no point in continuing on an EOF or whatever. + return err + } + conn.receiveBuffer.Write(hsBuf[:n]) + + var seed []byte + n, seed, err = hs.parseServerHandshake(conn.receiveBuffer.Bytes()) + if err == ErrMarkNotFoundYet { + continue + } else if err != nil { + return err + } + _ = conn.receiveBuffer.Next(n) + + // Use the derived key material to intialize the link crypto. + okm := ntor.Kdf(seed, framing.KeyLength*2) + conn.encoder = framing.NewEncoder(okm[:framing.KeyLength]) + conn.decoder = framing.NewDecoder(okm[framing.KeyLength:]) + + return nil + } +} + +func (conn *obfs4Conn) serverHandshake(sf *obfs4ServerFactory, sessionKey *ntor.Keypair) (err error) { + if !conn.isServer { + return fmt.Errorf("serverHandshake called on client connection") + } + + // Generate the server handshake, and arm the base timeout. + hs := newServerHandshake(sf.nodeID, sf.identityKey, sessionKey) + if err = conn.Conn.SetDeadline(time.Now().Add(serverHandshakeTimeout)); err != nil { + return + } + + // Consume the client handshake. + var hsBuf [maxHandshakeLength]byte + for { + var n int + if n, err = conn.Conn.Read(hsBuf[:]); err != nil { + // The Read() could have returned data and an error, but there is + // no point in continuing on an EOF or whatever. + return + } + conn.receiveBuffer.Write(hsBuf[:n]) + + var seed []byte + seed, err = hs.parseClientHandshake(sf.replayFilter, conn.receiveBuffer.Bytes()) + if err == ErrMarkNotFoundYet { + continue + } else if err != nil { + return + } + conn.receiveBuffer.Reset() + + if err = conn.Conn.SetDeadline(time.Time{}); err != nil { + return + } + + // Use the derived key material to intialize the link crypto. + okm := ntor.Kdf(seed, framing.KeyLength*2) + conn.encoder = framing.NewEncoder(okm[framing.KeyLength:]) + conn.decoder = framing.NewDecoder(okm[:framing.KeyLength]) + + break + } + + // Since the current and only implementation always sends a PRNG seed for + // the length obfuscation, this makes the amount of data received from the + // server inconsistent with the length sent from the client. + // + // Rebalance this by tweaking the client mimimum padding/server maximum + // padding, and sending the PRNG seed unpadded (As in, treat the PRNG seed + // as part of the server response). See inlineSeedFrameLength in + // handshake_ntor.go. + + // Generate/send the response. + var blob []byte + blob, err = hs.generateHandshake() + if err != nil { + return + } + var frameBuf bytes.Buffer + _, err = frameBuf.Write(blob) + if err != nil { + return + } + + // Send the PRNG seed as the first packet. + if err = conn.makePacket(&frameBuf, packetTypePrngSeed, sf.lenSeed.Bytes()[:], 0); err != nil { + return + } + if _, err = conn.Conn.Write(frameBuf.Bytes()); err != nil { + return + } + + return +} + +func (conn *obfs4Conn) Read(b []byte) (n int, err error) { + // If there is no payload from the previous Read() calls, consume data off + // the network. Not all data received is guaranteed to be usable payload, + // so do this in a loop till data is present or an error occurs. + for conn.receiveDecodedBuffer.Len() == 0 { + err = conn.readPackets() + if err == framing.ErrAgain { + // Don't proagate this back up the call stack if we happen to break + // out of the loop. + err = nil + continue + } else if err != nil { + break + } + } + + // Even if err is set, attempt to do the read anyway so that all decoded + // data gets relayed before the connection is torn down. + if conn.receiveDecodedBuffer.Len() > 0 { + var berr error + n, berr = conn.receiveDecodedBuffer.Read(b) + if err == nil { + // Only propagate berr if there are not more important (fatal) + // errors from the network/crypto/packet processing. + err = berr + } + } + + return +} + +func (conn *obfs4Conn) Write(b []byte) (n int, err error) { + chopBuf := bytes.NewBuffer(b) + var payload [maxPacketPayloadLength]byte + var frameBuf bytes.Buffer + + // Chop the pending data into payload frames. + for chopBuf.Len() > 0 { + // Send maximum sized frames. + rdLen := 0 + rdLen, err = chopBuf.Read(payload[:]) + if err != nil { + return 0, err + } else if rdLen == 0 { + panic(fmt.Sprintf("BUG: Write(), chopping length was 0")) + } + n += rdLen + + err = conn.makePacket(&frameBuf, packetTypePayload, payload[:rdLen], 0) + if err != nil { + return 0, err + } + } + + // Add the length obfuscation padding. In theory, this could be inlined + // with the last chopped packet for certain (most?) payload lenghts, but + // this is simpler. + + if err = conn.padBurst(&frameBuf); err != nil { + return 0, err + } + + // Write the pending data onto the network. Partial writes are fatal, + // because the frame encoder state is advanced, and the code doesn't keep + // frameBuf around. In theory, write timeouts and whatnot could be + // supported if this wasn't the case, but that complicates the code. + + if conn.iatDist != nil { + var iatFrame [framing.MaximumSegmentLength]byte + for frameBuf.Len() > 0 { + iatWrLen := 0 + iatWrLen, err = frameBuf.Read(iatFrame[:]) + if err != nil { + return 0, err + } else if iatWrLen == 0 { + panic(fmt.Sprintf("BUG: Write(), iat length was 0")) + } + + // Calculate the delay. The delay resolution is 100 usec, leading + // to a maximum delay of 10 msec. + iatDelta := time.Duration(conn.iatDist.Sample() * 100) + + // Write then sleep. + _, err = conn.Conn.Write(iatFrame[:iatWrLen]) + if err != nil { + return 0, err + } + time.Sleep(iatDelta * time.Microsecond) + } + } else { + _, err = conn.Conn.Write(frameBuf.Bytes()) + } + + return +} + +func (conn *obfs4Conn) SetDeadline(t time.Time) error { + return syscall.ENOTSUP +} + +func (conn *obfs4Conn) SetWriteDeadline(t time.Time) error { + return syscall.ENOTSUP +} + +func (conn *obfs4Conn) closeAfterDelay(sf *obfs4ServerFactory, startTime time.Time) { + // I-it's not like I w-wanna handshake with you or anything. B-b-baka! + defer conn.Conn.Close() + + delay := time.Duration(sf.closeDelay)*time.Second + serverHandshakeTimeout + deadline := startTime.Add(delay) + if time.Now().After(deadline) { + return + } + + if err := conn.Conn.SetReadDeadline(deadline); err != nil { + return + } + + // Consume and discard data on this connection until either the specified + // interval passes or a certain size has been reached. + discarded := 0 + var buf [framing.MaximumSegmentLength]byte + for discarded < int(sf.closeDelayBytes) { + n, err := conn.Conn.Read(buf[:]) + if err != nil { + return + } + discarded += n + } +} + +func (conn *obfs4Conn) padBurst(burst *bytes.Buffer) (err error) { + tailLen := burst.Len() % framing.MaximumSegmentLength + toPadTo := conn.lenDist.Sample() + + padLen := 0 + if toPadTo >= tailLen { + padLen = toPadTo - tailLen + } else { + padLen = (framing.MaximumSegmentLength - tailLen) + toPadTo + } + + if padLen > headerLength { + err = conn.makePacket(burst, packetTypePayload, []byte{}, + uint16(padLen-headerLength)) + if err != nil { + return + } + } else if padLen > 0 { + err = conn.makePacket(burst, packetTypePayload, []byte{}, + maxPacketPayloadLength) + if err != nil { + return + } + err = conn.makePacket(burst, packetTypePayload, []byte{}, + uint16(padLen)) + if err != nil { + return + } + } + + return +} + +var _ base.ClientFactory = (*obfs4ClientFactory)(nil) +var _ base.ServerFactory = (*obfs4ServerFactory)(nil) +var _ base.Transport = (*Transport)(nil) +var _ net.Conn = (*obfs4Conn)(nil) diff --git a/transports/obfs4/packet.go b/transports/obfs4/packet.go new file mode 100644 index 0000000..9865c82 --- /dev/null +++ b/transports/obfs4/packet.go @@ -0,0 +1,179 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 ( + "crypto/sha256" + "encoding/binary" + "fmt" + "io" + + "git.torproject.org/pluggable-transports/obfs4.git/common/drbg" + "git.torproject.org/pluggable-transports/obfs4.git/transports/obfs4/framing" +) + +const ( + packetOverhead = 2 + 1 + maxPacketPayloadLength = framing.MaximumFramePayloadLength - packetOverhead + maxPacketPaddingLength = maxPacketPayloadLength + seedPacketPayloadLength = seedLength + + consumeReadSize = framing.MaximumSegmentLength * 16 +) + +const ( + packetTypePayload = iota + packetTypePrngSeed +) + +// InvalidPacketLengthError is the error returned when decodePacket detects a +// invalid packet length/ +type InvalidPacketLengthError int + +func (e InvalidPacketLengthError) Error() string { + return fmt.Sprintf("packet: Invalid packet length: %d", int(e)) +} + +// InvalidPayloadLengthError is the error returned when decodePacket rejects the +// payload length. +type InvalidPayloadLengthError int + +func (e InvalidPayloadLengthError) Error() string { + return fmt.Sprintf("packet: Invalid payload length: %d", int(e)) +} + +var zeroPadBytes [maxPacketPaddingLength]byte + +func (conn *obfs4Conn) makePacket(w io.Writer, pktType uint8, data []byte, padLen uint16) (err error) { + var pkt [framing.MaximumFramePayloadLength]byte + + if len(data)+int(padLen) > maxPacketPayloadLength { + panic(fmt.Sprintf("BUG: makePacket() len(data) + padLen > maxPacketPayloadLength: %d + %d > %d", + len(data), padLen, maxPacketPayloadLength)) + } + + // Packets are: + // uint8_t type packetTypePayload (0x00) + // uint16_t length Length of the payload (Big Endian). + // uint8_t[] payload Data payload. + // uint8_t[] padding Padding. + pkt[0] = pktType + binary.BigEndian.PutUint16(pkt[1:], uint16(len(data))) + if len(data) > 0 { + copy(pkt[3:], data[:]) + } + copy(pkt[3+len(data):], zeroPadBytes[:padLen]) + + pktLen := packetOverhead + len(data) + int(padLen) + + // Encode the packet in an AEAD frame. + var frame [framing.MaximumSegmentLength]byte + frameLen := 0 + frameLen, err = conn.encoder.Encode(frame[:], pkt[:pktLen]) + if err != nil { + // All encoder errors are fatal. + return + } + var wrLen int + wrLen, err = w.Write(frame[:frameLen]) + if err != nil { + return + } else if wrLen < frameLen { + err = io.ErrShortWrite + return + } + + return +} + +func (conn *obfs4Conn) readPackets() (err error) { + // Attempt to read off the network. + var buf [consumeReadSize]byte + rdLen, rdErr := conn.Conn.Read(buf[:]) + conn.receiveBuffer.Write(buf[:rdLen]) + + var decoded [framing.MaximumFramePayloadLength]byte + for conn.receiveBuffer.Len() > 0 { + // Decrypt an AEAD frame. + decLen := 0 + decLen, err = conn.decoder.Decode(decoded[:], conn.receiveBuffer) + if err == framing.ErrAgain { + break + } else if err != nil { + break + } else if decLen < packetOverhead { + err = InvalidPacketLengthError(decLen) + break + } + + // Decode the packet. + pkt := decoded[0:decLen] + pktType := pkt[0] + payloadLen := binary.BigEndian.Uint16(pkt[1:]) + if int(payloadLen) > len(pkt)-packetOverhead { + err = InvalidPayloadLengthError(int(payloadLen)) + break + } + payload := pkt[3 : 3+payloadLen] + + switch pktType { + case packetTypePayload: + if payloadLen > 0 { + conn.receiveDecodedBuffer.Write(payload) + } + case packetTypePrngSeed: + // Only regenerate the distribution if we are the client. + if len(payload) == seedPacketPayloadLength && !conn.isServer { + var seed *drbg.Seed + seed, err = drbg.SeedFromBytes(payload) + if err != nil { + break + } + conn.lenDist.Reset(seed) + if conn.iatDist != nil { + iatSeedSrc := sha256.Sum256(seed.Bytes()[:]) + iatSeed, err := drbg.SeedFromBytes(iatSeedSrc[:]) + if err != nil { + break + } + conn.iatDist.Reset(iatSeed) + } + } + default: + // Ignore unknown packet types. + } + } + + // Read errors (all fatal) take priority over various frame processing + // errors. + if rdErr != nil { + return rdErr + } + + return +} diff --git a/transports/obfs4/statefile.go b/transports/obfs4/statefile.go new file mode 100644 index 0000000..814a545 --- /dev/null +++ b/transports/obfs4/statefile.go @@ -0,0 +1,156 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 ( + "encoding/base64" + "encoding/json" + "fmt" + "io/ioutil" + "os" + "path" + + "git.torproject.org/pluggable-transports/goptlib.git" + "git.torproject.org/pluggable-transports/obfs4.git/common/csrand" + "git.torproject.org/pluggable-transports/obfs4.git/common/drbg" + "git.torproject.org/pluggable-transports/obfs4.git/common/ntor" +) + +const ( + stateFile = "obfs4_state.json" +) + +type jsonServerState struct { + NodeID string `json:"node-id"` + PrivateKey string `json:"private-key"` + PublicKey string `json:"public-key"` + DrbgSeed string `json:"drbgSeed"` +} + +type obfs4ServerState struct { + nodeID *ntor.NodeID + identityKey *ntor.Keypair + drbgSeed *drbg.Seed +} + +func serverStateFromArgs(stateDir string, args *pt.Args) (*obfs4ServerState, error) { + var js jsonServerState + var nodeIDOk, privKeyOk, seedOk bool + + js.NodeID, nodeIDOk = args.Get(nodeIDArg) + js.PrivateKey, privKeyOk = args.Get(privateKeyArg) + js.DrbgSeed, seedOk = args.Get(seedArg) + + if !privKeyOk && !nodeIDOk && !seedOk { + if err := jsonServerStateFromFile(stateDir, &js); err != nil { + return nil, err + } + } else if !privKeyOk { + return nil, fmt.Errorf("missing argument '%s'", privateKeyArg) + } else if !nodeIDOk { + return nil, fmt.Errorf("missing argument '%s'", nodeIDArg) + } else if !seedOk { + return nil, fmt.Errorf("missing argument '%s'", seedArg) + } + + return serverStateFromJSONServerState(&js) +} + +func serverStateFromJSONServerState(js *jsonServerState) (*obfs4ServerState, error) { + var err error + + st := new(obfs4ServerState) + if st.nodeID, err = ntor.NodeIDFromBase64(js.NodeID); err != nil { + return nil, err + } + if st.identityKey, err = ntor.KeypairFromBase64(js.PrivateKey); err != nil { + return nil, err + } + var rawSeed []byte + if rawSeed, err = base64.StdEncoding.DecodeString(js.DrbgSeed); err != nil { + return nil, err + } + if st.drbgSeed, err = drbg.SeedFromBytes(rawSeed); err != nil { + return nil, err + } + + return st, nil +} + +func jsonServerStateFromFile(stateDir string, js *jsonServerState) error { + f, err := ioutil.ReadFile(path.Join(stateDir, stateFile)) + if err != nil { + if os.IsNotExist(err) { + if err = newJSONServerState(stateDir, js); err == nil { + return nil + } + } + return err + } + + if err = json.Unmarshal(f, js); err != nil { + return err + } + + return nil +} + +func newJSONServerState(stateDir string, js *jsonServerState) (err error) { + // Generate everything a server needs, using the cryptographic PRNG. + var st obfs4ServerState + rawID := make([]byte, ntor.NodeIDLength) + if err = csrand.Bytes(rawID); err != nil { + return + } + if st.nodeID, err = ntor.NewNodeID(rawID); err != nil { + return + } + if st.identityKey, err = ntor.NewKeypair(false); err != nil { + return + } + if st.drbgSeed, err = drbg.NewSeed(); err != nil { + return + } + + // Encode it into JSON format and write the state file. + js.NodeID = st.nodeID.Base64() + js.PrivateKey = st.identityKey.Private().Base64() + js.PublicKey = st.identityKey.Public().Base64() + js.DrbgSeed = st.drbgSeed.Base64() + + var encoded []byte + if encoded, err = json.Marshal(js); err != nil { + return + } + + if err = ioutil.WriteFile(path.Join(stateDir, stateFile), encoded, 0600); err != nil { + return err + } + + return nil +} diff --git a/transports/transports.go b/transports/transports.go new file mode 100644 index 0000000..6b80bdc --- /dev/null +++ b/transports/transports.go @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> + * 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 transports provides a interface to query supported pluggable +// transports. +package transports + +import ( + "fmt" + "sync" + + "git.torproject.org/pluggable-transports/obfs4.git/transports/base" + "git.torproject.org/pluggable-transports/obfs4.git/transports/obfs2" + "git.torproject.org/pluggable-transports/obfs4.git/transports/obfs3" + "git.torproject.org/pluggable-transports/obfs4.git/transports/obfs4" +) + +var transportMapLock sync.Mutex +var transportMap map[string]base.Transport + +// Register registers a transport protocol. +func Register(transport base.Transport) error { + transportMapLock.Lock() + defer transportMapLock.Unlock() + + name := transport.Name() + _, registered := transportMap[name] + if registered { + return fmt.Errorf("transport '%s' already registered", name) + } + transportMap[name] = transport + + return nil +} + +// Transports returns the list of registered transport protocols. +func Transports() []string { + transportMapLock.Lock() + defer transportMapLock.Unlock() + + var ret []string + for name := range transportMap { + ret = append(ret, name) + } + + return ret +} + +// Get returns a transport protocol implementation by name. +func Get(name string) base.Transport { + transportMapLock.Lock() + defer transportMapLock.Unlock() + + t := transportMap[name] + + return t +} + +func init() { + // Initialize the transport list. + transportMap = make(map[string]base.Transport) + + // Register all the currently supported transports. + Register(new(obfs2.Transport)) + Register(new(obfs3.Transport)) + Register(new(obfs4.Transport)) +} diff --git a/weighted_dist.go b/weighted_dist.go deleted file mode 100644 index 4f1f2a5..0000000 --- a/weighted_dist.go +++ /dev/null @@ -1,212 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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" - "fmt" - "math/rand" - - "git.torproject.org/pluggable-transports/obfs4.git/csrand" - "git.torproject.org/pluggable-transports/obfs4.git/drbg" -) - -const ( - minValues = 1 - maxValues = 100 -) - -// wDist is a weighted distribution. -type wDist struct { - minValue int - maxValue int - values []int - weights []float64 - - alias []int - prob []float64 -} - -// newWDist creates a weighted distribution of values ranging from min to max -// based on a HashDrbg initialized with seed. -func newWDist(seed *drbg.Seed, min, max int) (w *wDist) { - w = &wDist{minValue: min, maxValue: max} - - if max <= min { - panic(fmt.Sprintf("wDist.Reset(): min >= max (%d, %d)", min, max)) - } - - w.reset(seed) - - return -} - -// genValues creates a slice containing a random number of random values -// that when scaled by adding minValue will fall into [min, max]. -func (w *wDist) genValues(rng *rand.Rand) { - nValues := (w.maxValue + 1) - w.minValue - values := rng.Perm(nValues) - if nValues < minValues { - nValues = minValues - } - if nValues > maxValues { - nValues = maxValues - } - nValues = rng.Intn(nValues) + 1 - w.values = values[:nValues] -} - -// genBiasedWeights generates a non-uniform weight list, similar to the -// ScrambleSuit prob_dist module. -func (w *wDist) genBiasedWeights(rng *rand.Rand) { - w.weights = make([]float64, len(w.values)) - - culmProb := 0.0 - for i := range w.values { - p := (1.0 - culmProb) * rng.Float64() - w.weights[i] = p - culmProb += p - } -} - -// genUniformWeights generates a uniform weight list. -func (w *wDist) genUniformWeights(rng *rand.Rand) { - w.weights = make([]float64, len(w.values)) - for i := range w.weights { - w.weights[i] = rng.Float64() - } -} - -// genTables calculates the alias and prob tables used for Vose's Alias method. -// Algorithm taken from http://www.keithschwarz.com/darts-dice-coins/ -func (w *wDist) genTables() { - n := len(w.weights) - var sum float64 - for _, weight := range w.weights { - sum += weight - } - - // Create arrays $Alias$ and $Prob$, each of size $n$. - alias := make([]int, n) - prob := make([]float64, n) - - // Create two worklists, $Small$ and $Large$. - small := list.New() - large := list.New() - - scaled := make([]float64, n) - for i, weight := range w.weights { - // Multiply each probability by $n$. - p_i := weight * float64(n) / sum - scaled[i] = p_i - - // For each scaled probability $p_i$: - if scaled[i] < 1.0 { - // If $p_i < 1$, add $i$ to $Small$. - small.PushBack(i) - } else { - // Otherwise ($p_i \ge 1$), add $i$ to $Large$. - large.PushBack(i) - } - } - - // While $Small$ and $Large$ are not empty: ($Large$ might be emptied first) - for small.Len() > 0 && large.Len() > 0 { - // Remove the first element from $Small$; call it $l$. - l := small.Remove(small.Front()).(int) - // Remove the first element from $Large$; call it $g$. - g := large.Remove(large.Front()).(int) - - // Set $Prob[l] = p_l$. - prob[l] = scaled[l] - // Set $Alias[l] = g$. - alias[l] = g - - // Set $p_g := (p_g + p_l) - 1$. (This is a more numerically stable option.) - scaled[g] = (scaled[g] + scaled[l]) - 1.0 - - if scaled[g] < 1.0 { - // If $p_g < 1$, add $g$ to $Small$. - small.PushBack(g) - } else { - // Otherwise ($p_g \ge 1$), add $g$ to $Large$. - large.PushBack(g) - } - } - - // While $Large$ is not empty: - for large.Len() > 0 { - // Remove the first element from $Large$; call it $g$. - g := large.Remove(large.Front()).(int) - // Set $Prob[g] = 1$. - prob[g] = 1.0 - } - - // While $Small$ is not empty: This is only possible due to numerical instability. - for small.Len() > 0 { - // Remove the first element from $Small$; call it $l$. - l := small.Remove(small.Front()).(int) - // Set $Prob[l] = 1$. - prob[l] = 1.0 - } - - w.prob = prob - w.alias = alias -} - -// reset generates a new distribution with the same min/max based on a new seed. -func (w *wDist) reset(seed *drbg.Seed) { - // Initialize the deterministic random number generator. - drbg := drbg.NewHashDrbg(seed) - rng := rand.New(drbg) - - w.genValues(rng) - //w.genBiasedWeights(rng) - w.genUniformWeights(rng) - w.genTables() -} - -// sample generates a random value according to the distribution. -func (w *wDist) sample() int { - var idx int - - // Generate a fair die roll from an $n$-sided die; call the side $i$. - i := csrand.Intn(len(w.values)) - // Flip a biased coin that comes up heads with probability $Prob[i]$. - if csrand.Float64() <= w.prob[i] { - // If the coin comes up "heads," return $i$. - idx = i - } else { - // Otherwise, return $Alias[i]$. - idx = w.alias[i] - } - - return w.minValue + w.values[idx] -} - -/* vim :set ts=4 sw=4 sts=4 noet : */ diff --git a/weighted_dist_test.go b/weighted_dist_test.go deleted file mode 100644 index 16b93c4..0000000 --- a/weighted_dist_test.go +++ /dev/null @@ -1,82 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel <yawning at torproject dot org> - * 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 ( - "fmt" - "testing" - - "git.torproject.org/pluggable-transports/obfs4.git/drbg" -) - -const debug = false - -func TestWeightedDist(t *testing.T) { - seed, err := drbg.NewSeed() - if err != nil { - t.Fatal("failed to generate a DRBG seed:", err) - } - - const nrTrials = 1000000 - - hist := make([]int, 1000) - - w := newWDist(seed, 0, 999) - if debug { - // Dump a string representation of the probability table. - fmt.Println("Table:") - var sum float64 - for _, weight := range w.weights { - sum += weight - } - for i, weight := range w.weights { - p := weight / sum - if p > 0.000001 { // Filter out tiny values. - fmt.Printf(" [%d]: %f\n", w.minValue+w.values[i], p) - } - } - fmt.Println() - } - - for i := 0; i < nrTrials; i++ { - value := w.sample() - hist[value]++ - } - - if debug { - fmt.Println("Generated:") - for value, count := range hist { - if count != 0 { - p := float64(count) / float64(nrTrials) - fmt.Printf(" [%d]: %f (%d)\n", value, p, count) - } - } - } -} - -/* vim :set ts=4 sw=4 sts=4 noet : */