Encoding

Encoding constraints

The encoded payload must remain valid within DNS query names. It must fit the label and full-name length limits, use an appropriate alphabet, and leave room for the controlled domain. At the same time, the representation should avoid the conspicuous patterns of conventional tunnel encodings.

Encryption makes the intermediate bytes close to uniformly random. Encoding does not change the confidential message; it changes the visible representation of those bytes. A format constraint can reduce the output alphabet, while frequency shaping can make some characters more common than others.

Format Transforming Encryption

Format Transforming Encryption extends symmetric encryption with an encoding layer defined by a regular expression. In the construction introduced by Dyer and colleagues, plaintext is encrypted using AES-CTR and authenticated with HMAC. The resulting intermediate ciphertext is then mapped into the language accepted by the chosen format.

Let $F$ define a finite language $L(F)$ for the selected output length. The encrypted data is interpreted as an integer, and an unrank function maps that integer to the corresponding word in the language. A rank function reverses the mapping during decoding.

Y\xrightarrow{\operatorname{unrank}}C\in L(F), \qquad C\xrightarrow{\operatorname{rank}}Y.

FTE has previously been used for protocol misidentification, including making encrypted transport resemble HTTP. FTExfil applies the format constraint to DNS query names rather than introducing a new FTE construction.

A small rank/unrank example

For the format [a-c]{2}, the lexicographically ordered language is:

Index:   0   1   2   3   4   5   6   7   8
Word:   aa  ab  ac  ba  bb  bc  ca  cb  cc

The integer 5 maps to bc, and ranking bc returns 5. This illustrates the role of the language index. A real encrypted message requires a much larger language than this nine-word example.

In fte_rs, an anchored regex is compiled into a deterministic finite automaton. Counts of accepted suffixes support the mapping between integers and words of a fixed length.

Alphabet size and entropy

If output characters are uniformly distributed over alphabet $\mathcal A$ , their entropy is

H(X)=\log_2|\mathcal A|.

A 32-character alphabet carries 5 bits per character. For example,

^[A-Z2-7]{25}\.example\.com$

provides a theoretical capacity of $25\times5=125$ bits in the variable part: 15 complete bytes and 5 remaining bits. However, its output still resembles conventional Base32 tunnel data.

Restricting the alphabet to lowercase letters gives

^[a-z]{25}\.example\.com$

and changes the theoretical entropy to

H(X)=\log_2 26\approx4.7004\ \text{bits/character}.

The corresponding capacity is approximately $25\log_2 26\approx117$ bits, or 14 complete bytes. This is a less expansive alphabet, but transferring 1 MiB at 14 bytes per query would require 74,899 queries even before transfer and encryption overhead.

Longer names and theoretical capacity

The available name length can be used more fully with a format such as

^[a-z]{63}\.[a-z]{63}\.[a-z]{63}\.[a-z]{49}\.example\.com$

The four variable labels contain 238 letters. Their theoretical capacity is

238\log_2 26\approx1119\ \text{bits},

or 139 complete bytes. At that raw capacity, a 1 MiB file would require 7,544 queries. These figures describe the encoding’s theoretical capacity, not the application’s benchmark packet counts: metadata and encryption consume part of the available space, and the benchmark uses different chunk sizes.

The character distribution remains uniform over a–z. FTE constrains the language, but this simple regex does not make its letters follow a natural-language frequency distribution.

Huffman coding

Huffman coding is traditionally used for lossless compression. It assigns shorter binary codewords to frequent symbols and longer codewords to rarer ones. The codes are represented by paths through a binary prefix tree, so no symbol’s code is the prefix of another symbol’s code.

The tree is constructed from the bottom up:

Count or estimate the frequency of each symbol.
Create a weighted leaf for every symbol.
Combine the two lowest-weight nodes into a parent whose weight is their sum.
Repeat until only the root remains.
Label the two branches at each split with 0 and 1.
Read each codeword along the path from root to leaf.

Ordinary compression substitutes codewords for input characters. Decoding consumes bits until a leaf is reached, emits the corresponding character, and returns to the root.

Worked compression example

Consider the 32-character string:

thisisanexamplestringformythesis

The following codebook represents the Huffman tree used in the worked example:

Character	Frequency	Codeword
s	5	`000`
i	4	`010`
t	3	`110`
e	3	`111`
h	2	`1000`
a	2	`1001`
n	2	`1010`
m	2	`1011`
r	2	`00100`
x	1	`00101`
p	1	`00110`
l	1	`00111`
y	1	`01100`
f	1	`01101`
g	1	`01110`
o	1	`01111`

Binary Huffman tree for the example string, with leaf symbols, frequency weights, and zero or one branch labels — Huffman tree for “thisisanexamplestringformythesis”. The weights count symbol occurrences; each root-to-leaf path gives the corresponding codeword.

