Parasitic computing with ICMP: making routers do arithmetic | Anagogistis<br>When a router discards our packet because its TTL has reached zero, it will usually send back an ICMP Time Exceeded message to tell us what happened. Interestingly, the reply quotes the original IPv4 packet’s header and at least the first eight bytes of its payload, and the checksum is computed over the entire ICMP message, including those quoted payload bytes.<br>The idea we explore here is whether we can arrange the packet so that, despite all the other fields included in the calculation, the resulting value is the checksum of only the payload bytes we want to process.<br>The complication is that the payload is not the only thing included in the checksum. The reply also contains an ICMP header written by the router and the quoted IPv4 header of the original packet. We cannot remove those fields, but we can carefully choose some bytes in the original packet’s payload so that their contribution cancels out the contribution of the headers. The value left in the checksum field is then the Internet checksum of the remaining payload bytes.<br>This is in the spirit of parasitic computing: using protocol machinery to perform work unrelated to its intended purpose. The classic version of the trick abuses TCP checksum validation to answer yes-or-no questions. Here, the checksum field is not merely a test but the result itself, and with some chaining it is enough to build addition, subtraction, and multiplication out of nothing but expired packets.<br>Choosing the quoted payload<br>Before doing anything with the checksum, we need a way to place arbitrary bytes immediately after the IPv4 header. Using UDP or TCP would mean that the first quoted bytes belonged to a transport header, with fields that might be interpreted or rewritten along the path.<br>Instead, the probes use IPv4 protocol number 253, one of the values reserved by RFC 3692 for experimentation and testing. There is no transport protocol layered on top of it here: its payload is simply the sequence of bytes we choose to send.<br>That makes the first eight quoted payload bytes entirely ours. Middleboxes will normally have no reason to interpret or rewrite them, although some networks may simply filter packets carrying an unfamiliar protocol number.<br>The Internet checksum<br>ICMP, defined originally in RFC 792, carries diagnostics and error reports inside IPv4. Every ICMP message begins with a type, a code, and a 16-bit checksum.<br>That checksum is the Internet checksum described in RFC 1071. To compute it, the checksum field is first set to zero. The message is then divided into 16-bit words, those words are added using one’s-complement addition, and every bit of the final sum is flipped.<br>The important detail for us is that the checksum covers the entire ICMP message, including both its header and its payload.<br>One’s-complement addition is ordinary binary addition, except that a carry beyond the most significant bit is wrapped around and added back at the low end. For example:<br>11110000 11110000<br>+ 00010000 00110000<br>1 00000001 00100000

The leading 1 is the end-around carry. Adding it back into the low 16 bits gives:<br>00000001 00100001

Finally, flipping every bit produces the checksum:<br>~00000001 00100001 = 11111110 11011110

In general, for words w₁ through wₙ:<br>checksum = ~(w₁ ⊞ w₂ ⊞ ... ⊞ wₙ)

where ⊞ denotes one’s-complement addition and ~ denotes bitwise complement.<br>That final complement also makes verification simple. If the checksum word is included when all the words are added again, an intact message produces 0xFFFF.<br>One’s-complement arithmetic has two representations of zero: positive zero, 0x0000, and negative zero, 0xFFFF. Both act as additive identities:<br>S ⊞ 0x0000 = S<br>S ⊞ 0xFFFF = S

That second identity is particularly useful here.<br>The Time Exceeded reply<br>The message we are targeting is ICMP Time Exceeded, type 11, code 0. A router may return one after decrementing a packet’s TTL to zero. This is the same mechanism that traceroute uses to discover the routers along a path.<br>The reply has the following structure:<br>0 1 2 3<br>0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1<br>+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>| Type | Code | Checksum |<br>+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>| unused |<br>+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<br>| Internet Header + 64 bits of Original Data Datagram |<br>+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The payload of the ICMP reply contains the quoted IPv4 header followed by at least the first eight bytes of the original packet’s payload. Because we used protocol 253, those eight bytes are not a UDP or TCP header. They are simply the eight bytes we supplied.<br>Everything shown above contributes to the ICMP checksum. The quoted payload bytes are under our control, but the ICMP header and the quoted IPv4 header are present as well. To turn the reply into a clean checksum...