Cracker Cavern Reborn 4
Hacking Ⅳ: Loss of integrity
Here’s an excerpt from a chat during the 2019 edition:
<Parzival> according to the achievements PK3 is encryption (again) and 4 is to hack the server (again)
<meep> inb4 the crypto challenge is a weak RSA implementation on gameboy and you have to find the weakness and forge a signature
<ISSOtm> No, not that much xD
although next year…
Well. This is AES and not RSA, this is 2022 and not 2020, however we do have a crypto challenge on our hands here.
Ready? Nah, it’s not that bad.
The NPC can issue you a “silver” certificate, and then appraise it. Your task is to get a “gold” certificate. (Leaving the room “forfeits” the certificate, so the NPC offers you to generate a new one, btw.)
When you request a certificate, a string like
holder=Aelita/type=silver is sent to the server.
You can send custom strings (there don’t seem to be any size limitations), but there are a bunch of restrictions:
- It must be a slash-separated list of
typemust be present and exactly equal to
silver, otherwise the server complains
- Any keys other than
- The string is not trimmed
- Multiple values are ignored
- Any instance of
type=goldanywhere is rejected
…yeah, pretty locked down. And then, the server returns you the certificate… encrypted using AES.
When getting a certificate appraised, you send the encrypted certificate (the ciphertext) to the server, which either tells you that something is wrong with it, or returns the decrypted certificate (the plaintext) if it’s valid.
Yeah. We only get encrypted silver certificates to play with, and we gotta get some gold certificate. Somehow.
A primer on AES
Oh yeah. What is the Advanced Encryption Standard?
Well, I’ll spare you the obligatory Wikipedia link, as we aren’t interested in all of its inner workings here.
AES is what’s called a symmetric encryption protocol: the same key is used for encrypting and decrypting things. (Contrast this to RSA, which is asymmetric, as it employs a public and private key.)
AES allows encrypting 128 bits (16 bytes) using uhhh matrix transforms and uhhhhhhhhhhhhh XOR or something? Yeah, as I said, this is not very important.
What’s important is that:
- Changing one bit in the plaintext will change many in the ciphertext.
- Changing one bit in the ciphertext will cause many bits to be different in the corresponding plaintext.
- Even if you have some plaintext and ciphertext, it’s currently infeasible to recover the key.
So we can basically forget about creating our arbitrary certificates.
So, wat do?
It might be a good time to mention AES modes of operation. See, I mentioned that AES can only work on “blocks” of 16 bytes (128 bits) at once. So how is it used for bigger amounts of data? Simply enough, you slice the data up into 16-byte chunks, and then you encrypt each of them.
The simplest mode of operation is called ECB (Electronic Code Book), where each block is encrypted independently.
Then there is CBC, or Cipher Block Chaining, where the last ciphered block1 is XOR’d to the next block’s plaintext, and that gets ciphered:
There are other modes, but these two are the most common used with AES. We could easily rule out ECB, as swapping two blocks in the ciphertext does not yield a valid message. So it’s AES-CBC, which leaves us with very little control.
…Honestly, we stayed stuck at this point for a while. Until pfero had a breakthrough.
Chapter 8: The Part Where He Has A Breakthrough
We had noticed that changing one byte corrupted not only that block, but also the next one. But how come?
Ooh. He realized that little arrow going from one ciphertext block to the next plaintext block could be our ticket to victory.
See, we have full control over the ciphertext, and the “holder” field is located just before the “type” one. So, the plan is:
- Make the “holder” name a length that aligns
erare on two different blocks.
- We’ll need to “sacrifice” the block just before that; we can simply use part of the holder name, since it doesn’t matter.
Here, “asdf” and “hhhhhh” are used for aligning the
type= (point 1), and the
xxxxxxxxxxxxxxxx is our “sacrificial” block (point 2).
Now, it’s actually as simple as modifying the
xxxx’s ciphertext to transmute the
You can see from the diff (powered and colorized by delta) that we removed the last block (thus truncating the trailing
er), and that the last 4 bytes were changed to… magically give us
Let’s explain those a little better.
We know that the
00000040 block decrypts to something which, when XOR’d with the ciphertext of the
00000030 block, yields
I don’t particularly care about what that something is, I’ll instead use XOR’s properties:
|Original string (ASCII)|
|Target string (ASCII)|
|XOR of the two||0x14||0x06||0x00||0x12|
|With the XOR mask applied||0x84||0xA2||0x62||0x9E|
…and if you look again at the demonstration, this is exactly what the modified
00000030 block contains!
Here is a more thorough explanation, if you are still having trouble:
s0be the original string,
s1the target string,
b1the new one. Additionally, let
pbe the result of decrypting the
We know that
s0 = p ^ b0(from the decryption diagram above), and we want
s1 = p ^ b1.
We can substitute the variables in
s0 ^ s1, which yields
s0 ^ s1 = (p ^ b0) ^ (p ^ b1).
XOR is commutative (
a ^ b = b ^ a) and associative (
a ^ (b ^ c) = (a ^ b) ^ c), so we get
s0 ^ s1 = b0 ^ b1 ^ p ^ p.
a ^ a = 0and
b ^ 0 = b, this can be simplified to
s0 ^ s1 = b0 ^ b1.
We can then XOR both sides with
b0 ^ (s0 ^ s1) = b0 ^ b0 ^ b1, which gives us the solution
b1 = b0 ^ (s0 ^ s1)!
Anyway. As you have seen in the demonstration, this has the server return us a nice lil’ gold certificate—whoever the holder is, we don’t really care :32
…wait, it’s already over?
Well, the first plaintext block being the first, there is no “previous encrypted block”, so instead 16 bytes known as the “initialisation vector” (IV) are used. ↩
Actually, we do care that the corrupted
xxxxxxxxxxxxxblock doesn’t accidentally decrypt to any
/or other “bad” characters. This can be “fixed” by fiddling with the first 6 bytes until this is no longer the case. Those bytes are XOR’d onto the
hin the holder name, but those can be trashed just fine as well. ↩