Asian Cyber Security Challenge

問題ファイル: acsc-challenges-2021-public/crypto/wonderful_hash/distfiles at main · acsc-org/acsc-challenges-2021-public

TL;DR

元のコマンドと同じハッシュ値となるコマンドを送ると実行してくれる問題
一見原像攻撃に見えるが、ハッシュの構造から十分大きい候補から衝突ペアを見つければ良いので誕生日攻撃が有効
少なくない制約を掻い潜ってcat flagするようなコマンドを構成する

Prerequisite

誕生日攻撃

Writeup

次のようなスクリプトが動いている

import os
import string
from Crypto.Cipher import AES, ARC4, DES

BLOCK = 16


def bxor(a, b):
  res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
  return bytes(res)


def block_hash(data):
  data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
  data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
  data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
  return data[:-2]


def hash(data):
  length = len(data)
  if length % BLOCK != 0:
    pad_len = BLOCK - length % BLOCK
    data += bytes([pad_len] * pad_len)
    length += pad_len
  block_cnt = length // BLOCK
  blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
  res = b"\x00" * BLOCK
  for block in blocks:
    res = bxor(res, block_hash(block))
  return res


def check(cmd, new_cmd):
  if len(cmd) != len(new_cmd):
    return False
  if hash(cmd) != hash(new_cmd):
    return False
  for c in new_cmd:
    if chr(c) not in string.printable:
      return False
  return True


cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
       b"our days, some of them have excelent tasks, but in most cases "
       b"they're forgotten just after the CTF finished. We decided to make"
       b" some kind of CTF archive and of course, it'll be too boring to "
       b"have just an archive, so we made a place, where you can get some "
       b"another CTF-related info - current overall Capture The Flag team "
       b"rating, per-team statistics etc'")


def menu():
  print("[S]tore command")
  print("[E]xecute command")
  print("[F]iles")
  print("[L]eave")
  return input("> ")


while True:
  choice = menu()
  if choice[0] == "S":
    new_cmd = input().encode()
    if check(cmd, new_cmd):
      cmd = new_cmd
    else:
      print("Oops!")
      exit(1)
  elif choice[0] == "E":
    os.system(cmd)
  elif choice[0] == "F":
    os.system(b"ls")
  elif choice[0] == "L":
    break
  else:
    print("Command Unsupported")
    exit(1)

任意のコマンドを登録して実行出来るらしいが、元のコマンドと問題で用意されたハッシュ関数を利用したハッシュ値が一致していないと登録が出来ない。lsだけは登録しなくとも実行出来るため、ディレクトリの構成は判明する(実際の問題ではflagというファイルが存在した)。

このハッシュ関数は、入力を16バイトごとに分けて、それぞれに対してblock_hash()という関数に入れた結果の排他的論理和をとっている。この関数は複数のブロック暗号を利用してハッシュ値を計算しているが、最後にDESで暗号化してから末尾2バイトを削っているため、ハッシュ空間は48bitしか無い。競技時間中に48bitの全探索をするのは(クラウド計算資源を大量購入しているとかでない限り)現実的ではないが、衝突ペアを見つけるだけなら、誕生日攻撃によっておよそ24bit程度の総当りで済むため、ご家庭のコンピュータ一台でも十分計算出来るレベルになる。

目標となるのは問題で定義されているcmdと同じハッシュ値を出すコマンドを用意するため、一見原像攻撃のように見えてしまうが、ここで今回のハッシュの構造が活きる。

以下ではcmdをブロックに分割した結果をblocksとおく(実際にソースコードではそう定義されている)。hash()にメッセージmを放り込んだ結果が、blocks内の幾つかのメッセージだけを選んでblock_hash()にかけたものの排他的論理和と一致した場合、メッセージの残りの部分をcmdと一致させることで全体でも同じハッシュ値を得ることが期待出来る。

具体的な図にすると次のようになっている。blocks[i], blocks[j], blocks[k]をそれぞれblock_hash()にかけて排他的論理和をとったものがblock_hash(msg)(ここで簡単のため、msgは16バイトとする)と一致した場合を考える。これは結局block_hash()の衝突ペアを探すことに相当し、強衝突耐性(衝突ペアを見つけられることに対する耐性)は前述の通り破られていることから現実的な計算時間で見つかると考えられる。

ここで、ブロックの順序を変えて排他的論理和をとっても結果は同じであるため、それを並び替えて衝突が発生するブロックとそうでないブロックに分ける。すると、messageの残りのブロックを衝突が発生しないブロックと同じにすれば、hash()に入れた結果も一致する。

