Understanding Shadowsocks

Understanding Shadowsocks

Shadowsocks
is a network proxy tool that can bypass firewalls. It encrypts the original data before transmission, so the firewall on the network cannot determine the original content being sent and therefore lets it pass. In this way, it gets through the firewall—what is commonly known as “bypassing the firewall.”

In a free network environment, when accessing services from your local machine, a direct connection is established with the remote service to transmit data, as shown below:

But in a restricted network environment, there is a firewall, and all data transmitted between the local computer and the remote service must pass through the firewall for inspection, as shown below:

If the firewall detects that you are transmitting restricted content, it intercepts the transmission, which prevents the local machine from accessing the remote service.

What Shadowsocks
does is encrypt the transmitted data, so the firewall only sees encrypted data. Since it does not know what the original content is, it allows the request to pass, and the local machine is then able to access the remote service, as shown below:

In other words, the prerequisites for using Shadowsocks are:

• a server located outside the firewall;
• a Shadowsocks client installed on the local machine, used to encrypt transmitted data;
• the server must have the Shadowsocks
  server component installed, used to decrypt the encrypted transmitted data and, after recovering the original data, send it to the target server.

How Shadowsocks Works

Shadowsocks consists of two parts: ss-local
running locally and
ss-server running on a server outside the firewall. Below is a detailed introduction to their respective responsibilities (the following explanation of how Shadowsocks
works is only my rough understanding, so there may be slight differences).

ss-local

ss-local
is responsible for starting and listening on a service on the local machine. Network requests from local software are first sent to
ss-local. After ss-local
receives a network request from local software, it encrypts the original data to be transmitted according to the user-configured encryption method and password, and then forwards it to the server outside the firewall.

ss-server

ss-server
is responsible for starting and listening on a service on the server outside the firewall. This service listens for requests from the local machine’s
ss-local. Upon receiving data forwarded by ss-local,
it first symmetrically decrypts the data according to the user-configured encryption method and password to obtain the original content of the encrypted data. At the same time, it also parses the
SOCKS5 protocol to read the actual target service address for this request (for example, a Google
server address), and then forwards the decrypted original data to the real target service.

When the real target service returns data, the ss-server
side encrypts the returned data and forwards it to the corresponding ss-local side. After the ss-local
side receives the data, it decrypts it and forwards it to the software on the local machine. This is a symmetrical reverse process.

Since both the ss-local and ss-server
sides need to use symmetric encryption algorithms to encrypt and decrypt data, the encryption method and password on both sides must be configured identically. Shadowsocks
provides a range of standard and reliable symmetric algorithms for users to choose from, such as
rc4, aes, des, chacha20, and so on. The purpose of Shadowsocks
encrypting data before transmission is to obfuscate the original data so that firewalls along the way cannot determine what the original transmitted data is. But in fact, using these highly secure and computationally intensive symmetric encryption algorithms just for obfuscation is a bit like “using a sledgehammer to crack a nut.”

Introduction to the SOCKS5 Protocol

Shadowsocks data transmission is built on the SOCKS5 protocol. SOCKS5 is
a network proxy protocol at the TCP/IP layer.
The data decrypted by the ss-server side is encapsulated using the SOCKS5 protocol. Through
the SOCKS5 protocol, the ss-server
side can read the actual address of the service that the local software wants to access, as well as the original data to be transmitted. Below is a detailed introduction to
the communication details of the SOCKS5 protocol.

Establishing a Connection

The client initiates a connection to the server, and the data packet sent by the client is as follows:

The meanings of each field are as follows:
–VER: represents the SOCKS version; for SOCKS5,
the default is 0x05, and its fixed length is 1 byte;
–NMETHODS: indicates the length of the third field, METHODS, and its length is also 1 byte;
–METHODS: indicates the authentication methods supported by the client. There can be multiple methods, and its length is 1–255 bytes.

The currently supported authentication methods are:

• 0x00：NO AUTHENTICATION
  REQUIRED (no authentication required)
