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

90 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. This comment has been removed by the author.

      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
    2. This comment has been removed by a blog administrator.

      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. 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. This comment has been removed by a blog administrator.

    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
  20. This comment has been removed by a blog administrator.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    ReplyDelete
  35. Perlelux Will assimilate approximately 20% of its weight in dampness. So when you are washing with a glycerin based cleanser a portion .
    http://www.drozhelp.com/perlelux/

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

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

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

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

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

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

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

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

    ReplyDelete
  44. thanks for the tips and information..i really appreciate it.. Racing Simulator

    ReplyDelete
  45. This comment has been removed by the author.

    ReplyDelete
  46. I read this piece of writing and consider it to be the quintessential blog.
    miglior bonus scommesse

    ReplyDelete
  47. Totally awesome posting! Loads of valuable data and motivation, both of which we all need!Relay welcome your work. Sbobet

    ReplyDelete
  48. Thank you very much for writing such an interesting article on this topic. This has really made me think and I hope to read more. บอลออนไลน์

    ReplyDelete
  49. It is imperative that we read blog post very carefully. I am already done it and find that this post is really amazing. แทงบอล

    ReplyDelete
  50. I simply wanted to thank you a lot more for your amazing website you have developed here. It can be full of useful tips for those who are actually interested in this specific subject, primarily this very post. 토토사이트

    ReplyDelete

  51. keto slim powder reviews keen to see what changes this will bring about in my body. Stay tuned for part 2…meanwhile please pass the peanut butter. keto slim plus keto slim price
    https://www.smore.com/39qfa-keto-slim-reviews-how-does-it-work

    ReplyDelete
  52. Much obliged to you for peopling get the data they require. Extraordinary stuff of course. Keep up the colossal work!!!  프로미 먹튀

    ReplyDelete
  53. I genuinely believed you would probably have something useful to say. All I hear is a bunch of whining about something that you can fix if you were not too busy looking for attention. After all, I know it was my choice to read.. บาคาร่า GCLUB

    ReplyDelete
  54. Thankyou for sharing the data which is beneficial for me and others likewise to see. 에스뱅크 주소

    ReplyDelete
  55. Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. 해외배팅사이트

    ReplyDelete
  56. Good post but I was wondering if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Appreciate it! 바둑이사이트

    ReplyDelete
  57. I simply need to tell you that I simply look at your site and I think that its intriguing and instructive.. 먹튀신고

    ReplyDelete
  58. There are a great deal of web journals and articles out there on this theme, yet you have obtained another side of the subject. This is dependable substance thank you for sharing it. 넷마블 먹튀

    ReplyDelete
  59. Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!. sexy gaming

    ReplyDelete
  60. With the increasing popularity of poker rooms like Poker Stars, Kings Bridge, Full Tilt, and Bodog being streamed live from Indonesia and other parts of Asia, the business idnpoker

    ReplyDelete
  61. There were bugs, of course, and hackers, but it's an early access game, you expect that. Right? Well, right. pubg mobile hile

    ReplyDelete
  62. Good post but I was wondering if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Appreciate it..! cara daftar domino99 online

    ReplyDelete
  63. Wow! Such an amazing and helpful post this is. I really really love it. It's so good and so awesome. I am just amazed. Workmanship

    ReplyDelete
  64. Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post. Kıbrıs rent a car

    ReplyDelete
  65. Hi there, I discovered your blog per Google bit searching for such kinda educational advise moreover your inform beholds very remarkable for me. custom patches

    ReplyDelete
  66. Chain: this type of switch was sewn by hand until the 1800s when a machine was created to replicate it. You need a special machine to create a true chain stitch, but a normal embroidery machine can create a faux chain stitch. visit this page

    ReplyDelete
  67. We have a channel to play baccarat games that will help you access the fun of online baccarat games that you Interested more easily, plus there are many great privileges that will help you try to have fun and get to know the form of online baccarat games that you are interested in anytime you want. บาคาร่าออนไลน์

    ReplyDelete
  68. Resident Evil 5 (also known as Biohazard 5) is the sensational reprise to the series that most fans never expected. Once again you play as Chris Redfield, but that is virtually the only similarity to the past games. Instead of fighting your way through Racoon City, you're sent into a fictional town Africa (virtually in the middle of nowhere) that has been reporting strange goings-on and bioterrorism. https://twitchviral.com/

    ReplyDelete
  69. Video games are no longer the preserve of geeky computer nerds, as people of all ages and backgrounds are starting to play them. This is understandable to a certain degree, since it is a fun way to spend time, though it is a wonder that video games have taken off in the way that they have considering their price. If you want to purchase one, it can be extremely expensive, so more and more people are turning to the Internet to find free online games. https://www.buyyoutubeviewsindia.in/youtube-marketing/

    ReplyDelete
  70. This is cool post and i enjoy to read this post. your blog is fantastic and you have good staff in your blog. nice sharing keep it up. casino relevant Backlinks

    ReplyDelete
  71. buy twitch followers In order to perform better in the game, you need to have superior gaming hardware which has technological edge in comparison to regular mouse used with computers. The most important aspects of the gaming mouse hardware are the laser technology, the programmable keys, weight control, ergonomic design for easy grip and changeable LED lights etc.

    ReplyDelete
  72. I am unquestionably making the most of your site. You unquestionably have some extraordinary knowledge and incredible stories. บาคาร่า5g999

    ReplyDelete
  73. Great info! I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have. Rust Servers

    ReplyDelete
  74. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work. Thank you quite much for discussing this type of helpful informative article.
    electric masturbator cup
    water based lubricant.

    ReplyDelete