There was a very interesting presentation at the last 31C3 conference given by two very talented security researchers: Shahar Tal and Lior Oppenheim. The vulnerability they found targets many different routers from various manufacturers and was, apparently, patched 10 years ago (!) by the software company who made RomPager, the software in question. Let’s just say vendors are slow in deploying patches, leaving tens of millions of routers vulnerable to potential remote bricking, turning into botnets or who knows what else. It was named Misfortune Cookie for a good reason, but what does that have to do with math?
Apparently, there is a preallocated array in the webserver capable of storing 10 cookies, 40 bytes each. The cookie number is used as array index - converted to integer, multiplied by 40 and added to a memory address to read or write the correct location without ever checking boundaries.
You can pass an arbitrary number and address any memory location relative to a certain fixed point in memory. The only catch is that it gets multiplied by 40. What can you do if you need better precision to avoid overwriting something else near the memory location you are targeting?
This can be written in a form of ax ≡ y (mod m) and it’s called a Linear
Congruence. Obviously, a is 40 since we move in steps of 40. We need to find
such x that multiplied by 40 gives us a desired y modulo m we need to move in
memory relative to the present location. M is
(the size of a 32 bit
number could fit 0-4294967295, anything more than that and it will
overflow and start from zero again, just like a clock face starts from
1 when it reaches 12), making the equation 40 x ≡ y (mod
).
For this to have a solution, x needs to be divisible with the greatest common
divisor of both 40 and ,
which is 8 - that’s how many unique solutions we’ll get. Now we can
say
and reduce the expression to 5x ≡ z (mod 536870912). The way to solve it is to find the multiplicative inverse modulo m - a number we can multiply both sides with so that it gives 1 when multiplied by 5 in this modular algebra.
To get the other solutions, we need to keep adding the modulus value (536870912) to the result and reduce when needed. The referer is located at 0x2e48 to the LEFT of the cookie array. Since we cannot go backwards, we would like to add 0xffffd1b8 to overflow 32 bit number and end up at the desired address.
>>> def calc(a): return ((a/8)*214748365) % (1<<32)
>>> sorted([(calc(int('0xffffd1b8',16))+i*536870912)%(1<<32) for i in range(8)])
[322122251, 858993163, 1395864075, 1932734987, 2469605899, 3006476811, 3543347723, 4080218635]
# -- Let's do a check.
>>> hex((322122251*40) % (1<<32))
'0xffffd1b8'
Now let’s try it on my router!
send: 'GET / HTTP/1.1\r\nHost: 192.168.1.1:7547\r\nCookie: C322122251=/referer-test.html;\r\n\r\n'
reply: 'HTTP/1.1 404 Not Found\r\n'
header: Content-Type: text/html
header: Transfer-Encoding: chunked
header: Server: RomPager/4.07 UPnP/1.0
header: EXT:
<html>
<head>
<title>Object Not Found</title></head><body>
<h1>Object Not Found</h1>The requested URL '/' was not found on the RomPager server.
<p>Return to <A HREF="/referer-test.html">last page</A><p>
</body></html> ^^^^^^^^^^^^^^^^^^
Is there another way?
It’s not necessary to find a general solution, sometimes thinking differently can work too.
How many additional bits can multiplying by 40 add to a number’s binary
representation? It’s between 32 (that’s
) and 64 (that’s
), so we have to assume 6
bits. The question becomes, which number multiplied by 40 and with 6
most significant bits discarded is equal to our input variable y?
The router CPU might be stuck with 32 bits, but Python isn’t. Why not
simply reconstruct these discarded bits by testing each case? Guess
what the discarded value might have been and divide by 40 to check if
the assumption was correct. For just 6 bits added, it isn’t terribly
inefficient to check all possibilities and it goes to prove there are
many ways to address a problem. Pun intended! :)
Start with 4294955448 in binary form.
11111111111111111101000110111000
Multiplying by 40 gives 171798217920. In binary, that's
100111 11111111111110001100010011000000
overflow
The 100111 is simply too much to store in a 32 bit memory unit so it gets discarded, and the rest we called y. We now need to do this in reverse, starting from y, guessing the discarded part and checking if division by 40 gives the starting value. If it does - that’s it.
t = int('0xffffd1b8', 16)
>>> [i for i in map(lambda a: ((a<<32)+t)/40, range(64)) if (i*40)%(1<<32)==t and i<(1<<32)]
[322122251, 858993163, 1395864075, 1932734987, 2469605899, 3006476811, 3543347723, 4080218635]
So the next time you complain learning math is silly when studying for a CS degree, just remember you might actually need it!