ScrambleSuit Protocol Specification Philipp Winter 0. Preliminaries The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. 1. Overview ScrambleSuit is a pluggable transport protocol for the obfsproxy obfuscation framework [0]. Its entire payload is computationally indistinguishable from randomness, it modifies its flow signature to foil simple statistical classifiers and it employs authenticated encryption to disguise the transported protocol. For the motivation, a protocol overview, the threat model and an evaluation, please refer to the original research paper [1]. This protocol specification discusses a subset of the research paper in greater detail to facilitate alternative implementations of the protocol. Besides, this specification is intended to be updated if necessary whereas the research paper will remain as is. 2. Authentication There exist two ways for a client to authenticate itself towards a ScrambleSuit server. First, by redeeming a session ticket. Second, by conducting a UniformDH handshake. While a valid session ticket might not always be available, a client is always able to conduct a UniformDH handshake. Both authentication mechanisms rely on a previously shared secret without which authentication cannot succeed. Requiring a shared secret should thwart active probing attacks. As stated in the research paper [1], a server only replies to a client if the client can prove knowledge of the shared secret. As long as clients cannot prove knowledge of the shared secret, servers MUST NOT reply. If authentication did not succeed after 1532 bytes have been received, the server SHOULD stop processing incoming data to prevent denial-of-service attacks. The server MAY close the TCP connection. Alternatively, the server MAY proceed to accept data but it SHOULD stop buffering or processing the data, thus effectively ignoring the client. 2.1 UniformDH Handshake A client can authenticate itself towards a ScrambleSuit server by conducting a UniformDH handshake. UniformDH was originally proposed in the obfs3 protocol specification [2]. ScrambleSuit uses obfs3's 1536-bit UniformDH handshake. Note that in order for a UniformDH handshake to succeed, both parties MUST share a 160-bit secret k_B which is exchanged out-of-band over Tor's BridgeDB component. ScrambleSuit bridges automatically publish their k_B key. A UniformDH handshake consists of two messages: one from the client to the server and one from the server to the client. The diagram below illustrates the handshake. After the randomly chosen 192-byte UniformDH public key X, random padding P_C is appended. The length of the padding must be randomly chosen from {0..1308} bytes. After the padding, a 16-byte mark M_C is appended which is defined as: M = HMAC-SHA256-128(k_B, X) The mark is used to easily locate the MAC which is the last element of the client's handshake message. The 16-byte MAC is defined as: MAC = HMAC-SHA256-128(k_B, X | P_C | M_C | E) The variable E is a string representation of the current Unix epoch divided by 3600. It represents the amount of hours which have passed since the epoch. It is used by the client and the server to prove liveness. For example, the Unix timestamp 1378768086 would map to E = 1378768086 / 3600 = "382991". While the client MUST determine E, the server can simply echo the client's E in its response. The server's handshake message is created analogous to the client. After conducting UniformDH, a client and server agreed on a 192-byte random number. This random number is then hashed using SHA256 to obtain the 256-bit master key k_t. Session keys are then derived from k_t as discussed in Section 2.3. Client Server Legend: | X | P_C | M_C | MAC(X | P_C | M_C | E) | X: client public key | ---------------------------------------> | Y: server public key | Y | P_S | M_S | MAC(Y | P_S | M_S | E) | P_{C,S}: padding | <--------------------------------------- | M_{C,S}: mark to locate MAC | AEnc(k_t+1 | T_t+1) | E: approximate timestamp | <--------------------------------------- | k_t+1: future master key | AEnc(Tor traffic) | T_t+1: future ticket | <--------------------------------------> | Immediately after the handshake succeeded, the server proceeds to issue and send a new session ticket T_t+1 together with the according master key k_t+1. Session tickets are discussed in Section 2.2. This tuple can then be used by the client to authenticate itself the next time it connects to the server. After the newly issued ticket, encrypted and authenticated Tor traffic is finally exchanged between the client and the server. 2.2 Session Ticket Handshake Alternatively to UniformDH, implementations SHOULD support session tickets. A client can authenticate itself towards a ScrambleSuit server by redeeming a 112-byte session ticket T. Such a ticket contains the master key k_t and is encrypted and authenticated using keys only known to the server. The structure of a session ticket is discussed in Section 5.1. If a valid session ticket is available, a client SHOULD redeem it rather than conduct a UniformDH handshake. The handshake consists of one single message which is sent by the client to the server. The diagram below illustrates the handshake. After the 112-byte session ticket, random padding P is appended. The padding must be uniformly chosen from {0..1388} bytes. After the padding, a 16-byte mark M is appended which is defined as: M = HMAC-SHA256-128(k_sh, T) The mark is used to easily locate the MAC which is the last part of the handshake. k_sh is the 256-bit HMAC key which is used by the client to authenticate outgoing data. It is derived from k_t (which is embedded in the ticket) as described in Section 2.3. The MAC is defined as: MAC = HMAC-SHA256-128(k_sh, T | P | M | E) The variable E is a string representation of the current Unix epoch divided by 3600. It represents the amount of hours which have passed since the epoch. It is used by the client and the server to prove liveness. For example, the Unix timestamp 1378768086 would map to E = 1378768086 / 3600 = "382991". While the client MUST determine E, the server can simply echo the client's E in its response. Client Server Legend: | T | P | M | MAC(T | P | M | E) | T: session ticket | -------------------------------> | P: random padding | AEnc(k_t+1 | T_t+1) | M: mark to locate the MAC | <------------------------------- | E: approximate timestamp | AEnc(Tor traffic) | k_t+1: future master key | <------------------------------> | T_t+1: future ticket The server is initially unable to distinguish between a session ticket handshake and a UniformDH handshake as both handshakes are computationally indistinguishable from randomness. Therefore, it first tries to opportunistically decrypt the session ticket T after verifying its MAC. If the ticket's MAC (which should not be confused with the handshake message's MAC) is valid and the ticket can be decrypted and is not yet expired, the server then verifies the MAC which is built over T | P | M | E. If this MAC is valid, the handshake succeeded. The server, like the client, then proceeds to derive session keys from the 256-bit master key as described in Section 2.3. After a ticket handshake succeeded, the server replies by issuing a new session ticket T_t+1 together with the according master key k_t+1. The tuple can then be used by the client to authenticate itself the next time. 2.3 Key Derivation After authenticating either by redeeming a ticket or by running UniformDH, a client and server will have a shared 256-bit master key. Overall, 144 bytes of key material is derived from the master key using HKDF based on SHA256. For expansion, the master key is used as HKDF's PRK and the empty string as HKDF's "info" argument. The 144-byte output is used as follows. The byte offsets are in decimal. Bytes 000:031 - 256-bit AES-CTR session key to send data. Bytes 032:039 - 64-bit AES-CTR IV to send data. Bytes 040:071 - 256-bit AES-CTR session key to receive data. Bytes 072:079 - 64-bit AES-CTR IV to receive data. Bytes 080:111 - 256-bit HMAC-SHA256-128 key to send data. Bytes 112:143 - 256-bit HMAC-SHA256-128 key to receive data. 3. Header Format ScrambleSuit defines a 21-byte message header which contains the transported data. After authentication, all data is transported by encrypting it, authenticating it, and wrapping it in ScrambleSuit messages whose header is depicted below. +----------+------------+--------------+--------+------------+------------+ | 16 bytes | 2 bytes | 2 bytes | 1 byte | (optional) | (optional) | | MAC | Total len. | Payload len. | Flags | Payload | Padding | +----------+------------+--------------+--------+------------+------------+ \_ Plain _/ \____________ Encrypted and authenticated __________________/ The 16-byte MAC refers to HMAC-SHA256-128 which is keyed by a dedicated HMAC key which is derived from the session's master key (see Section 2.3). The MAC authenticates the remainder of the message. In accordance with the encrypt-then-MAC principle, the MAC is built over the already-encrypted remainder of the message. The 2-byte total length refers to the overall length of the message excluding the header whereas the 2-byte payload length refers to the payload only. The difference between total length and payload length is padding which is used for packet length obfuscation. Note that both fields can be set to 0 which results in an empty protocol message. ScrambleSuit's maximum message length is 1448 bytes. Exluding the header, this results in 1427 bytes for the transported data. The 1-byte flag field is used for protocol signalling. Below, all defined flags along with their semantics are explained. Flag name | Bit # | Description ----------------+-------+-------------------------------------------------- FLAG_PAYLOAD | 1 | The entire payload consists of encrypted | | application data which must be forwarded to the | | application. ----------------+-------+-------------------------------------------------- FLAG_NEW_TICKET | 2 | The payload holds a newly issued session ticket | | and master key. The format is: | | 32-byte master key | 112-byte ticket ----------------+-------+-------------------------------------------------- FLAG_PRNG_SEED | 3 | The payload holds the PRNG seed which is used to | | derive obfuscation distributions. The format is: | | 32-byte PRNG seed ----------------+-------+-------------------------------------------------- Finally, a ScrambleSuit message contains the transported data which is followed by padding. Padding MUST always be discarded. Since padding is always encrypted, client and server MAY simply pad with 0 bytes. When ScrambleSuit protocol messages are received, the receiver first MUST validate the MAC. The receiver may only process messages if the MAC is valid. If the MAC is invalid, the TCP connection MUST be terminated immediately. 4. Protocol Polymorphism Implementations SHOULD implement protocol polymorphism whose purpose is to modify ScrambleSuit's flow signature. In particular, the packet length distribution and the distribution of inter-arrival times are modified. To alter these two flow signatures, implementations maintain two discrete probability distributions from which random samples are drawn. These random samples dictate specific inter-arrival times and packet lengths. Both probability distributions are generated based on a random 256-bit PRNG seed which is unique for every ScrambleSuit server. Servers communicate their seed to clients in a dedicated protocol message whose FLAG_PRNG_SEED bit is set. The client then extracts the PRNG seed and derives its own probability distributions. 4.1 Deriving Probability Distributions Probability distributions SHOULD be derived from the 256-bit seed using a cryptographically secure PRNG. After the CSPRNG was seeded, the amount of bins for the respective probability distribution must be determined. Depending on the CSPRNG's output, the amount SHOULD be uniformly chosen from {1..100}. The exact way how the CSPRNG's output is used is up to the implementation. After the amount of bins has been determined, every bin is assigned a value together with a corresponding probability which is in the interval ]0, 1]. The probability of all bins sums up to 1. Again, the exact way how the CSPRNG's output is used is up to the implementation. For the packet length distribution, all values SHOULD be in {21..1448}. For the inter-arrival time distribution, all values SHOULD be in the interval [0, 0.01]. Since the distributions are generated randomly, it is possible that they cause particularly bad throughput. To prevent this, implementations MAY trade off obfuscation for additional throughput by carefully tuning the above parameters. 4.2 Packet Length Obfuscation In general, ScrambleSuit transmits MTU-sized segments as long as there is enough data in the send buffer. Packet length obfuscation only kicks in once the send buffer is almost processed and a segment smaller than the MTU would have to be sent. Instead of simply flushing the send buffer, a random sample from the discrete packet length probability distribution is drawn. Padding messages are then appended so that the size of the last segment in the burst equals the freshly drawn sample. 4.3 Inter-arrival Time Obfuscation To obfuscate inter-arrival times, implementations could maintain a dedicated send buffer. As long as there is data in the send buffer, random samples from the inter-arrival time distribution are drawn. The thread processing the send buffer is then paused for the duration of the freshly drawn sample until the next MTU-sized chunk is written to the wire. This process is repeated until the send buffer is empty. Note that inter-arrival time obfuscation has a drastic impact on throughput. As a result, implementations MAY implement packet length obfuscation but ignore inter-arrival time obfuscation. 5. Session Tickets ScrambleSuit employs a subset of RFC 5077 [3] as its session ticket mechanism. In a nutshell, clients can redeem session tickets to authenticate themselves and bootstrap a ScrambleSuit connection. This section discusses the format of session tickets and how server's manage them. 5.1 Session Ticket Structure Session tickets contain a server's state with the most important element being the 32-byte master key. The state structure is encrypted using 16-byte AES-CBC and authenticated using HMAC-SHA256. Refer to Section X.X for how the server manages this key pair. The basic structure of a 112-byte session ticket is depicted below: +----------+----------+----------+ | 16 bytes | 64 bytes | 32 bytes | | IV | E(state) | HMAC | +----------+----------+----------+ The 16-byte IV is used for AES-CBC, MUST come from a CSPRNG and MUST be different for every session ticket. The 64-byte encrypted state is described below. The 32-byte HMAC authenticates the ticket. It is defined as follows: HMAC = HMAC-SHA256(k, IV | E(state)) Server's MUST verify the HMAC before attempting to decrypt the state. E(state), the 64-byte encrypted server state, has the following structure in its decrypted form: +------------+------------+------------+----------+ | 4 bytes | 18 bytes | 32 bytes | 10 bytes | | Issue date | Identifier | Master key | Padding | +------------+------------+------------+----------+ The 4-byte issue date is a Unix epoch and specifies when the ticket was issued by the server. The 18-byte identifier contains the ASCII string "ScrambleSuitTicket". It is checked by the server in order to make sure that the ticket was decrypted successfully. The 32-byte master key is used to derive session keys as described in Section 2.3. The 10-byte padding is used to pad the entire structure to 64 byte; a multiple of AES' block size. The padding is ignored and it MAY consist of 0 bytes. 5.2 Session Ticket Management Session tickets are encrypted and authenticated with a pair of keys only known to the server. As a result, tickets are computationally indistinguishable from randomness and opaque to clients as well as passive observers. For encryption, AES-CBC with a 16-byte key is used. For authentication, HMAC-SHA256 with a 32-byte key is used. The server has to make sure that the two keys are stored safely. Furthermore, the server SHOULD regularly rotate its keys. A reasonable key rotation interval would be once a week. At any given point in time, the server SHOULD have a current, valid key pair as well as the previous, superseded key pair. The current key pair SHOULD be used to issue and verify new tickets. The superseded key pair SHOULD be used to verify tickets which cannot be verified with the current key pair. The superseded key pair further SHOULD NOT be used to issue new tickets. References [0] https://www.torproject.org/projects/obfsproxy.html.en [1] http://www.cs.kau.se/philwint/pdf/wpes2013.pdf [2] https://gitweb.torproject.org/pluggable-transports/obfsproxy.git/blob/HEAD:/doc/obfs3/obfs3-protocol-spec.txt [3] https://tools.ietf.org/html/rfc5077