[Let’s welcome new CITP blogger Pete Zimmerman, a first-year graduate student in the computer security group at Princeton. — Arvind Narayanan]
Following the revelations of wide-scale surveillance by US intelligence agencies and their allies, a myriad of services offering end-to-end encrypted communications have cropped up to take advantage of the increasing demand for privacy from surveillance. When coupled with anonymity, end-to-end encryption can prevent a central service provider from obtaining any information about its users or their communications. However, maintaining anonymity is difficult while simultaneously offering a straightforward way for users to find each other.
Enter Wickr. This startup offers a simple app featuring “military grade encryption” of text, photo, video, and voice messages as well as anonymous registration for its users. Wickr claims that it cannot identify who has registered with the service or which of its users are communicating with each other. During registration, users enter their email address and/or phone number (non-Wickr IDs). The app utilizes a cryptographic hash function (SHA-256 in this case) to obtain “anonymous” Wickr IDs from the non-Wickr IDs. Wickr IDs are then stored server-side and used for discovery. When your friends want to find you, they enter your phone number or email address, which is then put through the same hash function, resulting in the same output (Wickr ID). Wickr looks this up in its database to determine if you’ve registered with the service to facilitate message exchange. This process simplifies the discovery of other users, supposedly without Wickr having the ability to identify the users of the anonymous service.
The problem here is that while it’s not always possible to determine the input to a hash function given the output, we can leverage the fact that the same input always yields the same output. If the number of possible inputs is small, we can simply try all of them. Unfortunately, this is a recurring theme in a variety of applications as a result of misunderstanding cryptography — specifically, the fact that hash functions are not one-way if the input space is small. A great explanation on the use of cryptographic hash functions in attempts to anonymize data can be found here.
With this in mind, let’s consider how difficult it is for Wickr to uncover who its users are (or how difficult it is for somebody else who has obtained the list of Wickr IDs by a court order or compromising Wickr’s servers). Since there are less than 10^10 possible phone numbers in North America, a consumer-grade desktop with a decently powered GPU can compute the hash for all of them in a matter of seconds[1, 1a]. Precomputing and indexing the hashes for all possible phone numbers ahead of time allows the search to complete almost instantaneously (using up to 320 GB of storage, though this could be significantly compressed via a “time-memory trade off”). Similarly, one could precompute the hashes of email addresses from a list obtained through a variety of sources (legitimate or otherwise) and conduct a dictionary attack.
These attacks are similar to password cracking, suggesting Wickr could potentially mitigate this problem through the use of two defensive techniques: hash strengthening and salting. The former involves computing an iterated SHA-256 with N iterations to compute a Wickr ID from sensitive information. Unfortunately the numbers don’t appear to work here. If N=10^5, this isn’t enough to really make brute-force infeasible. It would take days on a single machine instead of seconds, but this still can be done in parallel quite cheaply and quickly (e.g., using an Amazon GPU instance runs in the ballpark of $0.7 per hour, per instance). Yet this would probably make Wickr’s contact discovery feature unacceptably slow to use on mobile devices. Given that an average smartphone can compute around 10^6 SHA-256 hashes per second[2], computing the Wickr ID in this manner for each entry in a user’s contact list would induce a noticeable delay while additionally draining the battery.
Salting, on the other hand, does not work for contact discovery at all. If Wickr were to add a random salt to each non-Wickr ID before hashing, it’s not possible to store the salt in a way that can be looked up given the ID. Salting works for password hashing because there is a separate username and password; the salt can be looked up given the username and then used for computing the password hash.
Wickr has definitively not solved the hard problem of anonymous registration or contact discovery — critical components which, if made cumbersome, could potentially hinder user adoption (and sink a startup). Many other communication tools punt on this problem as well, resorting to painful methods of out-of-band communication and stunting growth. However, including this feature through the misguided use of one-way hashes and misleading marketing claims only lulls Wickr users into a false sense of security.
[1] The North American Numbering Plan contains invalid and reserved prefixes. This would reduce the search space by several billion; thus, my estimate provides an upper bound on the time to complete the attack.
[1a] oclHashcat is a popular library for GPU-based password brute-forcing which provides our benchmarks on SHA-256 computation speed using a graphics card.
[2] https://en.bitcoin.it/wiki/Mining_hardware_comparison#Other
