Add preliminary support for packet length obfuscation.

The same algorithm as ScrambleSuit is used, except:
 * SipHash-2-4 in OFB mode is used to create the distribution.
 * The system CSPRNG is used when sampling the distribution.

This fixes most of #3, all that remains is generating and sending a
persistent distribution on the server side to the client.

6 files changed, 273 insertions, 37 deletions

diff --git a/README.md b/README.md
index ef38532..549e27c 100644
--- a/README.md
+++ b/README.md
@@ -17,7 +17,7 @@ is much closer to ScrambleSuit than obfs2/obfs3.
 The notable differences between ScrambleSuit and obfs4:
 
  * The handshake always does a full key exchange (no such thing as a Session
-   Ticket Handshake). (TODO: Reconsider this.)
+   Ticket Handshake).
  * The handshake uses the Tor Project's ntor handshake with public keys
    obfuscated via the Elligator mapping.
  * The link layer encryption uses NaCl secret boxes (Poly1305/XSalsa20).
@@ -32,7 +32,6 @@ handshake variants without being obscenely slow is non-trivial.
 
 ### TODO
 
- * Packet length obfuscation.
  * (Maybe) Make it resilient to transient connection loss.
  * (Maybe) Use IP_MTU/TCP_MAXSEG to tweak frame size.
  * Write a detailed protocol spec.
diff --git a/handshake_ntor.go b/handshake_ntor.go
index ea9de71..84cd93c 100644
--- a/handshake_ntor.go
+++ b/handshake_ntor.go
@@ -363,13 +363,10 @@ func findMark(mark, buf []byte, startPos, maxPos int) int {
 	return pos + startPos
 }
 
