[Cryptography] Implementations, attacks on DHTs, Mix Nets?

[Jerry Leichter]

On Aug 27, 2013, at 9:41 PM, Perry E. Metzger wrote:

> On Tue, 27 Aug 2013 21:13:59 -0400 Jerry Leichter <leichter at lrw.com>
> wrote:
>> I wonder if much of the work on secure DHT's and such is based on
>> bad assumptions.  A DHT is just a key/value mapping.  There are two
>> reasons to want to distribute such a thing:  To deal with high,
>> distributed load; and because it's too large to store on any one
>> node.
> 
> You've forgotten other reasons. One might want to avoid a single
> point of failure.
And yet DHT's have completely failed at doing this.

> One might also want to avoid having any central
> organization responsible for running a database so that it cannot be
> shut down by an adversary without shutting down thousands or millions
> of nodes.
Redundancy and validation of updates are issues separable from the implementation of the map and, in particular, from routing.  DHT's try to combine all four and, as we've seen, fail.

Just because it's possible to actually store the contents of a DHT in a single big database doesn't mean you'd actually want to do it that way.  I'm suggesting that you start with the idealization of a single, secure database, then make the modifications needed to actually attain the necessary properties in the face of high distributed QPS, random failures, and a variety of attacks.

>> I contend that the second has become a non-problem.
> 
> That is untrue.
> 
> Say that you want to distribute a database table consisting of human
> readable IDs, cryptographic keys and network endpoints for some
> reason. Say you want it to scale to hundreds of millions of users. A
> quick back of the envelope shows that no home user's little ARM based
> gateway machine is going to want to handle storing the entire database
> or handling the entire update traffic volume -- the latter alone
> might swamp someone even with quite reasonable connectivity.
Why in the world would you want to put the information for even a million users on such a server.  This would be a server that exists to provide services to at most a few 10's of people - probably fewer.  How many users will they, personally, ever contact it their collective lifetimes?  This is an ideal application for local caching of relevant information from the global database stored "somewhere else".  It might well, transparently, also contain mapping information that its own users received "out of band" and want to use - but have no reason to share globally.

> 
>> Even at the high end, what's today a fairly small, moderately
>> powered system can handle this much data with no problems.
> 
> I don't think so. Lets say you have a few hundred bytes per entry and
> a billion users. That's hundreds of gigabytes, far more than you can
> store on a thumb drive and an appreciable fraction even of today's
> hard drives. Furthermore, say that 1% of the entries update per day
> -- even at that low rate, you're going to swamp lots of people's
> internet transfer quotas.
Again, why would individuals want to store that much data?

The DHT model says that millions of Raspberry Pi's and thumb drives together implement this immense database.  But since a DHT, by design, scatters the data around the network at random, *my* thumb drive is full of information that I will never need - all the information *I* need is out there, somewhere - where, based on the research we've been discussing, I have no secure way to get at it.  Why would I buy into such a design?  Doesn't it make much more sense for me to store the information relevant to me?

It's not as if this isn't a design we have that we know works:  DNS.  Yes, DNS, even the "secure" versions, have security issues.  But then so do DHT's, so they are hardly an improvement.  And many of DNS's problems have to do with the assumption of a single hierarchy with, as a result, a small number of "extremely trusted" nodes up at the top.  That's a problem that can be attacked.

                                                        -- Jerry

> 
> Perry
> -- 
> Perry E. Metzger		perry at piermont.com