Security Notions for Fully Encrypted Protocols
Ellis Fenske, Aaron Johnson
https://censorbib.nymity.ch/#Fenske2023a
There’s an important class of censorship circumvention protocols that have sometimes been known as “look-like-nothing” or “randomized” protocols; examples are VMess, Shadowsocks, and obfs4. Rather than imitate some other protocol, these protocols encrypt (or otherwise obfuscate) the entire data stream, such that every byte appears to be uniformly random. This paper gives a name to this class of protocols—fully encrypted protocols or FEPs—and starts to formalize what security properties we should expect of them.
This paper considers a model of a stream-based (TCP-like) unidirectional FEP channel. The model builds on the stream-based channel model of Fischlin et al., which is meant to represent how network protocols work: a stream is not a single, atomic message, but a sequence of discrete fragments (whose boundaries may change on the way from sender to receiver). There is an abstract SEND function that encrypts a plaintext fragment and pushes it onto the network, and a RECV function that decrypts a received ciphertext fragment and recovers the next piece of plaintext. The authors make some changes for the FEP setting. The SEND function takes an additional parameter p that controls how many bytes of output are produced, in order to support a property called length shaping, defined later. And the RECV function returns not only a fragment of plaintext, but also a “channel closure” flag, to reflect the fact that closing a network connection is observable even in the presence of encryption, and that predictable closures may serve as a distinguisher. As simplifying assumptions, the model assumes a preshared symmetric key and an underlying reliable stream protocol like TCP.
The authors give definitions of FEP security against passive and active adversaries. In the passive setting, FEP-CPFA (Fully Encrypted Protocol under Chosen Plaintext-Fragment Attacks) gives the adversary a SEND oracle, with which it may encrypt a sequence of plaintext fragments; the adversary is challenged with distinguishing real protocol outputs from random byte strings of the same length. Some early FEPs, for instance obfuscated OpenSSH and obfs2, do not satisfy FEP-CPFA, because they have no secret key: a passive observer can decrypt the stream and undo the obfuscation. In the active setting, FEP-CCFA (Fully Encrypted Protocol under Chosen Ciphertext-Fragment Attacks) additionally gives the adversary a RECV oracle, which the adversary may supply with authentic SEND oracle outputs, its own crafted ciphertexts, or both. FEP-CCFA implies FEP-CPFA, but it is possible to satisfy FEP-CPFA without also satisfying FEP-CCFA; this is the case for obfs4, because of an active attack on unauthenticated length fields (which shows why modeling channel closure is important).
In order to resist traffic analysis, FEPs should be able to control the size of the fragments they send, a property the authors call length shaping. The abstract SEND function, in addition to a message parameter m, takes an output length parameter p. SEND must always output exactly p bytes (except for a special case at the end of a connection), even if there are no “real” bytes immediately available to send, and even if p is less than the size of the encrypted message. This requirement implies that FEPs must be able to do two things: (1) they must be able to produce unlimited padding on demand, and (2) they must buffer any outgoing data that cannot immediately be sent. Existing FEP implementations are generally not equipped to do length shaping, even if the protocol they use may technically permit it.
Finally, the paper gives a construction of a stream-based FEP that satisfies all the newly introduced security properties. The protocol resembles Shadowsocks AEAD, with 2-byte encrypted+authenticated length fields followed by an AEAD ciphertext of the specified length. The differences are that ciphertexts may contain encrypted padding, the receiver never closes the connection even after an authentication failure, and length shaping is implemented so that packet boundaries do not necessarily correspond to ciphertext boundaries. The SEND function has an input plaintext buffer buf and an output ciphertext buffer obuf. If there is enough in obuf to fill the p output length requirement, SEND removes that many bytes from obuf and returns them directly. Otherwise, SEND encrypts any data in buf, possibly with added padding, until at least p bytes are available.