It’s been a while since I wrote an “attack of the week” post, and the fault for is entirely mine. I’ve been busy writing boring posts about Schnorr signatures. But this week’s news brings an exciting story with both technical and political dimensions, namely: that a new Chinese technique is being used to trace AirDrop transmissions.
A quick note: most of my “attack of the week” posts are highlight recent research. This post is therefore a bit unusual: the attack in question is not really new; it dates back to 2019, when a set of TU Darmstadt researchers — Heinrich, Hollick, Schneider, Stute, and Weinert — reverse-engineered the Apple Airdrop protocol and disclosed several privacy issues to Apple. (The resulting paper, which appeared in Usenix Security 2021 can be found here.)
What makes this an attack of the week is a new piece of news initially broken by Bloomberg (other coverage without paywall) claiming that researchers in China’s Beijing Wangshendongjian Judicial Appraisal Institute have used these vulnerabilities to help police to identify the sender of “unauthorized” AirDrop materials, using a technique based on rainbow tables. While this new capability may not (yet) in widespread deployment, it represents a new tool that could strongly suppress the use of AirDrop in China and Hong Kong. And this is a big deal, since AirDrop is apparently one of a few channels that can still be used to disseminate unauthorized protest materials — and indeed, that was used in both places in 2019 and 2022, and (allegedly as a result) has already been subject to various curtailments.
In this post I’m going to talk about the Darmstadt research and how it relates to the news out of Beijing. Finally, I’ll talk a little about what Apple can do about it — something that is likely to be as much of a political problem as a technical one.
As always, rest of this post will be in the “fun” question-and-answer format I use for these posts.
What is AirDrop and why should I care?
Image from Apple. Used without permission.If you own an iPhone, you already know the answer to this question. Otherwise: AirDrop is an Apple-specific protocol that allows Apple devices to send files (and contacts and other stuff) in a peer-to-peer manner over various wireless protocols, including Bluetooth and WiFi.
The key thing to know about AirDrop is that it has two settings, which can be enabled by a potential receiver. In “Contacts Only” mode, AirDrop will accept files only from people who are in your contacts list (address book.) When set to “Everyone”, AirDrop will receive files from any random person within transmit range. This latter mode has been extensively used to distribute protest materials in China and Hong Kong, as well as to distribute indecent photos everywhere else.
The former AirDrop usage became such a big deal that in 2022, Apple pushed a software update to Chinese users that limited the “Everyone” receive-from mode — ensuring that phones would automatically switch back to “Contacts only” after 10 minutes. The company later extended this software update worldwide, but only after they were extensively criticized for apparently bowing to the Chinese government.
How does AirDrop know if a user is in their Contacts list? Also, is AirDrop supposed to be anonymous?
That’s really two different questions, so let’s tackle them one at a time.
Clearly for AirDrop recipients in “Contacts only” mode, there must be some way for a recipient to verify that a potential sender is actually in their Contacts list. This implies that the sender must somehow reveal their identity to the recipient — typically before you’ve even chosen the file you want to send.
But this poses a conundrum: the sender’s phone doesn’t actually know which nearby AirDrop users are willing to receive files from it — i.e., which AirDrop users have the sender in their Contacts — and it won’t know this until it actually talks to them. But talking to them means your phone is potentially shouting at everyone around it all the time, saying something like:
Hi there! My Apple ID is [email protected]. Will you accept files from me!??
Now forget about the phone and imagine yourself doing this to every random stranger on the train. It should be obvious that this will quickly become a privacy concern, even for a company that doesn’t care about privacy. And Apple generally does care quite a bit about privacy!
Thus, just solving this basic problem requires a clever way by which phones can figure out whether they should talk to each other — i.e., whether the receiver has the sender in its Contacts — without either side leaking any useful information to random strangers. Fortunately cryptography researchers have thought a lot about this problem! So much so that we’ve even given it a cool name: it’s called Private Set Intersection, or PSI.
I’ll make a long story pretty short: a PSI protocol takes a set of strings from the Sender and a set from the Receiver. It gives one (or both parties) the intersection of both sets: that is, the set of entries that appear on both lists. Most critically, it doesn’t reveal any other information about either of the sets.
In Apple’s case, the Sender would have just one entry (its own Apple ID) and the Receiver would have a big set (its entire Contacts list). The result would be either (1) the Sender’s address, or (2) nothing. A PSI protocol would therefore solve Apple’s problem nicely.
Great, so which PSI protocol does Apple use?
The best possible answer to this is: 
.
For a variety of mildly defensible reasons — which I will come back to in a moment — Apple does not use a secure PSI protocol to solve their AirDrop problem. Instead they did the thing that every software developer does when faced with the choice of doing complicated cryptography or “hacking something together in time for the next deadline”: they threw together their own solution using hash functions.
The TU Darmstadt researchers do a nice job of reverse-engineering Apple’s protocol in their paper. Read it! The important bit happens during the “Discovery” portion of the protocol, which happens during the HTTPS POST request below:
The very short TL;DR is this:
- In the POST request, a sender attaches a SHA-256 hash of its own Apple ID, as part of a certificate that it gets from Apple. (If the sender has more than one identifier, e.g., a phone number and an email address, this will contain hashes of each one.)
- The recipient then hashes every entry in its Contacts list, and compares the results to see if it finds a match.
- If the recipient finds a match, it indicates this and accepts later file transfers. Otherwise it aborts the connection.
(As a secondary issue, AirDrop also includes a very short [two byte] portion of the same hashes in its BLE advertisements. Two bytes is fairly short, which means this shouldn’t leak much information, since many different addresses will collide on a two-byte hash. However, some other researchers have determined that it generally does.)
A second important issue here is that the hash identifiers are apparently stored in logs within the recipient’s phone, which means that to obtain them you don’t have to be physically present when the transfer happens. You can potentially scoop them out of someone else’s phone after the fact.
So what’s the problem?
Many folks who have some experience with cryptography will see the problem immediately. But let’s be explicit.
Hash functions are designed to be one-way. In theory, this means that there is should be no efficient algorithm for “directly” taking the output of a hash function and turning it back into its input. But that guarantee has a huge asterisk: if I can guess a set of possible inputs that could have produced the hash, I can simply hash each one of my guesses and compare it to the hash. If one input matches, then chances are overwhelming that I’ve found the right input (also called a pre-image.)
In its most basic form, this naive approach is called a “dictionary attack” based on the idea that one can assemble a dictionary of likely candidates, then test every one. Since these hashes don’t contain any unpredictable information (such as salt), you can even do the hashing in advance to assemble a dictionary of candidate hashes, making the attack even faster.
This approach won’t work if your Apple ID (or phone number) is not guessable. The big question in exploiting this vulnerability is whether it’s possible to assemble a complete list of candidate Apple ID emails and phone numbers. The answer for phone numbers, as the Darmstadt researchers point out, is absolutely yes. Since there are only a few billion phone numbers, it is entirely possible to make a list of every phone number and have a computer grind through them — given a not-unreasonable amount of time. For email addresses this is more complicated, but there are many lists of email addresses in the world and the Chinese state authorities almost certainly have some good approaches to collecting and/or generating those lists.
As an aside, exploiting these dictionaries can be done in three different ways:
- You can make a list of candidate identifiers (or generate them programatically) and then, given a new target hash, you can hash each one. This requires you to compute a whole lot of SHA256 hashes, which is pretty fast on a GPU or FPGA (or ASIC.)
- You can pre-hash the list and make a database of hashes and identifiers. Then when you see a target hash, you just need to do a fast lookup. This means all computation is done once, and lookups are fast. But it requires a ton of storage.
- Alternatively, you can use something an intermediate approach called a time-memory tradeoff in which you exchange some storage for some computation once the target is found. The most popular technique is called a rainbow table, and it really deserves its own blog post.
The Chinese announcement explicitly mentions a rainbow table, so that’s a good indicator that they’re exploiting this vulnerability.
Well that sucks. What can we, or rather Apple, do about it?
If you’re worried about leaking your identifier, an immediate solution is to turn off AirDrop, assuming such a thing is possible. (I haven’t tried it, so I don’t know if turning this off will stop the settings.) Or you can unregister your Apple ID, or use a bizarre high-entropy Apple ID that nobody will possibly guess.
But those solutions are all terrible.
The proper technical solution is for Apple to replace their hashing-based protocol with a proper PSI protocol, which will — as previously discussed — reveal only one bit of information: whether the receiver has the sender’s address(es) in their Contacts list. Indeed, that’s the solution that the Darmstadt researchers propose. They even devised a Diffie-Hellman-based PSI protocol called “PrivateDrop” and showed that it can be used to solve this problem.
But this is not necessarily an easy solution, for both technical and political reasons. It’s worth noting that Apple almost certainly knew from the get-go that their protocol was vulnerable to these attacks — but even if they didn’t, they were told about these issues back in May 2019 by the Darmstadt folks. It’s now 2024, and Chinese authorities are exploiting it. So clearly it was not an easy fix.
Some of this stems from the fact that PSI protocols are more computationally heavy that the hashing-based protocol, and some of it (may) stem from the need for more interaction between each pair of devices. Although these costs are not particularly unbearable, it’s important to remember that phone battery life and BLE/WiFi bandwidth is precious to Apple, so even minor costs are hard to bear.
However in this case there is an even tougher political dimension.
Will Apple even fix this, given that Chinese authorities are now exploiting it?
And here we find the hundred billion dollar question: if Apple actually replaced their existing protocol with PrivateDrop, would that be viewed negatively by the Chinese government?
Those of us on the outside can only speculate about this. However, the facts are pretty worrying: Apple has enormous manufacturing and sales resources located inside of China, which makes them extremely vulnerable to an irritated Chinese government. They have, in the past, taken actions that appeared to be targeted at restricting AirDrop use within China — and although there’s no definitive proof of their motivations, it certainly looked bad.
Finally, Apple has recently been the subject of pressure by the Indian government over its decision to alert journalists about a set of allegedly state-sponsored attacks. Apple’s response to this pressure was to substantially tone down its warnings. And Apple has many fewer resources at stake in India, although that’s changing.
One hopes that despite all these concerns, we’ll soon see a substantial push to improve the privacy of AirDrop. But I’m not going to hold my breath.
Article Link: Attack of the week: Airdrop tracing – A Few Thoughts on Cryptographic Engineering