• 0x01：GSSAPI
• 0x02：USERNAME/PASSWORD (username and password)
• 0x03: to X’7F’ IANA ASSIGNED
• 0x80: to X’FE’ RESERVED FOR
  PRIVATE METHODS
• 0xFF: NO ACCEPTABLE
  METHODS (none supported, so the connection cannot be established)

Connection Response

After the server receives the client’s authentication information, it must respond to the client, indicating which authentication method information the server requires the client to provide. The packet format of the server’s response is as follows:

The meanings of each field are as follows:

• VER: represents the version of SOCKS; for SOCKS5,
  the default is 0x05, and its fixed length is 1 byte;
• METHOD: represents the authentication information that the server requires the client to provide according to this authentication method; its value is 1 byte in length and can be one of the six authentication methods above.

For example, if the server does not require authentication, it can respond to the client like this:

Establishing a Connection with the Target Service

After the connection initiated by the client has been verified by the server, the next step is for the client to tell the server the address of the actual target service, and then the server uses that address to request the actual target service. In other words, the client needs to tell the server the address of the Google service, google.com:80, and the server then requests google.com:80.
The target service address is in the format
(IP or domain name) + port, and the packet format that the client needs to send is as follows:

The meanings of each field are as follows:

• VER: represents the version of the SOCKS protocol; for SOCKS,
  the default is 0x05, and its value is 1 byte in length;
• CMD: represents the type of client request. The value is also 1 byte long, and there are three types;
  • CONNECT: 0x01;
  • BIND: 0x02;
  • UDP: ASSOCIATE 0x03;
• RSV: reserved field, with a value length of 1 byte;
• ATYP: represents the address type of the requested remote server. The value is 1 byte long, and there are three types;
  • IPV4: address: 0x01;
  • DOMAINNAME: 0x03;
  • IPV6: address: 0x04;
• DST.ADDR: represents the address of the remote server. It is parsed according to ATYP, and its value length is variable;
• DST.PORT: represents the port of the remote server, meaning which port to access. The value length is 2 bytes.

After the server obtains the target service address provided by the client, it connects to the target service. Regardless of whether the connection succeeds, the server should inform the client of the connection result. If the connection succeeds, the packet format returned by the server is as follows:

The meanings of each field are as follows:

• VER: represents the version of the SOCKS protocol. SOCKS
  defaults to 0x05, and its value length is 1 byte;
• REP represents the response status code. The value is also 1 byte long, and there are the following types
  • 0x00 succeeded
  • 0x01 general SOCKS server failure
  • 0x02 connection not allowed by ruleset
  • 0x03 Network unreachable
  • 0x04 Host unreachable
  • 0x05 Connection refused
  • 0x06 TTL expired
  • 0x07 Command not supported
  • 0x08 Address type not supported
  • 0x09 to 0xFF unassigned
• RSV: Reserved field, length is 1 byte
• ATYP: Represents the address type of the requested remote server, length is 1 byte, with three types
  • IP V4 address: 0x01
  • DOMAINNAME: 0x03
  • IP V6 address: 0x04
• BND.ADDR: Indicates the bound address, variable length.
• BND.PORT: Indicates the bound port, length is 2 bytes

Data Forwarding

After the client receives a successful response from the server, it begins sending data. After the server receives data from the client, it forwards it to the target service.

Summary

The purpose of the SOCKS5
protocol is essentially to move the process that would originally have the local machine directly request the target service to the server side, where the server proxies the client’s access instead.
Its operating process can be summarized as follows:

1. The local machine negotiates with the proxy server and establishes a connection;
2. The local machine tells the proxy server the address of the target service;
3. The proxy server connects to the target service and, after succeeding, informs the local machine;
4. The local machine starts sending to the proxy server the data that should originally be sent to the target service, and the proxy server completes the data forwarding.

The above content comes from the SOCKS5 Protocol Specification RFC1928.

Lightsocks Implementation

