SmashManiac

Secret room

Recommended Posts

Nah i dont think brute force is the way to go.

I'm still curious if we are supposed to find the pass in the game or in the gamefiles.

I remember i printed out the stringtables to read throw em on carrides and stuff like that, but after the first two pages i droped the idea.

The chance that I will hit it is pretty low i think. i dont know much about cryptographie.

But i will give it another chance for sure.

Share this post


Link to post
Share on other sites
Nah i dont think brute force is the way to go.

I'm still curious if we are supposed to find the pass in the game or in the gamefiles.

I remember i printed out the stringtables to read throw em on carrides and stuff like that, but after the first two pages i droped the idea.

The chance that I will hit it is pretty low i think. i dont know much about cryptographie.

But i will give it another chance for sure.

Brute forcing a password is a perfectly valid method of real world hacking :)

Share this post


Link to post
Share on other sites

There is still potential in dictionary attacks. I know Netrix tried it previously, but he appeared to have limited his attempt to a single word with mixed capitalization. My guess is that whatever this password is, it's probably a short sentence with correct grammar. I wouldn't be surprised if a dictionary generated from the in-game strings exclusively would be sufficient for the job.

Also, I just had another idea: is it possible to deduce an AES-256 key if we already know a chuck of the original data big enough to cover the key length? Based on the Lua source code and the game files, if we assume that the original SecretRoom.lua is compiled and was done so at the same location than the encrypted version, then I believe the first 69 bytes would be:

1B 4C 75 61 51 00 01 04 04 04 08 00 2A 00 00 00

40 44 61 74 61 2F 43 6F 6E 74 65 6E 74 2F 53 65

63 72 65 74 2F 52 6F 6F 6D 73 2F 53 65 63 72 65

74 52 6F 6F 6D 2E 6C 75 61 00 00 00 00 00 00 00

00 00 00 00 02

Share this post


Link to post
Share on other sites

AES is unfortunately not susceptible to known-plain-text attacks. But it might help when checking for a valid key.

Share this post


Link to post
Share on other sites

I was going through all of my old folders to organize my data and I came across the files related to this. For brute forcing, I did only try single words with symbols and numbers. I didn't get around to trying proper sentences from the game's strings. There are quite a bit of strings within the game files though so I don't know how long it will take to try up to even just 3 word sentences. I'll at least make an attempt though I do agree that this is almost certainly not the intended way to solve it.

Share this post


Link to post
Share on other sites

Just a quickie: that sentence from the "messed up glyphs" puzzle (something like quick brown wizards something something), was that tried as a password?

Share this post


Link to post
Share on other sites

You are talking about this line: "THE FIVE BOXING WIZARDS JUMP QUICKLY" It doesn't work as the password.

Share this post


Link to post
Share on other sites

Netrix, can you share the script you're using for bruteforcing?

Also, I just had an idea watching keybounce's stream. There's a few empty chests in the game. I originally thought it was unfinished content, but it is possible it's a hint for the secret room somehow.

Share this post


Link to post
Share on other sites

Idea.

 

I was thinking about the wishes that Smash had me use after completing the game, to get the encrypted secret room book.

 

What if the decryption key is one of those wish strings?

 

We've got a number of "useless" things in the game to consider, such as a treasure chest that has nothing in it. What if the chest itself is the decryption string -- or more accurately, the wish name that refers to that chest?

Share this post


Link to post
Share on other sites

So, just played through the game and tried to decrypt secret.lua

I got nothin'.

I'd glad to see this is still active as of last month, though, do you folks have any methods of attack or any progress?

Share this post


Link to post
Share on other sites

The only idea I have is that "wish string" that I mentioned before.

No one has yet figured out a solution.

 

 

Share this post


Link to post
Share on other sites
On 4/1/2017 at 6:21 PM, SmashManiac said:

Netrix, can you share the script you're using for bruteforcing?

Also, I just had an idea watching keybounce's stream. There's a few empty chests in the game. I originally thought it was unfinished content, but it is possible it's a hint for the secret room somehow.

Since any in-game script would be incredibly slow and useless for brute forcing, I'm using a C program that uses the same decryption process as the game that I've highly optimized. I can try about 6 million passwords per second, but if the password has special characters, has 8 or more characters, or is more than 3 words in length, it is practically impossible to brute force with current technology. Maybe some day in the future when we have quantum computing it will be possible to break the encryption, but it doesn't look like it will be any time soon. I've been busy recently but maybe at some point I'll package what I have so other people can play with it.

