DEF CON 30 - Orange Tsai - Let's Dance in the Cache - Destabilizing Hash Table on Microsoft IIS

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!