LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@e28992

Chap６. Cpaw Level3後編

Posted at

はじめに

CTF学習のため、Cpawというサイトの問題を解いていく記事です。
今回はCpaw最終回ということでLevel3の残り2問を解いていきます。

この記事の対象者

  • CTF超初心者
  • Cpawの問題を解いてみたい人

問題一覧

Q23. [Reversing] またやらかした！

ELFファイル
Level2のQ21でもあったELFファイルなるものを解析して、
暗号を解くプログラムを実行しましょう。

取り組んだ手順
Step1. WSL環境でコマンドの実行 (ファイルの種類確認)
Step2. WSL環境でコマンドの実行 (アセンブラ眺める)
Step3. Python または C++で暗号解く

実行するコマンド(WSL)

拡張子なしはとりあえずfileコマンドで種類確認を行いましょう。

file rev200
実行結果 (一部抜粋)
rev200: ELF 32-bit ... for GNU/Linux 2.6.24

案の定Q21と同じく32bit ELFファイルでしたね。

次にobjdumpコマンド -dオプションで逆アセンブル情報を見てみます。

objdump -d rev200

たくさんの文字列が出てきますが注目したいのは以下の部分です。

実行結果 (一部抜粋)
 80483f5:       c7 45 88 7a 00 00 00    movl   $0x7a,-0x78(%ebp)
 80483fc:       c7 45 8c 69 00 00 00    movl   $0x69,-0x74(%ebp)
 8048403:       c7 45 90 78 00 00 00    movl   $0x78,-0x70(%ebp)
 804840a:       c7 45 94 6e 00 00 00    movl   $0x6e,-0x6c(%ebp)
 8048411:       c7 45 98 62 00 00 00    movl   $0x62,-0x68(%ebp)
 8048418:       c7 45 9c 6f 00 00 00    movl   $0x6f,-0x64(%ebp)
 804841f:       c7 45 a0 7c 00 00 00    movl   $0x7c,-0x60(%ebp)
 8048426:       c7 45 a4 6b 00 00 00    movl   $0x6b,-0x5c(%ebp)
 804842d:       c7 45 a8 77 00 00 00    movl   $0x77,-0x58(%ebp)
 8048434:       c7 45 ac 78 00 00 00    movl   $0x78,-0x54(%ebp)
 804843b:       c7 45 b0 74 00 00 00    movl   $0x74,-0x50(%ebp)
 8048442:       c7 45 b4 38 00 00 00    movl   $0x38,-0x4c(%ebp)
 8048449:       c7 45 b8 38 00 00 00    movl   $0x38,-0x48(%ebp)
 8048450:       c7 45 bc 64 00 00 00    movl   $0x64,-0x44(%ebp)
 8048457:       c7 45 84 19 00 00 00    movl   $0x19,-0x7c(%ebp)

movl：32bitの処理をする命令
movl $0x7a,-0x78(%ebp)：0x7a(ASCII文字 'z')を−0x78アドレスに格納
これらからrev200ではこの辺が結果として得られてそうなことがわかります。
しかしこれの後に出力命令callがないため、flagがわからない状態です。

flag求めるソースコード

【やること】

  1. 0x～を配列に格納する
  2. keyを0x19として設定する
  3. forで配列の長さまでループ
  4. keyと配列のi番目でXORしたものを出力
q23.py
a = []

a.append(0x7a)
a.append(0x69)
a.append(0x78)
a.append(0x6e)
a.append(0x62)
a.append(0x6f)
a.append(0x7c)
a.append(0x6b)
a.append(0x77)
a.append(0x78)
a.append(0x74)
a.append(0x38)
a.append(0x38)
a.append(0x64)

key = 0x19

for i in a:
  # XORする
  print(chr(key^i))
q23.cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a;
    a.reserve(100);

    a.push_back(0x7a);
    a.push_back(0x69);
    a.push_back(0x78);
    a.push_back(0x6e);
    a.push_back(0x62);
    a.push_back(0x6f);
    a.push_back(0x7c);
    a.push_back(0x6b);
    a.push_back(0x77);
    a.push_back(0x78);
    a.push_back(0x74);
    a.push_back(0x38);
    a.push_back(0x38);
    a.push_back(0x64);

    int key = 0x19;

   
    for (size_t i = 0; i < a.size(); ++i) {
        cout << static_cast<char>(key ^ a[i]);
    }
    cout << endl;
    return 0;
}

これによってflagが得られました！

flag 
cpaw{vernam!!}

Q26. [PPC] Remainder theorem

Common Modulus Attackをする問題
Common Modulus Attackについてはこのサイトがわかりやすいと思います。

ざっくり言うと、RSA公開鍵(e1,N), (e2,N)と平文 m がある時、
Nに同じ鍵を使っているとできる攻撃です。

公開鍵
(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)
暗号文
80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904

これは...と書いてある箇所からは問題のNと中身が同じhint.txtをDLできるようです。

公開鍵
(e, N) = (13, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)
暗号文
14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664
求めるソースコードと解説

拡張ユークリッドの互除法はこのサイトとかを参考にしてみてください。

q29.py
# 拡張ユークリッド互除法関数
def excgcd(a, b):
    if(b != 0):
        # 最大公約数gcd求める
        gcd, y, x = excgcd(b, a % b)
        # ax + by = d を満たす係数 (x, y) を計算
        y -= (a // b) * x
        return gcd, x, y
    return a, 1, 0

# Common Modulus Attack
def commonModulusAttack(N, e_1, c_1, e_2, c_2):
    gcd, s_1, s_2 = excgcd(e_1, e_2)
    return (pow(c_1, s_1 ,N) * pow(c_2, s_2,N)) % N

# 公開鍵と暗号文定義
N = 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577
e_1 = 11
c_1 = 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904 
e_2 = 13
c_2 = 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664

m = commonModulusAttack(N, e_1, c_1, e_2, c_2)
print(m)
flag 
cpaw{424311244315114354}

おわりに

Cpaw最終回はLevel3の2問について解説しました。
CTFだけでなく競プロでもそうでしたが知識とアルゴリズムへの理解がないとなかなか厳しいことを痛感しました...。
最後までお付き合いただきありがとうございました！

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?