IPSEC VPNs - Advanced NAT

Here are some pointers for when you are trying to build an IPSEC VPN to a remote organization and they NAT the remote host due to address overlap.

For example:

Remote Host: 172.16.1.2
Translated Public IP: 2.2.2.2
Remote Firewall: 2.2.2.1 (Cisco 3000 Series VPN Concentrator/PIX/ASA)

Local Firewall: 3.3.3.1 (Fortigate)
Local Network: 172.16.1.0/255.255.255.0 (NAT traffic to external firewall interface)

Begin by reading this previous post: Advanced IPSEC with Phase 2 Quick Mode Selectors
The one change to note is that you need to configure this scenario in policy mode. There is either a bug or a "feature" which prevents the NAT from working correctly in interface mode. I am currently investigating.

The challenge for the above scenario is typically to select the correct phase 2 source and destination addresses to match the remote access lists. In the above example your local configuration should look similar to the following:

config firewall address
edit "net-172.16.1.0/24"
set subnet 172.16.1.0 255.255.255.0
next
edit "host -2.2.2.2"
set subnet 2.2.2.2 255.255.255.255
next
edit "host-3.3.3.1"
set subnet 3.3.3.1 255.255.255.255
next
end

config firewall addrgrp
edit "encdom-local-remote"
set member "net-172.16.1.0/24" "host-3.3.3.1"
next
end

config vpn ipsec phase1
edit "Remote_Firewall"
set interface "external"
set dpd disable
set nattraversal enable
set dhgrp 2
set proposal 3des-md5
set keylife 86400
set remote-gw 2.2.2.1
next
end

config vpn ipsec phase2
edit "Remote_Tunnel"
set phase1name "Remote_Firewall"
set proposal 3des-md5
set src-addr-type name
set src-name "encdom-local-remote"
set dst-addr-type name
set dst-name "host-2.2.2.2"
set keylifeseconds 28800
next
end

config firewall policy
edit 1
set srcintf "internal"
set dstintf "external"
set srcaddr "n-172.16.1.0/24"
set dstaddr "h-2.2.2.2"
set action ipsec
set schedule "always"
set service "ANY"
set profile-status enable
set logtraffic enable
set profile "scan"
set outbound enable
set natoutbound enable # Hide traffic behind firewall's external interface
set vpntunnel "Remote_Firewall"
next
end

Here is what you are telling the firewall: Take my traffic from 172.16.1.0/24 and send it through the VPN tunnel to the remote firewall. NAT the traffic so it appears to be coming from my firewall's external interface 3.3.3.1.
Notice that in the phase 2 quick mode selectors you specify both 3.3.3.1 as well as your local network 172.16.1.0/24. Otherwise the phase 2 parameters sent to the peer do not match.