The Chrome browser recently added a feature that randomizes the order of TLS extensions in an attempt to discourage or impede TLS fingerprinting. Because of this, the fingerprinting techniques used by network defenders and the threat intelligence community need to adapt how they normalize data. Fortunately, there is a simple solution that is quite effective. This post reviews TLS fingerprinting, then explains Chrome’s use of randomization and how sort normalization counters it, and its effect on accuracy . It also presents some security issues with randomization, and suggests that security protocols like TLS use a canonical ordering instead of randomization.

Fingerprinting the TLS Protocol

Protocol fingerprinting is an essential technique to detect malicious activity when monitoring networks; it can identify the applications, libraries, or operating systems creating network sessions. Fingerprinting the ubiquitous TLS protocol is especially important, because it is used in the majority of Internet connections. TLS fingerprinting is used in Network Protocol Fingerprinting (NPF), JA3, and other network security tools.

Note that TLS fingerprinting is totally different than browser fingerprinting, a technology that stealthily tracks individual users based on how their browser responds in web sessions. Browser fingerprinting is what unscrupulous web servers do to track you; TLS fingerprinting is what network defenders do to track malware. (You can find out how vulnerable you are to browser fingerprinting, and how to better protect yourself, from the Electronic Frontier Foundation.)

Randomized TLS Extensions

The Chrome browser recently started randomizing the order of TLS extensions in the Client Hello messages, to discourage server and middlebox implementations from fingerprinting that browser. Mozilla has work in progress to do the same thing.

The Client Hello is the first message in a TLS session; it starts the ‘handshake’ that clients and servers use to agree on the protocol options and cryptographic algorithms and parameters used in the session. A typical Client Hello message contains many extensions, which are used to express things like the protocol versions and cryptographic parameters supported by the client. There are 61 TLS extensions currently registered with the Internet Assigned Numbers Authority. The standard does not specify the order in which extensions appear (other than the pre_shared_key extension, which must be last), and different applications exhibit different orderings, mostly due to idiosyncrasies in the implementations. For most applications and libraries using TLS, the order of the extensions is the same for every run of the protocol, which makes that data feature useful in fingerprinting; it is used in the original TLS fingerprint format in NPF and in JA3. Those formats use a list of extension type codes that summarizes the extensions that appear in the Client Hello, in the order that they appear in that message. With randomized TLS extensions, the ordering of the extensions changes across different sessions, and each ordering will have a distinct fingerprint.

Sort Normalization

If you are a programmer or a fan of anagrams, the way to create fingerprints that are robust against randomization has probably already occurred to you: sort the extensions into order. We recently introduced a new format for TLS fingerprints in NPF, called npf:tls/1, which does just that. The slash and digit are just part of the naming scheme used to identify how a fingerprint was formed (NPF uses a URI scheme). The NPF QUIC fingerprint definition has always used sorting, for the same reason.

The example below illustrates how sort normalization works by showing the older and newer formats for the same Client Hello message. At top is the older format, pretty-printed with indentation to reveal the tree structure. The first line is the protocol string tls/. Each following line is a (possibly normalized) data field from the message, in hexadecimal. Lines 5 through 14 are the extensions, which are surrounded by parenthesis.

tls/
(0303)
(130213031301c02cc030009fcca9cca8ccaac02bc02f009ec024c028006bc023c0270067c00ac0140039c009c0130033009d009c003d003c0035002f00ff)
(
   (0000)
   (000b000403000102)
   (000a000c000a001d0017001e00190018)
   (0023)
   (0016)
   (0017)   
   (000d0030002e040305030603080708080809080a080b080408050806040105010601030302030301020103020202040205020602)
   (002b0009080304030303020301)
   (002d00020101)
   (0033)
)

The newer format is below. The tls/1 in the first line indicates the format version, and the extensions are surrounded by square brackets and are sorted lexicographically.

tls/1/
(0303)
(130213031301c02cc030009fcca9cca8ccaac02bc02f009ec024c028006bc023c0270067c00ac0140039c009c0130033009d009c003d003c0035002f00ff)
[
   (0000)
   (000a000c000a001d0017001e00190018)
   (000b000403000102)       
   (000d0030002e040305030603080708080809080a080b080408050806040105010601030302030301020103020202040205020602)
   (0016)
   (0017)
   (0023)
   (002b0009080304030303020301)
   (002d00020101)
   (0033)
]

