Last year, after Orange dug into the RCE loophole in Microsoft Exchange, this year we will shift the focus to the study of IIS.
Today, we will introduce the attack of HashCollision 25 years ago.
In order to avoid it, Microsoft implemented a dynamic miscalculation algorithm and implemented it in IIS.
However, is there really no problem with this hash algorithm?
In this journey, Orange will bring it through reverse engineering.
After a deep study of the dynamic miscalculation algorithm, we achieved the attack of high CPU DOS and authentication bypass.
Let's welcome Orange to give a speech.
Hi, everyone.
I don't know how many times you have participated in HITCON this year.
I myself participated in HITCON for the 14th time this year, and this is my 10th HITCON speech.
This is a big milestone for me.
Thank you.
Okay, let's get back to the topic.
I am Orange.
This speech is called Let's Dance in the Cache.
It's a long speech.
This is also a speech I gave at Black Hat and DEFCON this year.
First of all, let me give you a hint.
If you have a very safe place, and this place is protected by a very long password, and you don't know the password, you will never be able to log in to this very safe website.
But with the IIS design, all the passwords here can be successfully logged in.
Huh?
Yes, I heard someone say huh.
That's right, it's huh.
This is a demo we are going to show today, and we will also tell you why.
Hi, everyone.
I am Orange.
I am currently the chief security researcher at DEFCON.
My job is to find the most serious loopholes and attacks in the world, and report them to the manufacturers before the bad guys take advantage of them.
I specialize in web security and application security.
As long as it's related to the application layer, whether it's binary, web, or cryptography, it's all part of my research.
I have been a speaker at many conferences.
For example, I gave a speech at Black Hat and DEFCON five times.
I also gave a speech at HITCON 10 times.
My research has also won some awards.
For example, I was the winner of the Hacker Oscar.
And I was also the winner of Pong to Wong.
This is our outline for today.
First, I will do an introduction.
I will talk about the concepts we will use today.
Next, I will talk about our research, the loopholes, and some suggestions.
First, the hash table.
The hash table is the most basic data structure in computer science.
This data structure is so basic that you can see it in some computer infrastructures.
You can see that it is often used in whether it is a homework system, a programming language, a database, or even a web server.
It is used to store data.
The hash table is especially suitable for storing data in the form of key and value.
It can be stored in the memory with very fast efficiency, whether it is searching, adding, or deleting.
Let me give you an example.
This is a programming language.
Programming languages often use the hash table data structure.
But you don't know it just because programming languages package the hash table data structure into a more high-level data structure.
For example, in Python, a list, a directory, or an object.
So if you are a programming designer, you must have used the hash table data structure.
As for what is the inner workings of the hash table, I believe that most of you here have never been taught about the university algorithm.
I believe that you are all good students.
So today, we won't go into the inner workings of the hash table in too much detail.
I will talk about hash floating attack.
I believe that it is the best way to show an attacker how to abuse or how to use a classic algorithm.
The concept of hash floating attack is to put all the records into the same bucket.
It allows the hash table to
become a single linked list.
For example, here on the left, there are many records designed by attackers.
In the hash table, there is a hash function in the middle.
This hash function will process your records and turn them into a number.
Then it will put this number into the corresponding empty bucket on the right.
So, for the first record, the result after the hash function is 4.
It will put it into the fourth bucket.
The second result is also 4.
At this time, because 4 is occupied by someone, it will link it with a linked list.
The third one is also 4.
The fourth one is also 4.
The fifth one is also 4.
It can produce a lot of records and put all the records into the index of 4.
At this time, the hash table will turn from a high-performance data structure into a single linked list.
So, you can make the complexity of the hash table
is always in the worst-case, which is N of O.
You can imagine if you add N to data, the complexity of the data is the square of N.
Everyone can imagine that the square of N must be a slow operation.
This is the essence of hash floating attack.
Let's go back to the topic.
First of all, the IIS of Microsoft likes the hash table very much.
As I said, the hash table is a very important data structure.
It is used in many places.
Of course, the IIS is the favorite web server of Microsoft.
So, it is reasonable to use a lot of hash tables.
The IIS uses the hash table to store a lot of things.
For example, the HTTP header, variables, cache, or setting files are stored by the hash table.
In the IIS of Microsoft, Microsoft designed two hash tables.
Well...
I forgot to say that the hash table is very important.
Microsoft designed the hash table algorithm from the very beginning .
In order to fit the structure of the software, or the content of the software, the hash table algorithm was designed by Microsoft.
It is also the most common hash table seen in IIS.
The first one is TreeHashTable.
This hash table is the most standard hash table you can see in your university textbook.
It is the most standard sample code hash table, TreeHashTable.
When it encounters a collision, it will use LinkList, the method we talked about before.
If the hash table is unhealthy, it will use Rehash to calculate everything.
The hash function, as I said, is how to convert a record into an index.
The hash function uses djbhash and lcg.
We will talk about this in detail later.
The second one is LKRHash.
LKRHash is a hash table designed by Microsoft in 1997.
It consists of three people.
One is Paul Eisen, and the other two are from the IIS team.
The name LKRHash is written by these three people.
Microsoft designed this hash table in 1997 .
Interestingly, they patented it.
So you can find this patent in the U.S.
Microsoft has a patent.
The hash table is designed to be used for multi-threading or multi-core.
The hash table can be used for multi-threading or multi-core.
The hash table can be used in Microsoft's various products.
The hash table is designed in a highly customized way.
When you use the hash table, you can define many functions to customize the hash table.
For example, you can customize the hash function, or how to compare the key when a collision occurs, or how to extract the key from a record.
All of these can be customized by software designers.
Here is an interesting thing.
You can see there are two developers from the IIS team.
I guess this is why we often see the hash table in IIS.
After a brief introduction, let's talk about our research.
What should I talk about?
OK.
Our research...
Let me see Xiaochao.
OK.
As I said, the two hash tables are designed and built by Microsoft.
As you know, Microsoft doesn't have open source software.
The two hash tables but they don't have open source software.
So I thought this could be an area that no one has explored.
It could allow us to find some interesting loopholes.
So, our research focuses on first, is there any problem with the hash table?
Is there any memory problem?
Is there any logic problem?
In terms of logic, I'd like to highlight a loophole called CV20063017.
It's a 15-year-old loophole.
There is a guy called Stephen Acer.
If you follow the social media, you can know that this guy is a super god.
He used to study PHP security until the end.
Then he studied iOS security and wrote a jailbreak.
This loophole is very interesting because it appears in the onSet function of PHP.
When it calculates the index, there are some problems with the type.
So you can use a numeric array to delete any element.
When I see this CV, I think this is the logic hole I'm looking for.
Yes, this is the logic hole I'm looking for.
Of course, we will also look at the complexity of the algorithm .
Although hash floating attack is a problem from 20 years ago, most of the simple lower-hanging fruit have been found by other people.
So in this part, we focus on some of its logic.
This is the first part we will look at, the implementation part.
The second is that we want to see if there are any problems with the use of this hash table .
Like I just said, LKR hash is actually a hash table that can be highly customized by the developer.
The developer can put any function related to hash in it.
So when I see this, I will think if there is a problem the user or the application put in.
For example, is the function he put in good?
Is his key logic right?
Or is it right when he chooses record?
There are a lot of questions in my mind.
So the use of hash table is also a part of our research.
So...
Because most of the use of hash table in IIS is related to cache.
So we will also understand the mechanism of cache.
This is an IIS architecture diagram.
When a request comes in, the bottom of Windows http.sys will handle the connection and assign it to the user.
The http.sys will check the IIS service and ask if anyone can handle the connection.
If not, the WANS called Windows Activation Service will read some settings and then launch a worker.
If you are a software developer or a network manager, you often see the W3WP.exe process.
This process will initialize a lot of components.
Then it will load the IIS defined in the settings and load the pre -loaded modules.
In the pre-loaded state, the IIS will load a lot of modules, such as authentication, redirection, cache, or even record.
Among these modules, these four modules are the IIS's cache provider.
For example, file cache module is related to file cache.
And...
token cache module is also related to token.
Cut the crap.
OK.
After loading these modules, it will enter the request lifecycle.
All these modules can subscribe to the lifecycle and handle the request sent by the user.
OK.
This is the request lifecycle.
All the modules can subscribe to the event of interest.
When the request reaches the event, an event will be sent.
Then the module can handle its own logic.
Of course, a module can also subscribe to some global events.
For example, there are two events called CacheCleanup and CacheOperation.
If a module subscribes to these two global events, it can perform some cache operations or cache transmission.
So the four global cache providers subscribe to these two events to achieve the function of So our hash table usage research focuses on the request lifecycle and the two cache operations.
The four global cache providers are also our goal.
Next, let's talk about the loopholes.
There are three loopholes.
I will introduce them one by one.
First of all, the first one is the HashFloatingAttack.
First of all, the two hash tables designed by Microsoft
both have HashFloatingAttack.
The difference is that TreeHashTable is already there.
But LKRHash only exists if the developer or the application has set a bad hash function.
So HashFloatingAttack only exists.
But having a loophole doesn't mean it can be used.
In addition to how to access the loophole and how to find the entry point, there are many difficulties when using it .
We found the URICacheModule.
The purpose of this URICacheModule is to cache the settings of each network.
As you know, reading the settings is a very expensive operation.
In order to speed it up, this URICacheModule speeds it up.
So this URICacheModule can be accessed by pre-setting.
And every network you visit on IIS will trigger a HashTable to search, add, or delete.
The most important thing is this module uses the cache storage using the TreeHashTable which is the HashTable of the pre-set vulnerable module.
So imagine a pre -set TreeHashTable is a very good attack point.
Here is a graph .
This graph is the I add 1000 data.
This is the time I use.
OK.
Because Microsoft doesn't have open source.
In order to make this graph, we have to do a lot of reverse engineering.
And we have to dynamically render the structure of the module.
Theoretically, this limit is when I add 100,000 data and there is a collision.
The blue line is when I add 100,000 data and there is no collision.
Obviously, you can see the huge difference.
When I add 100,000 data, I use almost 250 seconds.
But if it is the same 100,000 data and it is random, I don't even need to spend a second.
But there is a problem.
The complexity of the hash table is O of N.
Theoretically, it should be a standard linear upward situation.
But why there is a small jump between 35 ,000 data and 75,000 data?
There is a small jump.
OK .
The answer is because I mentioned Rehash.
In the hash table algorithm, in the hash table, if I find that my hash table is unhealthy, for example, when there is too much data, I will do something called Rehash.
Of course, Microsoft has done the same thing.
This is part of Microsoft's source code for the newly added data.
You can see that after the update, there is a function called RehashTableIfNeeded.
This is to determine how many my hash table has.
If these records are greater than a certain threshold, greater than a certain value, then I will change my hash table to a bigger one.
After changing the hash table, what about the original record?
The original record is because my hash table is bigger and has more data.
The original index will change.
So I have to re -calculate all my records and put them in the new hash table.
You can imagine that this is a very expensive and time-consuming operation.
This is also the reason why there are a lot of changes in RehashTable.
Well, we know that the thing just now seems to be playable.
But there are still some problems that need to be solved.
For example, how do we control our cache key?
How do we control our records so that it can collision?
The second question is, is the difficulty of collision simple or easy?
First of all, when you visit a URL, for example, http://server-foo.bar, in fact, this module will calculate a cache key.
This cache key looks like the following.
The only thing you can control is the end part of this cache key.
The end part is the path of your network.
The path will reflect the end part of this cache key.
So you can partially control this cache key.
OK.
The second point is, is the hash function collidable?
Is it easy to collision?
This is the hash function of the treeHashTable.
You can see that it adds each byte of a cache key to 101.
to 101.
You can see that it is a very simple operation.
This hash function is actually a...
Sorry.
So is this hash function a good hash function?
The answer is no.
This study was done in 28C3, a German CCC.
Someone said that this hash function is not a good hash function.
They came up with a good way to attack it.
This hash function is actually a variable of djbHash.
The djb x33a is actually a person's name.
This person is actually the name of a cryptographer in the last layer .
He designed this hash function 30 or 40 years ago.
He should not be listening to this lecture.
Right.
This hash function has been proved that it can easily do collision.
The method of collision is called Equivalent Substring.
Let's say you find two hash functions are the same.
For example, here is ps and q2.
No matter what you add in front of these two or in the back, the hash of the new result must be the same.
For example, you add a in the back of ps and q2.
The hash of psA and q2A must be the same.
After you know this feature, you can...
After you know this feature, if you have two hash functions that are the same, you can combine infinite possibilities.
For example, ps, ps, q2, q2, ps, q2, q2.
The hash of these four will be the same.
This is called Equivalent Substring.
It was first proposed by the two people on 28C3.
So, after we know this feature, it is very easy to attack it.
We just need to find a few groups whose hash is the same.
Next, we will arrange them.
After that, all the URLs here will have the same hash.
They will collide and form a linked list This looks great.
But this attack has a very serious drawback.
It is too slow.
We just said that we need to have at least 35,000 We need at least 35,000 to see a significant increase.
But now, every URL, every visit, every HTTP access can only add a piece of information.
Every visit can only add a piece of information.
This is too slow.
What's more, in order to prevent you from doing this hash floating attack, IIS set a scavenger.
In Chinese, this scavenger is called Qingdaofu.
Its function is to delete records that usually no one visits.
So, I need to reach my target 35,000 times This attack is very slow.
Very slow.
These two drawbacks make our attack less practical.
So, what should we do?
We need to take a closer look at IIS.
When we were looking at IIS, we found an interesting thing.
In IIS, if it sees that your key has a diagonal line in the middle, it will treat every diagonal line as a new record.
It will treat every diagonal line as a new record.
It may be hard to understand.
You can look at this example.
We thought this URL would only do one search.
Search is to prevent repeated records.
If there are no repeated records, it will do an insert.
But in fact, in IIS, it will treat every diagonal line as a new result.
A new result.
What's more, in this new result, the paid-in record will be a neural record.
As I said, this neural record is very friendly.
It won't delete all records at once.
It will delete them slowly.
So...
This seems to be a great breakthrough for us.
The remaining question is how to use the method of equivalent substring we just learned to create an equation so that all the paths here can be collision.
Because the situation here is different from the situation at the beginning.
How do we use the method of equivalent substring to make all the equations here equal?
This may be a little difficult.
But if you make all the results equal to 0, this equation will be equivalent.
Because 0 times 0 is still 0.
After multiplying by 0, adding 0 is still 0.
So we just need to calculate some zero hash.
Then we can match this equation.
OK.
So we can make a little change to the attack rate at least 10 times higher.
Just make a little change and it can be 10 times higher.
OK.
Because this loophole affected the Windows Server we got a lot of bonus.
The result of this loophole is almost 30 requests per second can make an 8-core 32GB IIS can never be visited by others.
30 requests per second is not an exaggerated number.
Because the current Windows Server can handle thousands of requests at the same time.
So 30 requests per second is very easy.
OK.
Do we have a demo time?
Let's see.
36 minutes have passed.
OK.
I think we don't have a demo time.
Here is a web page.
You can see the web page on the video later.
Let's see the demo.
OK.
The second loophole is IIS's cache poisoning attack.
OK.
In IIS there is a cache function to cache HTTP response.
The most common response is static files.
For example, pictures, CSS, or JavaScript.
These things are cached by the kernel.
Another one is dynamic response.
For example, if I want to cache what should I do?
IIS provides a module called HTTP Cache Module to let you do this.
What are the benefits of doing this?
For example, you can cache product information or ad information in the online shop .
Then your visits won't be accessed to the database or file system.
This cache is done with LKR cache.
OK.
How to set it up?
In IIS's settings there is a function called Output Caching.
It can set the behavior I just mentioned.
I made a small setting here.
This setting is for all the HTTP visits I made.
Then I cache the ID of this parameter.
Where is the problem?
The problem is the cache module I just mentioned has a problem with the parser of the query string.
It has a problem.
If it has a problem, if its behavior is different from IIS's behavior of the query string parser, then it may cause IIS to cache the wrong result.
To cache the wrong result.
So in conclusion,
a very simple HTTP parameter pollution can solve this problem.
I just mentioned Output Caching.
This module when it sees the query string, if it encounters two identical keys, then it will only take the first one as its cache key.
But if the IIS at the back sees two identical keys, it will put them together.
The inconsistency of this behavior will cause IIS to cache the wrong result.
So let's take a simple example.
Here is a very simple SBX patch.
It will take your name from the ID and print it out.
At this time, the attacker can use the above UIL, ID equals orange and ID equals and you got poisoned.
At this time, this module will only take orange as its cache key and take and cache the result of this page.
But if SB.NET sees two identical keys, it will put them together.
So the result is when a user visits the original page, he will get the wrong result.
This is the IIS cache poisoning attack.
The last one is IIS authentication bypass.
Let's go back to the beginning.
For this, you must have this password to log in to this very sensitive and secret area.
In the IIS design, almost all the passwords can be successfully logged in.
Why is that?
There must be a lot of questions here.
For example, what is this root cause?
And how do I calculate those passwords?
Or you are thinking this must be some hcache.
It must be in a very special situation to be affected.
You must have a lot of questions.
The reason is in Windows, logging in is a very expensive operation.
In order to speed up the process, IIS wants to cache the result of the login.
Next time, when the same user logs in, I can get the cached result and I don't need to log in again.
So IIS wants to cache the result of Windows security token successfully.
But after caching, it can't be cached forever.
So it has a channel to cache the result every 15 minutes.
This cache...
10 minutes left...
The cached result is cached with LKR hash.
LKR cache allows the application to set its own functions related to hash table.
You can see the four in the middle are the functions set by the token cache manager.
Let's see how the token cache manager calculates the hash.
It calculates the hash by calculating the user name with djb and the password with djb and xor them into a hash.
This is how the token cache manager calculates the hash.
As for when a collision occurs, the token cache manager needs to retrieve the data.
How does it know which data is correct and which data is not?
The next function is called equalKeys.
It compares which data when a collision occurs.
It compares the log-count of the two records.
If they are the same, it compares the user name of the two records .
If the user name is the same, it compares the user name again.
You may wonder why it compares the user name twice.
I guess the purpose of IIS is to compare passwords.
But the developer forgot to change the variable name when copying the password.
So this is a classic mistake.
The reason for the mistake is when I calculate the hash, I have the user name and the password at the same time.
But when I compare, I only have the user name.
So this causes a problem.
You can use a random password to use the log-out result of another user.
You can use the log-out result of another user.
Of course, there are some prerequisites.
For example, the hash I mentioned is a 32-bit integer.
So the success rate of your random password is only 1 out of 4.2 billion.
Another limitation is when you use the log-out result of another user, there must be a log-out result before you log -in .
As I said, the log-out result of another user is only 1 out of 4.2 billion, so you must log-in every 15 minutes.
These two things are very difficult to use.
So we came up with some ways to make this attack more useful.
We came up with three ways.
The first one is to increase the success rate of collision.
The second one is a loophole that requires user interaction is very embarrassing.
So we have to find a way to make our use without user interaction.
We have to regain our control.
The third one is the tiny meter of 15 minutes is a very annoying limitation.
We found a way to make our use without limitation and to make the log-out result cache in the memory forever.
So we don't have the limitation of 15 minutes.
The first one is how to increase the success rate.
As I said, the hash is a 32-bit integer.
This integer has 4.42 billion possibilities.
This number is very hard to find.
Very hard to find.
The optimization we found is the LKR hash.
In order to make the hash result more messy, after the hash result is calculated, it uses an LCG to make the result more messy.
Because of the LKR hash, we can increase the success rate.
The reason is that the LKR hash is not a one-to-one mapping under the 32-bit integer.
So there must be some results that never show up.
So we can make a dictionary to eliminate the results that never show up.
After the calculation, we found that at least 13% results never show up.
So we can reduce 13% key space and increase the 13% success rate.
This is the first part.
The second part is to get the control.
We found that IIS has a preset function called connect us.
This is often used in virtual hosting or shared hosting.
Because it needs every customer to run an independent IIS process.
So it will set an independent account password and let IIS log in.
Under this setting, IIS will automatically log in with the account password when it starts the process.
So through this feature, we basically don't have to wait for a user to log in before we can attack.
We can use the customer log in IIS will automatically log in the customer's account password and we can crash the log in result.
In this situation, we don't need user interaction.
The last one.
We did a test.
Windows can handle 1800 log in
operations.
You can imagine every time we log in, it's not expensive for the attacker.
So if you run 1800 logs in a day, the success rate is 4.2%.
4.2% is higher than the SSR is higher.
Of course, you can run longer.
For example, if you run for 5 days, the success rate is 20.
If you run for 12 days, the success rate is 50.
If you run for 24 days, the success rate is 100%.
We successfully created a password after 5 days.
We can log in the long password.
The last one.
How do we defeat the time window?
Our idea is simple.
In today's large software design, there should be some design patterns.
The pattern is...
Because the software is complicated, there may be a service to check the health of each service regularly.
Or there may be a background cron-tab, cron-dropper.
It will periodically run some internal API.
The situation we imagine is like this.
If health check and cron-dropper run some internal API, they will have an account password.
And every time the cron-tab is less than 15 minutes, it means all...
all...
this token will always be cached in the memory.
Because it is less than 15 minutes, it will have an account password when it is cron -dropping .
You may think my idea is too ideal.
Is there a design like this?
Yes, there is.
Let's talk about Microsoft Exchange Server again.
In Exchange Server, there is a service called Active Monitoring.
It is a pre-opened service.
Its function is to check the health of all services.
It will use an account password to cron-drop OWA and ActiveSync.
Use an account password to cron-drop every 10 minutes.
All the conditions here are perfectly in line with what I just said.
It will always store the result in the memory.
We can try ActiveSync and once we get a set of passwords, we can use this set of passwords to cron-drop OWA.
Then we can check the mailbox of OWA.
This is quite suitable to be used in post-cron-dropping scenarios.
For example, if you don't have an account password, you can use this mailbox to do phishing or to cron-drop some necessary RCEs, to make a post-auth RCE into a pre-auth RCE.
Time is up.
This is my last CAS.
The last one is the mitigation part.
For the hash table design, I suggest to use some pseudorandom functions.
For example, SIP hash and hybrid hash.
By the way, this SIP hash was also proposed by DJD.
As for the design with cache, all the questions I talked about today are related to inconsistency.
Whether it is cache poisoning or authentication bypass, we still need to pay attention to consistency.
The last one is hash floating attack.
Because it is a by -design attack.
There have been many mitigations in history.
For example, limiting the input size.
Or when I calculate the hash, I will introduce a random seed to make it more messy.
But these things actually have a solution .
So I can only say that you can only learn more about the past historical attacks to prevent it.
Of course , there are also some future work.
For example , I came up with some more interesting things.
There was a technique called Timeless Timing Attack last year.
Can we use it to do something more advanced to make our success rate higher?
Because I'm lazy.
If you are interested in the topic here, please skip it.
Okay, this is the end of my speech.
Thank you all for being here today.
Thank you all.
Okay, because of the time, we have an open question.
Anyone want to ask?
There is a question on the line.
But you can ask it on the spot.
Okay, if there is no question, we will give it to the people on the line.
I can look at it directly.
Okay, someone asked how to get the Microsoft hash function code.
Most of them are obtained through reverse engineering.
But Microsoft has XP source code.
You can find it on GitHub.
You can refer to it.
Another one is after finding the bug, did Microsoft give you a bonus?
There is a $30,000 bonus for hash floating attack.
Will the bonus be the right sound of this picture?
I don't think so.
I am mainly based on interest and high influence.
I believe you can ask the last one, he is talking about bug bounty.
You can also ask him.
Okay, time is up.
We thank Orange again.
Thank you.