11 hours ago, 0xffe3 said:

So, just played through the game and tried to decrypt secret.lua

I got nothin'.

I'd glad to see this is still active as of last month, though, do you folks have any methods of attack or any progress?

I've just tried brute forcing and various guesses that other people have made.

Share this post


Link to post
Share on other sites
On 1/26/2017 at 5:19 PM, finsternacht said:

AES is unfortunately not susceptible to known-plain-text attacks. But it might help when checking for a valid key.

I've been questioning this statement recently.

Here's what I've gathered so far:

  • The key string is hashed using SHA-256, which is used as the key for AES-256-CBC with a null IV, to generate the output.
  • We already know the first 4 blocks of 16 bytes each of the original plaintext due to the Lua file structure and the game's directory structure (see my post from June 19, 2016).
  • Due to the properties of CBC, deciphering a block only requires the key, the block's ciphertext and the previous block's ciphertext, or the IV if there is no previous block.

With this information, we have 4 sets of AES-256 "equations" with only the hashed key as the unknown variable. The question is, is deducing the key from those "equations" realistic?

It sounds unlikely to me, but I could not find a definitive answer to this question. I've seen claims that terabytes of known plaintext block matches wouldn't be enough to do so, but could not find the mathematical arguments to support them.

Share this post


Link to post
Share on other sites

Well, that's exactly my field of pure mathematics, so let me look at AES and take a think about it.

Share this post


Link to post
Share on other sites

Alright, so, here's the most recent math on it, as far as I can figure: https://web.archive.org/web/20120905154705/http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf

This describes a 'key recovery attack', which assumes you know the method, all the plaintext, and all the ciphertext, and it concludes that for AES-256, we would need 2^254.4 time to recover the key, provided we have sufficient plaintext/ciphertext known matches.

That's around 10^60, or a trillion of a trillion of a trillion of a trillion of a trillion operations, so that's not a viable method anytime soon. It *is* slightly faster than brute forcing, though. And they assume full plaintext access.

I've thought a bit about the structure of AES and the fact that we're expecting code structure, but there's absolute confusion and absolute diffusion, so that doesn't help us.

Our best bet is either to attack the key, knowing it will probably make human-sense, or to continue looking for clues.

I have to admit, it would be fun to become recognized as the mathematician who provided a practical break for AES for the purposes of a videogame, but I trust that my skills in the area aren't up to match with the mathematicians who've been trying for the past decades.