To implement Lightsocks, two parts are needed: lightsocks-local running locally, and lightsocks-server running on a proxy server outside the firewall.
Below, I will teach you separately how to implement them using Golang. The reasons for using Golang are: good performance, cross-platform support, suitability for high concurrency, and a low learning curve. Interested in Golang? See A Collection of Chinese Golang Learning Resources

Implementing Data Obfuscation

In Shadowsocks,
standard symmetric encryption algorithms are used to implement data obfuscation, and symmetric algorithms require a large amount of computation during encryption and decryption.
For the sake of simplicity, Lightsocks
will use the simplest and most efficient method to implement data obfuscation. The specific principle is as follows.

This data obfuscation algorithm is very similar to symmetric encryption: both ends need to have the same key.
This key must meet the following requirements:

• It consists of 256 bytes, that is, an array, represented in Golang
  with the type [256]byte;
• This array must contain all 256 numbers from 0 to 255, with none missing;
• The value of the Ith element in this array cannot be equal to I;

For example, the following is a valid key (indices above, values below):

If the original data is [5,0,1,2,3], then after being encrypted with the above key, it becomes [236,186,118,82,201].
If the encrypted data is [186,118,82,201,235], then the original data obtained by decrypting it with the above key is [0,1,2,3,4]

A clever reader like you has surely understood the pattern: establish a one-to-one mapping among these 256 numbers from 1 to 255,
encryption means taking one number and getting its corresponding mapped number, while decryption is the reverse process, and the role of this key is precisely to describe this mapping relationship.
This is actually the inverse function taught in secondary school.

Why design the data obfuscation algorithm this way? During data transmission, data is streamed with the byte
as the smallest unit. A byte can only take values from
0 to 255. This obfuscation algorithm can directly encrypt and decrypt each individual byte,
without needing to encrypt a large block of data like standard symmetric algorithms do.
In addition, the algorithmic complexity of this algorithm for encrypting and decrypting N bytes of data is
N (direct access via array indexing), making it very suitable for stream encryption.

So how secure is the above encryption algorithm? How many possible combinations of keys satisfy the above requirements? Let’s calculate:
This is actually the permutation problem from the permutations and combinations taught in middle school. To visualize it, it is like taking
0 to 255 differently numbered people and assigning them to 0 to 255
differently numbered slots, with no matching numbers allowed—how many possible arrangements are there?
That is A(255,255)=255*254*253*...*1=255!, but half of these contain duplicates,
so the final result is 255!/2,
whose value is roughly on the order of 10^500.

Although the above encryption algorithm has many flaws, it is sufficient to achieve efficient data obfuscation and deceive firewalls.

Currently, Shadowsocks, which uses symmetric encryption algorithms to implement data obfuscation,
can already be identified by some firewalls through machine-learning-based feature analysis as traffic whose original content is likely legitimate, whereas
Lightsocks’s obfuscation algorithm currently cannot be easily identified.

The code for randomly generating one of the above keys is as follows:

package core
import (
	"math/rand"
	"time"
)
const PasswordLength = 256
type Password [PasswordLength]byte

func init() {
	// Update the random seed to prevent generating the same random password
	rand.Seed(time.Now().Unix())
}

// Generate a password made up of a random combination of 256 bytes
func RandPassword() *Password {
	// Randomly generate a byte array composed of 0~255
	intArr := rand.Perm(PasswordLength)
	password := &Password{}
	for i, v := range intArr {
		password[i] = byte(v)
		if i == v {
			// Ensure that no byte position is duplicated
			return RandPassword()
		}
	}
	return password
}

The code below is used to encrypt and decrypt data:

package core

type Cipher struct {
	// Password used for encoding
	encodePassword *Password
	// Password used for decoding
	decodePassword *Password
}

// Encrypt the original data
func (cipher *Cipher) encode(bs []byte) {
	for i, v := range bs {
		bs[i] = cipher.encodePassword[v]
	}
}

