For that I'd recommend tinc [1].

1: http://www.tinc-vpn.org

It's similar in that it's peer-to-peer, but doesn't require an auth/directory server to establish connections. If any known peer is accessible, the two can authenticate directly.

To successfully traverse many NATs you need a third party, which is already accessible from two parties trying to handshake.

Yep, that's what I meant by "accessible" too. But with Hamachi, there's a central service for client authentication. With freelan, peers authenticate directly via signed crts.

I looked into this heavily over the past few days. The punchline is this needs support for NAT traversal and some type of out-of-band way for clients to find each other.

NAT traversal is an implementation thing, and I favor Jabber as the out-of-band these days since everyone can get at least a GTalk account.

Though we now have libjingle, which basically merges both of these things and would probably elegantly solve the problem. But p2p vpn's aren't much use if you have to control the NAT router you're attached to.

> I favor Jabber as the out-of-band these days since everyone can get at least a GTalk account.

Isn't that deprecated in favour of Google Hangouts?

Whatever they're calling it, you can still get free XMPP accounts easily.

If it has been tied to hangouts then it has been tied to g+ and their ridiculous policies, I hardly class it as a good alternative.

Doesn't seem to be a problem with connecting with Pidgin, and I had it working with Wippien (sadly Wippien doesn't really work great with Win 7 or Linux).

Google has stopped federating with other Jabber services. They have replaced the GTalk Android app with the Google Hangouts app. They have started pushing people (forcibly) towards Google Hangouts instead of Google Talk. How long before XMPP support is dropped? I don't think we can claim that Google will keep it around for certain.

There are many other options, though: http://xmpp.net/

Not if one user is on Google Hangouts, and the other user isn't. Google dropped federation a while ago.

For VPN purposes, a throwaway Jabber account you use solely for that is perfectly acceptable though. The thing needed here is mostly a channel for two hosts to find their public IP addresses and communicate that information.

p2pvpn <http://www.p2pvpn.org/> uses BitTorrent trackers for it - which is actually a pretty good solution, but sadly also - no NAT holepunching or even UPnP yet.

Though I have been trying to find a VPN which uses a Tor hidden service to define network rendeavous point - since Tor is distributed and available, you could issue invites with the hidden service ID, and then send real IPs to members to establish P2P (so, not using the anonymity, just using it to bootstrap the network). SocialVPN does something similar, but I couldn't get it work reliably in tests (it would go up...then my hosts went down and I couldn't get them to appear to each other again).

Isn't the upnp feature of most home routers enough?