Second Priority Ideas Blog

Attack on Privacy Policy Matching

I just attended the SACMAT 2010 conference and learnt about the concept of privacy policy matching as proposed by Bertino et al. in PET 2004's "Privacy-Preserving Trust Negotiation". The basic idea is to match a P3P privacy policy against a set of preferences resulting in a score. Let me start by saying that I think the idea is cool and there probably is a real demand for such a thing. Nevertheless I think making this work in practice will be a challenge and here is why. There are tools (web sites) for price comparison for years. Now comparing prices (essentially a number) is trivial compared to comparing privacy policies. Nevertheless vendors have found numerous ways of subverting these sites tricking them into displaying a better rank than the actual costs imply, e.g. by hidden costs, special offers, etc. This is not surprising, since it is in the best interest of the vendor to charge as much as possible as well as being ranked as high as possible. Why should this be any different with privacy policies? It is in the best interest of service providers to diminish privacy as much as possible as well as it is to be ranked as high as possible by the policy matching tool. So what type of attacks are there to subvert privacy policy matching? I guess similar ones, like violations outside of P3P, complex general terms and conditions, etc. And even more interesting: what are possible countermeasures to secure the matching algorithm? This could be a nice paper and I look forward to seeing it. Unfortunately I do not have the time to work on it myself.

A New Cryptographic Assumption

Bilinear maps have been one of the weapons of choice for solving complex cryptographic problems in the recent past. They have lead to a number of algorithms with very interesting security properties, such as proxy re-encryption, searchable encryption and homomorphic encryption. Unfortunately bilinear maps can only be applied once, i.e. the designer can use them for one trick and then it's over. So there are many schemes out there that use bilinear maps for different purposes. Now, I think it would be nice to be able to combine those schemes, but there's nothing like a trilinear map.

I've been searching for alternative cryptographic assumptions that can be used in order to combine the features of two of those schemes that use bilinear maps. I haven't been all that successful, but I came across the following idea of combining RSA and bilinear maps. Let n=pq be a composite of two large primes. Then construct the bilinear maps over fields of size n. I denote h(a, b) the bilinear map (since my blogging tool has no embedded latex for \hat{e}). It should be hard to solve the following problem:

Given x^e, y^e and e, compute h(x, y)^e

Note that x^e and y^e are RSA ciphertexts. Computing h(x, y)^e is as hard as decrypting RSA, but given h(x, y)^e one can verify it like a signature, since h(x^e, y^e) = (h(x, y)^e)^e. I can construct nice things using based on the assumption that solving this problem is hard, but there is a draw-back. One can use it only with a single e for any n, since otherwise the common modulus attack on RSA makes the problem trivial. This limits most of the things I came up with and I have given up using it for now, but now I am publishing it here. Maybe somebody else can use it. If you do, please let me know.

Enforcing Honesty in Privacy-Preserving Computation

It's been some time since my recent post. The topic this time is honesty in privacy-preserving computation. Homomorphic encryption or secure multi-party computation allows a number of parties to compute a function on their joint input without revealing anything but the result. This can be very useful to implement mechanisms that would not be implementable without privacy. A typical is supply chain management where companies can combine their planning without revealing sensitive information, such as production costs or capacities. A fundamental problem is that there is no technique to force anyone to provide the honest input. No one can check the data, since it is encrypted and any revelation would contradict the idea of encrypting it in the first place. This can be detrimental, since if that participant can gain an advantage by lying, he might be inclined to lie destroying the mechanism. The ideal way to circumvent this to make the mechanism truth-inducing or provide fair benefits, but apparently this cannot always be done. So here my second priority idea: We implement the honesty check as another secure computation. Each party provides bounds on the other parties input, e.g. the production cost of my supplier may not be higher than the price I am paying and not lower than the prices its suppliers are charging him. Both pieces of information are known to parties other than the one inputting the cost. We can also use statistics. E.g. the distribution of production costs should correspond to the distribution of the average time the goods spend at that organization. Two questions remain: Does this lead to a truth inducing mechanism or at least limit the spectrum of the equilibrium ? Does this change the security requirements for the secure computation ? No one wants to implement the malicious security model.

Checking your Personal Firewall

A blog needs to be regularly update in order to find interested readers. I therefore made resolution to write an entry approximately each month. Let's see how long I can stick with it.

This idea might be already a bit outdated. At least I have seen fixes in some commercial products for this. It is also more of a possible attack and as such one should perform responsible disclosure. A personal firewall is a firewall protecting your PC, laptop, etc., but differently from regular firewalls it not only keeps evil from the Internet outside. It also checks traffic originating from your computer and is able to attribute this to specific applications. This comes in very handy for those applications that phone home to provide an enhanced user experience. The algorithm for most older personal firewalls was simple. They were a Berkeley packet filter (BPF) inspecting every incoming and outgoing packet against a list of rules. In order to determine the application sending a packet they walked the socket list in the kernel similar to "netstat -ano". The problem with this approach is simpe: some sockets your computer sends or listens on belong to other processes than the one causing the packet. Most notably the kernel performs some tasks for your processes. In former Windows 2000 times a good candidate was the DNS port (UDP 53). You could trick the kernel into sending and receiving via this port by using the gethostbyname() system call. All you need to do is to write your own DNS server and a rogue application can bypass the firewall by quering this server with names that encode the information you want to send. Using the firewall algorithm described above you would need to block all DNS traffic which blocks you from using the Internet.

This DNS attack seems to have been mostly fixed which makes me wonder if it ever has been exploited, but looking at my open ports I can still see several ports belonging to the kernel or system applications. Did they really catch every system call that causes a packet to be sent?

Managing Passwords on the Internet

I cannot believe that there is no better way to manage your accounts on the various web sites than passwords. No one can remember them. I've been bitten my malware, such that storing these passwords in Internet Explorer seems dangerous and many sites rightfully prevent it anyway. Some security experts recommend choosing variations of passwords (admittingly before the web explosion), but this is clearly a trade-off between randomness and memorizability. If you can remember it, it is probably not random enough. So I've been developing an idea that I claim combines memorizability and randomness. First choose an area that matters to you. It can be cars, music or like in my case movies. Then search for a web database that stores information about that area; in my case imdb.com. Now for each web site where you have an account find the topic in the area which you most associate with the web site. This association should be emotional and intuitive. It is well known that associative passwords are easier to remember. An example: For my bank's web site, I choose a movie about money: Boilerroom. Then go to the web database and look up a specific property of the associated item, e.g., the main actor. In the example this is Giovanni Ribisi. Choose three rules for modifying the looked up property. These rules must be the same for each password, such that you can remember them. They are used to prevent dictionary attacks, e.g., move the first three characters to the end, replace a-e with 1-5 and write r, s or t in uppercase. The resulting password is v1nniRi2iSigio. I've been able to recall passwords I haven't used for over a year and all of my passwords have been rated green by password checkers, but that's of course only one sample.

P.S. Don't think I've just told you my online banking password.