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/uniformdh/uniformdh.go | 183 ++++++++++++++++++++++++++++++ common/uniformdh/uniformdh_test.go | 220 +++++++++++++++++++++++++++++++++++++ 2 files changed, 403 insertions(+) create mode 100644 common/uniformdh/uniformdh.go create mode 100644 common/uniformdh/uniformdh_test.go (limited to 'common/uniformdh') 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