Anonymous Gravatar Problem

Gravatar is a service that serves avatars for users based on md5(email_address). The hash is embedded on websites, so it's public.

One of the problems with this solution is that it's easy to track users across websites, since the same e-mail will have the same hash.

I'm wondering if there's a cryptographic solution to that problem? Requirements:

A. It must not be practical to correlate users across websites by the avatar URL alone (hash/identifier for the same e-mail must be different on different sites)

B. The server, given a hash/identifier, can decode it and look user up in a large database in a better-than-linear time.

C. No clock synchronization, no challenge-response protocol (it must be possible to generate identifiers offline). Ideally it shouldn't require pre-shared keys for every website.

The only solution that comes to my mind is something like salt + hash(email_address + salt), which would meet requirements A and C, but not B: salted hash would force the server to re-hash e-mails of all users to find the relevant one.

• For B, why not sort the hashes and do a binary search? Also you could use domain instead of salt. – mikeazo Feb 13 '15 at 23:41
• @mikeazo Yes, domain is better than random salt. It's still rather expensive though: you need to keep users * domains hashes and any new domain is very costly to add. – Kornel Feb 14 '15 at 0:14
• Could you confirm that in the context of the question, email is a long-term, short email address (e.g. roberto@giaml.com, typo intentional); not a short-term, long email identifier aka Message-ID like 026b01d04aa6$9c2d37a0$d487a6e0$@giaml.com – fgrieu Feb 17 '15 at 13:05 • @fgrieu The idea behind gravatar is associating an image with an email address. So it needs long term email addresses to function properly. A couple of years ago I recovered about 20% of email addresses on stackoverflow by guessing. Others have achieved closer to 50% using a GPU hasher, but on a different dataset. – CodesInChaos Feb 17 '15 at 14:07 2 Answers Encrypt the hash using the public key of the avatar server with ECC. This has a space overhead of 32 bytes (43 Base64 characters). A modern CPU should be able to decrypt about 10000 messages per second per core. If a website uses a fixed key for all the avatars both sides can cache the shared key, so they don't have to pay the cost of the key exchange all the time. While this solves the "everybody can do an offline search to guess the email matching a hash" problem gravatar suffers from, it doesn't solve all its privacy problems. In particular the avatar service can track users, and the picture data itself allows correlation across sites, even if the hash differs. My previous answer was wrong because I misunderstood the exact model Gravatar worked under. This issue can be solved through public key crypto, for example Curve25519. Your gravatar service would have a public key available. Then, when a site wants to serve the gravatar of an user Alice with email alice@test.com they will generate the an URL containing$M$and$T$in some internet-friendly encoding (base64 for example): $$M \leftarrow AES256(SHA2(\text{"alice@test.com"}), Curve25519(K, t))$$ So the server can retrieve the userid$SHA2(\text{"alice@test.com"})$from$M$and$T$like such: $$SHA2(\text{"alice@test.com"}) \leftarrow AES256^{-1}(M, Curve25519(T, k))$$ Where$T, t$is an ephemeral keypair,$K, k$is the keypair of the gravatar service,$AES256(a, b)$is a single block encryption of$a$under key$b$,$AES256^{-1}$is decryption, and$Curve25519(C, d)$is a Curve25519 key exchange with public key$C$and private key$d\$.

• This answer might benefit from a bit more explanation. Where do the ephemeral keypairs come from? (how are they generated, and who knows them?), how do they come to be known to both Gravatar and the site?, and how does this differ from CodesInChaos's previous answer? – D.W. Feb 20 '15 at 5:09
• The ephemeral key is generated by the site that wants to embed a gravatar. They may choose to cache it for future use, or generate a new one for every gravatar. They shouldn't leak the private key however, as this will expose the hash of the user's email address. The public key is included in the gravatar URL, as said in the answer, so it's public knowledge. The difference between my answer and CodeInChaos's is that I explicitly give a scheme for the URL, display the primitives used and use ECDH rather than ECC. – orlp Feb 21 '15 at 5:57
• Thank you for the comments. That helps me understand this much better. I encourage you to edit the question to include this extra information -- comments are transitory and can disappear. – D.W. Feb 21 '15 at 6:01