How Windows Generates IP Header's ID Field

Background

Recently, I was browsing a freelance site and found reverse engineering task. Employers were interested in how Windows generates IP header's ID field. I decided to investigate whether this is a hard task or not.

According to MSDN protocol, driver calls ndis!NdisSendNetBufferLists to send data over network. If we set breakpoint on this function, we will find out that protocol driver in question is tcpip.sys. By walking the call stack and setting breakpoints on function calls that lead to ndis!NdisSendNetBufferLists call, we will find out that pointer to NET_BUFFER_LIST structure comes from netio!NetioAllocateAndReferenceNetBufferListNetBufferMdlAndData, that in turn calls ndis!NdisAllocateNetBufferList to obtain this pointer. Now let's see the structure of net buffer list:

NET_BUFFER_LIST holds pointer to NET_BUFFER, that holds pointer to MDL that describes data buffer. Each of these three structures can be linked (has Next field), so one NET_BUFFER_LIST can "host" multiple NET_BUFFER, and one NET_BUFFER can "host" multiple MDL. In my example, we have only one NET_BUFFER_LIST, one NET_BUFFER and one MDL.

MDL has MappedSystemVa and ByteCount members, so the memory range it describes starts at MappedSystemVa and ends before MappedSystemVa + ByteCount. NET_BUFFER has DataOffset and DataLength members that specify used subrange (that holds data payload) inside range described by MDL.

The format of network "unit":

We don't consider Data portion here, because in my example "unit" is split: NET_BUFFER's DataPhysicalAddress field points to Data portion of network "unit", so buffer described by MDL contains only MAC, IP header and TCP header. When netio!NetioAllocateAndReferenceNetBufferListNetBufferMdlAndData returns buffer that contains only TCP header. IP header and MAC are prefixed later, NET_BUFFER's DataOffset gets decremented and DataLength gets incremented accordingly, so when ndis!NdisSendNetBufferLists call is made, all headers are in place.

Lets see IP header format (IPv4):

We are interested in 16-bit identification field, namely how tcpip.sys driver generates it. I will not go into details, because I am not very interested in it, I just want to show what happens.

So How Does It Work

First, we allocates zero-initialized array of counters. Now imagine that for each element in this array (accessed by index), we reserve some unique value. On input, we have Signature, we feed this value to RtlLookupEntryHashTable to get corresponding hash table entry. This entry contains aforementioned index and corresponding value. Each time we generate id for some Signature, element accessed by corresponding index will be incremented. It looks like this on Windows 8.1 x86:

DWORD *pIpFragmentIdIncrementTable;    // global var

... IppStartPacketizeManager(...)
{
    ...

    pIpFragmentIdIncrementTable = ExAllocatePool(NonPagedPool, 8192 * sizeof(DWORD));

    ...
}

... IppCleanupPacketizeManager(...)
{
    ...

    ExFreePool(pIpFragmentIdIncrementTable);

    ...
}

// functions that generate ID values:
// 1) tcpip!Ipv4pFillProtocolHeader
// 2) tcpip!Ipv4pUpdateProtocolHeader
// 3) tcpip!IpNlpFastContinueSendDatagram 
// (this function will eventually call ndis!NdisSendNetBufferLists)

RTL_DYNAMIC_HASH_TABLE_ENTRY *pEntry = RtlLookupEntryHashTable(pHashTable, Signature, NULL);
UCHAR *p = *((UCHAR**)((UCHAR*)pEntry - 8));
WORD index = *((WORD*)(p + 0x56));
DWORD value = *((DWORD*)(p + 0x70));
DWORD prev = InterlockedIncrement(pIpFragmentIdIncrementTable + index) - 1;
WORD id = (WORD)((value + prev) & 0x7FFF);
id = (id >> 8) | (id << 8);        // swap on little endian machine

So we can say that protocol driver tcpip.sys uses hash table provided by Windows kernel and array of counters to generate IPv4 header's ID field.