references on non-central authority network protocols

Sun Apr 14 20:40:42 UTC 2002

Thus spake "Scott A Crosby" <crosby at qwes.math.cmu.edu>
> Rolling off the top of my head, I think its doable. The general
> trick is to make it hard to forge packets with arbitrary
> addresses (by using authentication).

No, the trick is for a distributed algorithm to generate a non-trivial
number of unique values for a (short) fixed-length field.

> Assume each host has an public and private key pair by some
> conventional algorithm (RSA, or other). The private key is
> never disclosed.
> ...
> A variant of this could be made where just the network is
> assigned with this scheme, the host isn't. IE, hosts are assigned
> addresses of:
>
>   k_public || hostaddr

For instance, let's say IP had started with a constant 24-bit network field
(no Class A or B), or 16M possible networks.  My rough count shows we have
97 /8's usefully allocated, or 776M hosts assuming 50% efficiency.  We'd
need 6.4M /24 networks to cover this many hosts, out of a possible 16M
networks.  I dare you to find any hash that can reliably give 38% of all
possible values without a collision.  Once you've done that, perhaps you can
enhance BGP to handle 800M routes :)

> Which isn't robust against malicious hosts in the same network,
> but thats fixable with a heirarchial scheme.

The odds of k_private being disclosed grow exponentially with the number of
hosts per network.

Interesting idea though.  Perhaps someone will write an i-d on autonomous
numbering for IPv6.

S