Detect NAT for udp/dublin strategy

[fujiapple852]

The udp/dublin strategy makes it possible to detect NAT(s) that occur along the path of a given flow. Some introductory information on the technique is given at https://dublin-traceroute.net/ and the details can be studied in the code.

For udp/dublin we maintain a stable udp checksum for each probe in a single round as the sequence number is encoded in the ip identifier field and so the virtual header is constant. Therefore, if the udp checksum observed in the nested (original datagram) of an ICMP response differs then we know that NAT has occurred at some point along the path.

By comparing the udp checksum for all probes in a given round, specifically checking for changes in the checksum between hops which responded in the round, we can identify at which hop(s) NAT occurred and report this to the user.

Note: this does not work for udp/paris as the checksum differs for each probe in a round, as the checksum is used to encode the sequence number. Indeed, udp/paris does not work at all when a path traverses a NAT. Likewise, this does not work for udp/classic as the udp checksum is not stable between probes in a round as the sequence is recorded in the src or dest port, which are part of the virtual header used to compute the udp checksum.

In the following example (for udp/dublin over 1 round) all the outgoing udp packets have checksum 0xe5fc. The checksum observed (in the udp original datagram payload of the icmp response) is 0xe5fc for the first hop (seq 33000) and there is no response for the probe at the 2nd hop (seq=33001).

The 3rd hop (seq=33002) has a different observed checksum of 0x8eb3 which indicates that this hop performed a NAT. Note that the NAT may have occurred at the previous hop (seq=33001) but as that did not respond in this round it is impossible to know.

The 4th hop (seq=33003) has the same checksum as the prior hop, 0x8eb3, and so whilst this differs from the initial checksum (i.e. 0xe5fc) this does not indicate an additional NAT. To say it another way, the change in checksum due to NAT "carries forward" throughout all remaining hops.

The 5th hop (seq=33004) shows a new checksum, 0xd993, which differs from the previous hop and so again we can conclude that NAT occurs at this hop.

Sent: seq=33000 checksum=0xe5fc
Recv: seq=33000 checksum=0xe5fc

Sent: seq=33001 checksum=0xe5fc
Recv: none

Sent: seq=33002 checksum=0xe5fc
Recv: seq=33002 checksum=0x8eb3 <- NAT #1

Sent: seq=33003 checksum=0xe5fc
Recv: seq=33003 checksum=0x8eb3

Sent: seq=33004 checksum=0xe5fc
Recv: seq=33004 checksum=0xd993 <- NAT #2

[fujiapple852]

It is not entirely clear if Dublin-style NAT detection is supposed to work or whether it is an artefact of a device which does not conform to specification.

Specifically, NAT can only be detected if a NAT device fails to correct the checksum of a UDP packet embedded in an ICMP error message in the WAN->LAN direction. So the question is, is the NAT device supposed to correct this checksum?

Example

We send the following IPv4/UDP packet (note the IPv4 Checksum A and UDP Checksum B):

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
|Version|  IHL  |Type of Service|          Total Length         | │             
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
|         Identification        |Flags|     Fragment Offset     | │             
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
|  Time to Live |    Protocol   |            Checksum A         | │ IPv4 Header 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
|                         Source Address                        | │             
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
|                      Destination Address                      | │             
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
                                                                                
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
|          Source Port          |        Destination Port       | │             
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ UDP Header  
|             Length            |            Checksum B         | │             
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │             
                                                                                

We expect to receive the following ICMP TimeExceeded error which contains the Original Datagram (OD) IPv4/UDP packet we sent above with Checksum A' and Checksum B':

 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
 |Version|  IHL  |Type of Service|          Total Length         | │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
 |         Identification        |Flags|     Fragment Offset     | │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
 |  Time to Live |    Protocol   |            Checksum C         | │ IPv4 Header                        
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
 |                         Source Address                        | │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
 |                      Destination Address                      | │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
                                                                                                        
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
 |      Type     |      Code     |            Checksum D         | │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ IPv4 Payload (ICMP TE Header)      
 |                             Unused                            | │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │                                    
                                                                   │                                    
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │                                  
 |Version|  IHL  |Type of Service|          Total Length         | │ │                                  
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │                                  
 |         Identification        |Flags|     Fragment Offset     | │ │                                  
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │                                  
 |  Time to Live |    Protocol   |            Checksum A'        | │ │ ICMP TE Payload (OD IPv4 Header) 
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │                                  
 |                         Source Address                        | │ │                                  
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │                                  
 |                      Destination Address                      | │ │                                  
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │                                  
                                                                   │ │                                  
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │ │                                
 |          Source Port          |        Destination Port       | │ │ │                                
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │ │ OD IPv4 Payload (UDP header)   
 |             Length            |            Checksum B'        | │ │ │                                
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ │ │ │                                

For Dublin NAT to work we are detecting when Checksum B' in the ICMP error does not match the Checksum B in the UDP packet we sent.

What does the spec say?

RFC 3022 section 4.3 says:

Changes to ICMP error message ([ICMP]) will include changes to IP and
ICMP headers on the outer layer as well as changes to headers of the
packet embedded within the ICMP-error message payload.

In order for NAT to be transparent to end-host, the IP address of the
IP header embedded within the payload of ICMP-Error message must be
modified, the checksum field of the embedded IP header must be
modified, and lastly, the ICMP header checksum must also be modified
to reflect changes to payload.

In a NAPT setup, if the IP message embedded within ICMP happens to be
a TCP, UDP or ICMP Query packet, you will also need to modify the
appropriate TU port number within the TCP/UDP header or the Query
Identifier field in the ICMP Query header.

Lastly, the IP header of the ICMP packet must also be modified.

My interpretation is that:

• "the checksum field of the embedded IP header" is Checksum A'
• "the ICMP header checksum must also be modified to reflect changes to payload" is Checksum D

Therefore this RFC says nothing about NAT modifying the checksum we are interesting in, namely Checksum B'.

RFC 1631 says:

If an ICMP message is passed through NAT, it may require two address
modifications and three checksum modifications. This is because most
ICMP messages contain part of the original IP packet in the body.
Therefore, for NAT to be completely transparent to the host, the IP
address of the IP header embedded in the data part of the ICMP packet
must be modified, the checksum field of the same IP header must
correspondingly be modified, and the ICMP header checksum must be
modified to reflect the changes to the IP header and checksum in the
ICMP body. Furthermore, the normal IP header must also be modified as
already described.

My interpretation:

• "three checksum modifications" is noteworthy as we have 4 checksums in our example, Checksums A, B, C & D.
• "for NAT to be completely transparent to the host" is perhaps poorly worded, but I think the intent is to say that the host should not be aware that NAT has occurred.
• "the checksum field of the same IP header must correspondingly be modified" is Checksum A'
• "the ICMP header checksum must be modified" is Checksum D
• "Furthermore, the normal IP header must also be modified as already described." is Checksum C

Therefore this RFC says nothing about NAT modifying the checksum we are interesting in, namely Checksum B'.

Conclusion

NAT devices are not required by RFC 3022 or RFC 1631 to correct Checksum B' (the checksum of the UDP header embedded in the ICMP error packet), despite requiring that "NAT to be completely transparent to the host".

NAT devices (and router, which perform NAT) are not forbidden from correcting this checksum however, so the Dublin NAT detection technique is useful only for such devices which choose not to perform this correction.