justCTF2020 - That's not crypto

問題概要

That's not crypto
This is very simple RE task, but you may need some other skills as well. :)

https://ams3.digitaloceanspaces.com/justctf/11456603-38e8-4b10-9863-296fc0cf0342/checker.pyc

単純なRevではなく、タイトル「That's not crypto」からCryptoも入っているんでしょうね。

解説

pycの解読

まずは渡されたpycについて調べます。pycについて注意する点は「特定のバージョンでしか実行できない」です。pycの最初4byteは「マジックナンバー」と呼ばれ、Pythonバージョン毎に異なる&&バージョンが異なると実行不可能です。checker.pycのマジックナンバーは\x33\x0d\x0d\x0aで、Python3.6がこれに該当します（ここはググりました）。

Python3.6で実行すると、FLAGの入力を求められ、適当に入力するとIncorrectという趣旨の出力がされました。この辺りCryptoゾーンっぽさがあります。

pycの解読については過去にqiita記事で解説しているのですが、そもそもこのプログラムの実行結果はかなりPythonコードに落としやすく、自動化出来そうなものです。disassemble出来ませんか？ということで、調べると、(uncompyle6)[https://pypi.org/project/uncompyle6/]というモジュールが見つかり、今回はこれで完全に復元出来ました。ざっくり以下のようなコードになります。

from random import randint

def make_correct_array(s):
  from itertools import accumulate
  s = map(ord, s)
  s = accumulate(s)
  return [x * 69684751861829721459380039 for x in s]

def validate(a, xs):
  
  def poly(a, x):
    value = 0
    for ai in a:
      value *= x
      value += ai

    return value

  if len(a) != len(xs) + 1
    return False
  else:
    for x in xs:
      value = poly(a, x)
      if value != 24196561:
        return False
    return True

if __name__ == '__main__':
  a = [...(数値の配列)]
  a = [ai * 4919 for ai in a]
  flag_str = input('flag: ').strip()
  flag = make_correct_array(flag_str)
  if validate(a, flag):
    print('Yes, this is the flag!')
    print(flag_str)
  else:
    print('Incorrect, sorry. :(')

さて、ここからCryptoパートですね。

フラグの逆算

上のプログラムで行われているフラグの変換は非常にシンプルで、可逆です。そのため、aから逆変換をする関数を作成することでフラグを求められます。

def inv_validate(a):
  xs = [0] * (len(a) - 1)
  for i in range(len(xs)):
    res = -1
    for j in range(1, 128):
      val = (sum(xs) + j) * 69684751861829721459380039
      if poly(a, val) == 24196561:
        res = j
        break
    assert res != -1
    xs[i] = res
  print('FLAG IS:', ''.join(list(map(chr, xs))))

ここは丁寧にプログラムの内容を理解し、逆演算を書きましょう。各文字については全探索して「関数にかけた結果と一致していればOK」という手法を取れば十分です。

FLAG IS: justCTF{this_is_very_simple_flag_afer_so_big_polynomails}

感想

Rev: Easy + Crypto: Easyが混ざっています。