[Official Write-up] HITCON CTF 2021 - chaos

Foreword

I planned to go through the details of these challenges about how components interacted with each other. But after seeing the team organizers posts their writeup which is so well organized and detailed I have a different thought. So readers, please refer to their write-up, especially the "challenge architecture" section which is accurate and illustrated. I suggest you to read their article if you'd like to know how to solve these challenges, and back to here if you are interested in knowing things that only the challenge author knows 😉

Before sharing fun facts or intended solutions I have to thank to the co-author of these "chaos" challenges - lyc. lyc also designed a lot crypto challenges for HITCON CTF every year, and without his help I won't have enough ideas or time to design this whole thing.

This year's HITCON CTF I provided several challenges (most in category pwnable and some in reversing), CHAOS was the one I spent lots of time to design and develop. I have released all sources and intended solutions on GitHub: https://github.com/david942j/hitcon-2021-chaos. If you check the commit history you can see there are 110 commits in total and the first one was sent at Nov 1st.

Speaking of time I noticed some teams complained about CHAOS was not released at the beginning of the game - I'm pretty sorry about this 😢. My original intention indeed was make them be released on game start. However we were too busy on preparing other challenges, it was two hours after the game started that I finally finished the exploit scripts for chaos-sandbox (must ensure it's truly exploitable on remote service before releasing it to public!). That was why we released them at the 4th hour of the game. Fortunately they were all solved by at least 2 teams which already reached my expectation.

This challenge set included three problems, and we named them as chaos-firmware, chaos-kernel, and chaos-sandbox.

Their category were marked as [crypto|pwn]+ because some of them were pure pwnables and some of them required both techs and we didn't want them be revealed - the true categories in our mind were "crypto,pwn", "pwn", and "crypto,pwn" for chaos-firmware, kernel, and sandbox, respectively. Turned out for chaos-sandbox a solution without any crypto knowledge existed (I felt I was so dumb when the team organizers told me their solution 😭) so it actually could be a pure pwn challenge, I will talk about what happened here later.

Idea

These challenges wasn't in my problem set for HITCON CTF at the beginning. However in my "thought list" of designing CTF challenges, two thoughts had lain there for a long time. One was "let device firmware signature verification being vulnerable" and another was "do kernel exploit from a device instead of user-space". So if you already know the CHAOS challenges, these two thoughts eventually became chaos-firmware and chaos-kernel, respectively.

The reason I didn't put them into this year's challenges at first was because I didn't know how to turn "let device firmware signature verification being vulnerable" into a challenge, it was more like in cryptanalysis area which I'm not familiar with. And this issue was resolved immediately after I told lyc the idea. The conversation was like

david942j: Hey I have an idea that.. but I don't know how to..

lyc: Let's make them crypto+pwn challenges and I will deal with the crypto part.

Then I was full of confidence that we will make it.

The name

CryptograpHy AcceleratOr Silicon, CHAOS. It was named when we had decided we'd like to make a "cryptography device", I simply checked the dictionary for words start with "C" for crypto and found the word chaos precisely fit our challenges - the teams work on this challenge will feel in chaos 😜

Actually it took us several days to decide to make it a cryptography device. We had considered making a TPU chip with machine learning accelerators because the new Google Tensor chip was recently announced. Other ideas were discarded because they were too complicated. One day I suddenly realized we must have functions embedded in the device "bootloader" that perform the firmware signature verification, why not simply extending the device to support more cryptography utilities? So this is the final decision that to design a device with supporting common hash algorithms and ciphers.

Intended solutions

This section shares our solutions of each challenge, you can find all scripts on my GitHub repo. Again I suggest you to read write-ups from other teams since I won't go through how the challenges work.

chaos-firmware

This part was much easier compare to other two challenges. So the competitors need to find a number N that has its low 128 bytes match a pre-hardcoded public key embedded in the sandbox binary and φ(N) is calculable. The intended solution we gave here was to find N that is a prime so φ(N) is N - 1.

chaos-kernel

With the experience of PoE the challenge I designed for HITCON CTF 2019 with 0 team solved the kernel exploitation, I decided to make my kernel challenges as friendly as possible (well apparently not easier enough but at least I got 2 solves this time).

I commented where the bug was when I developed the kernel driver. You can also check the sources here.

#include "chaos.h"

#define MAILBOX_TIMEOUT_MS 2000
/* BUG: should be "& (CHAOS_QUEUE_SIZE - 1)" to prevent OOB */
#define REAL_INDEX(v) ((v) & ~CHAOS_QUEUE_SIZE)

