These are the visual aids for my talk at the Workshop on Attacks in Cryptography in 2024, and a transcript of the audio.

wac7-fep.zip has some "source code" for the visuals, for example the obfs4 and TLS pcap files used to generate the protocol visualizations.

Some errors in the talk are marked in the transcript like this: ~~what was said~~ what was intended.

The presentation video here is excerpted from the session video posted to YouTube (WAC7 talk 3).

How cryptography relates to Internet censorship circumvention

David Fifield <david@bamsoftware.com>

Workshop on Attacks in Cryptography 7
2024-08-18

https://www.bamsoftware.com/talks/wac7-fep/

Show some neat, but little-known, crypto-related attacks on significant protocols.
Talk about Fully Encrypted Protocols (FEPs).
Introduce censorship threat models to the cryptography-minded.

"Comments on certain past cryptographic flaws affecting fully encrypted censorship circumvention protocols" (2023)
David Fifield
https://eprint.iacr.org/2023/1362

Okay. Button. Great.

Part of this talk is just, sort of, general outreach, because I want to show people the potentials of this field, and I think we would benefit from having more cryptographic expertise and more cryptographic involvement. So really, I'm trying to serve a few different purposes with this talk. One is that I want to show you some rather cool attacks that have happened against deployed and important censorship circumvention protocols. There are significant protocols, they're socially important, they have millions of users, but I think these attacks are not very well-known, and I just think they're interesting and more people should know about them. I also want to talk about fully encrypted protocols, or FEPs. It's a really cool topic that I just want to talk more about. And finally, I want to say, what is a censorship threat model? I want to give you an introduction to censorship threat modeling as, you know, someone who is experienced or knowledgeable about cryptography, and especially to help you get over some of the early pitfalls, or some of the early misconceptions that I've seen people have when they start doing research in this field. So I want you to be able to get started, hit the ground running, if you're interested in doing this kind of stuff.

This talk is growing out of an essay that I wrote that had roughly the same purpose. There were all these attacks happening that I was following, some of them discovered by me, some of them I was just paying attention to, but all the discussion was happening in bug trackers and mailing lists and things like that, and I didn't want these to get lost, and so I wrote them up in a more formal way. But I think this is still a rather accessible document. If you want to read more at your own pace, you can see this document.

Censorship and circumvention

Diagram of a censorship model, with a 'client' node in the middle of a censor-controlled network, connected by network links to an outside 'destination' node.

A simple but fairly general model of Internet censorship.

The censor derives utility from permitting some forms of network access. ("Block everything" is not a profitable strategy.)

Circumvention tools work by making what the censor wants to allow, and what the censor wants to block, difficult to tell apart—by obfuscating the censor's decision boundary such that underblocking is more appealing than overblocking.

Let's start by defining what we mean by censorship and circumvention. This is the rough picture I almost always have in my mind when I'm thinking about censorship stuff. There are variations possible, but this simple model will cover a large variety of general cases. We have some network, shown in red here, which is the censor-controlled network. Right? This often corresponds to, like, the boundaries of a country, or the boundaries of an AS, or something like that—there's someone who's exercising control over this network, called the "censor". And inside the censored network, there is a so-called "client", a censored client, who is subject to these controls by being inside this network. There's something outside the censor's network, we often call the "destination", and the client is trying to communicate with the destination, but the censor is preventing direct access. And that can take a variety of forms. It could be because the censor doesn't like the destination's identity. It could be an IP address, it could be a domain name, something like that. Or it could be the contents of the communication—what you're saying. It could be you're trying to send something through there, and it's got some keywords or something, and those keywords are what the censor wants to block. But anyway, straightforward communication between the client and the destination is being interfered with by the censor. And circumvention is finding ways to enable this communication despite this, sort of, adversary-in-the-middle interference.

We need to make a necessary assumption here, which is that the censor derives some benefit from allowing some forms of network access. Otherwise, the censor just trivially shuts everything off, and no communication is possible. Within that threat model, the censor is powerful enough to do that, but the censor has incentives not to do that. And if you think about how this maps to the real world, for example, a government that's censoring the Internet still wants its citizens to get online, in order to like, do work, to earn money, to pay taxes, and be happy enough not to, like, immediately revolt, and things like that. So you get some benefit by allowing some network access, but you want to be selective, as a censor. Allow some, but not allow all of it. And that's really where the art of censorship circumvention comes in, which is that circumvention is, sort of, blurring that decision boundary between what the censor wants to allow, and what the censor wants to block, and making those two difficult to distinguish. Right? Cryptography people are like, distinguishability, now you're speaking my language. We try to make that distinguishability problem difficult, and ideally, in the extreme, what we push it to, is that, the censor is faced with an all-or-nothing decision. Like, either we block everything, or we allow everything, and then we hope that the cost, the utility calculus works out, that the "allow everything" is the more attractive option for the censor.

A censor may be understood as a combination of detection and blocking components.

