Protecting against Pointer Subterfuge (Redux)

In a prior post, "Protecting against Pointer Subterfuge (Kinda!)" I described the algorithm we used to encode and decode long-lived pointers in memory to make them harder to exploit after a buffer overrun.

A couple of days after the post, I received an email from Steven Alexander about some research ("Defeating compiler-level buffer overflow protection") he had performed on the entropy used to encode the pointers, and pointed out that we may have a weakness – there was a reasonable chance the upper byte of the 32-bit random number could be zero. Steven sent me a link to his paper, and I suggested to a couple of kernel developers here that we tweak the algorithm. Based on the feedback from Steven, we have now changed the implementation in Windows Vista.

The entropy for the cookie was derived from:

• The higher portion of the system tick count (100 nano-second tick count since Jan 01, 1601) ^
• The lower portion the system tick count ^
• The interrupt time (number of ticks during interrupts) ^
• The number of system calls since system boot.

The entropy for the cookie is now derived from:

• The higher portion of the system tick count (100 nano-second tick count since Jan 01, 1601) ^
• The lower portion the system tick count ^
• The interrupt time (number of ticks during interrupts) ^
• The number of system calls since system boot ^
• The (ULONG)rdtsc CPU value ^
• The memory manager page fault count

This result is then rotated right on encode using Cookie % (sizeof (ULONG_PTR) * 8). In psuedocode on a 32-bit CPU, encoding looks like this:

Ptr_enc = (Ptr_clear ^ Cookie) >>> (Cookie % 32)

The reason for the rotation is to make it harder to target partial pointer overwrites, because target bits are in an unknown position in the encoded pointer.

Comments

• Anonymous
  August 22, 2006
  The comment has been removed
• Anonymous
  August 25, 2006
  This scheme is used for general pointer protection.  If it is used on saved instruction pointers (pehaps Mike can clarify but as far as I know it isn't), it would be in addition to any canary-based stack protection and the one-byte overflow scenario would probably not occur.  The variable rotation does increase security because it decreases the predictability with which an attacker can manipulate a program.  In cases where only a single byte overwrite is possible, it does allow an attacker more flexibility (he has a chance of modifying a series of bits at some random point in the upper three bytes instead of being limited to the lowest byte).  In the general case, it prevents an attacker from predictably overwriting only the bytes that he wants to modify.  I think the rotation is a good thing.
• Anonymous
  August 31, 2006
  I want to cover both comments from PaX Team and Steven.
  
  First, I don't see how this will allow "return to to [sic] many more addresses" a one-byte overwrite is still a one-byte overwrite! Also, an attacker's 'sploit would have to survive the XOR operation post rotation.
  
  This is for long-lived pointers, which may of course point to code. But as Steven says, this is also just part of a layered defense, we have the /GS stuff in there as well as ASLR, heap randomization and stack randomization, etc.