Hashing IMEI numbers does not protect privacy

In an effort to protect the privacy of users, mobile apps sometimes hash the user’s IMEI number prior to sending it to a server. We found that hashing IMEIs does not protect the privacy of users, even with the use of cryptographically secure hash functions. This result is due to the fundamental structure of IMEI numbers.

IMEI numbers and privacy concerns


Each modern cell phone has a private IMEI number—a 15-digit number that uniquely identifies the device on the cellular network. IMEIs are primarily useful for tracking stolen devices. As a secondary use, IMEIs are often re-purposed as user IDs in mobile applications.

Using IMEIs as user IDs represents a threat to privacy because it enables unrelated applications to compare notes on your behavior. For example, say I use two unrelated applications published by two different corporations: a web-browser app and an email app. The web-browser app knows which websites I visit (but not my real name), whereas the email app knows my real name (but not which websites I visit). If both apps use the IMEI as my user ID then the corporations can easily compare notes since they both share a common ID that uniquely identifies me. My privacy is threatened since it is possible for my browsing habits to be tied to my real name.

IMEI numbers can also help attackers spoof your identity. For example, a voicemail app might have the security feature that it only delivers voicemail to the user’s specific cell phone (as opposed to allowing the user to check their voicemail from multiple devices). One way the voicemail app might authenticate the phone is by checking that the phone’s IMEI number matches the user’s registered IMEI number. If an attacker learns the IMEI number of a particular user, it can help them impersonate that user and access their voicemail.

IMEI leakage

We recently behaviorally analyzed 10,000 apps from the Android Market for a mobile-malware survey for Black Hat 2011. To the best of our knowledge this study represents the largest behavioral analysis of Android apps to date. In agreement with previous studies (such as TaintDroid and Taming), we found that Android apps often leak IMEI numbers over the web. We observed that at least 8% of apps leaked the user’s IMEI number. 93% of those apps leaked IMEI numbers in the clear. In the other 7 percent, the apps hashed the IMEI with either MD5 or SHA-256—presumably in an attempt to protect user privacy.

Hashing the IMEI may seem like a good way to protect the privacy of users, since it is supposed to be difficult to reverse a hash value to obtain on original message. However, the inherent structure of IMEI numbers makes them vulnerable to reversing via lookup tables.

Background: lookup tables

Cryptographic hash functions should be irreversible. That is, it should be easy to generate a hash value from an original message but infeasible to reverse a hash value back to an original message. However, if the original messages are not sufficiently random, then hashing can be defeated using lookup tables—which are essentially dictionaries that map hash values back to original messages.

To generate a lookup table for IMEIs you simply need to go through a list of IMEIs, generating the hash value for each IMEI. Then to reverse a hash value, you simply look up the corresponding IMEI in the table. (For improved space efficiency you can use a rainbow table in place of a lookup table.)

First five entries in one of the iPhone lookup tables

Hashed IMEIs are vulnerable to lookup tables

Complete lookup tables are usually infeasible to build because there are so many possible entries. And at a first glance, it seems infeasible to build a useful lookup table for IMEI hashes. There are 10¹⁵ = one quadrillion possible IMEI values, necessitating 10¹⁵ entries.

For most adversaries, it would require a prohibitive amount of computation to create such a large lookup table. On my 8-core 2.26 GHz machine, I can hash 8 million IMEI numbers in about 2 seconds, using the SHA-1 cryptographic hash function. At that rate it would take about 8 years to compute all the hashes for a complete lookup table.

However, IMEI numbers are not distributed uniformly at random. The first 8 digits of an IMEI represent the Type Allocation Code (TAC), which is determined by the model of the phone. For example, because I have an HTC Thunderbolt, the first 8 digits of my IMEI are 99000032. Although this is the most significant portion of my IMEI number, it is not private information; knowing the model of my phone (or guessing the model) is sufficient to guess most of my IMEI number.

After the 8-digit TAC there are 6 digits that uniquely identify the specific cellular device. In the screen shot of my phone, I x’ed out those 6 digits to protect my privacy. These 6 digits are the only digits that are difficult for an attacker to guess. After those 6 digits the last digit is a Luhn-checksum digit, which is computed as a function of the first 14 digits. Thus, in a 15-digit IMEI number there is a relatively low amount of randomness.

With this knowledge in mind an adversary can follow a common attack pattern: build lookup tables only for the most common TAC numbers. Since a relatively small number of mobile devices dominates the market, the attacker only needs to build the lookup tables for the most popular TAC numbers.

Attack Demonstration

To demonstrate the practicality of this attack I built 105 lookup tables for 105 different iPhone TACs, using the SHA-1 hash function. Each table took up 55 megabytes of space, yielding 5.6 gigabytes in total (which is larger than the theoretical minimum since I stored data as ASCII). On an 8-core 2.26 GHz machine it took my simple Python script about six and a half minutes to build the iPhone lookup tables. With these tables built I was able to instantly reverse the IMEI hashes for all the iPhones in our office.

Recommendations

We recommend that mobile apps refrain from sending hashes of IMEIs over the web. It is easy for attackers to generate IMEI numbers when given the hash values of IMEIs—even for cryptographically secure hash functions. Salting the hash function (adding random bits to the input) helps to obscure the IMEIs further. However, if the adversary knows the salt value and the model of the phone (or can guesses well), it is easy to rebuild custom lookup tables.

In order to prevent apps from having the ability to compare notes on their users, apps need to refrain from basing their user IDs on device IDs altogether. Even if IMEIs were not vulnerable to lookup tables, two different app publishers could de-anonymize users by hashing the IMEI in the same way.

Last but not least, we recommend attending our Black Hat talk on August 4, where we will present other interesting findings from our dynamic analysis of 10,000 Android apps. ;-)