Detection	Blocking
Destination IP addresses TLS SNI (Server Name Indication) Contents of DNS queries Signatures of proxy protocols Plaintext keywords …	IP null routing TCP RST injection DNS response injection HTTP redirect injection Packet dropping …

Generally, circumvention tools use some kind of encrypted proxy: encryption to hide the content of communication, and a proxy to hide its endpoint.

All right. You can think of a censor, you can mentally model a censor, as complex or a combination of a detection module and a blocking module. So some part of it that says, for each packet, or each flow, or each connection, whatever your unit of analysis is, whether I want to allow this, or whether I want to block it. And there actually are shades, there's sort of a continuum between allowing and blocking. You can also have like, throttling in the middle, but we're not really going to get into those fine details. But you have something that does the allow/block decision, and then you need something that actually enforces that, that actually allows the allowed traffic and blocks the blocked traffic. And both of these can be lossy and imperfect filters and technologies.

When we model censors, we try not to put limits on them. Sometimes we make some computational assumptions, we put some bounds on them. We always assume, you know, they're bound by the laws of physics: they cannot guess crypto keys, they cannot do things that we think are computationally impossible. But otherwise, we generally allow them to be pretty powerful. And, they can inspect any traffic that's going by, they can inject their own traffic, they can tamper with existing traffic, anything like that.

But I'll mention a few of the detection things that actually exist in practice. That actually are a problem in the real world for people facing censorship. One big one is the destination IP address. You just block IP addresses, or block ranges of IP addresses. Very very common. Another is the TLS SNI. Do people know what SNI is? "Server Name Indication" in TLS? [One audience member vigorously raises hand.] Yeah, I think it's actually not as well-known as it should be, but every TLS connection has the destination hostname in plaintext as part of the Client Hello. There actually are things that are in progress trying to obscure that. But this, if you want to take one thing away from this talk, this is the number one means that is used to censor connections today. TLS SNI is like the absolute killer. It's so hard to work around the fact that the identity of the endpoint is baked in, in plaintext, with every TLS connection. But this is really big. And many many countries practice SNI-based detection. The contents of your DNS queries. Lots of DNS is still plaintext these days, and as that passes by the wire you can just inspect, and say, what name is being resolved? Is that a name I want to allow access to? Now, in addition, you as a censor, you want to block access to that destination, but we model our censors as being aware and adaptive, and the censors know about circumvention, and they know about proxies, and therefore there are also trying to block access to proxy protocols. Not only direct access, but there's a second-order censorship problem, which is they're trying to block this indirect access. So they will also do things like, look for IP addresses of known proxy servers, or look for byte signatures that are characteristic of proxy protocols. And the plaintext keywords, this is less and less relevant these days as more of the Internet becomes encrypted, but it still is a thing. For example, looking for certain fields in the URL part of an HTTP request. Or, if there's like a plaintext chat, you could look for certain keywords passing by in the chat. Those are the things that will get you detected by the detection module.

After detection happens, how is the blocking enforced? There are lots of ways that this happens, again, in practice. One is IP null routing. Just blackholing IP address. That's an effective… a very cost-effective, as well as effective, way of blocking access. TCP RST injection. You have a TCP connection, an on-path attacker can inject RST packets and just tear it down. There's no, like, cryptographic protection against doing that. DNS response injection. If a censor sees a DNS query go out with a name that it wants to block, it can actually send you back a fake DNS response, and it will have some useless IP address. And this, actually, is also very overwhelmingly popular. This happens in lots and lots of different countries. In Turkmenistan, for example, if you try to resolve a DNS query for a blocked domain name, you will get back a response that is for 127.0.0.1. It will say, that's your A record for that name you just looked up. ~~Curiously, you will also get back the legitimate response, which speaks a little bit to censors' practical limitations: why they would be an on-path attacker rather than an in-path attacker.~~ [This remark was likely incorrect: it is true, in China, that you also get back the legitimate response (which points to packet injection rather than flow dropping; cf. "Hold-On"), but in Turkmenistan, it is more likely that the DNS query packet is dropped and never reaches the intended resolver. Thanks to the TMC team for answering my question on this point.] But that's another detail I'm not going to get into right now. Some places, you will get an injected HTTP redirect, like a 301 or a 302, that goes to a block page, saying "this page is blocked". And often there'll just be packet dropping: this packet is suspect, we'll just drop it. Or, in order to effect throttling, you may just drop, you know, some fraction of packets.

In general, the circumvention problem requires some sort of encrypted proxy. So you need the encrypted part, and you need the proxy part, and that's because there's two things we're trying to protect. One is the actual content of the communication. So, any plaintext keywords, any proxy protocol signatures, or anything like that, we need to encrypt or somehow obfuscate so it's not immediately apparent to the censor. And then we need the proxy because we always need to do indirect access. We assume that the overt identity of the destination we're going for, that IP address or that domain name, is going to be blocked by the censor, so we need some third party, some proxy, to let us get around. Right? So you need these two elements, generally. Some sort of encryption, or "obfuscation", we often say, and some kind of proxy.

