welcome to the five o'clock track three unfortunately orange sai cannot be here today
however we are going to try to stream uh i'm sorry play his presentation for you guys
all right enjoy hi sorry i couldn't be on the stage because of the issue of visa
i hope one day we can make fast to fast in vegas
about 10 years ago i failed my algorithm course at university but i'm not here to
talk about the hash table this is a big achievement for me an orange and today my
topic is let's dance in the cache this tab rising hash table on microsoft iis
before
the talk i would like to give you a showcase if there is a super secret area which is protected
by a super secure password you cannot look in only if you know this long password
however under the design of iis
all of these passwords are valid and can log into the system
so if you have any questions please feel free to ask them in the chat and i will try to answer
all of your questions and answer them in the next session amazing right i guess you might have
several questions in your mind this is one of the attacks i will present today
and you will learn the details later
hi i'm orange and now the principal security researcher at defcore i am a zero day researcher and focusing on web and application security
my job is to discover the most severe bugs and the attack service that can impact the world
ahead of the bad guys my research has also received several awards such as the best server sidebot of
the pounding awards and the champion of the pound to own if you are interested welcome to follow my
twitter or chat with me in the chat if you have any questions please let me know in the chat and i will try to answer all of your questions
and i will try to answer all of your questions
this is the online today first we will introduce several essential concepts those concepts are
important to let you into microsoft iis internals and our topic today after having a good understanding
of iis internal and the cache mechanism we will elaborate on our research
we will make three different types of tasks followed by three different types of vulnerabilities
also we will demonstrate how we apply the attacks to microsoft exchange server as the showcase
of course we will provide mitigations recommendations and future works to those
components
so first what is the hash table
HatchTable is the most fundamental data structure in computer science, and its purpose is to
store data.
No matter what the data is, HatchTable can hold the data in memory very well.
HatchTable is especially good at handling the key-value pair and can operate data with
a high performance.
Due to those benefits, HatchTable is used extensively in computer infrastructures such
as the operating system, programming language, database, or web server.
Here is an example of the HatchTable usage in programming language.
Programming language uses the HatchTable widely.
However, you don't know because they wrap the HatchTable into a more high-level structure
such as the array, dictionary, or object.
So if you are a developer, you must have used HatchTable.
As the internal, I assume that everyone here is a good student at university.
So I skip the HatchTable internal.
Fyi first, what is the hash-folding attack?
Also, we are not going to talk about this attack only.
We still give it a slot because I believe that the hash-folding attack is the best
test to learn the mindset of how an attacker abuses the HatchTable.
HatchTable has a loop, so it focus on a thing or two.
The hash-folding attack does not have an object.
The idea of hash-folding attack with a hash number is one of the most important things in
hack is to drag all the records into the same bucket.
Since the hash algorithm is public,
an attacker can predict its hash and make all records fall
into the same bucket.
At the time, the attacker degenerate
the hash table, which can store a number of records
into a single linked list.
For example, the attacker has clapped several malicious
records on the left side.
The hash function in the middle will process and convert
the record into an index.
The first record is converted to the index 4
and put into the corresponding bucket.
The second is also processed.
Put into the same bucket.
The third, the fourth, the fifth.
And the attacker can drop all records into the same bucket.
And the table now becomes a single linked list.
So the hash floating attack can make the table always sit on,
on the worst case.
That means for inserting n records,
the time complexity comes to n squared.
We should all agree that n squared
is in a terrible performance.
OK, with a good understanding of the hash table,
let's discuss the relationship between the hash table and IIS.
First, IIS loves hash table.
As a well-known and only web server in Windows,
IIS uses the hash table extensively in its architecture
to store information such as HTTP header, server variables,
configuration, and cache.
Due to the massive use of this data structure,
Microsoft has designed its own hash table implementation
from a very early stage.
The following two are older implementations
that will be used in IIS.
One is called tree hash table,
and the other is called LKR hash table.
The tree hash table should be the most common,
like the simple code in your textbook.
It uses the linked list to resolve the collision
and rehash the table when it's in an unhealthy state.
The rehash is a series of rebuilding processes.
It first enlarges the table, recalculates all records,
and reposition them to their new index.
As for what hash function is used,
we will have a few examples.
We will talk about this in future discussion later.
The other table is the LKR hash,
an implementation that aims to build a scalable
and high concurrent hash table
under the multi-threading and multi-core environment.
The name LKR is an acronym for the name of the creators.
This implementation was also patented by Microsoft in 1999.
The LKR hash is a successor of linear hashing,
which has used another better algorithm
to resolve the expensive rehash to enhance the performance.
The creators put a lot of effort to make this implementation
portable, flexible, and usable.
The application can define its own table-related hash table.
The hash table can be used to create functions
to adapt to multiple products across Microsoft.
It's interesting to note that part of the creators
are also the IIS developer,
which should be the reason why we find
lots of this implementation in IIS.
Now we have a complete understanding of the hash table.
It's time to go deep into our discussion.
In this section, we will show the IIS internals
and define the scope we really cared about.
We will first explain our mindset and idea to uncover bugs.
We are mainly focusing on the hash table implementation
and its usage.
Since most of the hash tables used in IIS are cache-related,
we also study and look into its mechanism.
Because Microsoft has designed its own hash table
without open source,
the implementation should be an export area
to discover bugs.
So in this context,
we hunt not only for memory corruption,
but also logic bugs.
Here I would like to highlight the bug CVE-2006-3017.
It's a logic bug in the unset function of the PHP.
The hash table implementation didn't distinguish
the key type of an array
so that an attacker can delete arbitrary elements
with an index number.
When I saw this bug,
it amazed me,
and I believe this is just the bug I'm looking for.
Of course, we also look for the algorithm complexity problems
such as the hash folding attack.
However, since it's already a 20-year-old attack,
most of the low-hanging fruit should be disappeared.
So in this context,
we put more effort into the implementation
As for the usage,
we mentioned that the LKR hash
is designed to be portable, flexible,
and easy to use algorithm
that can be applied to any situation.
The convention requires the application
to configure its own table-related function
during initialization.
This kind of extensibility
gives us more opportunities to uncover bugs.
When I saw this,
I was curious that
is the particulars function good?
Is the key calculation good?
Or how does the function select the correct record
when a collision happens?
These types of questions all interested me.
So in this context,
we care more about the relationship
between the record,
the key,
and the function.
When an HTTP request is coming,
the kernel http.sys
will first handle the connection
and dispatch the request.
The kernel checks
if there is an active IIS worker.
If not,
it knocks the IIS service
to spawn a new process.
The WAS Windows activation service
first reads the configuration
to note several specific caches
for the process initialization
and spawn the worker process.
Several IIS components are loaded here.
The worker then loads the modules
which are defined in the configuration.
IIS by default
loads several modules
for different purposes
such as the compression,
redirection,
authentication,
and cache.
Among all modules,
the following four
are the global cache providers
to manage the cache between modules.
Each module is responsible
for handling a different cache,
such as the cache for a static file,
the cache for configuration,
and the cache for Windows token.
Once the modules are loaded,
the worker enters the code
and enters the request lifecycle.
The lifecycle is an event loop
that processes all the notifications
from the request.
There are several events in a lifecycle.
A module can subscribe
to its interesting events
to complete its logic.
There are also global events
that a module can subscribe to.
For example,
the cache provider subscribes
to the event cache cleanup
and the cache operation
to manage the cache between modules.
So our research is not only focusing
on the cache between the request lifecycle,
but also the global cache providers,
especially those four,
our golden targets.
The following section is about
our research and the bugs.
In this section,
we will first elaborate on our idea
and the direction we are trying to find bugs.
We will attach three different types
of vulnerabilities
to prove our idea works.
Our bugs include a hash-folding DOS,
a cache poisoning,
and authentication bypass.
We will also talk about
the exploitation of
how we maximize the severity
to make these bugs impactful.
Of course,
a real-world authentication bypass
on Microsoft Exchange Server
will be detailed and demonstrated.
So let's get started.
The first case we would like to share
is the hash-folding DOS.
First,
we would like to give you a spoiler
that all hash tables
implemented by Microsoft
are affected by hash-folding attack.
The tree hash table is vulnerable by default,
and the LKR hash is vulnerable
only if a pooled head
function is configured.
However,
vulnerable is not equal to exploitable.
Besides finding the entrance point,
we still have several obstacles
to overcome.
We find that URI cache module
seems to be a good target.
The purpose of this module
is to cache configuration for URLs.
Because read configuration is costly,
so cache is the best strategy.
In this module,
every HTTP access triggers
the cache operation.
And the most important thing is that
the module uses this tree hash table
as its cache storage.
Well,
an accessible by default tree hash table
sounds good to us.
This is the time chart
of every thousand new records
in tree hash table.
Because it's not open-sourced,
we must reverse the structure
and code the table dynamically
to get the data set.
The line in blue
is the time of inserting
random records.
And the line in orange
is the records with collisions.
You should be able to figure out
there is a huge difference
between the two lines.
However,
the jitters along
35,000 and 75,000 are weird.
What's the jitter?
Theoretically,
the line's growth in orange
should be in linear time.
So,
what actually makes the time
increase unsmoothly?
The answer is re-hash.
This is the part
of the insert operation.
The implementation first
traverses the linked list
to ensure no duplicates
and do its internal job.
However,
after the internal add operation,
there is a call
to the function re-hash table
if needed.
The function checks
the number of records
and re-hash the table
if the number is greater
than two times of the threshold.
The threshold is selected
from a list of prime numbers.
And once re-hashed,
the function enlarges the table
by the next prime number
and remaps all records
to their corresponding bucket.
This is a huge
and expensive operation.
And that's the reason
why the chart
increased unsmoothly.
To exploit that,
there are still several questions
to be solved.
For example,
how much of the cache key
we can control?
Or how to construct
the collision panel?
There are several elements
in a cache key.
And the only element
we can control
is the URL path,
which reflected at the end
of the cache key.
The implementation
will first convert
all the text to uppercase
and send the key
to the hash function.
The hash function
simply multiplies
each byte of the cache key
by 101
and sums them up.
The function
also uses an lcg
to scramble the result.
However,
is this hash function good?
This is the answer
from Alec and Zerri
in their awesome talk
at 28C Street.
This multiplies
the add method
is a variant
of bzbhash.
And this algorithm
has been proven
that collatable
by equivalent substrings.
When two keys
have the same hash
such as the ps
and q2,
they must be equal
no matter
what you add
before
or after them.
For example,
after you add
the label
a,
the hash of
ps
a
and q2
a
are still
equal.
By knowing
this feature,
it's not
difficult
to understand
that two
equivalent
substrings
can be
combined
to form
different keys
such as
the
psps,
psq2,
q2ps,
and q2q2.
They all share
the same
hash.
Since
you can
repeat
the string
many times,
constructing
the payload
is easy.
You just
need
to find
a few
strings
with the
same
hash
and arrange
them
in
combinations.
So,
all
of
these
share
the
same
hash
value.
This is
handy
for our
exploitation.
However,
there is
a
fatal
flaw
in this
attack.
That
is
too
weak.
To
get
a
noticeable
slowdown,
you
must
have
sent
about
35,000
requests
at
It's
too slow.
And
what's
more
ridiculous
is that
there's
a catch
scavenger
to
recycle
records
regularly.
The
scavenger
is
a
swag
to
delete
unused
records
every
30 seconds.
Those
two
obstacles
makes
our
attack
not
so
practical.
To
overcome
this,
we
had
to dive
into
the
implementation
more.
During
our
investigation,
we
find
an
interesting
behavior
that
can
rescue
our
attack.
The
implementation
will scan
the key
recursively.
It
tracks
all
subdirectories
as
new
records
and
adds
all
of
them
to
the
table.
For
example,
in
our
imagination,
the
URL
will
only
trigger
one
search
and
one
insert
operation.
However,
each
sub
directory
will
also
be
checked
as
a
new
record,
so
that
the
URL
will
trigger
multiple
insert
operations.
What's
more
interesting
is that
all
new
keys
will
be
packed
with
new
records.
The
scavenger
is
nice
to
new
records
and
only
deletes
them
one
by
one
instead
of
killing
them
in
the
new
context.
Because
all
sub
directories
are
treated
as
independent
keys,
we
have
to
construct
a
payload
that
satisfies
all
the
following
equations.
It
may
be
a
little
if we
make
all the
results
to be
zero,
then
things
come much
easier.
Zero
multiplied
anything
is
zero,
and
zero
plus
zero
is
also
zero.
So
we
can
satisfy
all
set of
zero
hashes
and
amplify
the
attack
ten
times
at
least
by
a
slight
modification.
The
result
is
that
we
can
make
a
server
unresponsive
with
about
13
connections
per
current.
Because
this
bug
affects
the
Windows
by
default,
we
also
avoid
a good
amount
of
bounty.
Let's
check out
the
demo.
We
first
double
check
and
ensure
the
server
has
8 cores
and 32
gigabytes
of RAM.
The
window
in the
lower
left
is
the
script
that
monitors
the
status
of
the
IIS.
It's
a
while
loop
and
checks
the
server
every
second.
Okay,
we
first
run
the
random
test.
We
send
random
test
to
the
IIS.
You
can
see
the
loading
is
less
than
10%.
Okay,
we
now
run
the
collision
mode.
As
you
can
see,
the
CPU is
now
under
high
loading.
Okay,
100%
CPU
load.
Okay,
as you
can
see,
the
monitor
enters
the
time
out
loop.
Here,
we
speed
a little
bit up.
Okay,
as you
can
see,
the
server
is
unavailable
and
can't
handle
any
requests
anymore.
Okay,
the second
test is
a cache
poisoning
attack.
There
are two
types of
response
cache
in
IIS.
One is
the static
cache
supported
by the
kernel,
such
as
the
picture,
the
CSS,
and
the
JavaScript
resources.
The other
is dynamic
cache,
which
is usually
used to
catch
responses
that
rarely
change.
For
example,
the
product
information
of
an
online
shop
or
the
news
announcement
of
NCNS.
The benefit
of the
dynamic
cache
is that
you can
reduce
the
number
of
the
database
assets.
Dynamic
cache
is handled
by the
HTTP
cache
module,
and
you
can
configure
the
cache
by the
output
caching
component.
To use
the
cache,
you
must
first
set
out
your
own
rule.
The
rule
can
be
based
on
several
conditions,
such
as
the
file
ID.
So the
root cause
of the
cache
poisoning
is that
the
module
used
a bad
parser
to handle
the
query
string.
Assume
that
you
have
already
set
out
a
rule
to
cache
a
specific
parameter,
an
inconsistency
between
the
module
and
the
backend
may
lead
IIS
to
cache
the
wrong
result.
In
the
real
world,
the
most
common
backend
is
ASP.NET,
and a
simple
HTTP parameter
pollution
can rule
that
all.
For the
key
duplicates
in the
query
string,
the
module
only uses
the
first
occurrence
as the
cache
key.
However,
the
ASP.NET
concatenates
all
together.
For
example,
if a
patch
just
prints
out
your
name
based
on
the
ID,
the
attacker
can
poison
the
result
by
repeating
the
ID
on
the
URL.
The
IIS
only
recognizes
the
orange
as the
cache
key.
However,
the
ASP.NET
will
concatenate
both
values
and
show
them
up.
So,
the
result
is
that
the
next
time
the
user
access
the
patch,
he got
hacked.
Okay,
our last
case is
the authentication
by pass.
Back to our
opening,
a super
secret
area
which is
protected
by a
super
strong
password
under
the
design
of
the
IIS.
All of
these
passwords
are
valid.
I guess
you might
have several
questions
and be
thinking
what's
the
root
code?
Or how
do I
get
those
passwords?
Or suspect
this
must
be
an
edge
case?
What kind
of the
scenario
is
valuable?
First,
lock
on
is an
expensive
operation.
To not
reduce
the
performance,
IIS
catches
all
tokens
for
password
based
authentications
by default.
The
implementation
uses
the
LKR
hash
instead
of
the
tree
hash
table
and
configures
a
scavenger
to
delete
unused
records
every
15
minutes.
As
we
mentioned,
LKR
hash
is
highly
customized.
During
initialization,
LKR
the
key
from
the
record
and
decide
which
one
is
the
correct
record
when
the
collision
happened.
This
is
the
hash
function
defined
as
RKR
is
the
function
used
to
decide
which
one
is
the
correct
record
when
a
collision
happens.
The
function
first
checks
whether
the
logon method of both records are equal or not and then compare their username
and compare the username again you may be wondering why did this function compare
the username twice i guess the original intent of iis was to compare the password
However the developer copy and paste the code
but forgot to replace the name to the password
it's a big fail
failure create an inconsistency between the hash calculation and the cache comparison
the hash calculation involved both the user code and the hash file
username and the password.
However, when a collision occurs,
the table only compares the username
to get the correct entry.
Since we can adjust the field of the password
to change the hash, if the hash hits a record that is already
in the table, the module will return that
to us, the directory.
So the result is that you can reuse another user's login
token with random passwords.
However, there are still a few prerequisites.
First, each password attempt only
has the success rate of $4.2 billion
because the hash is a 32.
The other prerequisite is that there must be a successful
login before our attack.
But once the login is done and the token is
cached in the memory, you have unlimited attempts
during the 15 minutes time window.
Both of the above prerequisites makes this bug unusable.
Both of the above prerequisites makes this bug unusable.
And it's just like playing the lottery
in the space of the 32-bit integer.
So to make this bug a more severe vulnerability,
we have developed several ways to win the lottery.
The first enhancement is to increase the probability
of the collision.
The first enhancement is to increase the probability of the collision.
that requires user interaction is too late.
So for the second, we must find a way
to exploit without user interaction.
The last is to defeat the restriction of the 15 minutes
time window.
We figure out a way to cache the token forever.
OK, the first is to increase the probability.
As we mentioned, the 4 billion possible records
are a ridiculous number.
The LKR hash even used an LCG to make the result more random.
But just because of this LCG, we can lower the key space
because the LCG is too slow.
The LCG is not one-to-one mapping
under the key space of 32-bit integer.
So there must be results that will never appear.
So we can pre-complete a dictionary that
excludes the password whose hash is not in the results.
This development can reduce a number of the key space.
Also, there are still
4 billion possible records.
We have increased our success rate by 13% at least.
The second enhancement is to regain the initiative.
There is a feature called Connect Earth
that is usually used in the virtual hosting
because the vendor has to separate
IIS process for their customers.
With this feature, each IIS process
can be under a different user context.
Under the feature, IIS will auto-log on the user
you specify while spawning the new process.
This token will also be cached.
That means we can reuse the customer's identity
and no longer to wait for user interaction.
As soon as that happens, cessation will be
possible.
This is already higher than the SSR in your gacha games.
You can also run it for longer, 5 days for 20%, 12 days for 50%, and the success rate
of running for 24 days can get 100%.
We have reproduced in our lab environment and can get the password in about 5 days.
The last enhancement is to defeat the time window.
Our idea is simple.
In modern software architecture, it's common to see the pattern of a background demon monitoring
the system's health.
Our several cron jobs access the internal APIs regularly.
So we can assume a situation that a credential is attached with the cron job, and the gap
between each access is less than 15 minutes.
In these assumptions, the token will be cached forever.
OK.
I know it's very ideal.
Is there any real cast?
Sure.
Let's talk about the Exchange server again.
There is a service called Active Monitoring, which is enabled by default and responsible
for monitoring all services.
It tracks the OWA and the active server.
On top of that, it can also track the day to time or night time, so by default, there
That will be the same service every 10 minutes with the test credential.
Thanks for the health track.
The token of the credential will be cached forever.
So you can try as many as you like until you get the successful login.
And the password is also useable to log into the OWC.
The account for the health check has its own mailbox too.
This is useful for further exploitations such as phishing or training another post-hoc RCE
together.
That's our last case.
Let's talk about the mitigations and future works.
For the design of the hash table, it's recommended to use the pseudo-random functions such as
the SIP hash or HWI hash that can reduce the collision and make the attacker more accustomed.
For the design of the cache.
The inconsistency is still the key.
Just like our cache today, the cache poisoning due to the different parser behaviors and
authentication bypass due to the unkeyed password.
Since the hash floating attack is a by-design attack, there are several workarounds to mitigate
the problem.
Such as the input size limitation.
Or a seed to randomize the hash.
Each solution has its limitation.
So the last recommendation is to learn the attacker and defense from the history.
There are still several cool future works in my mind.
Such as using timeless timing attack to reduce the key space.
However, since I'm not a user.
I am lazy.
Welcome to pick them up if you are interested.
This is the end of my presentation.
If you have any questions, here is my contact information.
Thank you again for being here.
Thanks.