The list of normalized extensions are sorted into lexicographic order, and the sorted list is included in the fingerprint format, surrounded by square brackets. The computational cost of the sorting step can be kept low by sorting a vector of references to the extensions, as opposed to sorting the extensions themselves, which avoids needless data movement.

To understand the examples above, it helps to realize how extensions are normalized to remove session data. The first two bytes of each extension (which correspond to the first four hex digits) are the extension’s type code. For extensions that contain session data, like 0000 (server name), only the type code is included in the format. For other extensions, like 002b (supported versions), the extension data is included in the format, as well as the type code.

Does Randomization Degrade the Effectiveness of Fingerprinting?

No. If sort normalization is used, there is almost no degradation in the ability to distinguish between implementations. In an experiment on packet captures of one-year old application traffic in which no clients were using randomization, I extracted fingerprints in both the npf:tls/1 (sorted) and npf:tls (unsorted) format. I found 2,149 distinct fingerprints with the npf:tls format, and 2,123 distinct fingerprints in the npf:tls/1 format. That is, 98.8% of the fingerprints are still distinct after sorting, because there are a lot of other data features in the fingerprints, and a lot of inherent diversity in implementations. Additionally, the randomization behavior itself is an identifiable data feature that could be used in fingerprinting.

Working With Different Formats

There are many existing data captures, databases, and threat intelligence reports that use the npf:tls and ja3 fingerprint formats, so it is important to be able to convert between formats. npf:tls fingerprints can be directly converted into npf:tls/1 fingerprints by sorting the extensions list. They can also be converted into ja3 fingerprints, by translating to the JA3 intermediate representation and then applying the MD5 hash function. It is not possible to directly compute an npf:tls from a ja3, because npf:tls includes more data features than ja3, and thus a single ja3 can correspond to multiple npf:tls fingerprints; furthermore, MD5 cannot be reversed. But if you have a large database of npf:tls fingerprints, you can compute all of the corresponding ja3 fingerprints, and thus effectively provide a table of all of the npf:tls fingerprints that a ja3 maps to (the mercury team published a tool to do this; perhaps we should publish the whole table). Mercury can now report TLS fingerprints in either format; the command line option --format=tls/1 specifies the newer one.

Problems with Randomization in Security Protocols

There are two significant demerits to randomizing extensions in TLS or any other security protocol. First, it introduces complexity into security-critical code. Second, it introduces a subliminal channel that an untrustworthy implementation could use either to leak part of the secret key, or to provide enough information to track individual users. TLS implementers should consider these issues, and the alternative proposed below, before going down the path of randomization.

The first issue is the easiest to understand. Not only do we have the widely accepted wisdom that complexity is the worst enemy of security, we also have the specific example of the infamous heartbleed vulnerability, which resulted from a bug in the implementation of a TLS extension.

The second issue might be less familiar, but is no less important. An algorithm substitution attack (ASA) replaces an honest implementation of a cryptographic tool by a subverted one that leaks private information while at the same time generating output indistinguishable from that of the honest tool. The essential idea was first presented in 1997 and called kleptography. After the Snowden revelations about pervasive surveillance, interest in this threat was rekindled, sparking new research that introduced ASAs against symmetric encryption, improved those attacks, and then introduced ASAs against digital signatures. In 2015, an actual ASA in a major security product was revealed.

A single permutation of 18 TLS extensions, as is common for Chrome, can be used as a subliminal channel that can leak lg(18!) = 52.5 bits, which is enough to undermine cryptographic security of many sessions. The addendum below provides more information on how randomizing the order of protocol elements can be used in the same manner as an ASA. It also provides more details on how the subliminal channel can be used to track individual users, a capability that is not usually considered in the ASA model, but which is even easier to achieve.

Let me be clear: I am not suggesting that the Chrome implementers are untrustworthy, or that they produce buggy code. I use Chrome regularly, and it is great software. But the existence of a single non-buggy, non-subverted implementation does not make the issues above go away. Should all TLS implementations change over to using randomization going forward? Should all security protocols randomize whatever message elements they can? The following section suggests not.

Canonical Ordering: A Better Idea Than Randomization

