• Content count

  • Joined

  • Last visited

About 0xffe3

  • Rank
  1. Secret room

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

    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.
  3. Secret room

    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.
  4. Secret room

    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.
  5. Secret room

    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)
  6. Secret room

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

    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?