// Decode the encrypted data back to the original data
func (cipher *Cipher) decode(bs []byte) {
	for i, v := range bs {
		bs[i] = cipher.decodePassword[v]
	}
}

// Create a new encoder/decoder
func NewCipher(encodePassword *Password) *Cipher {
	decodePassword := &Password{}
	for i, v := range encodePassword {
		encodePassword[i] = v
		decodePassword[v] = byte(i)
	}
	return &Cipher{
		encodePassword: encodePassword,
		decodePassword: decodePassword,
	}
}

Then use the Cipher above to wrap a
SecureSocket for encrypted transmission, so that the streaming data in a TCP Socket can be encrypted and decrypted directly. The code is as follows:

package core

import (
	"errors"
	"fmt"
	"io"
	"net"
)

const (
	BufSize = 1024
)

// TCP Socket for encrypted transmission
type SecureSocket struct {
	Cipher     *Cipher
	ListenAddr *net.TCPAddr
	RemoteAddr *net.TCPAddr
}

// Read encrypted data from the input stream, decrypt it, and put the original data into bs
func (secureSocket *SecureSocket) DecodeRead(conn *net.TCPConn, bs []byte) (n int, err error) {
	n, err = conn.Read(bs)
	if err != nil {
		return
	}
	secureSocket.Cipher.decode(bs[:n])
	return
}

// Encrypt the data in bs and immediately write all of it to the output stream
func (secureSocket *SecureSocket) EncodeWrite(conn *net.TCPConn, bs []byte) (int, error) {
	secureSocket.Cipher.encode(bs)
	return conn.Write(bs)
}

// Continuously read raw data from src, encrypt it, and write it to dst until no more data can be read from src
func (secureSocket *SecureSocket) EncodeCopy(dst *net.TCPConn, src *net.TCPConn) error {
	buf := make([]byte, BufSize)
	for {
		readCount, errRead := src.Read(buf)
		if errRead != nil {
			if errRead != io.EOF {
				return errRead
			} else {
				return nil
			}
		}
		if readCount > 0 {
			writeCount, errWrite := secureSocket.EncodeWrite(dst, buf[0:readCount])
			if errWrite != nil {
				return errWrite
			}
			if readCount != writeCount {
				return io.ErrShortWrite
			}
		}
	}
}

// Continuously read encrypted data from src, decrypt it, and write it to dst until no more data can be read from src
func (secureSocket *SecureSocket) DecodeCopy(dst *net.TCPConn, src *net.TCPConn) error {
	buf := make([]byte, BufSize)
	for {
		readCount, errRead := secureSocket.DecodeRead(src, buf)
		if errRead != nil {
			if errRead != io.EOF {
				return errRead
			} else {
				return nil
			}
		}
		if readCount > 0 {
			writeCount, errWrite := dst.Write(buf[0:readCount])
			if errWrite != nil {
				return errWrite
			}
			if readCount != writeCount {
				return io.ErrShortWrite
			}
		}
	}
}

// Establish a connection with the remote socket; data transmission between them will be encrypted
func (secureSocket *SecureSocket) DialRemote() (*net.TCPConn, error) {
	remoteConn, err := net.DialTCP("tcp", nil, secureSocket.RemoteAddr)
	if err != nil {
		return nil, errors.New(fmt.Sprintf("Failed to connect to remote server %s:%s", secureSocket.RemoteAddr, err))
	}
	return remoteConn, nil
}

This SecureSocket is used for TCP
communication between the local end and the server end,
and when only SecureSocket
is used for communication, the data transmitted in between will be encrypted, so the firewall cannot read the original data.

Implementing the local end

The responsibility of the local
end running on the local machine is to encrypt the data sent to it by local programs and then forward it to the proxy server outside the firewall. The overall workflow is as follows:

1. Listen for proxy requests from the local browser;
2. Encrypt the data before forwarding;
3. Forward socket data to the proxy server outside the firewall;
4. Forward the data returned by the server to the user’s browser.

The code for the local end that implements the above functions is as follows:

