ページ

2018/02/04

Very smooth (Crypto, 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())

できたprikeyをwiresharkのSSL設定で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。

0 件のコメント:

コメントを投稿