Initial import.

2 files changed, 617 insertions, 0 deletions

diff --git a/ntor/ntor.go b/ntor/ntor.go
new file mode 100644
index 0000000..da6dae4
--- /dev/null
+++ b/ntor/ntor.go
@@ -0,0 +1,435 @@
+/*
+ * 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/rand"
+	"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"
+)
+
+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)
+}
+
+// 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 := rand.Read(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
+	}
+}
+
+// LoadKeypair takes an existing Curve25519 private key from a buffer and
+// creates a Keypair including the public key.
+
+// 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) (bool, *KeySeed, *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) (bool, *KeySeed, *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
new file mode 100644
index 0000000..9d7c687
--- /dev/null
+++ b/ntor/ntor_test.go
@@ -0,0 +1,182 @@
+/*
+ * 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 : */