Hey there token, long time no see! (Did you do something with your hair?)


Consider a system where you have a lot of secured objects, and suppose further that checking whether a user has access to an object is a slow operation. This is not as rare as you might think: Even though a single access check against a security descriptor with a small number of ACEs might be fast, you can have objects with complicated security descriptors or (more likely) users who belong to hundreds or thousands of security groups. Since checking whether a security descriptor grants access to a token is potentially¹ O(nm) in the number of ACEs in the security descriptor and the number of groups the user belongs to (since each ACE needs to be checked to see if it matches each group), even a check against a small security descriptor can multiply out to a slow operation when the user belongs to thousands of groups.

Suppose your profiling shows that you spend a lot of time checking tokens against security descriptors. How can you create a cache of access/no-access results so you can short-circuit the expensive security check when a user requests access to an object? (And obviously, you can't have any false positives or false negatives. Security is at stake here!)

First, let's look at things that don't solve the problem: One option is to query the SID from the token and cache the access/no-access result with the SID. This option is flawed because between the two checks, the user's group membership may have changed. For example, suppose object X is accessible to members of Group G. Bob starts out as a member of Group G, asks you for access, and you grant it and cache the fact that Bob has access to object X. Later that day, Bob's membership in Group G is revoked, and when Bob logs on the next day, his token won't include Group G. If you had merely cached Bob's SID, you would have seen the entry in the cache and said, "Welcome back, Bob. Have fun with object X!" Bob then rubs his hands together and mutters Excellent! and starts making unauthorized changes to object X.

Now, Bob's membership in Group G might have been revoked at Bob's request. Reducing one's privileges is a common safety measure. For example, Bob might remove his membership in the Administrators group so he won't accidentally delete an important file. Low Rights Internet Explorer intentionally removes a slew of privileges from its token so that the scope of damage of an attack from a malicious site is limited.

Okay, so how can we recognize that the Bob that comes back has different group membership from the Bob that visited us the first time? You can do this with the help of the TOKEN_STATISTICS structure. This structure contains a number of locally-unique values which can be used to recognize and correlate tokens. A locally-unique value is a value that is unique on the local machine until the operating system is shut down or restarted. You request the statistics for a token by calling GetTokenInformation function, passing TokenStatistics as the information class.

The AuthenticationId is known in some places as the LogonId because it is assigned to the logon session that the access token represents. There can be many tokens representing a single logon session, so that won't work for our purposes.

The TokenId is a little closer. It is a locally-unique value assigned to a token when it is created. This value remains attached to that token until it is destroyed. This is closer, but still not perfect, because Bob can enable or disable privileges, and that doesn't change the token, but it sure changes the result of a security check!

The ModifiedId is a value which is updated each time a token is modified. Therefore, when you want to cache that This particular token has access to this security descriptor, you should use the ModifiedId as the key. (Remember, locally-unique values are good only until the system shuts down or restarts, so don't cache them across reboots!)

Now, a cache with a bad policy is another name for a memory leak, so be careful how much and how long you cache the results of previous security checks. You don't want somebody who goes into a loop alternatively calling AdjustTokenPrivileges and your function to cause your cache to consume all the memory in the system. (Each call to AdjustTokenPrivileges updates the ModifiedId, which causes your code to create a new cache entry.)

Now, you might decide to use as your lookup key the ModifiedId and some unique identifier associated with the object. This means that if Bob accesses 500 objects, you have 500 cache entries saying Bob has access to object 1 through Bob has access to object 500. (And you have to remembering to purge all cached results for an object if the object's security descriptor changes.)

It turns out you can do better.

Even though you may have millions of objects, you probably don't have millions of security descriptors. For example, consider your hard drive: Most of the files on that hard drive use one of just a handful of security descriptors. In particular, it's nearly always the case that all files in a directory share the same security descriptor, because they start out with the security descriptor inherited from the directory, and most people don't bother customizing it. Even if your hard drive is on a server with hundreds of users connecting and creating files, you will probably only have a few thousand unique security descriptors.

A better cache key would be the ModifiedId of the token being checked and the self-relative security descriptor that the token was checked against. If Bob accesses 500 objects, there will probably be only around five unique security descriptors. That's only five cache entries for Bob. It also saves you the trouble of remember to purge the cache when an object's security descriptor changes, since a new security descriptor changes one of the lookup keys, so it gets a new cache entry. Since security descriptors tend to be shared among many objects, you get two bonus benefits: The old security descriptor is probably still being used by some other object, so you may as well leave it in the cache and let it age out naturally. And second, there's a good chance the new security descriptor is already in your cache because it's probably already being used by some other object.

¹I use the word potentially because Windows Vista introduced an optimization which preprocesses the token to reduce the complexity of the access check operation. In practice, the access check is linear in the number of ACEs in the security descriptor.

Bonus chatter: Note that even though Bob can remove his membership in a group, the system still knows that he's just pretending. This is important, because the security descriptor might contain a Deny ACE for people on Project Nosebleed. Even if Bob removes the Nosebleed group membership from his token in an attempt to get around the Deny ACE, the operating system won't be fooled: "Nice try, Bob. I know it's still you."

Sponsorship message: I'd like to thank my pals over in the security team for reviewing this article and making suggestions and corrections. This article is sponsored by the AuthzAccessCheck function, which supports caching the results of an access check.

Comments (10)
  1. hagenp says:

    Thank you, Raymond. Excellent reading material, as always.

  2. ex-DonH says:

    To be pedantic, though, you should note that shortcircuiting access checks can also play havoc with SACL based auditing. You keep referring to "the ACEs in the security descriptor", but you're really referring to "the ACEs in the DACL in the security descriptor", and you're caching the results of that comparison. You're ignoring the ACEs in the SACL in the security descriptor and the fact that you can't cache those comparisons, because each evaluation may result in an audit entry. If an attacker is cruising around in your file system checking for access to your files you don't want to know just that he got write access to a file (and potentially hundreds more after that), but rather which files he got access to.

    [Good point. You can cache AccessCheck but not AccessCheckAndAuditAlarm. (Well, you can cache AccessCheckAndAuditAlarm if there is no SACL, and in practice, most ACLs have no SACL.) -Raymond]
  3. Gabe says:

    ex-DonH: When you cache whether access was granted, can't you also cache whether an audit entry has to be generated?

  4. Krunch says:

    potentially¹ O(nm)

    So, technically it always O(nm).

    </nitpicking>

  5. configurator says:

    @Krunch

    "In practice, the access check is linear in the number of ACEs in the security descriptor"

  6. Neil says:

    Of course, some operating systems don't require you to wait for Bob to log on again before noticing that he's no longer a member of group G.

  7. @DavidJuddDove says:

    Of course, some operating systems also don't support the concept of nested security groups.  I'm not a math geek, but recursing through nested groups is not something that you want to do on a regular basis because of the performance issues mentioned at the start of the article.  Therefore, the computation of the TokenGroups attribute occurs only at logon. (Written by someone who once increased logon script processing time from 2-5 seconds up to 4+ minutes by introducing a recursive-nested-groups-lookup function).

    [You also don't want to hit the domain controller each time you want to make a security check. (What if the network is down? Do you just say "ACCESS DENIED" to all requests to play it safe?) -Raymond]
  8. 640k says:

    To evade the security, pull the ethernet cable if you have been ousted from AD groups.

    [Noting of course that lets you evade the security only on the local machine. -Raymond]
  9. Boris says:

    Why does this sound like an answer to an MS interview question? (well, it's similar enough to what I was asked and I had no idea how to answer it. That's probably one of the reasons I didn't get the job)

  10. token says:

    [Hey there token, long time no see! (Did you do something with your hair?)]

    Thanks for noticing!  It's great to be back. I'd tell you all about what I was up to and what I'm going to be working on, but you no longer have access rights.

    Sorry.

Comments are closed.

Skip to main content