好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

Very smooth (Crypt, 300)

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で開いてみた。 image

主要そうなシーケンス(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さんによると、以下のような方法があるらしい。

他の方の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())

できたprikeywiresharkSSL設定でRSA keys listに登録。
Preferences > Protocols > SSL > RSA keys list
登録しておいて、再度 s.pcap を見てみる。
参考:Qiita/HTTPSのパケットをwiresharkで見てみる > 実際のデータ通信 decoded

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。