Monday, May 27, 2013

Winning in bad designed online games that use cryptographic hash functions as a proof of fair play


What it means that game uses cryptographic hash functions as a proof of fair play? When you start round a game state string is generated, and hash of it is displayed to you. After you lose or win original GSS (game state string) is displayed and you can verify that the hash is correct. More important fact is that GSS contains a readable wining/losing states that you can verify yourself (for example: in a "mines" game it will be position of all mines) after you end the game. This is the way some games use to show you that the game is really fair.

So basically when you crack that hash you will get GSS before you even start playing, and that will make you always win. Cracking that hash should be very hard and almost impossible and it strictly depends on GSS construction. However if GSS is bad designed you will be able to win everytime.

The best way to crack that game is to generate all possible GSSs with their hashes (this is so called "rainbow table"), but when the GSS is well designed you'll need a lot of storage (ex. thousands of petabytes). There are some GSS dynamic components (like timestamp) which make generating rainbow table impossible and that is why sometimes better option would be cracking hash on the fly (using GPU, multiple GPUs, etc.). But we have same issue here - if the GSS is well designed or you don't have enough computing power you will be waiting months, years, decades or even ages.

Now lets try to crack real example.

Satoshi-Karoshi is mines-like gambling game using bitcoin currency. There is "Free play!" option so we'll use it for our research purposes.

Step 1: Understanding GSS (game state string) structure and its implications.

First of all we need to collect some samples ("Free play!" option):
# 2x3 map:
128c4256f6fdf057b8cd759a137721efb412b10e - (2,2,2 | 2013-05-25 10:59:20)1ab8f2
84c2b4349e8884d1f024d579c4d6379bc6b46c49 - (1,2,2 | 2013-05-25 11:00:03)33bc57

# 3x6 map:
2fc25b3c901f49ada25b17d84eee033e8313a920 - (1,2,1,2,2,1 | 2013-05-25 11:00:18)b2c1af
e91cc7503926463dc9e2b9a75ee6c4378b058e40 - (3,1,2,2,2,2 | 2013-05-25 11:00:33)5c0e90
 
# 4x9 map:
74b8b7f6fb186e784883c496ed30468453c5afeb - (3,2,1,3,3,3,1,1,4 | 2013-05-25 11:00:57)b120d0
66570d11f8da47917f65e5754a875f947828d365 - (3,2,4,4,3,2,4,1,3 | 2013-05-25 11:01:17)c607fc
 
# 5x11 map:
936523f9bd3055011fbc95cd25e174b3eef762a2 - (3,4,4,1,2,4,5,3,5,1,5 | 2013-05-25 11:01:42)b599d1
73dfff09231396ebafc7aba4a1cd84156a180ffc - (3,4,2,1,3,3,1,5,1,3,5 | 2013-05-25 11:02:38)f2b4e7
It's obvious that GSS structure contains 3 different sections, and can be written as:
(MINES[positions] | TIMESTAMP)HEXSTRING
We can't generate rainbow table because of timestamp and assuming that we will be able to "guess" it, lets calculate all possibles GSSs (ignoring timestamp for now).
map 5x11 - 819200000000000 combinations (5^11[MINES] * 16^6[HEXSTRING])
map 4x9 - 4398046511104 combinations (4^9[MINES] * 16^6[HEXSTRING})
map 3x6 - 12230590464 combinations (3^6[MINES] * 16^6[HEXSTRING})
map 2x3 - 134217728 combinations (2^3[MINES] * 16^6[HEXSTRING})
So what about timestamp? We can synchronize our local computer time with game server time with some requests, or just use "Date" field from HTTP header (when you click "Free play!" there is ajax POST in the background which contains server time in http response header).

Step 2: Cracking

In ideal world we should be able to use existing tools for sha1 gpu brute-force cracking with "mask" feature (because we already know GSS structure, and we know that MINES section are numbers separated by comma, first character is always "(", etc.). oclhashcat is a great gpu hash cracker with "mask" attack support, but the maximum password length (in our case password=GSS) is set to 15 (and unfortunately oclhashcat is closed source). I haven't search enough to see if there are another alternatives gpu crackers with "mask" support but looking closer at combinations number for 2x3 map (134217728 is relatively small) we don't need to use GPU after all. I've written small brute-force cracker using fast sha1 implementation in x86 assembly by Nayuki Minase. I've modified only main() function from sha1test.c which now looks like:

...

