ångstromCTF 2019 Write-up - s4tt01237’s diary

はじめに
成績
Misc
- IRC [10pts, 895solves]
- Survey [10pts, 363solves]
Crypto
Rev
まとめ
チームメンバのWrite-up

はじめに

2019/04/20 ~ 2019/04/25 に開催されたångstromCTFにチーム(NekoChanNano!)で参加しました．
今回は自分が解いた問題についてのWrite-upです．

成績

59位でした (1問以上解いた1374チーム中)．

f:id:satto1237:20190426201003p:plain

Misc

IRC [10pts, 895solves]

We have an IRC channel, #angstromctf on freenode! Join us to ask questions, have fun, and get a flag.

アプローチ：読む

actf{like_discord_but_worse}

Survey [10pts, 363solves]

We have a short survey for you to fill out for a flag! Even though it's a single challenge, we encourage every individual to submit a response.

アプローチ：wget

アンケートに回答するとflagをもらえるみたいですが回答しなくてもとれます．

f:id:satto1237:20190426202116p:plain

> wget https://forms.gle/72by8ViMv3yM9JeU6
--2019-04-26 20:22:28--  https://forms.gle/72by8ViMv3yM9JeU6
Resolving forms.gle (forms.gle)... 151.101.65.195, 151.101.1.195
Connecting to forms.gle (forms.gle)|151.101.65.195|:443... connected.
HTTP request sent, awaiting response... 302 Found
Location: https://docs.google.com/forms/d/e/1FAIpQLSfGgWe6Gl1mcyOnD59NfT2luWa4N5fVKyhlTGszZ1FZyT_stw/viewform?usp=send_form [following]
--2019-04-26 20:22:29--  https://docs.google.com/forms/d/e/1FAIpQLSfGgWe6Gl1mcyOnD59NfT2luWa4N5fVKyhlTGszZ1FZyT_stw/viewform?usp=send_form
Resolving docs.google.com (docs.google.com)... 172.217.31.174
Connecting to docs.google.com (docs.google.com)|172.217.31.174|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: unspecified [text/html]
Saving to: `72by8ViMv3yM9JeU6'

72by8ViMv3yM9JeU6                         [ <=>                                                                    ] 441.15K  --.-KB/s    in 0.1s

2019-04-26 20:22:29 (4.22 MB/s) - `72by8ViMv3yM9JeU6' saved [451738]

> grep "actf{" 72by8ViMv3yM9JeU6
,["Thank you for completing our survey! We hope you enjoyed ångstromCTF, and as always: actf{we_hope_to_see_you_next_year}",0,0,0,0]

actf{we_hope_to_see_you_next_year}

Crypto

Classy Cipher [20pts, 718solves]

Every CTF starts off with a Caesar cipher, but we're more classy.

from secret import flag, shift

def encrypt(d, s):
    e = ''
    for c in d:
        e += chr((ord(c)+s) % 0xff)
    return e

assert encrypt(flag, shift) == ':<M?TLH8<A:KFBG@V'

アプローチ：シフトを探索

シフト数が不明ですがflagフォーマットをベースに全探索すれば解けます．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# :<M?TLH8<A:KFBG@V
# actf{***********}

def encrypt(d, s):
    e = ''
    for c in d:
        e += chr((ord(c)+s) % 0xff)
    return e

def searchShift():
    flag = 'actf{'

    for shift in range(0xff):
        enc = encrypt(flag, shift)
        if enc == ':<M?T':
            print(shift)
            return shift

if __name__ == '__main__':
    enc_flag = ':<M?TLH8<A:KFBG@V'
    shift = searchShift()
    dec_flag = ''

    for e in enc_flag:
        dec_flag += chr(ord(e) - shift + 0xff)

    print(dec_flag)

> python solve.py
216
actf{so_charming}

actf{so_charming}

Really Secure Algorithm [30pts, 548solves]

I found this flag somewhere when I was taking a walk, but it seems to have been encrypted with this Really Secure Algorithm!

p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
e = 65537
c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349

アプローチ：普通にRSA暗号を復号する

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import gmpy
import binascii

