Let's Dance in the Cache - Destabilizing Hash Table on Microsoft IIS

The presentation discusses the vulnerabilities in Microsoft Exchange Server's hash table and cache, and proposes enhancements to exploit them.

• Microsoft Exchange Server's hash table is vulnerable to hash flooding attack
• URI cache module is a good target for exploitation
• The implementation uses an lcg to scramble the hash result, which is weak
• The attack is slow and impractical due to cash scavenger and the need to send a large number of requests
• Enhancements proposed include pre-computing a dictionary to reduce key space, regenerating the token to reuse customer identity, and exploiting the token caching feature to defeat the time window

The presentation shows that the hash table implementation in Microsoft Exchange Server is vulnerable to hash flooding attack, and that the URI cache module is a good target for exploitation. The implementation uses an lcg to scramble the hash result, which is weak and can be exploited by constructing equivalent substrings. However, the attack is slow and impractical due to cash scavenger and the need to send a large number of requests. To overcome these obstacles, the presentation proposes enhancements such as pre-computing a dictionary to reduce key space, regenerating the token to reuse customer identity, and exploiting the token caching feature to defeat the time window.

Hash Table, as the most fundamental Data Structure in Computer Science, is extensively applied in Software Architecture to store data in an associative manner. However, its architecture makes it prone to Collision Attacks. To deal with this problem, 25 years ago, Microsoft designed its own Dynamic Hashing algorithm and applied it everywhere in IIS, the Web Server from Microsoft, to serve various data from HTTP Stack. As Hash Table is everywhere, isn't the design from Microsoft worth scrutinizing?We dive into IIS internals through months of Reverse-Engineering efforts to examine both the Hash Table implementation and the use of Hash Table algorithms. Several types of attacks are proposed and uncovered in our research, including (1) A specially designed Zero-Hash Flooding Attack against Microsoft's self-implemented algorithm. (2) A Cache Poisoning Attack based on the inconsistency between Hash-Keys. (3) An unusual Authentication Bypass based on a hash collision.By understanding this talk, the audience won't be surprised why we can destabilize the Hash Table easily. The audience will also learn how we explore the IIS internals and will be surprised by our results. These results could not only make a default installed IIS Server hang with 100% CPU but also modify arbitrary HTTP responses through crafted HTTP request. Moreover, we'll demonstrate how we bypass the authentication requirement with a single, crafted password by colliding the identity cache!