int main(int argc, char **argv) {

        if (argc<3) { // change it for MT, cause of extra argument
                printf("\n%s HASH DATETIME\n\n", argv[0]);
                exit(0);
        }

        // self-check
        if (!self_check()) {
                printf("Self-check failed\n");
                return 1;
        }


        // change hash string (argv[1]) into proper array of uint32_t, quick&dirty way :)
        uint32_t search[5];
        char search_str[40];
        uint8_t tmp[9];
        int i,k;

        memcpy(search_str, argv[1], 40);
        for(i=0,k=0;i<40;i+=8,k++) {
                memcpy(tmp, search_str+i, 8);
                tmp[8] = 0;
                search[k] = (uint32_t)strtol(tmp, NULL, 16);
        }

        // HEXSTRING section
        uint8_t chars[] = "731fda260594be8c"; // shuffled
        uint32_t chars_len = strlen(chars);

        // MINES section
        uint8_t markers[] = "12";
        uint32_t markers_len = strlen(markers);

        // message template
        uint8_t message[36] = "(-,-,- | 2013-05-22 15:46:01)------";

        // fill timestamp
        memcpy(message+9, argv[2], 19);
        
        // fill mines for MT       
        /*message[1] = argv[3][0];
        message[3] = argv[3][1];
        message[5] = argv[3][2];*/


        // cracking
        int i_a, i_b, i_c, i_d, i_e, i_f, i_m1, i_m2, i_m3;
        uint32_t hash[5];


        for(i_m1= 0; i_m1<markers_len; i_m1++) // remove for MT
        for(i_m2= 0; i_m2<markers_len; i_m2++) // remove for MT
        for(i_m3= 0; i_m3<markers_len; i_m3++) // remove for MT
        for(i_a=0; i_a<chars_len; i_a++)
        for(i_b=0; i_b<chars_len; i_b++)
        for(i_c=0; i_c<chars_len; i_c++)
        for(i_d=0; i_d<chars_len; i_d++)
        for(i_e=0; i_e<chars_len; i_e++)
        for(i_f=0; i_f<chars_len; i_f++) {
                // MINES section
                message[1] = markers[i_m1]; // remove for MT
                message[3] = markers[i_m2]; // remove for MT
                message[5] = markers[i_m3]; // remove for MT

                // HEXSTRING section
                message[34] = chars[i_f];
                message[33] = chars[i_e];
                message[32] = chars[i_d];
                message[31] = chars[i_c];
                message[30] = chars[i_b];
                message[29] = chars[i_a];
//              printf("%s\n", message);
                sha1_hash(message, 35, hash);

                // check generated hash
                if (hash[0]==search[0] && hash[1]==search[1] && hash[2]==search[2] && hash[3] == search[3] && hash[4] == search[4]) {
                        message[35] = 0;
                        printf("Found: %s\n", message);
                        return 0;
                }
        }

        return 0;
}

...

In spite of one thread this code crack that hash in seconds. However extending to simplified multithreading for 2x3 map is easy, proper lines are marked with *MT comment in code. After changes in code we should run 8 separate threads, like in that bash script:
#!/bin/bash
./crack $1 "$2" 111 &
./crack $1 "$2" 112 &
./crack $1 "$2" 121 &
./crack $1 "$2" 122 &
./crack $1 "$2" 211 &
./crack $1 "$2" 212 &
./crack $1 "$2" 221 &
./crack $1 "$2" 222 &

