[ksnctf] HTTPS is secure

11th Oct 2016

ksnctfにチャレンジ第33問目です。

※ksnctfは常駐型のCTFサイトです。 ※問題のページはコチラです。

HTTPS is secure

httpsでの通信をキャプチャした pcap が渡されるのでこれを解析します。

まず SSLで証明書がやり取りされている TLSv1 Certificate　が2箇所にあるのでを探しだし、通信内容の Secure Sockets Layer > Certificate > Certificate (id-at-commonName=chihiro/kei〜) を　Export Selected packet Bytes　しておきます。

ここで

$  openssl x509 -in (書きだしたファイル) -inform DER -text -noout

すると公開鍵をみることができます。

Modulus に表示されているのがそれです。 Exp = 65537 になっているのもちらっと確認しておきます。

今、2名に発行された公開鍵が２つ手にはいりましたが、通信を覗くためには　それぞれの秘密鍵が必要で公開鍵だけから秘密鍵を求めるのは基本的には無理なのでここで作業がとまります。

しかし、今回は

Hint: Two certificates are similar.

というヒントがあり、証明書が似通っている　ということなのでこの意味を考えると　秘密鍵に使われている　素数のペアの内片方を共有している可能性がありそうです。

通常　公開鍵を素因数分解するのは難しいですが同じ因数を持つ2数があるなら　それはユークリッドの互除法で最大公約数 = ２つの公開鍵が共有する素数　を求めることができます。

MathⅠで作った拡張ユークリッドを再利用して

class Euclid
 ~~ 略 ~~
end

euclid = Euclid.new()

pub1 = 0x00a5a7ce44462e8ac6e4da5e8a8d58e003b8267568b358106cf06412884ceeb7cc4251c2cce2db74689d1afa109bde9762402e81d96cb6c8c6c5aebc8d45a96bf214a618b499a8c6134035c5039bf9a39bc47190e4cc4560cb75ab8d63635cdee8e50f5815b29180cc51a4c8cf76a8bbe6e61c68aca385fdf99e712b10a6be7ed794cf27540b7aa00f59da5579040a9b3b7c23e9e22a15c29eb0c060b96d1f48d1c458e2c412512962ce5af885237b6138df6c9e85d101c266c3b80b02ff97d6fde46598e19e3fa1df2c56bd34addfe716569a2ed42c6442bf2db5e9a51cc2d7dd4497717ddd9a8a66ae281e1a2abf7df7a59779b499cc0f8167a19e3ca5c9bbe3
pub2 = 0x00a4daad49eae0b5c59da0452978ae987e1b96f149dedb62274c97f99ac4544aa90db4aaf9a0967f118b7009097bcb0baeb4a19636777a7747e06ad84496c9c61d18a7b5ca776585a817526ed6d9f0f2abd8c434c62cbf025eb7ce5a83e4a7f9938f3862de24e6292f43270ffda757c17aaa797ff9fe18fd1cb23921dc585d4550384ff5c4f24e6dfc6d4f44b569345808239247c20d266cd0f5e373889ed4e459590b7d742d2837c1c48dcf9418e22191ab4a0bca0ed79b1d45c0ca5d36ea6960c9360c11412329fd5d90ff3467f2d82e23021adf3b6d8be24903b76effc938154ec219f344118f1c41fec31171b62945a07e35762a961a05795389086052dec7
p = euclid.exgcd(pub1,pub2)
q1 = pub1/p
q2 = pub2/p
e = 65537

puts '1:(p,q) = ('+ p.to_s(10) + ',' + q1.to_s(10) + ')'
puts '2:(p,q) = ('+ p.to_s(10) + ',' + q2.to_s(10) + ')'

2つの共有鍵から　素数のペアを2つ計算することができました。