Notes on Teredo (part 2)

Before going more into Teredo it’s worth talking about the types of NAT.

Types of NAT

When an internal device sends a packet to an Internet device, the source address and port (i.e. the private IPv4 address and port number of the internal device) are translated by the NAT. The outgoing packet from the NAT device will have the source IPv4 address set as the public IPv4 address of the NAT box and a newly assigned port on the NAT box as the source port address of the packet. And a mapping for this will be stored on the NAT box (internal IPv4 address, port number <-> Public IPv4 address, port number).

What happens next is what defines the various types of NAT:

Cone NAT

In a cone NAT, once a mapping is thus stored, packets from any external device to the public IPv4 address and port number of the mapping will be forwarded to the internal IPv4 address and port number. The key word here is any. So my machine behind the NAT can send a packet to (say) from port 1234 of my machine -> this will create a mapping on the NAT box from my internal IPv4 address and port 1234 to the public IPv4 address and (say) port 5467. Now a totally different server (say) can send a packet to port 5678 of the public IPv4 address and it will be forwarded to my machine’s port 1234.

Essentially my internal machine has a port mapped on the NAT now which is always forwarded to my machine. Of course, the mapping could go after a while of disuse and then I’ll get a new external port number and mapping, but suppose I kept sending traffic to keep the mapping alive the port is forever forwarded to me.

You can imagine this looks like a cone. The tip of the cone is the public IPv4 address and port. The base – the open end – is everything in the external world. Everything in the external world can contact me on that port. It’s like a cone, hence the name.

Restricted NAT

In a restricted NAT, once a mapping is stored, only packets from the particular external device which the packets were originally sent to can connect to the mapping and be forwarded. That is, in the example above once there’s a mapping for my internal IPv4 address and port 1234 to the external public IPv4 and port 5467 for, only can send a packet to the external IPv4 address and port 5678 and it will be forwarded to my machine, if sends a packet to the same IPv4 address and port it will be discarded.

There is a stricter form of restricted NAT where even the port number of the sender is checked. That is, if initial packet was to pot 9999 of, only packets from port 9999 of are allowed to enter via that mapping. Packets from port 9998 of will be silently discarded!

Symmetric NAT

Symmetric NAT takes things one step further!

In the two NAT types above the mapping is stored for all traffic from the internal device and internal IP. That is if I send packets from port 1234 and my internal IPv4, a mapping is created to port 5678 on the NAT box and that is used for all traffic from port 1234 of my internal machine. So – I contact from internal port 1234, the same mapping is used. I contact from the same internal port, the same mapping is used. I contact from the same internal port, the same mapping is used! The only difference between the two types above was to do with the incoming packets – whether they were from an IPv4 address (and port, in the stricter version) that was previously contacted. But the mapping was always the same for all traffic.

However, in Symmetric mapping a new mapping is created for each destination. So if I contact from port 1234 of my internal machine, it could be mapped to port 5678 of the NAT box and a mapping created for that. Next, if I contact from port 1234 of the internal machine (same internal port as before), it could be mapped to port 5889 of the NAT box and a new mapping created for that. And later if I contact from again the same port 1234 of the internal machine, yet another mapping will be created on the NAT box, say to port 6798. And worse, each of these mappings behaves like a Restricted NAT mapping – i.e. only the IP address to which the packets were initially sent when creating that mapping can use the mapping to send back packets.

You can see why this is called Symmetric NAT. It’s because each traffic from the internal side has its own mapping on the external side. There is a one-to-one mapping from the internal port & IPv4 address to the external port for each traffic.

Why do the types matter?

It’s important to know what type of NAT a particular is in when using Teredo. Because remember my quick overview of Teredo – at step 2 the host behind the NAT asks the server for an IPv6 address and it gets it. What this also does is that a mapping is created on the NAT box for the host’s internal IPv4 address and port number to the NAT box’s public IPv4 address and external port. Now …

If the NAT were Cone, then at step 8 a Teredo relay can forward IPv6 over IPv4 packets to the internal host by sending to the external port and NAT public IPv4 address.

But if the NAT were Restricted, then step 8 would fail as the internal host hasn’t contacted the relay yet and so there’s no mapping for the relay’s IPv4 address and/ port port  (it could be that the internal host has contacted the relay to send some packets and this is a response from the relay, in which case it will be let through, but it could also be a fresh connection from the relay forwarding packets from an IPv6 host that are not in response to anything from the internal host – these will be discarded). So in the case of a restricted NAT Teredo has some additional stuff to do first – namely create a mapping in the NAT table for the Teredo relay’s IPv4 address.

First the Teredo relay checks if the IPv4 address and port of the Teredo client – which it extracts from the Teredo IPv6 address of the client – are known to it. If it is known (as in the relay and client have communicated recently) it means a mapping exists and the relay can send the packet to the client.

