picoCTF2018: quackme up

問題

問題文

The duck puns continue. Can you crack, I mean quack this program as well? You can find the program in /problems/quackme-up_2_bf9649c854a2615a35ccdc3660a31602 on the shell server.

問題概要

  • x86のELFファイルが与えられる.

解答例

指針

  • 置換表を作る

解説

まずは, wget で問題ファイルを Dowlonad.

$ wget --no-check-certificate https://2018shell.picoctf.com/static/2bc85a4cb3e4366183c37ec9146a9d05/main

file コマンドでファイルの種類を確かめる.

$ file main
main: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=7c2079a36a5c93cd78e2977b12e53d600f4c3521, not stripped

x86のELFファイルだった.

実行権限を付与して実行してみる.

$ chmod +x main
$ ./main
We're moving along swimmingly. Is this one too fowl for you?
Enter text to encrypt: hoge
Here's your ciphertext: 90 E0 60 40
Now quack it! : 11 80 20 E0 22 53 72 A1 01 41 55 20 A0 C0 25 E3 35 40 65 95 75 00 30 85 C1
That's all folks.

文字列を入力として与えると, それを暗号化した Bytes 列が表示され, おそらくは, flag を暗号化したであろう暗号文が与えられた.

文字列の長さから, 一文字ずつ暗号化されていると推測し, 以下のようにして置換表を作ってみた.

$ ./main
We're moving along swimmingly. Is this one too fowl for you?
Enter text to encrypt: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}_
Here's your ciphertext: 00 30 20 50 40 70 60 90 80 B0 A0 D0 C0 F0 E0 11 01 31 21 51 41 71 61 91 81 B1 02 32 22 52 42 72 62 92 82 B2 A2 D2 C2 F2 E2 13 03 33 23 53 43 73 63 93 83 B3 15 05 35 25 55 45 75 65 95 85 A1 C1 E3
Now quack it! : 11 80 20 E0 22 53 72 A1 01 41 55 20 A0 C0 25 E3 35 40 65 95 75 00 30 85 C1
That's all folks.

この置換表をもとに, 暗号文を復号してみる.

  • solver (Python3)
#!/usr/bin/env python3

cipher = "11 80 20 E0 22 53 72 A1 01 41 55 20 A0 C0 25 E3 35 40 65 95 75 00 30 85 C1"
table = {}
s = list("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}_")
enc = "00 30 20 50 40 70 60 90 80 B0 A0 D0 C0 F0 E0 11 01 31 21 51 41 71 61 91 81 B1 02 32 22 52 42 72 62 92 82 B2 A2 D2 C2 F2 E2 13 03 33 23 53 43 73 63 93 83 B3 15 05 35 25 55 45 75 65 95 85 A1 C1 E3"

for (s1, s2) in zip ( s, enc.split()):
    table[s2] = s1

print("".join( [table[x] for x in cipher.split()] ))
  • 実行結果
$ python solve.py
picoCTF{qu4ckm3_2e786ab9}

たいした解析をせずに解けてしまった.

flag: picoCTF{qu4ckm3_2e786ab9}

せっかくなので, Cutter を使ってバイナリを解析していく.

main のデコンパイル結果.

undefined4 main(void)
{
    char *s;
    undefined4 arg_ch;
    int32_t var_10h;
    int32_t var_ch;
    int32_t var_4h;
    
    puts("We\'re moving along swimmingly. Is this one too fowl for you?");
    printf("Enter text to encrypt: ");
    s = (char *)read_input();
    arg_ch = encrypt(s);
    printf("Here\'s your ciphertext: ");
    print_hex(s, arg_ch);
    printf("Now quack it! : %s\n", _encryptedBuffer);
    puts("That\'s all folks.");
    return 0;
}

文字列 s を受け取り, encrypt(s) を出力し, _encryptedBuffer を出力している.

_encryptedBufferencrypt() により暗号化された文字列と推測した. 次に, encrypt() を解析してみる.

  • Decompile code
int32_t encrypt(char *s)
{
    uint8_t uVar1;
    char cVar2;
    int32_t iVar3;
    int32_t var_10h;
    undefined4 var_ch;
    
    iVar3 = strlen(s);
    var_10h = 0;
    while (var_10h < iVar3) {
        uVar1 = rol4((int32_t)s[var_10h]);
        cVar2 = ror8((int32_t)(char)(uVar1 ^ 0x16));
        s[var_10h] = cVar2;
        var_10h = var_10h + 1;
    }
    return iVar3;
}

このコードは下記のコードと概ね同じである.

int encrypt(char *s) {
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    char x = rol4(s[i]);
    char y = ror8(x ^ 0x16);
    s[i] = y;
  }
  return len;
}

rol4, rol8 も調べる.

  • role4
uint32_t rol4(int32_t arg_8h)
{
    int32_t var_14h;
    int32_t var_1h;
    
    return (uint32_t)(uint8_t)((uint8_t)arg_8h << 4 | (uint8_t)arg_8h >> 4);
}

左右に4つビットシフトした者同士を, ビットごとの OR をとっている.

  • role8
uint32_t ror8(int32_t arg_8h)
{
    int32_t var_14h;
    int32_t var_1h;
    
    return arg_8h & 0xff;
}

0xff と ビットごとに AND をとっている. (下位1Byteを取り出している)

したがって, encrypt は全体として, 下記のようなことをしている.

int encrypt(char *s) {
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    char x = (s[i] << 4) | (s[i] >> 4);
    char y = (x ^ 0x16) & 0xff;
    s[i] = y;
  }
  return len;
}

一文字ごと全探索して, encrypt と同様の処理をして, _encryptedBuffer と等しくなるものを探せば良い.

import string

cipher = ("11 80 20 E0 22 53 72 A1 01 41 55 20 A0 C0 25 E3 35 40 65 95 75 00 30 85 C1").split()

def encrypt(c):
    x = (ord(c) << 4) | (ord(c) >> 4)
    y = (x^0x16) & 0xff
    return y

flag = ""
for c in cipher:
    num_c = int(c, 16)
    for cand in string.printable:
        if encrypt(cand) == num_c:
            flag += cand
            break

print(flag)
  • 実行結果
$ python solve.py
picoCTF{qu4ckm3_2e786ab9}

flag: picoCTF{qu4ckm3_2e786ab9}