« NSI accused of front running | Main | Viral load up, IQ down »
January 9, 2008
A cheap anti-frontrunning countermeasure: digested WHOIS
The reason that front running works at all is that WHOIS leaks the name of the domain you're looking to the WHOIS service operator and in this case the operator is the adversary, thus giving them an opportunity to get ahead of you. The usual answer to this problem is to create a set of policies that treat WHOIS queries as sensitive information (see ICANN's study on front running). One could, for instance, require the WHOIS operator to treat WHOIS queries as private.
However, there's a cheap, compatible, technical hack that
substantially increases the difficulty of front running attacks
without any new policies: allow WHOIS searches on hashes of domain
names. The way this would work is that the WHOIS operator would create
a parallel tree of phony domain name registrations in WHOIS. For
instance, if I registered example.org, then they would
also create an entry for SHA-1(example.org)=20116dfd6774a9e7b32eddfea3f6cb094e38fc3f.org
(we might need to register a new TLD to make this work and guarantee no
collisions) and populate
it with the record for example.org. Then, I could
locally compute the hash for each domain name I wanted to check on
and easily verify its existence or nonexistence.
Other properties:
- The WHOIS server doesn't get the name being searched for, just the hash. It's in principle possible to iterate through all possible names to see what hashes match, but this isn't practical for any at all unusual name, and of course most obvious names have already been registered.
- The WHOIS protocol doesn't need to change: this looks like a valid domain name.
- It's easy to generate the records on the server side: just run some script over your WHOIS database.
- It's easy to enhance your WHOIS client to do the hash first, but even if you don't, command line hash programs are easy to get.
- Note that there is some chance of name collisions
You still might need ICANN or someone like them to force the operators to do this, since it's not clearly in their interest. On the other hand, direct cost to them is so low that it's hard to really object to on difficulty grounds.
Technical Note 1: This problem is related to private information retrieval but is dramatically easier because we don't care about the server knowing what record we fetched if it exists, only if it doesn't exist. Actually, we only care if the record exists. We don't need the record itself, which makes the problem yet easier.
Technical Note 2: It would be nice to have a solution that didn't allow dictionary attack. The best solutions I know use Bloom filters.
- The server can send you a Bloom filter with the names he knows. This is completely resistant to dictionary attack but is still of linear size in the number of inserted domain names per key. And, of course, there are false positive issues.
- The client can request the values of specific bits in a server-side Bloom filter. By asking for a superset of the bits you want you can get some dictionary attack resistance. This has much lower space requirements, but still leaks some information to the attacker—I haven't done the math on how much, but it clearly scales to some extent with the number of bits requested, with the limit being all of them.
Note that the hash solution isn't technically constant size in the number of registered names either—the required hash size for any given false negative probability depends on the number of registered names. However, since 160 bits is so small people just think of this as constant size.
Posted by ekr at January 9, 2008 8:34 AM | Filed under: COMSEC, DNS
Comments
Then again, we would still be vulnerable to collusion between whois servers and registrars. It even looks like it would make front-running more orderly, since the registrars could sell discounted 'dibs' on a hash domain that would translate to the guarantee to front-run any actual registration that resolves to that hash, once the user is foolish enough to disclose it to the registrar :)
Or do I misunderstand the threat model?
Posted by: Thomas Themel at January 9, 2008 12:16 PM
Well, it's certainly true that the registrar can always frontrun you, but i don't see how the whois server is relevant in the scenario you outline--of course, as Cullen Jennings pointed out to me in another context, you could always allow hashed registrations, thus removing that problem as well.
Posted by: EKR at January 9, 2008 12:37 PM
It's appealing to try to find technical implementations that can avoid the swamp of "consensus policy" at ICANN, but I am afraid this solution doesn't do that. Unless all registrars were required to do use "hashed" Whois, it wouldn't really work that well, and the only way to achieve that would be to use ICANN's contractual leverage over registrars. While some registrars might voluntarily adopt it as a competitive measure to achiive customer goodwill, such adoption would be no different from a unilateral (and self-enforced) pledge not to engage in front-running. So, nice idea, and maybe something that should be implemented, but it seems to me there is no way to get there except through the policy route.
Posted by: Milton Mueller at January 15, 2008 11:46 AM
Well, it's different from self-enforced in at least one way: the only way the registrar can cheat is by lying about a name not existing. It still can't front run.
Posted by: EKR at January 15, 2008 11:55 AM
as private opulence is originally derived,is frequently powerful enough to enabled to carry on business for more than two years. When it was obliged to
Posted by: James at January 23, 2008 3:13 AM