SECCON 2017 online CTF の問題がGitHubで公開されたので、これを後追いでやってみた記事になります。
後追い記事の一覧はこちら
SECCON 2017 online CTF を後追いでみっちりやってみよう!
問題
Very smooth Decrypt index.html from PCAP. Please, submit the flag in the format: "SECCON{" + Answer + "}" * Answer is written in index.html very_smooth_36c055008b945516b9c17e2ecce1c582c184b57c2945bbffba20372a8f9a3449.zip
事前調査
与えられたzipを解凍すると、s.pcap
が出現。
このs.pcap
からindex.htmlをDecryptして、flagを見つけてねということらしい。
pcapなので、Wiresharkで開いてみる。
解法
Wiresharkで開いてみた。
主要そうなシーケンス(info)を抜き出すとこんな感じ。
- [24] Client Hello
- [30] Server Hello, Certificate, Server Hello Done
- [41] Client Hello
- [46] Server Hello, Certificate, Server Hello Done
- [56] Client Hello
- [58] Server Hello, Certificate, Server Hello Done
- [60] Client Key Exchange, Change Cipher Spec, Encrypted Handshake Message
- [62] New Session Ticket, Change Cipher Spec, Encrypted Handshake Message
- [64] Application Data, Application Data
- [66] Application Data, Application Data
- [68] Application Data, Application Data
Application Dataの中に、index.htmlが入っているであろうと思われるので、この通信を見るのがGoal。
SSL/TLSシーケンスの説明は下記が分かりやすかった。
IBM/SSL または TLS ハンドシェークの概要
作戦としては、Application Dataを復号するための鍵を手に入れたいわけだけども
- Application Dataは[60]で交換されたデータ暗号化用の共通鍵で暗号化されている
- この共通鍵のやり取りは、[30]などで通知されたサーバーの公開鍵で暗号化されている
ので、さかのぼって[30]などのServer Helloのシーケンスから紐解く必要がある。
まずはサーバー証明書を抜き出してみる。[30]の通信をターゲットに、下記を参考にして実施
ここでExport Packet Bytes
して得られたサーバー証明書がちゃんとexportできたか確認
(exportしたファイルはserver.bin
-> server.der
とrenameして保存)
$ openssl x509 -inform der -in server.der -text Certificate: Data: Version: 1 (0x0) Serial Number: a1:8b:63:0c:7b:30:99:df Signature Algorithm: sha256WithRSAEncryption Issuer: C=JP, ST=Kawasaki, O=SRL Validity Not Before: Oct 8 02:47:17 2017 GMT Not After : Oct 8 02:47:17 2018 GMT Subject: C=JP, ST=Kawasaki, O=SRL Subject Public Key Info: Public Key Algorithm: rsaEncryption RSA Public Key: (1024 bit) Modulus (1024 bit): 00:d5:46:aa:82:5c:f6:1d:e9:77:65:f4:64:fb:fe: 48:89:ad:8b:f2:f2:5a:21:75:d0:2c:8b:6f:2a:c0: c5:c2:7b:67:03:5a:ec:19:2b:37:41:dd:1f:4d:12: 75:31:b0:7a:b0:12:eb:86:24:1c:09:c0:81:49:9e: 69:ef:5a:ea:c7:8d:c6:23:0d:47:5d:a7:ee:17:f0: 2f:63:b6:f0:9a:2d:38:1d:f9:b6:92:8e:8d:9e:07: 47:fe:ba:24:8b:ff:df:f8:9c:df:af:47:71:65:89: 19:b6:98:1c:9e:14:28:e9:a5:34:25:ca:2a:31:0a: a6:d7:60:83:31:18:ee:0d:71 Exponent: 65537 (0x10001) Signature Algorithm: sha256WithRSAEncryption 78:92:11:fb:6c:e1:7a:f7:2a:33:b8:8b:08:a7:f7:5b:de:cf: 62:0b:a0:ed:be:d0:69:88:38:93:94:9d:05:41:73:bd:7e:b3: 32:ec:8e:10:bc:3a:62:b0:56:c7:c1:3f:60:66:a7:be:b9:46: f7:46:22:6a:f3:5a:25:d5:66:94:57:0e:fc:b5:16:33:05:1c: 6f:f5:85:74:57:a4:a0:c6:ce:4f:fd:64:53:94:a9:83:b8:96: bf:5b:a7:ee:8b:1e:48:a7:d2:43:06:0e:4f:5a:86:62:69:05: e2:c0:bd:4e:89:c9:af:04:4a:77:a2:34:86:6a:b8:d2:3b:32: b7:39 -----BEGIN CERTIFICATE----- MIIB0zCCATwCCQChi2MMezCZ3zANBgkqhkiG9w0BAQsFADAuMQswCQYDVQQGEwJK UDERMA8GA1UECAwIS2F3YXNha2kxDDAKBgNVBAoMA1NSTDAeFw0xNzEwMDgwMjQ3 MTdaFw0xODEwMDgwMjQ3MTdaMC4xCzAJBgNVBAYTAkpQMREwDwYDVQQIDAhLYXdh c2FraTEMMAoGA1UECgwDU1JMMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDV RqqCXPYd6Xdl9GT7/kiJrYvy8lohddAsi28qwMXCe2cDWuwZKzdB3R9NEnUxsHqw EuuGJBwJwIFJnmnvWurHjcYjDUddp+4X8C9jtvCaLTgd+baSjo2eB0f+uiSL/9/4 nN+vR3FliRm2mByeFCjppTQlyioxCqbXYIMxGO4NcQIDAQABMA0GCSqGSIb3DQEB CwUAA4GBAHiSEfts4Xr3KjO4iwin91vez2ILoO2+0GmIOJOUnQVBc71+szLsjhC8 OmKwVsfBP2Bmp765RvdGImrzWiXVZpRXDvy1FjMFHG/1hXRXpKDGzk/9ZFOUqYO4 lr9bp+6LHkin0kMGDk9ahmJpBeLAvU6Jya8ESneiNIZquNI7Mrc5 -----END CERTIFICATE-----
おお、できたできた。(実はここでうまくexportできなくてハマった。wireshark再インストールでうまく行った・・・)
ここで、server証明書の秘密鍵が入手できると、wiresharkなどのツールを利用してserverから降らせるデータを復号状態で見ることができる。
ということは、その秘密鍵をwiresharkに登録してApplication Dataのところを見ればフラグ(もしくはそのヒント)が出てくるはず。
この証明書から公開鍵を抜き出すのは、下記コマンドでちゃっとできる。
$ openssl x509 -in server.der -inform der -pubkey > server.pub
が、秘密鍵はもちろん抜き出すことはできない。
さてどうしよう。
RSAであることがわかっているのでとりあえず
RSA
,smooth
でググってみる。タイトル大事。
こんなサイトがヒット。
日本語の論文の方の概要を読んでみる。初心者にはありがたい。
合成数の中で、すべての素因数が pk 以下になる数を pk-smooth という.
ということで、英訳のalcさんでも smooth numberで調べると
どの素因数も一定の数以下である数
という解説が。どうやら素因数分解できるっぽい、と当たりをつける。
RSAの仕組みはPs and Qsのときに調査したので
まずは
- RSA modulus (n)
- Public exponent (e)
を証明書から抽出。
modulus N は下記で取り出せる。
$ openssl x509 -inform der -in server.der -modulus > modulus $ cat modulus Modulus=D546AA825CF61DE97765F464FBFE4889AD8BF2F25A2175D02C8B6F2AC0C5C27B67035AEC192B3741DD1F4D127531B07AB012EB86241C09C081499E69EF5AEAC78DC6230D475DA7EE17F02F63B6F09A2D381DF9B6928E8D9E0747FEBA248BFFDFF89CDFAF4771658919B6981C9E1428E9A53425CA2A310AA6D760833118EE0D71 ~ 略 ~
Public exponentは証明書の中に使える形(integer)での記載があるので
Exponent: 65537
さぁ、次はなんとかp,qを求めたいがどうしよう。
Ps and Qsのように、複数鍵が与えられているわけではないので、この方法は使えない。
上述のFactHacksさんによると、以下のような方法があるらしい。
- Batch trial division.
- Sieving.
- The rho method.
- The p-1 method.
- The elliptic-curve method.
- Early aborts, a way of combining all of the above methods.
他の方のwrite-upを読んだり、リンクの中身を見た結果、p-1法が良さそう。
リアルタイムのヒント無しだと、ここで詰まっただろうなぁ。
可能性の有りそうなやつをひたすら試すのだろうか。
素因数分解
,p-1
でググるとこんな解説記事が。流し読みする文には一番分かりやすかった。※それでもなんとなくしか理解できていないのだけども。。。汗
Pebble Coding/ポラードのp-1因数分解法
更に、BASIC言語で書かれたスクリプトとセットの解説も発見
Computer数論
この記事を参考に、pythonに起こしてみた。
p-1.py
#!/usr/bin/env python3 from math import gcd modulus = 'D546AA825CF61DE97765F464FBFE4889AD8BF2F25A2175D02C8B6F2AC0C5C27B67035AEC192B3741DD1F4D127531B07AB012EB86241C09C081499E69EF5AEAC78DC6230D475DA7EE17F02F63B6F09A2D381DF9B6928E8D9E0747FEBA248BFFDFF89CDFAF4771658919B6981C9E1428E9A53425CA2A310AA6D760833118EE0D71' N = int(modulus, 16) seed = 2 # seedは通常2か3, うまく分解できなかったときに動かす B = 100000 # B-smoothと仮定する 通常100000まで a = seed G = 1 cnt = 0 M = 1 while(G<=1): M = M + 1 if M >= B: break if M % 10000 == 0: print("M=" + str(M)) a = pow(a, M, N) G = gcd(a-1, N) if G > 1 and G < N: print("factor is " + str(G) + ", M = " + str(M)) else: print("try new seed") print("p: " + str(G)) print("q: " + str(N//G))
実行結果
$ python p-1.py factor is 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001, M = 400 p: 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 q: 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
おお、分解できたっぽい。良かったよかった。実行時間一瞬(計測はしていない)
※ここまでに、自然言語でのシーケンスからコードを起こしてみたりしたがうまく動かず。他言語でも動くサンプルがあって助かった!
あとは、Ps and Qsのときと同じように秘密鍵を生成する。
上のscriptに以下を追加して実行
from Crypto.PublicKey import RSA from Crypto.Util.number import inverse ~~~~ 上記script ~~~~ E = 65537 p = G q = N//G d = inverse(E, (p-1)*(q-1)) key = RSA.construct(map(int, (N, E, d))) open("prikey", "bw").write(key.exportKey())
できたprikey
をwiresharkのSSL設定でRSA keys listに登録。
Preferences > Protocols > SSL > RSA keys list
登録しておいて、再度 s.pcap を見てみる。
参考:Qiita/HTTPSのパケットをwiresharkで見てみる > 実際のデータ通信
decodeされた通信内容が出てきているのがわかる。やった!
[68]の通信で、HTMLをサーバーから返却しているので、そこの中をドリルダウン。
Line-based text data に下記を発見。
<html> <head><title>Very smooth</title></head> <body> <h1> Answer: One of these primes is very smooth. </h1> </body> </html>
うーん、flagのformatではないような・・・と思って問題文を見てみると、
Please, submit the flag in the format: "SECCON{" + Answer + "}"
とのことなので、これが答えでOK。