1. Psst! We just published some cool documents with tons of tips and secrets about both this forum and Mekorama. Whether you're just visiting, a new member, or have been with us for a while, we're sure you'll find them useful. So far we have Welcome_to_MekoramaForum.pdf, Introduction_to_Mekorama.pdf, and How_to_Share_a_Mekorama_Level.pdf. Find them all in this forum thread:

    Everything you have always wanted to know about Mekorama

    Dismiss Notice

QR code - Can it be reverse engineered?

Discussion in 'General' started by QuantumForce, Oct 19, 2016.

  1. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    I was curious whether the format for the level codes had been reverse engineered yet, and how the community would react to efforts to do so. This would enable both viewing the internals of existing levels and generating new levels with external programs. I did see a few levels around here that seemed to use non-standard share cards, but I didn't find any info about the format itself.
     
    BitByte likes this.
  2. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    Despite the performance of doing such a thing I don't think it's a good idea in order to publish it in the level section. Maybe as a proof of concept in the forum section, but not as an official level. @meko made a joke once but it was a fake :). If you've found levels that seem suspect please report them, but I am not sure it will be obvious to prove that.

    If I were Martin I would thought about encrypting the content (even weakly) so that it can be decode from the software only. You can encapsulate data in QR Code but it is not garanted that these data are "readable" without the needed key. I admit that I didn't invest my time in such a way despite I find this subject really interesting. ;)
     
    BitByte and QuantumForce like this.
  3. Martin Magni

    Martin Magni Active Member

    Messages:
    7
    Levels:
    12
    Albums:
    1
    Likes Received:
    144
    Joined:
    May 23, 2016
    Someone had the idea to store only the QR code data on the forum server and recreate the card image when requested. This would save a lot of storage space and, if done on the client side, bandwidth. In fact, this is how the in-game cards work.

    The data format is not encrypted as I did not want to prevent reverse engineering it. :)
     
    BitByte, meko, QuantumForce and 4 others like this.
  4. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    Thanks @Martin for your reply.

    That would be great! But as this forum is kind of a generic one (the XenForo platform), I am not sure it is possible to do so unless by developing a plugin with the agreement of its owner and studying how to do that on this platform... On another hand, cards need to be rendered in order to be shown in the website (but maybe it doesn't need to be as big as those uploaded). So pictures has to be stored somewhere, otherwise if the image is recreated each time the card is requested, it could heavily loads the server :eek:

    What could be also interesting from the server side is a way to check that the QR Code is valid and is readable each time it is uploaded. That could save a lot of time. But I don't see how to do that without a proper webserver with a dedicated development to do that ;)

    Hmmm... That intrigues me... :cool: Thanks for the tip... Maybe I'll check that one day as a challenge ;)
     
    QuantumForce likes this.
  5. Frenzies

    Frenzies Mekorama Critic Staff Member

    Messages:
    341
    Levels:
    17
    Albums:
    4
    Likes Received:
    1,083
    Joined:
    Jun 15, 2016
    @Gepeto Looks like we'll need to link the forum to the game to do it, then (for the game to scan and render the cards on your device, and not the sever), to prevent server overloading. Sadly, it doesn't look like something like that is going to happen soon :( (or anytime in the future, for that matter). Oh well...

    P.S. I hope that what I said made sense :D. I'm not an expert in these stuff.
     
    Last edited: Oct 21, 2016
  6. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    Maybe you're right but then, we are not mandatory to a QR Code interface... It could be any requests exchanges method between both parts. But that would need a real dedicated webserver software linked to the client application... That's a huge work from server and client side :eek:.

    QR Codes still a "friendly" way to exchange cards. It is also is a really great way for a universal exchange method and that's well considered. Cards can be exchanged everywhere (FB, Personnal websites, this forum,...), people look at them such as kids exchanging and collecting cards as they want at schools playgrounds. Myself I have got a big collection of cards in a folder of my device :D

    Things have to move on everytime but despite the fact that we have few details on Martin's projects, I am sure he's doing everything for the good of the game ;)
     
    QuantumForce and Frenzies like this.
  7. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    I'll take that as approval for the reverse engineering effort.

    Any levels generated programmatically would have to be validated through the official app in order to post the full screenshot with checkmark, so I think that using tools to help generate levels would be allowable within the rules of the forum.

    I looked up the level I was thinking of and it looks like they just cropped the screenshot down to the QR code, rather than creating it themselves. I'll avoid linking here to avoid getting the author in trouble. ;)

    One nice application for programmatically reading/writing levels would be to write a small program that would allow the level to be rotated, as suggested here.
     
  8. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    @Martin Magni Can you provide any basic info about the format? Knowing the compression scheme, endianness, and container format (if relevant) would be very helpful.

    I've started looking through basic test cases (e.g. blank levels with various names, levels with single blocks, etc). Part of my problem is that most QR readers seem to assume ascii text, so it's easy to get corrupted data if they try to interpret it as UTF-8. Using the zxing decoder I do see that packets are padded with 0xEC11 through to some fixed lengths (55, 80, 156 bytes, etc), which seems to be part of the QR spec and would indicate that I'm extracting the correct byte sequences. I was hoping that at least the title and author would be uncompressed, but that seems not to be the case.

    If anyone is interested in helping with the decoding, let me know and I can share my list of level data. It's kind of fun to make minor changes to the levels and try to see how that modifies the QR data.
     
    HackedUp likes this.
  9. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    I was working on this over the weekend but I'm now stuck. I can read and write data from QR codes, and recreating existing levels works. However, small changes to the levels can cause large changes to the data bytes, making interpretation very confusing. For instance, changing a stone block to a brick caused a 5-byte change in the data. Changing to a grass brick in the same position caused a 38 byte change (70% of the level data). To me this smells of compression, but the levels don't contain magic numbers for any of the standard compression schemes.

    Code is on my github: sbliven/mekoqr (I'll make that a link once I have enough likes)

    Edit: added link, fixed typo in repo name
     
    Last edited: Oct 25, 2016
    HackedUp, Gepeto and B Hill like this.
  10. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    So working with Java... Fine. I'll check that when I can but not sure it is soon :)
    I also tried to see differences in the data with nothing then one block of stone, metal, etc. and I have seen that the result was totally different so I gave up. I was waiting for some byte changes but no.
     
    QuantumForce likes this.
  11. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    I just wanna add that I like to hack things but not for bad purposes. Curiosity is a good temper but not if it leads to bad manners. That's my opinion. If at the end we'll see hacked levels published in the forum as original ones I would disagree. If we'll share hacked level in the forum section (not the levels one) as a curiosity with evidences on the method used I would find this as interesting and fun. Everything depends on the way it is presented ;)
     
  12. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    @Gepeto I was originally using python-zxing, but I had trouble with it trying to decode everything as unicode. The underlying Java exposes the raw data. Plus, the android app is likely using zxing since it's made by Google.

    I think that malicious "hacked levels" are unlikely. Things like automatically generated mazes sound perfectly legitimate to me, and I would say they belong in the main levels section (assuming they have thumbnails and checkmarks). The most problematic use I can think of is to analyze hidden internals on levels like @JANDREL's SEC.SYS.CODE, but that just spoils the puzzle. I guess it could make it easier to publish minor variants of others' levels, but that's also possible in the in-game editor (just more tedious).
     
    HackedUp, cpw and Gepeto like this.
  13. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    I suppose that you've worked with Python 2.7, as unicode and string encoding is a mess to manipulate. That's why I've moved to Python 3 for most new developements that do not require the use of OpenCV or other libraries that hasn't yet been ported to this version.

    I didn't try to develop something about QR Code with python but I've seen some interesting references to start with (qrtools, PyQRCode, PyXing and ZBar - I've already used this last at work for Code128 barcode).
     
    HackedUp likes this.
  14. B Hill

    B Hill Active Member

    Messages:
    63
    Levels:
    24
    Albums:
    3
    Likes Received:
    232
    Joined:
    Jul 27, 2016
    @QuantumForce Seeing log4j is giving me flashbacks to running Java under Unix Services for MVS...
     
    Last edited: Oct 24, 2016
  15. nGord

    nGord Pseudo Administrator Staff Member

    Messages:
    375
    Levels:
    7
    Albums:
    4
    Likes Received:
    1,729
    Joined:
    Jul 21, 2016
    Agreed.
    That would be phenomenal. I'm sure many designers would like that. Except that I don't think anyone could succeed at it. I suspect that the level picture in the card image is generated in the app and then stored as straight data on the card image (and QR code). To change the level picture, you'd have to find a new way to render it and then save it into the QR code. Not likely possible - particularly not simply by cracking the QR code.
    Nice. That is what I found as well. Except that I found that padding at the end of the QR code.

    What I tried was simply adding the character '7' after New Level (so that it read "New Level7"). I figured that this change would probably be the absolute smallest change from one QR code to another. Adding a checkmark to a card does not change the QR code as the checkmark resides in a lookup table on the respective device. Adding any block would add all kinds of information like what block, where located, what orientation, what shading, how does it look on the final level picture on the card image, etc.

    Like you, I was hoping that the card title and author would be a simple hex entry for the ASCII equivalents. No such luck, indicating - as you say - likely compression of the data prior to QR code encoding. The first task then would be to see if the compression algorithm could be determined. This is where I'm going to stop. I suspect that it'll be some form of lossless compression, but I haven't touched code since school.

    Good luck!
     
    QuantumForce and cpw like this.
  16. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    Given the ability to read and write levels, we could just generate a new level that is identical in every way except that the coordinates of each block are rotated.

    I agree. The other possibility is that there are some parity bits for error correcting, since I basically always see some changes in the last four bytes. That wouldn't explain the large changes, but it would make it easier to experiment with minor modifications without getting the 'Corrupted data' error upon reading.
     
    nGord likes this.
  17. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    Yesterday I have made some investigations on the chunk data from the QR Code.

    From what I have seen I am pretty sure that the data has been compressed with a Zlib compression or kind of. As PNG format uses the Deflate algorithm (which is the same algorithm used in the zlib compression library), Martin could have used the PNG library to compress the data, extract the IDAT part and package it in a suitable format (maybe with a custom signature?). I guess this because the PNG images generated from the game has an IDAT which begins with 0x78, 0x01 (the zlib with no/low compression signature) then some data that seems to be the size or else and looks like the structure I have found in the QR Code.

    I don't know yet if that could lead somewhere but that seems to be a good start to me.

    Here is the PNG Wikipedia page where the zlib compression is named (in english)
     
    Last edited: Oct 26, 2016
    nGord and QuantumForce like this.
  18. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    I think you're on to something. The QR code data always begins with 0x 01 13 0D FC 78 01 ED. Also, DEFLATE (e.g. zlib) streams end with a 4-byte ADLER32 checksum, which would be consistent with my observation that the last bytes tend to change frequently.
     
  19. QuantumForce

    QuantumForce Member

    Messages:
    35
    Levels:
    3
    Albums:
    1
    Likes Received:
    96
    Joined:
    Oct 19, 2016
    Bingo. Python's zlib.decompress works perfectly on the data, starting with the 0x7801. I see the title length and ascii, author length and ascii, and then 16*16*16 bytes that must give the level data.

    We're in business! Way to go, @Gepeto!
     
    Gepeto, nGord and sawdust like this.
  20. Gepeto

    Gepeto Moderator Staff Member

    Messages:
    349
    Levels:
    48
    Albums:
    1
    Likes Received:
    1,573
    Joined:
    Jul 7, 2016
    Wow, that's great! I have stopped before as the zlib.decompress method returned an "unknown compression method" but the header seemed to be accepted. Maybe tonight I'll dig on that.
     
    Last edited: Oct 26, 2016

Share This Page