And video of using it in action (I've used multithreaded version to make video length little shorter):

WARNING! If you want to win some bitcoins in that game, you should know that games for real bitcoins have different GSSs which are far more complicated and can't be cracked easily!

UPDATE 30-08-2013:
oclHashcat-plus v0.15 is capable of cracking passwords longer than 15 characters, although performance is worse. You can read more details in release note here

33 comments:

  1. What software exactly need to use on for purpose to crack satoshi karoshi hash, because I still can't understand?

    ReplyDelete
    Replies
    1. I've used fast SHA1 implementation by Nayuki Minase in x86 assembly. It's all described in "Step 2: Cracking".

      Delete
  2. Hello, I'm not very good in all those computer things, so I would like to ask, in your video, where did you get that redeemer@lust window and where need to write all those functions described in step 2: cracking? Thanks

    ReplyDelete
    Replies
    1. Hi. The window under Chrome browser is Putty (I'm using it to log into remote computer running Linux where I run cracking software). Cracker itself is written in C with SHA1 implementation in assembly. Basically you need to grab files from Nayuki Minase, replace main function from sha1test.c and compile it.

      However, please note that you won't be able to crack hashes for "real" games with it (white-red box under embedded video)

      Delete
  3. What cracking software do you use or this SHA1 implementation is cracking software and how to compile it? I'm sorry for being so bothering, but it's really hard to understand for me.

    ReplyDelete
    Replies
    1. "Cracking software" is written by me and uses SHA1 (you have to use SHA1 cryptographic hash function because satoshi-karoshi uses it). Moreover, "Step 2" contains all the information needed to reproduce that "software" like: link to source code of Nayukis SHA1 implementation and a source code of main() function for replacement.

      As a compiler I've used gcc on linux. How to Compile a C Program Using the GNU Compiler (GCC)

      Delete
  4. Good day, I have checked your video and read all this cracking stuff, but it's pretty hard to understand everything while I'm reading, so I was hoping, maybe you could make a video where you show step by step how you do all those functions, how you compile and how you crack. So if you could do that I would be grateful, thank you.

    ReplyDelete
    Replies
    1. I think step-by-step video is not necessary, however I can prepare ready to compile source code, or already compiled binaries if you are still interested.

      And again, repeating myself: please note that you won't be able to crack hashes for "real" games with it.

      Delete
  5. Well, maybe you could do both: that source code and compiled binaries, if I'm not asking too much. Thank you.

    ReplyDelete
    Replies
    1. Sorry for the delay, but here you go: http://cinu.pl/research/satoshi-karoshi-crack/satoshi-karoshi-crack.tar.bz2

      It contains both source code and compiled binary (ELF 64-bit LSB executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.18, not stripped).

      Delete
  6. is there anyway you would be able to crack satoshimines.com? It uses sha256 and an example of their secret is 10-18-16-ta8Mu73DT4 and the hash is 9721380f70bdf9d05459f36a48d81aeb57b333320d17a2753be04e6fffc331fa. The last part of the secret is always 10 characters long.

    ReplyDelete
    Replies
    1. Considering only suffix ("ta8Mu73DT4") there are (26+26+10)^10 = 839299365868340224 all possible suffixes.
      To crack it in reasonably time (in minutes) you will need be capable of compute hundreds of terahashes per second. For instance, if your hashrate is 500 Terahashes/s you will be able to crack it in ~15 minutes (worst case scenario is ~30minutes).

      On the other hand if you want to generate "rainbow tables" (it is possible since "secret" doesn't have dynamic data) and you can compress suffix to 4 bytes you will need ~2981 petabytes of storage.

      Delete
  7. where can i download your software

    ReplyDelete
    Replies
    1. http://blog.cinu.pl/2013/05/winning-in-bad-designed-online-games.html?showComment=1374053721179#c203301006653439467

      Delete
  8. Hi i read this Blog and it is very Interesting! Have you crack the "real money mode" too? Or is the time that it use to long? (sry for my bad English!)

    ReplyDelete
    Replies
    1. As far I remember "Real money mode" hash is far more complicated and can't be cracked in reasonable time and with reasonable resources.

      Delete
  9. Cool code and webpage, congrat! I saw many times it uses numbers only for hexstring, so I generated the possible 8000000 strings in statistical program, but getting their sha1 is a bit slow...can windows be used or linux is much faster?

    ReplyDelete
    Replies
    1. and according to resources, can we create a supercomputer? (link some dual core laptops and desktop pcs to sum cpus and rams) or can the written c program divide the tasks? how many comps do we need for a 10 or 16 string hexstring to decrypt? 10 is enough?

      Delete
    2. woud this fit:www.webstreet.com/super_computer.htm

      Delete
  10. Could you pm me?,thx
    ad11@hmamail.com

    ReplyDelete
  11. I compiled it, running, but no result, no error, what is the problem? without args it writes need hash and date
    ./crack hash "date"
    running, then prompt again ...

    ReplyDelete
  12. I tried your command line and everything works.. but I don't understand the "time" you are writing. It's not the time from the http response.. its like +3 hours. What's up with that?

    Best regards.

    ReplyDelete
    Replies
    1. I found it out by myself.. the server time is different than the http response. So I just add 2 hours.. bad that this doesn't work on real games with BTC. Maybe because the string is salted?..

      Delete
  13. Good job, ruined it for everybody

    ReplyDelete
  14. Can i have the final project, ready to use?

    ReplyDelete
  15. This comment has been removed by a blog administrator.

    ReplyDelete
  16. This comment has been removed by a blog administrator.

    ReplyDelete
  17. how to do bro loogpoochay09@gmail.com

    ReplyDelete
  18. You can also find helpful strategies and online games on parenting websites and other wellness and effectively becoming portals for parents. Free heart of vegas coins

    ReplyDelete
  19. carlton, your post seems good :-) i like your comment. satoshi really sucks for me. :-( im just good to play in Free heart of Vegas Coins .

    ReplyDelete