original_cmd    replaced_cmd    message
blocks[0]       blocks[i]       msg
blocks[1]       blocks[j]       ???
blocks[2]       blocks[k]       ???
-----------------------------------------------------------------
...             ...             ... (以下全部replaced cmdと同じ)
blocks[i]       blocks[0]
...             ...
blocks[j]       blocks[1]
...             ...
blocks[k]       blocks[2]
...             ...
blocks[26]      blocks[26]

問題は、メッセージの長さがcmdと同じ長さである事を要求されているため、この図の???に相当する、余剰ブロック分をどうするかであるが、同じバイト列の排他的論理和は0になることを利用する。もし、この余剰ブロック部分が偶数個であれば全て同じにすることで排他的論理和が0になる。よってこの部分をpadとおけば、msg || pad || replace_cmd (non collision blocks)のような形のメッセージを用意すれば、cmdと長さが同じでハッシュの衝突が起こると考えられる。

blocksの選び方は$2^{27}$通りと十分な量があるため、選んだブロックをblock_hash()にかけた結果の排他的論理和を保存し、いずれかがhash(msg)と一致するようなmsgを探す。但し、msgを1ブロック(16バイト)とするなら、余剰ブロック部分が偶数個で無くてはならないため、blocksから選んだブロックの数が奇数でなくてはならない。それでも$2^{26}$通りも存在することから、適当にmsgを選んでhash(msg)がどれかと一致している確率はmsgを同程度集めれば、有意な確率で存在すると思われる。

攻撃方法の概念は以上だが、細かい問題として次のようなものが残っている

フラグを入手出来るコマンドの送信
問題側の制限に弾かれないコマンドの送信
探索結果のキャッシュに要する空間計算量

1に関してはcat flag;<junk string>のようなものを送信すれば、cat flagが実行された後に「そんなコマンドは実在しません」と言われるだけなので特に問題は無い。但し、cmdのブロックを一部流用する都合上、次のような問題に引っかかる可能性がある

引用符'が閉じていないことでコマンドが実行出来ない
コマンド中に括弧: ()が存在することでシェルから構文エラーで怒られる

これは、衝突に寄与しない部分のブロックにおいて引用符が偶数個存在するような選び方をすれば良い。そして、それらの引用符の間に括弧が含まれるブロックを入れれば、文字列とみなされてシェルの構文として扱われなくなることからエラーを回避出来る。

(実は最後にこれに気付かず、構成したメッセージが実行出来ずに詰んだと思ったが、運良く引用符が2つ存在してくれたので事なきを得た)

2については「printableな文字のみからなること」と「長さがcmdと一致すること」が要求される。

前者に関しては特に問題はない。cat flag;で9バイトであり、16バイト¹にするには7バイトを埋めるだけだが、printableな文字はシェルが変に解釈しないように記号を除いたとしても26+26+10=62と多く存在し、$62^7 \gg 2^{24}$と候補が莫大な量存在するためどこかで当たると思われる。

長さの問題に関してはcmdと末尾のブロックを一致させ、残りのブロックで衝突ペアを探せば良いだけなのでこちらも特に問題はない(但し探索空間は$2^{25}$ぐらいに落ちる)。

3が一番苦しんだ問題で、blocksの選び方とそれに対応するblock_hash()の排他的論理和を辞書で保存する必要がある。最初はハッシュ値に対してどのインデックスを選んでいたかをリストで保存していたが、これが非常に大きなサイズを要するため、計算中にメモリをアホみたいに食う。さらにそれをキャッシュするためにPickleを使ったが、こいつの容量も大きくなり、保存やロードに時間が掛かる。結局どこのインデックスを用いるかはビット列で管理出来るのでそれに対応する数値で保存する事にした。

以上を解決して次の3つの手順を行ったらフラグを開示出来るコマンドが構成された

blocksの選び方とそれに対応するハッシュの辞書作成 (5分弱)
blocksの部分的な排他的論理和と衝突するバイト列の探索 (最悪50分)
msgの構築

最終的に実行したコマンドは次の通り(↓バッククォートで囲った見た目が悪すぎる)

cat flag;OUBqbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaey're forgotten The Flag (CTF) competitions in our days, some of them have exceTF finished. We decided to make some kind of CTFted info - curre rating, per-team statistics etc'

Code

辞書の作成、衝突の探索、ペイロード構築を1つのスクリプトでコメントアウトを駆使しながらやっているのでクソ汚い。更に衝突の探索には最悪50分ぐらいかかる。

