Version one, for individuals and small groups where everybody has administrative permissions:You pick a secure password. This is the only thing you need to remember, but as you both connect to the server and administrate everything with it you need to keep it secret. This password is used to create an asymmetric cryptographic key pair. This must always be the same every time (no random elements), so the password also must be VERY secure! The server has both the keys in the pair.
We use a peer to peer network (p2p, like bittorrent). The peers are random, so you connect to lots of strangers, since it's an open network.
The server does not need to be connected to the peer network 24/7, but it uploads the latest IP data there every few days (to prevent expiration) or when it changes.
The critical part: The IP adress of the computers you want to connect to are stored using DHT in the peer network, and it's signed with the private key and encrypted with the public key. You find it by searching in the DHT for a string that's unique to your key pair, probably the fingerprint of the public key. The current IP data is tagged with this string in the DHT.
The current data is always uploaded by the server every time it changes, and every time that the time stamp on the current IP data in the DHT gets too old.To connect to one of your computers, you enter your password in a program. It computes the key pair, it computes the unique string, it searches in the DHT for the IP data, checkts the timestamp on it (important!) and it decrypts it and verifies the signature.
Then you connect to the IP (there could be a list, from which you pick an IP address).
Version two, for giving public access to the computers:Changes:
Only the admin(s) has the password (as before), and the general public use the public key's fingerprint to connect instead of the password.
The public key is also uploaded into the DHT, and it is tagged with it's fingerprint. This fingerprint should be a SHA512 hash or comparable.
Both the public key and IP data is fetched from the DHT at the same time.
The IP data in the DHT is not encrypted, just signed with the private key.
Multiple IP's can be stored in the DHT, each IP can be tagged with a name. IPs can also be grouped. This allows you to easily give the public access to several different services and servers with one fingerprint, as well as letting admins managing servers with only one password to connect to them all. I would recommend using this in combination with TCPCrypt for additional security to prevent MitM attacks once you've got the correct IP. The server's public key (that the user already have) is used to authenticate the connection. This means that the user only has to know one thing (the fingerprint) to establish a secure connection. Either computer could switch IP at any time, move whenever it's he owner feels like it or the computers could even be replaced - but as long as the server admin keeps the pass secret and the user has the right fingerprint, they are both safe and can connect securely in seconds, anytime.
I think this can be very secure. I also think that the fingerprints has to be "visualized" someway when used to let the general public connect to your server. The client program should always compute a visualization that's unique for each string, but without randomization so that each fingerprint always has the same one. This makes it very easy for the user to be assured that he's entered the right fingerprint.
It should be a little "identicon like" (search for "Identicons" and you'll know what I mean), but probably more detailed and stylish. Those randomart images that SSH use comes to mind, but they are not random enough. The process to generate them should make it hard to generate multiple keys with images similiar enough to be mixed up by a user.
What do you think? I want comments.