IP fragmentation is an ancient mechanism that nevertheless yields surprising attacks in modern days, due to its complexity.
This post explains CVE-2018-8493, an interesting vulnerability that I’ve recently found and was patched in the latest Patch Tuesday.
INTRODUCTION
The IP protocol suite supports fragmentation in order to transport packets longer than a link’s MTU. The design relies on an identification field (“IP ID”), such that all fragments that belong to the same packet will have the same IP ID.
(Ipv4 only uses a 15 bit Identification field, whereas Ipv6 uses 31 bits which appears on an IPv6 optional header)
In 2003 it was shown that this design was vulnerable, as (in a naïve implementation, a global counter) an attacker could blindly intercept or discard packets. Later, more mature demonstrations surfaced (i.e this one).
Before that, predicting this identification field allowed attackers to scan networks without disclosing the compromised node (“idle scan”).
An excerpt from this master thesis shows the state of the art (2013) with major OSs’ implementations for the assignment method of IP ID:
Notice how Windows and non-BSD Linux are marked “Global” for a global counter. Not too great…
SO THEY SOLVED IT!
Around that time Microsoft started generating the IP ID randomly, uniquely per IP-PATH (=src,dst tuple).
They chosen the Toeplitz hash for this task (with a random 40 bytes key). Why? Because they were implementing Receive-Side-Scaling as hinted by the “Rss” prefix on the used functions. While mixing performance and security is not always the best idea, this design could in principle still be safe… but we’ll see.
IMPLEMENTATION
IP ID is calculated in the following way:
identification = base + increment
base is calculated at the IP path allocation (first packet sent to a new remote address). The logic is:
base = IpFragmentIdSecretTable ^ RssHashComputeToeplitzHash(protocol_family, SourceAddress, RemoteAddress);
IpFragmentIdSecretTable is a random DWORD generated on system start.
RssHashComputeToeplitzHash is calling RtlComputeToeplitzHash on the {SrcIP,DstIP} tuple
and increment is a dword out of an 0x8000 bytes long table called IpFragmentIdIncrementTable,
increment = IpFragmentIdIncrementTable[RssHashComputeToeplitzStreamHash(...) ^ IpFragmentIdSecretTableHighWord) & 0x1FFF]
CVE-2018-8493
The vulnerability lies in the fact that IpFragmentIdIncrementTable is not initialized with random content. It used to be (as it is in 6.2.9200.16399, from 2012), but in current latest windows 10 and 8.1 versions only 8 of its 0x8000 bytes are initialized. The rest are uninitialized, non-zeroed kernel memory, as received from ExAllocatePoolWithTagPriority.
Because of this reason, it is very likely that the increment value for an IP-path is zero, the attacker has many attempts to “hit” zero table entries, and can simply rank candidates for the key, choosing the highest ranking.
Using two samples of an identification field that were generated for different IP paths, and whose increment value is zero – it is possible to calculate a DWORD out of the key that is used for hashing, IpRssToeplitzHashKey.
RtlComputeToeplitzHash’s logic is:
int RtlComputeToeplitzHash(…){
result = 0;
do
{
result ^= matrices[2*offset+1][*input & 0xF] ^ matrices[2*offset][*input>>4];
offset += 2;
input++;
}
while ( remaining_bytes-- );
return result;
}
Essentially, each nibble from the input is used as an offset to a 4*4 Toeplitz matrix, the matrices are generated from the IpRssToeplitzHashKey. Taking a DWORD and a fifth byte each time, and taking a 32 bit “window” of the two with a specific bit offset (here I referred to the windowing as “rol”)
A Toeplitz matrix is simply a list of cells, each holds a mix of key bits (32 bits at a time), rolled a various number of times, and XORed between them.
an example to give the impression of it:
| 0 | rol(key[i],3) | rol(key[i],2) | rol(key[i],3) ⊕ rol(key[i],2) |
| rol(key[i],1) | rol(key[i],3) ⊕ rol(key[i],1) | rol(key[i],2) ⊕ rol(key[i],1) | rol(key[i],3) ⊕ rol(key[i],2) ⊕ rol(key[i],1) |
| rol(key[i],0) | rol(key[i],3) ⊕ rol(key[i],0) | rol(key[i],2) ⊕ rol(key[i],0) | rol(key[i],3) ⊕ rol(key[i],2) ⊕ rol(key[i],0) |
| rol(key[i],1) ⊕ rol(key[i],0) | rol(key[i],3) ⊕ rol(key[i],1) ⊕ rol(key[i],0) | rol(key[i],2) ⊕ rol(key[i],1) ⊕ rol(key[i],0) | rol(key[i],3) ⊕ rol(key[i],2) ⊕ rol(key[i],1) ⊕ rol(key[i],0) |
Important observations I had about this matrix and algorithm:
- The different cells contain different numbers of XOR’d elements.
- The hash state evolves by XORing itself with a new value
If we take two inputs that are identical besides their last element (= last nibble),
The hashing state for the two would be identical until the latest iteration, where it will evolve like this:
(i’ve taken 1 and 9 as the latest nibbles for the two samples)
Result1 ^= rol(key[i],3)
Result2 ^= rol(key[i],3) ^ rol(key[i],0)
In this case,
Result1 ^ Result2 gives rol(key[i],0), which is simply key[i].
This is apparently true to any pair of nibbles that are a XOR of 8 from the other (Toeplitz matrix characteristics)
And depending on the offset of the non identical nibbles – different parts of the key are uncovered.
PUTTING IT ALL TOGETHER
Two IP ID samples for which the IpFragmentIdIncrementTable cell is zero. (you don’t know this, but get enough samples, do the whole process and a clear winner will emerge)
Therefore
Identification = secret_dword ^ hash(ip_path)
The IP-Paths are identical but two nibbles, which are XOR 8 of each other
Therefore
Hash1 ^ hash2 = key[i]
And lastly, (because the secret_dword XORs itself out)
Sample1 ^ Sample2 = key[i]
This can be continued to get all the other key parts.
READING UNINITIALIZED KERNEL MEMORY
Since XORing two IP ID samples (with table values zero) yields a key part, which we know –
With one sample and a key part – we can calculate an expected IP ID for other IP Paths, if the table content for them was zero.
And comparing to an actual sample of the IP ID for that IP Path, if it’s greater than the expected value, the difference must be the cell content, Kernel data!
The results of a crude PoC:
SUMMARY OF THE ATTACK
- Generate/Acquire as many pairs of samples of fragmented IP packets sent on different IP paths
- The pairs must have the paths identical but one nibble, where the two samples would hold a values of XOR 8 from each other.
- XOR the IP IDs
- rank the outcomes. the one with most occurrences is a DWORD from the key.
- keep the IP IDs and IP PATHs that gave the correct outcome
- use those against other IP PATHs, where the relation is not a XOR of 8. Calculate the expected result (now that you have the key)
- the difference between the actual result and the expected is uninitialized kernel memory.
- break KASLR.
(For the advanced students: add logic that adjusts the outcomes to the fact that the IP IDs are only read in windows of 31 bits)
FINAL WORDS
a special thanks goes to @tom41sh from MSRC and the wise @ace__pace