static inline bool queue_full(u64 head, u64 tail)
{
	return (head ^ tail) == CHAOS_QUEUE_SIZE;
}

static inline u64 queue_inc(u64 index)
{
	return (++index) & ((CHAOS_QUEUE_SIZE << 1) - 1);
}

So an OOB read/write can be achieved if the indexes for accessing response and command queues are large values. My solution was using response queue to leak data on stack to find the addresses of command/response queues and kernel code base, then overwriting modprobe_path the cliché of kernel exploitation.

This bug design was, in my opinion, "practical". From a kernel developer's view, the indexes would never be large values because kernel driver is the only one that manipulates those indexes. However this assumption is totally broken if the attack comes from the device. Most kernel drivers simply fully trust the device they are dealing with, and I say it's an insecure design. I believe in real cases it's totally possible to attack device firmware with normal user privilege and attack back (like a U-turn?) to kernel from the device to achieve privilege escaping.

chaos-sandbox

The bug of this challenge was here:

Buffer THREEFISH_encrypt(const Buffer &key, const Buffer &inb) {
  CHECK(key.size() == threefish::kKeyLength);
  CHECK(inb.size() % sizeof(uint64_t) == 0);
  CHECK(inb.size() <= threefish::kBlockSize); // buggy, should be ==
  Buffer outb(inb.size());
  CHECK(outb.Allocate());
  threefish::encrypt(key.ptr(), key.size(), inb.ptr(), outb.ptr());
  return outb;
}

The assertion checks the input size is less than or equal to threefish::kBlockSize=32. We added similar checks to all encryptions and decryptions but threefish is the only cipher that uses block size 32 while others use 16. The block size difference matters because (gLibc's) ptmalloc uses minimum size equals 24 bytes. To leverage this bug we can pass an input buffer with 24 bytes, and during encryption the next heap chunk's size (8 bytes) will be considered as part of the input and encrypted, similarly the output buffer's next chunk size will be overwritten with the encrypted data. And that's a heap overflow.

So a challenge popped up here - we have input like

[24 controllable bytes][ a heap chunk size ]

are we able to find a key of threefish that make it be encrypted to

[ 24 don't care bytes ][a larger valid size]

?

The answer is no, at least we don't know how to. So lyc and I actually didn't know how to solve our own challenge after we decided to have this bug. We were like, hey the solution space is pretty large so it should be possible to solve.

Two days after, lyc told me he didn't know how to solve this challenge but he came up with an MITM method that achieved a similar result:

1. Choose fixed key1 and key2 (any is fine).
2. encrypt([0..2^32][any 20 bytes][0x21 the next chunk's size], key1)
• collect the 2^32 results of the last 8 bytes after encryption
3. decrypt([0..2^32][any 20 bytes][0x81 the desired large chunk size], key2)
4. Check whether any last 8 bytes in (3.) matches data generated in (2.), if yes we got a solution.

This is a two-step version of the original challenge, we don't know how to make it in one shot so let's use two shots.

We were pretty satisfy with this solution because it mixed crypto and pwn knowledges in a beautiful way.

When this idea of solution was proposed it was not easy to use - at that time the syscall of "register key" and "unregister key" weren't added (we always passed the key, input, output in syscall args), it was hard to arrange heap chunks. To make the challenge easier I decided to add the two syscalls I mentioned above, the purpose was having attackers be able to adjust the heap layouts so the input / output data wouldn't always use the same chunks.

However this decision made a huge impact of what attackers can do. Notice that I used 0x21 as the input's last 8 bytes because that was the only possible chunk size after the input data (which was the output chunk's size). And we needed a larger size such as 0x81 to crack heap allocator and eventually achieve arbitrary write. Therefore I thought MITM method was unpreventable (or maybe crypto experts are able to do it in one shot anyway). But the assumption that the next chunk size is always 0x21 wasn't true anymore after I introduced the key registration methods. And that's why a solution without crypto skills exists - one can carefully arrange heap chunks so that the next chunk size of input has a large size, and perform encryption + decryption with the same key to eventually overwrite the chunk next to output buffer with that large size. This was the solution used by the only two solves from organizers and Balsn.

Conclusion

I'm truly grateful to all teams for working on the challenges (or any challenge designed by me), no matter you solved them or not. All my challenges, it's my own criteria, have to be either a. fun to solve, b. educational, or c. practical. For CHAOS I hope you do feel some of these emotions (but not only in chaos(?)), and learned something after reading writeups of my challenges.

TBH this challenge sets exhausted all my pending ideas for designing CTF challenges, mostly because I rarely played CTFs for years. But it was also a great experience to me for developing this chaos, I'm pretty glad to introduce this to the world.