A better approach to limiting the data features that are usable in fingerprinting is just to use the convention that, when a client can choose any ordering for data elements, it uses the one such that the elements are sorted into lexicographic order. This convention provides no more information than randomization, and technically provides less, because it omits the conspicuous randomization behavior. It is significantly less complex than random shuffling, since it can be implemented straightforwardly using the fact that the order of the extension type codes is easily determined at compile time. Perhaps most importantly, the canonical-order convention eliminates the subliminal channel.

Because of these advantages, standards organizations producing security protocols should consider recommending this approach. To get the discussion started, here is some candidate text:

When the order of data elements is otherwise unspecified, implementations SHOULD use canonical ordering, in which the elements are in lexicographic order. This convention reduces the number of data features that can be used in protocol fingerprinting, by promoting a uniformity that enables implementations to ‘hide in the crowd’. When each data element starts with a type code or keyword, and all of the type codes or keywords in a message are distinct, this convention is equivalent to ordering the elements by ascending type codes or sorted keywords.

There are alternatives to lexicographic ordering, but it is not clear that there are any better ones. For instance, clients could use a specific ordering already in use by a popular TLS implementation. Doing that in a way that was equitable for all TLS clients would require the ongoing maintenance and publication of the canonical ordering, with some process for deciding how new extensions or other data features are handled. In contrast, lexicographic order is natural and requires no coordination.

Addendum: How Randomization Could Be Used To Leak Keys and Track Users

In this addendum, we consider a TLS client implementation created by an adversary whose goal is to undermine the security of the implementation’s users. The adversary could be an intelligence agency that poses as an open source contributor, or bribes a software developer, or surreptitiously modifies a code base or a binary package. This sort of ‘unauthorized code’ is unfortunately quite real. The implementation can leak information to the intelligence agency that helps it decrypt traffic or track users.

There are n! permutations of n elements in total, so a pseudorandom permutation of n elements conveys lg(n!) bits of information (where the logarithm is base two). As Table 1 (below) shows, a modest number of elements can convey a lot of information. With just eighteen elements (a typical number for a Chrome session), over half of a 96-bit key can be leaked in one session, enough to transform a secure algorithm into something that can be broken by a government agency, or possibly even by AWS, GCP, or Azure. If the secret is leaked over two or more sessions, the attack can succeed with even fewer elements.

To effectively leak information through a permutation, what is needed is a method for ranking and unranking permutations. A rank function takes a permutation of n elements as input and returns a number between zero and n!-1. An unrank function is its inverse; it takes a number and returns the corresponding permutation. There are simple and performant algorithms for doing this; a good reference is Ranking and unranking permutations in linear time by Myrvold and Ruskey. I put together a quick proof of concept of the covert channel, and was able to implement both algorithms in about 30 lines of C++. (There is no need for arbitrary precision integers, at least not when leaking a uint64_t or uint128_t worth of data.)

To send a secret through the covert channel, encode it into a permutation of elements using the unrank function. To decode the secret from the channel, obtain the permutation of elements, then use the rank function on it. Encryption could be applied to the secret before unranking, with corresponding decryption after ranking, to ensure that the permutations are actually pseudorandom enough to avoid detection. However, encryption would not be needed if the secrets being leaked are close to uniformly random, as would be the case with leaking some or all of the bits of a secret or private key.

Another possible use of the subliminal channel is tracking individual users, by providing information that could be passively observed in transit or monitored at the server. TLS is designed to prevent this sort of tracking. To use the channel to track users, the basic idea is that each user is associated with a distinct number, and for each session, that number is incremented, encrypted, and then unranked to generate a permutation. After observing a session and obtaining the permutation of elements, it is ranked to obtain the corresponding number, which is then decrypted and added to a database of observations, along with some session data or metadata. Within the observations, an individual will show up as a sequence of consecutive numbers. In this scenario, encryption is needed to make the permutation pseudorandom, because the Myrvold-Ruskey ranking algorithm has conspicuously non-random outputs when applied to consecutive integers. The user-to-number association could be randomly selected at first use, or derived from information such as an email address or a cookie. With this straightforward scheme, at most n! users can be tracked, possibly less if the associations are random. The basic scheme can be improved by using information from two or more sessions, or by combining this information with external context such as source addresses to disambiguate users. But with an 18-element permutation creating a 52.5 bit subliminal channel, the birthday paradox says that even the simple scheme with random user-to-number assignments can track 67 million users.

Top picture credit: A 16-input sorting network, Florian Foster / Wikimedia Commons.