RC03: The Curious Case of the Inconsistent Byte Order

This week, I started working on building a TCP/IP stack from scratch in C.

Part of the IP implementation is calculating the checksum, which requires splitting the IP header into 16-bit chunks. I'll be using these hex bytes from an IP packet as an example

45 00 00 14 00 01 00 00 40 06 00 00 0a 00 02 0f d0 5e 75 2b

which should be converted into the following chunks

4500 0014 0001 0000 4006 0000 0a00 020f d05e 752b

Sounds simple, right? I thought so too, but not when C code is involved! Things didn't work as I expected them to, and I decided to start an investigation.

Initial assessment

Here's the program I was working with. It first creates an IP packet, then displays the packet as 16-bit chunks.

#include <stdio.h>
#include <stdlib.h>
#include <arpa/inet.h>

struct ipv4 {
    uint8_t     version_ihl;
    uint8_t     tos;
    uint16_t    len;
    uint16_t    id;
    uint16_t    frag_offset;
    uint8_t     ttl;
    uint8_t     proto;
    uint16_t    checksum;
    uint32_t    src;
    uint32_t    dst;
};

int main(void) {
    struct ipv4 * ip = calloc(1, sizeof(struct ipv4));
    uint32_t saddr, daddr;
    inet_pton(AF_INET, "10.0.2.15", &saddr);
    inet_pton(AF_INET, "208.94.117.43", &daddr);

    ip->version_ihl = 4 << 4 | 5;
    ip->tos = 0;
    ip->len = 20;
    ip->id = 1;
    ip->frag_offset = 0;
    ip->ttl = 6;
    ip->proto = 6;
    ip->checksum = 0;
    ip->src = saddr;
    ip->dst = daddr;

    uint16_t *p = (uint16_t *) ip;
    size_t count = sizeof(*ip);
    
    while (count > 1)  {
        printf("%.4x ", *p++);
        count -= 2;
    }
    printf("\n");

    return 0;
}

And...that didn't go as I hoped.

$ gcc -o checksum checksum.c
$ ./checksum
0045 0014 0001 0000 0640 0000 000a 0f02 5ed0 2b75

Chunks 2, 3, 4 and 6 look correct, but the other chunks display individual bytes in the opposite order.

The prime suspect - Byte Order

I suspected this to have something to do with the byte order - the way in which our machines stores bytes.

I explain these terms briefly in the following sections, but I would also recommend reading the Byte Order section from Beej's Guide to Network Programming, an excellent resource for low-level network stuff.

I assigned all variables in the way I usually would, so I assumed that the machine would store and print all values in the same order.

But seeing an inconsistent byte order in the output instead confused me, which made the investigation very interesting.

Trial and error

I started with changing the printing section of the code to display individual bytes instead of chunks.

uint8_t *p = (uint8_t *) ip;
size_t count = sizeof(*ip);

while (count > 1) {
    printf("%.2x ", *p++);
    count -= 1;     
}

printf("\n");

The output confused me even more.

$ gcc -o checksum checksum.c
$ ./checksum
45 00 14 00 01 00 00 00 40 06 00 00 0a 00 02 0f d0 5e 75 2b

This looks closer to the header at the start of the post, but bytes 3-6 are written in the wrong order. The correct order would be 00 14 00 01.

Additionally, the bytes are displayed in the exact opposite order of the chunks output. What? Why?

*sigh*

Let's put some questions in place to guide the investigation:

Why are bytes in the chunks output reversed?
Why does the bytes output have only some bytes printed in the opposite order?

Getting somewhere

The answer to the first question is an example I remembered, from the book Hacking: The Art of Exploitation. It prints the contents of a register in different ways in gdb. Here's a modified version of it:

(gdb) x/xh $eip
0x8048384 <main+16>: 0x45c7
(gdb) x/2xb $eip
0x8048384 <main+16>: 0xc7 0x45

The second command is the individual byte representation of the first command, the same as my case. The book also explains why this happens - the byte order, my prime suspect.

The little-endian order, which is the byte order of my machine (and most machines), stores bytes in the reverse order to what we think they would store.

Keeping the above example in mind, it is common to think that the value 0x45c7 would be stored as the bytes 45 c7 in memory. But nope, my machine stores the value as c7 45 instead, which is the output of the second command.

If they were stored in the opposite order, they would have to be read in the opposite order too. So the bytes are read from right to left, and hence displayed in the reverse order when printed as a chunk.

Okay, one question solved, one more to go!

The case gets complicated

The second question was not as easy to answer.

The bytes in question, bytes 3-6 of the header, correspond to the len and id fields of the IP header. Let's start with the declaration of these fields:

uint16_t    len;
uint16_t    id;

They're both 16 bits or 2 bytes in size. Here's how they were assigned:

ip->len = 20;
ip->id = 1;

As little-endian is the default byte order of the machine, it applies to these assignments too. So the value 20 is represented as hex bytes 14 00 in memory, while the value 1 corresponds to the hex bytes 01 00.

Now this is a problem, as network programs store and read data from left to right, like we do. That order is called the big-endian order.

To solve this, we would need to switch the byte order from little to big-endian, which can be done with a function called htons() or host to network short. Host Byte Order in this case is little-endian, while Network Byte Order is always big-endian.

This would solve the problem, but something doesn't feel right. Changing the byte order just for two fields doesn't make sense. Why do the other values not require htons()?

Mystery solved

It's something I struggled to figure even as I started typing this post, but I think I got it:

The fields version_ihl, tos, ttl, and proto are 8 bits or 1 byte in size. Byte order matters for values greater than a byte, which isn't the case here. So no htons() required.
The src and dst fields (32 bits each) are in big-endian order already, thanks to inet_pton(). No htons() required here either.
The frag_offset and checksum fields were a big reason behind the confusion. They're the same size as len and id, but were intialized to 0. As the bytes 00 00 are the same as 00 00¹, it looked like they displayed correctly. htons() would be required for these fields.

And now, it all makes sense. The byte order needs to be switched for all fields greater than a byte.

Conclusion

Based on the above findings, I made the following changes, making the byte order consistent across the struct.

ip->version_ihl = 4 << 4 | 5;
ip->tos = 0;
ip->len = htons(20);
ip->id = htons(1);
ip->frag_offset = htons(0);
ip->ttl = 64;
ip->proto = 6;
ip->checksum = htons(0);
ip->src = saddr;
ip->dst = daddr;

With that set, the bytes print correctly!

$ gcc -o checksum checksum.c
$ ./checksum
45 00 00 14 00 01 00 00 40 06 00 00 0a 00 02 0f d0 5e 75 2b

I changed the printing section to display chunks again, and they look fine too.

$ gcc -o checksum checksum.c
$ ./checksum
0045 1400 0100 0000 0640 0000 000a 0f02 5ed0 2b75

I was wondering if this swapped order of chunks would affect the resulting checksum. According to RFC 1071, it doesn't:

For example, assume a "little-endian" machine summing data that is stored in memory in network ("big-endian") order. Fetching each 16-bit word will swap bytes, resulting in the sum [4]; however, storing the result back into memory will swap the sum back into network byte order.

Interesting! I didn't know little-endian byte order worked like this.

With that, I declare this investigation complete. Detective Piya, signing off!

Update: Just as I was finishing up this post, I read through the Byte Order section in Beej's Guide, where I found this:

A lot of times when you’re building packets or filling out data structures you’ll need to make sure your two- and four-byte numbers are in Network Byte Order.

Oh well, the solution was here all along. Regardless, I enjoyed sharpening my debugging skills by figuring things out step by step (and making this post, too!).

Notes

Which one refers to which byte order is totally up to you :P ↩