Fully Encrypted Protocols (FEPs)

Every byte in a connection appears independently and uniformly random.

"Security notions for fully encrypted protocols" (2023)
Ellis Fenske, Aaron Johnson
https://www.petsymposium.org/foci/2023/foci-2023-0004.php
https://github.com/net4people/bbs/issues/383

"Bytes to Schlep? Use a FEP: Hiding Protocol Metadata with Fully Encrypted Protocols" (2024)
Ellis Fenske, Aaron Johnson
https://arxiv.org/abs/2405.13310

"Obfuscated Key Exchange" (2024)
Felix Günther, Douglas Stebila, Shannon Veitch
https://eprint.iacr.org/2024/1086

The attacks I'm going to show you today are all examples of attacks on fully encrypted protocols. There's a class of censorship circumvention protocols known as fully encrypted protocols. This is something that has existed for a long time, and has developed formally for more than a decade, and has seen a lot of use in censorship circumvention, and is only recently, in the past one or two years, starting to be formalized, and given cryptographic security definitions, and things like this. I'm really really excited about this work. And if you want one important takeaway from this talk, it would be, read these three papers on this list, if you haven't heard of fully encrypted protocols, and become familiar with it, because I'm really excited about it.

What does it mean to be a fully encrypted protocol, or FEP? It means that every byte in the protocol, from beginning to end, appears as uniformly and independently random. So, unlike TLS, where you've got some plaintext stuff, like your ciphersuites and your plaintext SNI, or unlike SSH, like we saw this morning, where you've got this version number, and you've got, you know, some sort of cipher negotiation, fully encrypted protocols are not allowed to do that. Every byte has to be computationally indistinguishable from random. Kind of an interesting challenge, right, if you think about it. How do you actually achieve that? And these start to define some of those, and they give some example constructions, and things like that.

A bitmap of uniformly random grayscale pixels.

A bitmap that appears to be mostly uniformly random grayscale pixels, but with a noticeable smear of darker pixels near the top, corresponding to the TLS Client Hello at the beginning of the connection.

Protocol bytes mapped to grayscale pixels.

And if I show you these two graphics, and I tell you every pixel corresponds to one byte in a protocol, I've just concatenated all the packets in the protocol and extracted the bytes, and every pixel is a byte value from 0 to 255, can you tell which of these protocols is TLS, and which of these is a FEP? Yeah. Right. So it's the one on the right, is TLS, because you can see, it's got this, like dark smear at the top, and what that is, is a bunch of non-random bytes. That's actually the Client Hello you're seeing at the top there. And I think if you look very closely, you can also see some record headers and stuff, but they're much shorter. But they will also be mixed in there among the pseudorandom bytes. And the one on the left here is actually a protocol called obfs4, it's a very common one used especially with the Tor protocol. But this gives you an idea.

Now, if it is surprising to you that a protocol that looks like this [gesturing to left figure] could be useful for censorship circumvention, this is like, the first step in calibrating your mental model. This was also surprising to me, because you look at this, and you say, but wait a minute, most protocols don't look like this. So why can't I distinguish this weird totally random protocol from something like SSH, or from something like TLS? Why don't we just, like, check for randomness and block it? It's a really good question. These types of protocols are sort of unreasonably effective, and no one knows exactly why these are so resistant to censorship. We have some good ideas, we have some speculations, you know, and we can make some justification, but I think no one really knows why these have proven to be so effective for circumvention. But you can just take my word for it now, that they are, and have been for more than a decade.

FEP-like protocols have a long history in circumvention

Shadowsocks "stream ciphers" → Shadowsocks "AEAD ciphers"

Obfuscated OpenSSH (2009) → obfs2 (2012) → obfs3 (2013) → ScrambleSuit (2014) → obfs4 (2014)

VMess

And these are, like, among the most important class of circumvention protocols. And in fact, there are distinct lineages of these. Different developers have hit upon this idea at different times, and developed the idea independently, and it has just proved so effective, that they have continued to be used even to today. So, I know of at least three distinct lineages of fully encrypted circumvention protocols.

There is the Shadowsocks lineage. One of the attacks we'll talk about today is in Shadowsocks so-called "stream ciphers" mode, and then there is a successor to that, they call "AEAD ciphers" in Shadowsocks. Another lineage, the "obfs" lineage, goes way back to 2009, there was Obfuscated OpenSSH, led to obfs2, led to obfs3, ScrambleSuit broke the naming convention, and obfs4. And obfs4 is actually pretty good. You can see, it's decade old, and still being used. There are things now, that looking at obfs4, we say, we would do things a little differently. Right? There are some things that we would repair. But the only protocols that you can say that about, that you can actually complain about, are the ones that have survived this long. So it's actually, generally, pretty good, and is really one of the workhorses of circumvention today. Another one is VMess, this is often used in the V2Ray circumvention framework. So, this idea has just been hit upon multiple times in history and has just proved to be really effective.

