From 339c63f0c8cd4374f6fa26484498eb6fa91b7bca Mon Sep 17 00:00:00 2001 From: Yawning Angel Date: Sun, 17 Aug 2014 17:11:03 +0000 Subject: 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). --- 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 +++++++++++++++ 10 files changed, 1807 insertions(+) create mode 100644 common/csrand/csrand.go create mode 100644 common/drbg/hash_drbg.go create mode 100644 common/ntor/ntor.go create mode 100644 common/ntor/ntor_test.go create mode 100644 common/probdist/weighted_dist.go create mode 100644 common/probdist/weighted_dist_test.go create mode 100644 common/replayfilter/replay_filter.go create mode 100644 common/replayfilter/replay_filter_test.go create mode 100644 common/uniformdh/uniformdh.go create mode 100644 common/uniformdh/uniformdh_test.go (limited to 'common') 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 + * 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 + * 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 + * 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 + * 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 + * 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 + * 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 + * 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 + * 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 + * 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 + * 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") + } +} -- cgit v1.2.3