Is it possible to anonymize web traffic so that the IP Address cannot be determined while still being able to determine distinct IPs? I'd like to find a way to anonymize IP addresses in web logs to ensure user privacy given the following requirements:


If given an IP address, there is no way to look up which requests came from the IP address.
Given the set of requests, it can be determined which requests came from the same IP address.


This way no one (including an attacker) can determine the original IP addresses from the log.  An attacker (anyone with access to the log) would be able to determine which IPs are distinct, though.

I'm envisioning something like the this.  Each request is sent through a function that creates a unique identifier for each IP address (notice that request 1 and 4 are from the same IP address, but result in different hashes).


Request 1 - 192.168.0.1 => EIDKSJD
Request 2 - 192.168.0.2 => GIEKDJS
Request 3 - 192.168.0.3 => CIDJSDJ
Request 4 - 192.168.0.1 => DJCUDJS


But there is another function that takes two outputs and determines if they came from the same IP.


same_parent(EIDKSJD, GIEKDJS) returns false
same_parent(EIDKSJD, DJCUDJS) returns true


This method has it's downsides, specifically that searching for duplicates is not efficient.  If there's a method that is efficient for searching and meets criteria 1 and 2 above, I would up-vote twice if I could :).
In general, against an attacker that has fully compromised your webserver, your full requirements are unsatisfiable.

The reason is that, in order to find out which requests have been made from a given IP address, the attacker can always simply fool your server into thinking it has received a request from that address, and then compare the resulting log entry to the others.  (Of course, there may be more direct ways to achieve the same result, but this is a generic attack that works against any scheme.)

Conversely, against attackers who don't have full access to your webserver, but only to the logs, there's a simple solution: store a secret key on the server (in some way that will keep it out of the attacker's hands) and tag each log entry with HMAC(key, address).  Without the key, an attacker cannot distinguish HMAC from a random function; in particular, they won't be able to tell anything useful about the HMAC tag except that each IP address corresponds to a particular tag.

However, it's generally pretty hard to ensure that attackers can't get the key (and can't otherwise fool the server into logging a fake request) even if they can somehow get access to the database.  Just storing the key in, say, a secure hardware security module isn't enough, since the generic fake request attack still applies, so basically you need to harden your entire webserver.

You'll also want to make sure that your server isn't vulnerable to IP spoofing, e.g. by making sure that your TCP sequence numbers are unpredictable, and that requests are only logged after packets have been exchanged both ways between the client and the server.  Otherwise that would provide yet another way to create fake log entries without having to directly compromise the webserver at all.