So, take my word for it that these are good for circumvention, and also, in that threat model, we're going to consider any distinguishability from random, we consider that a break. Like, that's a flaw in the protocol. So, the attacks here are generally going to be distinguishability from random, although in one case, the very first one we'll look at, it's actually much worse.

Shadowsocks stream ciphers decryption oracle

"Redirect attack on Shadowsocks stream ciphers"
Zhiniang Peng
https://github.com/edwardz246003/shadowsocks
https://github.com/net4people/bbs/issues/24

Stream ciphers are completely broken and will be removed soon. New users must use AEAD ciphers.
This historic document is for educational purposes only.

https://shadowsocks.org/doc/stream.html

Client and server have a preshared symmetric key. The same key is used for encryption in both directions and across connections. Only the IV changes in different connections.

client→server	`IV`	1	`IPv4`	`port`	`data…`
server→client	`IV`	`data…`

The server receives and starts decrypting the client's stream, checks for the magic byte 1, tries to make a TCP connection to the specified target at IPv4:port, then forwards the decryption of the rest of the stream.

The server encrypts any downstream data received from the server and sends it back to the client.

This is a quick example of what the Shadowsocks stream ciphers mode looks like. And what I like about this, is it looks just like the first protocol you would invent in your first semester of learning cryptography, and you wanted to implement a proxy protocol. Which, actually, probably is not that far from the truth in terms of its historical development. So, both sides have a shared symmetric key. It's preshared in advance. And the same key is used to encrypt in both directions. And the key never changes. So the only thing that changes across different ~~protocols~~ connections is this random IV that happens at the beginning of the message.

These all use stream ciphers. The first client-to-server message, after the IV, you send a target specification, which is 7 bytes. The first byte is a literal byte "1", then there's 4 bytes for an IPv4 address, and then there's 2 bytes for a port number. The Shadowsocks server receives that stream. It starts to decrypt. It decrypts the first 7 bytes, it checks for the first byte being "1", then it decodes the IPv4 address and the port number, and then it makes a TCP connection to that requested destination. Now, it's actually a little more complicated than this. There are also constants for IPv6 addresses and hostnames. We'll just ignore that. We'll just assume it's only IPv4. And after it connects to that destination, it will just decrypt the rest of the stream, and send it to that destination. Anything the destination sends back, the Shadowsocks server will encrypt, using the same key and its own independent IV, and send back to the client. All right? Pretty clear.

This here, just this much information, is enough to imply the attack.

David Fifield

