Battling with freeswan, I finally succeeded in bringing a VPN tunnel between a server and a client behind a NAT gateway. It was not that easy because x509 and nat traversal patches are somewhat conflicting. I ended up in installing superswan, which is a heavily patched freeswan version (I'd advise kids NOT googling for superswan ). I'm so happy it eventually work I can't resist posting this micro howto here (moreover, backups are for wimps, real men upload their data to an FTP site and have everyone else mirror it).

The schema is the following :

[ LAN ] -- [ VPN GW ] --- Internet --- [ NAT GW ] -- [ VPN01 GW ] -- [ LAN ]
  ^             ^                        ^              ^             ^
192.168.1.0/24  |                   23.45.67.89         |    192.168.100.0/24
                123.45.67.237                       192.168.100.1

Relevant excerpt of ipsec.conf from server side :

conn tunnel-lan-vpn01
        left=123.45.67.237
        leftcert=gw.pem
        leftnexthop=23.45.67.89
        leftsubnet=192.168.1.0/24
        right=23.45.67.89
        rightcert=vpn01.pem
        rightnexthop=192.168.100.1
        rightsubnet=192.168.100.0/24
        auto=start

Relevant excerpt of ipsec.conf from client side (with nat_traversal=yes in setup stanza):

conn tunnel-vpn01-lan
        auto=start
        left=192.168.100.1
        leftcert=vpn01.pem
        leftnexthop=23.45.67.89
        leftsubnet=192.168.100.0/24
        right=123.45.67.237
        rightcert=gw.pem
        rightsubnet=192.168.1.0/16