-func makePad(min, max int64) ([]byte, error) {
-	padLen, err := randRange(min, max)
-	if err != nil {
-		return nil, err
-	}
+func makePad(min, max int) ([]byte, error) {
+	padLen := randRange(min, max)
 	pad := make([]byte, padLen)
-	_, err = rand.Read(pad)
+	_, err := rand.Read(pad)
 	if err != nil {
 		return nil, err
 	}
diff --git a/obfs4.go b/obfs4.go
index e69c7b7..cd6f75d 100644
--- a/obfs4.go
+++ b/obfs4.go
@@ -40,6 +40,7 @@ import (
 )
 
 const (
+	headerLength      = framing.FrameOverhead + packetOverhead
 	defaultReadSize   = framing.MaximumSegmentLength
 	connectionTimeout = time.Duration(15) * time.Second
 
@@ -54,6 +55,8 @@ const (
 type Obfs4Conn struct {
 	conn net.Conn
 
+	probDist *wDist
+
 	encoder *framing.Encoder
 	decoder *framing.Decoder
 
@@ -67,22 +70,33 @@ type Obfs4Conn struct {
 	listener *Obfs4Listener
 }
 
+func (c *Obfs4Conn) calcPadLen(burstLen int) int {
+	tailLen := burstLen % framing.MaximumSegmentLength
+	toPadTo := c.probDist.sample()
+
+	ret := 0
+	if toPadTo >= tailLen {
+		ret = toPadTo - tailLen
+	} else {
+		ret = (framing.MaximumSegmentLength - tailLen) + toPadTo
+	}
+
+	return ret
+}
+
 func (c *Obfs4Conn) closeAfterDelay() {
 	// I-it's not like I w-wanna handshake with you or anything.  B-b-baka!
 	defer c.conn.Close()
 
-	delaySecs, err := randRange(minCloseInterval, maxCloseInterval)
-	if err != nil {
-		return
-	}
-	toDiscard, err := randRange(minCloseThreshold, maxCloseThreshold)
+	delaySecs := randRange(minCloseInterval, maxCloseInterval)
+	toDiscard := randRange(minCloseThreshold, maxCloseThreshold)
+
+	delay := time.Duration(delaySecs) * time.Second
+	err := c.conn.SetReadDeadline(time.Now().Add(delay))
 	if err != nil {
 		return
 	}
 
-	delay := time.Duration(delaySecs) * time.Second
-	err = c.conn.SetReadDeadline(time.Now().Add(delay))
-
 	// Consume and discard data on this connection until either the specified
 	// interval passes or a certain size has been reached.
 	discarded := 0
@@ -286,7 +300,6 @@ func (c *Obfs4Conn) Read(b []byte) (int, error) {
 func (c *Obfs4Conn) Write(b []byte) (int, error) {
 	chopBuf := bytes.NewBuffer(b)
 	buf := make([]byte, maxPacketPayloadLength)
-	pkt := make([]byte, framing.MaximumFramePayloadLength)
 	nSent := 0
 	var frameBuf bytes.Buffer
 
@@ -295,26 +308,52 @@ func (c *Obfs4Conn) Write(b []byte) (int, error) {
 		n, err := chopBuf.Read(buf)
 		if err != nil {
 			c.isOk = false
-			return nSent, err
+			return 0, err
 		} else if n == 0 {
 			panic(fmt.Sprintf("BUG: Write(), chopping length was 0"))
 		}
 		nSent += n
 
-		// Wrap the payload in a packet.
-		n = makePacket(pkt[:], packetTypePayload, buf[:n], 0)
-
-		// Encode the packet in an AEAD frame.
-		_, frame, err := c.encoder.Encode(pkt[:n])
+		_, frame, err := c.makeAndEncryptPacket(packetTypePayload, buf[:n], 0)
 		if err != nil {
 			c.isOk = false
-			return nSent, err
+			return 0, err
 		}
 
 		frameBuf.Write(frame)
 	}
 
-	// TODO: Insert random padding.
+	// Insert random padding.  In theory it's possible to inline padding for
+	// certain framesizes into the last AEAD packet, but always sending 1 or 2
+	// padding frames is considerably easier.
+	padLen := c.calcPadLen(frameBuf.Len())
+	if padLen > 0 {
+		if padLen > headerLength {
+			_, frame, err := c.makeAndEncryptPacket(packetTypePayload, []byte{},
+				uint16(padLen-headerLength))
+			if err != nil {
+				c.isOk = false
+				return 0, err
+			}
+			frameBuf.Write(frame)
+		} else {
+			_, frame, err := c.makeAndEncryptPacket(packetTypePayload, []byte{},
+				maxPacketPayloadLength)
+			if err != nil {
+				c.isOk = false
+				return 0, err
+			}
+			frameBuf.Write(frame)
+
+			_, frame, err = c.makeAndEncryptPacket(packetTypePayload, []byte{},
+				uint16(padLen))
+			if err != nil {
+				c.isOk = false
+				return 0, err
+			}
+			frameBuf.Write(frame)
+		}
+	}
 
 	// Send the frame(s).
 	_, err := c.conn.Write(frameBuf.Bytes())
@@ -323,7 +362,7 @@ func (c *Obfs4Conn) Write(b []byte) (int, error) {
 		// at this point.  It's possible to keep frameBuf around, but fuck it.
 		// Someone that wants write timeouts can change this.
 		c.isOk = false
-		return nSent, err // XXX: nSent is a dirty lie here.
+		return 0, err
 	}
 
 	return nSent, nil
@@ -384,6 +423,10 @@ func Dial(network, address, nodeID, publicKey string) (net.Conn, error) {
 
 	// Connect to the peer.
 	c := new(Obfs4Conn)
+	c.probDist, err = newWDist(nil, 0, framing.MaximumSegmentLength)
+	if err != nil {
+		return nil, err
+	}
 	c.conn, err = net.Dial(network, address)
 	if err != nil {
 		return nil, err
@@ -420,6 +463,11 @@ func (l *Obfs4Listener) Accept() (net.Conn, error) {
 	cObfs.conn = c
 	cObfs.isServer = true
 	cObfs.listener = l
+	cObfs.probDist, err = newWDist(nil, 0, framing.MaximumSegmentLength)
+	if err != nil {
+		c.Close()
+		return nil, err
+	}
 
 	return cObfs, nil
 }
diff --git a/packet.go b/packet.go
index afccc47..7bf4a6c 100644
--- a/packet.go
+++ b/packet.go
@@ -79,12 +79,25 @@ func makePacket(pkt []byte, pktType uint8, data []byte, padLen uint16) int {
 
 	pkt[0] = pktType
 	binary.BigEndian.PutUint16(pkt[1:], uint16(len(data)))
-	copy(pkt[3:], data[:])
+	if len(data) > 0 {
+		copy(pkt[3:], data[:])
+	}
 	copy(pkt[3+len(data):], zeroPadBytes[:padLen])
 
 	return pktLen
 }
 
+func (c *Obfs4Conn) makeAndEncryptPacket(pktType uint8, data []byte, padLen uint16) (int, []byte, error) {
+	var pkt [framing.MaximumFramePayloadLength]byte
+
+	// Wrap the payload in a packet.
+	n := makePacket(pkt[:], pktType, data[:], padLen)
+
+	// Encode the packet in an AEAD frame.
+	n, frame, err := c.encoder.Encode(pkt[:n])
+	return n, frame, err
+}
+
 func (c *Obfs4Conn) decodePacket(pkt []byte) error {
 	if len(pkt) < packetOverhead {
 		return InvalidPacketLengthError(len(pkt))
@@ -99,8 +112,13 @@ func (c *Obfs4Conn) decodePacket(pkt []byte) error {
 	payload := pkt[3 : 3+payloadLen]
 	switch pktType {
 	case packetTypePayload:
-		// packetTypePayload
-		c.receiveDecodedBuffer.Write(payload)
+		if len(payload) > 0 {
+			c.receiveDecodedBuffer.Write(payload)
+		}
+	case packetTypePrngSeed:
+		if len(payload) == distSeedLength {
+			c.probDist.reset(payload)
+		}
 	default:
 		// Ignore unrecognised packet types.
 	}
diff --git a/utils.go b/utils.go
index ae7bc41..600a925 100644
--- a/utils.go
+++ b/utils.go
@@ -28,21 +28,40 @@
 package obfs4
 
 import (
-	"crypto/rand"
+	csrand "crypto/rand"
 	"fmt"
 	"math/big"
+	"math/rand"
 )
 
-func randRange(min, max int64) (int64, error) {
+var (
+	csRandSourceInstance csRandSource
+	csRandInstance       = rand.New(csRandSourceInstance)
+)
+
+type csRandSource struct {
+	// This does not keep any state as it is backed by crypto/rand.
+}
+
+func (r csRandSource) Int63() int64 {
+	ret, err := csrand.Int(csrand.Reader, big.NewInt(int64((1<<63)-1)))
+	if err != nil {
+		panic(err)
+	}
+
+	return ret.Int64()
+}
+
+func (r csRandSource) Seed(seed int64) {
+	// No-op.
+}
+
+func randRange(min, max int) int {
 	if max < min {
 		panic(fmt.Sprintf("randRange: min > max (%d, %d)", min, max))
 	}
 
 	r := (max + 1) - min
-	ret, err := rand.Int(rand.Reader, big.NewInt(r))
-	if err != nil {
-		return 0, err
-	}
-
-	return ret.Int64() + min, nil
+	ret := csRandInstance.Intn(r)
+	return ret + min
 }
diff --git a/weighted_dist.go b/weighted_dist.go
new file mode 100644
index 0000000..2fd39a0
--- /dev/null
+++ b/weighted_dist.go
@@ -0,0 +1,155 @@
+/*
+ * Copyright (c) 2014, Yawning Angel <yawning at schwanenlied dot me>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *  * Redistributions of source code must retain the above copyright notice,
+ *    this list of conditions and the following disclaimer.
+ *
+ *  * Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package obfs4
+
+import (
+	csrand "crypto/rand"
+	"encoding/binary"
+	"fmt"
+	"hash"
+	"math/rand"
+
+	"github.com/dchest/siphash"
+)
+
+const distSeedLength = 16
+
+// 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("hashDrbg: 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 [siphash.Size]byte
+}
+
+// newHashDrbg makes a hashDrbg instance based off an optional seed.  The seed
+// is truncated to distSeedLength.
+func newHashDrbg(seed []byte) *hashDrbg {
+	drbg := new(hashDrbg)
+	drbg.sip = siphash.New(seed)
+
+	return drbg
+}
+
+// Int63 returns a uniformly distributed random integer [0, 1 << 63).
+func (drbg *hashDrbg) Int63() int64 {
+	// Use SipHash-2-4 in OFB mode to generate random numbers.
+	drbg.sip.Write(drbg.ofb[:])
+	copy(drbg.ofb[:], drbg.sip.Sum(nil))
+
+	ret := binary.BigEndian.Uint64(drbg.ofb[:])
+	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.
+}
+
+// wDist is a weighted distribution.
+type wDist struct {
+	minValue int
+	maxValue int
+	values   []int
+	buckets  []float64
+}
+
+// newWDist creates a weighted distribution of values ranging from min to max
+// based on a CSDRBG initialized with the optional 128 bit seed.
+func newWDist(seed []byte, min, max int) (*wDist, error) {
+	w := new(wDist)
+	w.minValue = min
+	w.maxValue = max
+
+	if max <= min {
+		panic(fmt.Sprintf("wDist.Reset(): min >= max (%d, %d)", min, max))
+	}
+
+	err := w.reset(seed)
+	if err != nil {
+		return nil, err
+	}
+
+	return w, nil
+}
+
+// sample generates a random value according to the distribution.
+func (w *wDist) sample() int {
+	retIdx := 0
+	totalProb := 0.0
+	prob := csRandInstance.Float64()
+	for i, bucketProb := range w.buckets {
+		totalProb += bucketProb
+		if prob <= totalProb {
+			retIdx = i
+			break
+		}
+	}
+
+	return w.minValue + w.values[retIdx]
+}
+
+// reset generates a new distribution with the same min/max based on a new seed.
+func (w *wDist) reset(seed []byte) error {
+	if seed == nil {
+		seed = make([]byte, distSeedLength)
+		_, err := csrand.Read(seed)
+		if err != nil {
+			return err
+		}
+	}
+	if len(seed) != distSeedLength {
+		return InvalidSeedLengthError(len(seed))
+	}
+
+	// Initialize the deterministic random number generator.
+	drbg := newHashDrbg(seed)
+	dRng := rand.New(drbg)
+
+	nBuckets := (w.maxValue + 1) - w.minValue
+	w.values = dRng.Perm(nBuckets)
+
+	w.buckets = make([]float64, nBuckets)
+	var totalProb float64
+	for i, _ := range w.buckets {
+		prob := dRng.Float64() * (1.0 - totalProb)
+		w.buckets[i] = prob
+		totalProb += prob
+	}
+	w.buckets[len(w.buckets)-1] = 1.0
+
+	return nil
+}