SECCON BeginnersCTF 2018 に参加したので wite-upを書いたけど 解けなかった問題が多かったしコンテスト環境しばらく残していただけるそうなので、後追いでやってみる。（ほぼ大会中の話だったりする）
write-upはこちら kusuwada.hatenablog.com
[Crypto] Well Known
実は、大会参加当初「スコア」と「解けた人数」を逆に読んでいて、これが一番簡単な問題だと勘違いして最初に取り組んでしまった。
「え〜！Beginnersってこんなにレベル高いの〜！\@@/」と驚愕した苦い思い出。
問題
nc crypt1.chall.beginners.seccon.jp 31337
この文言と、下記のスクリプトが配布される。
server_75765ff6d20242c799334a98745fde1a782d93ef.py
import hashlib import sys import random from Crypto.Util.number import * from socketserver import ThreadingTCPServer, BaseRequestHandler from flag import FLAG class Signer: def __init__(self, L, N): self.q = getPrime(N) while True: self.p = self.q * random.getrandbits(L - N) + 1 if isPrime(self.p): break self.g = pow(2, (self.p - 1) // self.q, self.p) self.x = bytes_to_long(FLAG) self.y = pow(self.g, self.x, self.p) assert(self.x < self.q) def sign(self, m, k): r = pow(self.g, k, self.p) % self.q s = inverse(k, self.q) * (m + self.x * r) % self.q if s == 0: raise ValueError return (r, s) class Handler(BaseRequestHandler): def handle(self): key = Signer(2048, 256) rnd = random.getrandbits(64) self.request.sendall(bytes('p = {:d}\n'.format(key.p), 'ascii')) self.request.sendall(bytes('q = {:d}\n'.format(key.q), 'ascii')) self.request.sendall(bytes('g = {:d}\n'.format(key.g), 'ascii')) try: for i in range(3): self.request.sendall(b'Input your data (in hex):\n') data = long_to_bytes(int(self.request.recv(4096), 16)) k = pow(int(hashlib.sha1(data).hexdigest(), 16), rnd, key.q) h = int(hashlib.sha256(data).hexdigest(), 16) r, s = key.sign(h, k) self.request.sendall(bytes('r = {:d}\n'.format(r), 'ascii')) self.request.sendall(bytes('s = {:d}\n'.format(s), 'ascii')) except ValueError as e: self.request.sendall(bytes('Invalid value\n', 'ascii')) else: self.request.sendall(b'Bye.\n') if __name__ == '__main__': host = 'localhost' port = 31337 if len(sys.argv) >= 3: host = sys.argv[1] port = int(sys.argv[2]) s = ThreadingTCPServer((host, port), Handler) print('Listening at {}:{:d}'.format(host, port)) s.serve_forever()
まずは問題で指示された通りに叩いてみる。
$ nc crypt1.chall.beginners.seccon.jp 31337 p = 16679194083198950687969733986499924699835997894294807759601033231804550956076926394797958147206191858229465423843797136657860397100060653518514490788419250294275491646689139382741390885296209825510705565868543061881083043043446628516620883906294950391487746915826124373185188216150387558662775769805286515637408175762133603376999884676209361588612724070528494953605301744960179010609458234176550274930122827013540894528488276643059847223625821679882670154250268515234794527153017169583443601216000572420740097190510158670349989667726985760572138710696259607237091420821807056064853023532483648815991497848164747218929 q = 88967137731772648680425587173543061937973706623745105800741828685065752059867 g = 2205575219328681268586322263126158959805960545859875072720447872093269479444559630062394304494512448143523042089258619254204423242110599833444688328880935733612320348258085635290937281673030516545903041256327133878336387195428156600554101046621249609008064639306760200339500602176359940601289972850543735490094373239473342539256157264072918742944223085712953032309226874913361238483889448772032982320710296503313274066005155266183857629778883344435324830986829674201862988844232482517447003175462357914024090662173310667023410075095146627467896921016941051525444471914371051245117060842426553215352438575834348924616 Input your data (in hex): 12345 r = 40828681631463504478382954483613162276884884947495108827950662396476002595694 s = 81611600999760781997753154103325664950514841785927178244267137306488179262101 Input your data (in hex): 12345 r = 40828681631463504478382954483613162276884884947495108827950662396476002595694 s = 81611600999760781997753154103325664950514841785927178244267137306488179262101 Input your data (in hex): 6789 r = 46193120177709971851216730451461478989786841190546052989867921595000217230354 s = 56965693442241505124643039470781438264846837285047428812376957962077866760912 Bye.
3回適当にhexを入力すると終了。
何をしていいかさっぱりわからないので、まずは配布されたスクリプトを読んでみる。
サーバーで動作しているものと思われ、flagを使用して署名をしている。
Handler.handleが入力を処理しているところなのでそこを見てみる。
key = Signer(2048, 256) ・・・ self.request.sendall(bytes('p = {:d}\n'.format(key.p), 'ascii')) self.request.sendall(bytes('q = {:d}\n'.format(key.q), 'ascii')) self.request.sendall(bytes('g = {:d}\n'.format(key.g), 'ascii'))
ということで、keyはその前に定義されているSignerクラスのオブジェクト。表示されたp,q,gは環境に接続したときに毎回ランダムに作られる（と思ったんだけど何度接続しても同じだった）Signerオブジェクトの変数。
その下のループで、入力したデータのダイジェストを計算して作成したSignerオブジェクトで署名している。
k = pow(int(hashlib.sha1(data).hexdigest(), 16), rnd, key.q) h = int(hashlib.sha256(data).hexdigest(), 16) r, s = key.sign(h, k)
なぜ3回入力させるのか？そしてなぜダイジェスト計算でsha1とsha256が混合して使われているのか？と疑問が。というかsha1怪しい。
問題タイトルが Well Known とのことなので、なにか有名なアルゴリズムとか脆弱性なのか？と思って調べてみる。
調べようにもなんのワードで引っ掛けたらよいかわからぬ。
Signer というワードから、電子署名っぽいというのと、Signerクラスの変数名がアルゴリズム解説と一致しているのを期待して、signer algorithm p q g x yでググってみるなど。
Wikipedia様がHitしました！解説に載っている数式も気持ちいいくらい配布スクリプトの内容と一致。
日本語のWikiもありました。
Digital Signature Algorithm(日本語)
ぱっと目次を見て気になったのは 5 ランダム値の選択方法と安全性 の項。（2018年5月26日現在）
DSAにとって、署名の際のランダム値 k のエントロピー、機密性、唯一性は決定的に重要である。これら3つのうちの1つが破られることは、攻撃者に対して秘密鍵そのものが明かされることと等しい[8]。k として同じ値を二度用いること（k を秘密にしていたとしても）、予測可能な値を用いること、複数の署名に対するそれぞれの k が数ビットであっても漏洩することは、DSAを破るには十分である[9]。
kとして同じ値を二度用いると、DSAを破るには十分である、そうである。
kといえば、ちょうどさっき "なぜsha1?" と思ったところだ。
sha1だと衝突を起こしてダイジェストkが同一の値になるが、sha256は異なるようなデータを入力すると、(r,s)のセットが2パターン得られて秘密鍵xが解けるのかな。
sha1衝突といえば、前回のSECCON online予選でやったぞ。
これのSHA-1 is dead (Crypto) 100で利用した PDF1, PDF2を再度利用させていただく。
まずはPDF1, PDF2を下記から取得。1.pdf,2.pdfとして保存。
SHA-1ハッシュの衝突を現実的な時間で生成する攻撃「Shatterd」 文中のリンク PDF1 / PDF2 より
今回は特にdataの長さの指定はない(srcから4096byteで切られるようだが)ので、
先頭320バイトの部分で衝突が起きていてそれ以降が同じ値ならずっと衝突し続けるとのことです
先頭320バイトのデータだけで十分そう。
sha1衝突のpdfファイルたちの、先頭320バイトをhexにして出力。ついでにsha1衝突かどうかを確認。
#!/usr/bin/env python3 # -*- coding:utf-8 -*- import hashlib from Crypto.Util.number import * with open('1.pdf', 'rb') as f: data1 = (f.read()[:320]).hex() print('-------[data1]--------') print(data1) print('-------[len(data1), sha1(data1)]--------') print(len(data1)) print(hashlib.sha1(long_to_bytes(int(data1, 16))).hexdigest()) with open('2.pdf', 'rb') as f: data2 = (f.read()[:320]).hex() print('--------[data2]-------') print(data2) print('--------[len(data2), sha1(data2)]-------') print(len(data2)) print(hashlib.sha1(long_to_bytes(int(data2, 16))).hexdigest())
実行結果
$ python sha1_coll.py -------[data1]-------- 255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1 -------[len(data1), sha1(data1)]-------- 640 f92d74e3874587aaf443d1db961d4e26dde13e9c --------[data2]------- 255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1 --------[len(data2), sha1(data2)]------- 640 f92d74e3874587aaf443d1db961d4e26dde13e9c
うん、データそのものは異なっていて、sha1は一致しているようだ。
これらの値を入力してみる。
ちなみに、r の計算は
r = pow(self.g, k, self.p) % self.q
ということで、k が同じ場合は同じ値が返るはず。
s の計算は
s = inverse(k, self.q) * (m + self.x * r) % self.q
で、sha256を使って出したダイジェストも使っているので、異なる値が返るはず。
$ nc crypt1.chall.beginners.seccon.jp 31337 p = 16679194083198950687969733986499924699835997894294807759601033231804550956076926394797958147206191858229465423843797136657860397100060653518514490788419250294275491646689139382741390885296209825510705565868543061881083043043446628516620883906294950391487746915826124373185188216150387558662775769805286515637408175762133603376999884676209361588612724070528494953605301744960179010609458234176550274930122827013540894528488276643059847223625821679882670154250268515234794527153017169583443601216000572420740097190510158670349989667726985760572138710696259607237091420821807056064853023532483648815991497848164747218929 q = 88967137731772648680425587173543061937973706623745105800741828685065752059867 g = 2205575219328681268586322263126158959805960545859875072720447872093269479444559630062394304494512448143523042089258619254204423242110599833444688328880935733612320348258085635290937281673030516545903041256327133878336387195428156600554101046621249609008064639306760200339500602176359940601289972850543735490094373239473342539256157264072918742944223085712953032309226874913361238483889448772032982320710296503313274066005155266183857629778883344435324830986829674201862988844232482517447003175462357914024090662173310667023410075095146627467896921016941051525444471914371051245117060842426553215352438575834348924616 Input your data (in hex): 255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1 r = 45636497678086998881845417361785561409002743759730253294845457878442077404117 s = 59869305831594119091671905874461214249942153377099541166865700237879370926497 Input your data (in hex): 255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1 r = 45636497678086998881845417361785561409002743759730253294845457878442077404117 s = 17471558266643008894268466156956264226686761140595728320042874512081458751297
期待通りの結果が帰ってきた！
あとは、self.x の値を導くのみ。
そして、なんと先程のDSAのWikipediaから、直接使えそうな数式の載っているサイトにリンクが貼ってある。
数式抜粋
kの導き方
xの導き方
ここと配布されたスクリプトの数式を参考にしながら self.x が導けそう！これは・・・イケる！
・・・
・・・
・・・
というところまでいったのだが、解けなかった( ▔•з•▔ )
極端に小さい数値になったり、文字列変換できなかったり。
何処かで間違ったかなー。うーん、と悩むもタイムアップでした。
後追いでじっくり考えてみる。
ちょっと上で見つけた k を導く数式に囚われすぎていたかもしれない。配布スクリプトの方をしっかり読んで解こう。
と、スクリプトとリンク先の数式をにらめっこしたところ、間違い判明。数式側の k^-1 などの表記は、 1/k ではなく、 Crypto.Util.number.inverse(k, q) すなわち 1/(k % q) と置き換えて読むのが正しい。
それを意識して解くとフラグが出てきた。スクリプトのコメント部分に式展開が。剰余計算式ムズカシイ。
#!/usr/bin/env python3 # -*- coding:utf-8 -*- import hashlib from Crypto.Util.number import * p = 16679194083198950687969733986499924699835997894294807759601033231804550956076926394797958147206191858229465423843797136657860397100060653518514490788419250294275491646689139382741390885296209825510705565868543061881083043043446628516620883906294950391487746915826124373185188216150387558662775769805286515637408175762133603376999884676209361588612724070528494953605301744960179010609458234176550274930122827013540894528488276643059847223625821679882670154250268515234794527153017169583443601216000572420740097190510158670349989667726985760572138710696259607237091420821807056064853023532483648815991497848164747218929 q = 88967137731772648680425587173543061937973706623745105800741828685065752059867 g = 2205575219328681268586322263126158959805960545859875072720447872093269479444559630062394304494512448143523042089258619254204423242110599833444688328880935733612320348258085635290937281673030516545903041256327133878336387195428156600554101046621249609008064639306760200339500602176359940601289972850543735490094373239473342539256157264072918742944223085712953032309226874913361238483889448772032982320710296503313274066005155266183857629778883344435324830986829674201862988844232482517447003175462357914024090662173310667023410075095146627467896921016941051525444471914371051245117060842426553215352438575834348924616 data1 = "255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1" r = 45636497678086998881845417361785561409002743759730253294845457878442077404117 s1 = 59869305831594119091671905874461214249942153377099541166865700237879370926497 data2 = "255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1" s2 = 17471558266643008894268466156956264226686761140595728320042874512081458751297 h1 = int(hashlib.sha256(long_to_bytes(int(data1, 16))).hexdigest(), 16) h2 = int(hashlib.sha256(long_to_bytes(int(data2, 16))).hexdigest(), 16) # s1 - s2 = inverse(k, q) * (h1 - h2) # (s1 - s2) % q = inverse(k, q) * (h1 - h2) % q # inv((s1 - s2), q) = (k % q) / ((h1 - h2) % q) # inv((s1 - s2), q) = k / ((h1 - h2) % q) k = inverse((s1 - s2), q) * (h1 - h2) % q x = ((s1 * k) - h1) * inverse(r, q) % q print(x) print(bytes.fromhex(format(x,'x')).decode('utf-8'))
実行結果
2438621768693917430306159260440359572892614488672778021757
ctf4b{be_c4reful_w1th_k}
