[Freedombox-discuss] assigned *names* (was Re: assigned numbers without ICANN)
Thomas Lord
lord at emf.net
Fri Apr 29 02:12:56 UTC 2011
This one describes the trivial extensions needed
to also have a distributed and decentralized
way of managing assigned hostnames that are *almost*
as human-friendly as DNS hostnames, sorta.
I'll get into a plan for routing later but this
is a good point to pause.
-t
Allocating Assigned Host Names
in a Distributed and Decentralized Way
[ This document builds on what was described in the earlier in
"Allocating Assigned Routing Numbers in a Distributed and
Decentralized Way. ]
The mechanism used to allocate routing IDs can, with some
slight additions, be used to allocate human-friendly
hostnames.
OVERLAY NETWORK HOSTNAMES
Routing IDs have many desirable properties but they are not
terribly useful for human communication: they are just
abstract numbers.
Overlay hostnames are symbolic, human friendly names which
can be assigned to routing IDs, much as DNS hostnames can be
assigned to IP addresses.
An example overlay hostname:
thomas-lord%0a9k31
Notice that *unlike* DNS hostnames, overlay network hostnames
have an ugly base 36 number tacked on the end, following a
percent sign:
thomas-lord%0a9k31
||||||||
not actually user friendly!
The structure of this ugly appendage is a timestamp and
a hash:
thomas-lord%0a9k31
|
ugly percent sign
thomas-lord%0a9k31
|||
ugly timestamp (approximately 14 Apr 2011)
thomas-lord%0a9k31
|||
ugly small hash value in the range [0..36^3)
For every human-friendly part of an overlay host name
(e.g. "thomas-lord"), and every timestamp (e.g. "0a9"),
there are 36^3 overlay host names "created" (there are
36^3 possible "small hash" values).
36^3 = 46,656 chances to register a "thomas-lord%......"
hostname every 7 hours or so.
OBTAINING AN OVERLAY NETWORK HOSTNAME
Overlay hostnames are obtained by a variation on the process
used to obtain routing IDs. A name is requested by adding a
"hostname" field to a deed claim:
Timestamp: 0a9
Hostname: thomas-lord <--- request a host name
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key goes here ]
When the routing address claim is fully written,
it has a hash:
Timestamp: 0a9
Hostname: thomas-lord
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key ]
[ self signature of the above ]
Hash of above: Lljk28nsdf8867y234hnaoyuyptnn
The routing address is the timestamp plus the first 7
characters of the hash:
0a9Lljk28n
The overlay host name is formed from the same timestamp and
the next three characters of the hash:
thomas-lord%0a9sdf
When the user seals the routing address request, information
about the requested hostname is included. The sealed
message includes the exact host name requested, if any:
[encrypted routing ID claim]
ID: 0a9Lljk28n
Hostname: thomas-lord%0a9sdf
Claim ticket: 0146458n00 0a99ke8ij2
[ claim key signature ]
[ seal key signature ]
Sealed requests can share the exact same hostname field even
though they differ in ID. Unless all but one submitter of
conflicting requests agrees to abandon their name claim or
have cryptographically invalid claims, all of those requests
for that hostname must be rejected.
Therefore, it is encumbant upon each federation of admins to
combat "overlay hostname spam": a denial of service attack
conducted by filing (ultimately bogus/obnoxious) claims for
all variations of a given name (e.g., "thomas-lord%") in a
given time slot ("thomas-lord%0a9"). There are only 46,656
claims available for that prefix and the prefix has an hours
long window of availablility with each tick of the timestamp
clock. It is technically easy to conjure up, within the
allotted 7 or so hours, entries for all 46,656 variations on
the name. That's enough to prevent *anyone* from getting the
name during that time slot, if you are determined. One can
imagine "Coca-Cola Corp." dilligently registering all
variations on their name every seven hours, swamping admins
with a bunch of crap data and pointless work.
The routing ID protocols (with additions for hostnames) do not
attempt to prevent such an attack directly. Rather, if and
when such attacks occur, they are plain to see in the public
logs that define the federation -- and it is up to the admins
of the federation to fix the problem. That is why federations
have to form their own rules and fight such spam.
MAPPING OVERLAY HOSTNAMES TO ROUTING IDS
Routing issues are described in a separate document.
The short story is that a set of "renewal"-like operations for
both the hostname and the ID, entered into the admin logs,
changes the hostname to ID mapping.
-t
On Thu, 2011-04-28 at 19:08 -0700, Thomas Lord wrote:
> Allocating Assigned Routing Numbers
> in a Distributed and Decentralized Way
>
>
> NEED FOR AN OVERLAY NETWORK
>
> Programs for Freedomboxes can not assume that each box has a
> stable IP address. Boxes are most often likely to lack both a
> fixed IP and a DNS hostname. Many boxes are also likely to be
> connected behind highly restrictive firewalls.
>
> Nevertheless, using some kind of "overlay network", we wish to
> establish point-to-point communication between freedomboxes.
>
>
> ROUTING ADDRESSES FOR THE OVERLAY NETWORK
>
> This document is about how to allocate IP-like addresses for
> routing in the overlay network, without needing an ICANN-style
> central authority.
>
> A routing address is similar to an IP address. It...
>
>
> * is a logical name for a network node
>
> * is globally unique
>
> * has a specific owner
>
> * is transferable to a new owner (and new network node)
>
> * can be comfortably written on a small slip of paper
>
> * can be memorized, if need be
>
> * is reasonably secure (hard to forge or steal)
>
> * is the address used by (overlay) network routing
>
>
> That's like an IP address but there are also differences:
>
>
> * A routing address looks different. A typical routing address:
>
> 0a9jj39f7a
>
> * Routing addresses are allocated in a distributed and
> decentralized process - there is no central authority like
> ICANN.
>
> * Routing addresses don't break down into nets and subnets
> like IP addresses. A routing address has two parts:
>
>
> 0a9 jj39f7a
> ^^^ -------
> | |
> | timeslot id
> |
> timestamp (approximate time of creation)
>
> (What those parts mean is explained later.)
>
>
>
> ASSUMPTIONS
>
> This document describes how routing addresses come to be
> assigned, transfered, etc. The design includes some
> assumptions:
>
> * "Users" control their own freedomboxes.
>
> * Many boxes sit behind an ISP firewall, have no assigned host
> name, and have no fixed IP address.
>
> * Some users are "admins"
>
> * Admins have servers that aren't behind an overly restrictive
> firewall. They normally have at least an assigned hostname
> and ideally a fixed IP address.
>
> * Admins have more technical knowledge than is required of
> non-admin users. For example, admins can cooperate with one
> another to maintain a federated cryptographic "web of
> trust". Not all users have to be adept at such things.
>
> * Admins help other users to connect to the freedombox overlay
> network (over the Internet). Admin servers are hubs for
> tunneling and for routing to Freedombox users that sit
> behind firewalls on the net.
>
> * There is no central "admin authority". Admins compete.
> Admins do not need permission to become admins, but
> admins who cooperate and federate with other admins
> make both sides more effective and valuable. In the
> admin business, a good and well earned reputation means
> a lot.
>
> * Each user uses the services of one or more admins who that
> user trusts. This trust is mutually revokable. Most
> non-techie freedombox users will need to "sign on" with one
> or more admins to get the full benefit of the box.
>
> * Trust between user and admin is made manifest by an exchange
> of keys. The admin and the user each create new key pairs
> and exchange public keys. Either can revoke trust in the
> other by simply disregarding their own keys and their
> counter-party's public key.
>
> * All nodes on the overlay network can guess or compute the
> current time relative to GMT to an accuracy of within 12
> hours.
>
> In the system described here, if a user wants a new routing
> address, he sends a message to his admins. This document
> explains the routing address allocation protocol.
>
>
> THE ANATOMY OF A ROUTING ID
>
> All of the routing IDs we'll talk about here are written
> as 10 character numbers in base 36 (more than 51 and less
> than 52 bits).
>
> The system is extensible and longer and differently structured
> routing IDs are possible. Extensions are not discussed here.
>
> This:
>
> 0a9jj39f7a
>
> is a sample routing ID. It breaks down into three parts:
>
> 0a9jj39f7a
> |
> the year offset
>
>
> 0a9jj39f7a
> ||
> the time unit offset
>
>
> 0a9jj39f7a
> |||||||
> the time-slot ID
>
> Every routing ID is "created" (conceptually speaking) at a
> specific time. The time of its creation is recorded in the
> year offset and time unit offset of the routing ID.
>
>
> 0a9jj39f7a
> |
> the year offset relative to 2011
>
> 2011 + 0 base 36 = 2011
>
> This ID was created in 2011.
>
>
> Next is the time unit. The year is divided up into
> time units. (The last time unit within a year is shorter
> than the others. Some years are shorter than others.)
>
> 0a9jj39f7a
> ||
> the time unit offset
>
> ((a9 base 36) / (zz base 36)) * 8784 hours
>
> ~= 2503 hours (a bit more than 104 days)
>
> This ID was created on the 104th day of the year.
>
> So the timestamp:
>
> 0a9 ~= 14 April 2011 07:00 (GMT)
>
> The timestamp clock advances slightly faster than once
> per 7 hours.
>
> The final 7 digits are the time-slot ID:
>
> 0a9jj39f7a
> |||||||
> the time-slot ID
>
> In concept, when the timestamp clock advances, all routing ids
> with that timestamp and ANY time-slot ID are "created". They
> weren't available for allocation before that but then they
> are. IDs of a certain tick of the timestamp clock can only be
> allocated within the next to ticks of that clock. A routing
> ID that hasn't been claimed in 14 hours (within a 12 hour
> measure) won't ever be claimed.
>
> Every seven hours roughly, the number of routing IDs "created"
> is:
>
> 36^7 = 78,364,164,096 ~= 2^36.2
>
>
> DEEDS FOR ROUTING IDS
>
> For every routing ID that is owned by someone,
> there is a cryptographic document called the "deed" for
> that routing ID.
>
> Users create brand new deeds when they (successfully) allocate
> a new routing ID. Deeds are periodically updated for the
> purposes of renewal, transfer, cancelation and some forms of
> alteration.
>
> Valid deeds are "recorded" in a decentralized way. As many
> admins as possible keep complete or partial records of all
> currently valid deeds (and, optionally, a history of those
> records).
>
> Deeds begin life as a simple email-like text file.
>
> Routing ID Claim
>
> Timestamp: 0a9
> Keyword: freedombox
> Owner Name: Anonymous
> Contact Info: n/a
> Claim ticket: 0146458n00 0a99ke8ij2
> Notes: scratch ID for testing
>
> [ public key goes here ]
>
>
> STEP 1: OBTAINING A TICKET
>
> To claim a name, a user asks an admin for a claim ticket.
> In return, the admin provides something like this:
>
> Claim ticket: 0146458n00 0a99ke8ij2
>
> The first part of the claim ticket ("0146458n00") is itself a
> routing address. It is a routing address belonging to the
> admin. The second part of the claim ticket is a timestamped
> random number (timestamp "0a9" in this case, random number
> "99ke8ij2").
>
> This ticket gives the user a limited time ability to claim
> some name in the indicated time slot ("0a9" in this case).
>
>
> STEP 2: WRITING A CLAIM
>
> This explains how to write a claim for a routing
> address. Merely writing the claim doesn't
> secure the ID -- this is just the first "paperwork"
> step.
>
> The user, given the claim ticket, fills out a deed,
> as in the earlier example.
>
> Routing ID Claim
>
> Timestamp: 0a9
> Keyword: freedombox
> Owner Name: Anonymous
> Contact Info: n/a
> Claim ticket: 0146458n00 0a99ke8ij2
> Notes: scratch ID for testing
>
> [ public key goes here ]
>
>
> The user then signs the document, using the
> corresponding private key:
>
> Routing ID Claim
>
> Timestamp: 0a9
> Keyword: freedombox
> Owner Name: Anonymous
> Contact Info: n/a
> Claim ticket: 0146458n00 0a99ke8ij2
> Notes: scratch ID for testing
>
> [ public key ]
> ------------------
> [ self signature of above ]
>
>
> The user performs a cryptographic hash on the
> document (so far), and appends that:
>
>
> Routing ID Claim
>
> Timestamp: 0a9
> Keyword: freedombox
> Owner Name: Anonymous
> Contact Info: n/a
> Claim ticket: 0146458n00 0a99ke8ij2
> Notes: scratch ID for testing
>
> [ public key ]
> ------------------
> [ self signature of the above ]
> [ hash of the above in base 36 ]
>
> The first seven characters of the hash are the time-slot ID of
> the claimed routing ID. For example, if the hash is:
>
>
> Lljk28nsdf8867y234hnaoyuyptnn
>
> the first seven characters:
>
> Lljk28n
>
> are combined with the timestamp:
>
> 0a9
>
> to create a routing ID:
>
> 0a9Lljk28n
>
>
> SEALING A CLAIM
>
> To "seal" a claim is to encrypt it temporarily, later
> publishing the encryption key as a proof of work.
>
> To seal a deed, a user generates a new key pair. Call this
> the "seal keys".
>
> A deed, which initially looks something like this:
>
>
> Routing ID Claim
>
> Timestamp: 0a9
> Keyword: freedombox
> Owner Name: Anonymous
> Contact Info: n/a
> Claim ticket: 0146458n00 0a99ke8ij2
> Notes: scratch ID for testing
> [ public key ]
> [ self signature of the above ]
> Hash of above: Lljk28nsdf8867y234hnaoyuyptnn
>
>
> is encrypted for the public seal key:
>
>
> [encrypted routing ID claim]
>
>
> To that the user appends the claimed ID and the
> public seal key and claim ticket:
>
>
> [encrypted routing ID claim]
> [public seal key]
> ID: 0a9Lljk28n
> Claim ticket: 0146458n00 0a99ke8ij2
>
> Then signs it for the public key in the claim itself
> and finally for the seal key:
>
> [encrypted routing ID claim]
> ID: 0a9Lljk28n
> Claim ticket: 0146458n00 0a99ke8ij2
> [ claim key signature ]
> [ seal key signature ]
>
>
> STEP 3: SUBMITTING A CLAIM (the short form)
>
>
> The user transmits the sealed claim to one or more of his
> trusted admins.
>
> I'll describe the details of what the admins do among
> themselves later. For now, just assume that:
>
> Within about 48 hours, those admins send a reply either
> denying the claim, or giving tentative acceptance. A denial
> might say:
>
>
> Sorry, your request to claim
>
> 0a9Lljk28n
>
> didn't work out. The reason is [....]
>
> A claim might be rejected because it isn't timely (a timestamp
> too far in the past or future).
>
> A claim might be rejected for having an invalid claim ticket.
>
> A claim might be rejected if the admins are having trouble
> processing claims.
>
> A claim might be rejected if something goes wrong and,
> mysteriously, there are millions of attempts to register the
> exact some ID, all at once.
>
> Of course, a claim must be rejected if it is cryptographically
> invalid (or unvalidated for too long).
>
> A tentative acceptance, on the other hand, would say
> something like:
>
> Your tentative claim for 0a9Lljk28n
> has been registered. Please complete
> your claim within 12 hours.
>
> or:
>
> Your tentative claim for 0a9Lljk28n
> has been registered but there is a problem.
>
> 5 competing claims for the same ID have
> also been registered.
>
> If you would like to try to complete your claim, please
> respond within 12 hours. If two or more valid claims
> are registered, none of them is deemed valid.
>
>
> STEP 4: COMPLETING A CLAIM
>
> To complete a tentative claim, a user (the user's software)
> sends back to the admin (and anyone else) the PRIVATE seal
> key, signed with the public claim key.
>
> Using that key, any admin (or other user) who has a copy of
> the sealed claim:
>
>
> [encrypted routing ID claim]
> ID: 0a9Lljk28n
> Claim ticket: 0146458n00 0a99ke8ij2
> [ claim key signature ]
> [ seal key signature ]
>
> can now decrypt the encrypted part:
>
>
> Timestamp: 0a9
> Keyword: freedombox
> Owner Name: Anonymous
> Contact Info: n/a
> Claim ticket: 0146458n00 0a99ke8ij2
> Notes: scratch ID for testing
>
> [ public key ]
> ------------------
> [ self signature of the above ]
> [ hash of the above in base 36 ]
> ID: 0a9Lljk28n
> Claim ticket: 0146458n00 0a99ke8ij2
> [ claim key signature of sealed form ]
> [ seal key signature ]
>
>
> and can verify that the final lines (from "hash of the above"
> onwards) matches the preceeding material.
>
> If only one user successfully completes a claim, the domain is
> his. If none more more than one successfully complete a claim
> for the same ID, none of those claims succeed.
>
>
>
> RENEWALS
>
> Deeds don't remain valid forever: they must be renewed
> periodically.
>
> Deeds are renewed by displaying knowledge of their current
> claim key, and providing a (presumably new) replacement
> claim key.
>
>
> To renew a claim:
>
> First, a new claim ticket is obtained from a trusted admin:
>
> Claim ticket: 0146458n00 0b69e8ix83
>
> Then, a user generates a key pair and appends the new key and
> the new claim ticket:
>
>
> [deed needing renewal]
> Claim key: [new public key]
> Claim ticket: 0146458n00 0b69e8ix83
>
> and then signs it using the new and previous claim key:
>
>
> [deed needing renewal]
> Claim key: [new public key]
> Claim ticket: 0146458n00 0b69e8ix83
> [ signature using new key ]
> [ signature using old key ]
>
>
> This is sent to admin or admins and the federation of
> admins either recognizes the renewal or sends up
> red flags (for admins to sort out) about why renewal
> should be denied.
>
>
> TRANSFERS
>
> The transfer of a routing ID uses the same protocol as a
> renewal. The new public key and the new key signature
> are provided by the party acquiring the routing ID. The
> final old key signature is provided by the party relinquishing
> the routing ID.
>
>
> BACKING UP: ADMINS DO WHAT NOW?
>
> In the above I explained claim, renewal and transfer
> transactions in overview but left out the hard part: What
> exactly do admins do to make that magic happen? The
> remaining sections explain that.
>
>
> THE ADMIN PUBLIC LOGS
>
> Admins within a federation maintain a collective set of "news
> feeds" which are publicly broadcast (in any mode that is
> convenient). Each admin (identified by his own routing ID)
> publishes a log of administrative actions taken at that admin
> node.
>
> For example, when a user submits a claim:
>
> [encrypted routing ID claim]
> ID: 0a9Lljk28n
> Claim ticket: 0146458n00 0a99ke8ij2
> [ claim key signature ]
> [ seal key signature ]
>
> the admin can append a (conventional) timestamp and his own
> signature:
>
>
> [encrypted routing ID claim]
> ID: 0a9Lljk28n
> Claim ticket: 0146458n00 0a99ke8ij2
> [ claim key signature ]
> [ seal key signature ]
> Admin posted: <timestamp>
> Claim ticket: 0146458n00 0a99ke8ij2
> [ admin public key ]
> [ admin signature ]
>
> and post that to his public log feeds.
>
> A "federation of admins" is a group of admins who have a means
> by which to agree among themselves (and convince others) just
> what, "officially", a given admin's log feed contained at a
> particular tick of the routing ID timestamp clock. The
> timestamp clock ticks almost once in 7 hours and, after every
> few ticks, there is widespread and cryptographically
> documented consensus within the federation about the contents
> of the logs those few ticks before.
>
>
>
> RECONCILING (Part 1)
>
> After a user submits a sealed claim to one or more admins, it
> gets broadcast as part of the admin logs.
>
> Once the official logs of that period are fixed, the outcome
> of claim submissions is deterministic. If a user's claimed ID
> is unique among claims, then tentatively accept it. If there
> were suprising competing claims, tenatively accept but with a
> duplicate request warning. Otherwise, reject the claim.
> Anyone who can see a verifiable copy of the logs can be
> confident in the status of the user's claim.
>
>
> RECONCILING (Part 2)
>
> A tenatively accepted user (with or without duplicate request
> warnings) replies by revealing the private seal key. This is
> forward by the admin(s) to the admin logs of the federation.
>
> After another "settling out period" to reach consensus on the
> new contents of the logs, the validity of the private seal key
> and of the entire claim can be tested by anyone who cares to
> review the logs.
>
> Admins who agree that a successful claim is valid attest, sign
> and post such notice to their logs.
>
>
> RENEWALS AND TRANSFERS
>
> Happen similarly to initial claim reconciliations.
>
>
> ROUTING TO ROUTING IDs
>
> How exactly routing IDs are used in overlay network routing is
> left for later. This is just about the hard-enough-on-its-own
> problem of how to allocate from and manage the namespace of
> routing ids.
>
>
>
> -t
>
>
>
More information about the Freedombox-discuss
mailing list