If a mapping does not exist the Teredo relay takes help of the Teredo server to punch a hole in the NAT. This is akin to the Romeo & Juliet example I described yesterday. The relay needs to contact the client but the client’s NAT box will discard any packets that are not in response to something that the client has sent out, so the relay needs a third party server “friend” to help out. Here’s what happens:

  1. The Teredo relay queues the incoming packet.
  2. From the Teredo IPv6 address of the client it extracts the IPv4 address of the Teredo server.
  3. The relay then creates a “bubble packet” with the source address as the relay’s IPv6 address, destination as the client’s Teredo IPv6 address, and sends it to the Teredo server’s IPv4 address. A bubble packet is essentially an empty IPv6 packet. Since it is sent to the IPv4 address of the Teredo server, it will be encapsulated in an IPv4 packet.
  4. The Teredo server extracts the IPv6 bubble packet. From the bubble packet’s destination IPv6 address the Teredo server notes that it itself if the Teredo server for that client. This tells the server that its help is required for hole punching. It notes the IPv4 address of the relay from the source address of the packet (this is used in step 7).
  5. The Teredo server extracts the NAT IPv4 address and port from the host portion of the client’s Teredo address. It puts the bubble packet within a UDP message and sends it over IPv4 to the IPv4 address and port of the NAT box. The NAT box forwards this packet to the internal host (the Teredo client) as a mapping already exists for the Teredo server IPv4 address.
    • The UDP packet has to contain the Teredo server IPv4 address and port as the source address and port. It has to else the packet won’t pass through NAT. But the client also needs to know the IPv4 address of the Teredo relay. So the Teredo server sets an “Origin Indication” within this UDP packet that specifies the IPv4 address of the Teredo relay.
  6. The Teredo client receives the bubble packet in UDP. From the “Origin Indication” it knows the IPv4 address of the Teredo relay. From the bubble packet it knows the IPv6 address of the Teredo relay. And since it doesn’t know the Teredo relay’s IPv4 address and this packet came from its Teredo server – indicating that the client has to do it’s part of the hole punching – the client will now create a new IPv6 bubble packet, setting its Teredo IPv6 address as the source and the Teredo relay’s IPv6 address as the destination, put this within a UDP message, set the IPv4 address of the Teredo relay as the destination, and send it out.
  7. The packet passes through NAT and reaches the Teredo relay. Since this is a response to the bubble it previously sent, the Teredo relay knows the mapping is ready. Now the Teredo relay sends the previously queued incoming packet to the Teredo client and it gets through …!

Phew! Now we know why Teredo is a tunnel of last resort. There’s so much behind the scenes stuff that has to happen to keep it working. And that’s not to mention additional stuff like regular bubble packets from the Teredo client to server to keep the NAT mapping alive, checks to ensure there’s no spoofing done, and many more. Added to that, for security reasons an update to the Teredo RFC (Teredo RFC is RFC 4380, update is RFC 5991) specifies that Teredo should always assume it’s behind a Restricted NAT and so the above steps must always be done, even for clients behind Core NATs.

Back to NATs – if the NAT were Symmetric, Teredo does not work at all unless you make some changes on the NAT to exempt the Teredo clients. (Teredo in Windows Vista and above can work between Teredo clients if only one Teredo client is behind a Symmetric NAT and the other is behind a Cone/ Restricted NAT).

Identifying the type of NAT

Here’s how a Teredo client identifies the type of NAT it is behind.

Two things are in play here:

  1. The Teredo client IPv6 address has a flag that specifies whether it is behind a cone NAT or not. This flag is in the host bits of the address – remember I had previously mentioned the host bit has some flags, random bits, and the NAT IPv4 address and port number? One of these flags specifies whether the client is behind a cone NAT or not.
  2. The Teredo server has two public IPv4 addresses. The Teredo RFC does not expect these to be consecutive IPv4 addresses, but Windows Teredo clients expect these to be.

When the Teredo client contacts the Teredo server initially for an IPv6 address, it sends a Router Solicitation message as all IPv6 clients do (the difference being this is a unicast message, sent within a UDP message over IPv4 to a specific Teredo server address). The Router Solicitation message requires a link-local address – all Router Solicitation messages do – so the Teredo Client generates one, following the same format as a regular Teredo IPv6 address. The network prefix of this link-local address is set to fe80::/64, with the host bits having flags and random bits as usual but with the embedded IPv4 address being the private IPv4 address and port of the internal host rather than the public IPv4 address and port of the NAT box (because the Teredo client doesn’t know what this is).

This link-local address sets the cone flag is 1 – meaning the client believes it is behind a cone NAT.

When the Teredo server receives this it sends a Router Advertisement message as usual (as a UDP message within IPv4 unlike usual). The server does a trick here though. Instead of responding from the public IPv4 address on which it received the UDP message from the client, it responds from the second public IPv4 address. If this reply from a different IPv4 address gets through the NAT, then the client knows it is indeed behind a cone NAT. But if no replies come through (after an appropriate time-out (default: 4s) and number of retries (3 times)), the client realizes it may not be behind a cone NAT and so it sends a new Router Solicitation message to the Teredo server only this time it sets the cone flag to 0 (i.e. not behind a cone NAT).

Again the Teredo server receives the message and sends a Router Advertisement message, but now since the cone flag is 0 it sends the reply from the same IPv4 address as it received the message on. This will get through, confirming to the client that it is behind a non-cone NAT. (Note: If this reply too does not get through, after an appropriate time-out and number of retries the client realizes that UDP messages are blocked/ not getting through NAT/ firewall and so it sets the Teredo interface as disconnected/ off-line. Teredo cannot be used in this situation).

Next the client needs to know if it is behind a symmetric NAT. It now contacts the Teredo server on the second IPv4 address with a Router Solicitation message, setting the cone flag to 0 so the server uses the same IPv4 address when replying, and when it gets a reply from the Teredo server it compares the NAT port in the reply with the NAT port in the previous reply. If the ports are same the client determines that it is behind a restricted NAT; if the ports are different the client determines it is behind a symmetric NAT and that Teredo might not work.

(Note: I oversimplified a bit above to keep things easy. When the Teredo server sends a Router Advertisement, this includes the network prefix only. The host bits are set by the Teredo client once it identifies the type of NAT it is behind. The host bits require knowledge of the NAT IPv4 address and port, but how does the Teredo client know these? It knows these because the Router Advertisements from the Teredo server contains an “Origin Indication” field specifying the public IPv4 address and port. This is how the client gets the port number used for both Router Advertisements and determines if it is behind a symmetric NAT or not. Once that determination is done, the client has all the info required to self-assign a Teredo IPv6 address).