Firewalls And NAT'ing And The Traveling Packet

Its an interesting thing to me, that NAT'ing takes place before routing does on most firewalls.  So, if your public IP address space was 10.10.10.X/24, and you decided that you wanted to NAT your internal 192.168.1.10 server to the public IP address of 10.4.4.4, you could.  Now, you might start to think that "you cant do that" because your 10.4.4.4 is not on your 10.10.10.X/24 address space, right?  Well, actually, that is wrong.  You actually CAN  have a public IP address that is not on your public IP range and have it NAT through to your internal server.  Routing at the upstream router certainly poses a problem, but if a packet can make it to your firewall, then you can NAT your traffic to any public IP address you want to, even if its not part of your IP range on  your firewall interface.
I actually went through this recently on a certain problem I was having on a Check Point firewall.  You see, it was the same thing really.  I had a public range of, lets say, 40.40.40.0/25.  This gives us 126 usable IP addresses (1-126).  However, in the config, they had some NATs that were outside of that range.  Now, just so you know, they actually owned the whole /24 of 40.40.40.0.  But, on the firewall interface, they had split up this subnet and were not using anything above this range (40.40.40.0/25).
In our example, they had a static NAT translation of 40.40.40.200 pointing to a webserver inside the network at 192.168.1.200.  I thought that since it was not on the subnet of the public facing NIC on the firewall, the firewall would try to route it out its default gateway (the upstream router), which would try to send it back and ultimately the TTL would hit 0 and the packet would drop.  But, this is NOT what happens.  What actually happens is that NAT is checked FIRST.
Below, I have the best explanation (from Cisco) of the process the packet actually takes going through the firewall from the outside to the inside.  This process also applies to Check Point as well.  Notice that first, the ACL is checked to see if the packet is allowed, then NAT.   Notice its not until step 7 and 8 where routing comes into place.  Its a very interesting process for sure.  Take a walk through the steps below.  Its a really good read through.
Steps

1. The packet is reached at the ingress interface. Once the packet reaches the internal buffer of the interface, the input counter of the interface is incremented by one. 

2. Cisco ASA first looks at its internal connection table details in order to verify if this is a current connection. If the packet flow matches a current connection, then the Access Control List (ACL) check is bypassed and the packet is moved forward.If packet flow does not match a current connection, then the TCP state is verified. If it is a SYN packet or UDP (User Datagram Protocol) packet, then the connection counter is incremented by one and the packet is sent for an ACL check. If it is not a SYN packet, the packet is dropped and the event is logged. 

3. The packet is processed as per the interface ACLs. It is verified in sequential order of the ACL entries and if it matches any of the ACL entries, it moves forward. Otherwise, the packet is dropped and the information is logged. The ACL hit count is incremented by one when the packet matches the ACL entry. 

4. The packet is verified for the translation rules. If a packet passes through this check, then a connection entry is created for this flow and the packet moves forward. Otherwise, the packet is dropped and the information is logged. 

5. The packet is subjected to an Inspection Check. This inspection verifies whether or not this specific packet flow is in compliance with the protocol. Cisco ASA has a built-in inspection engine that inspects each connection as per its pre-defined set of application-level functionality. If it passed the inspection, it is moved forward. Otherwise, the packet is dropped and the information is logged.Additional security checks will be implemented if a Content Security (CSC) module is involved. 

6. The IP header information is translated as per the Network Address Translation/ Port Address Translation (NAT/PAT) rule and checksums are updated accordingly. The packet is forwarded to Advanced Inspection and Prevention Security Services Module (AIP-SSM) for IPS related security checks when the AIP module is involved. 

7. The packet is forwarded to the egress interface based on the translation rules. If no egress interface is specified in the translation rule, then the destination interface is decided based on the global route lookup. 

8. On the egress interface, the interface route lookup is performed. Remember, the egress interface is determined by the translation rule that takes the priority. 

9. Once a Layer 3 route has been found and the next hop identified, Layer 2 resolution is performed. The Layer 2 rewrite of the MAC header happens at this stage. 

10. The packet is transmitted on the wire, and interface counters increment on the egress interface. 

11. The packet is transmitted on the wire, and interface counters increment on the egress interface.

Below is Check Points explanation in the CP documentation.  Very similar.