if __name__ == '__main__':
    p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
    q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
    e = 65537
    c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349
    n = p * q

    l = gmpy.lcm(p-1, q-1)
    gcd, u, v = gmpy.gcdext(e, l)

    while u < 0:
        u += l

    m = pow(c, u, n)
    print(m)
    print(binascii.unhexlify(hex(m)[2:]))

> python solve.py
172070576318285777902351017014850513943749891499547486454156569029770767741
b'actf{really_securent_algorithm}'

actf{really_securent_algorithm}

Half and Half [50pts, 348solves]

Mm, coffee. Best served with half and half!

from secret import flag

def xor(x, y):
    o = ''
    for i in range(len(x)):
        o += chr(ord(x[i])^ord(y[i]))
    return o

assert len(flag) % 2 == 0

half = len(flag)//2
milk = flag[:half]
cream = flag[half:]

assert xor(milk, cream) == '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'

アプローチ：排他的論理和とエスパー

encoderを読むと次のことが分かります．

flagを分割して1文字ずつ排他的論理和をとっている
排他的論理和をとった結果は\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"
flag長は24

以上を考慮するとflagフォーマットから

milk  -> actf{*******
cream -> ***********}

milk  -> actf{******_
cream -> taste******}

となります．

次に6文字の単語を推測しなければいけませんが，ここは問題文にあるcoffeeが入ります(エスパー)．

# -*- coding: utf-8 -*-
#!/usr/bin/env python3

def decrypt(known_flag, mc_xor):
    partial_flag = ''
    for f, x in zip(known_flag, mc_xor):
        partial_flag += chr(ord(f) ^ x)

    return partial_flag

if __name__ == '__main__':

    partial_flag1 = decrypt('}',b'"')
    partial_flag2 = decrypt('actf{', b'\x15\x02\x07\x12\x1e')
    partial_flag3 = decrypt('coffee', b'\x100\x01\t\n\x01')

    print('actf{' + 'coffee' + partial_flag1 + partial_flag2 + partial_flag3 + '}')

> python solve.py
actf{coffee_tastes_good}

actf{coffee_tastes_good}

Runes [70pts, 235solves]

The year is 20XX. ångstromCTF only has pwn challenges, and the winner is solely determined by who can establish a socket connection first. In the data remnants of an ancient hard disk, we've recovered a string of letters and digits. The only clue is the etching on the disk's surface: Paillier.

n: 99157116611790833573985267443453374677300242114595736901854871276546481648883
g: 99157116611790833573985267443453374677300242114595736901854871276546481648884
c: 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

アプローチ：Paillier暗号

Paillier暗号については以下を参照してください(詳しくまとめられています)．

elliptic-shiho.hatenablog.com

256bit程度のnが与えられますがFacotrDBでサクッと素因数分解できます．

あとはやるだけです．

# -*- coding: utf-8 -*-
#!/usr/bin/env python3

import gmpy
import binascii

def L(u,n):
    return (u-1) // n

def decrypt():
    n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
    g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
    c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869
    p = 310013024566643256138761337388255591613
    q = 319848228152346890121384041219876391791

    lmd = gmpy.lcm(p-1, q-1)
    m = L(pow(c, lmd, n*n), n) * gmpy.invert(L(pow(g, lmd, n*n), n), n) % n

    return m

if __name__ == '__main__':

    m = decrypt()
    print(binascii.unhexlify(hex(m)[2:]))

> python solve.py
b'actf{crypto_lives}'

actf{crypto_lives}

Rev

Intro to Rev [10pts, 961solves]

Many of our problems will require you to run Linux executable files (ELFs). This problem will help you figure out how to do it on our shell server. Use your credentials to log in, then navigate to /problems/2019/intro_to_rev. Run the executable and follow its instructions to get a flag!

アプローチ：問題をよむ

> ./intro_to_rev
Welcome to your first reversing challenge!

If you are seeing this, then you already ran the file! Let's try some input next.
Enter the word 'angstrom' to continue:
angstrom
Good job! Some programs might also want you to enter information with a command line argument.