package local

import (
	"github.com/gwuhaolin/lightsocks/core"
	"log"
	"net"
)

type LsLocal struct {
	*core.SecureSocket
}

// Create a local endpoint
func New(password *core.Password, listenAddr, remoteAddr *net.TCPAddr) *LsLocal {
	return &LsLocal{
		SecureSocket: &core.SecureSocket{
			Cipher:     core.NewCipher(password),
			ListenAddr: listenAddr,
			RemoteAddr: remoteAddr,
		},
	}
}

// The local endpoint starts listening and accepts connections from the local browser
func (local *LsLocal) Listen(didListen func(listenAddr net.Addr)) error {
	listener, err := net.ListenTCP("tcp", local.ListenAddr)
	if err != nil {
		return err
	}

	defer listener.Close()

	if didListen != nil {
		didListen(listener.Addr())
	}

	for {
		userConn, err := listener.AcceptTCP()
		if err != nil {
			log.Println(err)
			continue
		}
		// When userConn is closed, clear all data immediately, regardless of unsent data
		userConn.SetLinger(0)
		go local.handleConn(userConn)
	}
	return nil
}

func (local *LsLocal) handleConn(userConn *net.TCPConn) {
	defer userConn.Close()

	proxyServer, err := local.DialRemote()
	if err != nil {
		log.Println(err)
		return
	}
	defer proxyServer.Close()
	// When Conn is closed, clear all data immediately, regardless of unsent data
	proxyServer.SetLinger(0)

	// Forward traffic
	// Read data from proxyServer and send it to localUser
	go func() {
		err := local.DecodeCopy(userConn, proxyServer)
		if err != nil {
			// During copying, network timeouts and other errors may be returned; as long as one error occurs, exit this task
			userConn.Close()
			proxyServer.Close()
		}
	}()
	// Send data from localUser to proxyServer; here, because it is in the proxying stage, network errors are more likely to occur
	local.EncodeCopy(proxyServer, userConn)
}

Implementing the server side

The server side running on the proxy server outside the firewall has the following responsibilities:

1. Listen for requests from the local proxy client;
2. Decrypt the data requested by the local proxy client, parse the SOCKS5
   protocol, and connect to the remote server that the user’s browser actually wants to reach;
3. Forward the encrypted content of the data returned by the remote server that the user’s browser actually wants to connect to back to the local proxy client.

The code for implementing the above functionality is as follows:

package server

import (
	"encoding/binary"
	"github.com/gwuhaolin/lightsocks/core"
	"log"
	"net"
)

type LsServer struct {
	*core.SecureSocket
}

// Create a new server
func New(password *core.Password, listenAddr *net.TCPAddr) *LsServer {
	return &LsServer{
		SecureSocket: &core.SecureSocket{
			Cipher:     core.NewCipher(password),
			ListenAddr: listenAddr,
		},
	}
}

// Run the server and listen for requests from the local proxy client
func (lsServer *LsServer) Listen(didListen func(listenAddr net.Addr)) error {
	listener, err := net.ListenTCP("tcp", lsServer.ListenAddr)
	if err != nil {
		return err
	}

	defer listener.Close()

	if didListen != nil {
		didListen(listener.Addr())
	}

	for {
		localConn, err := listener.AcceptTCP()
		if err != nil {
			log.Println(err)
			continue
		}
		// When localConn is closed, clear all data immediately, regardless of unsent data
		localConn.SetLinger(0)
		go lsServer.handleConn(localConn)
	}
	return nil
}