For instance, this becomes 110 1000 010 000. Substituting the codeword for every character produces 122 bits, compared with 256 bits for an 8-bit ASCII representation of the 32 characters. This comparison concerns the encoded content and excludes the cost of communicating a codebook.

Reversing Huffman coding for frequency shaping

Encrypted input cannot be compressed by exploiting the redundancy of ordinary text: its bits are approximately uniform. However, those bits can be treated as input to the decoding direction of a Huffman tree constructed from a desired character distribution.

FTExfil consumes ciphertext bits one at a time while traversing the tree. Each leaf emits a letter; traversal then restarts at the root. Letters with shorter codewords are more likely to be reached, and consequently appear more often in the output. At the receiver, each letter is replaced by its codeword to recover the encrypted bitstream.

The tree is built from a target distribution, not from the frequencies of the encrypted input. The output is a longer, frequency-shaped representation rather than a compressed version of the ciphertext.

Emission probabilities

Let $\ell(x)$ be the codeword length for letter $x$ . Under uniformly distributed input bits, the probability of reaching that leaf is

P_S(x)=2^{-\ell(x)}.

A three-bit codeword is therefore emitted with probability $1/8$ , while a nine-bit codeword has probability $1/512$ . For the English-frequency tree, common letters such as e and t have three-bit codes, and rare letters such as j, x, q, and z have nine-bit codes.

The target distribution is approximated, not reproduced exactly. The Huffman tree supplies codeword lengths, and those lengths restrict the output probabilities to powers of two.

Entropy and output length

Substituting the emission probabilities into Shannon’s expression gives

H(X)=-\sum_{x\in\mathcal A}2^{-\ell(x)}\log_2\left(2^{-\ell(x)}\right) =\sum_{x\in\mathcal A}2^{-\ell(x)}\ell(x).

This is also the expected number of encrypted bits consumed per emitted character. For a ciphertext bitstream of length $b$ , the expected output length is approximately

|S|\approx\frac{b}{H(X)}.

The complete transformation is

M\longrightarrow C=\operatorname{Enc}(K,M) \longrightarrow S=\operatorname{Huff}_{P_{\mathrm{target}}}(C).

Less uniform output has a lower entropy per character, but it also requires more characters to represent the same encrypted input. This directly reduces the payload capacity of a DNS query name.

English-frequency model

The first target model uses English letter frequencies. The resulting Huffman tree assigns shorter codes to common letters and produces a non-uniform output distribution.

Huffman tree constructed from English letter frequencies, including frequency weights and branch bits — Huffman tree constructed from English letter frequencies.

A 194-byte example illustrates the difference between conventional representation and frequency shaping:

Representation	Length	Measured entropy
Plaintext	194 bytes	≈ 4.25 bits/character
Encrypted input represented in Base64	260 characters	≈ 5.79 bits/character
Encrypted input represented through the English Huffman tree	371 characters	≈ 4.12 bits/character

For an English-tree entropy of approximately 4.19 bits per character, the expected expansion of 194 bytes is

\frac{194\times8}{4.19}=\frac{1552}{4.19}\approx370.4\ \text{characters}.

The 371-character result is consistent with this estimate. It illustrates the cost of changing the representation: lower per-character entropy requires a longer output.

Bar chart comparing a-z character frequencies for a Bruce Schneier quotation, Base64, Huffman output, and the English frequency target — Character-frequency comparison for the Bruce Schneier quotation: plaintext, Base64 representation, Huffman-shaped output, and the English target distribution.

DNS-specific frequency model

English and DNS character frequencies are related but not identical. To investigate a more specific model, a corpus of 2,092,120,183 hostnames from the scanner.ducks.party project was processed on a 64-core Linux instance on SDU’s UCloud infrastructure.

Hostnames were normalized to lowercase and their public suffixes removed. The frequency comparison was then restricted to a–z. The resulting distribution differs from standard English letter frequencies and motivates a separate DNS-derived Huffman tree.

Bar chart comparing English and DNS target letter frequencies with the corresponding distributions implied by Huffman codeword lengths — English and DNS target frequencies compared with the character probabilities implied by their Huffman trees.

Huffman tree constructed from DNS-specific letter frequencies — Huffman tree constructed from the DNS-derived frequency distribution.

The target frequencies and tree-derived frequencies remain distinct. Using DNS observations improves the relevance of the target, but does not make the emitted distribution an exact copy of the observed one.

Variable-length output

Unlike a fixed-width encoding, weighted Huffman output has a probabilistic length. Some encrypted bit patterns encounter many short codewords, generating more characters; others encounter longer codewords and generate fewer.

An expected-capacity estimate is therefore not a guarantee that every chunk fits. Chunk selection must allow for the DNS length boundary. The evaluation uses a conservative weighted chunk size selected through repeated encoding trials, and the resulting lower payload capacity contributes to its higher packet count.