When you run a file, command line arguments are given by running './introToRev argument1 argument2' where you replace each argument with a desired string.

To get the flag for this problem, run this file again with the arguments 'binary' and 'reversing' (don't put the quotes).

> ./intro_to_rev binary reversing
Welcome to your first reversing challenge!

If you are seeing this, then you already ran the file! Let's try some input next.
Enter the word 'angstrom' to continue:
angstrom
Good job! Some programs might also want you to enter information with a command line argument.

When you run a file, command line arguments are given by running './introToRev argument1 argument2' where you replace each argument with a desired string.

Good job, now go solve some real problems!
actf{this_is_only_the_beginning}

actf{this_is_only_the_beginning}

I Like It [40pts, 606solves]

Now I like dollars, I like diamonds, I like ints, I like strings. Make Cardi like it please.

> file i_like_it
i_like_it: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=5b91e9b31dffd010d9f32b21580ac3675db92a62, not stripped

アプローチ：2次方程式をとく？

> ./i_like_it
I like the string that I'm thinking of: 
aaaa
Cardi don't like that.

とりあえずidaで開くと

f:id:satto1237:20190427191913p:plain

f:id:satto1237:20190427191942p:plain

次のことが分かります．

I like the string that I'm thinking of: には okrrrrrrr
以下の条件を満たす2つの整数を入力する
- $a + b = 136$
- $a \times b = 3783$
- $a \lt b$

したがって，2つの整数については $x^{2} - 136x + 3783 = 0$ の解を入力すればいいことになります．

> ./i_like_it
I like the string that I'm thinking of: 
okrrrrrrr
I said I like it like that!
I like two integers that I'm thinking of (space separated): 
39 97
I said I like it like that!
Flag: actf{okrrrrrrr_39_97}

actf{okrrrrrrr_39_97}

One Bite [60pts, 521solves]

Whenever I have friends over, I love to brag about things that I can eat in a single bite. Can you give this program a tasty flag that fits the bill?

> file one_bite
one_bite: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=1378c7ef8cdf59c2cbe4d84274295b2567a09e91, not stripped

アプローチ：XOR

> ./one_bite 
Give me a flag to eat: 
aaaaaaaaaa
That didn't taste so good :(

とりあえずidaで開くと

f:id:satto1237:20190427194721p:plain

次のことが分かります．

入力文字列を1文字ずつ0x3cとXORしてる
XORした結果が]_HZGUcHTURWcUQc[SUR[cHSc^YcOU_WAになるのがflag

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def solve():
    target = ']_HZGUcHTURWcUQc[SUR[cHSc^YcOU_WA'
    flag = ''
    for x in target:
        flag += chr(ord(x) ^ 0x3c)

    print(flag)

if __name__ == '__main__':
    solve()

> python solve.py
actf{i_think_im_going_to_be_sick}

actf{i_think_im_going_to_be_sick}

High Quality Checks [110pts, 268solves]

After two break-ins to his shell server, kmh got super paranoid about a third! He's so paranoid that he abandoned the traditional password storage method and came up with this monstrosity! I reckon he used the flag as the password, can you find it?

> file high_quality_checks
high_quality_checks: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=e7556b55e0c73b4de8b3f387571dd59c3535a0ee, not stripped

アプローチ：Ghidraでデコンパイル

とりあえずidaで開くと
f:id:satto1237:20190427201745p:plain f:id:satto1237:20190427200107p:plain

次のことが分かります．

flag長は19文字
check関数はflagの判定を行っている
check関数の動作を理解するにはやる気と根気と時間が必要

ゆとりなのでGhidraでデコンパイルします．

f:id:satto1237:20190427201552p:plain

undefined8 check(char *pcParm1)

{
  int iVar1;
  
  iVar1 = d(pcParm1 + 0xc);
  if ((((((iVar1 != 0) && (iVar1 = v((ulong)(uint)(int)*pcParm1), iVar1 != 0)) &&
        (iVar1 = u((ulong)(uint)(int)pcParm1[0x10],(ulong)(uint)(int)pcParm1[0x11],
                   (ulong)(uint)(int)pcParm1[0x11]), iVar1 != 0)) &&
       ((iVar1 = k((ulong)(uint)(int)pcParm1[5]), iVar1 == 0 &&
        (iVar1 = k((ulong)(uint)(int)pcParm1[9]), iVar1 == 0)))) &&
      ((iVar1 = w(pcParm1 + 1), iVar1 != 0 &&
       ((iVar1 = b(pcParm1,0x12), iVar1 != 0 && (iVar1 = b(pcParm1,4), iVar1 != 0)))))) &&
     ((iVar1 = z(pcParm1,0x6c), iVar1 != 0 && (iVar1 = s(pcParm1), iVar1 != 0)))) {
    return 1;
  }
  return 0;
}

大分読みやすくなりましたね．
check関数内の各関数の動作を読み解いてflag:*******************を復元していきます(文字は0-indexで数えます)．

`d`関数

ulong d(int *piParm1)

{
  return (ulong)(*piParm1 == 0x30313763);
}

check関数でflagの12文字目以降を渡しているのでflagは************c710***となります．

`n`関数

ulong n(int iParm1)

{
  return (ulong)(uint)(iParm1 >> 1);
}

引数を1bit右シフトしてます．

`v`関数

ulong v(byte bParm1)

{
  int iVar1;
  
  iVar1 = n(0xac);
  return (ulong)((int)(char)(bParm1 ^ 0x37) == iVar1);
}

(0xac >> 1) ^ 0x37 = 97なのでflagはa***********c710***となります．

`o`関数

ulong o(char cParm1)

{
  int local_c;
  
  if (cParm1 < 'a') {
    local_c = (int)cParm1 + -0x30;
  }
  else {
    local_c = (int)cParm1 + -0x57;
  }
  local_c = (int)cParm1 * 0x100 + local_c;
  return (ulong)(uint)(local_c * 0x10001);
}

文字を引数として渡すと変換結果(数値)を返してくれます．

`u`関数

undefined8 u(char cParm1,char cParm2)

{
  int iVar1;
  
  iVar1 = n(0xdc);
  if (((int)cParm1 == iVar1) && (iVar1 = o((ulong)(uint)(int)cParm2), iVar1 == 0x35053505)) {
    return 1;
  }
  return 0;
}

check関数ではu関数の引数としてflagの16文字目と17文字目を渡しています．

n(oxdc)は110なのでflagの16文字目はnとなることが分かり，o関数の返り値が0x35053505になる文字は5なのでflagの17文字目は5となります(a***********c710n5*)．

`k`関数

ulong k(char cParm1)

{
  int iVar1;
  
  iVar1 = o((ulong)(uint)(int)cParm1);
  return (ulong)(iVar1 != 0x660f660f);
}

check関数ではflagの5文字目と9文字目を引数としてk関数に渡しています．
o関数が0x660f660になる文字はfなのでflagはa****f***f**c710n5*となります．

`w`関数

ulong w(char *pcParm1)

{
  return (ulong)((int)*pcParm1 + (int)pcParm1[2] * 0x10000 + (int)pcParm1[1] * 0x100 == 0x667463);
}

check関数ではflagの1文字目以降を引数としてw関数に渡しています．
0x667463はctfなのでflagはactf*f***f**c710n5*となります．

`e`関数

ulong e(int iParm1)

{
  uint uVar1;
  
  uVar1 = (uint)(iParm1 >> 0x1f) >> 0x1e;
  uVar1 = (iParm1 + uVar1 & 3) - uVar1;
  return (ulong)(uint)((int)(uVar1 + (uVar1 >> 0x1f)) >> 1);
}

引数に対する変換結果を返してくれます．

`b`関数

ulong b(long lParm1,uint uParm2)

{
  char cVar1;
  int iVar2;
  int iVar3;
  
  cVar1 = *(char *)(lParm1 + (long)(int)uParm2);
  iVar2 = n(0xf6);
  iVar3 = e((ulong)uParm2);
  return (ulong)((int)cVar1 == iVar3 * 2 + iVar2);
}

check関数ではflagと数値(0x12,4)を引数としてb関数に渡しています．
引数が0x12の場合は18文字目が}になることが分かり，引数が4の場合は4文字目が{になることが分かります．そのためflagはactf{f***f**c710n5}となります．

`z`関数

undefined8 z(long lParm1,char cParm2)

{
  char cVar1;
  int iVar2;
  char local_17;
  char local_16;
  uint local_14;
  
  local_17 = 0;
  local_16 = 0;
  local_14 = 0;
  while ((int)local_14 < 8) {
    cVar1 = (char)(((int)cParm2 & 1 << ((byte)local_14 & 0x1f)) >> ((byte)local_14 & 0x1f));
    if ((local_14 & 1) == 0) {
      local_16 = local_16 +
                 (char)((int)cVar1 << ((byte)((int)(local_14 + (local_14 >> 0x1f)) >> 1) & 0x1f));
    }
    else {
      local_17 = local_17 +
                 (char)((int)cVar1 << ((byte)((int)(local_14 + (local_14 >> 0x1f)) >> 1) & 0x1f));
    }
    local_14 = local_14 + 1;
  }
  if ((((*(char *)(lParm1 + (long)local_17) == 'u') &&
       (cVar1 = *(char *)(lParm1 + (long)local_17 + 1), iVar2 = n(0xdc), (int)cVar1 == iVar2)) &&
      (cVar1 = *(char *)(lParm1 + (long)local_16), iVar2 = n(0xea), (int)cVar1 == iVar2)) &&
     (*(char *)(lParm1 + (long)local_16 + 1) == 'n')) {
    return 1;
  }
  return 0;
}

一見ややこしい処理をしているように感じますが引数が0x6cなのでflagの6,7,10,11文字目がそれぞれu,n,u,nになっているか確認しているだけです．
そのためflagはactf{fun*func710n5}となります．

`s`関数

ulong s(long lParm1)

{
  int iVar1;
  int local_10;
  int local_c;
  
  local_10 = 0;
  local_c = 0;
  while (local_c < 0x13) {
    iVar1 = o((ulong)(uint)(int)*(char *)(lParm1 + (long)local_c));
    if (iVar1 == 0x5f2f5f2f) {
      local_10 = local_10 + local_c + 1;
    }
    local_c = local_c + 1;
  }
  return (ulong)(local_10 == 9);
}

flagの8文字目を引数としたo関数の返り値が0x5f2f5f2fになっていればいいことが分かります．
o関数の返り値が0x5f2f5f2fになる文字は_なので最終的なflagはactf{fun_func710n5}となります．

actf{fun_func710n5}

まとめ

Crypto担当なのにCrypto全く解けなくて申し訳ない😢
就活のせいでまともに参加できなくて申し訳ない😢
簡単な問題しか解けないのでWrite-up読んで勉強する
今更感あるけどGhidraすごくないですか？

チームメンバのWrite-up

#angstromCTF の「Chain of Rope」の解き方です（ROP無し） pic.twitter.com/ZmXVpcq1OE
— デンパ (@ousanko) 2019年4月25日

PIE Shopの解答です #angstromCTF pic.twitter.com/3hxI5jnUsX
— デンパ (@ousanko) 2019年4月25日

madousho.hatenadiary.jp

szarny.hatenablog.com

はじめに

成績

Misc

IRC [10pts, 895solves]

Survey [10pts, 363solves]

Crypto

Classy Cipher [20pts, 718solves]

Really Secure Algorithm [30pts, 548solves]

Half and Half [50pts, 348solves]

Runes [70pts, 235solves]

Rev

Intro to Rev [10pts, 961solves]

I Like It [40pts, 606solves]

One Bite [60pts, 521solves]

High Quality Checks [110pts, 268solves]

d関数

n関数

v関数

o関数

u関数

k関数

w関数

e関数

b関数

z関数

s関数

まとめ

チームメンバのWrite-up

`d`関数

`n`関数

`v`関数

`o`関数

`u`関数

`k`関数

`w`関数

`e`関数

`b`関数

`z`関数

`s`関数