I consider myself to be relatively experienced in setting up site-to-site (LAN to LAN) VPN tunnels, and to pinpoint what is wrong if the tunnel does not come up, but working today with a technician on the other side of the Atlantic to set up such a link turned out to be a challenge.
We had agreed on all cryptographic parameters, on what private subnet to be used on each side of the tunnel and of course the preshared key. The guy in the other end seemed experienced enough, but going over and in a structural manner fiddling each parameter to try to find a match did not give the break. The scenario was quite funny:
Scenario: Tunnel clears phase 1 of the negotiation, meaning that the preshared key and the IKE parameters are a match on both sides. In phase two, some discrepancy makes a "no proposal chosen" message appear in the logs on the Checkpoint.
Strange: Even though the tunnel did not come up on the Checkpoint side, it did on mine. I was able to ping devices on his side, but he was not able to ping my side.
Solution: After having tested virtually everything, the guy on the other side mentions that his device has defined a class B private network on the interface. The tunnel definition, however, was to be for a much narrower range, a 29 bits mask (255.255.255.248). Although it would be shooting sparrows with a cannon, we broadened the tunnel definition to match his device's network interface, and voilla, it worked! It seems to be a limitation of the Checkpoint device this guy was using (or a limitation of knowledge on how to configure this device correctly) - I have without trouble set up dozens of other links with a narrower tunnel IP range than what the device is running on its network interface.
Caution: If someone else experiencing a similar problem is reading this, my advice would be first to check any firewall that might be blocking traffic (it was my first guess). If you can temporarily isolate vulnerable parts of your network while testing your new tunnel, I would first bring up the tunnel with the firewall completely off.
