[tor-dev] The Onion Name System (OnioNS)

[Christian Grothoff]

On 05/19/2015 07:11 PM, OnioNS Dev wrote:
> On 05/19/2015 03:20 AM, tor-dev-request at lists.torproject.org wrote:
> 
>> I'm not sure how your proposal significantly improves on NameCoin,
>> except that it is specialized to Tor (and thus doesn't attempt to
>> be as compatible with DNS as Namecoin): for security, you still
>> rely on a PoW-supported consensus, so an adversary with sufficient
>> computational power can register important names first (who gets
>> facebook.tor first?). Given that you probably don't want to double
>> the electicity bill of 'normal' users when they want to register
>> names, my prediction is that if this is adopted, trolls (and name
>> squatters) will have a field day registering interesting names.
> My scheme is better than Namecoin in several key ways: 1) No miners.
> I'm relying on the existing trust of the Tor network and purposely
> did not create a new network. 2) Minimal networking costs. Namecoin
> typically requires users to hold the blockchain, and has very little
> client-side security when users rely on name servers to hold it for
> them. I require clients to check a set of signatures from Tor
> routers. Most of the attack vectors for OnioNS also results in a
> compromise of Tor, which makes the whole thing moot. Hence it makes
> sense to rely on Tor.

Yes and no.  Sure, if you currently compromise Tor, you may void
anonymity.  But with your system, authenticity then also breaks.
With ".onion", even if I controlled 99% of the Tor routers but
not the one hosting the hidden service, I could not break authenticity.

Furthermore, there is the question of time.  As .tor-names are pinned
(if you have a name, you get to keep it 'forever', right?), an adversary
may invest into the required resources to make the attack succeed
*briefly* (i.e. get the required majority), then re-assign names to
himself. New honest nodes would pick up this hacked consensus, and
thus it would persist even after the adversary lost the majority
required to establish it.  This is relevant, as an attack against
Tor user's anonymity only impacts the users as long as the attack
itself lasts, so the gains between the two attacks (temporary vs.
"forever") change the economic incentives for performing them.

So I'm not sure it is such an "obvious" choice to just rely on an
honest majority of (long-term/etc.) Tor routers.  I'm not saying
it is bad; however, simply saying that if those routers are compromised
all is lost anyway is not quite correct.

> The PoW is only for registration, no one else does it. Yes, it is
> first-come-first-serve, but so is Namecoin. On the Internet DNS,
> someone with lots of money could buy up domains too (ISPs do this all
> the time).

Right, I personally find this kind of first-mover advantage where we
literally hand out perpetual ownership over words problematic, as it
further increases the disadvantage of younger people and new businesses.
But, that's more a philosophical thing, as a design choice I guess this
is still valid. ;-)

> For well-known hidden services (such as DuckDuckGo) we
> could mark those names as reserved such that only the owner of that
> hidden service could register it on OnioNS, and let all other names
> be first-come-first-serve. I'm thinking of setting the proof-of-work
> relatively high, say four hours on an i7 or so. The reliance on
> scrypt and the complex of the domain registration should restrict
> this to CPUs.

Ok, let's assume a c4.xlarge EC2 instance (which is ~i7) takes 4h to
do this (on all cores).  For one month, the price is USD 170, which
means the registration cost is 70 cents/name (for eternity, or do
I have to do this repeatedly? Don't recall if you require a fresh PoWs).
Anyway, 4h sounds pretty inconvenient to a user, but as you can see is
still nothing for a professional domain name squatter who today pays
closer to 100x that to squat for a year.  I predict most 'short' names
will be taken in no time if this is deployed.

With Namecoin, you have an inherent limit on the rate at which names
can be registered.  Now, once people start squatting tons of .tor names,
maybe even your bandwidth advantage disappears as the consensus may
become rather large.

>> I didn't see a mechanism to transition a name from one RSA
>> key/.onion address to another. Is that intentionally missing? Will
>> users loose control over their .tor names when they rotate keys?
> I only have 12 pages, there wasn't enough space for that protocol.

I see, a well-known academic curse ;-).

>> It also seems you are unconcerned about zone enumeration. Both your
>> protocol on authenticated denial-of-existence and the entire
>> consensus system suggest that it should be easy for a peer to
>> enumerate all names in the .tor zone.
> I'm considering that all OnioNS data is public. There's no way to
> hide information in the Pagechain as Mirrors need to verify it.

Well, I prefer my hidden services to be really hidden and not public. I
understand that this weakness is somewhat inherent in the design, but
you should state it explicitly.

> An
> attacker could also spin up a machine, synchronize with the network,
> and enumerate them anyway. Clients must also see the domain names in
> the leaves of the Merkle tree in order to authenticate Records or
> verify that the domain does not exist by finding two domains that
> alphabetically span it. I also can't hide the domain names in the
> Merkle trees via hashes because then I'm mapping unique names to a
> binary space that may have collisions. It's far easier to just
> consider the information public. Fortunately, there's no
> personally-identifiable information in the Pagechain, so there's no
> advantage in hiding the data.

Eh, sorry, but no.  Having the ability to give a name to a service
doesn't mean the service should be public, and even if the RSA key
is not 'personally-identifiable information', there is clearly a
security advantage in being able to operate a service that the
adversary may not even know exists.

>> Why do you limit names to 128 characters, when DNS supports 253?
> For space reasons. Longer names introduce more storage and networking
> demands. The smaller choice shouldn't make any practical difference;
> I have yet to see a domain name on the Internet with a 253-character
> second-level domain.