// Parse the SOCKS5 protocol
// https://www.ietf.org/rfc/rfc1928.txt
func (lsServer *LsServer) handleConn(localConn *net.TCPConn) {
	defer localConn.Close()
	buf := make([]byte, 256)

	/**
	   The localConn connects to the dstServer, and sends a ver
	   identifier/method selection message:
		          +----+----------+----------+
		          |VER | NMETHODS | METHODS  |
		          +----+----------+----------+
		          | 1  |    1     | 1 to 255 |
		          +----+----------+----------+
	   The VER field is set to X'05' for this ver of the protocol.  The
	   NMETHODS field contains the number of method identifier octets that
	   appear in the METHODS field.
	*/
	// The first field, VER, represents the Socks version. Socks5 defaults to 0x05, and its fixed length is 1 byte
	_, err := lsServer.DecodeRead(localConn, buf)
	// Only version 5 is supported
	if err != nil || buf[0] != 0x05 {
		return
	}

	/**
	   The dstServer selects from one of the methods given in METHODS, and
	   sends a METHOD selection message:

		          +----+--------+
		          |VER | METHOD |
		          +----+--------+
		          | 1  |   1    |
		          +----+--------+
	*/
	// No authentication is required; authenticate successfully directly
	lsServer.EncodeWrite(localConn, []byte{0x05, 0x00})

	/**
		          +----+-----+-------+------+----------+----------+
		          |VER | CMD |  RSV  | ATYP | DST.ADDR | DST.PORT |
		          +----+-----+-------+------+----------+----------+
		          | 1  |  1  | X'00' |  1   | Variable |    2     |
		          +----+-----+-------+------+----------+----------+
	*/

	// Get the address of the actual remote service
	n, err := lsServer.DecodeRead(localConn, buf)
	// The shortest possible length of n is 7, in the case of ATYP=3 with DST.ADDR occupying 1 byte and having a value of 0x0
	if err != nil || n < 7 {
		return
	}

	// CMD represents the type of request from the client. Its value is also 1 byte long, and there are three types
	// CONNECT X'01'
	if buf[1] != 0x01 {
		// Currently only CONNECT is supported
		return
	}

	var dIP []byte
	// aType represents the address type of the requested remote server. Its value is 1 byte long, and there are three types
	switch buf[3] {
	case 0x01:
		//	IP V4 address: X'01'
		dIP = buf[4 : 4+net.IPv4len]
	case 0x03:
		//	DOMAINNAME: X'03'
		ipAddr, err := net.ResolveIPAddr("ip", string(buf[5:n-2]))
		if err != nil {
			return
		}
		dIP = ipAddr.IP
	case 0x04:
		//	IP V6 address: X'04'
		dIP = buf[4 : 4+net.IPv6len]
	default:
		return
	}
	dPort := buf[n-2:]
	dstAddr := &net.TCPAddr{
		IP:   dIP,
		Port: int(binary.BigEndian.Uint16(dPort)),
	}

	// Connect to the actual remote service
	dstServer, err := net.DialTCP("tcp", nil, dstAddr)
	if err != nil {
		return
	} else {
		defer dstServer.Close()
		// When the connection is closed, clear all data immediately, regardless of unsent data
		dstServer.SetLinger(0)

		// Respond to the client that the connection was successful
		/**
		          +----+-----+-------+------+----------+----------+
		          |VER | REP |  RSV  | ATYP | BND.ADDR | BND.PORT |
		          +----+-----+-------+------+----------+----------+
		          | 1  |  1  | X'00' |  1   | Variable |    2     |
		          +----+-----+-------+------+----------+----------+
		*/
		// Respond to the client that the connection was successful
		lsServer.EncodeWrite(localConn, []byte{0x05, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00})
	}

	// Start forwarding
	// Read data from localUser and send it to dstServer
	go func() {
		err := lsServer.DecodeCopy(dstServer, localConn)
		if err != nil {
			// During copying, network timeouts and other errors may be returned; as long as one error occurs, exit this task
			localConn.Close()
			dstServer.Close()
		}
	}()
	// Read data from dstServer and send it to localUser; here, network errors are more likely because this is the censorship-circumvention stage
	lsServer.EncodeCopy(localConn, dstServer)
}

The above is the core code for implementing a lightweight Shadowsocks.
For some other miscellaneous code, such as the startup entry point and configuration reading/writing, you can read the complete code in the lightsocks project.