(That said, I do see a potential 'attack the zeros' vector, and I don't see what's been done to prevent that from working, so I'm tinkering. Unfortunately, that would only enable partial decryption of 'null' characters, which can't be verified unless the code sample has null characters, so it's useless for us anyways)

 

Share this post


Link to post
Share on other sites

Heh, I thought for weeks about the P versus NP problem just for the kicks myself. No dice.

I'm surprised this paper doesn't reference the controversial eXtended Sparse Linearization (XSL) attack. Not sure if that's important or not though.

I don't know if attacking the zeroes matter, but if it does then I should point out that the last bytes at the end of the file immediately before the PKCS #7 padding should be:

00 00 00 00 00 00 00

Being able to guess the key string itself would be great, but if it's a long sentence like the normal PrincessChambers.lua key then we might be in trouble unless it's based on a string in the game or a known incantation.

As for clues, if they exist in the game, they are either truly well hidden, hidden in plain sight, or we overlooked them somehow. Otherwise, there could be clues hiding anywhere, including the following locations:

  • Amnesia Fortnight 2012/2014 material, including the 2012 special edition box set, trailers, documentary, the Hack 'n' Slash prototype and its box art.
  • All marketing material, including the full game press release with the HTTP trace, the ZIP/JPG hybrid teaser puzzle, trailers, the official wiki, the development blog and the official T-shirt.
  • Messages from Noughtceratops's Twitter account.
  • Devs Play season 1 episode 4, including the Zelda IPS patch and the currently-unsolved hacked Zelda cartridge winner puzzle.

Unless Brandon, someone else linked to the game or Double Fine gives us more information, that's what we have to work with.

Share this post


Link to post
Share on other sites

Mmm, as soon as I started to implement AES-256-CBC I realized my mistake.

So first, it adds a roundkey at each cycle, so now our zero is swapped . . . okay, whatever, we can still work with that. 
And then it also performs a substitution, so our zero is swapped again.

Which would all be fine, but then for AES-256, it performs the cycle 14 times. Our zeros won't keep their properties all through that. If it was only the substitution, I could do something, if it was only the addition, I could do something, but both together on multiple cycles means that a zero gets multiply-transformed probably 13 out of 14 times. We require a multiply-transform to work 0 times in order for an attack-the-zeros vector.

The odd number means that there IS a potential miss-in-the-middle attack using an attack-the-zeros vector, but having looked into some more papers, people have 100% tried that, and I think that's actually fully encapsulated by the use of bicliques. Which is handy.

My brain is still chewing on it, but like I said, I'm 100% not as good as, and 200% not as familiar with AES as the mathematicians who've been chewing on it for the last decade plus.
 

Share this post


Link to post
Share on other sites
Posted (edited)

So here's a potentially dumb question.

Say i_x is the xth bit of the AES-256 block input (after CBC XOR in our case), k_x the xth bit of the key, and c_x the xth bit of the ciphertext block output.

What would the functions c_x(i,k) and i_x(c,k) look like?

Edited by SmashManiac

Share this post


Link to post
Share on other sites
Posted (edited)

Complete confusion and complete diffusion

Every part of the ciphertext block relies on every letter of plaintext block, (diffusion), and every piece of the key (confusion).

So the key is broken up into 14 round keys using rotations and a substitution table. (For aes 256)

Then we take our block input, add the 1st roundkey to it, make substitutions, rotate the rows, and mix the columns.

edit: sorry, that entered before I finished. Continuing:

At this point, say, b(1,1), (block input at coordinates (1,1)), is now transformed by factors of: The roundkey portion that corresponds to (1,1), the block input from (2,4), (3,3), and (4,2), and the roundkey portions from those as well.

And the roundkey portions will correspond to different parts of the key.

Now to make the next roundkey, we start XORing against the previous roundkey

And we take our current block-in-memory, add the 2nd round key, make substitutions, rotate the rows, and mix the columns.

So, b(1,1) was transformed by b(1,1), b(2,4), b(3,3), b(4,2), and now it's going to be effected by block-in-memory (1,1), (2,4), (3,3), (4,2), which have each been transformed by their entire columns in the previous step. They are all in different columns.

Which means that b(1,1) has now been transformed by b(1,1), b(1,2), b(1,3), b(1,4), b(2,1), b(2,2), b(2,3), b(2,4), b(3,1), b(3,2), b(3,3), b(3,4), b(4,1), b(4,2), b(4,3), b(4,4) and the corresponding parts of the two roundkeys, which means it has been effected by ALL input, and in AES-256, some of the key. In AES-128, that would be all of the key.

There are now twelve more rounds after this.

If we change just one bit of the input, or one bit of the key, every single bit of the output is effected, (and on average, 50% of them will change).

nb: I've still only done a cursory examination of the algorithm, having never looked at it before, I'm probably still getting details wrong.

Feel free to derive the equation from that all . . . it'll take a lot of tedious work and it won't be helpful. That substitution step will do you dirty.

Edited by 0xffe3

Share this post


Link to post
Share on other sites

Hmm you're right. I read through the entire AES standard, and if we would skip the finite-field multiplicative inverse substitution in the SubBytes step, each output bit could be represented as a series of XOR operations.

I have no idea what a formula for this multiplicative inverse would look like... if one can even be written. :S

Share this post


Link to post
Share on other sites

It's what we call  a 'non-linear algorithm' . . . it can't be represented by normal means without the use of "if-then" statements, so it doesn't follow a linear path and can't be (easily) expressed as a single equation.

(Many of them can theoretically be expressed as single equations through very hack-y means that wouldn't help to simplify the problem any)

You can see why a non-linear step is considered essential for cryptographic purposes. It just thwarts analysis by making the algorithm itself the simplest way to express the transformation.

If you want to understand some of the theoretical concerns because ciphers like AES better, I can skeleton out a brief road map?

First: if you don't already have a basic understanding of substitution ciphers, how to solve and etc. play with a tool like http://rumkin.com/tools/cipher/cryptogram.php, and some cryptograms you can find anywhere on the web.

Second: One of the earliest ciphers which demonstrates an understanding of confusion and diffusion is the Hill Cipher. It doesn't contain any non-linear steps, and it does contain some linear algebra, so it's an excellent starting point into modern cryptography. I would start with 2-letter and 3-letter Hill Ciphers, and then extend your learned techniques to 6-letter Ciphers.

Once you know how to crack that, consider a block cipher version of it. Say, a 2-letter version. First, the message is padded out until the length is a power of 2. Then each pair is encoded as normal. Then we go up a layer and encode each pair of pairs, pairwise. Then we go up a layer, and encode each pair of (pair of pairs), (pair of pair) wise. In the end that'll be log(n)*n encodings, and every cipher-letter will depend on every plaintext-letter.

Fourth, then start on Hill ciphers as they are meant to be used: In combination with other techniques. In the original patent, Hill mentions using a non-linear substitution cipher on the text before and after the application of the Hill Cipher . . . so it appears he saw it as providing diffusion to the ciphertext. Diffusion and Confusion would not be named terms until partway through WWII, however.

Fifth, start on now-broken block ciphers, like some early Feistal ciphers. Those will also contain non-linear steps, and some that are 'broken' are still only 'academically broken' in the sense that the breaks are still non-practical to ever realistically attempt.

By that point, you will have a workable understanding of each component of the AES cipher, and why it's constructed the way it is. The roundkeys, the rotations, the non-linear step, etc., everything is designed to bring a particular strength to the algorithm, and it's very little more than plug-together in that respect . . . that it was a top contender in encryption that was heavily analysed by many people, and many of its other contenders were struck down for discovered or suspected weaknesses, is where its strength comes from. Not from a derivable difficultly value, but from the sense that it was remaining after tough examination that eliminated its competitors.

That all said, do we have the implementation of the AES encryption in the game somewhere? I want to comb through it for differences from other implementations and see if I sniff an implementation weakness.

Share this post


Link to post
Share on other sites

Thanks a lot, I'll take a closer look at those when I have some time.

The AES functions in the game are exposed in the Lua environment through the DFHack object as encipherBuffer and decipherBuffer. Their implementation are in the Hack.exe x86 binary. tjablin apparently did a disassembly, but the code he posted as reference is no longer accessible, and I'm not sure if the C version he wrote is an exact match or not.

Share this post


Link to post
Share on other sites
On 5/30/2018 at 12:37 AM, SmashManiac said:

Thanks a lot, I'll take a closer look at those when I have some time.

The AES functions in the game are exposed in the Lua environment through the DFHack object as encipherBuffer and decipherBuffer. Their implementation are in the Hack.exe x86 binary. tjablin apparently did a disassembly, but the code he posted as reference is no longer accessible, and I'm not sure if the C version he wrote is an exact match or not.

It can still be accessed here: https://bitbucket.org/tjablin/dfhack/src/default/ His version is mostly good except that it does two rounds of decryption when it should only be one due to a bug in the game that caused tjablin's .lua file to be double-encrypted. When I have a chance, I'll post my version which does one round of decryption and is optimized (at least partially) for speed and works on Windows as well. While I tried bruteforcing and used dictionary attacks with it, its most useful function would be to quickly try various passphrases (and variations of them) to see if they are correct without having to open the game to try it manually.

Share this post


Link to post
Share on other sites

I was under the impression that tjablin's posted C code was not actual disassembly, but only reproduced the output? Unless Hack.exe also uses LibTomCrypt?

As the encryption is triggered by entering DRMRoof, the trick to avoid multiple encryption is to not exit DRMRoof while a book is on the pedestal, including with PrincessChambers already there by default.

Share this post


Link to post
Share on other sites

If it successfully decrypts it, then it's a point-for-point copy as far as the algorithm cares.

Share this post


Link to post
Share on other sites

This is going on for so long now.
You guys remember the HL2 Sourcecode leak when it was in development?
At this point, I woudn't be surprised if people try to infect Brandons PC.

Oh man, once (if) this gets solved this will make whoever does it into an instand internet legend for me.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now