Careful here, I think you're confounding names and labels. DNS labels (
including "second-level domains") are limited to 63 characters (6-bit
length prefix in DNS encoding!), while DNS names (full name
label.label.label.tld) are limited to 253 characters.  So if you are
just talking about the second level domain, 128 is more than twice what
DNS allows (also incompatible, why do you double the limit?).
Furthermore, unless you have some odd reason to not use a variable-size
field, I don't quite see how this really saves you any bandwidth in
practice.  I would urge you to stick to precisely the DNS limits (even
though they are odd and awkward), just to not break compatibility for no
reason.

>> With respect to Zooko's triangle, I would point out that you define
>> it differently than GNS does (and we checked with Zooko about the
>> definition at the time). In particular, you assume that the
>> adversary has limited computational power and doesn't dominate the
>> consensus. For GNS, we assume that PoW is useless (adversary can do
>> PoW for all memorable names) and that consensus is useless
>> (adversary has majority). This is because in practice, governments
>> do have more computational power than citizens, and when it comes
>> to censorship it is important to protect minorities and their
>> opinions, not majorities. (see also
>> http://grothoff.org/christian/fps2013wachs.pdf).  Thus, you might
>> want to make it clearer in your paper that you 'square' Zooko's
>> triangle under exactly the same conditions as Namecoin: a weaker
>> adversary model / definition of 'secure'.
> I think you may misunderstand. Computational power (PoW) here has
> nothing to do with Zooko's Triangle. With Namecoin, the network is
> assumed to have more CPU power than adversaries and thus they can
> achieve all three properties.

See, that's the point: Namecoin (and your system) assume a different
adversary model than what Zooko intended to imply when he formulated his
triangle.  When Zooko said "secure", he meant "against an adversary that
does have more CPU power than all of the network combined and unlimited
identities".  When you say "secure", you talk about Namecoin's adversary
model where the adversary is in the minority (CPU and
identity/bandwidth-wise).

Thus, it is unfair for you to say that your system 'solves' Zooko's
triangle, as you simply lowered the bar.

> Here, PoW is only used to increase the
> difficulty of claiming a domain name, and I get the uniqueness
> property because I assume that Tor routers are generally honest. This
> is a safe assumption as if Tor routers weren't honest, Tor circuits
> would not provide privacy and again the whole system breaks and
> becomes moot. So, I assume that Tor routers follow the rules and
> reject duplicate domain names, therefore the network as a whole
> prevents collisions. An attacker could win here by Sybil attack by
> spinning up many new Tor routers and gaining control of the Quorum by
> placing the statistics in their favor. My analysis shows that this is
> extremely unlikely for L_Q >= 127.

Bitcoiners also maintained that a 51% attack was extremely unlikely,
just until a pool grew to ~50%. I would agree (without analysis) with
your statement that a majority-attack against Tor is 'unlikely', were it
not for the fact that succeeding once would then provide control
over names for a long time (until the next one succeeds with the same
attack).  So if this is successfully deployed and massively used, I
could see the NSA/FBI/CIA team up, buy up computing and network
resources globally for a month (or however long it takes) to take
control of _all_ established high-profile hidden service sites. At least
that's plausible enough for me.

>> So maybe Tor can plan to incorporate ".tor", ".bit" (namecoin),
>> ".onion" and ".gnu". After all, each solution has interesting
>> advantages and drawbacks. (The problem then only becomes educating
>> the user about those.)  Regardless, good luck with ".gnu" and I
>> look forward to the resulting discussions on dnsop (IETF
>> mailinglist), where you really should launch a discussion on this
>> as well.
> Yawning mentioned this. It's easy enough to create a spec that
> defines the protocol for handling other pseudo-TLDs. Currently Tor
> writes "*.tor" to a named pipe, reads "*.onion", and finishes the
> lookup. It's easy to use that protocol for any alternative DNS. It's
> outside Tor's scope to care how the *.tor -> *.onion map is
> accomplished.

Could we please make the protocol a bit more general than this?
For GNS, you also 'send' the name, but you get back an extended DNS
record set, i.e. we can return multiple records with 32-bit record types
(DNS uses 16 bits, hence 'extended').  For .tor, you could initially
still return a CNAME record pointing to the '.onion' name if you want,
but ultimately I would prefer to have a new record type "TOR-HS" that
gives you not a name but really just the key (EdDSA or RSA or whatever
-- ok, let's have TOR-HS-RSA and TOR-HS-EdDSA record types, after all,
we have 4 billion numbers).

With GNS (or Namecoin), we could then also return things like TLSA
records (bypassing X.509 CAs), or IP addresses (A/AAAA), so one could
reserve names for non-HS as well to defeat DNS censorship (I worry that
finding a Tor exit where a DNS lookup returns an honest result might be
tricky in the future).

So please don't specify mapping name-to-name. It will be more flexible
if we specify the lookup service as something that maps names to record
sets (and take a look at the GNS record set binary format (admittedly
insufficiently documented right now, so 'to look' means to read code)
--- we re-use DNS for the lowest 65536 record types, and I'll be very
happy to allocate GNS record type numbers for Tor-specific features).
Using CNAMES you could still map name-to-name, but as I said, even that
would not be my choice.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0xE29FC3CC.asc
Type: application/pgp-keys
Size: 14032 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150520/4c59ed06/attachment-0001.key>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150520/4c59ed06/attachment-0001.sig>