from pwn import process
import os
import string
from Crypto.Cipher import AES, ARC4, DES
from tqdm import tqdm
import pickle

BLOCK = 16


def bxor(a, b):
    res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
    return bytes(res)


def block_hash(data):
    data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
    data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
    data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
    return data[:-2]


def hash(data):
    length = len(data)
    if length % BLOCK != 0:
        pad_len = BLOCK - length % BLOCK
        data += bytes([pad_len] * pad_len)
        length += pad_len
    block_cnt = length // BLOCK
    blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
    res = b"\x00" * BLOCK
    for block in blocks:
        res = bxor(res, block_hash(block))
    return res


def check(cmd, new_cmd):
    if len(cmd) != len(new_cmd):
        return False
    if hash(cmd) != hash(new_cmd):
        return False
    for c in new_cmd:
        if chr(c) not in string.printable:
            return False
    return True


def i_to_bits(i):
    ret = []
    for j in range(26):
        if i & (1 << j):
            ret.append(j)

    return ret


table = string.ascii_letters + string.digits
table_length = len(table)
def get_s(i: int) -> bytes:
    ret = ""
    while i != 0:
        x = i % table_length
        ret = ret + table[x]
        i //= table_length

    return ret.encode()


cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
       b"our days, some of them have excelent tasks, but in most cases "
       b"they're forgotten just after the CTF finished. We decided to make"
       b" some kind of CTF archive and of course, it'll be too boring to "
       b"have just an archive, so we made a place, where you can get some "
       b"another CTF-related info - current overall Capture The Flag team "
       b"rating, per-team statistics etc'")

org_cmd = cmd

data = cmd
length = len(data)
if length % BLOCK != 0:
    pad_len = BLOCK - length % BLOCK
    data += bytes([pad_len] * pad_len)
    length += pad_len
block_cnt = length // BLOCK
blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
hash_blocks = list(map(hash, blocks))
print(len(blocks))

# create dictionary
# d = {}

# for i in tqdm(range(1, 2**25)):
#     idxes = i_to_bits(i)
#     if len(idxes) % 2 == 0:
#         continue
#     h = b"\x00" * 6
#     for j in idxes:
#         h = bxor(h, hash_blocks[j])

#     d[h] = i

# with open("hash_dict", "wb") as f:
#     pickle.dump(d, f)

# exit()

# search collision
# with open("hash_dict", "rb") as f:
#     d = pickle.load(f)

# print("[+] start searching...")
# cmd = b"cat flag;"

# result = (0, b"", [], False)
# for i in tqdm(range(1, 2**26)):
#     m = cmd + get_s(i)
#     length = len(m)
#     if length % BLOCK != 0:
#         pad_len = BLOCK - length % BLOCK
#         m = m + b"a" * pad_len
#     h = hash(m)
#     if h in d:
#         result = (i, m, i_to_bits(d[h]), True)
#         break

# _i, _cmd, l, res = result

# if res:
#     print(_i, _cmd, l)
# else:
#     print("[+] Unlucky...")

# exit()

# exploit
padded = b"a" * 16

i, cmd, l = 18696264, b'cat flag;OUBqbaa', [0, 1, 6, 7, 9, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23]
assert len(blocks) - 1 not in l

assert len(cmd) % BLOCK == 0
print(len(l), l)
add_blocks = []
quote_cnt = 0
quote_block_cnt = 0
cmd = cmd + padded * (len(l) - 1)

for _i, b in enumerate(blocks[:-1]):
    if _i not in l:
        if b"'" in b:
            cmd = cmd + b
        else:
            add_blocks.append(b)


for b in add_blocks:
    cmd = cmd + b

cmd = cmd + blocks[-1]

cmd = cmd[:-15]
print(len(cmd) == len(org_cmd))
print(hash(cmd) == hash(org_cmd))

sc = process(["python3", "chall.py"])
sc.recvuntil(b"> ")
sc.sendline(b"S")
sc.sendline(cmd)
sc.recvuntil(b"> ")
sc.sendline(b"E")
print(sc.recvline())

Flag

ローカルでやっただけ

なお、msgを16バイト「以下」で探索した結果、ハッシュに送り込む際にパディングが発生して、ここがprintableでないため、最初の衝突ペアを見つけた時にコマンドとして無効になって絶望した

Asian Cyber Security Challenge - Wonderful Hash

TL;DR

Prerequisite

Writeup

Code

Flag