It's not the same IV. Although I did find one implementation that erroneously did use the same IV. It's not supposed to be the same IV. There's enough here to see the attack. It does require a little creativity. One kind of creative attack, which is not the one I'm going to emphasize, if you send just random bytes to a Shadowsocks server, notice there's not authentication or authenticity anywhere. There's no MACs or anything like that. If you send random bytes to a Shadowsocks server, with probability 1 out of 256, that first byte will decrypt to a "1", and it will try to initiate a connection. So we actually have a timing side channel. You just send a bunch of random bytes, and when you see it takes longer in 1 out of 256 cases (again, I'm ignoring some details here), you can say, oh, this is likely a Shadowsocks server. So that's a genuine attack, but that's not the one that I'm going to show you, which is much more devastating.

Idea: take a recorded server→client stream and replay it as a client→server stream.

The Shadowsocks server will interpret the first 7 bytes as a (addrtype, IPv4, port) target specification, decrypt the rest of the stream, and send it to that target.

This gives an attacker awkward oracle access to the server's secret key.

An attacker who can guess the first 7 bytes of plaintext (e.g. "HTTP/1.") can XOR its own IP address into the target specification and have the plaintext sent to a destination of its choosing.

Here's the idea. We have no integrity protection, and also we have the same key being used in both directions. Those are kind of the keys to this. Also, maybe I didn't emphasize this, but we are using stream ciphers, as the name suggests, and they're malleable. Right? You can just XOR them from outside. What we're going to do is take a previously recorded server-to-client stream, a downstream, we're going to replay it back in the upstream, the client-to-server direction. Now what happens when we do that? So there's a difference…

I wonder if I can go backwards. Yeah.

Notice there's a difference. In the client-to-server direction we have that target specification, those 7 bytes. In the server-to-client direction, we don't have that. So what happens when we sent that to the server as if it were a client stream? Well, the server is going to decrypt it, it will still decrypt, and decrypt those first 7 bytes, and see, does it look like a target specification, does the first byte decrypt to a "1", and if so, I'm just going to connect to whatever this IP address and port is.

So this is kind of weird, right? You've got this host out there that you can send ciphertext to, and it will decrypt it, and it will send it… somewhere on the Internet. Right? Whatever those bytes decrypt to, it's going to send it there. With the caveat that the first one has to be a valid addrtype, that constant byte "1". The full attack here, though, is that if you know, or you can guess, the first 7 bytes of the plaintext, you can modify it so that those first 7 bytes decrypt to an IP address of your choosing. So let's walk through the way that you might develop this attack.

Replay a recorded server→client stream to the server. (IV omitted here.)

7c20f534e986dbce37f555c6760ea24faa928f76

The server logs:

unsupported addrtype 72, maybe wrong password or encryption method

	`7c20f534e986dbce37f555c6760ea24faa928f76`
⊕	`485454502f312e` ("`HTTP/1.`")
⊕	`01cb0071051f40` (203.0.113.5:8000)
	`35bfa115c3a8b5ce37f555c6760ea24faa928f76`

"Why care about chosen ciphertext attacks? Won't it just decrypt to gibberish?"

"How would an attacker get access to a decryption oracle anyway?"

So here's how you do that full attack. We start with that recorded stream. We take the first 7 bytes, and we XOR in this ASCII, "HTTP/1.", and then we XOR in our own target specification, you can see it start with the constant byte "1" there and then there's an IP address and a port. Now, when the server decrypts it, it will see the first 7 bytes is a constant byte "1", an IPv4 address, and a port number, and that can be anything we want, and we can have that server just send that decrypted plaintext back to us. I don't know. It's a really cool attack.

Now the other thing I really like about this. Beside this protocol being, like a very natural to implement protocol, right, this is the kind of thing that you do when you're beginning with cryptography. I remember helping TA security courses, and students would have questions about this, like: "Why do we care about chosen ciphertext attacks?" "If an attacker messes with the ciphertext, won't it just decrypt to gibberish?" And for example, in the talk this morning, it will mess something up in the application layer, and things are just going to fail eventually anyway. And here's an example where we really care about ciphertext integrity. And another one is, when we play this, like, adversary game, in a chosen-ciphertext attack scenario, "Why is it realistic to give an attacker access to a decryption oracle? How would you ever have that in practice?" And here's an example, in a non-contrived, very naturally developed protocol, where that can arise.

obfs4 and Elligator

obfs4

Forward secrecy (X25519 handshake)
Server authentication
Integrity protection
Probe resistance

Elligator

Represents public curve points (ephemeral public keys for Diffie–Hellman) as uniform random byte string "representatives".

All right, we're going to move on to the next batch of attacks. And this in the obfs4 protocol. And specifically, it's just in the key exchange part of the obfs4 protocol. So obfs4 was developed around 2014, and it was developed specifically in response to the known problems in some earlier FEP-like circumvention systems. And, so, it is much better cryptographically than a bunch of ones that went before. So it has forward secrecy, it starts off with an elliptic curve Diffie–Hellman exchange to do an ephemeral session key. It has server authentication, it has integrity protection (with one caveat I won't get into). And it has another property, not really cryptographic, but very important for circumvention protocols, called probing resistance.

Now, we do this elliptic curve Diffie–Hellman exchange, we have a problem, which is that if you send elliptic curve points straightforwardly on the wire, they are distinguishable from random. Right? If you send an x- and y-coordinate, you can just say, oh, they satisfy the curve equation. Even if you just compress down to the x-coordinate, you can still tell, these are not random bits. So you need some way to obfuscate those keys that you're exchanging, because you don't have a shared session key to encrypt them yet, and you need to do it in a way that looks like random, because that's a security requirement of the protocol.

So how do we do that? There is an algorithm called Elligator that does exactly this. It maps from elliptic curve points to bit strings that are indistinguishable from random, and then back again. So obfs4 uses this algorithm to take its Diffie–Hellman shares, turn them into pseudorandom bit strings, and then exchange those. So the whole protocol still looks like uniformly random. We call these "representatives", the byte string representation of the public key points.

A graph of pluggable transports used to access Tor from 2024-05-20 to 2024-08-18. The order of transports from most to least is obfs4, snowflake, Default OR protocol, meek.

Circumvention protocols used to access Tor. (Tor Metrics.)

obfs4 begins with an elliptic curve Diffie–Hellman key exchange. Client and server exchange ephemeral public keys from which a shared session key is derived.

Public keys are sent as Elligator representatives, so they look as random as the rest of the protocol.

Non-canonical public key representatives
Most significant bit always zero
Only points from the large prime-order subgroup

Non-canonical representatives

The final step of the Elligator inverse map is to take a square root in GF(q), where q =2²⁵⁵ − 19.

The square root is supposed to produce only non-negative outputs (e.g., field elements in [0, (q − 1)/2]).

The implementation of Elligator used at the time did not use canonical square roots, and instead systematically produced either a positive or negative square root for a given input. (In other words, bit 254 was not independent of the lower bits.)

"Implementing Elligator for Curve25519" (2013)
Adam Langley
https://www.imperialviolet.org/2013/12/25/elligator.html

The first was that the representatives were what we say are "non-canonical". Has anyone used Elligator before, or knows how Elligator works? Okay. The final step in the Elligator inverse map, which is what takes you from a point to a byte string, is to take a square root in a finite field. And there is an easy-to-miss requirement that this square root is supposed to be what has come to be called "canonical", meaning that you need to designate just about half the field as being non-negative, and it need to only map to those non-negative elements. Right? So this one detail, the implementation that was widely used at the time, of Elligator, missed this one detail. And what that means is, it would systematically give you either a positive or a negative square root depending on the input. And to put that in practical terms, what it means is that bit 254 of your byte string was not independent of the lower-order bits. Right? It was a consequence of those bits. You could see that correlation, and you could say, this is definitely non-random, if you observe enough of these over time.

Oh, and I should say, all of these obfs4 attacks have the same sort of flavor, in that they are passive attacks, but they are also probabilistic. By looking at one connection, you can't be certain. You're going to have to look at a bunch of connections over time to build up confidence that this really is non-random. In this case, you've got a 50% chance of increasing your confidence at each iteration.

The attack: observe a possible public key representative at the beginning of a suspected obfs4 connection.

Interpret the bytes as a field element, square it, and take the square root using the same non-canonical square root algorithm.

The output will match the input only 50% of the time for random byte strings, but 100% of the time for the non-canonical representatives.

"Incorrect (non canonical) representative output for ScalarBaseMult()" (2020)
Loup Vaillant
https://github.com/agl/ed25519/issues/27

Most significant bit always zero

Elligator outputs 254-bit representatives (when the canonical square root is used). But programming interfaces are more naturally expressed using bytes, not bits.

Unclear API boundaries meant that nothing was randomizing the remaining 2 bits of the byte[32].

$ perl -an -e '/^obfs4 (\S*) (?:\S+) cert=(\S+)/ && \
print "$1 $2\n";' bridges.txt | while read addr cert; do \
./obfs4-bug-check $addr $cert; done
.................... 185.31.174.60:443 FAIL 0/20
.................... 142.132.237.143:2538 FAIL 0/20
1.111...1...1..11..1 90.127.32.238:42024 PASS 9/20

https://bugs.torproject.org/tpo/anti-censorship/team/91

All right. The next attack. You can maybe argue whether this is a crypto attack. I'd say it kind of still counts as a crypto attack. When you do the Elligator inverse map, it has a 254-bit output. And that's if you're using the natural way of doing this canonical square root algorithm. Right? Because they're always going to be positive, the sign bit's always going to be zero, so you have 254 bits of output. But when you're programming, you don't really have a 254-bit data type. Right? What do you have? You have an array of 32 bytes. 256 bits. Like, that's what's convenient to program with. And because of, sort of, a lack of understanding of responsibility, or unclear API boundaries, nothing was touching those top 2 bits. I mean, the second-to-last bit was being set as a result of the previous distinguishability flaw. But the top bit was never being set, and you could look at a bunch of these connections and say, oh, this bit is never being set. That's clearly non-random. Right?

Here's an example of a remote tester that I wrote for this, testing some of the obfs4 bridges available for Tor at the time. And you can see the top two are failed, because they always return zero. The third one returned a mix of zero and one, and so it passes the test. According to this test, we cannot say that it's not random. The reason why I say this maybe counts as cryptographic is, you know, there is such a thing as misuse-resistant cryptography, and this is one example of how, this is an API that is just easy to misuse.

Only points from the large prime-order subgroup

Curve25519 has order 8p for a large prime p. To avoid small-subgroup attacks, the base point of X25519 generates the subgroup of order p. Also, private key scalars are "clamped" to be multiples of 8.

But Elligator representatives must not always represent points on the order-p subgroup, because random byte strings do not have that property.

The passive attack is to observe a suspected obfs4 handshake, map the public key representative to an elliptic curve point, multiply by p, and check for the result always being the identity element.

https://bugs.torproject.org/tpo/anti-censorship/pluggable-transports/lyrebird/40007

And this one's probably the most subtle one. This one was discovered later. This attack was discovered later that the earlier ones. So, Curve25519, which is used in this key exchange, it has order 8p, where p is a large prime. And the X25519 key exchange kind of has your back. It does a lot of things to protect you against small-subgroup attacks. So the base point of X25519 generates the subgroup of order p. And, by convention, private keys in X25519 are "clamped" to be multiples of 8, so that even if you get some other random point, you'll still end up on order-p subgroup.

But when your doing the Elligator representation, you do not want things that are on the order-p subgroup, just because random strings do not always map to the order-p subgroup. This is very very easy to overlook. There is a writeup by Loup Vaillant who was implementing Elligator, and has a section in his writeup called "dodging a bullet". And this is very non-obvious if you read the Elligator paper. I mean, there are a lot of pitfalls.

So the attack here, is again, you observe a suspected handshake, you take that public key representative, you map it to an elliptic curve point, you multiply by p, and you check, is it always the identity element. And again, you have the same sort of balance of increasing confidence with multiple observations.

If you're doing any implementation with Elligator, your first stop should be https://elligator.org/.

The effect of these attacks

Shadowsocks stream ciphers are dead (one hopes), but Shadowsocks is otherwise still going strong.

obfs4 implementations were patched and obfs4 continues to be a workhorse in Tor and elsewhere. There's no evidence of any of these passive obfs4 distinguishability attacks having been used in practice.

Fully encrypted protocols remain probably the most important single class of circumvention protocols.

"How the Great Firewall of China Detects and Blocks Fully Encrypted Traffic" (2023)
Mingshi Wu, Jackson Sippe, Danesh Sivakumar, Jack Burg, Peter Anderson, Xiaokang Wang, Kevin Bock, Amir Houmansadr, Dave Levin, Eric Wustrow
https://gfw.report/publications/usenixsecurity23/en/

All right. So here's where we tie it back to censorship threat models in practice. What was the effect of these? Well, okay, Shadowsocks stream ciphers are kind of dead, right? But Shadowsocks continues on. It still has a large and thriving development community. obfs4 continues on. obfs4 is still one of the most widely used circumvention protocols. And fully encrypted protocols are still probably the most important single class of circumvention protocols. Even though there are many many different kinds.

You may say, David, I'm aware of this research that said in China, the Great Firewall was blocking protocols that appeared to be encrypted. That's true. But what you don't get from reading that paper is that that detection actually went away, after a while. So that's kind of a curious… That helps enrich your mental model of how censors work. It's not true, anymore, that fully encrypted protocols cannot be used in China.

Why?

In circumvention, the crypto is usually not the weak link. Available evidence indicates that censors prefer to attack circumvention systems in other ways, when possible.

Censors are not just classifiers—they also bear asymmetric costs for misclassifications.

Classification advantage is asymmetric: censors are highly sensitive to false positives. A classifier FPR of 0.1% spells a successful circumvention protocol.

Corollary: censors almost universally prefer allow-by-default rather than deny-by-default, fail open rather than fail closed.

Censors, empirically, dislike employing probabilistic or stateful attacks like the obfs4 passive distinguishers.

So, why is it that, despite these cryptographic attacks, and these weaknesses, why did these continue on being strong and important? Well, one of it is that, in circumvention, crypto is necessary but not sufficient, and it's often not the weak link in this whole chain of things that have to go right in order for circumvention to happen.

In cryptography, you often talk about distinguishers—we often say "classifiers" when we're talking about network stuff—but a censor is more than just a classifier. Right? This is how I picture it to myself. A censor is a classifier plus a cost model. It's like, plus a utility function. And the costs are very very asymmetric. And that means, in a crypto context, you may be interested in something that is non-negligibly different from ½, right? But in a circumvention context, if we get a false positive rate of 0.1%, that's like, we win. Right? Because if you're falsely classifying, if you're blocking 0.1% of network traffic, in order to catch the 0.0001%, or whatever, of actual circumvention traffic, you're actually just going to be breaking, you're going to be wrecking a lot of the utility of the network. So there's this huge asymmetry, and that's one difference between cryptographic and circumvention threat models.

We see this in practice by censors, almost always, preferring allow-by-default rather than deny-by-default. And that's almost universal across the world. And another thing we see is that censors, for whatever reason, they hate applying attacks like those obfs4 attacks I showed you. Those ones that require maintaining state, or correlating multiple different connections over time. If a censor has an attack where they just have to look at one packet, like a DNS response injection, they will do that. If they have an attack that requires reassembling a TCP stream, it's like, "oh, okay, but I'm only going to reassemble like the first 10 packets". Right? You see these sorts of cost constraints start to creep in, because when you're doing stuff on a big network, like, international transfer point, you actually have to be somewhat concerned about, what is the computational, and what is the memory cost of all these operations that I'm doing on every connection? So this is a little insight into the censor mindset.

Shadowsocks, for its shortcomings, is easy to specify and easy to implement, and for those reasons has huge support and momentum.

…worse-is-better has better survival characteristics than the-right-thing…

https://dreamsongs.com/RiseOfWorseIsBetter.html

Circumvention technology stands to benefit from better cryptography, but we must still have due respect for the other factors that matter.

Another aspect is this "worse is better" idea. You've probably seen this essay, and it's got a phrase in it that I've always loved: "…worse-is-better has better survival characteristics than the-right-thing…".

And Shadowsocks, to me, is kind of an example of worse is better. It can be criticized cryptographically on a lot of grounds, even the newer Shadowsocks AEAD has some shortcomings, but, because it's so simple to implement, it's so easy to understand, this whole ecosystem and market has grown around it, there are people who know the protocol, who can provide user support, who can do documentation, who can sell this stuff commercially… It's really hard to beat that kind of advantage.

And so what I mean to communicate, by saying all this, is that it's not that cryptography is irrelevant to circumvention. I think that circumvention stands to gain from a lot more involvement from people who know cryptography really well. And you could help, you know, shape the future of the field. But we also have to have due respect for all the other forces that matter for these things in practice.

机场jīchǎng

"Airports" are paid Shadowsocks/etc. hosting services that are common and commonly used in China.

Shadowsocks logo.

All right, we're almost done, but I'm going to teach you a Chinese word. The word is 机场 jīchǎng. And this word means "airport". It's just the ordinary Chinese word for airport. But it's also Chinese slang for a Shadowsocks, or similar, reseller. So there are businesses in China that will set up some Shadowsocks servers on some VPS somewhere, or they'll set up some obfs4 servers. And then you pay them money, and they give you an IP address and they give you a password, and they say, here's your server that you can use for circumvention. And it's a huge market in China! This is a big thing. The reason they call them airports, by the way, is because of the Shadowsocks logo, which is a paper airplane.

Such that, the Great Firewall of China is often held up as the most difficult censor, the most extreme censor. But really, if you're deploying a censorship circumvention system in China, your greatest competition may not be the Great Firewall, but your actual competitors. Right? Your business competitors. Because there's so much back-and-forth and it's so developed there. So this is another way in which, you know, the real-world threat models may not match your intuition.

Why doesn't a simple TLS connection to a proxy suffice?

TLS fingerprinting
Active probing
But the big one is: how do you prevent the censor from discovering the IP addresses of your proxies and simply blocking them by IP address?

In practice, the biggest challenge is not protocol obfuscation but endpoint blocking: the "bridge distribution problem".

"Lox: Protecting the Social Graph in Bridge Distribution" (2023)
Lindsey Tulloch, Ian Goldberg
https://censorbib.nymity.ch/#Tulloch2023a
https://github.com/net4people/bbs/issues/320

All right, we're just about finished. And now we should have enough background, here, to answer a question. This is another question I often get. And I hope you have the perspective now to consider this thoughtfully. We need an encrypted proxy, why don't we just use TLS to some random IP address? Why doesn't that suffice for circumvention? Well, there's a few reasons.

One is that there's TLS, and then there's TLS. If you implement your TLS client and server using, like, the normal Python libraries, the normal Go libraries, the normal Rust libraries, you will get blocked. And why is that? Because of TLS fingerprinting. There are different ways to implement TLS, different ways to order the fields in a Client Hello, all things like that, and if you do that incorrectly, and you don't look like Nginx, or you don't look like Chrome, or you don't look like Firefox, you'll get blocked on that basis. And this is real. This has happened to me, in fact.

Another is active probing. Think about this attack scenario: the censored client connects to its secret TLS proxy. The censor, in the middle, observes this connection happening, and says, this is a little bit suspicious. What I'm going to do is I'm going to make my own TLS client connection to that same server, and I'm going to try speaking a proxy protocol to it. And if it responds in the way that I expect, I'm going to block it. This also really happens. This is also an attack you need to worry about. You need some way to mitigate that, which is separate from just TLS superencryption.

But the big problem here, the real killer, is: how do you communicate that server's identity to your users, without also communicating it to the censor? Users generally are people you don't know. You need to somehow get it out there to them. How do you do that without giving that up to the one who's going to block your servers? And this is the endpoint blocking aspect of circumvention, which I didn't get into very much here, but in my mind, it's almost harder than the protocol obfuscation part. The good news, for this venue, is that there is also a place for cryptography in this problem. A good place to start, if you're interested in this, is this paper from last year, Lox. And it is a crypto-based paper, it uses anonymous credentials in order to build up a reputation for users, in order to avoid giving bridge identities to untrustworthy users, people who are agents of the censor, and thereby getting them blocked. So there's a space for cryptography also in this very fascinating aspect of circumvention.

David Fifield <david@bamsoftware.com>

The censorship and circumvention forum I manage: https://github.com/net4people/bbs

David Fifield

Yeah yeah. Very good. This is actually a really fascinating and current topic. For many years, I have sort of deprecated these types of classification, because it used to be very popular, especially among program committees, they were like, "What are you doing against traffic fingerprinting? What are you doing against obfuscating packet sizes and timing?" Sort of, what we think of as like, web site fingerprinting attack models. And I think it is still correct that you should basically ignore that issue until you have covered all these other fundamentals.

But it is something that is becoming more and more important. And, for example, there is a recent thread on the forum from this April, about possibly the first time, the first time I'm aware of, of this type of classification being used in practice. There's reliable documentation of it having been used in some ISPs in Russia starting back in April, where you could send random bytes, and if you send them in a certain—with certain thresholds—and a certain amount of like, slop is allowed—that seem to map onto TLS, the sizes of Client Hellos and things like that, your connection will get blocked. So this was the first time we've actually seen that in practice. It's actually one of my current research interests and one of the things I'm working on, is making tools more able to shape their traffic in order to counter this sort of threat. But yeah. You're absolutely right. After everything is random, you still have things like packet boundaries and timing.